Comment peut-il être montré qu'aucun ll (1) grammaire ne peut être ambigu?
Je sais ce qui est la grammaire ambiguë mais ne pouvait pas prouver le théorème / lemme ci-dessus.
3 Réponses :
Je pense que c'est presque un résultat direct de la définition de LL (1). Essayer des preuves par contradiction; Supposons que vous avez une grammaire LL (1) qui est ambiguë et cherche quelque chose que vous pouvez montrer pour être vrai et non vrai. Comme point de départ "Que savez-vous toujours lorsque vous traitez la saisie?"
Comme cela ressemble à un problème de devoirs et que je n'ai pas terminé le problème plus que je suis esquissé ci-dessus, je m'arrêterai là.
BTW, je ne suis pas * sûr que la conjecture est correcte, mais cela semble raisonnable.
Prouvez qu'aucune grammaire ambiguë ne peut être une grammaire LL (1). Pour les astuces, voir http: //www.cse.ohio- state.edu/~rountev/756/pdf/syntaxanalysis.pdf , diapositives 18-20. Voir aussi http://seclab.cs.sunysb.edu/sekar/cse304/partse .pdf , pg. 11 et précédent.
Voici mon premier projet à une preuve. Cela pourrait avoir besoin d'un réglage fin, mais je pense que cela couvre tous les cas. Je pense que de nombreuses solutions sont possibles. C'est une preuve directe.
(Note latérale: il est dommage, alors ne prend pas en charge les mathématiques, tels que en latex.) P>
Preuve forte> P> Soit t et n être les ensembles de symboles Terminal et non-terminal. P> Laissez les attentes suivantes p> Notez qu'une grammaire est ll ( 1) Si ce qui suit détient pour chaque paire de productions A -> B et A -> C: P> 1. (not MaybeEmpty(B)) or (not MaybeEmpty(C))
2. (First(B) intersect First(C)) = empty
3. MaybeEmpty(C) => (First(B) intersect Follow(A)) = empty
Vous ne pouvez pas prouver une définition. Voir mon commentaire ci-dessus.
@DavidSpector Il y a beaucoup de grammaires non ambiguë mais toujours pas ll (k). Certaines d'entre elles sont LR (k) qui contiennent LL (k). Pour intérêt, vous pouvez être surpris de constater que l'exclusion de l'ambiguïté ne figure dans aucune définition standard de la grammaire LL (k), bien que cette idée soit souvent exprimée de manière informelle. Une des raisons pour laquelle cela pourrait surprendre, c'est que les gens apprennent souvent que ll (k) analysant, qui est prédictif et déterministe. Ll (k) grammaires regardent les mêmes trucs de l'autre côté. Ils sont génératifs non prédictifs et il n'y a pas de concept de déterminisme dans les grammaires formelles.
Je ne vous suis pas. Avez-vous vraiment voulu écrire ce que vous avez fait? Il est facile d'écrire une grammaire comme A -> B; A -> B qui semble être ll (1) car il semble qu'il a clairement clair les premiers ensembles, mais parce qu'ils se chevauchent, la grammaire est ambiguë. Ces grammaires ne sont pas ll (k) car l'ambiguïté ne les fait pas ll (k); Il n'y a pas d'autre raison.
@DavidSpector Oui. Explorons votre exemple. Un analyseur simple pourrait traiter un -> B; A -> B; comme deux productions. Cette grammaire semble ambiguë, mais ce n'est pas, comme le Productions d'une grammaire sont en réalité un ensemble , donc des doublons unifiez. Cette grammaire est en fait la même chose que A-> B. Revenir à la définition de ll (k), cela ne mentionne pas l'exclusion de l'ambiguïté car, bien que nécessaire, il ne soit pas suffisant et peut être dérivé mathématiquement d'autres propriétés. C'est ce qui a été montré ici pour ll (1).
Merci pour votre correction, mais j'ai toujours un doute. L'ambiguïté signifie qu'il y a deux analyses possibles (chemins à travers les productions) pour certaines entrées. Bien qu'il soit vrai que les grammaires sont décrites en utilisant des ensembles, deux productions identiques sont représentées par deux ensembles différents, ayant le même contenu. Ainsi, pour l'entrée B, il y a deux analyses, un choix de la première production et un choix de la seconde. Ll (k) la théorie de la grammaire, je pense, ne fournit pas explicitement un moyen de fusionner des productions avec un contenu identique.
En outre, voici une grammaire ambiguë qui fonctionne de la même manière, mais n'a pas de productions en double: S: 'A' A | B 'A' A: 'A' B: 'A'. L'entrée est "AA".
@DavidSpector J'aime votre exemple car il montre un préfixe commun peut être masqué en nidifiant. Cette grammaire est définitivement ambiguë, car «AA» peut être dérivé de deux manières. Je pense que nous convenons que ce n'est pas non plus ll (k) pour tout k. Notre question est alors de savoir s'il n'est pas ll (k) parce que les grammaires ambigus sont exclus par la définition, ou si ce n'est pas ll (k) car une autre condition est violée. Ici pour K = 1, nous avons d'abord ('A' A) = 'A' et premier (B 'A') = 'A', qui ont une intersection non vide. Donc, par définition, la grammaire n'est pas ll (1). Cependant, ces conditions de faible niveau excluent également l'ambiguïté.
Je pense que vous avez atteint la conclusion pivotante sur laquelle nous sommes d'accord: qu'une intersection non vide entre les premiers ensembles pour deux productions ayant le même symbole non mortminal LHS est la seule façon dont une analyse LL (1) peut avoir plus d'un arbre d'analyse distinct , qui est la définition d'une grammaire ambiguë. Ainsi, si l'ambiguïté est causée par des productions en double (mon premier exemple) ou un préfixe commun imbriqué (mon deuxième exemple), une grammaire LL (1) ne peut pas être ambiguë. Contrairement à votre commentaire original, ll (1) Les grammaires sont prédictifs et déterministes (contrairement aux grammaires générales sans contexte).
@DavidSpector Je vois ma toute première réponse a causé une certaine confusion. Pour être clair, ll (k) les grammaires sont grammaires déterministes sans contexte (adjectif), et je ne voulais pas dire autrement. Plutôt, je disais que le déterminisme (nom) n'est pas un concept distinct avec les grammaires, mais uniquement des caractéristiques de la manière dont les grammates concernent la machinerie informatique des analyseurs, ou au moins des reconnaissants, tous deux déterministes. Laissons ce sujet de côté, car il n'est pas indispensable à notre sujet principal.
@Davidspector Je crois vraiment que nous sommes du même côté de cette discussion. Vous avez défini une intuition sonore que ll (1) grammaires ne peut pas être ambigu et la preuve ici exprime la même idée officiellement.
Je crée actuellement un système d'analyseur LL (k) et je trouve que de simples grammaires intuitives peuvent être ambiguës. Je me rends compte également que l'ambiguïté de l'analyse n'est pas vraiment nocive, si vos actions sémantiques sont effectuées de bas en haut. Je me rends également compte que la réalisation de LR (k) peut être effectuée avec une arrière-marche locale plutôt peu coûteuse. Apprendre beaucoup de choses pratiques en faisant. Ces idées ne sont pas dans des livres. J'aime d'abord allusion comme une optimisation pour une analyse plus générale de la CFG. Plus la grammaire est générale, plus il est facile d'écrire!
Il ne peut y avoir aucune preuve de ce type, car la liberté de l'ambiguïté fait partie de la définition de grammaires LL (k). Vous ne pouvez pas prouver une définition. Un exemple simple est un: a | a. Étant donné l'entrée "A", il existe exactement deux analyses qui reconnaissent ou acceptent le "A". Cette grammaire n'est donc pas ll (1) car elle est ambiguë. Notez que A a un premier ensemble valide: {A}.