start ::= e
e ::= e "+" e | e "*" e | e "/" e | block | "(" e ")" | e "(" e* ")"
    | e "||" e | e "<" e
    | ident | intLiteral | floatLiteral

valdef ::= fdef | "val" ident ":" type "=" e
fdef ::= "def" ident "(" typedIdList ")" ":" type "=" e

block ::= "{" valdef* e "}"

ident ::= letter (letter | diggit)*
intLiteral ::= nonZerodigit digit*
             | "0"
             | "0" "x" hexDigit+
             | "0" digit*
floatLiteral ::= intLiteral "." digit*
type ::= "int" | "float" | "(" type* ")" "=>" type

Consider a sublanguage that has only ident, intLiteral, floatLiteral. Draw automaton for ident and intLiteral and mark accepting states.

Give first and follow symbols for 'fdef' and 'block'.

Why is this grammar not LL(1)? Explain.

Rewrite grammar to encode priorities: * more than + and eliminate any reasons why grammar is not LL(1).

Give type checking rules for this language.

intLiteral is same as others. float and int are of different type, but int is implicitly converted into float when combined with another float using + or - or *.

The operator

|| 

takes two int typed expressions. If first one is not zero, the result is first result. If it is zero, the result is the second argument.

{
   def twice(f : float => float) : float => float = {
     def g(x : float) : float = {
       f(f(x))
     }
     g
   }
   def h(x : float) = (0.5 * x)
   twice(h)(8 + 2.3)
}

Apply type checking rules to expression

twice(h)(8 + 2.3)

in the environment given by the above program, assuming that 'twice' is type correct and present in the environenment.

Generate code for JVM for this expression in the case when x::int, y::int

(x < 1) || (1000 < y / x)

(see attached JVM instruction set table). You can use CafeBabe syntax as in your project.

Draw CFG for the same example.

Use the following types of nodes.

Consider running an interval analysis that maintains a mapping from integers to integers.

Run it on the previous example with the following initial values.