LL(1) Grammar for Simple Compiler

Last Update Time-stamp: "97/06/27 19:22:22 umrigar"

The grammar is for a simple language consisting of assignment statements ID:= expr separated by ;'s. Expressions can contain parentheses, numbers and identifiers with the binary operators +, -, *, /, mod and div having the usual precedences. The grammar follows:

program
  : stmts
  ;
stmts
  : assgnStmt
  | assgnStmt ';' stmts
  ;  
assgnStmt
  : ID ':='  expr
  ;
expr
  : expr '+' term
  | expr '-' term
  | term
  ;
term
  : term '*' factor
  | term '/' factor
  | term 'div' factor
  | term 'mod' factor
  | factor
  ;
factor
  : '(' expr ')'
  | ID
  | NUM
  ;

Unfortunately, the above grammar is left-recursive and hence is not amenable to top-down parsing. If we use the standard grammar transformations to remove the left recursion, we get the following grammar:

$S: /* Rule 0 */
  program
  <EOF>
program: /* Rule 1 */
  stmts
stmts: /* Rule 2 */
  assgnStmt
  stmtsRest
stmtsRest: /* Rule 3 */
  ';'
  stmts
stmtsRest: /* Rule 4 */
  /* EMPTY */
assgnStmt: /* Rule 5 */
  ID
  ':='
  expr
expr: /* Rule 6 */
  term
  exprRest
exprRest: /* Rule 7 */
  '+'
  term
  exprRest
exprRest: /* Rule 8 */
  '-'
  term
  exprRest
exprRest: /* Rule 9 */
  /* EMPTY */
term: /* Rule 10 */
  factor
  termRest
termRest: /* Rule 11 */
  '*'
  factor
  termRest
termRest: /* Rule 12 */
  '/'
  factor
  termRest
termRest: /* Rule 13 */
  DIV
  factor
  termRest
termRest: /* Rule 14 */
  MOD
  factor
  termRest
termRest: /* Rule 15 */
  /* EMPTY */
factor: /* Rule 16 */
  '('
  expr
  ')'
factor: /* Rule 17 */
  ID
factor: /* Rule 18 */
  NUM

Feedback: Please email any feedback to zdu@acm.org.

Up to Parsing Demos Main Page