Je veux prouver que cette grammaire est ambiguë, mais je ne suis pas sûre de la façon dont je suis censée le faire. Dois-je utiliser des arbres d'analyse?Comment puis-je montrer que cette grammaire est ambiguë?
S -> if E then S | if E then S else S | begin S L | print E
L -> end | ; S L
E -> i
Vous pouvez mettre la grammaire dans un générateur d'analyseur qui prend en charge toutes les grammaires sans contexte, un générateur d'analyseur général sans contexte. Générez l'analyseur, puis analysez une chaîne qui vous semble ambiguë et découvrez en regardant la sortie de l'analyseur.
Un générateur d'analyseur général sans contexte génère des analyseurs qui produisent toutes les dérivations en temps polynomial. Des exemples de tels générateurs d'analyseurs comprennent SDF2, Rascal, DMS, Elkhound, ART. Il y a aussi une version backtracking de yacc (btyacc) mais je ne pense pas qu'elle le fasse en temps polynomial. Habituellement, la sortie est codée sous la forme d'un graphique où des arbres alternatifs pour les sous-phrases sont codés avec un ensemble imbriqué d'arbres alternatifs.
Vous pouvez le montrer est ambigu si vous pouvez trouver une chaîne qui parse plus d'une façon:
if i then (if i then print i else print i ;)
if i then (if i then print i) else print i ;
Cela arrive à être l'ambiguïté classique « dangling else ». Googler votre tag (s), titre & grammaire donne d'autres résultats.
Toutefois, si vous ne vous arrive pas à deviner une chaîne ambiguë puis googling your tag(s) & title:
how can i prove that this grammar is ambiguous?
Il n'y a pas de méthode facile pour prouver une grammaire sans contexte ambigu - en fait, the question is undecidable, par réduction au Post correspondence problem.
Je vote pour clore cette question hors-sujet parce que ce n'est pas une question de programmation. –
Que voulez-vous dire par _ambiguous_? Qu'il existe un mot pour lequel plus d'une dérivation est possible? – Codor
@Codor Oui, il doit y avoir au moins une chaîne avec plus d'un arbre d'analyse. – name