Как разобрать лямбда-термин - PullRequest
Новая
       9

Как разобрать лямбда-термин

2 голосов
/ 11 декабря 2010

Я бы хотел разобрать лямбда-исчисление. Я не знаю, как разобрать термин и соблюсти приоритет скобок. Пример: 

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

Мне не удается найти хороший способ сделать это. Я просто не вижу адаптированный алгоритм. Термин представлен структурой, которая имеет тип (APPLICATION, ABSTRACTION, VARIABLE) и правый и левый компонент типа "член".

Есть идеи, как это сделать?

РЕДАКТИРОВАТЬ

Извините, что беспокою вас снова, но я действительно хочу понять. Можете ли вы проверить функцию «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);
    }
}

Спасибо

1 Ответ

2 голосов
/ 11 декабря 2010

Можно упростить, отделив приложение от других выражений: 

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 в дерево приложений. Рекурсивный спуск настолько прост, что вы можете легко превратиться в императивное решение с явным стеком, если хотите.

...