Was würden Sie erhalten, wenn Sie kontextfreie Grammatiken mit Parametern versehen?

13

Ich dachte an Grammatiken für indendationssensitive Sprachen und es sieht so aus, als würden CF-Grammatiken in Kombination mit Parametern den Trick machen. Betrachten Sie als Beispiel dieses Fragment für eine vereinfachte Python-Grammatik im ANTLR-ähnlichen Format:

// on top-level the statements have empty indent
program  
    : statement('')+
    ;

// let's consider only one compound statement and one simple statement for now
statement(indent) 
    : ifStatement(indent)
    | passStatement(indent)
    ;

passStatement(indent)
    : indent 'pass' NEWLINE
    ;

// statements under if must have current indent plus 4 spaces
ifStatement(indent)
    : indent 'if' expression ':' NEWLINE (statement(indent '    ')+)
    ;

Meine Frage: Hat diese Art von Grammatik (CFG mit Parametern) einen Namen?

Es sieht so aus, als ob es nicht schwierig wäre, einen rekursiven Abstiegsparser für diese Grammatik zu schreiben (Parameter sollten im Grunde Parser sein). Was könnten die Schwierigkeiten bei diesem Ansatz sein?

Erhöht das Hinzufügen von Parametern die unterstützte Sprachklasse über kontextfrei?

Aivar
quelle
1
Wenn die Menge der Werte, die die Parameter annehmen können, endlich ist, ist sie noch immer trivial kontextfrei (Sie können dann alle Werte durchlaufen und alles ausschreiben).
Ratschenfreak
1
Erwähnenswert ist, dass Ihr Vorschlag einrückungssensitive Sprachen mit fester Einrückung betrifft. Python (und andere solche Sprachen) sind auf diese Weise nicht eingeschränkt. Sie akzeptieren alle vom Benutzer gewünschten Einrückungen. Dies wirkt sich nicht auf die Syntaxanalyse aus (mit Ausnahme des Umgangs mit Tabulatorzeichen), aber es wäre schwierig, Ihren Vorschlag auszudrücken, zumindest so, wie ich es verstehe.
rici
Attribut Grammatiken
Hendrik Jan
@HendrikJan, Attributgrammatiken sind eine Möglichkeit, Grammatik mit semantischen Aktionen zu kommentieren. Sie steuern das Parsen nicht.
AProgrammer
1
Wenn das Ziel darin besteht, Einrückungen zu verarbeiten, ist dies eher für den Tokenizer als für den Parser geeignet. Lassen Sie den Tokenizer virtuelle INDENT- und UNINDENT-Token ausgeben, wenn sich die Einrückungsstufe ändert. In diesem Fall müssen Sie die Sprachgrammatik nicht um Informationen zum Einrücken erweitern.
John Kugelman

Antworten:

14

Affix-Grammatiken (parametrisierte kontextfreie Grammatiken) wurden vom angesehenen niederländischen Informatiker Cornelis HA Koster ausgiebig untersucht , beginnend mit seiner 1962 erschienenen Arbeit "Basic English, eine generative Grammatik für einen Teil des Englischen", die gemeinsam mit der LGLT Meertens verfasst wurde. 1970 produzierte er einen Formalismus des Konzepts; Einen nützlichen Überblick bietet sein 1971 erschienener Aufsatz "Affix Grammatics for Programming Languages", dessen Version ich bei Citeseer gefunden habe .

In diesem Aufsatz vergleicht Koster seinen Formalismus (und einen ähnlichen) mit den zweistufigen Grammatiken von Van Wijngaarden und findet, dass sie sehr ähnlich sind.

Dick Grunes wertvolle kommentierte Bibliographie zu Parsing-Techniken enthält eine Vielzahl weiterer nützlicher Referenzen für Affix-Grammatiken und andere nicht-chomskysche Formalismen. (Siehe Abschnitt 18.2.6 der Bibliographie, obwohl es in anderen Abschnitten nützliche Dokumente gibt.) Grune behandelt das kurze Anbringen von Grammatiken in §15.3.2 der zweiten Ausgabe von Parsing Techniques: A Practical Guide (und noch kurz in der ersten Ausgabe) (online verfügbar) unter Hinweis auf die Tatsache, dass es einfach ist, Top-Down- (und andere) Analysetechniken anzupassen.

einnbncn

Koster, der auch Redakteur des Algol 68-Berichts war, war der ursprüngliche Entwickler der Compiler Description Language (CDL) , basierend auf seinen Ideen zu Affix-Grammatiken. Dieses Toolkit und seine späteren Derivate wurden viele Jahre lang in der Produktion eingesetzt. Diese Seite , die ich mit einer Google-Suche gefunden habe und deren Beständigkeit ich nicht garantieren kann, enthält Links zum Handbuch und zur Download-Site für CDL3.

rici
quelle
Ich glaube, die CDL-Sprachen ähneln eher Attributgrammatiken : Die Werte der Attribute können durch extern definierte Funktionen berechnet werden. Ich würde den Namen reservieren Affix Grammatik für Fälle , in denen die Beziehungen zwischen den Werten der Affixe (Attribute) innerhalb des Formalismus definiert sind, wie in Erweiterte Affix - Grammatiken .
Reinierpost
@reinierpost: Sie haben selbstverständlich Anspruch auf Ihre eigene Terminologie; Das Privileg ist nicht auf anthropomorphe Eier beschränkt. Das CDL-Handbuch selbst behauptet jedoch, dass "CDL3 eine Implementierungssprache ist, die auf Affix-Grammatiken basiert", was meines Erachtens berücksichtigt werden sollte. (Handbuch verfügbar unter ftp.cs.kun.nl/pub/cdl3/cdl3-manual-1.2.7.pdf ). Das habe ich in meiner Antwort behauptet: Diese CDL basierte auf Kosters Arbeit über Affix-Grammatiken. Wie Grune betont, ist der Unterschied zwischen der Affix- und der Attributgrammatik gering. seine Unterscheidung ist, ob die Affixe verwendet werden, um die syntaktische Gültigkeit zu bestimmen.
rici
(Das Zitat stammt von der ersten Seite des Handbuchs.)
rici
Ich weiß ... und du hast recht. Mein Kommentar sollte Ihnen nicht widersprechen.
Reinierpost
6

Nehmen Sie das Pumplemma für CFGs :

Nimm die Grammatik

S -> A("")
A(p) -> p 
      | p '\n' A(p"*") '\n' p 

Dies beschreibt ein Sternendreieck:

*
**
***
**
*

uvwxy{uvnwxny|n>0}vx

Dies bedeutet, dass das Sternendreieck keine kontextfreie Sprache ist.

Oder ein einfacheres Beispiel:

S-> B("")
B(p)-> p 'a' p 'a' p
     | B(p 'b')

{bneinbneinbn|n0}

Ratschenfreak
quelle
3

Ich habe diesen Formalismus noch nie gesehen (auch nicht in Grunes Parsing-Techniken ). Abhängig von den Details, wie Sie genau definieren, "Parameter sollten im Grunde Parser sein", sieht es für van Wijngaardens Grammatiken mit zwei Niveaus, die die gleiche Kraft haben wie aus Uneingeschränkte Phasenstruktur-Grammatik (dh leistungsfähiger als kontextsensitiv, Sie könnten eine VW-Grammatik schreiben, die alle Halteprogramme enthält).

Ein Programmierer
quelle
Koster und seine Gruppe haben, soweit mir bekannt ist, zwei Arten von Zusatzgrammatiken untersucht: 1) eingeschränkte Formen von Van Wijngaarden-Grammatiken, die eine leichtere Erkennung ermöglichen sollen; 2) die CDL-Sprachen, praktische Compiler-Beschreibungssprachen ohne explizite Manipulation von Zusatzwerten, aber mit der Option, Regeln in der Zielsprache (z. B. Assembler) zu definieren, um sie zu vervollständigen.
Reinierpost