ラムダの構文解析方法

Question

ラムダ計算を解析したいと思います。私はその用語を解析し、括弧の優先順位を尊重する方法を知らない。例：

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

私はこれを行う良い方法を見つけることはできません。私は適応アルゴリズムを見ることができません。 用語は、タイプ（APPLICATION、ABSTRACTION、VARIABLE）およびタイプ「struc term」の右と左のコンポーネント を持つ構造で表されます。

どうすればいいですか？

EDIT

再びお邪魔して申し訳ありませんが、私は本当に理解したいです。あなたが正しいかどうか私に知らせるために関数 "式（）"を調べることができますか？

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

おかげ

Answer 1

ザ・は他の式からアプリケーションを分離することによって単純化することができます。

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

APPL -> EXPR +  "application" 

あなたのアプローチとの唯一の違いはあるため、アプリケーションが、式のリストとして表現されていることですabcdは暗黙的に(((ab)c)d)と読み替えることができます。したがって、解析中にabcdとして保存することをお勧めします。

この文法に基づいて、簡単な再帰下降パーサは先読みの単一の文字を使用して作成することができます。

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 

ルートシンボルはもちろん、APPLです。ポスト・パースのステップとして、APPL = EXPRのリストをアプリケーションのツリーにすることができます。再帰的な降下はとてもシンプルなので、望むなら簡単に明示的なスタックを使って簡単な解決策に変えることができます。