I have three grammars:
A -> aB | b | CBB
B -> aB | ba | aBb
C -> aaA | b | caB
I need to "determine whether [they] are LL grammars by performing the pairwise disjoint test, showing the first sets of each RHS of each nonterminal.
This is what I have so far...
A -> aB | b | CBB
first(aB) = a
first(b) = b
first(CBB) = aaA = a
This is the one I'm having trouble with. Did I do CBB correctly? If so I would say that they intersect & the rule fails the test. (right?)
B -> aB | ba | aBb
first(aB) = a
first(ba) = b
first(aBb) = a
They are intersected & thus the rule fails the test.
C -> aaA | b | caB
first(aaA) = a
first(b) = b
first(caB) = c
They are not intersected & thus the rule passes
The point of the test is to see if, looking at the first terminal, you can tell which rule to use (a requirement for LL). Its pretty obvious for B that there are 2 rules that could apply for the terminal a; its also pretty obvious the each rule for C starts with a different terminal. And you can see that the possible first terminals for C (and hence CBB) overlaps for the other rules for A.
Bottom line: looks good (although, if you had stopped at a single terminal for CBB and happened to choose c, you would have come to the wrong conclusion).
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With