Quais são os casos em que não podemos realizar a análise de LR sem gramática aumentada?

Question

Muitos textos de design padrão de compilador mencionam a construção de gramática aumentada como primeiro passo da análise do LR.

A razão é freqüentemente

.
1. é necessário nos casos em que o símbolo de início vem à direita de qualquer produção
2. É necessário quando o RHS do símbolo inicial tem várias produções.

Eu percebi que, se na parte de ação da tabela de análise do primeiro estado de DFA, fornecemos "sucesso" sob a entrada de '$' nós não exigiria gramática aumentada.É isso correto ou estou perdendo alguma coisa?

editar: Aqui está como eu acho que podemos declarar uma análise como sucesso:

considere s -> .a Depois de reduzirmos 'A' em vez de ir para o (s) de nosso estado atual, um ttop de pilha, podemos simplesmente lookeahead '$' e sucesso de resultados

Answer 1

Uma vez que temos uma mesa de análise, podemos analisar (ou rejeitar) qualquer frase sem qualquer referência à gramática. Então, nesse ponto, o fato de que a gramática era ou não era aumentada é essencialmente discutível. (Seria significativo se houvesse uma ação semântica de usuário ligada à produção exclusiva de símbolo de início aumentada, mas isso parece impossível, uma vez que a produção de símbolo de início aumentada foi adicionada automaticamente, não pelo usuário.)

e é de fato o caso que a maioria dos geradores analisadores, de fato, otimize sua tabela de análise, tornando a mudança do marcador final de entrada a ação de aceitação, em vez de esperar pelo início aumentado a produção do símbolo a ser reduzida. Com essa otimização, o símbolo de início aumentado nunca é usado em uma ação analisadora, então o próprio símbolo não precisa existir. Se o gerador analisador aumentou a gramática, esse aumento foi essencialmente desfeito, exceto por um pequeno mistério: O que é esse símbolo de entrada de entrada que pode ser deslocado? Não aparece em qualquer lado direito redutível.

De qualquer forma, o ponto é que não é analisando que requer uma gramática aumentada; A gramática aumentada é necessária para criar a tabela de parsing. Os casos em que são necessários são essencialmente os casos em que há alguma ação de redução não padrão associada a um símbolo de fim de entrada LookAhead. Que a ação de redução só poderia ter sido adicionada corretamente à tabela de análise por meio da análise de um estado que inclui a produção de símbolo de início aumentada.

(estritamente falando, como aludado anteriormente, o símbolo final de entrada não pode existir na tabela de análise, a menos que esteja presente em algum lado direito na gramática, e não esteja presente até A gramática é aumentada; o aumento não só adiciona um não-terminal adicional, também adiciona o símbolo final de entrada em si.)