You are to implement a syntax analyzer for the programming language Toy, as defined in project #1. You should first design a CFG G for Toy based on the following Backus Normal Form (BNF) description, and then write a program to (1) create a parsing table for G, and (2) perform a one- symbol lookahead parsing on various input Toy programs and print appropriate parsing actions.

The grammar of Toy is given in a variant of extended BNF. The meta-notation used:

x means that x is a terminal i.e. a token. All terminal names are lowercase. X (in italic) means X is a nonterminal. All nonterminal names are capitalized.

means zero or one occurrence of x, i.e., x is optional x* means zero or more occurrences of x x+ means one or more occurrences of x x+, a comma-separated list of one or more xs (commas appear only between xs)

| separates production alternatives

For readability, we represent operators by the lexeme that denotes them, such as + or != as opposed to the token (_plus, _notequal) returned by the scanner.

1. Program ::= Decl+ 2. Decl ::= VariableDecl | FunctionDecl | ClassDecl | InterfaceDecl 3. VariableDecl ::= Variable ; 4. Variable ::= Type id 5. Type ::= int | double | boolean | string | Type [] | id 6. FunctionDecl ::= Type id ( Formals ) StmtBlock | void id ( Formals ) StmtBlock Formals ::= Variable+, | 7. Formals ::= Variable+, |

8. ClassDecl ::= class id < implements id+, > { Field* } 9. Field ::= VariableDecl | FunctionDecl

10. InterfaceDecl ::= interface id { Prototype* }

11. Prototype ::= Type id ( Formals ) ; | void id ( Formals ) ;

12. StmtBlock ::= { VariableDecl* Stmt* }

13. Stmt ::= <Expr> ; | IfStmt | WhileStmt | ForStmt | BreakStmt | ReturnStmt | PrintStmt | StmtBlock

14. IfStmt ::= if ( Expr ) Stmt Stmt>

15. WhileStmt ::= while ( Expr ) Stmt

16. ForStmt ::= for ( <Expr> ; Expr ; <Expr> ) Stmt

17. BreakStmt ::= break ;

18. ReturnStmt ::= return <Expr> ;

19. PrintStmt ::= println ( Expr+, ) ;

20.

Expr ::= Lvalue = Expr | Constant | Lvalue | Call | ( Expr ) |

Expr + Expr | Expr Expr | Expr * Expr | Expr / Expr | Expr % Expr | - Expr |Expr < Expr | Expr <= Expr | Expr > Expr | Expr >= Expr | Expr == Expr | Expr != Expr | Expr && Expr | Expr || Expr | ! Expr readln () | new ( id ) | newarray ( intconstant , Type )

21. Lvalue ::= id | Lvalue [ Expr ] | Lvalue . id

22. Call ::= id ( Actuals ) | id . id ( Actuals )

23. Actuals ::= Expr+, |

24. Constant ::= intconstant | doubleconstant | stringconstant | booleanconstant | null

Operator precedence from highest to lowest:

[ . (array indexing and field selection) ! - (logical not, unary minus) * / % (multiply, divide, mod) + - (addition, subtraction) < <= > >= (relational)

== != (equality) && (logical and) || (logical or) = (assignment)

All binary arithmetic and logical operators are left-associative.

The assignment and relational operators are not associate, which means we cannot chain a

sequence of operators that are on the same precedence level. For example, a < b >= c should not

parse, but a < b == c is allowed.

Parentheses may override precedence and associativity.

For every input Toy program, you should print out a sequence of tokens generated by your first project (the lexical analyzer), and print out the action (either "shift" or "reduce") decided by your parser for each token. If the action is "reduce", also print out the production number. For instance, given the following CFG:

S->a X c

X -> b X

X->b

X -> Y d

Y -> Y d

Y-> d

The sample output for string abbbc should be

a [shift] b [shift] b [shift] b [shift] c [reduce 3][reduce 2][reduce 2][shift]

[reduce 1]

[accept]

and the output for abcd should be

a [shift] b [shift] c [reduce 3][shift]

d [reduce 1]

[reject]