Suppression de la récursion gauche dans la grammaire tout en maintenant l'association gauche de l'opérateur

13

J'ai un problème avec cet exercice:

Soit G la grammaire ambiguë suivante pour le λ-calcul:

E → v | λv.E | EE | (E)

où E est le symbole non terminal unique, λv.E représente l'abstraction par rapport à la variable v dans E et EE représente l'application.

  1. Définissez une grammaire LL (1) G ′ telle que L (G ′) = L (G) et l'ambiguïté de G soit résolue en imposant les conventions habituelles suivantes:
    1. l'abstraction est associative droite;
    2. l'application est laissée associative;
    3. l'application a une priorité plus élevée que l'abstraction.
  2. Afficher la table d'analyse LL (1) pour G ′ et l'arbre d'analyse obtenu lors de l'analyse de la chaîne λv1. λv2. v1v2v1.

J'ai éliminé l'ambiguïté en établissant la priorité et l'association, obtenant cette grammaire:

E -> EF | F
F -> λv.G | G
G -> (E) | v

qui n'est pas LL (1), puisque la production E -> EFest laissée récursive. Cependant, en éliminant la récursion gauche de cette production, j'obtiens:

E -> FE¹
E¹-> FE¹ | ɛ
F -> λv.G | G
G -> (E) | v

qui n'est pas conforme à l'exigence 1.2.

J'ai cherché une solution sur Internet, mais il semble qu'il ne soit pas possible d'éliminer la récursion gauche en préservant l'associativité gauche.

Cependant, cet exercice est apparu à l'examen des compilateurs il y a quelques années, il doit donc y avoir une bonne réponse.

Merci de votre aide.

Marco DallaG
la source

Réponses:

11

Compatibilité de l'associativité gauche et de l'analyse LL (1)

Vous venez de frapper l'une des principales incohérences dans l'utilisation de la syntaxe sans contexte (CF). Les gens veulent choisir des grammaires pour que l'arbre d'analyse reflète la structure prévue de la phrase, proche de sa sémantique, en particulier dans le cas des opérateurs non associatifs, tels que l' application . C'était à peu près l'intention originale des grammaires des FC en linguistique. Mais en même temps, ils se limitent à une technologie d'analyse qui ne tolérera que certains types de grammaires.

En effet, si l'arbre d'analyse doit refléter l'associativité gauche d'un opérateur, alors la grammaire est nécessairement récursive à gauche, car le nœud d'application supérieur dans l'arbre d'analyse ajoute nécessairement le terme le plus à droite des applications successives non paréthisées. Donc l'analyse LL est hors de question. Tu as raison.

Il y a deux solutions à cela. La première consiste à ne pas se fier à l'analyseur pour donner le "arbre d'analyse" à utiliser pour les étapes ultérieures du traitement (comme la réduction de l'expression lambda, ici). Cela a conduit au concept d'arbres de syntaxe abstraite (AST) qui peuvent être construits à partir de l'arbre d'analyse, mais avec une structure différente.

L'autre solution consiste à utiliser des techniques d'analyse plus générales qui acceptent toute grammaire CF et à analyser conformément à celle-ci. Les analyseurs généraux des FC sont une technologie bien développée (et je ne cesse de me demander pourquoi LL reste si populaire).

Je n'ai aucune idée de ce qui pourrait être considéré comme une réponse appropriée à ces exigences contradictoires.

Ce que je ferais, c'est montrer qu'ils sont en contradiction avec les exigences. Donnez une première grammaire qui respecte les contraintes d'associativité et de priorité, puis transformez la grammaire en grammaire LL (1) pour l'analyse.

Le fait que quelque chose soit apparu dans un journal ou lors d'un examen n'est pas une garantie totale qu'il est correct. Et je me trompe peut-être aussi ... mais j'ai fait quelques vérifications, en plus de ma propre connaissance du problème.

À propos de cet exemple spécifique

Cela dit, la première grammaire que vous proposez ne semble pas tout à fait correcte. Il n'a pas de moyen de produire λu.λv.v.

Une astuce à savoir est de commencer par les opérateurs (ici abstraction ou application) avec la priorité la plus basse (abstraction). Il en va de même pour les expressions arithmétiques.

babou
la source
Merci beaucoup pour votre commentaire détaillé. Vous avez raison, j'ai fait une erreur avec la première grammaire, merci aussi. Je demanderai alors au professeur.
Marco DallaG
Je peux ajouter à la réponse, avec une petite note sur la conception grammaticale pour les nuls (moi aussi), si cela vous intéresse. Dites-nous aussi ce que dit votre professeur à ce sujet.
babou
Je mettrai à jour le fil lorsque le professeur répondra à cette question. Quoi qu'il en soit, n'hésitez pas à ajouter plus d'informations si ce n'est pas un problème pour vous, bien sûr, je l'apprécierais beaucoup. Merci encore pour votre aide
Marco DallaG
@MarcoDallaG Je suis tombé sur cela en travaillant sur TAPL de Pierce. Est-ce que votre professeur a dit quelque chose de différent de cette réponse? :)
lcn
0

Ma tentative:

E  -> A | λv.E
A  -> FA'
A' -> A | ɛ
F  -> (E) | v

Cette grammaire est LL (1) et doit respecter les propriétés requises.


la source