Shift-reduce:quando parar de redução?

Question

Eu estou tentando aprender sobre shift-reduce análise.Suponha que temos a seguinte gramática, usando recursiva regras que impõem a ordem das operações, inspirado pelo ANSI C Yacc gramática:

S: A;

P
    : NUMBER
    | '(' S ')'
    ;

M
    : P
    | M '*' P
    | M '/' P
    ;

A
    : M
    | A '+' M
    | A '-' M
    ;

E queremos analisar 1+2 usando shift-reduce análise.Primeiro, o 1 é deslocado como um NÚMERO.A minha pergunta é, que é, então, reduzida a P, então M e, em seguida, Um e, finalmente, S?Como ele sabe onde parar?

Suponha que ele faz reduzir toda a forma de S, então muda '+'.Gostaríamos agora de uma pilha que contém:

S '+'

Se nós shift '2', as reduções podem ser:

S '+' NUMBER
S '+' P
S '+' M
S '+' A
S '+' S

Agora, um de cada lado da última linha, S poderia ser P, M, A, ou NÚMERO, e ainda seria válido, no sentido de que qualquer combinação seria uma representação correta do texto.Como o analisador de "saber" para torná-lo

A '+' M

Assim que pode reduzir a expressão completa para Um, em seguida, S?Em outras palavras, como ele sabe parar de redução antes de mudar o próximo token?É esta uma grande dificuldade em LR parser geração?

---

Editar: Uma adição para a questão seguinte.

Suponha, agora, que vamos analisar 1+2*3.Alguns shift/reduzir as operações são as seguintes:

Stack    | Input | Operation
---------+-------+----------------------------------------------
         | 1+2*3 | 
NUMBER   | +2*3  | Shift
A        | +2*3  | Reduce (looking ahead, we know to stop at A)
A+       | 2*3   | Shift
A+NUMBER | *3    | Shift (looking ahead, we know to stop at M)
A+M      | *3    | Reduce (looking ahead, we know to stop at M)

Isso está correto (concedido, não é totalmente analisada ainda)?Além disso, não procura pelo símbolo 1 também nos dizer para não reduzir A+M para A, como fazer isso resultaria em um inevitável erro de sintaxe, depois de ler *3 ?

Answer 1

O problema que você está descrevendo é um problema de criar LR(0) Analisadores - isto é, analisadores de baixo para cima que não fazem nenhuma aparência aos símbolos além do atual que estão analisando. A gramática que você descreveu não parece ser um LR(0) Gramática, e é por isso que você tem problemas ao tentar analisá -lo sem aparência. Isto faz parece ser LR(1), no entanto, ao procurar 1 símbolo à frente na entrada, você pode determinar facilmente se deve mudar ou reduzir. Nesse caso, um LR(1) Parser olharia para frente quando tivesse o 1 Na pilha, veja que o próximo símbolo é um +, e perceber que não deveria reduzir o passado A (já que essa é a única coisa que poderia reduzir para isso ainda corresponderia a uma regra com + na segunda posição).

Uma propriedade interessante de LR gramáticas é isso para qualquer gramática que seja LR(k) por k>1, é possível construir um LR(1) Gramática que é equivalente. No entanto, o mesmo não se estende até LR(0) - Existem muitas gramáticas que não podem ser convertidas para LR(0).

Veja aqui para mais detalhes sobre LR(k)-ness:

http://en.wikipedia.org/wiki/lr_parser

Answer 2

Eu não estou exatamente certo do Yacc / Bison algoritmo de análise e quando ele prefere deslocar sobre a redução, no entanto eu sei que Bison suporta LR(1) ao analisar o que significa que ele tem uma visão antecipada de token.Isso significa que os créditos não são passados para a pilha imediatamente.Em vez disso, eles aguarde até que não haja mais reduções podem acontecer.Então, se mudando o próximo token faz sentido, aplica-se essa operação.

Primeiro de tudo, no seu caso, se você está avaliando 1 + 2, desloca-1.Ele irá reduzir esse token para uma a Uma, porque o '+' lookahead token indica que sua válida apenas curso.Uma vez que não há mais reduções, ele vai mudar o '+' token para a pilha e mantenha pressionado 2 como lookahead.Ele vai mudar o 2 e reduzir para um M desde A + M produz uma a Uma e a expressão é completa.