Rekursiven Abstiegs-Parsing - von LL (1) bis

Question

Die folgende einfache „Rechner Ausdruck“ Grammatik (BNF) kann leicht mit einem trivialen rekursiv absteigenden Parser, die prädiktive LL (1) analysiert werden:

<expr>      :=  <term> + <term>
            |   <term> - <term>
            |   <term>
<term>      :=  <factor> * <factor>
                <factor> / <factor>
                <factor>
<factor>    :=  <number>
            |   <id>
            |   ( <expr> )
<number>    :=  \d+
<id>        :=  [a-zA-Z_]\w+

Weil es immer genug, um das nächste Token, um zu sehen, die Regel zu wissen, zu holen. Allerdings nehme an, dass ich die folgende Regel hinzu:

<command>   :=  <expr>
            |   <id> = <expr>

Für die Zwecke mit dem Rechner auf der Kommandozeile der Interaktion mit Variablen, wie folgt aus:

calc> 5+5
=> 10
calc> x = 8
calc> 6 * x + 1
=> 49

Ist es wahr, dass ich nicht eine einfache LL (1) prädiktive Parser zu analysieren Regeln <command> verwenden kann? Ich habe versucht, den Parser für sie zu schreiben, aber es scheint, dass ich mehr Token vorwärts wissen. Ist die Lösung Rückzieher zu verwenden, oder kann ich nur LL (2) umzusetzen und immer nach vorne schauen zwei Token?

Wie Parser-Generatoren dieses Problem (ANTLR, zum Beispiel) behandeln RD?

Answer 1

Das Problem mit

<command>   :=  <expr>
            |   <id> = <expr>

ist, dass, wenn Sie „sehen“ <id> man kann nicht sagen, ob es der Beginn einer assignement (zweite Regel) ist oder es ist ein „<factor>“. Sie werden nur wissen, wann Sie das nächste Token gelesen werden.

AFAIK ANTLR ist LL (*) (und ist auch in der Lage Parser rat-pack zu erzeugen, wenn ich mich nicht irre), so wird dies grammare Berücksichtigung zwei Token sofort wohl behandeln.

Wenn Sie mit der Grammatik spielen können, würde ich vorschlagen, entweder ein Schlüsselwort für die Zuordnung hinzufügen (z let x = 8):

<command>   :=  <expr>
            |   "let" <id> "=" <expr>

oder verwenden Sie die = Auswertung zu bedeuten:

<command>   :=  "=" <expr>
            |   <id> "=" <expr>

Answer 2

Ich denke, es gibt zwei Möglichkeiten, dies mit einem Rekursiver Abstieg zu lösen. Entweder mit (mehr) Look-Ahead oder durch Rückzieher

Die Look-Ahead

command() {
    if (currentToken() == id && lookaheadToken() == '=') {
        return assignment();
    } else {
        return expr();
    }
}

Backtracking

command() {
    savedLocation = scanLocation();
    if (accept( id )) {
         identifier = acceptedTokenValue();
         if (!accept( '=' )) {
             setScanLocation( savedLocation );
             return expr();
         }
         return new assignment( identifier, expr() );
    } else {
         return expr();
    }
}

Answer 3

Das Problem ist, dass die Grammatik:

<command>   :=  <expr>
            |   <id> = <expr>

ist keine gegenseitig rekursive Prozedur. Für eine rekursive anständigen Parser müssen Sie eine nicht-rekursive äquivalent zu bestimmen.

rdentato Post zeigt, wie dieses Problem zu beheben, vorausgesetzt, Sie mit der Grammatik spielen. Diese Powerpoint legt das Problem in etwas mehr Detail und zeigt, wie es zu korrigieren: http://www.google.com/url?sa=t&source=web&ct=res&cd=7&url=http%3A%2F % 2Fxml.cs.nccu.edu.tw% 2Fcourses% 2Fcompiler% 2Fcp2006% 2Fslides% 2Flec3-Parsing% 26TopDownParsing.ppt & ei = -YLaSPrWGaPwhAK5ydCqBQ & usg = AFQjCNGAFrODJxoxkgJEwDMQ8A8594vn0Q & sig2 = nlYKQVfakmqy_57137XzrQ

Answer 4

ANTLR 3 verwendet eine "LL (*)" Parser im Gegensatz zu einem LL (k) Parser, so dass es nach vorne schauen, bis sie das Ende des Eingangs erreicht, wenn es hat, ohne Rückzieher, einen speziell optimierte determinstic endlichen Automaten (DFA) verwendet wird.