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

  1. 34

    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 :).

    Bon point sur la distinction entre la langue et de la grammaire. Si une grammaire n'est pas LL(1), il peut encore être possible de construire une grammaire LL(1) de la langue.
    +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

  2. 15

    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

    A → A + A | a

    n'est pas LL(1), tandis que

    A → A | b

    est.

    Mais quand vous obtenez plus complexe que cela, vous aurez besoin de faire une analyse.

    A → B | a

    B → A + A

    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:

    expr → terme { '+' terme }

    terme → facteur de { '*' facteur de }

    facteur → nombre de | '(' expr ')'

    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).

    BTW, vous n'avez pas besoin de calculer SUIVRE pour LL(1), puisque c'est uniquement définie en termes de la PREMIÈRE.
    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

  3. 9

    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

  4. 9

    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:

    1. Pour aucune borne "a" faire les deux alpha et bêta dériver les chaînes de caractères commençant par "a"
    2. Au plus un de alpha et bêta peut dériver la chaîne vide
    3. Si bêta peut atteindre le vide de transition par zéro, un ou plusieurs transitions, puis alpha ne vient pas d'une chaîne commençant par un terminal dans la suite(UN). De même, si alpha peut atteindre le vide de transition par zéro, un ou plusieurs transitions, puis bêta ne vient pas d'une chaîne commençant par un terminal dans la suite(UN)

    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

  5. 2

    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

  6. 0

    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

  7. -2
    p0 S' → E
p1 E → id
p2 E → id ( E )
p3 E → E + id
    • Construire le LR(0) DFA, l'ensemble E et du REFLEX action/goto tables.
    • Est-ce une LR(0) de la grammaire? Prouver votre réponse.
    • À l'aide de la SLR de tables, de montrer les étapes (quarts de travail, les réductions, les accepter) d'un analyseur LR analyse:
      id ( id + id )

    OriginalL'auteur dida