I have an indirect left recursive grammar: expr_1 := expr_1 ...

expr_1 := `not`expr | expr_2
 expr_2 := expr_3 or expr_2 | expr_3
 expr_3 := expr_4 and expr_3 | expr_4
 expr_4 := expr_1 `if` expr_1 `else` expr_5 | expr_5
 expr_5 := expr_1

I do not understand why the algorithm https://en.wikipedia.org/wiki/Left_recursion works and what ordering I should choose.

Edit: I will try the reverse ordering now.

  • $\begingroup$ I would suggest you first dry-run the algorithm on your example grammar and possibly try a few more. Then the rationale behind the algorithm would be clear. You can also find explanations in the standard textbooks as well. $\endgroup$
    – codeR
    Commented May 17 at 11:09


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.