Homework 1

Please use the VCL image "Linux Lab Machine (Realm RHEnterprise 6)" to solve the programming exercises. (You may use your own laptop or any other environment but you will be graded against this VCL image.)

1. (5 points) Extend the simple calculator on the last slide of lec1.ppt to support both multiplication/division and addition/subtraction, yet on decimal numbers in "dot" notation an arbitrary leading/trailing number of digits such as 2., .2, 0.2, 2.0, 2 etc.

   Turn in files calc.l and calc.y.

2. (10 points) Construct a DFA for the scanner of the last excercise by hand and turn in its graphics representation as a PDF. Then code it up manually translating the state machine one-to-one into C code with gotos. Make it compatible with the parser (calc.y) from the previous exercise, and test it out.

   Turn in files scan.c and scan.pdf.

---

Generate a scanner and parser for the parpseudo language below. Of course, once you generate a compiler, it is no longer a pseudo language, strictly speaking :-) Consider the following notation for pseudo code:

Program	Block
Block	VAR Declarations BEGIN ... END
Test	IF Comparison THEN ... ELSE ... ENDIF
	IF Comparison THEN ... ENDIF
Loop	WHILE Comparison DO ... ENDWHILE
	REPEAT ... UNTIL Comparison ENDREPEAT
	FOR Variable := Expression TO Expression DO ... ENDFOR
	PARFOR Variable := Expression TO Expression PRIVATE Variables REDUCE ReduceOp Variables DO ... ENDPARFOR
Procedure	PROC Procname ( Parameters ) Block ENDPROC
	PARPROC Procname ( Parameters ) Block ENDPARPROC
Parameter	Passby Variable : Type
Passby	IN | OUT | INOUT
Input	READ(Variable)
Output	WRITE(Variable)
Declaration	Variable : Type
Type	INT | REAL | INT[Expression] | REAL[Expression]
Assignment	Variable := Expression
	Variable[Expression] := Expression
Expression	Variable
	Variable[Expression]
	IntegerNumber
	RealNumber
	Expression ArithmeticOp Expression
	INT ( Expression )
	Sign Expression
LogicOp	AND OR
ComparisonOp	= <> > < >= <=
Comparison	Expression ComparisonOp Expression
	Comparison LogicOp Comparison
	NOT Comparison

Notice:
• Variables are declared and strictly typed. Variable names start with a letter followed by letters of digits.
• Precedence between arithmetic and logic operators are as in any other languages (and as assumed by math), e.g., NOT has high precedence than AND has higher precedence than OR. DIV and MOD are used for modulo division of integers with dividend and remainder as results, respectively, while / is used for division of real numbers.
• Spaces, tabs and new line characters are ignored.
• Every assignment, block, loop, procedure and I/O statement is terminated by a semicolon.
• Variable declarations and parameter lists are separated by commas.
• All numbers may be handled as "double" precision internally (although they may originally be entered as integers). This does require conversions around certain operations (e.g., DIV and MOD).
• Coersion is supported via implicit type casting to a more general type, namely REAL . Explicit casting via INT() is required to a more specific type.
• Procedures (but not parallel procedures) may be called recursively.
• Parameter passing for procudures is by copy in/out/inout (where copy in is equivalent to by value) or reference (for scalars and arrays).
• Nested scope variables override access to previous (outer) declarations by the same name.
• Parallel procedures may only have in/out/inout parameters and cannot access variables outside its own scope. Any subset of the parallel loops inside parallel procedures may be parallelized.
• Parallel loops may be parallelized. If so, privatized variables are allocated per thread (with undefined initial values) and reductions are performed across all threads (on a privatized copy, which is eventually copied out to the non-privatized variable by the same name in the next outer scope.)

To make your life easier, here is the grammar of the pseudo language in EBNF notation (Notice that [ X ] means X is optional, but '[' and ']' refer to the open/close bracket symbols.):

Program ::= Block
Block ::= [ Declarations ] BEGIN { Statement } END
Declarations ::= VAR { Varlist : Type ; }
Varlist ::= Variable { , Variable }
Type ::= BasicType | ArrayType
ArrayType ::= BasicType '[' Expression ']'
BasicType ::= INT | REAL
Statement ::= Assignment ; | Block ; | Test ; | Loop ; | Input ; | Output ; | Procedure ; | ProcCall ;
Assignment ::= Variable := Expression | Variable'['Expression']' := Expression ;
Expression ::= Variable | Variable'['Expression']' | [ Sign ] IntegerNumber | 
               [ Sign ] RealNumber | Expression ArithmeticOp  Expression | INT '(' Expression ')' | Sign Expression
ArithmeticOp ::= + | - | * | / | DIV | MOD
LogicOp ::= AND | OR
ComparisonOp ::= = | <> | < | > | <= | >=
Comparison ::= Expression ComparisonOp Expression |
               Comparison LogicOp Comparison | NOT Comparison
Test ::= IF Comparison THEN { Statement } [ ELSE { Statement } ] ENDIF
Loop ::= WHILE Comparison DO { Statement } ENDWHILE |
         REPEAT { Statement } UNTIL Comparison ENDREPEAT |
         FOR Variable := Expression TO Expression DO { Statement } ENDFOR
         PARFOR Variable := Expression TO Expression ParMod DO { Statement } ENDPARFOR
ParMod ::= [ PRIVATE Varlist ] { REDUCE ReduceOp Varlist }
ReduceOp ::= + | - | MIN | MAX
Input ::= READ '(' Variable ')'
Output ::= WRITE '(' Expression ')'
Procedure ::= PROC Procname '(' [ Parameters ] ')' Block ENDPROC |
              PARPROC Procname '(' [ Parameters ] ')' Block ENDPARPROC
Parameters ::=  Parameter { , Parameter }
Parameter ::= Passby Variable : Type
Passby ::= IN | OUT | INOUT | REF
ProcCall ::= Variable '(' Arguments ')'
Arguments ::= Expression { , Expression }

3. (30 points) Specify the lexical analysis starting with pseudo.l (incomplete) and a Makefile so that you can use flex to generate a scanner. This includes recognition of operators, key words, numbers (int and real, e.g., 123 and 12.3 but no exponent notation), identifiers and handling of white space. The scanner should generate exactly those tokens (declared as constants in the parser specification, see below) given by the syntax above. Allow for a reference to the line number (later used by the parser). Identifiers and numbers should be provided in yylval as str_ptr / int_val / double_val.
4. (55 points) Specify the syntax analysis starting with pseudo.y (incomplete) so that you can use bison to generate a parser. This includes declaration of all tokens (with type information for identifiers and numbers), associativity and precedence of operators, grammar rules as indicated by the EBNF above (only minor changes are necessary for the transformation to rules) as well as syntax errors indicated with a line number and the affected token.
Files for testing: error.psd and ok.psd.

Turn in files pseudo.l and pseudo.y.

Hints:

• Lex/Yacc Tutorial

Other useful references:

• EOS guide - information and tutorials for new students: how to use the eos/unity systems etc.
• Gdb reference card
• Gnu manuals (make, gdb and many more)