A gramática que descreve uma equação no prefixo (polonês) a notação sempre inequívoca?

Question

Eu completou recentemente um problema em que me pediram para gerar uma árvore de análise para a expressão $ + \, 5 \, * \, 4 \, 3 $ usando a gramática a seguir e derivação mais à direita:

$$ Expr \ Rightarrow + \, expr \, expr \, | \, * \, Expr \, expr \, | \, 0 \, | \, \ Dots \, | \, 9 \, $$

Enquanto não tenho dificuldade em tomar a derivação e criar sua análise, a questão também pergunta se a gramática é ambígua. No âmbito do que eu fui ensinado, minha única ferramenta para provar a ambigüidade foi encontrar uma árvore de análise diferente para qualquer derivação mais alta ou mais à direita, provando múltiplas parsas e ambigüidade válidas. No entanto, não me disseram como provar inejiguidade. Estou razoavelmente confiante de que a gramática descrita acima é inequívoca baseada parcialmente na intuição e parcialmente porque é projetada para notação de prefixo. Eu tentei gerar novas árvores para uma determinada string para provar ambiguidade, mas desde que o operador é sempre mais à esquerda, não consegui encontrar nenhuma string na qual várias árvores de análise poderiam ser criadas. Se estou enganado, por favor me avise.

Minha pergunta é esta: é possível que a gramática que descreva as cordas usando a notação do prefixo (polonês), como a acima para ser ambíguo? Minha intuição me diz que sempre será inequívoca, mas eu estava me perguntando por que isso pode ser o caso.

Answer 1

Sua pergunta é fácil de responder.Pegue sua gramática e adicione as seguintes regras: $$ \ começo {alinhar *} & S \ to t \ mid \ mathit {expr} \\ & T \ to \ mathit {expr} \ fim {alinhar *} $$

Sua gramática particular, no entanto, parece inequívoca.

Aqui está como eu tentaria provar isso.Primeiro, mostre as expressões são auto-delimitando: nenhuma expressão é um prefixo de outro.

Agora, ao tentar analisar uma expressão, você pode determinar qual regra deve ser aplicada primeiro olhando para o primeiro símbolo.Nos casos interessantes, você então tem que dividir a entrada em duas expressões.A propriedade de auto-delimitação deve tornar isso possível de uma maneira única.