Wie lambda Ausdruck zu behandeln

Question

Ich würde gerne ein Lambda-Kalkül analysieren. Ich weiß nicht, wie man den Begriff analysiert und Klammernpriorität respektiert. Bsp .:

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

Ich schaffe es nicht, den guten Weg zu finden, dies zu tun. Ich kann den angepassten Algorithmus einfach nicht sehen. Ein Ausdruck wird durch eine Struktur dargestellt, die einen Typ (ANWENDUNG, ABSTRAKTION, VARIABLE) und eine rechte und linke Komponente vom Typ "Strukturbegriff" haben.

Irgendeine Idee, wie man das macht?

EDIT

Sorry, Sie wieder zu stören, aber ich möchte wirklich verstehen. Können Sie die Funktion "expression()" überprüfen, um mich wissen zu lassen, ob ich recht habe?

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); 
    } 
} 

Dank

Answer 1

Das kann durch die Trennung die Anwendung von anderen Ausdrücken vereinfacht werden: ist

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

APPL -> EXPR +  "application" 

Der einzige Unterschied mit Ihrem Ansatz, dass die Anwendung als eine Liste von Ausdrücken dargestellt wird, weil abcd kann implizit als (((ab)c)d) gelesen werden, so dass Sie es bei der Analyse gut als abcd speichern können.

Auf der Grundlage dieser Grammatik, ein einfacher Parser rekursiven Abstiegs kann mit einem einzigen Charakter von Look-Ahead erstellt werden:

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 

Die Wurzel Symbol APPL ist, natürlich. Als Post-Parsing-Schritt können Sie Ihre APPL = Liste von EXPR in eine Baumstruktur von Anwendungen umwandeln. Der rekursive Abstieg ist so einfach, dass Sie leicht zu einer imperativen Lösung mit einem expliziten Stack werden können, wenn Sie es wünschen.