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

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.

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.

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.