Como resolver um conflito de redes de mudança na gramática inequívoca

Question

Estou tentando analisar uma gramática simples usando um gerador de analisador LALR (1) (bisonte, mas o problema não é específico para essa ferramenta) e estou atingindo um conflito de redes de mudança. Os documentos e outras fontes que encontrei sobre como consertar isso tendem a dizer um ou mais dos seguintes:

• Se a gramática for ambígua (por exemplo, ambiguidade se-then-else), altere o idioma para corrigir a ambiguidade.
• Se for um problema de precedência do operador, especifique explicitamente precedência.
• Aceite a resolução padrão e peça ao gerador para não reclamar.

No entanto, nada disso parece se aplicar à minha situação: a gramática é inequívoca até onde eu sei (embora é claro que seja ambíguo com apenas um personagem de Lookahead), ele tem apenas um operador, e a resolução padrão leva a analisar erros na entrada formada corretamente. Existem técnicas para reformular a definição de uma gramática para remover conflitos de redes de mudança que não caem nos baldes acima?

Para concretude, aqui está a gramática em questão:

%token LETTER

%%
%start input;
input:          /* empty */ | input input_elt;
input_elt:      rule | statement;
statement:      successor ';';
rule:           LETTER "->" successor ';';
successor:      /* empty */ | successor LETTER;
%%

A intenção é analisar linhas semicolon-separadas da forma [a-za-z]+" ou [a-za-z]-> [a-za-z]+".

Answer 1

Usando a versão solaris de yacc, Eu recebo:

1: shift/reduce conflict (shift 5, red'n 7) on LETTER
state 1
    $accept :  input_$end
    input :  input_input_elt
    successor : _    (7)

    $end  accept
    LETTER  shift 5
    .  reduce 7

    input_elt  goto 2
    rule  goto 3
    statement  goto 4
    successor  goto 6

Portanto, o problema é que, como muitas vezes é, a regra vazia - especificamente, o sucessor vazio. Não está completamente claro se você deseja permitir um semi -colon como uma entrada válida - no momento, é. Se você modificou a regra do sucessor para:

successor: LETTER | successor LETTER;

O conflito de mudança/redução é eliminado.

Answer 2

Obrigado por afastar a gramática e postá -la. Mudando a regra do sucessor para -

successor:      /* empty */ | LETTER successor;

... trabalhou para mim. Itym o Língua parecia inequívoco.