Grammar refactoring for LL parsing
Question
In a simple example, I'm confused about how to turn this grammar into a LL one by removing the left recursion. Any hints are welcome.
G = {
A -> A a | A B | a
B -> b
}
I get the following by applying this algorithm:
G = {
A -> a X
X -> e | A | B X
B -> b
}
This seem to work to generate a C pseudo-code for the parser:
void A() {
switch (token) {
case 'a' : next(); X(); break;
}
}
void X() {
switch (token) {
case 'e' : finish(); break;
case 'a' : A(); break;
case 'b' : B(); X(); break;
}
}
void B() {
next();
}
And to generate a parsing tree for the word: aabab
:
A ---+
| |
a X
|
A ---+
| |
a X ---+
| |
B X
| |
b A ---+
| |
a X ---+
| |
B X
| |
b e
Well, I'm just not sure if it's right...
Solution
First, your grammar seems to accept sequences of a
s separated by single b
s, so that no 2 b
come together. (aaa...abaaaaa...abaaa...a
) This should be equivalent to something like:
Q -> P | P b P
P -> a | a P
Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow