CE305 Languages and Compilers

You should start on building the Expression Analyser for Assignment One. You may wish to refamiliarise yourself with the second CE204 assignment and the initial program code you were given in CE204 and as well as your submitted solution. You should also have a go at running the gForth interpreter, which is the target of both the expression analyser and the compiler project. (The CE305 notes on the gForth interpreter contain some simple exercises to try).

Things to try:

1. Write the regular expressions for tokens of (i) integer arithmetic and (ii) floating point arithmetic, assuming the Forth representation of floating point numbers.
2. Write context free grammar rules for (i) conventional (infix) integer arithmetic, and (ii) postfix integer arithmetic.
3. Adapt the program for CE204, or write/adapt your own program, to accept an integer expression (infix) and then print out the string of tokens.
4. Have a go at adapting the program to accept infix floating point expressions, printing out the string of tokens.
5. What happens if you enter an expression that uses inappropriate tokens? Try to adapt or extend the program so that sensible error messages are produced.

Note the potential ambiquity for some tokens, such as - and +. Both of these can occur as binary operators (23+32, 32-23), and as (unary) signs, where they are normally considered to be part of the number (e.g. -23 and +32). They may also prefix an expression (as in -(2+3), which could be intepreted as an abbreviation of 0-(2+3)).

There are further ambiguities to consider with floating point numbers. Compare 1e1 + -23e-32 with 1e1 + -23e -32, and with 1e1 + - 23e-32, for example. Note that some of these are syntactically or semantically ill-formed, but it is not up to the tokeniser to deal with such matters.

Note: You may wish to try to simplify the development of your assignment using a "compiler-compiler" tool, such as ANTLR. Now might be a good time to start investigating such tools.

1. You can continue the work on tokenisation, but also consider the question of how you will build your parser.
2. The first step is to specify a grammar, which you may already have done.
3. Note that you can build your parser even if you have not got your tokeniser working. You just have to test your program with manually generated token streams.
4. If you are using tools, such as ANTLR or COCO/R, then you should work through the tutorials on writing a grammar, and invoking the tools to build the parser.
5. If you are building on the CE204 code you need to think how you might adapt and extend this so that you can show your token stream, visualise the parse tree, deal with floating point expressions, and give meaningful error messages.
6. If you are writing the parser from scratch, then you should consider using shift-reduce parsing.
   • This requires you to implement a shift operator, that can push a token on to the stack, and a reduce operation, which checks whether the symbols at the top of the stack match the RHS of a grammar rule, and if so, replaces those items with the LHS of the matching rule. You also need to implement an operation to initialise the parser, and a function or method that can identify that a string of tokens has been accepted.
   • Ideally the primitive operations should be implemented in a way that "encapsulates" the underlying data-structures, so that you can change how you store and access the stack, rules, and (ultimately) parse tree without having to rewrite other parts of the program. This allows you to refine your data-structures at a later date, in the event that you start off with something relatively naive.
   • Calculating tables for LR(k) parsers by hand is error prone. A simpler solution is to implement shift-reduce parsing more directly.
   • There are ways of encoding the grammar rules which make it easy to match "handles" on the stack with the RHS of the rules. One option is to think about the rules in reverse, so conceptually x –> a b c is thought of as (< c, b, a >, x). If you have a c at the top of the stack, then you start matching subsequent items on the stack against the remaining items in what was the RHS of the rule, in the given order.
   • You can start off building a recogniser. Once that is working you can turn it into a parser that constructs the syntax tree.

Continue work on the first assignment.

1. You will be expected to demonstrate your program that implements the expression analyser for Assignment One.
2. You should start work on the Small Compiler for the second assignment. You might want to experiment with variables, conditionals and loops in Forth, as discussed in the previous lecture.

You should continue work on the Small Compiler for the second assignment. You might want to experiment with variables, conditionals and loops in Forth, as discussed in the lectures for week 21.

Note that gForth requires that control statements only occur within "compiled" Forth, which means they must occur within the context of a definition.

   <Forth global variable declarations go here>
   : program
   <Body of Forth program code goes here>
   ;
   program 

If you are stuck, try to make sure your tokeniser and parser are working with assignment statements. If you cannot get declarations working, then you can test your programs by declaring some default variables automatically in the compiler's output, as shown below.

   variable a
   variable b
   variable c
   : program
   <output of compiler goes here>
   ;
   program 

Once these are working, you can start on if-then conditionals. While-loops should then be fairly easy. If you are stuck on if-then-else then look at the notes on the "dangling else" problem. Then you can go back and sort out variable declaration and "type-checking".