Y a-t-il un exemple de grammaire de langage qui est possible pour Yacc à exprimer mais impossible pour Antlr4 ?

Question

J'essaie récemment d'apprendre sur les analyseurs de langage et ai toujours vu l'examen sur la différence entre Yacc et Antlr (à propos de LALR et LL). C'était toujours une conclusion comme "LALR est plus puissant". Mais je ne peux pas comprendre ce que cela signifie vraiment

Alors est-ce que quelqu'un pourrait s'il vous plaît m'éclairer sur la signification du mot puissant ici ?

Je suppose simplement que cela voudrait dire "Yacc peut faire quelque chose qu'Antlr ne peut pas faire", si c'est le cas, je souhaiterais pouvoir voir l'exemple exact à ce sujet

Answer 1

Une langue qui est LR(1) mais pas LL(*)

La question Comparaison théorique des grammaires LL et LR dispose d'une réponse avec la langue suivante qui est LR(1) mais pas LL(*):

{ a^i b^j | ij }

C'est-à-dire, un certain nombre de a suivi par un nombre égal ou inférieur de b.

La même langue est citée par cette réponse à la question similaire Exemple d'une grammaire LR qui ne peut pas être représentée par LL?. Cependant, la question présente est différente car l'autre mentionne "LL", signifiant LL(k), tandis que nous parlons ici de LL(*) (et Antlr4).

Démonstration intuitive (pas une preuve)

Expliquons intuitivement que ceci est LR(1) mais pas LL(*).

Tout d'abord, la grammaire LR(1) (copiée de la deuxième réponse liée):

S ::= a S | P
P ::= a P b | 

De manière intuitive, ceci est LR(1) car un parseur LR(1) peut empiler n'importe quel nombre de symboles a sur sa pile, puis, lorsqu'il arrive au premier b, commencer à dépiler les symboles a correspondants en paires a,b, en utilisant la première production pour P. S'il se retrouve sans symboles b, il dépile les symboles a restants en utilisant la première production pour S. S'il se retrouve sans symboles a alors qu'il reste des symboles b, il signale une erreur. (Rappelez-vous, dans ce contexte, nous sommes principalement concernés par la reconnaissance, donc la sortie est soit "oui" soit "erreur".)

En revanche, cette grammaire n'est pas LL(*). De manière intuitive, un parseur LL(*) doit décider, lorsqu'il voit le premier a, s'il doit utiliser la première ou la deuxième production de S. Il aimerait anticiper pour voir s'il y a autant de symboles b que de symboles a restants, car dans le cas contraire, il saurait qu'il doit utiliser la première production pour "consommer" les symboles a en trop. Mais la capacité de prévision de LL(*) est limitée à reconnaître un langage régulier, et un langage régulier ne peut pas reconnaître { a^i b^i } puisqu'il ne peut pas "compter".

Bien sûr, le fait qu'une grammaire ne soit pas LL(*) n'implique pas que le langage ne soit pas LL(*), car il pourrait exister une grammaire plus astucieuse. Pour prouver qu'il n'est pas LL(*), je commencerais probablement par la définition formelle, supposerais que j'avais une grammaire avec ces conditions, puis utiliserais un argument de lemme du pompage pour montrer qu'elle ne peut pas reconnaître correctement le langage d'intérêt. Mais je laisserai aux ressources liées le soin de justifier rigoureusement que le langage n'est pas LL(*).

Interprétation à un niveau supérieur

La façon dont je le vois, LL prend des décisions en descendant dans l'arbre d'analyse, alors que LR les prend en remontant. Pour créer un langage qui n'est pas LL(k), nous disposons les choses de manière à ce qu'un parseur hypothétique doive s'engager dans une interprétation d'un symbole lorsque l'information nécessaire pour le faire est au-delà de l'horizon de k symboles. Pour le rendre pas LL(*), nous devons placer l'information cruciale au-delà d'un horizon qui ne peut être franchi qu'en reconnaissant d'abord un langage non régulier.

En revanche, LR peut empiler des symboles, reportant leur interprétation jusqu'à ce qu'il ait vu la fin de la production associée et déjà construit des interprétations de tout ce qui se trouve entre les deux.

Pour essayer de rendre ceci un peu plus concret, imaginez un langage de programmation qui a deux types de choses entre accolades, disons, des blocs de code et des littéraux d'objet (comme en Javascript). Imaginez qu'ils peuvent tous les deux apparaître dans le même contexte (contrairement à Javascript):

  var x = { console.log("Je suis un bloc de code"); /*le résultat est*/ 6; };
  var x = { a:1, b:2 };

Dans ce contexte, un parseur rencontre {. LL doit décider immédiatement s'il s'agit du début d'un bloc de code ou d'un littéral d'objet. En Javascript, les clés des littéraux d'objets doivent être des identifiants ou des littéraux de chaîne, et l'union des deux est un langage régulier, donc un parseur LL(*) peut passer rapidement à côté de l'expression régulière pour "identifiant ou littéral de chaîne" pour vérifier s'il y a un :, ce qui signalerait un littéral d'objet (sinon bloc de code).

  {                    // hmm, code ou objet?
  { a                  // clé possible de littéral objet
  { a :                // a-ha! définitivement littéral objet

S'il s'agissait plutôt d'une clé pouvant être une expression de type chaîne arbitraire, alors LL(*) est en difficulté car il doit équilibrer les parenthèses pour passer la clé présumée afin de vérifier le ::

  {                    // début de littéral objet?
  { (                  // oh là là ...
  { (a                 // je suis
  { (a ?               //     en train de me
  { (a ? b             //             perdre
  { (a ? b :           // est-ce le ':' après une clé? aider!

En revanche, LR reporte volontiers l'interprétation de {, l'empilant, et procède, en fait, avec deux interprétations potentielles jusqu'à ce qu'un jeton les désambiguïse.

J'espère que cela fournit une certaine intuition sur les types de choses que LR contient mais pas LL(*)

Il existe des exemples de l'inverse (LL(*) mais pas LR), bien que je ne sache pas à quoi ils ressemblent ("pas LR" est une classe difficile à imaginer); voir la première question liée pour plus de détails.

Prédicats sémantiques Antlr4

Maintenant, le titre de la question demande en réalité à propos d'Antlr4. Antlr4 dispose de prédicats sémantiques, permettant efficacement au programmeur d'insérer un calcul de prévision arbitraire. Donc, si vous êtes prêt à sortir du formalisme de la grammaire, en réalité il n'y a pas de limite (à part la décidabilité) à ce qu'un parseur Antlr4 peut reconnaître.

Answer 2

Voici un exemple de grammaire, pour lequel il existe des exemples que ni ANTLR ni YACC ne peuvent analyser sans manipulation :

   stmt = declaration ';' ;
   stmt = expression ';' ;
   declaration = type  ID ;
   type = ID '*' ;
   expression = product ;
   product = ID ;
   product = product '*' ID ;

Voici un exemple que ni ANTLR ni L(AL)R ne peuvent analyser :

x * y ;

en utilisant cette grammaire.

Il y a deux analyses possibles : 1) comme une instruction, 2) comme une déclaration.

Cet exemple est tiré du langage C. (Vous pouvez établir une grammaire plus petite ; j'ai essayé de laisser cela sous une forme facile à comprendre son réalisme).

Les analyseurs L(AL)R et ANTLR vous fourniront au maximum une dérivation. Ce qui signifie qu'ils rateront toute alternative.

On peut tricher avec le mécanisme d'analyse pour résoudre cela (comme GCC le faisait notoirement) en apportant des informations sur la table des symboles. Cela mêle l'analyse et la construction de la table des symboles qui, à mon avis, transforme simplement le parseur en fouillis. En particulier, vous ne pouvez pas décider de ce qu'il accepte en ne regardant que la grammaire.

Le problème est que ANTLR et L(AL)R n'analyseront pas tous les langages libres de contexte. Ils n'analysent que des sous-ensembles (différents); cela signifie que l'un peut analyser certaines instances que l'autre ne peut pas et vice versa. Cela signifie que l'un n'est pas plus puissant que l'autre.

Si vous voulez un analyseur plus puissant, par exemple, qui traite entièrement des langages libres de contexte, vous devez vous tourner vers les analyseurs Earley, ou les analyseurs GLR ou GLL. Les analyseurs Earley ne sont pas très efficaces. Les analyseurs GLR et GLL tendent à être efficaces sur des parties de la grammaire qui n'introduisent pas d'ambiguïtés (analyses multiples) ou ne nécessitent pas de grands nombres de regards en avant. Mais la plupart des constructions de langage de programmation que vous pourriez vouloir analyser ont tendance à ne pas être déroutantes car les gens ont du mal à les lire dans ce cas également.

En raison des limites de L(AL)R et ANTLR, ma société (Semantic Designs) utilise des analyseurs GLR pour environ 40 langages. Cela inclut le C++17 complet qui présente plus d'analyses ambiguës et de cas de grands regards en avant que vous ne pouvez en imaginer, y compris l'exemple ci-dessus, la plupart d'entre eux étant beaucoup plus obscurs. Autant que je sache, nous avons le seul analyseur C++17 qui utilise une grammaire directe ; GCC et Clang utilisent des descentes récursives codées à la main avec de nombreuses vérifications imbriquées de la table des symboles.

[L'auteur de l'autre réponse, Scott McPeak, a construit des analyseurs C++ pour d'anciens dialectes de C++ en utilisant GLR, plus ou moins en même temps que nous avons commencé à le faire. Chapeau bas à lui.]