Transformação de gramática de expressões aritméticas

9

No artigo Analisando expressões por descendência recursiva de Theodore Norvell (1999), o autor começa com a seguinte gramática para expressões aritméticas:

E --> E "+" E | E "-" E | "-" E | E "*" E | E "/" E | E "^" E | "(" E ")" | v

o que é bastante ruim, porque é ambíguo e recursivo à esquerda. Então ele começa removendo a recursão esquerda e seu resultado é o seguinte:

E --> P {B P}
P --> v | "(" E ")" | U P
B --> "+" | "-" | "*" | "/" | "^"
U --> "-"

Mas não consigo descobrir como ele chegou a esse resultado. Quando tento remover a recursão esquerda, faço da seguinte maneira:

  1. Primeiramente, agrupo as produções que não deixaram recursão em um grupo e outras (recursivas à esquerda) em outro grupo:

    E --> E "+" E | E "-" E | E "*" E | E "/" E | E "^" E     // L-recursive
    E --> v | "(" E ")" | "-" E
  2. Em seguida, nomeio-os e considero as manipulações mais fáceis:

    E --> E B E  // L-recursive; B stands for "Binary operator"
    E --> P  // not L-recursive; P stands for "Primary Expression"
    P --> v | "(" E ")" | U E   // U stands for "Unary operator"
    B --> "+" | "-" | "*" | "/" | "^"
    P --> "-"

    Agora, preciso lidar apenas com as duas primeiras produções, que agora são mais fáceis de lidar.

  3. Reescrevo essas duas primeiras produções começando da produção não L-recursiva (que é simplesmente Pa expressão Primária) e seguindo-a pela cauda opcional T, que eu defino como o restante da produção original menos o primeiro não-recursivo esquerdo recursivo à esquerda (isto é, apenas B E) seguido pela cauda T, ou que pode estar vazia:

    E --> P T
    T --> B E T |

    (observe a alternativa vazia para a cauda).

  4. Agora, essas duas produções agora posso reescrever no EBNF:

    E --> P {B E}

    que é quase o que o autor obtém, mas eu tenho, em Evez disso P, dentro do padrão de repetição de zero ou mais (a cauda). As outras produções são exatamente as mesmas que ele tem:

    P --> v | "(" E ")" | U E
    B -> "+" | "-" | "*" | "/" | "^"
    U -> "-"

    mas aqui também eu tenho, em Evez de Pna primeira produção paraP .

Então, minha pergunta é: o que estou perdendo? Que transformação algébrica na sintaxe eu preciso proceder agora para obter a mesma forma exata que o autor obtém? Tentei substituições E, mas isso só me leva a loops. Eu suspeito que eu preciso de alguma forma para substituir Ppara E, mas eu não sei qualquer transformação legal que a justifique. Talvez você saiba qual é o último passo que falta?

SasQ
fonte
Por favor, considere usar o LaTeX para formatação. Veja aqui uma cartilha . (Veja aqui uma discussão sobre a adequação do LaTeX nesse caso.)
Raphael

Respostas:

8

A etapa que falta:

E --> P T
T --> B E T |

reescreva E em T:

E --> P T
T --> B P T T | 

Simplifique T:

E --> P T
T --> B P T | 

Equivalente a:

E --> P T
T --> {B P}

E aí está você.

kena
fonte
11
Obrigado por uma boa resposta :-) Agora vejo o que perdi: substituí-o pelo contrário e esse era o problema. Mas ainda não entendo um pedacinho: como você sabe que pode unir os Ts com segurança em um T? Existe alguma regra para isso? (Eu suspeito que poderia ser de alguma forma semelhante à regra em lógica booleana algébrica que diz "aa = a".)
SasQ
BTW, por que essa postagem foi movida para cá do cstheory.sx e qual é a diferença? Eu gostaria de saber para evitar erros no futuro.
SasQ
2
O @SasQ CSTheory destina -se apenas a perguntas de nível de pesquisa em ciência da computação teórica; consulte as perguntas frequentes do CSTheory para obter detalhes.
Juho
11
TxTTεxTxTεeueu=eueuεeu+eu+eu+
@ Rafael: Isso tem algo a ver com a regra da idempotência *? Eu vi no "Dragon Book" (3.3, p.91) isso x** = x*. Essa é a mesma regra que você usou?
SasQ