Recursão à esquerda e fatoração à esquerda - qual deles vai primeiro?

8

se eu tiver uma gramática com uma produção que contenha recursão esquerda e fatoração esquerda como

FFBumacDSc

qual deles tem prioridade, recursão esquerda ou fatoração esquerda?

Andrea Tucci
fonte
11
Que estratégia de análise você está usando? Para descida recursiva, a recursão esquerda deve ser evitada a todo custo. O fatoração à esquerda é importante se você estiver fazendo uma análise de LL, por exemplo.
Ken Li
2
Desculpe, esqueci de escrever. Eu estou usando a estratégia analisador top-down (LL (1))
Andrea Tucci
De acordo com inst.eecs.berkeley.edu , é a mesma coisa! (no terceiro exercício)
Andrea Tucci

Respostas:

12

Transformações como fatoração à esquerda ou remoção da recursão à esquerda não têm regras de precedência. Obviamente, as gramáticas resultantes podem ser diferentes, mas reconhecerão o mesmo idioma.

O exemplo de gramática da pergunta é mais difícil do que o típico problema de lição de casa na graduação. Portanto, mostrar nosso trabalho será útil.

Recursão Esquerda

Vamos definir uma transformação que remove a recursão esquerda.

Dado

UMAUMAα0 0UMAα1 1UMAαnBβ0 0Bβ1 1Bβn ,

removemos a recursão esquerda assim:

UMAhBβ0 0Bβ1 1BβnUMAtα0 0α1 1αnUMAt+UMAtUMAt+UMAtUMAUMAhUMAt+UMAh

A generalidade acima não é normalmente apresentada nos textos do compilador, mas a análise de textos como Grune e Jacobs cobre isso. O fatorial esquerdo pode ser aplicado à gramática transformada acima, mas apenas introduzirá regras extras que não mudarão a resposta. Portanto, simplificaremos a apresentação sem que seja realizado um fator extra à esquerda.

Nesta resposta, não abordaremos questões de recursão à esquerda indireta, porque estamos preocupados apenas com as regras de um único não terminal. Observe que a recursão indireta à esquerda pode ser tratada. (Abra uma pergunta separada, se isso for importante.)

Left Factoring

A remoção do fatoramento esquerdo está na maioria dos textos introdutórios do compilador, feitos dessa maneira. Dado

UMAxyxz

rendimentos de fatoração à esquerda:

UMAsyzUMAxUMAs

Agora isso é realizar as transformações nos dois pedidos.

Factoring esquerdo primeiro

Vamos deixar de lado a gramática da pergunta

FsDSεFFBumacFs

e remova a recursão esquerda:

FhcFsFtBumaFt+FtFt+|FtFsDSεFFhFt+Fh

Removendo a recursão esquerda primeiro

E para os outros pedidos, vamos remover a recursão esquerda da gramática da pergunta

FhcDScFtBumaFt+FtFt+FtFFhFt+Fh

e então deixou o fator terminal :c

FhsDSεFhcFhsFtBumaFt+FtFt+FtFFhFt+Fh

Ah, as gramáticas resultantes são as mesmas!

Em geral, provar que duas gramáticas são equivalentes é indecidível. Portanto, se uma série de transformações gramaticais pudesse influenciar o idioma reconhecido , seria desastroso.

codeah
fonte
Obrigado, muito bem explicado! Portanto, se eu tenho recursão esquerda e fatoração esquerda, posso escolher qual remover primeiro. Obrigado novamente
Andrea Tucci
"Em geral, provar que duas gramáticas são equivalentes é indecidível." - quer dizer, provar que isso é impossível, ou quer dizer que não existe algoritmo que sempre faz isso? Somente o último está correto. Além disso, não seria "desastroso" se apenas um pedido mantivesse o idioma inalterado: você teria que usar o pedido correto. Mas certamente está claro que, se as duas transformações forem usadas independentemente de outra, elas não poderão influenciar a linguagem gerada.
Raphael
Observe que temos aqui ferramentas de formatação bastante sofisticadas (Markdown e LaTeX) para melhorar a clareza. Eu editei sua postagem de acordo. Dê uma olhada.
Raphael
11
@Raphael A linguagem "prova" é ambígua e a redação "desastrosa", acho que é exagerada. Boa pegada.
Codd #
@ Rafael Obrigado pela atenção na sintaxe.
Codd #