2

ラムダ計算を解析したいと思います。用語を解析し、括弧の優先順位を尊重する方法がわかりません。元： 

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

これを行う良い方法を見つけることができません。適応されたアルゴリズムが見えません。タームは、タイプ (APPLICATION、ABSTRACTION、VARIABLE) とタイプ「struc term」の右コンポーネントと左コンポーネントを持つ構造体によって表されます。

これを行う方法はありますか？

編集

何度もお邪魔して申し訳ありませんが、本当に理解したいです。関数「expression()」をチェックして、私が正しいかどうかを教えてもらえますか。 

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

ありがとう

4

1 に答える 1

2

は、アプリケーションを他の式から分離することで簡素化できます。

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

APPL -> EXPR +        "application"

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

この文法に基づいて、単純な再帰降下パーサーを先読みの 1 文字で作成できます。

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 のリストをアプリケーションのツリーに変えることができます。再帰的降下は非常に単純であるため、必要に応じて明示的なスタックを使用して簡単に命令型ソリューションに変えることができます。

于 2010-12-11T20:25:18.947 に答える