Analisi della discesa ricorsiva - da LL (1) in su

Question

La seguente semplice " espressione calcolatrice " la grammatica (BNF) può essere facilmente analizzata con un banale parser ricorsivo-discendente, che è predittivo LL (1):

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

Perché è sempre sufficiente vedere il token successivo per conoscere la regola da scegliere. Tuttavia, supponiamo di aggiungere la seguente regola:

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

Allo scopo di interagire con la calcolatrice sulla riga di comando, con variabili come questa:

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

È vero che non posso usare un semplice parser predittivo LL (1) per analizzare le regole <command>? Ho provato a scrivere il parser per questo, ma sembra che ho bisogno di sapere più token in avanti. È la soluzione per utilizzare il backtracking o posso semplicemente implementare LL (2) e guardare sempre due token in avanti?

In che modo i generatori di parser RD gestiscono questo problema (ANTLR, per esempio)?

Answer 1

Il problema con

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

è quello quando " vedi " <id> non puoi dire se è l'inizio di un incarico (seconda regola) o è un " <factor> " ;. Saprai solo quando leggerai il token successivo.

AFAIK ANTLR è LL (*) (ed è anche in grado di generare parser di pacchetti di ratti se non sbaglio), quindi probabilmente gestirà questa grammatica considerando due token contemporaneamente.

Se puoi giocare con la grammatica, suggerirei di aggiungere una parola chiave per il compito (ad esempio let x = 8):

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

o usa = per indicare la valutazione:

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

Answer 2

Penso che ci siano due modi per risolverlo con un parser ricorsivo per la discesa: usando (più) lookahead o backtracking.

Lookahead

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

Il problema è che la grammatica:

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

non è una procedura reciprocamente ricorsiva. Per un parser decorsivo ricorsivo dovrai determinare un equivalente non ricorsivo.

I post di rdentato mostrano come risolvere questo problema, supponendo che tu possa giocare con la grammatica. Questo powerpoint chiarisce il problema in modo un po 'più dettagliato e mostra come correggerlo: http://www.google.com/url?sa=t <> amp;! source = web <> amp;! Ct = res <> amp;! cd = 7 <> amp;! url = http% 3A % 2F% 2Fxml.cs.nccu.edu.tw% 2Fcourses% 2Fcompiler% 2Fcp2006% 2Fslides% 2Flec3-Analisi% 26TopDownParsing.ppt amp &; & ei = -YLaSPrWGaPwhAK5ydCqBQ amp; amp USG = AFQjCNGAFrODJxoxkgJEwDMQ8A8594vn0Q &; SIG2 = nlYKQVfakmqy_57137XzrQ

Answer 4

ANTLR 3 utilizza un " LL (*) " parser al contrario di un LL (k) parser, quindi guarderà avanti fino a raggiungere la fine dell'input se deve, senza backtracking, utilizzando un automa deterministico finito (DFA) appositamente ottimizzato.