Gramáticas e Análise:A ambiguidade em Sequências

Question

FUNDO

Estou a escrever uma gramática e parser para um domínio específico do idioma.Há uma forma específica de expressão que, apesar de simples, está me dando dores de cabeça.

Dado terminais:

• "a":Palavras-CHAVE
• "b":INTVAL
• "c":DECVAL
• "d":STRVAL

Regras:

• "E":VALOR <- INTVAL
• "F":VALOR <- DECVAL
• "G":VALOR <- STRVAL
• "H":VALORES <- VALOR
• "Eu":VALORES <VALORES - VALOR
• "J":LINHA <- VALORES DE PALAVRA-CHAVE

Não é complicado, certo?Este subconjunto específico de terminais e regras deve ser capaz de analisar a seguinte linha:

• PALAVRAS-CHAVE DECVAL DECVAL DECVAL DECVAL

Em outras palavras, uma palavra-chave seguida por uma ou mais valores devem ser gramaticalmente correto linha.DECVAL tokens deve reduzir a um VALOR de fichas, que são por sua vez, agregados em uma série de VALORES, no ponto em que a linha reduz de acordo com a regra "J".

PROBLEMA

No entanto, considere o seguinte analisar o estado, após as duas primeiras fichas foram deslocadas e lookahead é o próximo DECVAL:

• PALAVRAS-CHAVE DECVAL | DECVAL

Este é um shift-reduzir o conflito, porque ele pode mudar o lookahead DECVAL de acordo com a regra de "F" ou reduzir o DECVAL no topo da pilha sob a mesma regra ("F").Por padrão, a maioria dos analisadores irá realizar a mudança--caso em que a série nunca irá reduzir porque há um DECVAL muito "profundo" na pilha.

PERGUNTA

Mas como você (por exemplo) definir a precedência de tal forma como para indicar uma regra específica deve reduzir, quando em conflito com ele mesmo?É que até mesmo uma boa ideia?Com base na minha própria compreensão limitada, deve haver uma maneira de reestruturar as regras gramaticais, certo?Mas não é óbvio, para mim, o que é isso.

Answer 1

Este analisador estado

KEYWORD DECVAL DECVAL
               ^
               |---------- Lookahead

não é um conflito, porque uma mudança de ação não é possível.Não há produção em que Um DECVAL segue outro DECVAL.Não há nem mesmo uma produção em que um VALUE segue outro VALUE.Antes de lookahead DECVAL pode ser deslocado, o DECVAL no topo da pilha deve ser reduzido para algo que pode ser seguido com DECVAL.