Existe-t-il un moyen de distinguer la grammaire LL (k) et LR (k)?

J'étudie récemment la conception de compilateurs. J'ai appris l'existence de deux types de grammaire: la grammaire LL et la grammaire LR.

Nous savons également que chaque grammaire LL est LR, c'est-à-dire que la grammaire LL est un sous-ensemble approprié de la grammaire LR. Le premier est utilisé dans l'analyse descendante et le second est utilisé dans l'analyse ascendante.

Mais est-il possible de dire qu'une grammaire donnée est LL ou LR?

grammaires L L ( k ) et L R ( k ) sont agréables non seulement parce qu'elles peuvent être analysées efficacement, mais aussi parce que nous pouvons vérifier si une grammaire est L L ( k ) ou L R ( k $LL(k)$$LR(k)$$LL(k)$$LR(k)$, et parce que nous pouvons générer des tables pour eux (les tables d'analyse sont utilisées pour analyser les chaînes d'entrée). Notez que pour ces deux classes, avoir la table d'analyse vous permet immédiatement de vérifier si les grammaires sont dans les classes, car c'est le cas si et seulement si les tables ne contiennent aucune erreur. De plus, oui, il existe des classes de grammaires que nous pouvons analyser efficacement si nous avons une table d'analyse, mais pour lesquelles nous ne pouvons pas générer la table si elle existe.

Tout manuel sur les méthodes d'analyse vous apprendra comment générer les tableaux pour les méthodes et éventuellement aussi pour L R ( 1 ) (bien que S L R ( 1 ) soit plus courant). Des manuels tels que Parsing Theory de Sippu et Soisalon-Soininen traitent également la génération de table d'analyse pour les grammaires L L ( k ) et L R ( k ) .$LL(1)$$LR(1)$$SLR(1)$$LL(k)$$LR(k)$

Malheureusement, pour des grammaires vraiment étranges, les tables d'analyse pour et L R ( k ) (mais pas pour L L ( 1 ) ) peuvent exploser et devenir énormes; ils le feront même pour des grammaires normales si k est suffisamment élevé. Il existe des tests disponibles qui peuvent vérifier si une grammaire est L L ( k ) ou L R ( k $LL(k)$$LR(k)$$LL(1)$$k$$LL(k)$$LR(k)$ou non qui s'exécutent en temps polynomial (la génération de table est exponentielle). Pour plus de détails, lisez le manuel ci-dessus. Notez que dans de nombreux cas, la table est de taille raisonnable, donc le test n'est pas nécessaire.

$k$$k$$LL(k)$$LR(k)$$LR(k)$$k$$LL(c)$$c$$k$(voir ici pour plus de détails).

Nous devons seulement vérifier qu'une grammaire est LL ou non car chaque grammaire LL est LR qui est LL est un sous-ensemble approprié de LR. Donc, si une grammaire est LL, elle doit être LR mais chaque LR n'est pas LL.

Une grammaire G est dans LL ssi A-> C | D, la condition suivante doit être vérifiée:

1. First (C) et First (D) sont des ensembles disjoints.
2. Si vide est dans First (D), First (C) et Follow (A) sont des ensembles disjoints de même que empty est dans First (C).