parsinggrammarll-grammar

My grammar isn't LL(1)? Where it's incorrect?

I have tried put my rules to https://www.cs.princeton.edu/courses/archive/spring20/cos320/LL1/ but it can't parse string

for name := num to num do begin operator ; end ;

S ::= for NAME := NUM1 T NUM2 do LIST C
NAME ::= name
NUM1 ::= num T
T ::= to NUM2
NUM2 ::= num
LIST ::= begin O
O ::= operator C D
C ::= ;
D ::= O
D ::= end C
Solution

  • The grammar is LL(1), but this tool it seems to use S internally for the start rule, and you already have it in your grammar. If you rename it to 'X' (for example) it seems to be recognized. Also you probably do not want NUM1 ::= num T as T is already available after NUM1 in rule S that should be renamed. You may also not want T ::= to NUM2 to have NUM2 as NUM2 is already in S after T.

    Based on your comment down, I will update the answer. As I have written up, the grammar is probably not what you want, here is the changed grammar:

    ST ::= for NAME := NUM1 T NUM2 do LIST
NAME ::= name
NUM1 ::= num
T ::= to
NUM2 ::= num
LIST ::= begin O
O ::= operator C D
C ::= ;
D ::= O
D ::= end C

    I have removed the T from NUM1 and NUM2 from T, because they are already expected in ST. I have also removed C from the end of ST, because the LIST has O in its end that has C D already. The original question was is the grammar LL(1), and 'yes' it is. But does the grammar recognize what you expect is another question.

    If however you need exactly your original grammar, then this input will be accepted:

    for name := num to num to num num do begin operator ; end ; ;