Left factoring grammar

0
votes

I am trying to build a recursive decent parser with backtracking. Here is my grammar:

Re -> Sq | Sq + Re
Sq -> Ba | Ba Sq
Ba -> El | Ba*
El -> lower-or-digit | (Re)

After trying a lot of things i am having problems with the production Sq−>Ba|BaSq And i end up with infinite recursion here. So a possible solution i found for this is left factoring the grammar.

My problem is that the production i wanna left factor does not seem to match any of the examples i found. How can i left factor the grammar? Or is there another teqnique that i can use?

1
parsinggrammarformal-languages
Ba | Ba Sq should not cause infinite recursion. It simply requires infinite lookahead or backtracking. You can fix that by left-factoring, but if you're okay with backtracking anyway, you don't actually need to do that. What's likely causing your infinite recursion is that your Ba rule is left-recursive. – sepp2k
For the record, left-factoring is generally trivial. For example, transform Sq->Ba|Ba Sq into Sq->Ba Sq'; Sq'->ε | Ba Sq'. Indeed, a very similar transform can be used to remove the left-recursion in Ba->El|Ba*; Ba->El Ba'; Ba'->ε | * Ba'. – rici

1 Answers

0
votes

Assuming <Sq> is a non-terminal (or the grammar won't be CFG) and <Ba> also is a non terminal :

Sq -> Ba Z

Z -> epsilon | Sq