2

我想解析一个 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);
    }
}

谢谢

4

1 回答 1

2

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

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

于 2010-12-11T20:25:18.947 回答