A complete lexer for this project is included in lexer.mll (incuding rules for the extra credit). You should understand this file, but do not modify it.

Find in cfast.ml a specification of the AST for this assignment. There are already rules in parser.mly and lexer.mll for arithmetic. You must add the following rules, summarized below:

• For hints on precedence levels, look at the function prec_of_exp in cfast.ml.
• = is right-associative: a = b = c is a = (b = c)
• ; from the sequencing rule is also right-associative. This is consistent with the ; in variable binding expressions. The ;s in a for loop are used purely as delimiters and therefore do not have any associativity.
• The var_decl part of for can be zero or more comma-separated variable declarations.
• The trickiest part of the grammar is the solution to the dangling-else ambiguity introduced by if. Try to figure this out first before adding rules for the other control flow structures. An else should always bind to the closest if.
• If you do come across an if without an else, fill in the else branch of the AST node with a Cfast.Unit.
• You may have noticed that the AST node for for has no space for storing variable declarations. During parsing, you should lift any variables declared in the for loop outside the For node as Let nodes.
• As in the expressions assignment, you may not use ocamlyacc's precedence directives.

Instead of directly building X86 assembler as you did in the expressions assignment, this time you'll be generating intermediate code. The abstract instructions are defined in cfil.mli. These are mapped to X86 instructions in the file cfilerase.ml, which you may read at your leisure. All of your code generation logic belongs in controlflow.ml, where you must implement il_of_ast as defined in controlflow.mli.

We have provided some code to get you started. You don't need to use our definitions if you have a different design in mind.

To store temporary values or the values of variables in this assignment, you should use space on the stack. The module Cfil defines the type svar to represent a single 4-byte stack location. You can generate unique svars with mk_svar (). You'll have to keep track of the svars you use, as when you finally construct the proc containing your IL, you will need to specify all of the stack locations you use as an svar list.

You don't have to recycle svars after you're finished with them, but doing so will result in better code (since we aren't doing any optimization).

The let node, like OCaml's let, introduces a scoped variable binding. A variable's name bound by some let is only valid inside the expression wrapped by that let. It is not an error for one let to shadow another let's binding; that is, a program like this:

is perfectly valid (and has a return value of 6).

Note that, as in C and Java, the expression a = 3 returns the value 3 (and not unit as would a := 3 in OCaml).

Module Cfil expects you to generate program code in basic blocks. Since this can be inconvenient, we suggest that you first generate your program as a flat list of instructions. After this step, you can easily convert the list to a control flow graph. Look at the type cgext we have provided and the IL pseudo-instruction Ext for hints. Also remember that you can create fresh (that is, uniquely named to the current run of the compiler) labels using X86struct.mk_label ().

Seq evaluates its left hand side, discards the result if there is any, then evaluates its right hand side.

If evaluates its guard. If the guard is nonzero, the If evaluates and uses the result of its left branch. If the guard is zero, it evaluates and uses the result of its right branch.

Since this language does not require any static checking, it is possible to write unsafe programs. In particular, you can write a program of the form int a = ( if (0) 1 ); a Your code will not be tested for this case; you may assume that if one branch of an if returns unit, the other branch also returns unit (ditto with ints). We will investigate methods for static checking in future assignments; this is the last assignment for which you can assume well-formed input.

While evaluates its guard. If the guard is nonzero, the body of the While is executed and its result is discarded; control flow then returns to the start of the loop. If the guard is zero, then the body of the While is skipped.

For evaluates its condition (or uses 1 as the value of its condition if none was given). If the condition is nonzero, then the body of the For is evaluated and its result is discarded; For then evaluates its increment expression (or does nothing if none was given) and returns to the start of the loop. If the condition is zero, then the body of the loop (and its increment expression) are skipped.

The while and for loops do not ever return values. Seq and Let return the value of their right-hand expressions. if may return values or it may return unit (or no value). Again, assume that if one branch of the if returns a value, the other branch will do the same.

Unless you're doing the extra credit, you don't need to generate code for the Switch or the ScBinop AST nodes. For those nodes, you can simply failwith "No extra credit."

Implement some combination of switch and short-circuit evaluation. switch looks up an integer in a table of labels. If the integer is bound to a label in the table, control flow passes to that label. If nothing in the table matches, control flow passes to the default label. Switches can return values (and it is expected that every branch will consistently return or not return a value). In short-circuit evaluation, the right-hand side of a logical operator is evaluated only if necessary. If the operator is ||, the right-hand side need not be evaluated if the left-hand side is nonzero. If the operator is &&, the right-hand side need not be evaluated if the left-hand side is zero. Make sure to return the correct value!

For switch, you will need to add the following to the grammar:

There are no delimiters between switch branches: switch(4) 1 => 2 200 => 3 300 => 4 4 => 5 7 => 8 default => 4 A switch may have no branches, but must always have a default case. It is illegal for a branch to be duplicated.

No new grammar rules for short-circuit evaluation are necessary. You will need to generate code for the ScBinop node. There are no special instructions for short-circuit evaluation.

You can choose to implement switch in terms of If instructions or in terms of the Switch control-flow IL instruction. If you choose to do the latter, you will need to implement the Il.Switch case in cfilerase.ml. This will allow you to use different dispatch techniques, including jump tables (in which case you are permitted to use LInsn.Ix (X86.Insn.ExtInlineJumpTable (table_label, branch_labels)) which emits inline with the rest of your X86 code the labels in the branch_labels list).

We will also award extra credit points for interesting and clever solutions. This will be based in part on timings for benchmarks collected on ENIAC.