2

Given a grammar G defined by

A -> Ca
B -> Cb
C -> e|f

Is this grammar LL(1)?

I realize that we could compress this down into a single line, but that's not the point of this question.

Mainly, can an LL(1) grammar have multiple rules that begin with the same non-terminal?

As a follow up question, how do I construct a parse table for the above grammar?

I've worked out the following:

FIRST(A) = {e,f}
FIRST(B) = {e,f}
FIRST(C) = {a,b}

FOLLOW(A) = {}
FOLLOW(B) = {}
FOLLOW(C) = {a,b}

I looked at this post, but didn't understand how they went from the FIRSTs and FOLLOWs to a table.

Community
  • 1
  • 1

2 Answers2

2

The grammar you've given is not LL(1) because there is a FIRST/FIRST conflict between the two productions A → Ca and A → Cb.

In general, grammars with multiple productions for the same nonterminal that begin with the same nonterminal will not be LL(1) because you will get a FIRST/FIRST conflict. There are grammars with this property that are LL(1), though they're essentially degenerate cases. Consider, for example, the following grammar:

A → Ea

A → Eb

E → ε

Here, the nonterminal E only expands out to the empty string ε and therefore, in effect, isn't really there. Therefore, the above grammar is LL(1) because there are no FIRST/FIRST conflicts between the two productions. To see this, here's the parse table:

     a  b  $
A    Ea Eb -
E    ε  ε  -

Hope this helps!

Community
  • 1
  • 1
templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
  • Can you add some details about how to go from FIRST/FOLLOW sets to a parse table? –  Feb 12 '14 at 02:04
  • Wait, so we always know which rule to use in the parse table because this is LL(1)? I think I understand the use of FIRST sets in the table. I'm still uncertain about the roles of the FOLLOW ones. –  Feb 12 '14 at 02:15
  • @al92 Yes, the grammar is LL(1) because the table is unambiguous. We use FIRST sets exclusively in the A row to determine which productions to use when reading an `a` or `b`, and we use FOLLOW sets exclusively in the E row. Think of it this way - at some point, we need to expand out E to ε. If the current nonterminal is an E and we read an a or b, we know that the a or b really belong to another production and that the current E is getting in the way, so we should apply the production E -> ε to get the E out of the way. This happens because FOLLOW(E) = {a, b}. – templatetypedef Feb 12 '14 at 03:10
  • Note that the language is LL(1), because there are LL(1) grammars for it (in fact, the language is regular `[ab][ef]`). – Apalala Feb 12 '14 at 10:55
1

I am solve your question in 2 case:

First case if the terminal is {a,b,e,f} enter image description here

Second case if the terminal is {a,b,f} and e is epsilon

enter image description here

so no multipe entry this is LL(1).

For more information: look at this explanation and example below:

enter image description here

enter image description here

Best regards

YouZerSef
  • 26
  • 4