A Simple Syntax-Directed Translator

2.1 Introduction

• This chapter is an introduction to the compiling technique translating representative programming language statements into three-address code, an intermediate representation.
  

• The analysis phase of a compiler breaks up a source program into constituent pieces and produces an internal representation for it, called intermediate code, Analysis is organized around the

  • Syntax: The proper form of programs
  • semantics: what programs mean

• A lexical analyzer allows a translator to handle multicharacter constructs like identifiers, which are written as sequences of characters, but are treated as units called tokens during syntax analysis

• Two forms of intermediate code: abstract syntax trees (simply syntax tree) and three-address code (x=y op z)
  

2.2 Syntax Definition

• A grammar naturally describes the hierarchical structure of most programming language constructs. For example, an if-else statement in Java can have the form
  if ( expression ) statement else statement
• Using the variable expr to denote an expression and the variable stmt to denote a statement, this structuring rule can be
  expressed as
  stmt -> if ( expr ) stmt else stmt
  • '->' means 'has a form of'
  • such a rule is called a production

2.2.1 Definition of Grammars

• A context-free grammar has four components:
  1. A set of terminal symbols, sometimes referred to as “tokens.”
  2. A set of nonterminals, sometimes called “ syntactic variables.”
  3. A set of productions consists of a nonterminal, called the head or left side of the production, an arrow, and a sequence of terminals and/or nonterminals, called the body or right side of the production
  4. A designation of one of the nonterminals as the start symbol

2.2.2 Derivations

• A grammar derives strings by beginning with the start symbol and repeatedly replacing a non-terminal by the body of a production for that non-terminal. The terminal strings that can be derived from the start symbol form the language defined by the grammar.
• The terminal strings that can be derived from the start symbol form the language defined by the grammar
• Parsing is the problem of taking a string of terminals and figuring out how to derive it from the start symbol of the grammar, and if it cannot be derived from the start symbol of the grammar, then reporting syntax errors within the string

2.2.3 Parse Trees

• A parse tree pictorially shows how the start symbol of a grammar derives a string in the language
• From left to right, the leaves of a parse tree form the yield of the tree, which is the string generated or derived from the nonterminal at the root of the parse tree
• The language generated by a grammar is as the set of strings that can be generated by some parse tree
• Formally, given a context-free grammar, a parse tree according to the gram- mar is a tree with the following properties:
  1. The root is labeled by the start symbol.
  2. Each leaf is labeled by a terminal or by e.
  3. Each interior node is labeled by a nonterminal.
  4. 4. If A is the nonterminal labeling some interior node and
        $X_I,X_z,...,X_n$ are the labels of the children of that node from left to right, then there must be a production
        $A\to X_1{X}_2..X_n$. Here,
        $X_1,X_2,...,X_n$, each stand for a symbol that is either a terminal or a nonterminal. As a special case, if
        $A\to ϵ$ is a production, then a node labeled A may have a single child labeled
        $ϵ$.

example

• $9-5+2$

1. list
   $\to$ list + digit
2. list
   $\to$ list - digit
3. list
   $\to$ digit
4. digit
   $\to$ 0|1|2|3|4|6|6|7|8|9

• a) 9 is a list by production (3), since 9 is a digit.
• b) 9-5 is a list by production (2), since 9 is a list and 5 is a digit.
• c) 9-5+2 is a list by production (1), since 9-5 is a list and 2 is a digit

2.2.4 Ambiguity

• An ambiguous grammar can have more than one parse tree generating a given string or terminals. e.g.

2.2.5 Associativity of Operators

• The four arithmetic operators, addition, subtraction, multiplication, and division are left-associative (e.g. 9-5-2)
• exponentiation, the assignment operator = in C and its descendants are right associative (e.g. a=b=c)

example

• Parse tree for left- and rightassociative grammars

2.2.6 Precedence of Operators

• 先乘除後加減
• expr → expr + term I expr - term I term
• term → term * factor I term / factor I factor
• factor → digit I (expr)

2.3 Syntax-Directed Translation

• Attributes: An attribute is any quantity associated with a programming construct.
• (Syntax-directed) translation schemes: A translation scheme is a notation for attaching program fragments to the productions of a grammar.

2.3.1 Post-fix Notation

• The postfix notation for an expression E can be defined inductively as follows:
  1. If E is a variable or constant, then the postfix notation for E is E itself.
  2. If E is an expression of the form
     $E_1$ op
     $E_2$, where op is any binary operator, then the postfix notation for E is
     $E_1^{\prime }{E}_2^{\prime }$ op, where
     $E_1^{\prime }$ and
     $E_2^{\prime }$ are the postfix notations for
     $E_1$ and
     $E_2$, respectively.
  3. If E is a parenthesized expression of the form (
     $E_1$), then the postfix notation for E is the same as the postfix notation for
     $E_1$.
• examples
  • (9-5)+2 is 95-2+
  • 9-(5+2) is 952±
  • 952±3→97-3 →23* →6

2.3.2 Synthesized Attributes

• A syntax-directed definition associates
  • With each grammar symbol, a set of attributes, and
  • With each production, a set of semantic rules for computing the values of the attributes associated with the symbols appearing in the production
• An attribute is said to be synthesized if its value at a parse-tree node N is determined from attribute values at the children of N and at N itself
• Synthesized attributes have the desirable property that they can be evaluated during a single bottom-up traversal of a parse tree

2.3.3 Simple Syntax-Directed Definitions

• The string representing the translation of the nonterminal at the head of each production is the concatenation of the translations of the nonterminals in the production body, in the same order as in the production, with some optional additional strings interleaved
• A syntax-directed definition with this property is termed simple

2.3.4 Tree Traversals

• Tree traversals will be used for describing attribute evaluation and for specifying the execution of code fragments in a translation scheme
• A traversal of a tree starts at the root and visits each node of the tree in some order
• A depth-first traversal starts at the root and recursively visits the children of each node in any order
• Synthesized attributes can be evaluated during any bottom-up traversal, that is, a traversal that evaluates attributes at a node after having evaluated attributes at its children

2.3.5 Translation Schemes

• A syntax-directed translation scheme is a notation for specifying a translation by attaching program fragments to productions in a grammar
• A translation scheme is like a syntax-directed definition, except that the order of evaluation of the semantic rules explicitly specified
• Program fragments embedded within production bodies are called semantic actions
• 
  

2.4 Parsing

• Parsing is the process of determining how a string of terminals can be generated by a grammar
• Recursive descent can be used both to parse and implement syntax-directed translators
• Programming–language parsers almost always make a single left-to-right scan over the input, looking ahead one terminal at a time, and constructing pieces of the parse tree as they go * Most parsing methods fall into one of two classes, called the top-down and bottom-up methods
• In top-down parsers, construction starts at the root and proceeds towards the leaves, while in bottom-up parsers, construction starts at the leaves and proceeds towards the root

2.4.1 Top-Down Parsing

• The top down construction of a parse tree:
  • At node N, labeled with nonterminal A, select one of the productions for A and construct children at N for the symbols in the production body
  • Find the next node at which a subtree is to be constructed, typically the leftmost unexpanded nonterminal of the tree
• The current terminal being scanned in the input frequently referred to as the lookahead symbol
• When the node being considered in the parse tree is for a terminal, and the terminal matches the lookahead symbol, then we advance in both the parse tree and the input
• A production is unsuitable if, after using the production, we cannot complete the tree to match the input string

2.4.2 Predictive Parsing

• Predictive Parsing: the lookahead symbol unambiguously determines the flow of control through the procedure body for each nonterminal * The sequence of procedure calls during the analysis of an input string implicitly defines a parse tree for the input, and can be used to build an explicit parse tree, if desired
• Predictive parsing relies on information about the first symbols that can be generated by a production body
• 

2.4.3 When to Use

$ϵ$-Productions

• Our predictive parser uses an ε-production as a default when no other production can be used

2.4.4 Designing a Predictive Parser

• A predictive parser is a program consisting of a procedure for every nonterminal
  • It decide which A-production to use by examining the lookahead symbol
  • The procedure mimics the body of the chosen production

2.4.5 Left Recursion

• It is possible for a recursive-descent parser to loop forever
• A problem arises with “left-recursive” productions like expr →expr+term
• A left-recursive production can be eliminated by rewriting the offending production
• A→Aα|β the nonterminal A and its production are said to be left recursive
• Rewriting the productions for A using a new nonterminal
  • R: A→βR
  • R→αR|ε
• 

2.4.6 Exercises for Section 2.4 (important)

• Exercise 2.4.1 : Construct recursive-descent parsers, starting with the following grammars:
• 
• 
• 

2.5 A Translator for Simple Expressions

2.5.1 Abstract and Concrete Syntax

• In an abstract syntax tree for an expression, each interior node represents an operator; the children of the node represent the operands of the operator
• In the syntax tree, interior nodes represent programming constructs while in the parse tree, the interior nodes represent nonterminals
• A parse tree is sometimes called a concrete syntax tree, and the underlying grammar is called a concrete syntax for the languagez
• 

2.5.2 Adapting the Translation Scheme

• Transforms the production A→Aα|Aβ|γ into A→γR, R → αR|βR|ε
• Semantic actions embedded in the productions are simply carried along in the transformation, as if they were terminals
• Left-recursion elimination must be done carefully, to ensure that we preserve the ordering of semantic actions
• 
• 

2.5.3 Procedures for the Non-terminals

• Functions expr, rest, and term in Fig. 2.25 implement the syntax-directed translation scheme in Fig. 2.23. These functions mimic the production bodies of the corresponding nonterminals. Function expr implements the production expr -> term rest by the calls term() followed by rest ().
• 

2.5.4 Simplifying the Translator

• Certain recursive calls can be replaced by iterations
• When the last statement executed in a procedure body is a recursive call to the same procedure, the call is said to be tail recursive
• For a procedure without parameters, a tailrecursive call can be replaced simply by a jump to the beginning of the procedure
• 

2.5.5 The Complete Program

• Execution begins with function main, which is defined in class Postfix
• Function main creates an instance parse of class Parser and calls its functions Parser, expr, term, and match
• The function Parser, with the same name as its class, is a constructor
• Function expr is the result of the simplifications
• Function term uses the routine isDigit from the Java class Character to test if the lookahead symbol is a digit
• The function match checks terminals
• 

2.6 Lexical Analysis

• A lexical analyzer reads characters from the input and groups them into “token objects”
• A token object carries additional information in the form of attribute values
• A token is a terminal along with additional information
• A sequence of input characters that comprises a single token is called a lexeme
• 

2.6.1 Removal of White Space and Comments

for ( ; ; peek = next input character ) { 
    if ( peek is a blank or a tab ) do nothing; 
    else if ( peek is a newline ) line = line+-I; 
    else break; 
}

2.6.2 Reading Ahead

• A lexical analyzer may need to read ahead some characters before it can decide on the token to be returned to the parser
• A general approach to reading ahead on the input, is to maintain an input buffer from which the lexical analyzer can read and push back character
• One-character read-ahead usually suffices, so a simple solution is to use a variable, say peek, to hold the next input character
• The lexical analyzer reads ahead only when it must

2.6.3 Constants

• Integer constants can be allowed either by creating a terminal symbol, say num, for such constants or by incorporating the syntax of integer constants into the grammar
• The job of collecting characters into integers and computing their collective numerical value is generally given to a lexical analyzer
• When a sequence of digits appears in the input stream, the lexical analyzer passes to the parser a token consisting of the terminal num along with an integervalued attribute computed from the digits

if ( peek holds a digit ) { 
    u = 0; 
    do { 
    v = v * 10 + integer value of digit peek peek = next input character; ) 
    }while ( peek holds a digit ) ; 
    return token (num, v);
    }

2.6.4 Recognizing Keywords and Identifiers

• Most languages use fixed character strings such as for, do, and if, as punctuation marks or to identify constructs
• Such character strings are called keywords
• Character strings are also used as identifiers to name variables, arrays, functions, and the like
• Keywords generally satisfy the rules for forming identifiers, so a mechanism is needed for deciding when a lexeme forms a keyword and when it forms an identifier
• The problem is easier to resolve if keywords are reserved
• The lexical analyzer solves two problems by using a table to hold character strings:
  • Single Representation: A string table can insulate the rest of the compiler from the representation of strings, since the phases of the compiler can work with references or pointers to the string in the table
  • Reserved Words: Reserved words can be implemented by initializing the string table with the reserved strings and their tokens
    
    

2.6.5 A Lexical Analyzer

• Class Token and Subclass Num and Word
  
  
• Token and Tag
  
  
• Subclass Num and Word of Token
  
  
• : Code for a lexical analyzer
  
  

2.6.6 Exercises for Section 2.

2.7 Symbol Tables

• Symbol tables are data structures that are used by compilers to hold information about sourceprogram constructs
• Entries in the symbol table contain information about an identifier such as its character string (or lexeme), its type, its position in storage, and any other relevant information
• A program block with declarations will have its own symbol table with an entry for each declaration in the block

Who Creates Symbol-Table Entries?

• Symbol-entries are created and used during the analysis phase by the lexical analyzer, the parser, and the semantic analyzer
• With its knowledge of the syntactic structure of a program, a parser is often in a better position than the lexical analyzer to distinguish among different declarations of an identifier

2.7.1 Symbol Table Per Scope

• The term scope by itself refers to a portion of program that is the scope of one or more declaration
• Scopes are important, because the same identifier can be declared for different purposes in different parts of a program
• If blocks can be nested, several declarations of the same identifier can appear within a single block
• The most-closely nested rule for blocks is that an identifier x is in the scope of the most-closely nested declaration of x

2.7.2 The Use of Symbol Tables

• Chained symbol tables
  
  

2.8 Intermediate Code Generation

2.8.1 Two Kinds of Intermediate Representations

2.8.2 Construction of Syntax Tree

2.8.3 Static Checking

2.8.4 Three-Address Code

2.8.5 Exercises for Section 2.8

homework

2.2.1(a)(b)
2.2.3
2.2.4(a)(b)©(d)
2.3.2
2.4.1(b)©
2.6.2
2.8.1

tags: Compiler CSnote