0

I wonder if this production is left recursive: "expr -> {print('+')} expr + term". So that if it's left recursive I need to eliminate the left recursion so that it want get stuck in a loop. I'm not sure here because of the statement: "{ print ('+') }" came before: "expr".

FortMax
  • 33
  • 11
  • The left-most term of the rule is a terminal, it can't be left-recursive. – Mephy Jul 07 '15 at 13:52
  • If `{..}` here has the conventional meaning of zero or more repetitions then I think I disagree with the two other posters: the production is left-recursive because `expr` can be reached from itself with no tokens consumed in between. – 500 - Internal Server Error Jul 07 '15 at 15:44
  • 1
    Care to reveal which parser-generator you are using? The syntax shown in your question is confusing without this context. – rici Jul 07 '15 at 16:23
  • If I knew which parser generator you were using, I might try an actual answer. However, if `{print ('+')}` is supposed to be a mid-rule action, practically no parser generator will work with that rule, not because of left-recursion, but because it would require a crystal ball to know that the reduction is appropriate. (You could use a parser generator with deferred actions, but I think that you don't actually want to defer that action, unless you also defer all the other actions.) – rici Jul 07 '15 at 19:26
  • I'm using a parser to transform an expression from infix notation to prefix notation. – FortMax Jul 08 '15 at 00:37
  • @FortMax: I got that out of another comment you made. But I still don't know how you are creating that parser, or where your notation comes from. – rici Jul 08 '15 at 05:06

2 Answers2

0

No it is not left recursive, as the leftmost thing being derived is not the nonterminal on the left hand side of the production. An example of left recursion would be:

expr -> expr '+' term

as the first thing being derived is the thing being defined. This can be problematic for certain parsing algorithms (See this question for details: Why can't a recursive-descent parser handle left recursion) as it can cause infinite loops. If you do encounter left recursion, and want to eliminate it, you can get rid of it by left factoring your grammar. More details about left factoring can be found here (or by googling "left factor grammar")

Community
  • 1
  • 1
Matt
  • 4,029
  • 3
  • 20
  • 37
0

I'm assuming here that the meaning of {print('+')} is "output '+' to the screen when this production is entered".¹

In that case it is irrelevant for the purpose of identifying left recursion as the relevant question to find left-recursion isn't "Does any code execute before the recursion?", but "Are any tokens consumed before the recursion?". Since executing embedded code does not consume any tokens, the answer to this question is "no" and thus there is indeed left recursion.

¹ I'm assuming this because {...} is a common syntax for embedding code in parser generators (in fact it's the only syntax I've ever seen), print('x') does indeed look like it might be code meant to be embedded, and if print('x') were meant as a sequence of terminals, it would have more likely been written as 'print' '(' 'x' ')' (because why would you put quotes around the x and nothing else?).

sepp2k
  • 363,768
  • 54
  • 674
  • 675
  • Yes, your assumption is right. The cause of this print statement is to produce a prefix notation of the input, like this: 5+2 -> +52. – FortMax Jul 07 '15 at 17:49