Search code examples
compilationcompiler-warningsformal-languages

grammar LL(1) conflicts


Hello I don't understand why there is a conflict in the assgnStmt production. I'm using coco/R and I get "LL1 warning in assgnStmt: ID is start & successor of deletable structure". Thank you.

 COMPILER program

 CHARACTERS
 Letter= 'a'..'z'.
 Digit= '0'..'9'.

 TOKENS
 NUM= Digit {Digit}.
 ID= Letter {Letter}.

 PRODUCTIONS  
 program
   = stmts
   .
  stmts = assgnStmt { assgnStmt ';' } .

  assgnStmt
     = {ID "==" }  expr
  .
  expr = term { ('+' | '-') term } .

  term = factor { ( '*' | '/'  ) factor  } .

  factor
     = '(' expr ')'
     | ID
     | NUM
     .
  END program.

Solution

  • {ID "=="} is a "deletable structure", which is a way of saying that it is optional. It can start with ID, obviously. But expr can also start with ID, and if {ID "=="} is not present, the parser must try to recognise an expr.

    LL parsers always need to know what production they are trying to recognise. But when the parser encounters an ID in this context, it cannot tell whether to expect {ID "=="} or expr.

    That is what the error message means. Fixing it is trickier, although not impossible. You could start by trying something like ID {"==" ID} rest-of-expr but that will only recognise some assignments (precisely the ones where expr does start with ID).

    (This is an example of why I don't find LL(1) parser generators very satisfactory. An LR(1) parser would have no problems with that syntax. So I don't know enough about Coco/R to provide more suggestions.)