如何解析 lambda 项

Question

我想解析 lambda 演算。我不知道如何解析该术语并尊重括号优先级。例如：

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

我找不到好的方法来做到这一点。我只是看不到适应的算法。 术语由具有类型（应用程序、抽象、变量）的结构表示，并且 “结构术语”类型的左右组件。

知道怎么做吗？

编辑

很抱歉再次打扰您，但我真的很想理解。你能检查一下函数“表达式（）”让我知道我是否正确。

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 列表转换为应用程序树。递归下降非常简单，如果您愿意，您可以轻松地将其转变为具有显式堆栈的命令式解决方案。