spezifische Fehlerbeseitigung in Bison/Yacc

Question

Ich lese ein "Compiler Konstruktion, Prinzipien und Praxis" Buch von Kenneth Louden und versuchen, Fehlerkorrektur in Yacc zu verstehen.

Der Autor gibt ein Beispiel mit dem folgenden Grammatik:

%{ 
#include <stdio.h> 
#include <ctype.h> 

int yylex(); 
int yyerror(); 
%} 

%% 

command : exp { printf("%d\n", $1); } 
     ; /* allows printing of the result */ 

exp : exp '+' term { $$ = $1 + $3; } 
    | exp '-' term { $$ = $1 - $3; } 
    | term { $$ = $1; } 
    ; 

term : term '*' factor { $$ = $1 * $3; } 
    | factor { $$ = $1; } 
    ; 

factor : NUMBER { $$ = $1; } 
     | '(' exp ')' { $$ = $2; } 
     ; 

%% 

int main() { 
    return yyparse(); 
} 

int yylex() { 
    int c; 

    /* eliminate blanks*/ 
    while((c = getchar()) == ' '); 

    if (isdigit(c)) { 
    ungetc(c, stdin); 
    scanf("%d\n", &yylval); 
    return (NUMBER); 
    } 

    /* makes the parse stop */ 
    if (c == '\n') return 0; 

    return (c); 
} 

int yyerror(char * s) { 
    fprintf(stderr, "%s\n", s); 
    return 0; 
} /* allows for printing of an error message */ 

Welche der folgenden Zustandstabelle erzeugt (nachfolgend als Tabelle 5.11 später)

Zahlen in den Kürzungen entsprechen folgenden Produktionen:

(1) command : exp. 
(2) exp : exp + term. 
(3) exp : exp - term. 
(4) exp : term. 
(5) term : term * factor. 
(6) term : factor. 
(7) factor : NUMBER. 
(8) factor : (exp). 

Dann gibt Dr. Louden das folgende Beispiel:

Überlegen Sie, was, wenn ein Fehler-Produktion auf die yacc Definition wurden hinzugefügt hapen würde

factor : NUMBER {$$ = $1;} 
     | '(' exp ')' {$$=$2;} 
     | error {$$ = 0;} 
     ; 

erste fehlerhafte Eingabe Betrachten 2 ++ 3 als Im vorherigen Beispiel (Wir verwenden weiterhin Tabelle 5.11, obwohl die zusätzliche Fehlererzeugung zu einer leicht abweichenden Tabelle führt.) Wie zuvor erreicht der Parser den folgenden Punkt:

parsing stack   input 
$0 exp 2 + 7   +3$ 

Nun ist die Fehler-Produktion für factor wird vorsehen, dass Fehler a Rechts Vorgriffs-in Zustand 7 und Fehler sofort verschoben auf dem Stapel sein und zu factor reduziert, 0 den Wert verursacht zurückgegeben werden . Nun hat der Parser den folgenden Punkt erreicht:

parsing stack     input 
$0 exp 2 + 7 factor 4   +3$ 

Dies ist eine normale Situation, und der Parser wird weiterhin normalerweise bis zum Ende auszuführen. Der Effekt ist der Eingang als 2 + 0 + 3 zu interpretieren - die 0 zwischen den beiden + Symbole gibt es, weil dort die Fehler pseudotoken eingeführt wird, und durch die Wirkung für den Fehler Produktion, Fehler wird als äquivalent zu einem Faktor mit dem Wert betrachtet 0.

Meine Frage ist ganz einfach:

wie er, indem man die Grammatik wußte, dass, um von diesem spezifischen zu erholen Fehler (2 ++ 3) Er muss einen Fehler Pseudotoken zur factor Produktion hinzufügen? Gibt es einen einfachen Weg, es zu tun? Oder der einzige Weg, dies zu tun ist, mehrere Beispiele mit der Zustandstabelle auszuarbeiten und zu erkennen, dass dieser spezielle Fehler in diesem gegebenen Zustand auftritt und daher, wenn ich einen Fehler Pseudotoken zu einer bestimmten spezifischen Produktion hinzufüge, wird der Fehler behoben .

Jede Hilfe wird geschätzt.

Answer 1

In dieser einfachen Grammatik haben Sie sehr wenige Optionen für eine Fehlererzeugung, und alle von ihnen erlauben es, das Parsen fortzusetzen.

Die Auswahl am unteren Ende des Ableitungsbaums ist in diesem Fall sinnvoll, aber das ist keine allgemeine Heuristik. Es ist häufiger nützlich, Fehlerproduktionen an den Anfang des Ableitungsbaums zu setzen, wo sie verwendet werden können, um das Parsen neu zu synchronisieren. Angenommen, wir die Grammatik für mehrere Ausdrücke zu ermöglichen geändert hatte, die jeweils in einer eigenen Zeile: (was erfordern würde, zu modifizieren yylex, so dass es nicht fälschen ein EOF tut, wenn es \n sieht):

program: %empty 
     | program '\n' 
     | program exp '\n' { printf("%g\n", $1); } 

wenn wir jetzt, wollen einfach nur Fehler ignorieren und Parsing weiter, können wir eine Resynchronisation Fehler-Produktion hinzu:

 | program error '\n' 

Der ‚\ n‘ Terminal in dem oben bewirkt, dass Token übersprungen werden, bis ein newline zu verschoben werden kann Reduzieren Sie die Fehlerproduktion, so dass die Analyse mit der nächsten Zeile fortgesetzt werden kann.

Nicht alle Sprachen sind jedoch so einfach zu resynchronisieren. Anweisungen in C-ähnlichen Sprachen werden nicht notwendigerweise durch ; beendet, und ein naive Versuch einer erneuten Synchronisierung wie oben würde eine gewisse Verwirrung verursachen, wenn der Fehler beispielsweise ein fehlender } wäre. Es würde jedoch ermöglichen, dass das Parsen in irgendeiner Weise fortgesetzt wird, und das könnte ausreichend sein.

Nach meiner Erfahrung erfordert das Erzielen von Fehlerproduktionen in der Regel viel Versuch und Irrtum; es ist viel mehr eine Kunst als eine Wissenschaft. Es hilft, viele fehlerhafte Eingaben zu versuchen und die Fehlerkorrektur zu analysieren.

Der Punkt einer Fehlerproduktion ist, von einem Fehler zu beheben. Das Erzeugen von guten Fehlermeldungen ist ein nicht verwandtes, aber ebenso schwieriges Problem. Zu dem Zeitpunkt, zu dem der Parser eine Fehlerkorrektur versucht, wurde die Fehlernachricht bereits an yyerror gesendet. (Natürlich könnte diese Funktion die Fehlermeldung ignorieren und sie der Fehlerproduktion überlassen, um einen Fehler zu drucken, aber es gibt keinen ersichtlichen Grund dafür.)

Eine mögliche Strategie für die Erstellung guter Fehlermeldungen ist eine Art zu tun von Tabellennachschlagen (oder -berechnung) auf dem Parserstapel und dem Lookahead-Token. Im Endeffekt erweiterte Bison die Fehlerbehandlung, und das führt oft zu ziemlich vernünftigen Ergebnissen, also ist es ein guter Startpunkt. Alternative Strategien wurden untersucht. Eine gute Referenz ist Clinton Jeffreys 2003-Papier Generating LR Syntax Error Messages from Examples; Sie können auch herausfinden, Russ Cox's explanation wie er diese Idee auf einen Go-Compiler angewendet hat.