Comment analyser le terme lambda

Question

Je voudrais analyser un lambda-calcul. Je ne sais pas comment analyser le terme et respecter la priorité des parenthèses. Ex:

(lx ly (x(xy)))(lx ly xxxy) 

Je n'arrive pas à trouver le bon moyen de le faire. Je ne peux pas voir l'algorithme adapté. Un terme est représenté par une structure qui a un type (APPLICATION, ABSTRACTION, VARIABLE) et un composant droit et gauche de type "terme struc".

Une idée de comment faire cela?

EDIT

Désolé de vous déranger à nouveau, mais je veux vraiment comprendre. Pouvez-vous vérifier la fonction "expression()" pour me faire savoir si j'ai raison.

Term* expression(){ 
    if(current==LINKER){ 
     Term* t = create_node(ABSTRACTION); 
     get_next_symbol(); 
     t->right = create_node_variable(); 
     get_next_symbol(); 
     t->left = expression(); 
    } 

    else if(current==OPEN_PARENTHESIS){ 
     application(); 
     get_next_symbol(); 
     if(current != CLOSE_PARENTHESIS){ 
      printf("Error\n"); 
      exit(1); 
     } 
    } 
    else if(current==VARIABLE){ 
     return create_node_variable(); 
    } 
    else if(current==END_OF_TERM) 
    { 
     printf("Error"); 
     exit(1); 
    } 
} 

Merci

Answer 1

La peut être simplifiée en séparant l'application d'autres expressions:

EXPR -> l{v} APPL  "abstraction" 
    -> (APPL)  "brackets" 
    -> {v}   "variable" 

APPL -> EXPR +  "application" 

La seule différence avec votre approche est que l'application est représentée comme une liste d'expressions, parce que abcd peut être implicitement lu comme (((ab)c)d) de sorte que vous pourriez bien le stocker comme abcd tout en analysant.

Sur la base de cette grammaire, un analyseur simple descente récursive peut être créé avec un seul caractère de préanalyse:

EXPR: 'l' // read character, then APPL, return as abstraction 
     '(' // read APPL, read ')', return as-is 
     any // read character, return as variable 
     eof // fail 

APPL: ')' // unread character, return as application 
     any // read EXPR, append to list, loop 
     eof // return as application 

Le symbole racine est APPL, bien sûr. En tant qu'étape post-analyse, vous pouvez transformer votre APPL = liste d'EXPR en une arborescence d'applications. La descente récursive est si simple que vous pouvez facilement vous transformer en une solution impérative avec une pile explicite si vous le souhaitez.