LinuxQuestions.org

LinuxQuestions.org (/questions/)
-   Programming (https://www.linuxquestions.org/questions/programming-9/)
-   -   Removing Left Recursion (https://www.linuxquestions.org/questions/programming-9/removing-left-recursion-873649/)

MTK358 04-07-2011 03:39 PM
Removing Left Recursion
 
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 (Post 4317383)
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 (Post 4318773)
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 (Post 4319069)
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 (Post 4319156)
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 (Post 4319162)
Yes!!!
What do you mean?

Sergei Steshenko 04-09-2011 10:51 AM
Quote:
Originally Posted by MTK358 (Post 4319163)
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 (Post 4319214)
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.


All times are GMT -5. The time now is 01:04 AM.