Existe-t-il une grammaire LL (k) pour PCF?

Question

Nous travaillons sur l'analyse descendante dans une classe de conception de compilateur. Les exemples sont tous les langages Java. J'ai décidé d'essayer un langage fonctionnel simple pour le rendre intéressant, donc je suis allé avec PCF (see e.g. here). Cependant, je n'arrive pas à l'inclure dans une grammaire LL (1). Je pense que le problème est l'application de la fonction (c'est-à-dire la juxtaposition de deux expressions). Je ne reçois pas de réponses claires sur la façon de déterminer si c'est juste mon manque de compétence ou si c'est une langue pour laquelle il n'y a pas de grammaire LL (1), ou LL (k) d'ailleurs. Quelqu'un peut-il clarifier si je dois juste être plus intelligent ou s'il n'existe tout simplement pas une telle grammaire?

Fondamentalement, ma version de PCF est quelque chose comme l'esquisse ci-dessous (majuscules sont non-terminaux, "//" commence commentaire). Je dis "quelque chose comme" parce que je ne suis pas marié à exactement cela et j'ai écrit de nombreuses variantes - je veux juste une variante raisonnable de PCF.

Notez que j'ai essayé le factorisation à gauche et la prise en compte de la préséance avec des non-terminaux intermédiaires.

Exp -> Const  // integer and boolean literals, normal ops e.g. + 
    | if Exp then Exp else Exp 
    | lambda identifier dot Exp //lambda (function) abstraction 
    | Exp Exp      // function application 
    | fix Exp      // fixpoint operator (recursion) 

Answer 1

Le problème est que votre grammaire reste récursif, qui ne joue pas bien avec parseurs haut vers le bas, comme décrit par LL (k). En particulier, essayer d'analyser un Exp conduit à essayer d'analyser d'abord la première partie d'une application de fonction Exp Exp ... qui, pour un analyseur descendant, crée une boucle infinie.

La solution probable dans votre cas serait de mettre en œuvre une application fonction de longueur arbitraire dans un bon style récursif:

AppExp -> Exp | Exp AppExp 

Exp -> Const | (AppExp) | ... 

Notez que cette construction supprime une ambiguïté de la grammaire. Malheureusement, il résout dans la mauvaise direction pour votre problème - et il n'y a pas de bonne façon de le réparer; une version associative gauche:

AppExp -> Exp | AppExp Exp 

sera tout aussi récursive à gauche que l'original. La manière (pas si sympathique) de corriger cela dans le cadre d'un analyseur descendant est d'accepter la grammaire associative droite, de traiter AppExp comme une liste, et de l'inverser après l'analyse afin que votre syntaxe abstraite arbre a l'associativité vous voulez:

application expression: f a b c d 
    | 
    | LL(1) parse 
    v 
right-associative ---> left-associative 
     @    list    @ 
    /\   reversal   /\ 
    f @       @ d 
     /\      /\ 
     a @      @ c 
     /\     /\ 
     b @     @ b 
      /\    /\ 
      c .    . a 
       |    | 
       d    f 

bibliothèques de l'analyseur de Combinator comme parsec ont généralement commodément caractéristiques pré-emballés qui le fera pour vous.

En termes de langue théorie, cela démontre la distinction entre la langue acceptée par une grammaire et une analyse produit par un analyseur syntaxique basé sur cette grammaire ....