COMPILER

CONSTRUCTION
Complete Note

PROF. A. O. OGUNDE
2025/2026 SESSION

Recommended Textbook
Compilers: Principles, Techniques and Tools by Alfred V. Aho, Ravi Sethi
and Jeffery D. Ullman.
INTRODUCTION
Compiler construction is a broad field. Compiler writing is perhaps the most
pervasive topic in computer science, involving many fields as:
– Programming languages – Architecture – Theory of computation
– Algorithms – Software engineering
In the early days, much of the effort was on how to implement high-level
constructs. Then, for a long time, the major emphasis was on improving the
efficiency of generated code. These topics remain important today, but many
new technologies have caused them to become more specialized.

WHY STUDY COMPILERS?

Compiler construction is studied for some of the following reasons:
➢ Writing a compiler gives a student experience with large-scale applications
development.
➢ Compiler writing is one of the shining triumphs of Computer Science
theory. It demonstrates the value of theory over the impulse to just "hack
up" a solution.
➢ Compiler writing is a basic element of programming language research.
Many language researchers write compilers for the languages they design.
➢ Many applications have similar properties to one or more phases of a
compiler, and compiler expertise and tools can help an application
programmer working on other projects besides compilers.

Translator
This special software translates other programs into the machine language.
They are in three categories:

1. Assembler: this translates a program written in assembly language into

the machine language.
2. Interpreter: this translates the source program into the object program
line by line and runs execute the program) straightaway.
3. Compiler: this translates the whole source program at once into the object
program

Some Differences between an Interpreter and a Compiler

No Interpreter Compiler
1 A line in error can be corrected The whole program must be
and run again before moving on compiled again in case there is error
2 Requires more memory space Less memory space is needed for
to store the interpreter when program to run
the program is running
3 Programs run very slow Programs usually run faster
4 Very useful in teaching More useful in production
environment environment

2
More on Compilers
A compiler is a program that reads a program written in one language (the
source language) and translates it into an equivalent program in another
language (the target language). The compiler reports any errors found during
the translation process.
Source Target
program Compiler program

Error
messages

The source language might be General purpose, e.g. C or Pascal, Or a “little

language” for a specific domain, e.g. SIML
The target language might be
– Some other programming language
– The machine language of a specific machine

A compiler creates machine code that runs on a processor with a specific

Instruction Set Architecture (ISA), which is processor-dependent. For
example, you cannot compile code for an x86 and run it on a MIPS
architecture without a special compiler. Compilers are also platform-
dependent. That is, a compiler can convert C++, for example, to machine code
that’s targeted at a platform that is running the Linux OS. A cross-compiler,
however, can generate code for a platform other than the one it runs on itself.
A cross-compiler running on a Windows machine, for instance, could generate
code that runs on a specific Windows operating system or a Linux (operating
system) platform. Source-to-source compilers translate one program, or code,
to another of a different language (e.g., from Java to C). Choosing a compiler
then, means that first you need to know the ISA, operating system, and the
programming language that you plan to use. Compilers often come as a
package with other tools, and each processor manufacturer will have at least
one compiler or a package of software development tools (that includes a
compiler. Compiler construction poses some of the most interesting problems
in computing.

More on Interpreters
A program that reads an executable program and produces the results of
running that program. An interpreter translates code like a compiler but reads
the code and immediately executes on that code, and therefore is initially
faster than a compiler. Thus, interpreters are often used in software
development tools as debugging tools, as they can execute a single in of code
at a time. Compilers translate code all at once and the processor then executes
upon the machine language that the compiler produced. If changes are made
to the code after compilation, the changed code will need to be compiled and
added to the compiled code (or perhaps the entire program will need to be re-
compiled.) But an interpreter, although skipping the step of compilation of the
entire program to start, is much slower to execute than the same program
that’s been completely compiled. Interpreters, however, have usefulness in

3
areas where speed doesn’t matter (e.g., debugging and training) and it is
possible to take the entire interpreter and use it on another ISA, which makes
it more portable than a compiler when working between hardware
architectures. There are several types of interpreters: the syntax-directed
interpreter (i.e., the Abstract Syntax Tree (AST) interpreter), bytecode
interpreter, and threaded interpreter (not to be confused with concurrent
processing threads), Just-in-Time (a kind of hybrid interpreter/compiler), and
a few others. Instructions on how to build an interpreter can be found on the
web. Some examples of programming languages that use interpreters are
Python, Ruby, Perl, and PHP.

More on Assemblers

An assembler translates a program written in assembly language into

machine language and is effectively a compiler for the assembly language, but
can also be used interactively like an interpreter. Assembly language is a low-
level programming language. Low-level programming languages are less like
human language in that they are more difficult to understand at a glance; you
have to study assembly code carefully in order to follow the intent of execution
and in most cases, assembly code has many more lines of code to represent
the same functions being executed as a higher-level language. An assembler
converts assembly language code into machine code (also known as object
code), an even lower-level language that the processor can directly
understand.

Assembly language code is more often used with 8-bit processors and
becomes increasingly unwieldy as the processor’s instruction set path
becomes wider (e.g., 16-bit, 32-bit, and 64-bit). It is not impossible for people
to read machine code, the strings of ones and zeros that digital devices
(including processors) use to communicate, but it’s likely only read by people
in cases of computer forensics or brute-force hacking. Assembly language is
the next level up from machine code, and is quite useful in extreme cases of
debugging code to determine exactly what’s going on in a problematic
execution, for instance. Sometimes compilers will “optimize” code in
unforeseen ways that affect outcomes to the bafflement of the developer or
programmer such that it’s necessary to carefully follow the step-by-step action
of the processor in assembly code, much like a hunter tracking prey or a
detective following clue.

Types of Compilers

There are several major kinds of compilers:

• Native Code Compiler
Translates source code into hardware (assembly or machine code)
instructions. Example: gcc.
• Virtual Machine Compiler
Translates source code into an abstract machine code, for execution by
a virtual machine interpreter. Example: javac.
• JIT Compiler

4
 Translates virtual machine code to native code. Operates within a
virtual machine. Example: Sun's HotSpot java machine.
• Preprocessor
Translates source code into simpler or slightly lower level source code,
for compilation by another compiler. Examples: cpp, m4.
• Pure Interpreter
Executes source code on the fly, without generating machine code.
Example: LISP.

What qualities are important in a compiler?

1. It must generate correct code
2. The output should run fast
3. The compiler should run fast
4. The compilation time should be proportional to program size
5. There should be support for separate compilation
6. There should be good diagnostics for syntax errors
7. The compiler must work well with the debugger
8. There should be good diagnostics for flow anomalies
9. It should allow cross language calls
10. The compiler should be consistent and predictable

How to Build a Compiler: Analysis-Synthesis Model of Compilation

There are two parts to compilation: analysis and synthesis.
(i) ANALYSIS: The analysis part breaks up the source program into
constituent pieces and creates an intermediate representation of the source
program.
(ii) SYNTHESIS: The synthesis part constructs the desired target program
from the intermediate representation, of the two parts, synthesis requires the
most specialized techniques.
During analysis, the operations implied by the source program are determined
and recorded in a hierarchical structure called a tree. Often, a special kind of
tree called a syntax tree is used, in which each node represents an operation
and the children of a node represent the arguments of the operation.
Sometimes we call the analysis part the FRONT END and the synthesis part
the BACK END of the compiler. Of the two parts, synthesis requires the most
specialized techniques. Note that the two can be written independently.

Source Code Analysis

Many software tools that manipulate source programs first perform some kind
of analysis. Some examples of such tools include:
– STRUCTURE EDITORS try to fill out syntax units as you type
– PRETTY PRINTERS highlight comments, indent your code for you etc.
– STATIC CHECKERS try to find programming bugs without actually running
the program

5
– INTERPRETERS do not bother to produce target code, but just perform the
operations implied by the source program

Source code analysis comes in three phases. They are:

– LINEAR ANALYSIS processes characters left-to-right and groups them into
tokens
– HIERARCHICAL ANALYSIS groups tokens hierarchically into nested
collections of tokens
– SEMANTIC ANALYSIS makes sure the program components fit together, e.g.
variables should be declared before they are used

6
 Phases of a Compiler
The diagram below represents the phases of a compiler.

Source Program

Lexical Analysis

Syntax Analysis

Semantic Analysis

Symbol-table management Error handling

Intermediate Code
Generation

Code Optimization

Code Generation

Target Program

Linear (Lexical) Analysis

The linear analysis stage is called lexical analysis or scanning. For
example, the characters in the assignment statement
position = initial + rate * 60
would be grouped into the following tokens and is translated as:
1. The IDENTIFIER “position”
2. The ASSIGNMENT SYMBOL “=”
3. The IDENTIFIER “initial”
4. The PLUS OPERATOR “+”
5. The IDENTIFIER “rate”
6. The MULTIPLICATION OPERATOR “*”
7. The NUMERIC LITERAL 60
Blanks are always eliminated during lexical analysis

Hierarchical (syntax) analysis

The hierarchical stage is called syntax analysis or parsing. It involves
grouping the tokens of the source program into grammatical phrases that are

7
used by the compiler to synthesize output. The hierarchical structure of the
source program can be represented by a PARSE TREE, for example:
Assignment statement

=
identifier expression

position +
expression
expression

expression * expression
identifier

initial identifier number

rate 60
The hierarchical structure of the syntactic units in a programming language
is normally represented by a set of recursive rules. Example of such rules for
expressions is:
1. Any identifier is an expression
2. Any number is an expression
3. If expression1 and expression2 are expressions, then so are
expression1+expression2
expression1*expression2
(expression1)
Rules (1) and (2) are (nonrecursive) basic rules, while (3) defines expressions
in terms of operators applied to other expressions.

Similarly, example of such rules for statements is:

1. If identifier1 is an identifier and expression2 is an expression, then
identifier1 = expression2 is a statement.
2. If expression1 is an expression and statement2 is a statement, then the
following are statements:

while (expression1 )dostatement2

if( expression1 ) thenstatement2
are statements.

Lexical vs. Syntactic analysis

Generally, if a syntactic unit can be recognized in a linear scan, we convert it
into a token during lexical analysis. More complex syntactic units, especially
recursive structures, are normally processed during syntactic analysis
(parsing).Identifiers, for example, can be recognized easily in a linear scan, so
identifiers are tokenized during lexical analysis.

It is common to convert complex parse trees to simpler syntax trees, with a

node for each operator and children for the operands of each operator. For the
analysis of Position=initial + rate *60
we have,

8
Semantic Analysis
The semantic analysis stage:
– Checks for semantic errors, e.g. undeclared variables
– Gathers type information
– Determines the operators and operands of expressions
Example: if rate is a float, the integer literal 60 should be converted to a float
before multiplying. Then, we have

Symbol-table management
A symbol table is a data structure containing a record for each identifier with
fields for the attributes of the identifier. During analysis, we record the
identifiers used in the program. The symbol table stores each identifier with
its attributes. Example of attributes:
– How much storage is allocated for the id – The id’s type– The id’s scope–
For functions, the parameter protocol
Some attributes can be determined immediately; some are delayed until later
phases.

Error detection
Each compilation phase can have errors. Normally, we want to keep
processing after an error, in order to find more errors. Each stage has its own
characteristic errors, e.g.
– Lexical analysis: a string of characters that do not forma legal token
– Syntax analysis: unmatched { } or missing ;
– Semantic: trying to add a float and a pointer
The internal representations of this process is illustrated with our case
example below

9
Intermediate code generation
Some compilers explicitly create an intermediate representation of the source
code program after semantic analysis. The representation is as a program for
an abstract machine. Most common representation is “three-address code” in
which all memory locations are treated as registers, and most instructions
apply an operator to two operand registers, and store the result to a
destination register.

Code optimization
This phase attempts to improve the intermediate code. At this stage, we
improve the code to make it run faster.

Code generation
This is the final phase of the compiler where the target code is generated. In
this final stage, we take the three-address code (3AC)or other intermediate
representation, and convert to the target language. We must pick memory
locations for variables and allocate registers. For example, using registers 1
and 2, the translation of our case sample code might become

MOVF id3, R2
MULF #60.0, R2
MOVF id2, R1
ADDF R2, R1
MOVF R1, id1

i.e.
temp1 := id3 * 60.0
id1 := id2 + temp1

10
Compiler writing tools
Many software tools have been developed to help implement various compiler
phases. The following is a list of some useful compiler construction tools:
Scanner generators produce lexical analyzers automatically.
– Input: a specification of the tokens of a language (usually written
as regular expressions)
– Output: C code to break the source language into tokens.
e.g. Lex
Parser generators produce syntactic analyzers automatically.
– Input: a specification of the language syntax (usually written as a
context-free grammar)
– Output: C code to build the syntax tree from the token sequence.
e.g. Yacc
There are also automated systems for code synthesis.

Assignment
Distinguish between a compiler and an interpreter.

11
LEXICAL ANALYSIS
This is the first phase of a compiler. Its task is to read the input characters
and produce as output a sequence of tokens that the parser uses for syntax
analysis.
Source token
Lexical
Parser
program Analyzer
get next token

Symbol
Table

This interaction is commonly implemented by making the lexical analyzer be

a subroutine or a coroutine of the parser. Upon receiving a “get next token”
command from the parser, the lexical analyzer reads input characters until it
can identify a token and returns it. Since the lexical analyzer is part of the
compiler that reads the source text, it may also perform certain secondary
tasks at the user interface. They are:
– Strip out comments and white space from the source code.
– Correlate parser errors with the source code location (the parser
does not know what line of the file it is at, but the lexer does)

Tokens, Patterns, Lexemes

A TOKEN is a set of strings over the source alphabet. A PATTERN is a rule
that describes that set. A LEXEME is a sequence of characters in the source
program that is matched by the pattern for a token. E.g. in Pascal, for the
statement
const pi = 3.1416;
The substring pi is a lexeme for the token “identifier”
Example of tokens, lexemes, patterns
Token Sample Lexemes Informal Description of Pattern
if If If
while While While
relation <, <=, =, <>, >, >= < or <= or = or <> or > or >=
id count, sum, i, j, pi, D2 letter followed by letters and digits
num 0, 12, 3.1416, 6.02E23 any numeric constant
literal “please enter input values” any characters between “and”
Together, the complete set of tokens form the set of terminal symbols used in
the grammar for the parser. In most languages, the tokens fall into these
categories:
– Keywords
– Operators
– Identifiers
– Constants
– Literal strings
– Punctuation

Usually the token is represented as an integer. The lexer and parser just agree
on which integers are used for each token.

12
Token attributes
If there is more than one lexeme for a token, we have to save additional
information about the token.
Example: the token number matches lexemes 10 and 20.
Code generation needs the actual number, not just the token. With each
token, we associate ATTRIBUTES. Normally just a pointer into the symbol
table. For C source code E=M*C*C
We have token/attribute pairs
<ID, ptr to symbol table entry for E>
<Assign_op, NULL>
<ID, ptr to symbol table entry for M>
<Mult_op, NULL>
<ID, ptr to symbol table entry for C>
<Mult_op, NULL>
<ID, ptr to symbol table entry for C>
Lexical errors
When errors occur, we could just crash but it is better to print an error
message then continue. Possible techniques to continue on error:
– Delete a character
– Insert a missing character
– Replace an incorrect character by a correct character
– Transpose adjacent characters

Implementation of Lexical Analyzer

There are 3 general approaches to the implementation of a lexical analyzer.
1. Lexical analyzer generator can be used, such as the Lex compiler to
produce the lexical analyzer from a regular expression based
specification. In this case, the generator provides routines for
reading and buffering the input.
2. Writing the lexical analyzer in a conventional systems-programming
language, using the I/O facilities of that language to read the input
3. Writing the lexical analyzer in assembly language and explicitly
managing the reading of input.

The three are written in the order of increasing difficulty for the implementer.
Unfortunately, the harder to implement approaches often yield faster lexical
analyzers. Note that the design and use of an automatic generator and some
concepts for the organization of a hand-designed lexical analyzer shall be
discussed here.

Token specification
REGULAR EXPRESSIONS (REs) are the most common notation for pattern
specification. Every pattern specifies a set of strings, so a RE names a set of
strings. Some definitions are stated below:
– The ALPHABET or CHARCATER (often written) is the set of legal input
symbols and denotes any finite set of symbols e.g. letters and characters e.g.
{0,1) is an example of binary alphabet, ASCII and EBCDIC is an example of
computer alphabet
– A STRING over some alphabet is a finite sequence of symbols from  e.g.
sentence and word in language theory

13
– The LENGTH of string s is written |s|. It is the number of occurrences of
symbols in s
– The EMPTY STRING is a special 0-length string denoted by 
A PREFIX of s is formed by removing 0 or more trailing symbols of s e.g. ban
is a prefix of banana
A SUFFIX of s is formed by removing 0 or more leading symbols of s e.g. nana
is a suffix of banana
A SUBSTRING of s is formed by deleting a prefix and a suffix from s e.g. nan
is a substring of banana
A PROPER prefix, suffix, or substring is a nonempty string x that is,
respectively, a prefix, suffix, or substring of s but with x ≠s.
A SUBSEQUENCE of s is any string formed by deleting zero or more not
necessarily contiguous symbols from s e.g. baaa
A LANGUAGE is a set of strings over a fixed alphabet .Examples are:
– $ (the empty set)
–{"}
– { a, aa, aaa, aaaa }
The CONCATENATION of two strings x and y is written xy
String EXPONENTIATION is written si, where s0 = and si= si-1s for i>0.

Operations on languages

Several important operations can be applied to languages. For lexical analysis,

we are interested primarily in union, concatenation, and closure, which are
defined below. We can also generalize the “exponentiation” operator to
languages by defining L° to be {}, and Li to be Li-1L. Thus, Li is L concatenated
with itself i-1 times.

The UNION of L and M:L M = { s | s is in L OR s is in M }

The CONCATENATION of L and M:LM = { st | s is in L and t is in M }
The KLEENE CLOSURE of L:L* ={ i =0 Li }


The POSITIVE CLOSURE of L: L+={ i =1 Li }



Example:
Let L be the set {A, B..., z, a, b,.., z} and D the set (0, 1, 2, ……9). We can think
of L and D in two ways. We can think of L as the alphabet consisting of the
set of upper and lower case letters, and D as the alphabet consisting of the
set of the ten decimal digits. Alternatively, since a symbol can be regarded as

14
a string of length one, the sets L and D are each finite languages. Here are
some examples of new languages created from L and D by applying the
operators defined above.

1. L  D is the set of Letters and digits.

2. LD is the set of strings consisting of a letter followed by a digit

3. L4 is the set of all four-letter strings.

4. L* is the set of all strings of letters, including , the empty string.

5. L(L U D)* is the set of all strings of letters and digits beginning with a
letter

6. D* is the set of all strings of one or more digits.

Regular Expressions
In Pascal, an identifier is a letter followed by zero or more letters or digits; that
is, an identifier is a member of the set defined in part (5) of the above example.
Regular expression is presented here which allows us to define precisely sets
such as this. With this notation, we might define Pascal identifiers as
Ietter(Ietter|digit)*
The vertical bar here means “or”, the parentheses are used to group sub-
expressions, the star means “zero or more instances of” the parenthesized
expression, and the juxtaposition of letter with the remainder of the
expression means concatenation.

A regular expression is built up out of simpler regular expressions using a set

of defining rules. Each regular expression r denotes a language L(r). The
defining rules specify how L(r) is formed by combining in various ways the
languages denoted by the sub expressions of r.
Here are the rules that define the regular expressions over alphabet Z
Associated with each rule is a specification of the language denoted by the
regular expression being defined

1.  is a regular expression that denotes {}, that is, the set

containing the empty string.

2. If a is a symbol in , then a is a regular expression that denotes {a},

i.e., the set containing the string a. Although we use the same
notation for all three, technically, the regular expression a is
different from the string a or the symbol a. It will be clear from the
context whether we are talking about a as a regular expression,
string, or symbol.

3. Suppose r and s are regular expressions denoting the languages L(r)

and L(s). Then,

(a) (r)|(s) is a regular expression denoting L(r) U L(s).

15
 (b) (r)(s) is a regu1ar expression denoting L(r)L(s)

(c) (r)* is a regular expression denoting (L(r))* (that is, extra pairs of
parentheses may be placed around regular expressions if we so
desire).

(d) (r) is a regular expression denoting L(r)

A language denoted by a regular expression is said to be a regular set.

The specification of a regular expression is an example of a recursive
definition. Rules (I) and (2) form the basis of the definition; the term basic
symbol is used to refer to  or a symbol in  appearing in a regular expression.
Rule (3) provides the inductive step.

Unnecessary parentheses can be avoided in regular expressions if we adopt

the convention that:

1. the unary operator * has the highest precedence and is left associative

2. concatenation has the second highest precedence and is left associative

3. | has the lowest precedence and is left associative.

Under these conventions, (a)|((b)*(c))is equivalent to a|b*c. Both expressions

denote the set of strings that are either a single a or zero or more b’s followed
by one c.

Example: Let  = {a, b}.

1. The regular expression a|b denotes the set {a, b}.

2. The regular expression (a|b)(a|b) denotes {aa, ab, ba, bb), that is, the
set of all strings of a’s and b’s of length two. Another regular expression
for this same set is aa|ab|ba|bb.

3. The regular expression a* denotes the set of all strings of zero or more
a’s, i.e. (, a, aa, aaa, …).

4. The regular expression (a|b)* denotes the set of all strings containing
zero or more instances of an a or b, that is, the set of all strings of a’s
and b’s. Another regular expression for this set is (a*b*)*

5. The regular expression a |a*b denotes the set containing the string a
and all strings consisting of zero or more a’s followed by b.

If two regular expressions r and s denote the same language, we say r and s
are equivalent and write r = s. For example, (a|b) = (b|a).
There are a number of algebraic laws obeyed by regular expressions and these
can be used to manipulate regular expressions into equivalent forms. The
table below shows some algebraic laws that hold for regular expressions r, s.
and t.

16
Regular Definitions
To make our REs simpler, we may wish to give names to regular expressions
and to define regular expressions using these names as If they were symbols.
If S is an alphabet of basic symbols, them a regular definition is a sequence
of definitions of the form
d1→ r1
d2→r2
………
dn→rn
where each di is a distinct name, and each ri is a regular expression over the
symbols in  {d1, d2,. . . di-1}, i.e., the basic symbols and the previously
defined names. By restricting each ri to symbols of  and the previously
defined names, we can construct a regular expression over  for any ri by
repeatedly replacing regular expression names by the expressions they
denote. If ri used dj for some j i, then ri might be recursively defined and this
substitution process would not terminate. To distinguish names from
symbols, we print the names in regular definitions in bold face.

Example:
Here is a regular definition for identifier in Pascal
letter → A | B | . . . | Z | a | b | …… | z
digit → 0|1|...|9
id → letter(letter|digit)*

Here is a regular definition for identifier in C

letter → A | B | . . . | Z | a | b | …… | z
digit → 0|1|...|9
id → letter(letter|___ ) (letter|digit|___)*

17
Example for numbers in Pascal:
digit → 0 | 1 | …….. | 9
digits →digitdigit*
optional_fraction → . digits |
optional_exponent → (E ( + | - | ) digits) |
num →digits optional_fraction optional_exponent

This definition says that an optional_fraction is either a decimal point

followed by one or more digits, or if it is missing (the empty string). An
optional_exponent, if it is not missing, is an E followed by a + or - sign,
followed by one or more digits. Note that at least, one digit must follow the
period, so num does not match 1. however, it does match 1.0

Notational Shorthand
To simplify out REs, we can use a few shortcuts:
1. + “means one or more instances of” e.g. a+ (ab)+

2. ? means “zero or one instance of”

e.g. optional_fraction→ (. digits ) ?
3. [ ] creates a character class
e.g. [A-Za-z][A-Za-z0-9]*

Token Recognition
Having known how to specify the tokens for our language, how then do we
write a program to recognize them?
Consider this grammar example:
stmt→if expr then stmt
| if expr then stmt else stmt
|
expr→term relop term
| term
term→id
| num
where the terminals if, then, else, relop, id and num generates sets of strings
given by the following regular definitions.
if → If
then → Then
else → Else
relop → < | <= | = | <> | > | >=
id → letter(letter | digit)*
num → digit*(.digit*)? (E(+|-)? digit*)?

It is assumed that keywords are reserved, lexemes are separated by white

space, consisting of non-null sequences of blanks, tabs and newlines. The
lexical analyzer will strip out the white space by comparing the strings with
the regular definition ws below:

Delim → blank | tab | newline

ws → delim*

18
If a match for ws is found, the lexical analyzer does not return a token to the
parser; rather, it proceeds to find a token following the white space and
returns that to the parser. The goal is to construct a lexical analyzer that will
isolate the lexeme for the next token in the input buffer and produce as output
a pair consisting of the appropriate token and attribute-vaIue, using the
translation table given by the table below.

NOTE
Note that the regular expression constructs permitted by Lex are listed below
in decreasing order of precedence. In this table, c stands for any single
character, r for a regular expression, and s for a string.

19
Transition Diagrams
The transition diagram is a stylized flowchart produced as one of the
intermediate steps in the construction of a lexical analyzer. It depicts the
action taken when a lexical analyzer is called by the parser to get the next
token. Transition diagrams are also called finite automata.
Positions in a transition diagram are drawn as circles and are called states.
The states are connected by arrows, called edges. Edges leaving state s have
labels indicating the input characters that can next appear after the transition
diagram has reached state s. The label other refers to any character that is
not indicated by any of the other edges leaving s. Usually, when we recognize
OTHER, we need to put it back in the source stream since it is part of the next
token. This action is denoted with a * next to the corresponding state.
We assume the transition diagrams of this section are deterministic; that is,
no symbol can match the labels of two edges leaving one state. One state is
labeled the start state; it is the initial state of the transition diagram where
control resides when we begin to recognize a token. Certain states may have
actions that are executed when the flow of control reaches that state. On
entering a state we read the next input character. If there is an edge from the
current state whose label matches this input character, we then go to the
state pointed to by the edge. Otherwise, we indicate failure.
The figure below shows a transition diagram for the patterns >= and >. The
transition diagram works as follows, its start state is state 0. In state 0, we
read the next input character. The edge labeled > from state 0 is to be followed
to state 6 if this input character is >. Otherwise, we have failed to recognize
either > or >=.

On reaching state 6 we read the next input character. The edge labeled = from
state 6 is to be followed to state 7 if this input character is an =. Otherwise,
the edge labeled other indicates that we are to go to state 8. The double circle
on state 7 indicates that it is an accepting state, a state in which the token
>=has been found.

Notice that the character > and another extra character are read as we follow
the sequence of edges from the start state to the accepting state 8. Since the
extra character is not a part of the relational operator >, we must retract the
forward pointer one character. We use a * to indicate states on which this
input retraction must take place.

In general, there may be several transition diagrams, each specifying a group

of tokens. If failure occurs while we are following one transition diagram, then
we retract the forward pointer to where it was in the start state of this diagram,
and activate the next transition diagram. Since the lexeme-beginning and
forward pointers marked the same position in the start state of the diagram,
the forward pointer is retracted to the position marked by the lexeme-

20
beginning pointer. If failure occurs in all transition diagrams, then a lexical
error has been detected and we invoke an error-recovery routine.

Transition diagram for re1ationaI operators

Transition diagram for identifiers and keywords

A simple technique for separating keywords from identifiers is to initialize

appropriately the symbol table in which information about identifiers is saved.
For the tokens described above, we need to enter the strings if, then, and else
into the symbol table before any characters in the input are seen. We also
make a note in the symbol table of the token to be returned when one of these
strings is recognized. The return statement next to the accepting state in the
figure above uses gettoken() and install_id() to obtain the token and attribute
value, respectively, to be returned. The procedure install_id() has access to the
buffer, where the identifier lexeme has been located. The symbol table is
examined and if the lexeme is found there marked as a keyword, install_id()
returns 0. If the lexeme is found and is a program variable install_id() returns
a pointer to the symbol table entry. If the lexeme is not found in the symbol
table, it is installed as a variable and a pointer to the newly created entry is
returned.

The procedure gettoken() similarly looks for the lexeme in the symbol table. If
the lexeme is a keyword, the corresponding token is returned; otherwise, the
token Id is returned. Note that the transition diagram does not change if
additional keywords are to be recognized; we simply initialize the symbol table
with the strings and tokens of the additional keywords. The technique of
placing keywords in the symbol table is almost essential if the lexical analyzer
is coded by hand. Without doing so, the number of states in a lexical analyzer
for a typical programming language is several hundred, while using the trick,
fewer than a hundred states will probably suffice.

21
 Transition diagram for unsigned numbers in Pascal

The treatment of ws, representing white space, is different from that of the
patterns discussed above because nothing is returned to the parser when
white space is found in the input. A transition diagram recognizing ws by
itself is shown below:

Nothing is returned when the accepting state is reached; we merely go back

to the start state of the first transition diagram to look for another pattern.
Whenever possible, it is better to look for frequently occurring tokens before
less frequently occurring ones, because a transition diagram is reached only
after we fail on all earlier diagrams. Since white space is expected to occur
frequently, putting the transition diagram for white space near the beginning
should be an improvement over testing for white space at the end.

For each state, in every diagram, a piece of code is written to compare the
next input with the outgoing transitions and set the next state. If no next state
is possible for the given input, we call fail(). fail() backtracks to the beginning
of the token and tries again with the next transition diagram. If all diagrams
fail, we generate an error. Ordering of the diagrams is important. E.g. for
unsigned numbers, the longer diagrams have to be tried first.

22
A LANGUAGE FOR SPECIFYING LEXICAL ANALYZERS

Several tools have been built for constructing lexical analyzers from special-
purpose notations based on regular expressions. We have already seen the
use of regular expressions for specifying token patterns. Before we consider
algorithms for compiling regular expressions into pattern-matching programs
we give an example of a tool that might use such an algorithm.
in this section, we describe a particular tool, called Lex that has been widely
used to specify lexical analyzers for a variety of languages. We refer to the tool
as the Lex compiler, and to its input specification as the Lex Language.
Discussion of an existing tool will allow us to show how the specification of
patterns using regular expressions can be combined with actions, e.g.,
making entries into a symbol table, that a lexical analyzer may be required to
perform. Lex-like specifications can be used even if a compiler is not available;
the specifications can be manually transcribed into a working program using
the transition diagram techniques of the previous section.
Lex is generally used in the manner depicted in the diagram below.

23
First, a specification of a lexical analyzer is prepared by creating a program in
lex.1 in the Lex language. The lex.1 is run through the Lex compiler to produce
a C program [Link].c. The program [Link].c consists of a tabular
representation of a transition diagram constructed from the regular
expressions of lex.1, together with a standard routine that uses the table to
recognize Iexemes. The actions associated with regular expressions in lex.1
are pieces of C code and are carried over directly to [Link].c. Finally, [Link].c
is run through the C compiler to produce an object program [Link], which is
the lexical analyzer that transforms an input stream into a sequence of
tokens.

FINITE AUTOMATA
A recognizer for a language is a program that takes as input a string x and
answers “yes” if x is a sentence of the language and “no” otherwise. Regular
expression is compiled into a recognizer by constructing a generalized
transition diagram called a finite automaton. A finite automaton can be
deterministic or nondeterministic, where nondeterministic means that more
than one transition out of a state may be possible on the same input symbol.
Both deterministic and nondeterministic finite automata are capable of
recognizing precisely the regular sets. Thus they both can recognize exactly
what regular expressions can denote. However, there is a time-space tradeoff;
while deterministic finite automata can lead to faster recognizers than non-
deterministic automata, a deterministic finite automaton can be much bigger
than an equivalent nondeterministic automaton. The conversion into a
nondeterministic automaton is more direct.

Nondeterministic Finite Automata

A nondeterministic finite automaton (NFA, for short) is a mathematical model
that consists of
1. a set of states S
2. a set of input symbols  (the input symbol alphabets)
3. a transition function move that maps state-symbol pairs to sets of
states
4. a state So that is distinguished as the start (or initial) state
5. a set of states F distinguished as accepting (or final) states

An NFA can be represented diagrammatically by a labeled directed graph

called a transition graph, in which the nodes are the states and the labeled
edges represent the transition function. This graph looks like a transition
diagram, but the same character can label two or more transitions out of one
state, and edges can be labeled by the special symbol  as well as by input
symbols. The transition graph for an NFA that recognizes the language
(a|b)*abb is shown below. The set of states of the NFA is {0, 1, 2, 3} and the
input symbol alphabet is (a,b}. State 0 is distinguished as the start state, and
the accepting state 3 is indicated by a double circle.

24
In a Computer, the transition function of an NFA can be implemented in
several different ways of which easiest implementation is a transition table in
which there is a row for each state and a column for each input symbol and 
if necessary. The entry for row i and symbol a in the table is the set of states
(or more likely in practice, a pointer to the set of states) that can be reached
by a transition from state i on input a. The transition table for the NFA above
is shown below:

The transition table representation has the advantage that provides fast
access to the transitions of a given state on a given character; its disadvantage
is that it can take up a lot of space when the input alphabet is large and most
transitions are to the empty set. Adjacency list representations of the
transition function provide more compact implementations, but access to a
given transition is slower. It should be clear that we can easily convert any
one of these implementations of a finite automaton into another.
An NFA accepts an input string x if and only if there is some path in the
transition graph from the start state to some accepting state, such that the
edge labels along this path spell out x. The NFA described above accepts the
input strings abb, aabb, babb, aaabb. For example, aabb is accepted by the
path from 0, following the edge labeled a to state 0 again, then to states I, 2,
and 3 via edges labeled a, b, and b, respectively.
A path can be represented by a sequence of state transitions called moves.
The following diagram shows the moves made in accepting the input string
aabb:

In general, more than one sequence of moves can lead to an accepting stale.
Notice that several other sequences of moves may be made on the input string
aabb but none of the others happen to end in an accepting state. For example,
another sequence of moves on input aabb keeps reentering the non- accepting
state 0:

The language defined by an NFA is the set of input strings it accepts.

Exercise:
1. Show that the NFA above accepts (a|b)*abb.
2. Design an NFA to accept aa*|bb*

25
Solution:

Deterministic Finite Automata (DFA)

A deterministic finite automaton (DFA, for short) is a special case of a
nondeterministic finite automaton in which
1. no state has an -transition i.e., a transition on input , and
2. for each stale sand input symbol a, there is at most one edge labeled
a leaving s,

A deterministic finite automaton has at most one transition from each state
on any input, if we are using a transition table to represent the transition
function of a DFA, then each entry in the transition table is a single state.
Consequently, it is very easy to determine whether a deterministic finite
automaton accepts an input siring, since there is at most one path from the
start state labeled by that string.
Example below shows the transition graph of a deterministic finite automaton
accepting the same language (a|b)*abb as that accepted by the NFA described
above. It follows the sequence of states 0, 1, 2, 1, 2, 3

Assignment
1. Write Regular Expressions for Identifiers in any other four programming
languages.

26
EXAMPLES OF IDENTIFIERS IN COMMON PROGRAMMING LANGUAGES

IDENTIFIERS IN C++
How to check identifier in C++?
• Names can contain letters, digits and underscores.
• Names must begin with a letter or an underscore (_)
• Names are case-sensitive ( myVar and myvar are different variables)
• Names cannot contain whitespaces or special characters like !, #, %, etc.
Regular Expression
letter → A | B | . . . | Z | a | b | …… | z
digit → 0 | 1 | . . . | 9
id → (letter|___) (letter|digit|___)*
Also written in Lex convention as
^_|A-Z|a-z]+[_|A-Z|a-z|0-9]*$

Example
// C++ program to illustrate the identifiers
#include <iostream>
using namespace std;

// here Car_24 identifier is used to refer the below class

class Car_24 {
string Brand;
string model;
int year;
};

// calculateSum identifier is used to call the below function

void calculateSum(int a, int b)
{
int _sum = a + b;
cout << "The sum is: " << _sum << endl;
}

int main()
{
// identifiers used as variable names
int studentAge = 20;
double accountBalance = 1000.50;
string student_Name = "Karan";

calculateSum(2, 10);

return 0;
}

Question?
1. How many identifiers are in the above code? Name them.

IDENTIFIERS IN C#
In programming languages, identifiers are used for identification purposes. Or in other words,
identifiers are the user-defined name of the program components. In C#, an identifier can be
a class name, method name, variable name, or label.

27
Example:
public class GFG {
static public void Main ()
{
int x;
}
}

Here the total number of identifiers present in the above example is 3 and the names of these
identifiers are:
GFG: Name of the class
Main: Method name
x: Variable name

Rules for defining identifiers in C#:

There are certain valid rules for defining a valid C# identifier. These rules should be followed,
otherwise, we will get a compile-time error.
• The only allowed characters for identifiers are all alphanumeric characters ([A-Z], [a-
z], [0-9]), ‘_‘ (underscore). For example “geek@” is not a valid C# identifier as it contains
‘@’ – special character.
• Identifiers should not start with digits ([0-9]). For example “123geeks” is not valid in
the C# identifier.
• Identifiers should not contain white spaces.
• Identifiers cannot be used as keywords unless they include @ as a prefix. For example,
@as is a valid identifier, but “as” is not because it is a keyword.
• C# identifiers allow Unicode Characters.
• C# identifiers are case-sensitive.
• C# identifiers cannot contain more than 512 characters.
• Identifiers do not contain two consecutive underscores in their name because such
identifiers are used for the implementation.

Regular Expression
letter → A | B | . . . | Z | a | b | …… | z
digit → 0 | 1 | . . . | 9
id → (letter|___) (letter|digit|___)*
Also written in Lex convention as
^_|A-Z|a-z]+[_|A-Z|a-z|0-9]*$

// Simple C# program to illustrate identifiers

using System;

class GFG {

// Main Method
static public void Main ()
{

// variable
int a = 10;
int b = 39;
int c;

// simple addition
c = a + b;
[Link]("The sum of two number is: {0}", c);
}
}

28
Output:

The sum of two number is: 49

Below table shows the identifiers and keywords present in the above
example:

Keywords Identifiers

using GFG

public Main

static A

void B

int C

IDENTIFIERS IN PYTHON
Python Identifier is the name we give to identify a variable, function, class, module or other
object. That means whenever we want to give an entity a name, that's called identifier. A
python identifier is a name given to various entities like variables, functions, and classes.
The isidentifier() method returns True if the string is a valid identifier, otherwise False. A
string is considered a valid identifier if it only contains alphanumeric letters (a-z) and (0-9),
or underscores (_). A valid identifier cannot start with a number, or contain any spaces.
In Python, identifiers are case-sensitive, meaning that foo and Foo are considered to be two
different identifiers.

Rulesfor Identifiers in Python

• Keywords cannot be used as identifiers in python (because they are reserved words)
• The name of identifiers in python cannot begin with a number
• All the identifiers in python should have a unique name in the same scope
• The first character of identifiers in python should always start with an alphabet or
underscore, and then it can be followed by any of the digit, character, or underscore.
• Identifier name length is unrestricted
• Names of identifiers in python are case sensitive meaning ‘car’ and ‘Car’ Would be
treated differently
• Special characters such as ‘%’, ‘#’,’@’, and ‘$’ are not allowed as identifiers in python.

Examples of Python Identifiers

Valid Identifiers in Python
yourname - It contains only lowercase alphabets.
Name_school - It contains only ‘_’ as a special character.
Id1 - Here, the numeric digit comes at the end.
roll_2 - It starts with lowercase and ends with a digit.
_classname - Contains lowercase alphabets and an underscore and It starts with an
underscore ‘_’

29
Invalid Identifiers in Python
(for, while, in) - these are the keywords in python that cannot use as identifiers in python.
1myname - Invalid identifier because It begins with a digit
\$myname - Invalid identifier because It starts with a special character
a b - Invalid identifier because it contains a blank space
(a/b and a+b) - are Invalid identifiers because contain special character

Regular Expression
letter → A | B | . . . | Z | a | b | …… | z
digit → 0 | 1 | . . . | 9
id → (letter|___) (letter|digit|___)*
Also written in Lex convention as
^_|A-Z|a-z]+[_|A-Z|a-z|0-9]*$

IDENTIFIERS IN JAVA
The valid rules for defining Java identifiers are:
• It must start with either lower case alphabet[a-z] or upper case alphabet [A-Z] or
underscore (_) or a dollar sign($).
• It should be a single word, the white spaces are not allowed.
• It should not start with digits.

Rules For Defining Java Identifiers

There are specific rules to follow when defining these identifiers.
1. Alphanumeric Characters: Identifiers can include letters (A-Z and a-z), digits (0-9),
underscore (_), and dollar sign ($). However, they must start with a letter, an underscore or
a dollar sign. They cannot begin with a digit.
2. Case Sensitivity: Java is case-sensitive, meaning MyIdentifier and myidentifier would be
recognized as distinct identifiers.
3. No Reserved Words: Identifiers cannot be Java reserved words or keywords. For example,
you cannot name a variable int or class as these are reserved by the language.
4. No Special Characters: Apart from underscore and dollar sign, no other special characters
or spaces are allowed in identifiers.
5. Length Limitation: Technically, there is no limit on the length of an identifier in Java.
However, it is advisable to keep them concise for the sake of readability and maintainability
of the code.

Regular Expression for JAVA

letter → A | B | . . . | Z | a | b | …… | z
digit → 0 | 1 | . . . | 9
id → (letter|___|$) (letter|digit|___)*
Also written in Lex convention as
^_|$|A-Z|a-z]+[_|A-Z|a-z|0-9]*$

Here's a table on valid and invalid identifiers in Java for a quick glance.

Criteria Valid Identifiers Invalid Identifiers

Start with a letter,
underscore (_), or dollar myVariable, _value, $id 9pins, -name
sign ($)
Subsequent characters var1, i9, _1_value a@b, hello!world
(Case variations are valid but
Case Sensitivity myVariable, MyVariable
represent different identifiers)
No reserved words userInput, totalSum class, int, void
(No length-based invalidity, but very
Unlimited length
longIdentifierName123 long names are discouraged for
(practically reasonable)
readability)

30
SYNTAX ANALYSIS
Every programming language has rules that prescribe the syntactic structure
of well-formed programs. In Pascal, for example. a program is made out of
blocks, a block out of statements, a statement out of expressions, an
expression out of tokens. and so on. The syntax of programming language
constructs can be described by context-free grammars or BNF (Backus-Naur
Form) notation. Grammars offer significant advantages to both language
designers and compiler writers.

What is a Grammar?
• A grammar gives a precise, yet easy-to-understand, syntactic specification
of a programming language.
• From certain classes of grammars we can automatically construct an
efficient parser that determines if a source program is syntactically well
formed. As an additional benefit, the parser construction process can reveal
syntactic ambiguities and other difficult-to-parse constructs that might
otherwise go undetected in the initial design phase of a language ad its
compiler.
• A properly designed grammar imparts a structure to a programming
language that is useful for the translation of source programs into correct
object code and for the detection of errors. Tools are available for converting
grammar-based descriptions of translations into working programs.

THE ROLE OF THE SYNTAX ANALYZER (PARSER)

The parser obtains a string of tokens from the lexical analyzer and verifies
that the string can be generated by the grammar for the source language. We
expect the parser to report any syntax errors in an intelligible fashion. It
should also recover from commonly occurring errors so that it can continue
processing the remainder of its input.
There are three general types of parsers for grammars. Universal parsing
methods such as the Cocke-Younger-Kasami algorithm and Earley’s
algorithm can parse any grammar. These methods, however, are too inefficient

31
to use in production compilers. Commonly used methods in compilers are
classified as being either top-down or bottom-up. As indicated by their names,
top-down parsers build parse trees from the top (root) to the bottom (leaves),
while bottom-up parsers start from the leaves and work up to the root. In both
cases, the input to the parser is scanned from left to right, one symbol at a
time.
The most efficient top-down and bottom-up methods work only on subclasses
of grammars, but several of these subclasses, such as the LL and LR
grammars, are expressive enough to describe most syntactic constructs in
programming languages. Parsers implemented by hand often work with LL
grammars. Parsers for the larger class of LR grammars are usually
constructed by automated tools.

Syntax Error Handling

Most programming language specifications do not describe how a compiler
should respond to errors: the response is left to the compiler designer.
Planning the error handling right from the start can both simplify the
structure of a compiler and improve its response to errors.
We know that programs can contain errors at many different levels. For
example,
• lexical, such as misspelling an identifier, keyword, or operator
• syntactic, such as an arithmetic expression with unbalanced parentheses
• semantic, such as an operator applied to an incompatible operand
• logical, such as an infinitely recursive call

Often much of the error detection and recovery in a compiler is centered

around the syntax analysis phase. One reason for this is that many errors are
syntactic in nature or are exposed when the stream of tokens coming from the
lexical analyzer disobeys the grammatical rules defining the programming
language. Another is the precision of modern parsing methods; they can
detect the presence of Syntactic errors in programs very efficiently. Accurately
detecting the presence of semantic and logical errors at compile time is a
much more difficult task.
The error handler in a parser has simple-to-state goals:
• It should report the presence of errors clearly and accurately.
• It should recover from each error quickly enough to be able to detect
subsequent errors.
• It should not significantly slow down the processing of correct programs.
The effective realization of these goals presents difficult challenges.
Fortunately, common errors are simple ones and a relatively straightforward
error-handling mechanism often suffices. In some cases, however, an error
may have occurred long before the position at which its presence is detected
and the precise nature of the error may be very difficult to deduce. In difficult
cases, the error handler may have to guess what the programmer had in mind
when the program was written.

32
Several parsing methods, such as the LL and LR methods, detect an error as
soon as possible. More precisely, they have the viable-prefix property, meaning
they detect that an error has occurred as soon as they see a prefix of the input
that is not a prefix of any string in the language.

Error-Recovery Strategies
There are many different general strategies that a parser can employ to
recover from a syntactic error. Although no one strategy has proven itself to
be universally acceptable, a few methods have broad applicability. E.g.:
• panic mode
• phrase level
• error productions
• global correction

Panic-mode recovery: This is the simplest method to implement and can be

used by most parsing methods. On discovering an error, the parser discards
input symbols one at a time until one of a designated set of synchronizing
tokens is found. The synchronizing tokens are usually delimiters, such as
semicolon or end, whose role in the source program is clear. The compiler
designer must select the synchronizing tokens appropriate for the source
language. While panic-mode correction often skips a considerable amount of
input without checking it for additional errors. It has the advantage of
simplicity and, unlike some other methods. It is guaranteed not to go into an
infinite loop. In Situations where multiple errors in the same statement are
rare, this method may be quite adequate.

Phrase-Ievel recovery: On discovering an error, a parser may perform local

correction on the remaining input; that is, it may replace a prefix of the
remaining input by some string that allows the parser to continue. A typical
local correction would be to replace a comma by a semicolon, delete an
extraneous semicolon, or insert a missing semicolon. The choice of the local
correction is left to the compiler designer. We must be careful to choose
replacements that do not lead to infinite loops, as would be the case, for
example, if we always insert something on the input ahead of the current
input symbol. This type of replacement can correct any input string and has
been used in several error-reporting compilers. The method was first used
with top-down parsing. Its major drawback is the difficulty it has in coping
with situations in which the actual error has occurred before the point of
detection.

Error productions: If we have a good idea of the common errors that might
be encountered we can augment the grammar for the language at hand with
productions that generate the erroneous constructs. We then use the
grammar augmented by these error productions to construct a parser. If an
error production is used by the parser, we can generate appropriate error

33
diagnostics to indicate the erroneous construct that has been recognized in
the input.

Global correction: ideally, we would like a compiler to make a few changes

as possible in processing an incorrect input string. There are algorithms for
choosing a minimal sequence of changes to obtain a globally least-cost
correction. Given an incorrect input string and grammar G, these algorithms
will find a parse tree for a related string y, such that the number of insertions,
deletion, and changes of tokens required to transform x into y is as small as
possible. Unfortunately, these methods are in general too costly to implement
in terms of time and space, so these techniques are currently only of
theoretical interest.

Finally, note that a closest correct program may not be what the programmer
had in mind. Nevertheless, the notion of least-cost correction does provide a
yardstick for evaluating error-recovery techniques, and it has been used for
finding optimal replacement strings for phrase-level recovery.

Context-Free Grammars (CFG)

Grammars were introduced in the previous section to systematically describe
the syntax of programming language constructs like expressions and
statements. Using a syntactic variable stmt to denote statements and variable
expr to denote expressions, the production

stmt → if ( expr ) stmt else stmt

specifies the structure of this form of conditional statement. Other

productions then define precisely what an expr is and what else a stmt can
be.

The Formal Definition of a Context-Free Grammar

A context-free grammar (grammar for short) consists of terminals,
nonterminals, a start symbol, and productions.

1. Terminals are the basic symbols from which strings are formed. The term
"token name" is a synonym for '"terminal" and frequently we will use the word
"token" for terminal when it is clear that we are talking about just the token
name. We assume that the terminals are the first components of the tokens
output by the lexical analyzer. In the statement example above, the terminals
are the keywords if and else and the symbols "(" and ")".

2. Nonterminals are syntactic variables that denote sets of strings. In the

example above, stmt and expr are nonterminals. The sets of strings denoted

34
by nonterminals help define the language generated by the grammar.
Nonterminals impose a hierarchical structure on the language that is key to
syntax analysis and translation.

3. In a grammar, one nonterminal is distinguished as the start symbol, and

the set of strings it denotes is the language generated by the grammar.
Conventionally, the productions for the start symbol are listed first.

4. The productions of a grammar specify the manner in which the terminals

and nonterminals can be combined to form strings. Each production consists
of:
(a) A nonterminal called the head or left side of the production; this production
defines some of the strings denoted by the head.
(b) The symbol →. Sometimes ::= has been used in place of the arrow.
(c) A body or right side consisting of zero or more terminals and nonterminals.
The components of the body describe one way in which strings of the
nonterminal at the head can be constructed.

EXAMPLE
1. Consider the grammar below for arithmetic expressions, identify the
terminals, nonterminals and the start symbol in the grammar.

Solution
In this grammar, the terminal symbols are:

The nonterminal symbols are expression, term and factor, and

expression is the start symbol.

NOTATIONAL CONVENTIONS
To avoid always having to state that "these are the terminals," "these are the
nonterminals ," and so on, the following notational conventions for grammars
are used in most texts.

35
1. These symbols are used to represent terminals:
(a) Lowercase letters early in the alphabet, such as a, b, c.
(b) Operator symbols such as +, *, and so on.
(c) Punctuation symbols such as parentheses, comma, and so on.
(d) The digits 0,1,. . . ,9.
(e) Boldface strings such as id or if, each of which represents a single terminal
symbol.

2. These symbols are used to represent nonterminals:

(a) Uppercase letters early in the alphabet, such as A, B, C.
(b) The letter S, which, when it appears, is usually the start symbol.
(c) Lowercase, italic names such as expr or stmt.
(d) When discussing programming constructs, uppercase letters may be used
to represent nonterminals for the constructs. For example, nonterminals for
expressions, terms, and factors are often represented by E, T, and F,
respectively.

3. Uppercase letters late in the alphabet, such as X, Y, Z, represent grammar

symbols; that is, either nonterminals or terminals.

4. Lowercase letters late in the alphabet, chiefly u, v, . . . , x, represent (possibly

empty) strings of terminals.

5. Lowercase Greek letters, , β,  for example, represent (possibly empty)

strings of grammar symbols. Thus, a generic production can be written as A
→ , where A is the head and  the body.

6. A set of productions A with a common head A (call them A-productions),

may be written A → 1, A → 2, A → 3, ……….. A → k may be written A → 1
| 2 | 3 |……….. |k. Call 1 , 2 , 3 ,……….. k the alternatives for A.

7. Unless stated otherwise, the head of the first production is the start symbol.

Example: Using the above conventions, the grammar in the example above
can be rewritten concisely as
E → E+T | E-T | T
T → T*F | T/F | F
F → (E) | id
The notational conventions tell us that E, T, and F are nonterminals, with E
the start symbol. The remaining symbols are terminals.

36
DERIVATIONS
The construction of a parse tree can be made precise by taking a derivational
view, in which productions are treated as rewriting rules. Beginning with the
start symbol, each rewriting step replaces a nonterminal by the body of one
of its productions. This derivational view corresponds to the top-down
construction of a parse tree, but the precision afforded by derivations will be
especially helpful when bottom-up parsing is discussed. As we shall see,
bottom-up parsing is related to a class of derivations known as “rightmost"
derivations, in which the rightmost nonterminal is rewritten at each step.
For example, consider the following grammar, with a single nonterminal E,

E → E + E | E * E | -E | ( E ) | id

The production E | - E signifies that if E denotes an expression, then -E must

also denote an expression. The replacement of a single E by -E will be
described by writing
E→-E

which is read, “E derives -E." The production E → ( E ) can be applied to

replace any instance of E in any string of grammar symbols by (E), e.g., E * E
→) (E) * E or E * E → E * (E). We can take a single E and repeatedly apply
productions in any order to get a sequence of replacements. For example,
E → -E → -(E) → -(id)
We call such a sequence of replacements a derivation of -(id) from E. This
derivation provides a proof that the string -(id) is one particular instance of
an expression.
For a general definition of derivation, consider a nonterminal A in the middle
of a sequence of grammar symbols, as in AB where  and β are arbitrary
strings of grammar symbols. Suppose A →  is a production. Then, we write
AB → B. The symbol → means, “derives in one step." When a sequence of
derivation steps 1 → 2 → 3 → ……… n rewrites
1 to n, we say 1 derives n. Often, we wish to say, “derives in zero or more
∗
steps." For this purpose, we can use the symbol →. Thus,
∗
1.  → , for any string , and
∗ ∗ ∗
2. If  → β, and β → , then  → 
+
Likewise, → means, “derives in one or more steps."

∗
If S → , where S is the start symbol of a grammar G, we say that  is a
sentential form of G. Note that a sentential form may contain both terminals
and nonterminals, and may be empty.

A sentence of G is a sentential form with no nonterminals. The language

generated by a grammar is its set of sentences.

37
Thus, a string of terminals w is in L(G), the language generated by G, if and
∗
only if w is a sentence of G (or S → w).

A language that can be generated by a grammar is said to be a context-free

language. If two grammars generate the same language, the grammars are
said to be equivalent.

The string - (id + id) is a sentence of the above grammar because there is a
derivation
E →-E →-(E) → -(E + E) → -(id + E) → -(id + id)
Note that the strings -E, -(E), ……… -(id + id) are all sentential forms of this
grammar.
∗
We write E → -(id + id) to indicate that -(id + id) can be derived from E.

At each step in a derivation, there are two choices to be made. We need to

choose which nonterminal to replace, and having made this choice, we must
pick a production with that nonterminal as head. For example, the following
alternative derivation of -(id+id) differs from the derivation above in the last
two steps:
E →-E →-(E) → -(E + E) → -( E + id) → -(id + id)

Each nonterminal is replaced by the same body in the two derivations, but
the order of replacements is different. To understand how parsers work, we
shall consider derivations in which the nonterminal to be replaced at each
step is chosen as follows:
1. In leftmost derivations, the leftmost nonterminal in each sentential form
is always chosen. If  → β is a step in which the leftmost nonterminal in
 is replaced, we write  → 𝛽.
𝑙𝑚
2. In rightmost derivations, the rightmost nonterminal is always chosen;
we write  → 𝛽 in this case.
𝑟𝑚
Therefore, the first derivation above, which is leftmost, can be rewritten as
E → -E →-(E) → -(E + E) → -(id + E) → -(id + id)
𝑙𝑚 𝑙𝑚 𝑙𝑚 𝑙𝑚

If S → , then we say that  is a left-sentential form of the grammar at hand.

𝑙𝑚
Analogous definitions hold for rightmost derivations. Rightmost derivations
are sometimes called canonical derivations.

Parse Trees and Derivations

A parse tree is a graphical representation of a derivation that filters out the
order in which productions are applied to replace nonterminals. Each interior
node of a parse tree represents the application of a production. The interior

38
node is labelled with the nonterminal A in the head of the production; the
children of the node are labelled, from left to right, by the symbols in the body
of the production by which this A was replaced during the derivation.

For example, the parse tree for -(id + id) resulting from the above derivations
is shown below.

Note that the leaves of a parse tree are labelled by nonterminals or terminals
and, read from left to right, constitute a sentential form, called the yield or
frontier of the tree.

To see the relationship between derivations and parse trees, consider any
derivation 1 → 2 → 3 → ……… n, where 1 is a single nonterminal A. For
each sentential form i in the derivation, we can construct a parse tree whose
yield is i. The process is an induction on i.

Note that a parse tree ignores variations in the order in which symbols in
sentential forms are replaced, and there is a many-to-one relationship
between derivations and parse trees. For example, both the leftmost and
rightmost derivations above are associated with the same parse tree. The
figure below shows the sequence of parse trees for the leftmost derivation
above.

39
In what follows, we shall frequently parse by producing a leftmost or a
rightmost derivation, since there is a one-to-one relationship between parse
trees and either leftmost or rightmost derivations. Both leftmost and
rightmost derivations pick a particular order for replacing symbols in
sentential forms, so they too filter out variations in the order. It is not hard to
show that every parse tree has associated with it a unique leftmost and a
unique rightmost derivation.

Ambiguity
A grammar that produces more than one parse tree for some sentence is said
to be ambiguous. Put another way, an ambiguous grammar produces more
than one leftmost derivation or more than one rightmost derivation for the
same sentence.

Example 4.11: The arithmetic expression grammar given in the sections

above permits two distinct leftmost derivations for the sentence id + id * id,
as shown below.

Likewise, the corresponding parse trees are shown below.

Note that the parse tree in (a) above reflects the commonly assumed
precedence of + and *, while the tree of (b) does not. That is, it is customary
to treat operator * as having higher precedence than +, corresponding to the
fact that we would normally evaluate an expression like a + b * c as a + (b *
c), rather than as (a + b) * c.

40
For most parsers, it is desirable that the grammar be made unambiguous, for
if it is not, we cannot uniquely determine which parse tree to select for a
sentence. In other cases, it is convenient to use carefully chosen ambiguous
grammars, together with disambiguating rules that “throw away" undesirable
parse trees, leaving only one tree for each sentence.

Eliminating Ambiguity
Sometimes an ambiguous grammar can be rewritten to eliminate the
ambiguity. As an example, we shall eliminate the ambiguity from the following
“dangling-else" grammar:
stmt → if expr then stmt
| If expr then stmt else stmt
| other
Here “other" stands for any other statement.
According to this grammar, the compound conditional statement
if E1 then S1 else if E2 then S2 else S3
below has the parse tree shown below.

Also, note that the above grammar is ambiguous since the string
if E1 then if E2 then S1 else S2
has the two parse trees below.

41
In all programming languages with conditional statements of this form, the
first parse tree is preferred. The general rule is, “Match each else with the
closest unmatched then." This disambiguating rule can theoretically be
incorporated directly into a grammar, but in practice it is rarely built into the
productions.

Example
We can rewrite the dangling-else grammar above as the following
unambiguous grammar.

Figure: Unambiguous grammar for if-then-else statements

The idea is that a statement appearing between a then and an else must be
“matched"; that is, the interior statement must not end with an unmatched
or open then. A matched statement is either an if-then-else statement
containing no open statements or it is any other kind of unconditional
statement. Thus, we may use the unambiguous grammar above. This
grammar generates the same strings as the dangling-else grammar, but it
allows only one parsing for string if E1 then if E2 then S1 else S2; namely, the
one that associates each else with the closest previous unmatched then.

Verifying the Language Generated by a Grammar

Although compiler designers rarely do so for a complete programming-
language grammar, it is useful to be able to reason that a given set of
productions generates a particular language. Troublesome constructs can be
studied by writing a concise, abstract grammar and studying the language
that it generates. A proof that a grammar G generates a language L has two
parts: show that every string generated by G is in L, and conversely that every
string in L can indeed be generated by G.

Exercise
Consider the context-free grammar: S → S S + | S S * | a and the string aa
+ a*.
a) Give a leftmost derivation for the string.
b) Give a rightmost derivation for the string.
c) Give a parse tree for the string.
d) Is the grammar ambiguous or unambiguous? Justify your answer.
e) Describe the language generated by this grammar.

42
Writing a Grammar
Grammars are capable of describing most, but not all, of the syntax of
programming languages. For instance, the requirement that identifiers be
declared before they are used, cannot be described by a context-free grammar.
Therefore, the sequences of tokens accepted by a parser form a superset of
the programming language; subsequent phases of the compiler must analyze
the output of the parser to ensure compliance with rules that are not checked
by the parser.

Lexical Versus Syntactic Analysis

Everything that can be described by a regular expression can also be
described by a grammar. We may therefore reasonably
ask: “Why use regular expressions to define the lexical syntax of a language?"
There are several reasons.
1. Separating the syntactic structure of a language into lexical and non-lexical
parts provides a convenient way of modularizing the front end of a compiler
into two manageable-sized components.
2. The lexical rules of a language are frequently quite simple, and to describe
them we do not need a notation as powerful as grammars.
3. Regular expressions generally provide a more concise and easier-to-
understand notation for tokens than grammars.
4. More efficient lexical analyzers can be constructed automatically from
regular expressions than from arbitrary grammars.

There are no firm guidelines as to what to put into the lexical rules, as opposed
to the syntactic rules. Regular expressions are most useful for describing the
structure of constructs such as identifiers, constants, keywords, and white
space. Grammars, on the other hand, are most useful for describing nested
structures such as balanced parentheses, matching begin-end's,
corresponding if-then-else's, and so on. These nested structures cannot be
described by regular expressions.

43
BASIC PARSING TECHNIQUES
The previous section showed how a context-free grammar can be used to
define the syntax of a programming language. This section shows how to
check whether an input string is a sentence of a given grammar and how to
construct, if desired, a parse tree for the string. As every compiler performs
some type of syntax analysis, usually after lexical analysis, the input to a
parser is typically a sequence of tokens. The output of the parser can be of
many different forms. This note assumes for simplicity that the output is some
representation of the parse tree.

This section discusses two common forms of parsers; operator precedence

and recursive descent. Operator precedence is especially suitable for parsing
expressions, since it can use information about the precedence and
associativity of operators to guide the parsing. Recursive descent uses a
collection of mutually recursive routines to perform the syntax analysis. The
great bulk of compilers in existence in the early 1970's use one or both of
these methods. A common situation is for operator precedence to be used for
expressions and recursive descent for the rest of the language.

The primary advantage of these methods is that they are easy to implement
by hand. But there are some drawbacks as well. Operator precedence has the
curious property that if one is not careful, one can recognize inputs that are
not in the language of the underlying grammar. Likewise, recursive descent,
particularly when augmented with backtracking, can produce further
unexpected results.

Fortunately, there are two newer methods that are more general than the older
methods and more firmly grounded in grammar theory. Moreover, with the
proper tools (parser generators) the newer methods are easier to use than the
more classical approaches. The first of these methods, LL parsing, will be
mentioned in this section, as it is really a table-based variant of recursive
descent. The second method, LR, is the subject of the next section.

Parsers
A parser for grammar G is a program that takes as input a string w and
produces as output either a parse tree for w, if w is a sentence of G or an
error message indicating that w is not a sentence of G. Often the parse tree is
produced in only a figurative sense, in reality, the parse tree exists only as a
sequence of actions made by stepping through the tree construction process.
This section discusses the operation of two basic types of parsers for context-
free-free grammars: bottom-up and top-down. As indicated by their names,
bottom-up parsers build parse trees from the bottom (leaves) to the top (root),
while top-down parsers start with the root and work down to the lcaves. In
both cases, the input to the parser is being scanned from left to right, one
symbol at a time.

44
The bottom-up parsing method discussed here is called "shift-reduce" parsing
because it consists of shifting input symbols onto a stack until the right side
of a production appears on top of the stack. The right side may then be
replaced by (reduced to) the symbol on the left side of the production, and the
process repeated.
Unfortunately, if A → XYZ is a production, then not every time that XYZ is on
top of the stack is it correct to reduce XYZ to A; there may be occasions where
it is necessary to continue to shift input symbols on top of XYZ.
Designing an algorithm from a grammar so that shift-reduce decisions are
made properly is the fundamental problem of bottom-up parser construction.
In the next section, we show how to construct one kind of shift-reduce parser
called an operator-precedence parser. A more general type of shift-reduce
parser will also be discussed later called LR parsers. The top-down parsing
method we discuss is called recursive descent parsing. Also, how to construct
a tabularized form of recursive descent parser called a predictive parser will
be shown. A discussion of LL parsers, a special kind of predictive parser will
also be presented.

Representation of a Parse Tree

The output of a parser is treated here as a representation of a parse tree for
the input, if the input is syntactically well-formed. There are two basic types
of representations we shall consider; implicit and explicit. The sequence of
productions used in some derivation is an example of an implicit
representation. A linked list structure for the parse tree is an explicit
representation.

Consider the grammar below.

(1) S → iCtS
(2) S → iCtSeS
(3) S → a
(4) C → b

Here, i, t, e stands for if, then and else, C and S stand for “condition” and
“statement”. A leftmost derivation for the sentence w = i b t i b t a e a is shown
below.
S→ iCtS
𝑙𝑚
→ ibtS
𝑙𝑚
→ ibtiCtSeS
𝑙𝑚
→ ibtibtSeS
𝑙𝑚
→ ibtiCtaeS
𝑙𝑚
→ ibtiCtaea
𝑙𝑚

45
The corresponding parse tree is also shown below.

Shift-Reduce Parsing
This parsing method is bottom-up because it attempts to construct a parse
tree for an input string beginning at the leaves (the bottom) and working up
towards the root (the top). We can think of this process as one of reducing a
string w to the start symbol of a grammar. At each step, a string matching
the right side of a production is replaced by the symbol on the left.
For example., consider the grammar
S → aAcBe
A → Ab | b
B→d
and the string abbcde. We want to reduce this string to S. We scan abbcde
looking for substrings that match the right side of some production. The
substrings b and d qualify. Let us choose the leftmost b and replace with A,
the left side of the production A → b. We obtain the string aAbcde. We now
find that Ab, b, and d each match the right side of some production. Suppose
this time we choose to replace the substring Ab by A, the left-side of the
production A → Ab. We now obtain aAcde. Then replacing d by the left side of
the production B →d, we obtain aAcBe. We can go on and replace the entire
string S.
Each replacement of the right side of a production by the left side in the
process above is called a reduction. Thus, by a sequence of four reductions we
were able to reduce abbcde to S. These reductions, in fact figure out a
rightmost derivation in reverse.
Informally, if we consider a substring which is the right side of a production,
such replacement of that substring by the production on the left side leads
eventually to a reduction to the start symbol, by the reverse of a rightmost
derivation called a "handle." The process of bottom-up parsing may be viewed
as that of finding and reducing handles.

Handles
A handle of a right-sentential form  is a production A → β and a position of 
where the string β may be found and replaced by A to produce a previous
right-sentential form in a rightmost derivation of . That is,

46
If S → 𝐴𝑤 → 𝛽𝑤 , then A → β in the position following  is a handle of 𝛽𝑤.
𝑟𝑚 𝑟𝑚
The string w to the right of the handle contains only terminal symbols.
In the example above, abbcde is a right-sentential form whose handle is A →
β at position 2. Likewise, aAbcde is a right-sentential form whose handle is A
→ Ab at position 2.
Sometimes we shall say “the substring β is a handle of βw” if the position of
β and the production A → β we have in mind are clear. If a grammar is
unambiguous, then every right-sentential form of the grammar has exactly
one handle.

Consider the following grammar

(1) E → E+E
(2) E → E * E
(3) E → (E)
(4) E → id

Consider the rightmost derivation

E→ E+E
𝑟𝑚
→ E+E*E
𝑟𝑚
→ E + E * id3
𝑟𝑚
→ E + id2 * id3
𝑟𝑚
→ id1 + id2 * id3
𝑟𝑚

Consider the grammar above and the example that followed and the input
string idl + id2 + id3. The following sequence of reductions reduces idl + id2 +
id3 to the start symbol E.

Observe that the sequence of right-sentential forms in this example is just the
reverse of the sequence in the rightmost derivation in the upper example.
Again, recall that there is another rightmost derivation in which idl + id2
comes from a single E, and this rightmost derivation implies a different
sequence of handles.

47
Stack Implementation of Shift-Reduce Parsing
There are two problems that must be solved if we are to automate parsing by
handle pruning. The first is how to locate a handle in a right-sentential form
and the second is what production to choose in case there is more than one
production with the same right side. Before we get to these questions, let us
first consider the type of data structures to use in a handle-pruning parser. A
convenient way to implement a shift-reduce parser is to use a stack and an
input buffer. We shall use $ to mark the bottom of the stack and the right
end of the input.

Stack Input
$ w$

The parser operates by shifting zero or more input symbols onto the stack
until a handle β is on top of the stack. The parser then reduces β to the left
side of the appropriate production. The parser repeats this cycle until it has
detected an error or until the stack contains the start symbol and the input
is empty.
Stack Input
$S $

In this configuration, the parser halts and announces successful completion

of parsing.
While the primary operations of the parser are shift and reduce, there are
actually four possible actions a shift-reduce parser can make: (1) shift, (2)
reduce, (3) accept, and (4) error.
1. In a shift action, the next input symbol is shifted to the top of the stack.
2. In a reduce action, the parser knows the right end of the handle is at the
top of the stack. It must then locate the left end of the handle within the stack
and decide with what nonterminal to replace the handle.
3. In an accept action, the parser announces the successful completion of
parsing.
4. In an error action, the parser discovers that a syntax error has occurred
and calls an error recovery routine.

There is an important fact that justifies the use of a stack in shift-reduce

parsing: the handle will always eventually appear on top of the stack, never
inside. This fact becomes obvious when we consider the possible forms of two
successive steps in any rightmost derivation.

48
Example:
Let us step through the actions a shift-reduce parser might make in parsing
the input string idl + id2 + id3; according to grarmmar
(1) E → E+E
(2) E → E * E
(3) E → (E)
(4) E → id
using the derivation that followed the grammar above.

The sequence is shown in the figure below.

Note that because the grammar used has two rightmost derivations for this
Input, there is another sequence of steps a shift-reduce parser could take.

49
OPERATOR PRECEDENCE PARSING TECHNIQUE
For a certain small class of grammars, we can easily construct efficient shift-
reduce parsers by hand. These grammars have the property (among other
essential requirements) that no production right side is empty or has two
adjacent nonterminals. A grammar with the latter property is called an
operator grammar.

Example: Consider the following grammar for expressions

E → EAE | (E) |-E| id
A →+|-|*|/|^

This grammar is not an operator grammar, because the right side EAE has
two (in fact three) consecutive nonterminals. However, if we substitute for A
using each of its alternates, we obtain the following operator grammar:
E → E+E| E-E| E*E| E/E| E^E| (E) | -E| id

We shall now describe an easy-to-implement parsing technique called

operator-precedence parsing. Historically, the operator-precedence technique
was first described as a manipulation of tokens without any reference to an
underlying grammar. Once we finish building an operator-precedence parser
from a grammar, we may effectively ignore the grammar using the
nonterminals on the stack only as placeholders for the nodes of the parse tree
being constructed in the bottom-up fashion just described.
As a general parsing technique, operator-precedence parsing has some
disadvantages. For example,
(1) it is hard to handle tokens like the minus sign which has two different
precedences (depending on whether it is unary or binary).
(2) Worse, since the relationship between the grammar for the language
being parsed and the operator-precedence parser itself is tenuous, one
cannot always be sure the parser accepts exactly the desired language.
(3) Finally, only a small class of grammars can be parsed using operator
precedence techniques.

Nevertheless, because of its simplicity, numerous compilers using operator-

precedence parsing techniques for expressions have been successfully built.
Often these parsers use recursive descent, described in the next section, for
statements and higher-level constructs. Operator-precedence parsers have
even been built for entire languages. SNOBOL, being virtually all operators, is
an example of a language for which operator precedence works well.

In operator-precedence parsing, we use three disjoint precedence relations,

<., =. and .>, between certain pairs of terminals. These precedence relations
guide the selection of handles. If a <. b, we say a “yields precedence to” b; if a
= b, we say a ''has the same precedence as” b; if a > b, we say a “takes
. .

precedence over” b.

50
Please note that while these relations may appear similar to the arithmetic
relations “less than”, "equal to” and “greater than”, the precedence relations
have quite different properties. For example, we could have a <. b and a .> b
for the same language, or we might have none of a <. b, a =. b, and a .> b
holding for some terminals a and b.

There are two common ways of determining what precedence should hold
between a pair of terminals. The first method presented here is intuitive and
is based on the traditional notions of associativity and precedence of
operators. For example, if * is to have higher precedence than +, we make + <.
* and * .> +. This approach will be seen to resolve the ambiguities of the
expression grammar discussed in the above section and to enable us to write
an operator precedence parser for it (although the unary minus sign causes
problems).

The second method of selecting operator-precedence relations is to first

construct an unambiguous grammar for the language, a grammar which
reflects the correct associativity and precedence in its parse trees. This task
is not difficult for expressions. For the other common source of ambiguity with
the dangling else, the grammar, which uses the nonterminal restricted-
statement to generate statements other than the if …… then statement, is a
useful model. Having obtained an unambiguous grammar, there is a
mechanical method for constructing operator-precedence relations from it.
These relations may not be disjoint, and they may parse a language other
than that generated by the grammer, but with the standard sorts of arithmetic
expressions, few problems are encountered in practice.

Operator-Precedence Relations
The intention of the precedence relations is to delimit the handle of a
sentential form, with <. marking the left end, =. appearing in the middle of
the handle (if any) and .> marking the right end. To be more precise, suppose
we have a right-sentential form of an operator grammar, the fact that no
adjacent nonterminals appear on the right sides of productions implies that
no right-sentential form will have two adjacent nonterminals either. Thus, we
may write the right-sentential form as a1β1, ……………………., amβn, where
each β, is either  (the empty string) or a single nonterminal, and each a, is a
single terminal. Suppose that between ai and ai+1, exactly one of the relations
<., =. and .> holds. Further, $ marks each end of the string, and we define $
<. b and b .> $ for all terminals b.

Now suppose we remove the nonterminals from the string and place the
correct relation, <., =. , or .> between each pair of terminals and between the
endmost terminals and the $'s marking the ends of the string. For example,

51
suppose we initially have the right-sentential form id + id * id and the
precedence relations are given below,

Id + * $
id .> .> .>

+ <. .> <. .>

* <. .> .> .>

$ <. <. <.

then the string with the precedence relations inserted is:

$<.id.>+<.id.>*<.id.>$
For example, <. is inserted between $ and id since <. is the entry in row $ and
column id. Now, the handle can be found by the following process.

1. Scan the string from the left end until the leftmost .> is encountered. In
the example above, this occurs between the first id and +.
2. Then scan backwards (to the left) over any = 's until a < is
. .

encountered. In the above example, we scan backwards to $.

3. The handle contains everything to the left of the first .> and to the right
of the <. encountered in step (2), including any intervening or
surrounding nonterminals. The inclusion of surrounding nonterminals
is necessary so that two adjacent nonterminals do not appear in a right
sentential form. In the example above, the handle is the first id.

If we are dealing with the grammar,

E → E+E| E-E| E*E| E/E| E^E| (E) | -E| id

we then reduce id to E. At this point we have the right-sentential form E+id*id.

After reducing the two-remaining id's to E by the same steps, we obtain the
right-sentential for E+E*E. Consider now the string $+*$ obtained by deleting
the nonterminals. Inserting the precedence relations, we get
$<.+<.*.>$
indicating that the left end of the handle lies between + and * and the right
end between * and $. These precedence relations indicate that, in the right-
sentential form E+E*E, the handle is E*E. Note how the E's surrounding the *
become part of the handle.

Since the nonterminals do not influence the parse, we need not worry about
distinguishing among them. A single marker “nonterminal" can be kept on the
stack of a shift-reduce parser to indicate placeholders for nodes of the parse
tree being constructed or to indicate a variety of possible translations.

It may appear from the discussion above that the entire right-sentential form
must be scanned at each step to find the handle. Such is not the case if the
precedence relations are used to guide the actions of a shift-reduce parser. If
52
the precedence relation <. or =. holds between the topmost terminal symbol
on the stack and the next input symbol, the parser shifts. The parser has not
yet found the right end of the handle. If the relation .> holds, a reduction is
called for. Now the parser has found the right end of the handle, and the
precedence relations can be used to find the left-end of the handle in the
stack. If no precedence relation holds between a pair of terminals (indicated
by a blank entry in the table above), then a syntactic error has been detected
and an error recovery routine is invoked.

Operator-Precedence Relations from Associativity and Precedence

For a language of arithmetic expressions we can use the following heuristic to
produce a useful set of precedence relations. Note that grammar
E → E+E| E-E| E*E| E/E| E^E| (E) | -E| id
is ambiguous, and right-sentential forms could have many handles. Our rules
are designed to select the proper handles to reflect a given set of associativity
and precedence rules for binary operators.

Rules
1. If operator 1, has higher precedence than operator 2, make 1.> 2 and
2 <. 1. For example, if * has higher precedence than +, make * .> + and
+ <. *. These relations ensure that, in an expression of the form
E+E*E+E, the central E*E is the handle that will be reduced first.

2. If 1 and 2 are operators of equal precedence (they may in fact be the

same operator), then make 1 .> 2, and 2 .> 1, if the operators are left-
associative, or make 1 <. 2 and 2 <. 1, if they are right-associative. For
example, if + and - are left-associative, then make + .> +, + .> -, - .> -
and - .> +. If ^ is right associative, then ^ <. ^. These relations ensure
that E-E+E will have handle E-E selected and E^E^E will have the
last E^E selected.

3. Make  <. id, id .> ,  <. (, ( <. , ) .> ,  .> ),  .> $ and $ <.  for all
operators . Also, the following rules hold.

( =. ) $ <. ( $ <. id
( <. ( id .> $ ) .> $
( <. id id .> ) ) .> )

These rules ensure that id will be reduced to E wherever found and (E) will be
reduced to E wherever found. Also, $ will serve as both left and right
endmarker, causing handles to be found between $'s wherever possible.

Using the above rules, the operator precedence relations for the grammar
E → E+E| E-E| E*E| E/E| E^E| (E) | -E| id
is as follows.
53
Assuming,
1. ^ is of highest precedence and right-associative,
2. * and / are of next highest precedence and left-associative, and
3. + and - are of lowest precedence and left-associative,

+ - * / ^ id ( ) $
+ .> .> <. <. <. <. <. .> .>

- .> .> <. <. <. <. <. .> .>

* .> .> .> .> <. <. <. .> .>

/ .> .> .> .> <. <. <. .> .>

^ .> .> .> .> <. <. <. .> .>

id .> .> .> .> .> .> .>

( <. <. <. <. <. <. <. .

=
) .> .> .> .> .> .> .>

$ <. <. <. <. <. <. <.

Figure: Operation Precedence Relations

Note that in the table, blanks denote error entries. Also there could be some
problems associated with the treatment of the unary minus.

Exercise
Using the grammar for arithmetic expressions below,
E → E+E| E-E| E*E| E/E| E^E| (E) | -E| id
show the processing of the input id * (id ^ id) – id/id.

Handling Unary Operators

If we have a unary operator such as (logical negation), which is not also a
binary operator, we can easily incorporate it into the above scheme in creating
operator-precedence relations. Supposing - to be a unary operator, we make
 <. - for any operator , whether unary or binary and make - .>  if - has
higher precedence than  and - <.  if not.

One commonly used solution to the problem of operator precedence parsers

is to ignore the nonterminals as far as parsing is concerned. We assume that
reductions by single productions could be made as needed. Then we keep only
terminals on the stack and make only those reductions that do not involve
single productions. The disadvantage of this method is that we lose the power
the non-terminals have to warn us that pieces of the input do not fit together
properly, and in fact, we, may wind up accepting an input that was not a
sentence of the operator-precedence grammar. However, any sentence will be
parsed by this method. In the next sections, we shall discuss a shift-reduce
parsing method that parses all sentences and only sentences.

54
TOP-DOWN PARSING
In this section, we first discuss a general form of top-down parsing that may
involve backtracking, that is, making repeated scans of the input. After that,
we discuss a special case, called recursive-descent parsing, which eliminates
the need for backtracking over the input.

Top-down parsing can be viewed as an attempt to find a leftmost derivation

for an input string. Equivalently, it can be viewed as attempting to construct
a parse tree for the input starting from the root and creating the nodes of the
parse tree in preorder. For example, consider the grammar
S → cAd
A → ab | a
and the input w = cad.

To construct a parse tree for this sentence top-down, we initially create a tree
consisting of a single node labelled S. An input pointer points to c, the first
symbol of w. We then use the first production for S to expand
the tree and obtain the tree below.

The leftmost leaf, labelled c, matches the first symbol of w. So we now advance
the input pointer to a, the second symbol of w, and consider the next leaf,
labelled A. We can then expand A using the first alternate for A to obtain the
tree below.

We now have a match for the second input symbol.

We now consider d, the third input symbol, and the next leaf, labelled b. Since
b does not match d, we report failure and go back to A to see whether there
is another alternate for A that we have not tried but which might produce a
match. In going back to A we must reset the input pointer to position 2, the
position it had when we first came to A. We now try the second alternate for
A to obtain the tree below.

55
The leaf a matches the second symbol of w and the leaf d matches the third
symbol. Since we have now produced a parse tree for w, we halt and announce
successful completion of parsing.

An easy way to implement such a parser is to create a procedure for each

nonterminal. In the case of this simple grammar, generating only two Strings,
there is no need for recursion among the procedures, but in practical cases,
where grammars derive an infinite number of strings, recursive procedures
are essential.

In many compiler-writing systems based on top-down parsing with backtrack,

an interpreter is used to simulate a collection of recursive procedures. In later
section, we shall discuss predictive parsers, which, in effect, enable us to
interpret recursive procedures having no backtrack.

Problems of Top-Down Parsers

i. Left recursion:
A grammar is left recursive if it has a nonterminal A such that there
+
is a derivation A → A for some string . Top-down parsing methods
cannot handle left-recursive grammars as they can cause a top-
down parser to go into an infinite loop, so a transformation that
eliminates left recursion is needed. That is, if we try to expand A, we
may eventually find ourselves again trying to expand A without
consuming any input. This cycling will surely occur on an erroneous
input string, and it may also occur on legal inputs, depending on the
order in which the alternates for A are tried. Therefore, to use top-
down parsing we must eliminate all left recursion from the grammar.

ii. Backtracking: if we make a series of erroneous expansions and

subsequently discover a mismatch, we may have to undo the
semantic effects of making these erroneous expansions. For
example, we may have to remove an entry from the symbol table.
Since undoing semantic actions require a substantial overhead, it is
reasonable to consider top-down parsing with no backtracking. The
recursive descent and predictive parsers are such types. They

56
 compensate somewhat for the lack of backtracking by using the next
input symbol to guide the parsing actions.

iii. The order in which the alternates are tried can affect the language
accepted.

iv. When failure is reported, we have very little idea where the error
actually occurred. In the form given here, a top-down parser with
backtrack simply returns failure no matter what the error is.

Elimination of Left Recursion

A grammar is left recursive if it has a nonterminal A such that there is a
+
derivation A → A for some string. Top-down parsing methods cannot handle
left-recursive grammars, so a transformation is needed to eliminate left
recursion.
If we have a left-recursive pair of productions A → A | β where β does not
begin with an A, we can eliminate the left recursion by replacing the pair of
productions with
A → βA
A →  A | 

without changing the strings derivable from A. This rule by itself suffices for
many grammars.

Example
Consider the following grammar
E→E+T|T
T→T*F|F
F → (E) | id
Eliminating the immediate left recursion, we obtain,

E → TE
E → +T E | 
T → FT
T → * F T | 
F → (E) | id

In general, to eliminate immediate left recursion among all A productions, we

first group the A productions as
A → A1 | A2 |………………… Am | β1 | β1 | ……… |βn

Where no β begins with an A. Then we replace the A-productions by

57
 A → β1A | β2A | …………… |βnA
A → 1A |2A | …………… |mA |

The nonterminal A generates the same strings as before but is no longer left
recursive. This procedure eliminates all left recursions from the A and A
productions (provided no i is ), but it does not eliminate left recursion
involving derivations of two or more steps.
For example, consider the grammar below
S → Aa | b
A → Ac |Sd | 
The nonterminal S is left recursive because S → Aa → Sda, but it is not
immediately left recursive.

The algorithm below systematically eliminates left recursion from a grammar.

It is guaranteed to work if the grammar has no cycles (derivations of the form
A ) + A) or -productions (productions of the form A ! ). Cycles can be eliminated
systematically from a grammar, as can -productions.

Figure: Algorithm to eliminate left-recursion from a grammar

Example
Let us apply the Algorithm above to the grammar above it. Technically, the
algorithm is not guaranteed to work, because of the -production, but in this
case, the production A →  turns out to be harmless.
We order the nonterminals S, A. There is no immediate left recursion among
the S-productions, so nothing happens during the outer loop for i = 1. For i =
2, we substitute for S in A → Sd to obtain the following A-productions.

58
 A → Ac |Aad |bd | 
Eliminating the immediate left recursion among these A-productions yields
the following grammar.
S →A a | b
A → b d A
A → c A | a d A | 

Recursive-Descent Parsing
In many practical cases, a top-down parser needs no backtrack. In order that
no backtracking be required, we must know, given the current input symbol
a and the nonterminal A to be expanded, which one of the alternates of a
production A → 1 |2 | …………… |n is the unique alternate that derives a
string beginning with a. That is, the proper alternate is detectable by looking
at only the first symbol it derives. For example, control structures with their
distinguishing keywords, are detectable in this way. Suppose we have
productions,
Statement → if condition then statement else statement
| while condition do statement
| begin statement-list end

Then the keywords if, while, and begin tell us which alternate is the only one
that could possibly succeed if we are to find a statement. One nuance
concerns the empty string. If one alternate for A is , and none of the other
alternates derives a string beginning with a, then on input a, we may expand
A by A → , that is, we succeed without further ado in recognizing an A. A
parser that uses a set of recursive procedures to recognize its input with
no backtracking is called a recursive-descent parser. The recursive
procedures can be quite easy to write and fairly efficient if written in a
language that implements procedure calls efficiently.

To avoid the necessity of a recursive language, we shall also consider a tabular

implementation of recursive descent, called predictive parsing, where a stack
is maintained by the parser, rather than by the language in which the parser
is written.

Left-Factoring
Often the grammar one writes down is not suitable for recursive-descent
parsing, even if there is no left-recursion. For example, if we have the
productions
Statement → if condition then statement else statement
| if condition then statement

59
we could not, on seeing the input symbol if., tell which to choose to expand
statement. A useful method for manipulating grammars into a form suitable
for recursive-descent parsing is left-factoring, the process of factoring out the
common prefixes of alternates.

If A → β| are two A-productions, and the input begins with a nonempty
string derived from , we do not know whether to expand A to β or to . We
may defer the decision by expanding A to A. Then, after seeing the input
derived from a, we expand A to β or to . That is, left-factored, the original
productions become
A → A
A → β | 

Example
Consider again the grammar below, which abstracts the dangling else
problem. Left-factor this grammar.

Solution
S → iCtSS | a
S → eS | 
C→b

Thus, we may expand S to iCtSS on input i, and wait until iCtS has been
seen to decide whether to expand S to eS or to .

PREDICTIVE PARSERS
A predictive parser is an efficient way of implementing recursive-descent
parsing by handling the stack of activation records explicitly. We can picture
a predictive parser as we have in the Figure below.

60
The predictive parser has an input, a stack, a parsing table, and an output.
The input contains the string to be parsed, followed by $, the right endmarker.
The stack contains a sequence of grammar symbols, preceded by $, the
bottom-of-stack marker. Initially, the stack contains the start symbol of the
grammar preceded by $. The parsing table is a two-dimensional array M[A, al,
where A is a nonterminal, and a is a terminal or the symbol $. The parser is
controlled by a program that behaves as follows.

The program determines X, the symbol on top of the stack, and a, the current
input symbol. These two symbols determine the action of the parser.
There are three possibilities.

1. If X = a = $, the parser halts and announces the successful completion

of parsing.

2. If X = a ≠ $, the parser pops X off the stack and advances the input
pointer to the next input symbol.

3. If X is a nonterminal, the program consults entry M[X, a] of the parsing

table M. This entry will be either an X-production of the grammar or an
error entry. If M[X, a] = [X → UVW], the parser replaces X on top of the
stack with WVU (with U on top). As output, the grammar does the
semantic action associated with this production, which, for the time
being, we shall assume is just printing the production used.

4. If M[X, a] = error, the parser calls an error recovery routine.

We shall describe the behaviour of the parser in terms of its configurations,

which gave the stack contents and the remaining input. Initially, the parser
is in configuration shown below.

Stack Input
$S w$

where S is the start symbol of the grammar and w is the string to be parsed.
The program that utilizes the predictive parsing table to produce a parse is
shown in the algorithm below.

61
Example
Consider grammar the grammar below
E → TE
E → +T E | 
T → FT
T → * F T | 
F → (E) | id

A predictive parsing table for this grammar is shown below.

Note from the table that blanks are error entries. Also, note that we have not
yet indicated how these entries could be selected. but we shall do so shortly.

With input id + id * id, the predictive parser would make the sequence of
moves below.

62
If we observe the actions of this parser carefully, we see that it is tracing out
a leftmost derivation for the input. The productions’ outputs are those of a
leftmost derivation. The input symbols that have already been scanned,
followed by the grammar symbols on the stack (from top to bottom), make up
the left-sentential forms in the derivation.

CONSTRUCTION OF THE PREDICTIVE PARSING TABLE

Now let us consider how to fill in the entries of a predictive parsing table. We
need two functions associated with a grammar G. These functions are FIRST
and FOLLOW.

FIRST and FOLLOW

The construction of both top-down and bottom-up parsers is aided by two
functions, FIRST and FOLLOW, associated with a grammar G. During top-
down parsing, FIRST and FOLLOW allow us to choose which production to
apply, based on the next input symbol. During panic-mode error recovery,
sets of tokens produced by FOLLOW can be used as synchronizing tokens.

Define FIRST(), where  is any string of grammar symbols, to be the set of

∗
terminals that begin strings derived from . If  → , then  is also in FIRST
∗
(). For example, in the figure below, A → c, so c is in FIRST (A).

63
For a preview of how FIRST can be used during predictive parsing, consider
two A-productions A →  | β, where FIRST() and FIRST(β ) are disjoint sets.
We can then choose between these A-productions by looking at the next input
symbol a, since a can be in at most one of FIRST() and FIRST(β), not both.
For instance, if a is in FIRST(β), then choose the production A → β.

Define FOLLOW(A), for nonterminal A, to be the set of terminals a that can

appear immediately to the right of A in some sentential form; that is, the set
∗
of terminals a such that there exists a derivation of the form S → Aaβ, for
some  and β. Note that there may have been symbols between A and a, at
some time during the derivation, but if so, they derived  and disappeared. In
addition, if A can be the rightmost symbol in some sentential form, then $ is
in FOLLOW(A); recall that $ is a special “endmarker" symbol that is assumed
not to be a symbol of any grammar.

Computation of the FIRST set

To compute FIRST(X) for all grammar symbols X, apply the following rules
until no more terminals or  can be added to any FIRST set.

1. If X is a terminal, then FIRST(X) = {X}.

2. If X is a nonterminal and X → Y1Y2 ……………. Yk is a production for

some k ≥ 1, then place a in FIRST(X) if for some i, a is in FIRST(Yi), and
∗
 is in all of FIRST(Y1), ………….. FIRST(Yi-1); that is, Y1 ………. Yi-1 →  .
If  is in FIRST(Yj) for all j = 1, 2, …………, k, then add  to FIRST(X).

For example, everything in FIRST(Y1) is surely in FIRST(X). If Y1 does

∗
not derive , then we add nothing more to FIRST(X), but if Y1 → , then
we add FIRST(Y2), and so on.

3. If X →  is a production, then add  to FIRST(X).

64
Now, we can compute FIRST for any string X1X2 …………. Xn as follows. Add
to FIRST(X1X2 …………. Xn) all non- symbols of FIRST(X1). Also add the non-
 symbols of FIRST(X2), if  is in FIRST(X1); the non- symbols of FIRST(X3), if
 is in FIRST(X1) and FIRST(X2), and so on. Finally, add  to FIRST(X1X2 … Xn)
if, for all i,  is in FIRST(Xi).

Computation of the FOLLOW set

To compute FOLLOW(A) for all nonterminals A, apply the following rules until
nothing can be added to any FOLLOW set.

1. Place $ in FOLLOW(S), where S is the start symbol, and $ is the input

right endmarker.

2. If there is a production A → Bβ, then everything in FIRST(β) except 

is in FOLLOW(B).

3. If there is a production A → B, or a production A → Bβ, where

FIRST(β) contains , then everything in FOLLOW(A) is in FOLLOW(B).

Example
Consider again the non-left-recursive grammar below. Compute the FIRST
and FOLLOW sets.
E → TE
E → +T E | 
T → FT
T → * F T | 
F → (E) | id
Solution
FIRST(F) = FIRST(T) = FIRST(E) = { (. id }
FIRST(E) = { +,  }
FIRST(T) = { *,  }
FOLLOW(E) = FOLLOW(E) = { ), $ }
FOLLOW(T) = FOLLOW(T) = { +, ), $ }
FOLLOW(F) = { +, *, ), $ }

Explanations of the above answers

1. FIRST(F) = FIRST(T) = FIRST(E) = { (. id }

To see why, note that the two productions for F have bodies that start with
these two terminal symbols, id and the left parenthesis. T has only one
production, and its body starts with F. Since F does not derive , FIRST(T)
must be the same as FIRST(F). The same argument covers FIRST(E).

65
2. FIRST(E) = { +,  }.
The reason is that one of the two productions for E has a body that begins
with terminal +, and the other's body is . Whenever a nonterminal derives ,
we place  in FIRST for that nonterminal.

3. FIRST(T) = { *,  }.
The reasoning is analogous to that for FIRST(E).

4. FOLLOW(E) = FOLLOW(E) = { ), $ }.
Since E is the start symbol, FOLLOW(E) must contain $. The production body
( E ) explains why the right parenthesis is in FOLLOW(E). For E, note that
this nonterminal appears only at the ends of bodies of E-productions. Thus,
FOLLOW(E) must be the same as FOLLOW(E).

5. FOLLOW(T) = FOLLOW(T) = { +, ), $ }.
Notice that T appears in bodies only followed by E. Thus, everything except 
that is in FIRST(E) must be in FOLLOW(T); that explains the symbol +.
∗
However, since FIRST(E) contains  (i.e., E → ), and E is the entire string
following T in the bodies of the E-productions, everything in FOLLOW(E) must
also be in FOLLOW(T). That explains the symbols $ and the right parenthesis.
As for T, since it appears only at the ends of the T-productions, it must be
that FOLLOW(T) = FOLLOW(T).

6. FOLLOW(F) = { +, *, ), $ }.
The reasoning is analogous to that for T in point (5).

CONSTRUCTION OF PARSING TABLES

The following algorithm can be used to construct a predictive parsing table for
a grammar G.

If, after performing the above, there is no production at all in M[A, a], then set
M[A, a] to error (which we normally represent by an empty entry in the table).

66
The idea behind the algorithm is simple.
Suppose A→  is a production with a in FIRST(). Then, whenever the parser
has A on top of the stack with a as the current input symbol, the parser will
∗
expand A by a. The only complication occurs when  =  or  → . In this case,
we should also expand A by  if the current input symbol is in FOLLOW(A),
or if the $ on the input has been reached and $ is in FOLLOW(A).

Example
For the non-recursive expression grammar below.
E → TE
E → +T E | 
T → FT
T → * F T | 
F → (E) | id

The above algorithm produces the parsing table below. Blanks are error
entries; nonblanks indicate a production with which to expand a nonterminal.

Consider production E → TE. Since FIRST(TE) = FIRST(T) = { ( , id }, this

production is added to M[E, (] and M[E, id].
Production E → +TE is added to M[E, +] since FIRST(+TE) = { + }.
Since FOLLOW(E) = { ), $ }, production E →  is added to M[E; )] and M[E,$].

LL(1) Grammars
Predictive parsers, that is, recursive-descent parsers needing no
backtracking, can be constructed for a class of grammars called LL(1). The
first “L" in LL(1) stands for scanning the input from left to right, the second
“L" for producing a leftmost derivation, and the “1" for using one input symbol
of lookahead at each step to make parsing action decisions.

A grammar whose parsing table has no multiply-defined entries is said to be

LL(1). Algorithm above can be applied to any grammar G to produce a parsing

67
table M. For every LL(1) grammar, each parsing-table entry uniquely identifies
a production or signals an error. For some grammars, however, M may have
some entries that are multiply defined. For example, if G is left-recursive or
ambiguous, then M will have at least one multiply defined entry. Although
left-recursion elimination and left factoring are easy to do, there are some
grammars for which no amount of alteration will produce an LL(1) grammar.

Example
For instance, the language in the following example has no LL(1) grammar at
all.
S → iEtSS | a
S → eS | 
E→b

The parsing table for this grammar is shown below.

The entry for M[S, e] contains both S → eS and S → . The grammar is

ambiguous and the ambiguity is manifested by a choice in what production
to use when an e (else) is seen. We can resolve this ambiguity by choosing S
→ eS. This choice corresponds to associating an else with the closest previous
then. Note that the choice S →  would prevent e from ever being put on the
stack or removed from the input, and is surely wrong.

EXERCISE
1. The following is an LL(1) grammar for regular expressions over alphabet
{a, b}, with + standing for the union operator ( | ) and with € for the
symbol .

E → TE
E → +E | 
T → FT
T → T | 
F → PF
F → *F | 
P → (E) | a | b | 

68
 a) Compute the FIRST and the FOLLOW sets for each nonterminal of the
above grammar.
b) Show that the grammar is LL(1).
c) Construct the predictive parsing table for the grammar.
d) Construct a recursive-descent parser for the grammar.

BOTTOM-UP PARSERS
A bottom-up parse corresponds to the construction of a parse tree for an input
string beginning at the leaves (the bottom) and working up towards the root
(the top). It is convenient to describe parsing as the process of building parse
trees, although a front end may in fact carry out a translation directly without
building an explicit tree. The sequence of tree snapshots in the figure below

illustrates a bottom-up parse of the token stream id * id, with respect to the
expression grammar below.

We can think of bottom-up parsing as the process of “reducing" a string w to

the start symbol of the grammar. At each reduction step, a specific substring
matching the body of a production is replaced by the nonterminal at the head
of that production. The key decisions during bottom-up parsing are about
when to reduce and about what production to apply, as the parse proceeds.

ABOUT LR PARSERS
This section shows how to construct efficient bottom-up parsers for a large
class of context-free grammars. These parsers are called LR parsers because
they scan the input from left to right and construct a rightmost derivation in
reverse. LR parsers are attractive for a variety of reasons. Some of them are
listed as follows.
• LR parsers can be constructed to recognize virtually all programming-
language constructs for which context-free grammars can be written.
• The LR parsing method is more general than operator precedence or
other common shift-reduce techniques discussed in the last section.

69
 Yet, it can be implemented with the same degree of efficiency as these
different methods. LR parsing also dominates the common forms of top-
down parsing without backtracking.
• LR parsers can detect syntactic errors as soon as it is possible to do so
on a left-to-right scan of the input.

The principal drawback of the LR method is that there is too much work to be
done to implement an LR parser by hand for a typical programming language
grammar. One needs a specialized tool- an LR parser generator. Fortunately,
many such generators are available. With such a generator, one can write a
context-free grammar and have the generator automatically produce a parser
for that grammar. If the grammar contains ambiguities or other constructs
that are difficult to parse in a left-to-right scan of the input, then the parser
generator can locate these constructs and inform the compiler designer of
their presence.

Logically, an LR parser consists of two parts, a driver routine and a parsing

table. The driver routine is the same for all LR parsers: only the parsing table
changes from one parser to another. The schematic form of an LR parser is
shown in the figure below.

70
As the driver routine is simple to implement, we shall often consider the LR
parser-construction process as one of producing the parsing table for a given
grammar.

There are many different parsing tables that can be used in an LR parser for
a given grammar. Some parsing tables may detect errors sooner than others,
but they all accept the same sentences, exactly the sentences generated by
the grammar. In this section, we shall give three different techniques for
producing LR parsing tables but only one will be fully explained here.

The first method called simple LR (SLR for short), is the easiest to implement.
Unfortunately, it may fail to produce a table for certain grammars on which
the other methods succeed.

The second method, called canonical LR, is the most powerful and will work
on a very large class of grammars. Unfortunately, the canonical LR method
can be very expensive to implement.

The third method, called lookahead LR (LALR for short), is intermediate in

power between the SLR and the canonical LR methods. The LALR method will
work on most programming-language grammars and, with some effort, can
be implemented efficiently.

The LR Parsing Algorithm

The figure below depicts an LR parser.

Figure: Model of an LR Parser

71
The parser consists of an input, an output, a stack, a driver program, and a
parsing table that has two parts (ACTION and GOTO). The driver program is
the same for all LR parsers; only the parsing table changes from one parser
to another. The parsing program reads characters from an input buffer one at
a time. Where a shift-reduce parser would shift a symbol, an LR parser shifts
a state. Each state summarizes the information contained in the stack below
it.

The stack holds a sequence of states, s0s1 …………… sm, where sm is on top. In
the SLR method, the stack holds states from the LR(0) automaton; the
canonical-LR and LALR methods are similar. By construction, each state has
a corresponding grammar symbol. Recall that states correspond to sets of
items and that there is a transition from state i to state j if GOTO(Ii, X) = Ij. All
transitions to state j must be for the same grammar symbol X. Thus, each
state, except the start state 0, has a unique grammar symbol associated with
it.

Structure of the LR Parsing Table

The parsing table consists of two parts: a parsing-action function ACTION and
a goto function GOTO.

1. The ACTION function takes as arguments a state i and a terminal a (or

$, the input endmarker). The value of ACTION[i, a] can have one of four forms:

a. Shift j, where j is a state. The action taken by the parser effectively

shifts input a to the stack but uses state j to represent a.

b. Reduce A → β. The action of the parser effectively reduces β on top of

the stack to head A.

c. Accept. The parser accepts the input and finishes parsing.

d. Error. The parser discovers an error in its input and takes some
corrective action.

2. We extend the GOTO function, defined on sets of items, to states: if

GOTO[Ii, A] = Ij , then GOTO also maps a state i and a nonterminal A to
state j.

LR-Parser Configurations
To describe the behaviour of an LR parser, it helps to have a notation
representing the complete state of the parser: its stack and the remaining
input. A configuration of an LR parser is a pair:
(s0s1 …………… sm, ai ai+1 ………. an$)

72
where the first component is the stack contents (top on the right), and the
second component is the remaining input. This configuration represents the
right-sentential form
X1X2 ………….. Xm ai ai+1 ………… an
in essentially the same way as a shift-reduce parser would; the only difference
is that instead of grammar symbols, the stack holds states from which
grammar symbols can be recovered. That is, Xi is the grammar symbol
represented by state si. Note that s0, the start state of the parser, does not
represent a grammar symbol, and serves as a bottom-of-stack marker, as well
as playing an important role in the parse.

Behaviour of the LR Parser

The next move of the parser from the configuration above is determined by
reading ai, the current input symbol, and sm, the state on top of the stack,
and then consulting the entry ACTION[sm, ai] in the parsing action table. The
configurations resulting after each of the four types of moves are as follows.

1. If ACTION[sm, ai] = shift s, the parser executes a shift move; it shifts the
next state s onto the stack, entering the configuration
(s0s1 …………… sm s, ai+1 ………. an$)

The symbol ai need not be held on the stack, since it can be recovered from s,
if needed (which in practice it never is). The current input symbol is now ai+1.

2. If ACTION[sm, ai] = reduce A → β, then the parser executes a reduce move,

entering the configuration
(s0s1 …………… sm-r s, aiai+1 ………. an$)

where r is the length of β , and s = GOTO[sm , A]. Here the parser first popped
r state symbols off the stack, exposing state sm-r. The parser then pushed s,
the entry for GOTO[sm-r, A], onto the stack. The current input symbol is not
changed in a reduce move.

For the LR parsers we shall construct, Xm-r+1, ……..… Xm, the sequence of
grammar symbols corresponding to the states popped off the stack, will
always match β, the right side of the reducing production.

The output of an LR parser is generated after a reduce move by executing the

semantic action associated with the reducing production. For the time being,
we shall assume the output consists of just printing the reducing production.

3. If ACTION[sm , ai] = accept, parsing is completed.

4. If ACTION[sm , ai] = error, the parser has discovered an error and calls an
error recovery routine.

73
The LR-parsing algorithm is summarized below. All LR parsers behave in this
fashion; the only difference between one LR parser and another is the
information in the ACTION and GOTO fields of the parsing table.

LR-parsing algorithm.

INPUT: An input string w and an LR-parsing table with functions ACTION

and GOTO for a grammar G.

OUTPUT: If w is in L(G), the reduction steps of a bottom-up parse for w;

otherwise, an error indication.

METHOD: Initially, the parser has s0 on its stack, where s0 is the initial state,
and w$ in the input buffer. The parser then executes the program in Fig. 4.36.

Example
The figure below shows the ACTION and GOTO functions of an LR-parsing
table for the expression grammar below, repeated here with the productions
numbered.

(1) E → E + T
(2) E → T
(3) T → T * F
(4) T → F
(5) F → (E)
(6) F → id

74
The codes for the actions are:
1. si means shift and stack state i,
2. rj means reduce by the production numbered j,
3. acc means accept,
4. blank means error.

Note that the value of GOTO [s , a] for terminal a is found in the ACTION field
connected with the shift action on input a for state s. The GOTO field gives
GOTO[s , A] for nonterminals A. Although we have not yet explained how the
entries in this parsing table were selected, we shall deal with this issue
shortly.

On input id + id * id, the sequence of stack and input contents is shown in

the figure below.

75
Also shown for clarity, are the sequences of grammar symbols corresponding
to the states held on the stack. For example, at line (1) the LR parser is in
state 0, the initial state with no grammar symbol, and with id the first input
symbol. The action in row 0 and column id of the action field of the parsing
table above is s5, meaning shift by pushing state 5. That is what has
happened at line (2): the state symbol 5 has been pushed onto the stack, and
id has been removed from the input.

Then, * becomes the current input symbol, and the action of state 5 on input
* is to reduce by F → id. One state symbol is popped off the stack. State 0 is
then exposed. Since the goto of state 0 on F is 3, state 3 is pushed onto the
stack. We now have the configuration in line (3). Each of the remaining moves
is determined similarly.

LR Grammars
Our primary question is, "How do we construct an LR parsing table from a
grammar? A grammar for which we can construct a parsing table in which
every entry is uniquely defined is said to be an LR grammar. Unfortunately,
there are context-free grammars which are not LR, but these can generally be
avoided for typical programming-language constructs. Intuitively, in order for
a grammar to be LR, it is sufficient that a left-to-right parser be able to
recognize handles when they appear on top of the stack.

An LR parser does not have to scan the entire stack to know when the handle
appears on top. Rather, the state symbol on top of the stack contains all the
information it needs. It is a remarkable fact that if it is possible to recognize
a handle knowing only what is in the stack, then a finite automaton can, by
76
reading the stack from bottom to top, determine what handle, if any, is on top
of the stack. The driver routine of an LR parser is essentially such a finite
automaton. It need not, however, read the stack on every move. The state
symbol stored on top of the stack is the state the handle-recognizing finite
automaton would be in if it had read the stack from bottom to top. Thus, the
LR parser can determine from the state on top of the stack everything that it
needs to know about what is in the stack.

Another source of information than an LR parser can use to help make its
shift-reduce decisions is the next k input symbols. In practice, k=0 or k=1 is
sufficient, and we shall only consider LR parsers with k ≤ 1 here. A grammar
that can be parsed by an LR parser examining up to k input symbols on each
move is called an LR(k) grammar.

It is worth noting that the LR requirement that we be able to recognize the

occurrence of the right side of a production, having seen what is derived from
that right side, is far less stringent than the requirement for a predictive
parser, namely that we be able to recognize the apparent use of the production
seeing only the first Symbol it derives. Thus, it should be no surprise that LR
parsers are more general than predictive parsers.

The Canonical Collection of LR (0) Items

This section begins to show how to construct a "simple" LR (SLR) parser for a
grammar, if such a parser exists. The central idea is the construction of a DFA
from the grammar. In the next section we show how to turn this DFA into an
Lk parsing table. The DFA recognizes viable prefixes of the grammar, that is,
prefixes of the right-sentential forms that do not contain any symbols to the
right of the handle. A viable prefix is so-called because it is always possible to
add terminal symbols to the end of a viable prefix to obtain a right-sentential
form. Therefore, there is apparently no error as long as the portion of the input
seen to a given point can be reduced to a viable prefix.

We define an LR(0) item (item for short) of a grammar G to be a production of

G with a dot at some position on the right side. Thus, production A → XYZ
generates the four items below.

A → .XYZ
A → [Link]
A → XY.Z
A → XYZ.

The production A →  generates only one item, A → .

77
Inside the computer, items are easily represented by pairs of integers, the first
giving the number of the production and the second the position of the dot.
Intuitively, an item indicates how much of a production we have seen at a
given point in the parsing process. For example. the first item above would
indicate that we are expecting to see a string derivable from XYZ next on the
input. The second item would indicate that we have just seen on the input a
string derivable from X and that we next expect to see a string derivable from
YZ. We group items together into sets, which give rise to the states of an LR
parser. The items can be viewed as the states of an NFA recognizing viable
prefixes, and the "grouping together' is really the subset construction
discussed earlier in the course.

One collection of sets of LR(0) items, called the canonical LR(0) collection,
provides the basis for constructing a deterministic finite automaton that is
used to make parsing decisions. Such an automaton is called an LR(0)
automaton. In particular, each state of the LR(0) automaton represents a set
of items in the canonical LR(0) collection. The automaton for the expression
grammar we have been using is shown in the figure below, This will serve as
the running example for discussing the canonical LR(0) collection for a
grammar.

78
To construct the canonical LR(0) collection for a grammar, we need to define
an augmented grammar and two functions, CLOSURE and GOTO.

If G is a grammar with the start symbol S, then G, the augmented grammar
for G. is G with a new start symbol S and production S → S. The purpose of
this new starting production is to indicate to the parser when it should stop
parsing and announce acceptance of the input. This would occur when the
parser is about to reduce by S → S.

Closure of Item Sets

If I is a set of items for a grammar G, then the set of items CLOSURE(I) is
constructed from I by the following rules.

1. Initially, add every item in I to CLOSURE(I).

2. If A → .Bβ is in CLOSURE(I) and B →  is a production, then add the

item B → , to CLOSURE(I), if it is not already there. Apply this rule
until no more new items can be added to CLOSURE(I).

Intuitively, A → .Bβ is in CLOSURE(I) indicates that, at some point in the

parsing process, we think we might next see a substring derivable from Bβ as
input. The substring derivable from Bβ will have a prefix derivable from B by
applying one of the B-productions. We therefore add items for all the B-
productions; that is, if B →  is a production, we also include B → . in
CLOSURE(I).

Example
Consider the augmented expression grammar below.
E → E
E→E+T|T
T→T*F|F
F → (E) | id

If I is the set of one item {[E → E ]}, then CLOSURE(I) contains the set of items
I0 in the DFA above (see below).
E → .E
E → .E + T
E → .T
T → .T * F
T → .F
F → .(E)
F → .id

79
That is, E → .E is in CLOSURE(I) by rule (1). Since there is an E immediately
to the right of a dot, by rule (2) we are forced to add the E-productions with
dots at the left end, that is, E → .E + T and E → .T. Now there is a T immediately
to the right of a dot, so we add T → .T*F and T → .F. Next, the F to the right of
a dot forces F → .(E) and F → .id to be added. be added. No other items are
put into CLOSURE(I) by rule (2).

The function CLOSURE can be computed as in the algorithm below.

A convenient way to implement the function CLOSURE is to keep a Boolean

array ADDED, indexed by the nonterminals of G. such that ADDED[B) is set
to true if and when we add the items B → . for each B-production B → . Note
that if one B-production is added to I with the dot at the left end, then all B-
productions will be similarly added to I. In fact, it is not necessary in some
circumstances to actually list the items B → . added to l by CLOSURE. A list
of the nonterminals B whose productions were so added will suffice.

GOTO
The second useful function is GOT0(I, X) where I is a set of items and X is a
grammar symbol. GOTO(I, X) is defined to be the closure of the set of all items
[A → X.β] such that [A → .Xβ] is in I. Intuitively, if l is the set of items that
are valid for some viable prefix , then GOTO(I, X) is the set of items that are
valid for the viable prefix X.

Example
If I is the set of items {[E → E.]}, {[E → E .+ T]}, then GOTO(I, +) consists of
E → E +.T
T → .T * F
T → .F
F → .(E)
F → .id
80
That is, we examine I for items with + immediately to the right of the dot. E
→ E. is not such an item, but E → E.+T is. We move the dot over + to get E →
E +.T and take the closure of this set.

The Sets-of-Items Construction

We are now ready to give the algorithm to construct C, the canonical collection
of sets of LR(0) items for an augmented grammar G; the algorithm is shown
below.

Example
The canonical collection of sets of items for the expression grammar below is
shown in the figure below it. The GOTO function for this set of items has been
shown as the transition diagram of a deterministic finite automaton above.
(1) E → E + T
(2) E → T
(3) T → T * F
(4) T → F
(5) F → (E)
(6) F → id

81
Constructing SLR-Parsing Tables
The SLR method for constructing parsing tables is a good starting point for
studying LR parsing. We shall refer to the parsing table constructed by this
method as an SLR table, and to an LR parser using an SLR-parsing table as
an SLR parser. The other two methods augment the SLR method with
lookahead information.

The SLR method begins with LR(0) items and LR(0) automata, introduced
before. That is, given a grammar, G, we augment G to produce G, with a new
start symbol S. From G, we construct C, the canonical collection of sets of
items for G together with the GOTO function.

The ACTION and GOTO entries in the parsing table are then constructed
using the following algorithm. It requires us to know FOLLOW(A) for each
nonterminal A of a grammar
82
The parsing table consisting of the ACTION and GOTO functions determined
by the Algorithm is called the SLR(1) table for G. An LR parser using the SLR(1)
table for G is called the SLR(1) parser for G, and a grammar having an SLR(1)
parsing table is said to be SLR(1). We usually omit the “(1)" after the “SLR,"
since we shall not deal here with parsers having more than one symbol of
lookahead.

Example
Let us construct the SLR table for the augmented expression grammar that
we have been using in this section. The canonical collection of sets of LR(0)
items for the grammar was constructed above.
First, consider the set of items I0:
E → .E
E → .E + T
E → .T
T → .T * F
T → .F
F → .(E)
83
 F → .id

The item F → .(E) gives rise to the entry ACTION[0 , (] = shift 4, and the item F
→ .id to the entry ACTION[0 , id] = shift 5. Other items in I0 yield no actions.

Now consider I1:

E → E.
E → E. + T

The first item yields ACTION[1 , $] = accept, and the second yields ACTION[1
, +] = shift 6.

Next, consider I2:

E → T.
T → T. * F

Since FOLLOW(E) = {$ , + , )], the first item makes ACTION[2 , $] = ACTION[2

, +] = ACTION[2 , )] = reduce E → T

The second item makes ACTION[2 , *] = shift 7.

Continuing in this fashion, we obtain the ACTION and GOTO tables that was
already shown above. In that figure, the numbers of productions in reduce
actions are the same as the order in which they appear in the original
grammar. That is, E → E + T is number 1, E → T is 2, and so on.

Finally, let us note that every SLR(1) grammar is unambiguous, but there
are many unambiguous grammars that are not SLR(1).

Example
Consider the grammar with productions
S→L=R|R
L → *R | id
R→L

Think of L and R as standing for l-value and r-value, respectively, and * as an

operator indicating “contents of." The canonical collection of sets of LR(0)
items for this grammar is shown below.

84
Consider the set of items I2. The first item in this set makes ACTION[2 , =] be
“shift 6." Since FOLLOW(R) contains = (to see why, consider the derivation S
→ L= R → *R = R, the second item sets ACTION[2 , =] to “reduce R → L." Since
there is both a shift and a reduce entry in ACTION[2 , =], state 2 has a
shift/reduce conflict on input symbol =.

It should be noted that the grammar above is not ambiguous. This

shift/reduce conflict arose from the fact that the SLR parser construction
method is not powerful enough to remember enough left context to decide
what action the parser should take on input =, having seen a string reducible
to L. The canonical and LALR methods will succeed on a larger collection of
grammars, including this grammar in context). Note, however, that there are
unambiguous grammars for which every LR parser construction method will
produce a parsing action table with parsing action conflicts. Fortunately, such
grammars can generally be avoided in programming language applications.

85
SEMANTIC ANALYSIS
We have learnt how a parser constructs parse trees in the syntax analysis
phase. The plain parse tree constructed in that phase is generally useless for
a compiler, as it does not carry any information on how to evaluate the tree.
The productions of context-free grammar, which makes the rules of the
language, do not accommodate how to interpret them.
For example, consider the grammar production below.
E→E+T
The above CFG production has no semantic rule associated with it, and it
cannot help in making any sense of the production.
Semantic ("meaning") analysis refers to a phase of compilation in which the
input program is studied in order to determine what operations are to be
carried out. The two primary components of a classic semantic analysis phase
are variable reference analysis and type checking. These components both
rely on an underlying symbol table.

What we have at the start of semantic analysis is a syntax tree that

corresponds to the source program as parsed using the context free grammar.
Semantic information is added by annotating grammar symbols with
semantic attributes, which are defined by semantic rules. A semantic rule is
a specification of how to calculate a semantic attribute that is to be added to
the parse tree. So the input is a syntax tree...and the output is the same tree,
only "fatter" in the sense that nodes carry more information. Another output
of semantic analysis are error messages detecting many types of semantic
errors.

The semantics of a language provide meaning to its constructs, like tokens

and syntax structure. Semantics help interpret symbols, their types, and their
relations with each other. Semantic analysis judges whether the syntax
structure constructed in the source program derive any meaning or not.
CFG + semantic rules = Syntax Directed Definitions
For example,
int a = “value”;
should not issue an error in the lexical and syntax analysis phase, as it is
lexically and structurally correct, but it should generate a semantic error as
the type of the assignment differs. These rules are set by the grammar of the
language and evaluated in semantic analysis.
Objectives of Semantic Analysis
• Type checking
• Detecting undeclared variables
• Verifying scope rules
• Checking function parameter matching
• Ensuring type compatibility in expressions

Example:
int x = 10;
x = "Hello"; // Semantic error: type mismatch

86
The syntax is correct, but semantically invalid because a string cannot be
assigned to an integer.

Two typical examples of semantic analysis include:

• Variable Reference Analysis
The compiler must determine, for each use of a variable, which variable
declaration corresponds to that use. This depends on the semantics of the
source language being translated.

• Type Checking
The compiler must determine, for each operation in the source code, the types
of the operands and resulting value, if any.

Semantic Analysis makes sure that declarations and statements of program

are semantically correct. It is a collection of procedures which is called by
parser as and when required by grammar. Both syntax tree and symbol table
are used to check the consistency of the given code.
Type checking is an important part of semantic analysis where compiler
makes sure that each operator has matching operands.

It uses syntax tree and symbol table to check whether the given program is
semantically consistent with language definition. It gathers type information
and stores it in either syntax tree or symbol table. This type information is
subsequently used by compiler during intermediate-code generation.

Functions of Semantic Analysis:

1. Type Checking –
Ensures that data types are used in a way consistent with their
definition.
2. Label Checking –
A program should contain labels references.
3. Flow Control Check –
Keeps a check that control structures are used in a proper
manner.(example: no break statement outside a loop)

Example:
float x = 10.1;
float y = x*30;
In the above example integer 30 will be typecasted to float 30.0 before
multiplication, by semantic analyzer.
Static and Dynamic Semantics:
1. Static Semantics –
It is named so because of the fact that these are checked at compile
time. The static semantics and meaning of program during
execution, are indirectly related.
2. Dynamic Semantic Analysis –
It defines the meaning of different units of program like expressions
and statements. These are checked at runtime unlike static
semantics.

87
Concept of Types in Programming Languages
A type defines:
• The kind of values a variable can hold
• The operations that can be performed on it
• The memory layout and representation
Common Basic Types
• Integer
• Float
• Character
• Boolean
• String
Composite Types
• Arrays
• Structures
• Classes
• Pointers
• Functions

Type Systems
A type system is a set of rules that assigns types to various components of a
program such as variables, expressions, functions, etc.
The compiler uses the type system to:
• Detect invalid operations
• Ensure safe memory access
• Prevent runtime errors

Static vs Dynamic Typing

Static Typing
• Type checking occurs at compile time
• Errors detected before program execution
Examples:
• C
• Java
• C++
int x = 10;
x = 5.5; // Compile-time error (possible warning or error)
Advantages
• Early error detection
• Faster execution
• More optimized code

Dynamic Typing
• Type checking occurs at runtime
• Variable types determined during execution
Examples:
• Python
• JavaScript
x = 10
x = "Hello" # Allowed in Python
Advantages
• Flexibility
• Faster development

88
Strongly Typed vs Weakly Typed Languages
This is often confused with static vs dynamic typing, but they are different
concepts.

Strongly Typed Language

A strongly typed language strictly enforces type rules. It does not allow implicit
conversion between incompatible types.
Examples:
• Java
• Python
• C#
x = 10
y = "5"
print(x + y) # TypeError in Python
The language prevents mixing incompatible types.
Characteristics
• Strict type enforcement
• Fewer unexpected runtime behaviors
• Safer code

Weakly Typed Language

Allows implicit type conversion between incompatible types.
Examples:
• C (in some cases)
• JavaScript
[Link](5 + "5"); // Output: "55"
JavaScript automatically converts number to string.
Risk
Implicit conversion may cause logical errors.

Type Checking
Type checking ensures that operations are applied to compatible types.
Example:
int a = 5;
float b = 3.2;
float c = a + b; // Valid (implicit conversion)
Type Checking Strategies
1. Static Type Checking
Done at compile time
2. Dynamic Type Checking
Done at runtime

Type Compatibility
Type compatibility determines whether two types are compatible for
assignment or operation.
Two main methods:
1. Name Equivalence
Types are compatible only if they have the same name.
2. Structural Equivalence
Types are compatible if their structures are identical.

89
Example:
struct A { int x; };
struct B { int x; };
Under name equivalence → Not compatible
Under structural equivalence → Compatible

Type Conversion
Implicit Conversion (Coercion)
Automatically performed by compiler.
int x = 5;
float y = x; // Implicit conversion
Explicit Conversion (Casting)
The programmer forces conversion.
float y = (float) 5;

Type Errors Detected During Semantic Analysis

1. Undeclared variable usage
2. Type mismatch in assignment
3. Wrong function arguments
4. Return type mismatch
5. Invalid operator usage
Example:
int add(int a, int b) {
return a + b;
}

add(5, "hello"); // Semantic error

Comparison Summary
Feature Static Typing Dynamic Typing
Type Check Time Compile-time Runtime
Performance Faster Slightly slower
Error Detection Early Late

Feature Strongly Typed Weakly Typed

Implicit Conversion Minimal Extensive
Type Safety High Lower
Runtime Errors Fewer More likely

Notations Used in Semantic Analysis

• Syntax-directed definitions
High-level (declarative) specifications of semantic rules
• Translation schemes
Semantic rules and the order in which they get evaluated.
In practice, attributes get stored in parse tree nodes, and the semantic rules
are evaluated either (a) during parsing (for easy rules) or (b) during one or
more (sub)tree traversals.

90
Semantic Errors
We have mentioned some of the semantics errors that the semantic analyzer
is expected to recognize:
• Type mismatch
• Undeclared variable
• Reserved identifier misuse.
• Multiple declarations of variables in a scope.
• Accessing an out-of-scope variable.
• Actual and formal parameter mismatch.

Attribute Grammar
Attribute grammar is a special form of context-free grammar where some
additional information (attributes) are appended to one or more of its non-
terminals in order to provide context-sensitive information. Each attribute has
a well-defined domain of values, such as integer, float, character, string, and
expressions.

Attribute grammar is a medium to provide semantics to the context-free

grammar and it can help specify the syntax and semantics of a programming
language. Attribute grammar (when viewed as a parse tree) can pass values
or information among the nodes of a tree.
Example:
E → E + T { [Link] = [Link] + [Link] }
The right part of the CFG contains the semantic rules that specify how the
grammar should be interpreted. Here, the values of non-terminals E and T
are added together and the result is copied to the non-terminal E.

Semantic attributes may be assigned to their values from their domain at the
time of parsing and evaluated at the time of assignment or conditions. Based
on the way the attributes get their values, they can be broadly divided into
two categories: synthesized attributes and inherited attributes.

Synthesized Attributes
These attributes get values from the attribute values of their child nodes. To
illustrate, assume the following production:

S → ABC

If S is taking values from its child nodes (A,B,C), then it is said to be a

synthesized attribute, as the values of ABC are synthesized to S.

As in our previous example (E → E + T), the parent node E gets its value from
its child node. Synthesized attributes never take values from their parent
nodes or any sibling nodes.

91
Inherited attributes
In contrast to synthesized attributes, inherited attributes can take values
from parent and/or siblings. As in the following production,

S → ABC

A can get values from S, B and C. B can take values from S, A, and C. Likewise,
C can take values from S, A, and B.
Expansion: When a non-terminal is expanded to terminals as per a
grammatical rule

Reduction: When a terminal is reduced to its corresponding non-terminal

according to grammar rules. Syntax trees are parsed top-down and left to
right. Whenever reduction occurs, we apply its corresponding semantic rules
(actions).
Semantic analysis uses Syntax Directed Translations (SDT) to perform the
above tasks.

The semantic analyzer receives AST (Abstract Syntax Tree) from its previous
stage (syntax analysis).

Semantic analyzer attaches attribute information with AST, which are called
Attributed AST.

Attributes are two tuple value, <attribute name, attribute value>

For example:
int value = 5;
<type, “integer”>
<presentvalue, “5”>
For every production, we attach a semantic rule.

92
S-attributed SDT (Syntax Directed Translation)
If an SDT uses only synthesized attributes, it is called as S-attributed SDT.
These attributes are evaluated using S-attributed SDTs that have their
semantic actions written after the production (right hand side).

As depicted above, attributes in S-attributed SDTs are evaluated in bottom-

up parsing, as the values of the parent nodes depend upon the values of the
child nodes.

L-attributed SDT
This form of SDT uses both synthesized and inherited attributes with
restriction of not taking values from right siblings.

In L-attributed SDTs, a non-terminal can get values from its parent, child,
and sibling nodes. As in the following production
S → ABC

S can take values from A, B, and C (synthesized). A can take values from S
only. B can take values from S and A. C can get values from S, A, and B. No
non-terminal can get values from the sibling to its right.

Attributes in L-attributed SDTs are evaluated by depth-first and left-to-right

parsing manner.

We may conclude that if a definition is S-attributed, then it is also L-attributed

as L-attributed definition encloses S-attributed definitions.

93
Difference Between a Parse Tree and a Syntax Tree
In compiler design, both Parse Tree and Syntax Tree (Abstract Syntax Tree
– AST) are data structures generated during syntax analysis. However, they
serve different purposes and differ in structure and level of abstraction.

Parse Tree (Concrete Syntax Tree)

A parse tree is a tree representation of the syntactic structure of an input
string according to a given context-free grammar (CFG). It shows every detail
of the derivation, including grammar rules and terminal symbols. It strictly
follows the grammar productions used during parsing.
Characteristics of Parse Tree
• Contains all terminals and non-terminals.
• Shows complete derivation steps.
• Grammar-dependent.
• Larger and more detailed.
• Used mainly for syntax verification.
Example
Consider the expression:
a+b*c
Assume grammar:
E→E+T|T
T→T*F|F
F → (E) |id
Parse Tree Representation
E
/|\
E + T
| /|\
T T * F
| | |
F F id
| |
id id
Observation
• Every non-terminal (E, T, F) appears.
• All grammar productions are represented.
• It reflects the exact grammar rules applied.

Syntax Tree (Abstract Syntax Tree – AST)

A syntax tree is a simplified and compact representation of the program
structure. It removes unnecessary grammar symbols and focuses only on
essential constructs. It represents the hierarchical structure of operations.
Characteristics of Syntax Tree
• Contains only essential nodes (operators and operands).
• Removes redundant non-terminals.
• Compact and efficient.
• Used in semantic analysis and code generation.
• Independent of specific grammar rules.

Example
For the same expression:
a+b*c
94
Syntax Tree Representation
+
/\
a *
/\
b c
Observation
• Only operators and operands are shown.
• Grammar symbols (E, T, F) are removed.
• Shows operator precedence clearly (* before +).

3. Key Differences
Feature Parse Tree Syntax Tree (AST)
Also Called Concrete Syntax Tree Abstract Syntax Tree
Grammar Symbols Includes all Removes unnecessary
Size Large Compact
Purpose Syntax checking Semantic analysis & code
generation
Dependency Grammar-dependent More abstract
Nodes Terminals & Nonterminals Operators & Operands

Another Example: Using the same grammar above, construct (i) parse tree
and (ii) syntax tree for the expression (3 + 4) * 5.
Parse Tree (Simplified)
E
|
T Syntax Tree
/|\ *
T* F /\
/ \ + 5
F 5 /\
/|\ 3 4
( E)
/| \
E+T
| |
T F
| |
F 4
|
3

Why Syntax Tree is Preferred After Parsing

After syntax analysis:
• Compiler no longer needs grammar rules.
• Semantic analysis requires operator structure.
• Code generation needs simplified expression structure.
• Optimization is easier with AST.
Thus, most compilers convert the parse tree into a syntax tree before further
phases.

95
INTERMEDIATE CODE GENERATION
In the analysis-synthesis model of a compiler, the front end of a compiler translates a
source program into an independent intermediate code, then the back end of the
compiler uses this intermediate code to generate the target code (which can be
understood by the machine). The benefits of using machine-independent intermediate
code are:
• Because of the machine-independent intermediate code, portability will be
enhanced. For example, if a compiler translates the source language to its
target machine language without having the option for generating
intermediate code, then for each new machine, a full native compiler is
required. Because, obviously, there were some modifications in the compiler
itself according to the machine specifications.
• Retargeting is facilitated.
• It is easier to apply source code modification to improve the performance of
source code by optimizing the intermediate code.

If we generate machine code directly from source code then for n target machines, we
will have optimizers and n code generators but if we will have a machine-independent
intermediate code, we will have only one optimizer. Intermediate code can be either
language-specific (e.g., Bytecode for Java) or language independent (three-address
code).
The following are commonly used intermediate code representations:
1. Postfix Notation: Also known as reverse Polish notation or suffix notation.
The ordinary (infix) way of writing the sum of a and b is with an operator in
the middle: a + b.
The postfix notation for the same expression places the operator at the right
end as ab +. In general, if e1 and e2 are any postfix expressions, and + is any
binary operator, the result of applying + to the values denoted by e1 and e2 is
postfix notation by e1e2+. No parentheses are needed in postfix notation
96
 because the position and arity (number of arguments) of the operators permit
only one way to decode a postfix expression. In postfix notation, the operator
follows the operand.

Example 1: The postfix representation of the expression (a + b) * c is : ab +

c*
Example 2: The postfix representation of the expression (a – b) * (c + d) +
(a – b) is : ab – cd + *ab -+

2. Three-Address Code: A statement involving no more than three references

(two for operands and one for result) is known as a three-address statement.
A sequence of three address statements is known as a three-address code.
Three address statement is of form x = y op z, where x, y, and z will have
addresses (memory location). Sometimes a statement might contain less than
three references but it is still called a three-address statement.

Example: The three-address code for the expression a + b * c + d is

T1 = b * c
T2 = a + T1
T3 = T2 + d
T1, T2 and T3 are temporary variables.

There are 3 ways to represent a Three-Address Code in compiler design:

i) Quadruples
ii) Triples
iii) Indirect Triples

3. Syntax Tree: A syntax tree is nothing more than a condensed form of a

parse tree. The operator and keyword nodes of the parse tree are moved to
their parents and a chain of single productions is replaced by the single link
in the syntax tree the internal nodes are operators and child nodes are
operands. To form a syntax tree, put parentheses in the expression, this way
it is easy to recognize which operand should come first.
Example: x = (a + b * c) / (a – b * c)

97
98
CODE OPTIMIZATION
The code optimization in the synthesis phase is a program transformation technique,
which tries to improve the intermediate code by making it consume fewer resources (i.e.
CPU, Memory) so that faster-running machine code will result. Compiler optimizing
process should meet the following objectives:
• The optimization must be correct, it must not, in any way, change the
meaning of the program.
• Optimization should increase the speed and performance of the program.
• The compilation time must be kept reasonable.
• The optimization process should not delay the overall compiling process.

When to Optimize?

Optimization of the code is often performed at the end of the development stage since
it reduces readability and adds code that is used to increase the performance.

Why Optimize?

Optimizing may involve reducing the size of the code. So optimization helps to:
• Reduce the space consumed and increases the speed of compilation.
• Manually performing the optimization is tedious and is better done using a
code optimizer.
• An optimized code often promotes re-usability.

Types of Code Optimization

The optimization process can be broadly classified into two types:

1. Machine Independent Optimization: This code optimization phase

attempts to improve the intermediate code to get a better target code as the
output. The part of the intermediate code which is transformed here does not
involve any CPU registers or absolute memory locations.

2. Machine Dependent Optimization: Machine-dependent optimization is

done after the target code has been generated and when the code is
transformed according to the target machine architecture. It involves CPU
registers and may have absolute memory references rather than relative
references. Machine-dependent optimizers put efforts to take
maximum advantage of the memory hierarchy.

Code Optimization is done in the following different ways:

99
1. Compile Time Evaluation:

C
(i) A = 2*(22.0/7.0)*r
Perform 2*(22.0/7.0)*r at compile time.

(ii) x = 12.4
y = x/2.3
Evaluate x/2.3 as 12.4/2.3 at compile time.

2. Variable Propagation:

C
//Before Optimization
c = a * b
x = a
till
d = x * b + 4

//After Optimization
c = a * b
x = a
till
d = a * b + 4

3. Constant Propagation:
• If the value of a variable is a constant, then replace the variable with the
constant. The variable may not always be a constant.
Example:
C
(i) A = 2*(22.0/7.0)*r
Performs 2*(22.0/7.0)*r at compile time.
(ii) x = 12.4
y = x/2.3
Evaluates x/2.3 as 12.4/2.3 at compile time.
(iii) int k=2;
if(k) goto L3;
It is evaluated as:
goto L3 (Because k = 2 which implies condition is always
true)

4. Constant Folding:

• Consider an expression: a = b op c and the values b and c are constants,

then the value of a can be computed at compile time.

100
Example:
C
#define k 5
x = 2 * k
y = k + 5

This can be computed at compile time and the values of x and y are :
x = 10
y = 10

Note: Difference between Constant Propagation and Constant Folding:

• In Constant Propagation, the variable is substituted with its assigned
constant where as in Constant Folding, the variables whose values can be
computed at compile time are considered and computed.

5. Copy Propagation:

• It is extension of constant propagation.

• After a is assigned to x, use a to replace x till a is assigned again to another
variable or value or expression.
• It helps in reducing the compile time as it reduces copying.
Example :
C
//Before Optimization
c = a * b
x = a
till
d = x * b + 4

//After Optimization
c = a * b
x = a
till
d = a * b + 4

6. Common Sub Expression Elimination:

• In the above example, a*b and x*b is a common sub expression.

7. Dead Code Elimination:

• Copy propagation often leads to making assignment statements into dead

code.
• A variable is said to be dead if it is never used after its last definition.
• In order to find the dead variables, a data flow analysis should be done.

101
Example:
C
c = a * b
x = a
till
d = a * b + 4

//After elimination :
c = a * b
till
d = a * b + 4

8. Unreachable Code Elimination:

• First, Control Flow Graph should be constructed.

• The block which does not have an incoming edge is an Unreachable code
block.
• After constant propagation and constant folding, the unreachable branches
can be eliminated.

9. Function Inlining:

• Here, a function call is replaced by the body of the function itself.

• This saves a lot of time in copying all the parameters, storing the return
address, etc.

10. Function Cloning:

• Here, specialized codes for a function are created for different calling
parameters.
• Example: Function Overloading

11. Induction Variable and Strength Reduction:

• An induction variable is used in the loop for the following kind of

assignment
i = i + constant. It is a kind of Loop Optimization Technique.
• Strength reduction means replacing the high strength operator with a low
strength.
Examples:
C
Example 1:
Multiplication with powers of 2 can be replaced by a left shift operator
which is less
expensive than multiplication
a=a*16
// Can be modified as:
a = a<<4

102
 Example 2:
i = 1;
while (i<10)
{
y = i * 4;
}

//After Reduction
i = 1
t = 4
{
while (t<40)
y = t;
t = t + 4;
}

Loop Optimization Techniques:

1. Code Motion or Frequency Reduction:

• The evaluation frequency of expression is reduced.
• The loop invariant statements are brought out of the loop.
Example:
C
a = 200;
while (a>0)
{
b = x + y;
if (a % b == 0}
printf(“%d”, a);
}

//This code can be further optimized as

a = 200;
b = x + y;
while(a>0)
{
if (a % b == 0}
printf(“%d”, a);
}

2. Loop Jamming:
• Two or more loops are combined in a single loop. It helps in reducing the
compile time.
Example:
C
// Before loop jamming
for(int k=0;k<10;k++)
{

103
 x = k*2;
}

for(int k=0;k<10;k++)
{
y = k+3;
}

//After loop jamming

for(int k=0;k<10;k++)
{
x = k*2;
y = k+3;
}

3. Loop Unrolling:
• It helps in optimizing the execution time of the program by reducing the
iterations.
• It increases the program’s speed by eliminating the loop control and test
instructions.

Example:
C
//Before Loop Unrolling

for(int i=0;i<2;i++)
{
printf("Hello");
}

//After Loop Unrolling

printf("Hello");
printf("Hello");

Where to Apply Optimization?

Now that we learned the need for optimization and its two types, now let us see where
to apply these optimizations.
• Source program: Optimizing the source program involves making changes
to the algorithm or changing the loop structures. The user is the actor here.
• Intermediate Code: Optimizing the intermediate code involves changing
the address calculations and transforming the procedure calls involved. Here
compiler is the actor.

104
 • Target Code: Optimizing the target code is done by the compiler. Usage of
registers, and select and move instructions are part of the optimization
involved in the target code.
• Local Optimization: Transformations are applied to small basic blocks of
statements. Techniques followed are Local Value Numbering and Tree
Height Balancing.
• Regional Optimization: Transformations are applied to Extended Basic
Blocks. Techniques followed are Super Local Value Numbering and Loop
Unrolling.
• Global Optimization: Transformations are applied to large program
segments that include functions, procedures, and loops. Techniques followed
are Live Variable Analysis and Global Code Replacement.
• Interprocedural Optimization: As the name indicates, the optimizations
are applied inter procedurally. Techniques followed are Inline Substitution
and Procedure Placement.

Three Address Code in Compiler

Three address code is a type of intermediate code which is easy to generate and can
be easily converted to machine code. It makes use of at most three addresses and one
operator to represent an expression and the value computed at each instruction is stored
in temporary variable generated by compiler. The compiler decides the order of
operation given by three address code.

General representation –
a = b op c
Where a, b or c represents operands like names, constants or compiler generated
temporaries and op represents the operator
Example-1: Convert the expression a * – (b + c) into three address code.

Example-2: Write three address code for following code

for(i = 1; i<=10; i++)
{
a[i] = x * 5;
}

105
1. i=1 Explanation Optimized Version
2. L1: • i = 1 → Initialization (Since x * 5 is Constant
3. if i > 10 goto L2 • L1: → Loop start label in Loop)
4. t1 = x * 5 • if i > 10 goto L2 → Because x * 5 does not
5. t2 = i Loop termination depend on i, it can be
6. a[t2] = t1 check computed once:
7. i=i+1 • t1 = x * 5 → Evaluate 1. i = 1
8. goto L1 expression 2. t1 = x * 5
9. L2: • a[t2] = t1 → Store 3. L1:
value into array 4. if i > 10 goto L2
• i = i + 1 → Increment 5. a[i] = t1
• goto L1 → Repeat loop 6. i = i + 1
• L2: → Exit point 7. goto L1
8. L2:

Implementation of Three Address Code –

There are 3 representations of three address code namely
1. Quadruple
2. Triples
3. Indirect Triples
1. Quadruple –
It is structure which consist of 4 fields namely op, arg1, arg2 and result. op denotes
the operator and arg1 and arg2 denotes the two operands and result is used to store the
result of the expression.
Advantage –
• Easy to rearrange code for global optimization.
• One can quickly access value of temporary variables using symbol table.
Disadvantage –
• Contain lot of temporaries.
• Temporary variable creation increases time and space complexity.

Example – Consider expression a = b * – c + b * – c.

The three-address code is:
t1 = uminus c
t2 = b * t1
t3 = uminus c
t4 = b * t3
t5 = t2 + t4
a = t5

106
2. Triples –
This representation does not make use of extra temporary variable to represent a
single operation instead when a reference to another triple’s value is needed, a pointer
to that triple is used. So, it consists of only three fields namely op, arg1 and arg2.
Disadvantage –
• Temporaries are implicit and difficult to rearrange code.
• It is difficult to optimize because optimization involves moving
intermediate code. When a triple is moved, any other triple referring to it
must be updated also. With help of pointer one can directly access symbol
table entry.

Example – Consider expression a = b * – c + b * – c

107
3. Indirect Triples –
This representation makes use of pointer to the listing of all references to
computations which is made separately and stored. Its similar in utility as compared to
quadruple representation but requires less space than it. Temporaries are implicit and
easier to rearrange code.
Example – Consider expression a = b * – c + b * – c

Question – Write quadruple, triples and indirect triples for the following expression :
(x + y) * (y + z) + (x + y + z)

Explanation – The three-address code is:

t1 = x + y
t2 = y + z
t3 = t1 * t2
t4 = t1 + z
t5 = t3 + t4

108
109
110
CODE GENERATION
Code generation can be considered as the final phase of compilation. Code
generation translates the intermediate representation (IR) of a source program
into target machine code or assembly language that a computer can execute.
Through post code generation, optimization process can be applied on the
code, but that can be seen as a part of code generation phase itself. The code
generated by the compiler is an object code of some lower-level programming
language, for example, assembly language. The quality of this phase
determines the efficiency, correctness, and performance of the compiled
program.
We have seen that the source code written in a higher-level language is
transformed into a lower-level language that results in a lower-level object
code, which should have the following minimum properties:
• It should carry the exact meaning of the source code.
• It should be efficient in terms of CPU usage and memory management.

Code Generator
A code generator is expected to have an understanding of the target machine’s
runtime environment and its instruction set. The code generator should
consider the following things to generate the code:
1. Target language: The code generator has to be aware of the nature of
the target language for which the code is to be transformed. That
language may facilitate some machine-specific instructions to help the
compiler generate the code in a more convenient way. The target
machine can have either CISC or RISC processor architecture.
2. IR Type: Intermediate representation has various forms. It can be in
Abstract Syntax Tree (AST) structure, Reverse Polish Notation, or 3-
address code.
3. Selection of Instruction: The code generator takes Intermediate
Representation as input and converts (maps) it into target machine’s
instruction set. One representation can have many ways (instructions)
to convert it, so it becomes the responsibility of the code generator to
choose the appropriate instructions wisely.
4. Register Allocation: A program has a number of values to be
maintained during the execution. The target machine’s architecture
may not allow all of the values to be kept in the CPU memory or
registers. Code generator decides what values to keep in the registers.
Also, it decides the registers to be used to keep these values.
5. Ordering of Instructions: At last, the code generator decides the order
in which the instruction will be executed. It creates schedules for
instructions to execute them.

Objectives of Code Generation

The major objectives include:
• Producing correct target code that preserves program meaning
• Generating efficient machine instructions
• Optimizing memory and register usage
• Ensuring compatibility with the target system

111
Inputs to Code Generation
The code generator receives:
a. Intermediate Representation (IR)
Example:
Source Code:
a=b+c
Intermediate Representation:
t1 = b + c
a = t1

b. Symbol Table
Contains details such as:
• Variable names
• Data types
• Memory locations
Example:
Variable Type Memory Location
a Integer 1000
b Integer 1004
c Integer 1008

Outputs of Code Generation

The output may be:
• Machine code
• Assembly language
• Object code
Example (Assembly Code):
MOV R1, b
ADD R1, c
MOV a, R1

Major Tasks in Code Generation

a. Instruction Selection
The compiler selects suitable machine instructions.
Example:
IR:
t1 = b + c
Generated Machine Instructions:
LOAD R1, b
ADD R1, c
STORE R1, t1

b. Register Allocation
Registers are faster than memory. The compiler assigns frequently used
variables to registers.
Example:
Without Register Optimization:
LOAD b
ADD c
STORE temp

112
 LOAD temp
STORE a
With Register Allocation:
MOV R1, b
ADD R1, c
MOV a, R1

c. Memory Management
The compiler determines how data is stored in memory.
Example:
If variables a, b, and c are stored in memory addresses, the compiler generates
instructions to access them properly.

d. Instruction Scheduling
The compiler rearranges instructions to improve execution efficiency.
Example:
Before Scheduling:
LOAD R1, b
WAIT
ADD R1, c
After Scheduling:
LOAD R1, b
LOAD R2, d
ADD R1, c

Issues in Code Generation

Common challenges include:
• Supporting multiple processor architectures
• Limited register availability
• Maintaining execution efficiency
• Balancing speed and memory usage

Code Optimization in Code Generation

Example of Redundant Instruction Removal:
Before Optimization:
LOAD R1, b
STORE R1, a
LOAD R1, b
ADD R1, c
After Optimization:
LOAD R1, b
STORE R1, a
ADD R1, c

Importance of Code Generation

Efficient code generation improves:
• Program execution speed
• Memory utilization
• Overall software performance

113