1.. Calculate the following (if the set is large, you may describe it rather than giving it explicitly):

(a) First(const)

(b) First(op)

(c) First(fun var arrow exp)

(d) First(var)

(e) First(value)

(f) First(let var equal exp in exp)

(g) First(if exp then exp else exp)

(h) First(app exp to exp)

2. Calculate Follow(exp).

3. Explain why the grammar above for MicrOCaml is LL(1). It happens that the grammar of MicrOCaml is unambiguous, even without parentheses.

You may have guessed that the reason for this is the odd app f to x syntax.

4. Explain, in a short paragraph, why the grammar of MicrOCaml would become ambiguous and not LL(1) if we replaced the production app exp to exp with exp exp, the equivalent construct for application in real OCaml. (Explain both why it would be ambiguous and why it would be not LL(1).

2 MicrOCaml In this section, you will build a predictive parser for a tiny subset of OCaml, appropriately called MicroCaml. The grammar of MicroCaml is shown below: var num op + (+)/(-)|(*)()|()|(=) =)|(&&)| (ID) + [a 2, A - Z][a 2, A 2,0-9]* [0-9]+ const true false num value const op fun var -> exp exp var | value | let var exp in exp | if exp then exp else exp | app exp to exp Note that the grammar above is the concrete syntax of MicrOCaml (without whites- pace and comments, both of which are allowed and ignored by the lexer): it's what you'd type to write a program. MicrOCaml supports Booleans and integers, as well as operators on them, lambdas, let-bindings, if statements and function application. There are a few imporant major differences between MicrOCaml and OCaml: application is explicit, using, for example, app f to x instead of f x. In addition, there are no infix operators: while MicrOCaml supports many of the integer and Boolean operations of OCaml (addition, subtraction, multiplication, division, less than, greater than, less-or-equal, greater-or-equal, equal, Boolean and, and Boolean or), these must be applied as functions using the (+) syntax of OCaml. We've already implemented a lexer for MicroCaml in parse.ml. The lexer turns an input into a list of tokens. The tokens used are defined in the type token at the top of parse.ml. The grammar for MicrOCaml as seen by the parser is then: op + PLUS MINUS | TIMES | DIV | LT | GT LEGE EQOP AND OR const + TRUE FALSE NUM value const op FUN VAR ARROW exp exp VAR | value | LET VAR EQUAL exp in exp | IF exp THEN erp ELSE exp | APP exp To exp Note that the nonterminal num has been replaced by token Num, which carries an integer, and the nonterminal var has been replaced by token VAR, which carries a string. The = sign in the let syntax has its own token (which is distinct from the token used for (=) as an operator, since these are two distinct language features even though they use the same concrete syntax!), as does the arrow -> in the lambda syntax. 2 MicrOCaml In this section, you will build a predictive parser for a tiny subset of OCaml, appropriately called MicroCaml. The grammar of MicroCaml is shown below: var num op + (+)/(-)|(*)()|()|(=) =)|(&&)| (ID) + [a 2, A - Z][a 2, A 2,0-9]* [0-9]+ const true false num value const op fun var -> exp exp var | value | let var exp in exp | if exp then exp else exp | app exp to exp Note that the grammar above is the concrete syntax of MicrOCaml (without whites- pace and comments, both of which are allowed and ignored by the lexer): it's what you'd type to write a program. MicrOCaml supports Booleans and integers, as well as operators on them, lambdas, let-bindings, if statements and function application. There are a few imporant major differences between MicrOCaml and OCaml: application is explicit, using, for example, app f to x instead of f x. In addition, there are no infix operators: while MicrOCaml supports many of the integer and Boolean operations of OCaml (addition, subtraction, multiplication, division, less than, greater than, less-or-equal, greater-or-equal, equal, Boolean and, and Boolean or), these must be applied as functions using the (+) syntax of OCaml. We've already implemented a lexer for MicroCaml in parse.ml. The lexer turns an input into a list of tokens. The tokens used are defined in the type token at the top of parse.ml. The grammar for MicrOCaml as seen by the parser is then: op + PLUS MINUS | TIMES | DIV | LT | GT LEGE EQOP AND OR const + TRUE FALSE NUM value const op FUN VAR ARROW exp exp VAR | value | LET VAR EQUAL exp in exp | IF exp THEN erp ELSE exp | APP exp To exp Note that the nonterminal num has been replaced by token Num, which carries an integer, and the nonterminal var has been replaced by token VAR, which carries a string. The = sign in the let syntax has its own token (which is distinct from the token used for (=) as an operator, since these are two distinct language features even though they use the same concrete syntax!), as does the arrow -> in the lambda syntax