Trasformando una LR (1) in una grammatica di espressioni in LL (1)

Question

Trasformando una LR (1) in una grammatica di espressioni in LL (1)

#1 da (1 voti)

2

Ho la seguente grammatica per le espressioni logiche, relazionali e aritmetiche che ho bisogno di rendere compatibile LL (1).

E -> A | B
A -> A op1 T | T
T -> T op2 F | F
F -> ( A ) | v
B -> B lop B2 | B2
B2 -> A rop A | ( B )
op1 -> + | -
op2 -> * | /
rop -> > | < | == | <= | >=
lop -> AND | OR

Finora sono stato in grado di rimuovere la ricorsione sinistra

E -> A | B
A -> T A2
A2 -> op1 T A2 | e
T -> F T2
T2 -> op2 F T2 | e
F -> ( A ) | v
B -> B2 B3
B3 -> lop B2 B3 | e
B2 -> A rop A | (B)
op1 -> + | -
op2 -> * | /
rop -> > | < | == | <= | >=
lop -> AND | OR

Dove e è la stringa nulla. Ora dopo questo non riesco a capire come renderlo compatibile con LL (1).

(Questo è un problema di compiti a casa. Qualsiasi aiuto sarebbe apprezzato)

EDIT: Il mio problema principale è quando una parentesi aperta si incontra in E, con un lookahead non riesco a decidere se la regola

E -> A

dovrebbe essere seguito o la regola

E -> B

Questo perché entrambi derivano stringhe che iniziano con una parentesi di apertura. Non sono in grado di capire come rimuovere questo problema.

compiler

posta Srajan Jain 19.02.2017 - 17:01

fonte

1 risposta

Leggi altre domande sui tag compiler

Applicazione cloud multi-tenant e credenziali utente Come modificare questa implementazione per coprire gli inconvenienti di Mediator Design Pattern qui

score 1 · Answer 1

Hai una grammatica LR per le espressioni logiche, relazionali e aritmetiche e ti piacerebbe una grammatica LL (1) per questo.

Ai livelli più bassi che iniziano con% non inferiore A o B ciò che in effetti hai avuto è corretto. Stavo pensando che puoi unirti a loro semplicemente con E -> A | B dove sei andato. E questo è semplicemente perché non stavi seguendo lo schema che era stato costruito fino a quel punto.

Nelle grammatiche per espressioni come il tuo esempio, nonminminals come A, B, T, F aggiungi una classe di cose che puoi aggiungere all'espressione, ad es. per B tipi di espressioni booleane; per tipi di espressioni aritmetiche-relazionali.

Tuttavia la rigida gerarchia nella grammatica è ciò che specifica la precedenza degli operatori: cioè che le espressioni relazionali si legano più strettamente delle espressioni logiche. Quindi, quando hai E -> A | B , violi quella gerarchia avendo le espressioni aritmetiche e booleane allo stesso livello e questo è ciò che fa sì che la grammatica LL (1) abbia uno scontro "primo set": stiamo provando a predire un rapporto aritmetico espressione o stiamo cercando di prevedere un'espressione logica?

Quindi suddividiamolo nella parte che funziona, e poi continuiamo a estenderlo.

Hai (usando la sintassi ANTLR):

A -> T A2 .
A2 -> op1 T A2 | e .
op1 -> + | - .

T -> F T2 .
T2 -> op2 F T2 | e .
op2 -> * | / .

F -> ( A ) | v .
e -> .

E questo permette e mette una gerarchia su espressioni di tipo multiplo rispetto ad addizioni. Quindi ora estendiamo il primo agli operatori aritmetici relazionali:

B -> A B2 .
B2 -> rop A B2 | e .
rop -> > | < | == | <= | >= .

A -> T A2 .
A2 -> op1 T A2 | e .
op1 -> + | - .

T -> F T2 .
T2 -> op2 F T2 | e .
op2 -> * | / .

F -> ( B ) | v .
e -> .

E infine agli operatori logici:

E -> B E2 .
E2 -> lop B E2 | e .
lop -> AND | OR .

B -> A B2 .
B2 -> rop A B2 | e .
rop -> > | < | == | <= | >= .

A -> T A2 .
A2 -> op1 T A2 | e .
op1 -> + | - .

T -> F T2 .
T2 -> op2 F T2 | e .
op2 -> * | / .

F -> ( E ) | v .
e -> .

Infine, lasciami dire che una ricerca su google ha mostrato questo interessante correttore grammaticale: link