Emitir resolver um conflito carrega-reduz em minha gramática

Question

Eu estou tentando escrever um pequeno analisador com Ironia . Infelizmente eu recebo um "shift-reduzir os conflitos". Gramáticas não são meu ponto forte, e eu só precisa obter esta pequena coisinha feito. Aqui está a gramática reduzida que produz o erro:

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

O que significa o "shift-reduzir os conflitos" significa e como posso resolver isso? Percebi que isso significa que a minha gramática é ambígua, mas não posso torcer minha lógica suficiente para ver como.

Adicionado: Para esclarecer - "ASD" é simplesmente uma string "asd" literal. Então eu esperaria que as expressões a seguir são analisados ??por esta gramática:

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

Adicionado 2:. Esqueci de dizer, a raiz da gramática é LogicalExpression

Adicionado 3: Ahh, eu entendi! A ambiguidade é porque uma expressão como

asd AND asd OR asd

poderia ser interpretado de duas maneiras diferentes:

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

Mas como posso resolver isso? OK, eu posso colocar um de E ou Ou para ser mais forte do que o outro (eu tinha inteded de qualquer maneira). Mas agora eu vejo que o erro aparece mesmo se houver apenas um operador. Em outras palavras, isso também produz o mesmo erro:

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

Neste caso, eu quero isso:

asd OR asd OR asd

a ser analisado a esta:

(asd OR asd) OR asd

O que é a maneira não-ambígua de fazer isso?

Adicionado 4: Got it

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

Esta analisa todas as expressões booleanas, com precedência operador que NÃO> E-> OR. "Asd" pode ser substituída com a expressão destina-se a seus termos.

Answer 1

Sua gramática é ambígua, se você usar apenas uma única visão antecipada. Para ilustrar, o que é "asd"? É um ExpressionTerm ou um prazo mais longo. Isso é shift-reduzir os conflitos. Eu suspeito que um conflito reduz-reduz aqui também.

A maioria LL (1) / LALR (1) Geradores irá fornecer alguma forma de lidar com o conflito shift-reduce via operadores de precedência. A maioria também será o padrão para a mais longa sequência na presença de um conflito carrega-reduz, de forma mais do que muitas vezes estes podem ser ignoradas (após algum escrutínio). (Neste caso, talvez você precise mover o único termo para o fundo para que ele se comporte corretamente).

Answer 2

Shift-Reduzir meio de conflito que sua gramática é ambígua. Com sua regra recursiva um "asd" símbolo poderia ser interpretado como parte de qualquer ExpressionTerm ou LogicalExpression eo analisador não pode decidir qual. Precisa de uma regra adicional para quebrar o empate.

Answer 3

Mudança reduzir os conflitos são uma das coisas mais difíceis de fazer o seu cérebro quando se trata de analisadores. A maneira mais fácil para ilustrar o conflito é neste código pseudo:

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

A declaração mais poderia ligar para o primeiro ou segundo se. No caso de gramática ambígua, você normalmente definir um valor para indicar o número de espera shift-reduce avisos em sua gramática.

Como alternativa, você pode usar um LL (k) ou analisador LL (*). Estes tipos de analisadores não têm o shift / reduzir a ambiguidade. Dependendo da sua aplicação que pode ser mais fácil ou mais difícil do que a LALR (1) parser.

Answer 4

gramática é ambígua na LL(1) ou LALR(1) desde asd token pode ser substituído em ExpressionTerm e também LogicalExpression achatar as regras gramaticais a mudança resolve / reduzir conflitos