Introduction to Compilers

Keywords and phrases:source-language, object-language, syntax-directed, compiler, assembler, linker, loader, parser, scanner, top-down, bottom-up, context-free grammar, regular expressions

Introduction

A programming language provides a set of operations. Thus, for example, it is possible to speak of a Java computer or a Haskell computer. For the programmer, the programming language is the computer; the programming language defines a virtual computer. The virtual machine for Simple consists of a data area which contains the association between variables and values and the program which manipulates the data area.

Between the programmer's view of the program and the virtual machine provided by the operating system is another virtual machine. It consists of the data structures and algorithms necessary to support the execution of the program. This virtual machine is the run time system of the language. Its complexity may range in size from virtually nothing, as in the case of FORTRAN, to an extremely sophisticated system supporting memory management and inter process communication as in the case of a concurrent programming language like SR. The run time system for Simple as includes the processing unit capable of executing the code and a data area in which the values assigned to variables are accessed through an offset into the data area.

User programs constitute another class of virtual machines.

A language translator is a program which translates programs from source language into an equivalent program in an object language. The source language is usually a high-level programming language and the object language is usually the machine language of an actual computer. From the pragmatic point of view, the translator defines the semantics of the programming language, it transforms operations specified by the syntax into operations of the computational model---in this case, to some virtual machine. Context-free grammars are used in the construction of language translators. Since the translation is based on the syntax of the source language, the translation is said to be syntax-directed.

A compiler is a translator whose source language is a high-level language and whose object language is close to the machine language of an actual computer. The typical compiler consists of an analysis phase and a synthesis phase.

In contrast with compilers an interpreter is a program which simulates the execution of programs written in a source language. Interpreters may be used either at the source program level or an interpreter may be used it interpret an object code for an idealized machine. This is the case when a compiler generates code for an idealized machine whose architecture more closely resembles the source code.

There are several other types of translators that are often used in conjunction with a compiler to facilitate the execution of programs. An assembler is a translator whose source language (an assembly language) represents a one-to-one transliteration of the object machine code. Some compilers generate assembly code which is then assembled into machine code by an assembler. A loader is a translator whose source and object languages are machine language. The source language programs contain tables of data specifying points in the program which must be modified if the program is to be executed. A link editor takes collections of executable programs and links them together for actual execution. A preprocessor is a translator whose source language is an extended form of some high-level language and whose object language is the standard form of the high-level language.

The typical compiler consists of several phases each of which passes its output to the next phase

• The lexical phase (scanner) groups characters into lexical units or tokens. The input to the lexical phase is a character stream. The output is a stream of tokens. Regular expressions are used to define the tokens recognized by a scanner (or lexical analyzer). The scanner is implemented as a finite state machine.
• The parser groups tokens into syntactical units. The output of the parser is a parse tree representation of the program. Context-free grammars are used to define the program structure recognized by a parser. The parser is implemented as a push-down automata.
• The contextual analysis phase analyzes the parse tree for context-sensitive information often called the static semantics. The output of the contextual analysis phase is an annotated parse tree. Attribute grammars are used to describe the static semantics of a program.
• The optimizer applies semantics preserving transformation to the annotated parse tree to simplify the structure of the tree and to facilitate the generation of more efficient code.
• The code generator transforms the simplified annotated parse tree into object code using rules which denote the semantics of the source language.
• The peep-hole optimizer examines the object code, a few instructions at a time, and attempts to do machine dependent code improvements.

The Scanner

• Key words,
• identifiers,
• operators,
• constants: numeric, character, special, and
• comments.

Lex and Flex are tools for generating scanners is C. Flex is a faster version of Lex.

The Parser

Yacc and Bison are tools for generating bottom-up parsers in C. Bison is a faster version of Yacc. Jack is a tool for generating scanners and top-down parsers in Java.

Symbol Tables and Error Handlers

Contextual Checkers

This phase is often combined with the paser. During the parse, information concerning variables and other objects is stored in a symbol table. The information is utilized to perform the context-sensitive checking.

Intermediate Code Generator

• assembly language like or
• be an abstract syntax tree.

Code Optimizer

It may be possible to restructure the parse tree to reduce its size or to present a parse to the code generator from which the code generator is able to produce more efficient code. Some optimizations that can be applied to the parse tree are illustrated using source code rather than the parse tree.

• Constant folding

      I := 4 + J - 5;  --> I := J - 1;
     or
      I := 3; J := I + 2;  --> I := 3; J := 5

• Loop-Constant code motion

From:
       while (count < limit) do
          INPUT SALES;
          VALUE := SALES * ( MARK_UP + TAX );
          OUTPUT := VALUE;
          COUNT := COUNT + 1;
       end;  -->
to:       
       TEMP :=  MARK_UP + TAX;
       while (COUNT < LIMIT) do
          INPUT SALES;
          VALUE := SALES * TEMP;
          OUTPUT := VALUE;
          COUNT := COUNT + 1;
       end;

• Induction variable elimination Most program time is spent in the body of loops so loop optimization can result in significant performance improvement. Often the induction variable of a for loop is used only within the loop. In this case, the induction variable may be stored in a register rather than in memory. And when the induction variable of a for loop is referenced only as an array subscript, it may be initialized to the initial address of the array and incremented by only used for address calculation. In such cases, its initial value may be set

From:
       For I := 1 to 10 do
          A[I] := A[I] + E
to:
       For I := address of first element in A 
             to address of last element in A 
             increment by size of an element of A do
          A[I] := A[I] + E

• Common subexpression elimination

From:
      A := 6 * (B+C);
      D := 3 + 7 * (B+C);
      E := A * (B+C);
to:     
      TEMP := B + C;
      A    := 6 * TEMP;
      D    := 3 * 7 * TEMP; 
      E    := A * TEMP;

• Strength reduction

     2*x  --> x + x
     2*x  --> shift left x

• Mathematical identities

      a*b + a*c --> a*(b+c)
      a - b --> a + ( - b )

Code Generator

The code generator's task is to translate the intermediate representation to the native code of the target machine. The native code may be an actual executable binary, assembly code or another high-level language. Producing low-level code requires familiarity with such machine level issues such as

• data handling
• machine instruction syntax
• variable allocation
• program layout
• registers
• instruction set

As the source program is processed, it is converted to an internal form. The internal representation in the example is that of an implicit parse tree. Other internal forms may be used which resemble assembly code. The internal form is translated by the code generator into object code. Typically, the object code is a program for a virtual machine. The virtual machine chosen for Simp consists of three segments. A data segment, a code segment and an expression stack.

The data segment contains the values associated with the variables. Each variable is assigned to a location which holds the associated value. Thus, part of the activity of code generation is to associate an address with each variable. The code segment consists of a sequence of operations. Program constants are incorporated in the code segment since their values do not change. The expression stack is a stack which is used to hold intermediate values in the evaluation of expressions. The presence of the expression stack indicates that the virtual machine for Simp is a ``stack machine''.

Declaration translation

integer x,y,z.         DATA 2

Statement translation

If the code is placed in an array, then the label addresses must be back-patched into the code when they become available.

Expression translation

constant LD_INT constant

variable LD variable

e1 op e2 code for e1
code for e2
code for op

Peephole Optimizer

Figure N.1 contains a context-free grammar for a simple imperative programming language. It will be used to illustrate the concepts in this chapter.

Figure N.2: Context-free grammar for Simple

program ::= LET definitions IN command_sequence END

definitions ::= e | INTEGER id_seq IDENTIFIER .

id_seq ::= e | id_seq IDENTIFIER ,

command_sequence ::= e | command_sequence command ;

command := SKIP 
        |  READ IDENTIFIER
        |  WRITE exp
        |  IDENTIFIER := exp
        |  IF exp THEN command_sequence ELSE command_sequence FI 
        |  WHILE bool_exp DO command_sequence END 

exp ::=  exp + term | exp - term  | term
term :: term * factor | term / factor | factor 
factor ::= factor^primary  | primary 
primary ::=  NUMBER | IDENT | ( exp ) 
bool_exp ::=  exp = exp | exp < exp | exp > exp

Systematic development of a recursive descent parser

There are four steps in the systematic construction of a recursive descent parser.

1. Transform the grammar into proper form.
2. Determine the sets First[E] and Follow[N] for each right-hand side E and non-terminal N of the grammar.
3. Construct parsing procedures from the grammar.
4. Construct the parser.

Figure N.3: Grammar Transformation Rules

• Convert the grammar to EBNF
• Remove left-recursion: replace N ::= E | NF with N ::= E(F)*
• Left-factor the grammar: replace N ::= EFG | EF'G with N ::= E(F|F')G
• If N ::= E is not recursive, remove it and replace all occurrences of N in the grammar with E

The first and follow sets are used by the parser to select the applicable grammar rule. Figure N.2 summarizes the rules for computing the First and Follow sets. 

Figure N.2: First[E] and Follow[N]
 

First[e]	=	empty set
First[t]	=	{t}	t is a terminal
First[N]	=	First[E]	where N ::= E
First[E F]	=	First[E] union First[F]	if E generates lambda
	=	First[E]	otherwise
First[E|F]	=	First[E] union First[F]
First[E*]	=	First[E]
Follow[N]	=	{t}	in context Nt, t is terminal
	=	First[F]	in context NF, F is non-terminal

Figure N.3 summarizes the rules for converting the EBNF grammar to a collection of parsing procedures. 

Figure N.3: EBNF to Parsing Procedures

• For each grammar rule N::=E, construct a parsing procedure

parseN {
    parse E
}

• Refine parse E

If parse E is:	then refine to:
parse lambda	skip
parse t	accept(t) where t is a terminal
parse N	parseN where N is a non-terminal
parse E F	parse E; parse F
parse E|F	if currentToken.class in First[E] then parse E else if currentToken.class in First[F] then parse F else report a syntactic error
parse E*	while currentToken.class in First[E] do parse E

if currentToken.class in First[E] then
        parse E
else if currentToken.class in First[F] then
        parse F
else
        report a syntactic error

while currentToken.class in First[E] do
        parse E

The parser consists of:

• a global variable currentToken;
• auxiliary procedures
• scanToken obtains the next token from the scanner
• accept(tc) which obtains the next token from the scanner if the current token is of the class tc else returns a syntactic error. In some instances, the current token is known and then a simplified procedure acceptIt may be used. It obtains the next token from the scanner.
• the parsing procedures developed from the grammar;
• a driver parse that calls parseS (where S is the start symbol of the grammar) after having called the scanner to store the first input token in currentToken;

parse() {
   getChar;
   scanToken;
   parseS;
}

Systematic development of a table-driven parser

Systematic development of a scanner

There are three steps in the systematic construction of a scanner.

1. Transform the regular expressions into an EBNF grammar.
2. Transcribe each EBNF production rule N ::= E to a scanning procedure scanN, whose body is determined by E.
3. Construct the scanner.

Figure N.M: RE to EBNF

• Each regular expression RE_i defining a token class T_i is put into the EBNF form: T_i ::= RE_i.
• A regular expression Sep is constructed defining the symbols which sparate tokens.
• The EBNF production S ::= Sep*(T₀|...|T_n) is added to the grammar.

Figure N.3: EBNF to Scanning Procedures

• For each grammar rule T_i::=E_i, construct a scanning procedure scanT_i {scan E_i}.
• Refine scan E_i

scan Ei	Refinement
scan lambda	skip
scan ch	takeIt(t) where ch is a character
scan N	scanN where N is a non-terminal
scan E F	scan E; scan F
scan E|F	if currentChar in First[E] then scan E else if currentChar in First[F] then scan F else report a syntactic error
scan E*	while currentChar in First[E] do scan E

1. Objects
• currentChar contains the current character.
• currentToken contains the current token, its spelling and its class.
2. Convert the grammar to EBNF with a single production rule for each non-terminal symbol.
3. The scanner consists of the procedures developed in step (2) enhanced to record the token's class and spelling;
4. a procedure scanToken that scans 'separator*Token', and sets currentToken.spelling to the charactor string scanned and currentToken.class token.
5. the auxiliary procedures
• start sets currentToken.spelling to the empty string.
• getChar appends currentChar to currentToken.spelling and fetches the next character into currentChar.
• finish sets currentToken.class to the identified class (used for simple disjoint classes)
• screen sets currentToken.class to the identified class (used for complex classes that require additional analysis to determine class).

Attribute Grammars and Contextual Constraints

Attribute grammars are an extension of context-free grammars which permit the specification of context-sensitive properties of programming languages. Attribute grammars are actually much more powerful and are fully capable of specifying the semantics of programming languages as well.

For an example, the following partial syntax of an imperative programming language requires the declaration of variables before reference to the variables.

P ::= D B 
D ::= V... 
B ::= C ... 
C ::= V := E $|$ ...

Since there is no generally accepted notation for attribute grammars, attribute grammars will be represented as context-free grammars which permit the parameterization of non-terminals and the addition of where statements which provide further restrictions on the parameters. Figure~\ref{ag:decl} is an attribute grammar for declarations.

Figure : An attribute grammar for declarations

P ::= D(SymbolTable) B(SymbolTable)
D(SymbolTable)  ::= ...V( insert( V in SymbolTable)...
   
B(SymbolTable) ::= C(SymbolTable)... 
C(SymbolTable) ::= V := E(SymbolTable, Error(if V not in SymbolTable)
                   | ...

The parameters marked with $\downarrow$ are called inherited attributes and denote attributes which are passed down the parse tree while the parameters marked with $\uparrow$ are called synthesized attributes and denote attributes which are passed up the parse tree. Attribute grammars have considerable expressive power beyond there use to specify context sensitive portions of the syntax and may be used to specify:

• context sensitive rules
• evaluation of expressions
• translation

Historical Perspectives and Further Reading

Exercises

1. (translation) Construct a translation semantics for
1. Simple
2. HTML to TeX/LaTeX
3. TeX/LaTeX to HTML
2. Construct a scanner and a parser for expressions (use a grammar from chapter 2)
3. Construct an attribute grammar for expressions
4. Construct a calculator using the attribute grammar for expressions.
5. Construct a scanner for Simple
6. Construct a parser for Simple
7. Construct a code generator for Simple
8. Construct an interpreter for Simple
9. Construct an interpreter for BASIC.