Comment faire pour déterminer si une langue est LL(1) LR(0) SLR(1)
Est-il un moyen simple de déterminer si une grammaire est LL(1), LR(0), SLR(1)... il suffit de regarder sur la grammaire, sans faire l'analyse complexe?
Par exemple: de décider De la BNF, de la Grammaire est LL(1) vous devez calculer d'Abord et Suivez jeux - qui peut prendre beaucoup de temps dans certains cas.
Quelqu'un a une idée comment faire cela plus rapidement?
Toute aide serait vraiment appréciée!
OriginalL'auteur Chris | 2009-01-24
Vous devez vous connecter pour publier un commentaire.
Tout d'abord, un peu de pédantisme. Vous ne pouvez pas déterminer si un langue est LL(1) à partir de la visite d'une grammaire pour cela, vous pouvez seulement faire des déclarations au sujet de la grammaire lui-même. Il est parfaitement possible d'écrire non LL(1) les grammaires de langues pour lesquelles une grammaire LL(1) existe.
Avec cela de la sorte:
Vous pourriez écrire un analyseur syntaxique de la grammaire et un programme de calculer d'abord et suivez les ensembles et d'autres propriétés pour vous. Après tout, c'est le gros avantage de la BNF, de grammaires, ils sont de la machine compréhensible.
Inspecter la grammaire et de regarder pour violations de contraintes par la grammaire les types. Par exemple: LL(1) permet de droite mais pas à gauche de la récursivité, ainsi, une grammaire qui contient récursion à gauche n'est pas LL(1). (Pour les autres propriétés de la grammaire, vous allez devoir passer un peu de temps de qualité avec les définitions, parce que je ne me rappelle de rien d'autre sur le dessus de ma tête en ce moment :).
+1 pour la pédanterie. C'est une touche de distinction, et le fait qu'il est généralement passées sous silence, est un obstacle à la compréhension.
Idem.
OriginalL'auteur Aaron Maenpaa
En réponse à votre question principale: Pour une très simple de la grammaire, il peut être possible de déterminer si elle est LL(1) sans construction de la PREMIÈRE et de SUIVRE des ensembles, par exemple
est.
Mais quand vous obtenez plus complexe que cela, vous aurez besoin de faire une analyse.
Ce n'est pas LL(1), mais il peut ne pas être immédiatement évident
Les règles de grammaire, de l'arithmétique rapidement devenir très complexe:
Cette grammaire ne gère que des multiplications et des additions, et déjà il n'est pas immédiatement clair si la grammaire est LL(1). Il est encore possible de l'évaluer en regardant à travers la grammaire, mais aussi la grammaire grandit, il devient de moins en moins réalisable. Si nous sommes à la définition d'une grammaire pour l'ensemble d'un langage de programmation, il est presque certainement va prendre un certain complexe d'analyse.
Cela dit, il ya quelques signes que la grammaire n'est pas LL(1) — comme l'A → A + A ci — dessus et si vous pouvez trouver l'un de ces dans votre grammaire, vous savez qu'il doit être réécrit si vous êtes en train de rédiger un appel récursif à la descente de l'analyseur. Mais il n'y a pas de raccourci pour vérifier que la grammaire est LL(1).
En fait vous avez besoin de SUIVRE des ensembles de LL(1) dans le cas où le nonterminals sont les valeurs null. De cette façon, vous pouvez "look" de la non-terminal en question pour voir qui de la production à l'utilisation.
OriginalL'auteur Bruce Alderman
Un aspect, est la langue, de la grammaire ambiguë", est connu indécidable question comme le Post correspondance et l'arrêt de problèmes.
OriginalL'auteur BCS
Directement à partir de l'ouvrage "les Compilateurs: Principes, Techniques, & Outils" par Aho, et. al.
Page 223:
Une grammaire G est LL(1) si et seulement si chaque fois qu'Un -> alpha | bêta sont deux productions distinctes de G, les conditions suivantes s'appliquent:
Essentiellement, c'est une question de vérification de la grammaire passe le Paires Disjointness Test et aussi n'implique pas de Récursion à Gauche. Ou plus succinctement une grammaire G, c'est-à-gauche récursive ou ambiguë ne peut pas être LL(1).
OriginalL'auteur Matthew Erwin
Vérifier si la grammaire est ambiguë ou non. Si c'est le cas, la grammaire n'est pas LL(1), car aucun ambigu de la grammaire est LL(1).
OriginalL'auteur Ananya Sahu
ya il existe des raccourcis pour grammaire ll(1)
1) si Un->B1|B2|.......|Bn
alors tout d'abord(B1)de l'intersection de la première(B2)de l'intersection .la première(Bn)=ensemble vide, alors il est grammaire ll(1)
2) si Un->B1|epsilon
puis B1 intersection de la suite(Un)est l'ensemble vide
3) si G est une grammaire quelconque, de telle façon que chaque non terminal tire une seule production, alors la grammaire est LL(1)
OriginalL'auteur srinath
id ( id + id )
OriginalL'auteur dida