Removing Left Recursion

MTK358 · 04-07-2011, 03:39 PM

First of all, I'm still a but confused about the standard way of removing it for left-associative operators:

http://stackoverflow.com/questions/2...left-recursion

Especially about how to construct an AST from it by executing a peice of code for every nonterminal matched. And I'm still not totally convinced that it will be left-associative, I just barely understand it.

Also, how would you remove left-recursion for something like this:

Code:

expr ::= expr "(" param_list ")"
       | other stuff...

?

Sergei Steshenko · 04-09-2011, 12:14 AM

Quote:

Originally Posted by MTK358

First of all, I'm still a but confused about the standard way of removing it for left-associative operators:

http://stackoverflow.com/questions/2...left-recursion

Especially about how to construct an AST from it by executing a peice of code for every nonterminal matched. And I'm still not totally convinced that it will be left-associative, I just barely understand it.

Also, how would you remove left-recursion for something like this:

Code:

expr ::= expr "(" param_list ")"
       | other stuff...

?

Back to the past:

Code:

no_parenthesis_expr OPTIONALLY_FOLLOWED_BY arg_list_in_parenthesis

.

MTK358 · 04-09-2011, 07:21 AM

Quote:

Originally Posted by Sergei Steshenko

Back to the past:

Code:

no_parenthesis_expr OPTIONALLY_FOLLOWED_BY arg_list_in_parenthesis

.

That kind of makes sense, but what about calling the result of a function, like this:

Code:

my_function()()

?

Sergei Steshenko · 04-09-2011, 09:31 AM

Quote:

Originally Posted by MTK358

That kind of makes sense, but what about calling the result of a function, like this:

Code:

my_function()()

?

Regarding the items in red - how about

Code:

list_of_arg_lists_in_parenthesis

?

And since the suggested construct is list, the list itself doesn't require recursion, but, of course, the list elements do.

For lists in my parser-generator engine I had a REPEATED_ITEMS construct whose members were other language items, i.e. for my engine I would write

Code:

REPEATED_ITEMS(arg_list_in_parenthesis)

.

wizard211990 · 04-09-2011, 09:42 AM

Quote:

Originally Posted by Sergei Steshenko

Regarding the items in red - how about

Code:

list_of_arg_lists_in_parenthesis

?

And since the suggested construct is list, the list itself doesn't require recursion, but, of course, the list elements do.

For lists in my parser-generator engine I had a REPEATED_ITEMS construct whose members were other language items, i.e. for my engine I would write

Code:

REPEATED_ITEMS(arg_list_in_parenthesis)

.

Yes!!!

MTK358 · 04-09-2011, 09:44 AM

Maybe it's OK, but it doesn't follow the way the language is supposed to work (any expression can be called, including but not limited to functions).

I guess you can make the list_of_arg_lists make an AST that calls the expr_without_parens and then calls the result of the previous call with the args in the next list, but it seems like there should be a better way.

---------- Post added 2011-04-09 at 10:45 ----------

Quote:

Originally Posted by wizard211990

Yes!!!

What do you mean?

Sergei Steshenko · 04-09-2011, 10:51 AM

Quote:

Originally Posted by MTK358

Maybe it's OK, but it doesn't follow the way the language is supposed to work (any expression can be called, including but not limited to functions).
...

And how does my proposed solution interfere with "the way the language is supposed to work" ?

Or, in other words, what prevents nodes in the AST from knowing who their parents are ?

MTK358 · 04-09-2011, 11:48 AM

Quote:

Originally Posted by Sergei Steshenko

And how does my proposed solution interfere with "the way the language is supposed to work" ?

Or, in other words, what prevents nodes in the AST from knowing who their parents are ?

I thought there could be a more elegant way. Anyway, is this right:

Code:

call_param_list_list ::= OPAREN call_param CPAREN {OPAREN call_param CPAREN}

call ::= no_call_expr call_param_list_list

expr ::= no_call_expr
       | call
       
no_call_expr ::= <other stuff>

MTK358 · 05-11-2011, 02:13 PM

This reply is a bit late since I figured it out a long time ago, but I thought I would say how I did it:

I used loops instead of recursion. It's much simpler, very intuitive, and infix operators can easily be made left-associative. The only disadvantage that I see is that it's impossible to describe in BNF.

Here's an example:

Code:

expr = expr2 (("+" | "-") expr2)*
expr2 = expr3 (("*" | "/") expr3)*
expr3 = expr4 ("^" expr3)?
expr4 = (NUMBER | "(" expr ")")

expr and expr2 are left-associative, and expr3 is right-associative.

And it's very nice not to depend on Lex/YACC (or any other parser-generator tool, for that matter) anymore. It's much easier to interface to, gives detailed syntax error information, and it's designed so that multiple instances of it can run at the same time in different threads if I ever need that. And of course, I got a much better understanding of parsers.