Comment déterminer si une langue est LL (1) LR (0) SLR (1)

StackOverflow https://stackoverflow.com/questions/475949

Question

Existe-t-il un moyen simple de déterminer si une grammaire est LL (1), LR (0), SLR (1) ... rien qu’en regardant sur la grammaire sans effectuer d’analyse complexe?

Par exemple: pour décider si une grammaire BNF est LL (1), vous devez calculer les ensembles First et Follow, ce qui peut parfois prendre beaucoup de temps.

Quelqu'un a-t-il une idée de la manière de procéder plus rapidement? Toute aide serait vraiment appréciée!

Était-ce utile?

La solution

Tout d’abord, un peu de pédantisme. Vous ne pouvez pas déterminer si une langue est l'inspecteur d'une grammaire pour LL (1). Vous pouvez uniquement faire des déclarations sur la grammaire elle-même. Il est parfaitement possible d’écrire des grammaires non-LL (1) pour les langues pour lesquelles une grammaire LL (1) existe.

Avec cela à l'écart:

  • Vous pouvez écrire un analyseur syntaxique pour la grammaire et demander à un programme de calculer d'abord et de suivre les ensembles et autres propriétés pour vous. Après tout, c’est le gros avantage des grammaires BNF: elles sont compréhensibles par la machine.

  • Inspectez la grammaire et recherchez les violations des contraintes de différents types de grammaire. Par exemple: LL (1) permet une récursion droite mais pas gauche. Ainsi, une grammaire contenant une récursion gauche n'est pas LL (1). (Pour les autres propriétés de grammaire, vous devrez passer du temps de qualité avec les définitions, car je ne me souviens de rien d’autrefois:).

Autres conseils

En réponse à votre question principale: pour une grammaire très simple, il peut être possible de déterminer s'il s'agit de LL (1) sans construire les ensembles FIRST et FOLLOW, par exemple

.
  

A & # 8594; A + A | un

     

n'est pas LL (1), alors que

     

A & # 8594; a | b

est.

Mais lorsque vous devenez plus complexe que cela, vous devrez procéder à une analyse.

  

A & # 8594; B | un
  B & # 8594; A + A

Ceci n'est pas LL (1), mais cela peut ne pas être immédiatement évident

Les règles de grammaire pour l'arithmétique deviennent rapidement très complexes:

  

expr & # 8594; terme {'+' terme}
  terme & # 8594; facteur {'*' facteur}
  facteur & # 8594; nombre | '(' expr ')'

Cette grammaire ne gère que la multiplication et l’addition, et il n’est déjà pas clair si la grammaire est bien LL (1). Il est encore possible de l'évaluer en regardant à travers la grammaire, mais à mesure que la grammaire grandit, elle devient moins faisable. Si nous définissons une grammaire pour un langage de programmation complet, une analyse complexe sera certainement nécessaire.

Cela dit, il existe quelques signes évidents indiquant que la grammaire n’est pas LL (1) & # 8212; comme le A & # 8594; A + A ci-dessus & # 8212; et si vous pouvez trouver l'un de ces éléments dans votre grammaire, vous saurez qu'il doit être réécrit si vous écrivez un analyseur récursif de descente. Mais il n’existe aucun raccourci pour vérifier que la grammaire est LL (1).

Un aspect, "la langue / grammaire est ambiguë", est une question indécidable connue comme le Envoyer une correspondance et résolution des problèmes .

Extrait du livre "Compilers: Principles, Techniques, & amp; Outils " par Aho, et. al.

Page 223:

Une grammaire G est LL (1) si et seulement si à chaque fois que A - > alpha | beta sont deux productions distinctes de G, les conditions suivantes sont remplies:

  1. Pour aucun terminal "a" les chaînes alpha et bêta doivent-elles dériver des chaînes commençant par "a"
  2. Au plus, alpha et beta peuvent générer la chaîne vide
  3. Si beta peut atteindre la transition vide par zéro ou plusieurs transitions, alpha ne dérive aucune chaîne commençant par un terminal dans FOLLOW (A). De même, si alpha peut atteindre la transition vide par zéro ou plusieurs transitions, beta ne dérive aucune chaîne commençant par un terminal dans FOLLOW (A)

En gros, il s’agit de vérifier que la grammaire a réussi le test de paire par discordance et qu’elle n’implique pas non plus une récursion à gauche. Ou plus succinctement, une grammaire G récursive à gauche ou ambiguë ne peut être LL (1).

Vérifiez si la grammaire est ambiguë ou non. Si tel est le cas, la grammaire n’est pas LL (1) car aucune grammaire ambiguë n’est LL (1).

ya il y a des raccourcis pour la grammaire ll (1)

1) si A - > B1 | B2 | ....... | Bn     puis première intersection (B1) première intersection (B2) intersection .first (Bn) = ensemble vide puis correspond à la grammaire ll (1)

2) si A- > B1 | epsilon      alors B1 suivre l'intersection (A) est un ensemble vide

3) si G est une grammaire telle que chaque non terminal ne dérive qu’une production, alors la grammaire est LL (1) 

p0 S' → E
p1 E → id
p2 E → id ( E )
p3 E → E + id
  • Construisez le DFA LR (0), les tables FOLLOW pour E et les tables action / goto des reflex.
  • S'agit-il d'une grammaire LR (0)? Prouvez votre réponse.
  • À l'aide des tables de reflex, indiquez les étapes (analyses, réductions, acceptation) d'une analyse syntaxique d'un analyseur syntaxique LR:
    id (id + id)
Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top