Problema risolvere un conflitto shift-ridurre in mia grammatica

Question

Sto cercando di scrivere un piccolo parser con Ironia . Purtroppo ho un "conflitto shift-reduce". Grammatiche non sono il mio forte, e ho solo bisogno di ottenere questo piccolo thingy fatto. Ecco la grammatica ridotta che produce l'errore:

ExpressionTerm := "asd"
LogicalExpression :=
    ExpressionTerm |
    LogicalExpression "AND" LogicalExpression |
    LogicalExpression "OR" LogicalExpression

Che cosa significa il "shift-ridurre i conflitti" significa e come posso risolverlo? Mi sembra di capire che vuol dire che la mia grammatica è ambigua, ma non riesco a girare la mia logica sufficientemente per vedere come.

Aggiunto: per chiarire - "asd" è semplicemente una stringa letterale "asd". Quindi mi aspetto che le seguenti espressioni vengono analizzati da questa grammatica:

asd
asd AND asd
asd AND asd OR asd
asd OR asd AND asd OR asd

Aggiunto 2:. Hai dimenticato di dire che la radice della grammatica è LogicalExpression

Aggiunto 3: Ahh, ho capito! L'ambiguità è perché un'espressione come

asd AND asd OR asd

potrebbe essere interpretato in due modi diversi:

(asd AND asd) OR asd
asd AND (asd OR asd)

Ma come posso risolvere questo problema? OK, posso mettere una delle AND o OR per essere più forte rispetto agli altri (che avevo in questione, destinate a comunque). Ma ora vedo che l'errore si verifica anche se v'è un solo operatore. In altre parole, questo produce anche lo stesso errore:

LogicalExpression := "asd" | LogicalExpression "OR" LogicalExpression

In questo caso voglio questo:

asd OR asd OR asd

per essere analizzato a questo:

(asd OR asd) OR asd

Qual è il modo non ambiguo di fare questo?

Aggiunto 4: Capito

LogicalExpression1 := LogicalExpression1 "OR" LogicalExpression2 | LogicalExpression2
LogicalExpression2 := LogicalExpression2 "AND" LogicalExpression3 | LogicalExpression3
LogicalExpression3 := "NOT" LogicalExpression4 | LogicalExpression4
LogicalExpression4 := "asd" | "(" LogicalExpression1 ")"

Questa analizza tutte le espressioni booleane, con precedenza degli operatori come NON-> AND> O. "Asd" può essere sostituito con l'espressione destinato per i termini.

Answer 1

la grammatica è ambigua, se si utilizza solo un singolo lookahead. Per illustrare, ciò che è "asd"? È un ExpressionTerm o di un termine più lungo. Questo è SHIFT-ridurre i conflitti. Ho il sospetto di un conflitto di ridurre-ridurre anche qui.

La maggior parte LL (1) / LALR (1) generatori fornirà un modo per affrontare il conflitto shift-ridurre tramite operatori di precedenza. La maggior parte sarà anche per default la sequenza più lunga in presenza di un conflitto shift-ridurre, in modo il più delle volte questi possono essere ignorati (dopo un certo controllo). (In questo caso forse è necessario spostare il singolo termine verso il basso per questo comportarsi correttamente).

Answer 2

Maiusc-ridurre il conflitto significa che la grammatica è ambigua. Con la regola ricorsiva un gettone "asd" potrebbe essere interpretato come parte di uno o di ExpressionTerm LogicalExpression e il parser non può decidere quale. Hai bisogno di una regola aggiuntiva per rompere il legame.

Answer 3

Turno ridurre i conflitti sono una delle cose più difficili da mettere il tuo cervello quando si tratta di parser. Il modo più semplice per illustrare il conflitto è in questo pseudo codice:

if (a) then
   if (b) then
     printf('a + b');
   else
     print('this could be a + !b or !a');

La dichiarazione altro potrebbe legarsi al primo o al secondo caso. Nel caso delle grammatiche ambigue, di solito si definisce un valore per indicare il numero di atteso shift-ridurre le avvertenze nella tua grammatica.

In alternativa, è possibile utilizzare un LL (k) o LL (*) parser. Questi tipi di parser non hanno il cambiamento / ridurre l'ambiguità. A seconda dell'applicazione possono essere più facile o più difficile di quanto il LALR (1) parser.

Answer 4

grammatica è ambigua in LL(1) o LALR(1) dal gettone ASD può essere sostituito in ExpressionTerm e anche LogicalExpression appiattire le regole grammaticali per risolvere spostamento / ridurre i conflitti