c - 如何解析 lambda 术语

Question

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

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

谢谢

Answer 1

可以通过将应用程序与其他表达式分开来简化:

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

APPL -> EXPR +        "application"

您的方法的唯一区别是应用程序表示为表达式列表，因为 abcd 可以隐式读取为 (((ab)c)d) 所以你最好在解析时将它存储为 abcd。

基于这个语法，可以创建一个简单的递归下降解析器，其中包含一个 lookahead 的单个字符:

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