Por que eu tenho uma mudança de redução / conflito na ')' e não '('?

Question

Eu sintaxe como

%(var)

e

%var

e (Var)

As minhas regras são algo como

optExpr:
    | '%''('CommaLoop')'
    | '%' CommaLoop

CommaLoop:
    val | CommaLoop',' val

Expr:
    MoreRules
    | '(' val ')'

O problema é que não parece ser capaz de dizer se) pertence a %(CommaLoop) ou % (val) mas reclama sobre a) em vez do (. Que diabos? Should que reclamar sobre (? E como eu deveria corrigir o erro? Eu acho que fazendo %( um token é uma boa solução, mas eu quero ter certeza porque $( is not um erro antes de fazer isso.

Answer 1

Isto é devido à forma como os trabalhos LR análise. LR análise é efetivamente bottom-up, agrupar fichas de acordo com o RHS de suas regras gramaticais, e substituí-los com as LHS. Quando o analisador 'turnos', ele coloca um sinal na pilha, mas na verdade não corresponder a uma regra ainda. Em vez disso, que é reproduzido parcialmente correspondida regras via o estado atual. Quando se chega a um estado que corresponde ao fim da regra, pode reduzir, aparecendo os símbolos para o RHS da pilha e empurrando para trás um único símbolo que denota os LHS. Então, se há conflitos, eles não aparecem até que o analisador chega ao final de alguma regra e não pode decidir se quer reduzir (ou o que para reduzir).

No seu exemplo, depois de ver % ( val , que é o que vai estar na pilha ( . top é no lado direito aqui) Quando o lookahead é ) , ele não pode decidir se ele deve colocar o val e reduzir via a regra CommaLoop: val , ou se ele deve mudar o ) para que ele possa, em seguida, pop 3 coisas e reduzir com a regra Expr: '(' val ')'

Estou assumindo aqui que você tem algumas regras adicionais, tais como CommaLoop: Expr , caso contrário, sua gramática na verdade não corresponde a nada e bisonte / yacc irá queixar-se não-terminais não utilizados

Answer 2

Agora, a sua explicação e sua gramática não parecem corresponder. Em sua explicação, você mostrar todas as três frases como tendo 'var', mas seus programas de gramática aqueles que começam com '%' como permitindo uma lista separada por vírgula, enquanto a outra sem permite apenas um único 'val'.

No momento, eu vou assumir todos os três devem permitir uma lista separada por vírgulas. Neste caso, eu levar a gramática mais como esta:

optExpr: '%' aList

aList: CommaLoop
    | parenList

parenList: '(' CommaLoop ')'

CommaLoop: 
    | val 
    | CommaLoop ',' val

Expr: MoreRules
    | parenList

Eu mudei optExpr e Expr de modo nenhum pode corresponder a uma seqüência vazia - o meu palpite é que você provavelmente não tinha a intenção de que para começar. Eu polpa isso o suficiente para executá-lo através byacc; não produz avisos ou erros.