Eine Notation für leere rechte Seiten der Regeln

Question

Wenn Sie eine ("theoretische") Grammatik mit einer Regel mit einer leeren rechten Seite schreiben, verwenden Sie immer ein Symbol wie ε (oder 1), um diese Leerstelle explizit zu machen :

A → ε | a A 

eine solche Grammatik in Yacc und andere aussehen würde dann wie

a: | 'a' a 

oder "schlechter"

a:  { $$ = new_list(); } 
| a 'a' { $$ = $1; $$->append($1); } 
; 

Die Tatsache, dass in "Realwelt-Grammatiken" (Yacc, Bison usw.) dieser leere rechte Teil der Regel nicht explizit als leer markiert ist, beunruhigt mich: Es ist leicht zu übersehen, dass ein rhs leer ist, oder schlimmer : vergessen | einzusetzen und verwenden tatsächlich eine Aktion Mitte der Regel:

a:  { $$ = new_list(); } 
    a 'a' { $$ = $1; $$->append($1); } 
; 

1) ich von Werkzeug nicht wissen, dass sie zu einem leeren rhs explizit machen bietet. Sind da irgendwelche?

Zukünftige Versionen von Bison unterstützen möglicherweise ein dediziertes Symbol mit Fehlern, wenn es in einer nicht leeren rhs verwendet wird, und Warnungen, wenn eine implizit leere rhs übrig ist.

2) Halten die Leute das für nützlich?

3) Welche Schreibweise würden Sie vorschlagen?

Derzeit ist der Kandidat $empty:

a: $empty { $$ = new_list(); } 
| a 'a' { $$ = $1; $$->append($1); } 
; 

EDIT

Die gewählte Syntax ist %empty:

a: %empty { $$ = new_list(); } 
| a 'a' { $$ = $1; $$->append($1); } 
; 

Tat $empty sieht aus wie ein pseudo-Symbol, wie $accept dass Bison generiert für die erste Regel oder die $@n Pseudosymbole für Mid-Regel-Aktionen oder $eof für, nun, Ende der Datei. Aber es ist definitiv kein Symbol, es ist gerade die Abwesenheit von Symbolen.

Auf der anderen Seite bezeichnet % eindeutig eine Direktive (irgendeine Art von Attribut/Metadaten), wie %pred.

Es ist also ein kleiner Unterschied der Syntax, aber es ist mehr konsistent mit der Gesamtsyntax. Der Dank geht an Joel E. Denny.

Answer 1

Ich habe epsilon selbst verwendet, sowie Variationen über für leere Produktionen, an die ich etwas Code in geschweiften Klammern anschloss.

Ein reserviertes Symbol in der Bison-Grammatik wäre nützlich; Ich mag das vorgeschlagene $ Präfix, um Kollisionen mit benutzerdefinierten Symbolen zu vermeiden.

Answer 2

1) Nun gibt es die offensichtliche

 
e: a 'b' 
a: 'a' 
| empty 
empty: 

2) Ja, das wäre sehr hilfreich sein.

3) Die $accept, $end und $undefined Symbole immer definiert sind, und für Bison internen Gebrauch ausschließlich (zB vorbehalten., Können sie nicht in der Grammatik erscheinen). Bison generiert $@n für Mid-Rule-Aktionen, aber diese können auch nicht in der Grammatik des Benutzers verwendet werden.

Das einzige vordefinierte Token, das der Benutzer in der Grammatik verwenden kann, wenn ich mich nicht irre, ist error. Warum schlagen Sie nicht empty für dieses dedizierte Symbol vor? Das wäre ziemlich vernünftig erschienen. Oder schlagen Sie vor, auch $error einzuführen?

Haben Sie in Betracht gezogen nothing? Das könnte ich lieber.

Answer 3

ich in der Regel nur einen Kommentar verwenden:

a: /*epsilon*/ { $$ = new_list(); } 
| a 'a' { $$ = $1; $$->append($1); } 
; 

ohne Änderungen Adaequat und macht die Absicht klar ....

IMO, kommt dies der Überschrift unter „Wenn es nicht kaputt ist , nicht fix it“

Answer 4

ich würde vorschlagen, die folgenden:

definieren sie die Erklärung:

%empty ID 

deren Semantik sind zweifach:

1) ID kann als die einzigen nicht-Token-Regel in einer RHS verwendet werden, um anzuzeigen, dass die RHS eine epsilon-Produktion ist; und

2) Epsilon-Produktionen, die nicht mit ID markiert sind, gelten als Syntaxfehler.

So mit der Erklärung:

%empty epsilon 

epsilonMuss verwendet werden, um eine leere RHS zu markieren; ohne eine %empty Deklaration, der Status quo gilt, wo leere RHS nicht markiert sind (außer vielleicht mit Kommentaren).

Das würde es Benutzern, die gerne leere RHS explizit markieren, ermöglichen, dies sofort zu tun, ohne irgendwelche Auswirkungen auf vorhandene Grammatikdateien oder Benutzer zu haben, die nicht leere RHS auf diese Weise explizit markieren möchten.

Persönlich würde ich wahrscheinlich eine solche Erklärung verwenden, obwohl um ehrlich zu sein bin ich ziemlich gewöhnt, einen Kommentar zu verwenden, um eine leere RHS zu markieren, und ich glaube nicht, dass ich jemals versehentlich eine leere RHS gemacht habe. Also würde ich es nicht als eine vorrangige Feature-Anfrage markieren, aber ich würde auch nichts gegen seine Implementierung einwenden.

Answer 5

Natürlich ist die Produktion in gewissem Sinne nicht wirklich "leer", wenn sie eine Aktion enthält, da es in Yacc/Bison schwer ist, die Tatsache nicht zu ahnen, dass Aktionen hinter den Kulissen in nullbare Nicht-Terminals umgewandelt werden. Und wenn Sie (oder das Buch) während des Semesters in der Klasse "epsilon" gesagt haben, hat "% epsilon" vielleicht mehr Wahrscheinlichkeit als "% empty".

sinne ich über diese in eine allgemeinere Behauptung Mechanismus zu subsumieren:

lines : %assert(epsilon) 
     | %assert(on WORD) lines line ; 

line : WORD '\n' ; 

%assert(nullable(lines)) 
%assert(!nullable(line)) 
%assert(WORD in FIRST(lines)) 
/* etc. */ 

Die Idee genau zu leicht abnehmen zu sein, den Schmerz, herauszufinden, welche Sprache yacc/Bison nach tatsächlich umgesetzt hat, sind alle Heuristiken gekickt Der Rest funktioniert mehr oder weniger wie Sie angegeben haben, eine Option, die vor "leeren" Regeln warnt, es sei denn, die "leere" Regel enthält% assert (epsilon). Im Hinblick auf die Prioritäten würde ich denken, dass es eine viel höhere Priorität für Bison gibt, wenn es einen Parser erstellt hat, der die Eingabegrammatik möglicherweise nicht akzeptieren kann (z. B. können eine oder mehrere Produktionen niemals feuern). Zumindest war diese Fähigkeit nicht da, ich habe nachgesehen, aber ich habe einen ziemlich alten Bison :-). Und kann man das Problem von Produktionen mit gemeinsamen linken Präfixen, die sich durch eingebettete Aktionen unterscheiden, auf Englisch nicht erklären? Wenn es nicht viel besser geworden ist, würde ich denken, dass es noch eine Menge erklärender Verbesserungen gibt, die mehr helfen würden als eine Überprüfung auf unbeabsichtigt leere Regeln.

Es wäre interessant, einige Daten zu den häufigsten Fehlern zu sehen, mit denen die Schüler konfrontiert sind (ich hätte diesen als Kandidat nicht gewählt!). Das wäre ein interessantes Experiment: hacken Sie die Schülerkopie von Bison, damit sie jeden Lauf in eine Datenbank schickt, verwenden Sie eine Software, um sie zu bereinigen, und analysieren Sie die häufigsten Missverständnisse.