Advanced Models and Programs F2009 ---------------------------------- sestoft@itu.dk 2009-02-11 ASSIGNMENT 3 (concrete and abstract syntax, lexing, parsing, interpretation, checking and compilation) All the subproblems below concern extensions to the simple expression language: * whose lexer and parser specification is in file Expressions.ATG * whose abstract syntax etc is in file Expressions.cs * whose abstract stack machine is in file Machine.cs There are four subproblems that should be adequately answered. In addition there is a bonus problem (3.2B) that need not be answered, but you may think about them while waiting for the metro. In each subproblem you must: * extend the CoCo/R lexer and parser specification in Expressions.ATG; * extend the interpretation methods (Eval), * extend the static checking methods (Check), * extend the compilation methods (Compile), all in file Expressions.cs; * and if necessary modify other parts of Expressions.cs. However, it should not be necessary to modify the abstract stack machine in Machine.cs. The assignment is due Wednesday 18 February 2009. Hand in your assignment to sestoft@itu.dk as one file. This may be an edited text file (or PDF generated from LaTeX document, or a Word or OpenOffice document) briefly describing the necessary changes in Danish or English, showing the code changes you have made, and stating your name and the assignment number. Or submit a zip file with the edited Expressions.ATG and Expressions.cs files including easily searchable comments that clearly indicate what changes you have made, and what subproblem is addressed by each change. GETTING STARTED Download the following files: * CoCo/R, that is, Coco.exe, Scanner.frame, Parser.frame * Expressions.ATG, the lexer and parser specification * Expressions.cs, the expression interpreter, checker and compiler * Machine.cs, the abstract stack machine * e1.txt, a file containing the expression: 2 + 3 * 4 To check that everything works out of the box, do the following: Coco -namespace Expressions Expressions.ATG csc Expressions.cs Scanner.cs Parser.cs Expressions e1.txt run Expressions e1.txt check Expressions e1.txt compile csc Machine.cs Machine a.out TROUBLESHOOTING Problem: Running Coco.exe or Expressions.exe generates an exception with a long complicated message. Diagnosis: Windows does not allow you to execute files from a network drive. Solution (quick and dirty): Copy the .exe file to the local disk (C:). Solution (proper): Go to Start => Control Panel => Administrative Tools => Microsoft .NET Framework 2.0 Configuration => Configure Code Access Security Policy => Adjust Zone Security => Make changes to this computer => Local Intranet => 3/4 trust. Problem: The prompt claims that csc is an unknown program. Diagnosis: You're using a Command Prompt instead of an SDK Command Prompt. Solution: Use Start => All Programs => .NET Framework SDK => SDK Command Prompt PROBLEM 3.1: Add the modulus operator (e1%e2) to the expression language. The operator has the same meaning as in C#. The operator should have the same precedence as multiplication (e1*e2) and integer division (e1/e2). Note that the stack machine has a MOD instruction with a suitable effect. PROBLEM 3.2: Add a logical "and" (e1&e2) operator, which evaluates e1 and e2 and whose result is true if both e1 and e2 evaluate to true, and false otherwise. This operator has lower precedence than the relational operators (==, !=, and so on). Note that when implementing Compile, you can use the stack machine's MUL instruction to implement logical AND, if you assume that false is represented by 0 and true is represented by 1. BONUS PROBLEM 3.2B, answer NOT required: Consider the logical "or" (e1|e2) operator, which evaluates e1 and e2 and whose result is false if both e1 and e2 evaluate to false, and true otherwise. The question is: Could you Compile logical "or" to code for the stack machine? That is, do the existing instructions for the stack machine suffice to implement logical "or" such that it preserves the invariant that false is represented by 0 and true is represented by 1? PROBLEM 3.3: Add simple let-expressions to the expression language. A possible syntax might be: let x = e1 in e2 end This expression should be evaluated by evaluating e1, binding the value to x, and then evaluating e2. The expression should be type checked by finding the type for e1, and then using that as the type of x when finding the type of e2; the type of e2 is the type of the entire let-expression. Hint: To implement Eval, use REnv methods AllocateLocal and PopEnv. Hint: To implement Check, use TEnv methods DeclareLocal and PopEnv. Hint: To implement Compile, use CEnv methods DeclareLocal and PopEnv; and generate SWAP and INCSP(-1) stack machine instructions to remove the let-bound variable from the stack. Make sure that complex expressions get parsed and evaluated correctly. For instance, each of these expressions should evaluate to 20: let x = 2 in let y = x+3 in y*4 end end let x = let y = 2 in y+3 end in x*4 end let x = 2 in let x = x+3 in x*4 end end let x = let x = 2 in x+3 end in x*4 end Given the previous exercises, you may check this by evaluating (if you dare): let x = 2 in let y = x+3 in y*4 end end == 20 & let x = let y = 2 in y+3 end in x*4 end == 20 & let x = 2 in let x = x+3 in x*4 end end == 20 & let x = let x = 2 in x+3 end in x*4 end == 20 Also, these let-expressions should be type-correct: let x = 2+3 in x > 7 end let x = 2==2 in x & x end whereas this one is not type-correct: let x = 2+2 in x & x end PROBLEM 3.4: Add conditional expressions in the lexer and parser specification, and define abstract syntax for them conditional expressions in Expressions.cs, for instance IfElseExpression : Expression. In this subproblem you can ignore the Eval, Check, and Compile methods; just let them throw Exception("Not implemented"). For the concrete syntax you may choose an SML-style syntax such as: if e1 then e2 else e3 end or a C/C++/Java/C#-style syntax such as: e1 ? e2 : e3 In the latter case you'll probably find parsing much easier if you always require parentheses around the expression, as in ( e1 ? e2 : e3 ) PROBLEM 3.5: Implement one or more of the Check, Eval and Compile methods for conditional expressions as in 3.4.