Как разбирать лямбда-счет

Question

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

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

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

Любая идея, как это сделать?

EDIT

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

На основе этой грамматики, простой метод рекурсивного спуска может быть создан с помощью одного символа из опережающего просмотра:

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