How to parse lambda term

I would like to parse a lambda calculus. I dont know how to parse the term and respect parenthesis priority. Ex:

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

I don't manage to find the good way to do this. I just can't see the adapted algorithm. A term is represented by a structure that have a type (APPLICATION, ABSTRACTION, VARIABLE) and a right and left component of type "struc term".

Any idea how to do this ?

EDIT

Sorry to disturb you again, but I really want to understand. Can you check the function "expression()" to let me know if I am right.

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

Thanks

---

The can be simplified by separating the application from other expressions:

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

APPL -> EXPR +        "application"

The only difference with your approach is that the application is represented as a list of expressions, because abcd can be implicitly read as (((ab)c)d) so you might at well store it as abcd while parsing.

Based on this grammar, a simple recursive descent parser can be created with a single character of 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

The root symbol is APPL, of course. As a post-parsing step, you can turn your APPL = list of EXPR into a tree of applications. The recursive descent is so simple that you can easily turn into an imperative solution with an explicit stack if you wish.