/ CASE STUDY
/ The Compiler
The task of a compiler is to translate a program written in a source language into a semantically equivalent program in a target language.
This task can be decomposed into subtasks
Program(-> P) Translate(P)Here, Program reads the source program and returns a structured representation (the ``abstract syntax'') in its output parameter P. This representation is then processed by Translate, which is invoked with P as an input parameter.
Consider the example MiniLAX program in Fig. 6.1.
For this program the predicate Program
will deliver a value of P as shown
in Fig. 6.2.
This will be translated by Translate into the ICode program shown in Fig. 6.3.
The abstract syntax representation of a prgram is a structured value (a ``term'') that expresses the hierarchical composition of the program. Abstract syntax ignores syntactic sugar and concrete tokens, that only serve to make the input unambiguous. It merely specifies which alternative was used for a construct and what its constituents were.
A term type is introduced by a type declaration. For example, the following declaration introduces the abstract syntax of statements:
'type' STMT assign(DESIG, EXPR, POS) read(DESIG, POS) write(EXPR, POS) call(IDENT, EXPRLIST, POS) if(EXPR, STMT, STMT, POS) while(EXPR, STMT, POS) seq(STMT, STMT)These alternatives serve as templates for values: If E is an EXPR, S an STMT, and Pos the source coordinate of the phrase, then
while (E, S, Pos)is a value of type STMT.
Concrete syntax is described by grammar rules, e.g.
'rule' Stat(-> while(E, S, Pos)) : "WHILE" Expr(-> E) @(-> Pos) "DO" StatSeq(-> S) "END"This rule parses a phrase
WHILE Expr DO StatSeq ENDE is the abstract syntax of Expr, S the abstract syntax of StatSeq, and Pos the source coordinate of Expr. From these values, the abstract syntax of the phrase is constructed:
while (E, S, Pos)Translation is described by action rules, e.g.
'rule' Statement(while(E, S, Pos)) : NewLabel(-> L1) NewLabel(-> L2) JMP(L2) LAB(L1) Statement(S) LAB(L2) Expression(E -> T) CheckBool(T, Pos) INV FJP(L1)This rule unparses the term
while (E, S, Pos)thereby emitting the target code
JMP L2 L1: Statement L2: Expression INV FJP L1where Statement is the code for S, and Expression is the code for E.
When the source program is translated into an internal representation, rules are selected by the parser according to the given source. Consider the rules
'rule' Stat(-> read(V, Pos)) : "READ" "(" Desig(-> V) @(-> Pos) ")" 'rule' Stat(-> write(E, Pos)) : "WRITE" "(" Expr(-> E) @(-> Pos) ")"If a statement has the form READ(Desig), the first rule is selected and the internal form is read(V,Pos). If a statement has the form WRITE(Expr), the second rule is selected and the internal form is write(E,Pos).
When the internal representation is processed, rules are selected according to the given term. Consider the rules
'rule' Statement(read(V, Pos)) : Designator(V -> T) CheckSimple(T, Pos) TypeCode(T -> N) REA(N) STI 'rule' Statement(write(E, Pos)) : Expression(E -> T) CheckSimple(T, Pos) TypeCode(T -> N) WRI(N)If the predicate Statement is called with the term read(V, Pos), the first rule is selected and corresponding target code for reading an item is emitted. If the predicate is called with write(E, Pos), the the second rule is selected and emits code to write an item.
The overall organization of the compiler is expressed by the root clause, which is elaborated by executing its statements. Our specification starts with the root clause: