Compiler Design

e-Notes	Topic	Subject Experts
Unit 1	Introduction, Lexical Analysis	Dr.Jagadish S Kallimani, MSRIT, Bangalore
Unit 2	Syntax Analysis - 1
Unit 3 & 4	Syntax Analysis - 2 & 3 : Bottom-up Parshing	Dr.S.Rajashekarmurthy, RVCE, Bangalore
Unit 6	Intermediate Code Generation	Dr.N.K.Cauvery, RVCE, Bangalore
Unit 7	Run-Time Environments
Unit 8	Code Generation
Unit 5	Syntax Directed Translation	Dr.Jayalakshmi D.S.,MSRIT, Bangalore
Unit 6A	Intermediate Code Generation

Regular, CFG, Recursive languages

Identities of regular expression

1) R*R* = R*
2) (R*)* = R*
3) RR* = R*R
4)(PQ)*P =P(QP)*
5) (a+b)* = (a*b*)* = (a*+b*)* = (a+b*)* = a*(ba*)*
 example simplify ((a*b*)* (b*a*)*)*
   = ((a+b)*(b+a)*)*
   = ((a+b)*(a+b)*)*  //set union is commutative that is a+b = b+a
   = (a+b)*                  //using above 1) and 2)
6) ∅ + R = R
7) Rε = R
8) ∅* = ε

The empty set  ∅ = {} is not the same as the empty string ε. So {}* = {ε} != {}.

Example simplify  ∅* + a* + b* + (a + b)*
since  ∅* ={ε} and ε subset of (a + b)*
a* and b* are also subset of (a + b)*
i.e a* + (a + b)* =(a + b)*
so its (a+b)*

Properties of Regular expressions

1. Associativity
associative over both Union and Concatenation
a+(b+c)=(a+b)+c  and (ab)c =a(bc)

 2)Commutative
over union only
a+b = b+a  but ab != ba

3)Distributive 
Concatenation over union
 both left and right distributive
 a . (b + c) = a.b + a.c  and also (a+b).c = a.c+b.c
Union over concatenation
 not distributive that is b+(a.c) != (b+a ). (b+c)

4)Identity
R+∅ = R  // for union
R.ε =R  // for concatenation

5)Annihilator
For concatenation  ∅ is annihilator
R.∅ = ∅
For union no annihilator

Practice problems
http://www.cs.utexas.edu/~cline/ear/automata/CS341-Fall-2004-Packet/2-Homework/

Finite Automata

• with output
• Moore m/c
• Mealy m/c
• without output
• Deterministic for each input there is one and only one state to which automata can transition from current state
• Non deterministic automata can be in several state at once
• epsilon NFA

Deterministric Automata
Five tuple A = (Q,Σ,δ,q,F)
1. A finite set of states, often denoted Q
2. A finite set of input symbols, often denoted Σ
3. A transition function that takes as arguments a state and an input symbol and returns a state
The transition function is commonly denoted δ
δ(q,a) =p
4. A start state, one of the states in Q
5. A set of final or accepting states F (F ⊆ Q)

Note In transition table the new state on any input is single unlike NFA where its set of states


Non deterministic Automata

• can be several states at once
• each NFA accepts language that is accepted by some DFA 
• easier than DFA
• we can convert NFA to DFA
• Transition function δ(q,a)  returns set of states {p1,p2,p3..}

DFA has almost as many states as NFA but has more transitions
In worst case DFA can have 2^n states when correponding NFA has n states

A NFA is allowed to make transition without getting any inputs called epsilon transition, this does not affects the class of language accepted but make implementation easier

For every DFA  there is equivalent RE
For every RE there is equivalent eNFA

DFA ---------->  RE

State Elimination Method

Eliminates states of the automaton and replaces the edges with regular expressions that includes the behavior of the eliminated states.
Eventually we get down to the situation with just a start and final node, and this is easy to express as a RE

1)If more than one final state make it single final state with all final going to this new

2)If the two states are different, we will have an automaton that looks like the following:

Note
when eliminating the state we take care to loop for all the possible loops that go through that state

Closure properties of regular language

we say language L is closed under operation X if the output of X is in L whenever inputs are in L.
Regular languages are closed under

1)Union and Intersection
cross-product of the two DFA will recognize union and intersection of two languages

2)Set complement
if we make non final states as final and final states are non final states, we get a DFA accepting the complement of language

3)String Reversal
pick NFA recognizing the languag. create new final state with epsilon transitions from old state then swap the start and final states and change directions on each transition we have a NFA accepting the reversed string

4)Set difference
can be rewritten in form of intersection and compliment

6)Concatenation and star

5)Homomorphism (substitution of string for symbols)
It is function from string ---> string  . Its output on multicharacter string is its output on individual characters in string
h(xy) =h(x)h(y) for any string x and y
Since we can always write regular expression for any homomorphism of regular language its closed under homomorphism

6)Inverse Homomorphism

Regular language not closed under

1)Subset and Superset operations


Homomorphism
consider symbols of language L as {a,b} and Homomorphism H symbol set as {a,b,c}
h(a) =ab ,h(b) =bbc then
h(aba)=h(a)h(b)h(c) = abbbcab
The homomorphic image of language L1 ={aa,aba} is h(L1) ={abab,abbbcab}

Decision properties of Regular Language
1)Membership
Is string w in regular language L?
If string w is accepted in the FA of language L then its member

2)Emptiness
Is L = ∅ ?
Remove all unreachable states and edges from the FA for the language L and then check if it has any final(accepting) state. Use graph reachability algorithm to check.

3)Finiteness
Is L finite language?
A regular language is not necessarily finite
DFA method
Remove states that are not reachable from the start state and all states that donot reach an accepting state from the DFA
If there are any cycles in the remaining DFA then it is infinite else finite
Regular Expression Method
If there are any * in the RE then it should be infinite but there are exceptions like
0ε*1 is not infinite nor is 0*∅  so we need to eliminate ∅ and ε equivalent expressions from RE
Remember
E+F is equivalent to ∅ iff both E and F are equivalent to ∅
EF is equivalent to ∅  if either E or F is
ε is not equivalent to ∅ neither is E*

E+F is equivalent to ε iff both E and F are equivalent to ε
EF is equivalent to ε  if both E and F are
E*  is equivalent to ε iff E is 

4)Equivalence
in product automaton LxM
final state pair for which exactly one final state of q and r
the language accepted should be empty for equivalence

5)Containment
Is L subset of M?
in product automata LxM
make those pair as final state for which only L is final and M is not
the language accepted should be empty for containment

make

Non Regular Language

Not recognized by finite automata
Finite automata cannot distinguish infinite string because they have limited memory

Myhill-Nerode's theorem

Indistinguishable strings
String x and y in Σ* are indistinguishable with respect to language L if and only if every string z like xz, yz are both in L or both are not in L
1)choose z
2)append z to strings
3)and check new string  whether they are in language or not
example  Check whether a and aa are indistinguishable with respect to language {aⁿ} over alphabet a
1)we choose string z in Σ* to be a^k ,
2)check string of form aa^kand aa^k, for every k this strings are in language
3)so this strings are indistinguishable

Theorem
Theorem : A language L over alphabet Σ is nonregular if and only if there is an infinite subset of  Σ^* , whose strings are pairwise distinguishable with respect to L.

Example Let L₁ = { aⁿbⁿ | n is a positive integer } over alphabet { a , b } show its nonregular using Myhill-Nerode
1)Consider the set of strings S₁ = { aⁿ | n is a positive integer } . S₁ is over alphabet { a , b } and it is infinite. We will check for its strings and try to show that they are pairwise distinguishable with respect to L₁.
 2)Let x= a^k and y= a^m be two strings of the set S₁, where k,m >0 and k != m .
3)Select z= b^m as a string to be appended to a^k and a^m  .
4)we see that a^kb^m is not into L₁ while a^mb^m is in L₁ .
Hence a^k and a^m are distinguishable with respect to L₁ . Since a^k and a^m are arbitrary strings of S₁, S₁ satisfies the conditions of Myhill-Nerode theorem. Hence L₁ is nonregular.

Pumping Lemma : Suppose that a language L is regular. Then there exist integer n > =1  such that for any string x in L with |x| >=  n(pumping length), there are strings u, v and w which satisfy the following relationships:
            x = uvw
            |uv| <= n     // loop appears within first n letters where n is pumping length
            |v| > 0   and 
            for every integer m >= 0, uv^mw element of L.   // v is the repeated string or one that loops

• Pumming lemma follows from simple pigeonhole rule that if  number of symbols is at least the size of string in the language then atleast one state must be repeated.
• pumping length n is the number of states in the FA
• v is the string that is repeated.choosing v to be of at least one letter assures that loop appears within first p letters
• so we chose a string x of length at least n  and try to prove that there is some repeated state

Pumping lemma gives necessity condition for language to be regular but its not the sufficient condition i.e even if we prove pumming lemma for language L its not necessarily  regular language

Context Free Grammar

Closure Properties
1)Union
Is L1 U L2 a CFL?
closed under union
by adding a new rule for starting symbol like S->S1|S2

2)Concatenation and closure
closed under both
for concatenation add S1->S2
for kleen closure add S->S1|S|e

3)Homomorphism
closed under homomorphism

4)Substitution
Homomorphism is special case of substitution
closed under substitution

5)Intersection
not closed under intersection

6)Intersection with Regular language
L1 CFL and L2 regular then L1 intersection L2 is CFL

7) Complementation

not closed as would mean intersection is closed which is not
¬(¬L1 ∪ ¬L2) = L1 ∩ L2 

8)Set difference
not closed under set difference

8) Set difference with Regular language
L1 CFL L2 Regular then
L1-L2 =L1 intersection L2'
which is CFL so its closed under CFL

9)Inverse Homomorphism
closed under inverse homomorphism

Decision problems of CFG
Decidable
1)Emptiness

2)finiteness

3)membership

Undecidable
1)equivalence L1 and L2 CFG then is L1=L2?
2)Inclusion or containment 
can L1 generate all string generated by L2?
3)is CFG for language ambigous
4)Universality
Does it generate the language of all strings over the alphabet of terminal symbols used in rules
Is L(G) = Σ^*?
5)given context sensitive grammer does it describe CFG or
6)given CFG does it describle Regular language



If grammar G is in CNF any derivation of string w has 2n-1 steps for |w|=n



Problem  DFA recognizing L = {x ∈ Σ∗ : 1110 is not a prefix of x}.
Solution

CYK algorithm

//incomplete for now

To check if membership property of CFL

when blank inthe table ?
when S inthe table ?


division for substring of size 3  aab can be
aa  b
a ab
which can be solved by looking at level 2 and level 1 only

for substring of size 4
division can be
a aba
aab a
which can be solved by looking at level 1 and 3
aa ba
which can be solved by looking at level 2

for substring of level 5
division ca be
a abaa
aaba a
 looking at level 1 and 4
aab aa
aa baa
level 2 and 3

Pushdown Automata

like NFA with stack(unlimited memory assumed), stack provide additional memory which help recognize some non regular languages
NPDA equivalent in power to CFG
PDA can write symbols(push) on the stack and read them(pop) back
LIFO
DPDA and NPDA are not equal in power. Expressive power of NDPD more than DPDA
NPDA can recognize languages not recognized by DPDA  unlike DF and NF in regular grammar which accepts same set of languages

Theorem
A language is context free if and only if there is some pushdown automata that recognizes it and also
If PDA accepts any language then its CFL

Theorem
L1 be set of languages accepted by PDA by empty stack L2 be set of languages accepted by PDA by final state then L1=L2

Fig. state transition in PDA

Difference between NPDA and PDA

language like L1= {ww^R|w (a+b)*}  and L2 = {aⁱb^jc^k | i=j or j=k}
needs non determinism to recognize them
In Language L1 at each point we need to nondeterministically guess middle of string and in L2 we need two state on transition from a to b from one state we check for c also by popping and on other we check for b by popping
L1 can be converted such that its accepted by DPDA by including some middle marker in it.


Non Context Free Languages
L3 = {ww| we(a+b)*} is not accepted by PDA because the here we need FIFO but stack is LIFO
while complement of L3 is CFL

L4 = ({aⁱb^jc^k | i,j,k= n }
Its not accepted by PDA because we can either match a with a or c. It requires two memory elements
Complement of L4 is also CFL

L5 = {aⁱb^jc^kdm | i,j,k= n }

Check for Non CFG

1) denote each symbol power in form of variable i j k ..
 If language L6= {aⁿbⁿc^m | n,m >=1} convert it to {aⁱb^jc^kdm | i=j=n,k= m, i,j,k >=1}
check if more than one comparision required (more than one memory element required) in variables i, j, k..
 for above language we have only one comparision i=j so its CFL
For language L7 = {a^mbⁿc^mdⁿ  m,n>=1} we convert it to {ab^jc^kd^l   i=k, j=l i,j,k,l >= 1}
we see there are two comparisons so its not a CFL

2)Check if FIFO is required if so not a CFL
example L= {ww}

3)If language is over single alphabet then it behaves similar to Regular grammar, that is, It is CFL only if the length of string(power of letter) is in arithematic progression
example L8={aⁿ² | n>=1} and  L9={a^n! |n>=1} are not CFL

Recursive and Recursively Enumerable

A language L is recursively enumerable(re) or Turing Acceptable if there exists a TM M such that L=L(M) or some TM accepts the language L.For a string not in language it may halt or may loop forever unlike recursive language
A language L is recursive(r)  or Turing Decidable if there exists a TM M such that L=L(M) or L is accepted by some TM and M halts on every w∈ Σ+ .
For recursive language a membership algorithm  exists.
For string not in language it should halt in non final state
that is L' is also recursive or is decidable

Non recursively Enumerable L'
If a language is not accepted by TM then its non recursively enumerable that is there is no algorithm to describe the language
L' is not recursively enumerable and hence not recursive

Recursive enumerable but not recursive
that is there exist a TM that accepts the language but doesnot halt on some input
or There exists a recursively enumerable language that is not recursive.
Universal language Lu is example.

If languages L and L' are both RE, then L is recursive.

implications
if L is not RE then L cannot be recursive
if L' is not RE then L is not recursive
if L is RE but not recursive then L' is not RE

If L is recursive, then L' is recursive.

If G is an unrestricted grammar, then L(G) is recursively enumerable.

Problem Consider language L1, L2, and L3 are recursively enumerable over the alphabet Σ such that
(a) Li ∩ Lj = Φ when i ≠ j; and
(b) L1 ∪ L2 ∪ L3 = Σ*
Prove that L1 is recursive.

Solution

We know that language is recursive if L and its complement L' are both RE
L1 is RE, we check L1' which is (L2 U L3)
L2 , L3 are recursive enumerable and we know that RE are closed under union, so L1' is also RE
Hence L1 is Recursive.

Problem Prove that L* is recursive if L is recursive
Solution Kleen closure is defined in terms of union and since recursive language is closed under union L* is also recursive

Problem 

1) If A is regular and B is regular, then A ∪ B'
regular because regular languages are closed under union and complementation

2)If A is regular and B is context free, then A ∪ B'
A is also context free because every regular language is context free
complement of B may not be CF because context free languages not closed under complementation
So we cannot say whether regular or context free grammar here, we check for recursive language here
B is context free so is recursive also and recursive languages are closed under complementation so B' is also recursive . Similarly we can prove its Recursive

3)If A is context-free and B is regular, then A∪ B' is
Context Free

4)If A is recursive and B is recursive, then A∪ B' is:
Recursive

5)If A is recursive and B is Recursively enumerable, then A∪ B' is:
can not be deduced

6)If A is recursively enumerable and B is recursive then A∪ B' is:
Recursive enumerable

Problem Prove that if a finite set of recursively enumerable languages partition Σ∗ , then the languages are recursive
Solution
Since language complement is also recursively enumerable and we know that L and L' are recursively enumerable then L must be recursive.

Problem If L1 is recursive language. L2 and L3 are recursively enumebrable but not recursive then
1)L2 -L1
L2 -L1 = L2 intersection L1'
L1 is recursive and we know that recursive languages are closed under complementation so L1' is also recursive and every recursive language is also recursively enumerable so L1' is also recursively enumerable
, recursively enumerable language are closed under intersection so its recursively enumerable
2)L1-L3
L1 intersection L3'
L3 is recursively enumerable but complement of L3 is not necessarily recursively enumerable.
so we cannot deduce anything
3)L2 intersection L1
Recursively enumerable


Closure properties of recursive language
Recursive Languages are closed under
1)complementation
because if language L is accepted by TM M and it halts on every input then
machine M' accepts w if M rejects it and M' rejects if M accepts it.
2)difference
3)intersection.
first run on M1 and them on M2 if accepted but both then Accept else reject
4)union.


Closure properties of recursive enumerable languages
1)Recursively enumerable languages are closed under union.
For any two Turing-recognizable language L1 and L2, let M1 and M2 be the TMs that
recognize them. We construct a TM M that recognizes the union of L1 and L2.
- For the input w
- Run M1 and M2 in parallel.
- If either accept, accept
- If both reject, reject.
2)Closed under Intersection
3)Closed under kleen closure
We can use a multi tape Turing machine as all multi tapes Turing machines have an equivalent one tape Turing machine For any Turing-recognizable language L, Let M be the TM that recognizes it. We construct a TM M1 that recognizes the star of L:
On input w, split w into w1w2…wn, save each on a tape
Run M on wi for i=1,2,…,n.
If M accepts each of these string wi, accept.
If reject reached on the possible parts, reject.”
If there is a way to cut w into substrings such M accepts all the substrings, w belongs
to the star of L and M1 will accept w after a finite number of steps.


Not Closed under
5) set difference
6)Complementation (we only need to show that there is a language that is r.e. but not recursive.)

 If L is r.e. but not recursive then L' is not r.e.


Turing Machine
Unlimited and Unrestricted memory
tape as its unlimited memory, tape head to read and write symbols and move around on the tape
Difference between Finite automata
A TM can both read from and write on the tape
Read write head can move both left and right
infinite tape
special states for accepting and rejecting take effect immediately


Every Non Deterministic TM and an equivalent Deterministic TM
that is has same expressive power
A language is decidable if and only if some NTM decides it

Halting problem
recognizer are more powerful than decider
Acceptance of string by TM is called Halting problem
its undecidable

A language is decidable if both L and its complement L' is Turing recognizable
Compliment of Acceptance problem by TM is not TM recognizable else it would be decidable

Decision problem for Type 0 or recursive enumerable language
Undecidable
1)Given M ,  is L(M) regular, context-free, recursive
2)membership inclusion universality equivalence emptiness 

    

	w ∈ L?	L = ∅?	L = Σ*?	L1 ⊆ L2?	L1 = L2?	L1 ∩ L2 = ∅?
Regular (type 3)	D	D	D	D	D	D
Det. Context Free	D	D	D	O	U	U
Context Free (type 2)	D	D	U	U	U	U
Context Sensitive (type 1)	D	U	U	U	U	U
Recursive	D	U	U	U	U	U
Recursively Enumerable (type 0)	U	U	U	U	U	U

References
www.cs.uiuc.edu/class/fa05/cs475/Lectures/new/bwlec21.pdf     //closure
web.cs.wpi.edu/~kal/courses/cs503/module10/hw9s07solns.pdf  //good problems
http://www.soe.ucsc.edu/classes/cmps132/Winter01/         //problems on turing and recursive lan 
http://www.cs.odu.edu/~toida/nerzic/390teched/regular/reg-lang/non-regularity.html
http://www.cs.odu.edu/~toida/nerzic/390teched/web_course.html  // complete course
http://www.dhedhi.com/tazeen/CS341_F03/notes/mistakes.htm   // frequent mistakes
www2.imm.dtu.dk/courses/02140/L8-MF.pdf //decision property of regular language
http://www.cs.uiuc.edu/class/fa07/cs273/      //problem set  
www.cs.uwaterloo.ca/~watrous/360/assignments/1-solutions.pdf   //problems on prefix substrings 
http://www.cs.utexas.edu/~cline/ear/automata/CS341-Fall-2004-Packet/2-Homework/   //problems 
http://www.cs.wcupa.edu/~rkline/csc520/    //undecidable problems 

Bottom-Up Parsing

We shall now turn from top-down or predictive parsing to the reverse. Instead of predicting what is to come and verifying it from the input we shall use a bottom-up approach. This means that rather than beginning with the starting symbol and generating an input string, we shall examine the string and attempt to work our way back to the starting symbol. In other words, we shall reconstruct the parse. We will process the input and decide how it was generated using our parser stack as a notebook. Let us begin by examining a string generated by the grammar:

A ® aB
B ® Ab
B ® b

The following chart provides an intuitive overview of this new approach to parsing. Here the string aabb is parsed in a bottom-up manner. We shall discuss the steps after presenting the chart.

In step 1 we moved the first input symbol (a) into the examination area and guessed that we might be working on A ® aB. But, since we had not seen a B we put off making any decisions and pushed the a onto the stack to save it for awhile. In step 2 we did the same. In step three we encountered a b. We knew that it could come from applying the production B ® b. So we substituted a B for the b. (Remember that we are working backwards.) In step 4 we looked at the stack and sure enough discovered an a. This meant that we could surely apply A ® aB, and so we did. (We moved the new A in to be examined after getting rid of the B which was there as well as the a on the stack since we used them to make the new A.) In step 5 we looked at the stack and the examination area, could not decide what was going on (except something such as B ® Ab possibly), so we just put the A onto the stack. Then in step 6 we looked at the b in the examination area and the A on the stack and used them both to make a B via the production B ® Ab. This B entered the examination area. Looking at this B and the stacked a in step 7 we applied A ® aB to them and placed an A in the examination area. Since nothing was left to do in step 8 and we were examining our starting symbol we accepted.

See what happened? We looked at our input string and whenever we could figure out how a symbol was generated, we applied the production that did it. We in essence worked our way up the derivation tree. And, we used the stack to save parts of the tree to our left that we needed to tie in later. Since our grammar was unambiguous and deterministic, we were able of do it.

Now let us do it all over with some new terminology and some mixing up of the above columns. When we push an input symbol into the stack we shall call it a shift. And when we apply a production we shall call it a reduce operation. We shall shift our guesses onto the stack with input symbols. For example, if we see an a and guess that we're seeing the results of applying the production A ® aB, we shift the pair (a, aB) onto the stack. After we reduce, we shall place a guess pair on the stack with the nonterminal we just produced. Here we go.

Our new parsing technique involves keeping notes on past input on the stack. For instance, in step 5 we have an a (which might be part of an aB) at the bottom of our stack, and an A (which we hope shall be part of an Ab) on top of the stack. We then use these notes to try to work backwards to the starting symbol. This is what happens when we do reduce operations. This is the standard bottom-up approach we have always seen in computer science. Our general method is to do a rightmost derivation except that we do it backwards! Neat. What we did at each step was to examine the stack and see if we could do a reduction by applying a production to the top elements of the stack. If so, then we replaced the right hand side symbols (which were at the top of the stack) with the left-hand side nonterminal.

After doing a reduction we put the new nonterminal on the stack along with a guess of what was being built. We also did this when we shifted a terminal onto the stack. Let us examine these guesses. We tried to make them as accurate as possible by looking at the stack before pushing the (symbol, guess) pair. We should also note that the pair (a,aB) means that we have placed the a on the stack and think that maybe a B will come along. On the other hand, the pair (b,Ab) indicates that the top two symbols on the stack are A and b, and, we have seen the entire right hand side of a production. Thus we always keep track of what is in the stack.

Now for another enhancement. We shall get rid of some duplication. Instead of placing (a, aB) on the stack we shall just put a|B on it. This means that we have seen the part of aB which comes before the vertical line - the symbol a. Putting aB| on the stack means that we have a and B as our top two stack symbols. Here is the same computation with our new stack symbols.

Let's pause a bit and examine these things we are placing on the stack. They are often called states and do indicate the state of the input string we have read and partially parsed. States are made up of items that are just productions with an indicator that tells us how far on the right hand side we have progressed. The set of items for the previous grammar is:

A ® |aB	B ® |Ab	B ® |b
A ® a|B	B ® A|b	B ® b|
A ® aB|	B ® Ab|

Recall what an item means. A ® a|B means that we have seen an a and hope to see a B and apply the production. Traditionally we also invent a new starting symbol and add a production where it goes to the old starting symbol. In this case this means adding the items:

S0 ® |A

S0 ® A|

to our collection of items.

There are lots and lots of items in a grammar. Some are almost the same. Now it is time to group equivalent items together. We take a closure of an item and get all of the equivalent ones. These closures shall form the stack symbols (or states) of our parser. These are computed according to the following procedure.

Figure 5 - Closure Computation for Items

We should compute a few closures for the items in our grammar. The only time we get past the first step above is when the vertical bar is to the left of a nonterminal. Such as in B ® |Ab. Let's do that one. We place B ® |Ab in CLOSURE(B ® |Ab) first. Then we look at all A ® a productions and put A ® |a in CLOSURE(B ® |Ab) also. This gives us:

CLOSURE(B ® |Ab) = {B ® |Ab, A ® |aB}

Some more closures are:

CLOSURE(S ® |A) = {S ® |A, A ® |aB}
CLOSURE(S ® A|) = {S ® A|}
CLOSURE(A ® a|B) = {A ® a|B, B ® |Ab, B ® |b, A ® |aB}

Thus the closure of an item is a collection of all items which represent the same sequence of things placed upon the stack recently. These items in the set are what we have seen on the input string and processed. The productions represented are all those which might be applied soon. The last closure presented above is particularly interesting since it tells us that we have seen an a and should be about to see a B. Thus either Ab, b, or aB could be arriving shortly. States will built presently by combining closures of items.

Let's return to our last table where we did a recognition of aabb. Note that in step 2 a|B was on top to the stack and the next input was b. We then placed b| on the stack. Traditionally sets of items called states are placed upon the stack and so the process of putting the next state on the stack is referred to as a GOTO. Thus from step 2 to step 3 in the recognition of aabb we execute:

GOTO(a|B, b) = b|.

In step 3 we reduced with the production B ® b and got a B. We then placed aB| on the stack. In our new terminology this is:

GOTO(a|B, B) = aB|.

It is time now to precisely define the GOTO operation. For a set of items (or state) Q and symbol x this is:

GOTO(Q, x) = {CLOSURE(A ® a x|b )} for all A ® a |xb Î Q

Check out the operations we looked at above and those in the previous acceptance table. Several more examples are:

GOTO({S ® |A, A ® |aB}, A)	= CLOSURE(S ® A|) = {S ® A|}
GOTO({S ® |A, A ® |aB}, a)	= CLOSURE(A ® a|B) = {A ® a|B, B ® |Ab, B ® |b, A ® |aB}

So, all we need do is add a new starting production (S₀ ® S) to a grammar and execute the following state construction algorithm in order to generate all the states we require in order to do parsing.

Figure 6 - State Construction Algorithm

The seven states determined for our example grammar using the above algorithm are:

Q₀ = {S ® |A, A ® |aB}
Q₁ = {S ® A|}
Q₂ = {A ® a|B, B ® |Ab, B ® |b, A ® |aB}
Q₃ = {A ® aB|}
Q₄ = {B ® A|b}
Q₅ = {B ® b|}
Q₆ = {B ® Ab|}

and the relationships formed from the GOTO(Q, x) relationship are:

Note that not all state-symbol pairs are represented. We do know why there are no states to go to from Q₁, Q₃, Q₅, and Q₆ - right? Because they are states that contain items we shall reduce. After that we shall place another item on the stack as part of the reduction process.

All that remains is to build a parser that will carry out the sample computation we presented above. It is easy. Here are the rules for building the parser table. (Recall that the stack symbols or states are along the left side while grammar symbols lie across the top.)

Figure 7 - Parser Table Construction

That is all there is to it. Quite simple. Another note - we shall attach a GOTO table to the right side of our parser table so that we know what to place on the stack after a reduction. The parser for our sample grammar is provided below. The words shift and reduce have been omitted because they refer always to states and productions respectively and there should be no problem telling which is which. (Aliases for the states have been provided so that the table is readable.)

We know intuitively how these parsers work, but need to specify some things precisely. Shift operations merely push the indicated state on the stack. A reduce operation has two parts. For a reduction of A ® a where the length of a is k, first pop k states off the stack. (These are the right hand side symbols for the production.) Then if Q_i is on top of the stack, push GOTO(Q_i ,A) onto the stack. So, what we are doing is to examine the stack and push the proper state depending upon what was at the top and what was about to be processed. And last, begin with Q₀ on the stack. Try out our last example and note that exactly the same sequence of moves results.

Now let us label what we have been doing. Since we have been processing the input from left to right and doing rightmost derivations, this is called LR parsing. And the following theorem ties the LR languages into our framework.

Theorem. The following classes are equivalent.

a) Deterministic context free languages.
b) LR(1) languages.
c) LR(0) languages with endmarkers.
d) Languages accepted by deterministic pushdown automata.

Building Top-Down Parsers

The major class of grammars used for top-down parsing is the class of LL(1) grammars. LL(1) means that the parser we build from the grammar is processing the input string from left to right (that's the first L) using leftmost derivations (the second L). This is exactly what the parsers we wish to design shall do. They will create a leftmost derivation and check it against the input string. In addition, they are allowed to look ahead one symbol. This means that the parser can examine the next symbol on its input string without advancing past it. The major piece of information that the parsers need to do this is called the select set.

Definition. The select set for the production A ® a (denoted SELECT(A ® a )) where A is a nonterminal and a is a string of terminal and nonterminial symbols is the set of all terminal symbols which begin strings derived from a .

Consider the grammar S ® e | aSb. The select set for the second production is {a}. For the first production, we cannot apply the above definition, so we have to think about things a little. Note that if the parser is looking at a symbol which follows S, then we probably should apply S ® e whenever we see that symbol. In this case the symbol b always follows S. The parser built from this appears in figure 1.

Figure 1 - A Parser for S ® e | aSb

It is important to note that in the second row of the table, the parser looked ahead one symbol to determine that S ® e should be applied.

Here is the formal definition of LL(1) grammars, a class of deterministic context free grammars based upon select sets.

Definition. A context free grammar is an LL(1) grammar if and only if any two productions with the same left-hand sides have different select sets.

We need now to fully define select sets for arbitrary productions. Intuitively, they will contain all of the terminal symbols first produced by the production, which we call its FIRST set. If the production can lead to the empty string, then the FOLLOW set of the left-hand side nonterminal must be included. Here are the formal definitions.

Definition. FIRST(A ® a ) is the set of all terminal symbols a such that some string of the form ab can be derived from a .

The FIRST set for S ® aSb is of course the set {a}.

Definition. The follow set for the nonterminal A (denoted FOLLOW(A)) is the set of all terminals a for which some string a Aab can be derived from the starting symbol S. (Where a and b are possibly empty strings of both terminals and nonterminals.)

The FOLLOW set for S in the grammar S ® e | aSb is the set {b}.

Definition. SELECT(A ® a ) contains FIRST(A ® a ). If e can be derived from a then it also contains FOLLOW(A).

We begin by determining which nonterminals can generate the empty string e using the algorithm of figure 2.

Figure 2 - Finding Nullable Nonterminals

Let's pause a moment and make sure that the algorithm for finding nonterminals which generate the null string is correct. Two steps are needed for this.

We claim that it terminates because one nonterminal is deleted every time the loop is executed and sooner or later the loop will terminate since there are no more epsilon rules or we shall run out of nonterminals.

As an example, let us apply the algorithm of figure 2 to the following grammar.

S ® ABA | cC
A ® e | a
B ® e | bD
C ® AD | b
D ® aA | c

First we remove all of the productions containing terminals. Only the following four productions remain.

S ® ABA

A ® e

B ® e

C ® AD

Executing the loop one time places A and B into the set of nullable nonterminals and leaves the two following productions after removing the epsilon rules and substituting e for A and B in the above productions.

S ® e

C ® D

The loop is executed once more and S is added to the nullable nonterminal set and then the algorithm halts since C ® D is not an epsilon rule.

Correctness comes from thinking about just how a nonterminal A could generate the null string e . There must be a production A ® a where all of the nonterminals in a in turn generate e . And one of them must generate e directly.

Now we must work out computing procedures for FIRST, FOLLOW, and SELECT. We have defined them, but have not demonstrated how to compute them.

(Note: In the following, capital Roman letters are nonterminals, small Roman letters from the beginning of the alphabet are terminals, x and y can be either terminals or nonterminals. All Greek letters (except for e ) are possibly empty strings of terminals and nonterminals.)

In order to compute FIRST sets several steps are necessary. We start by identifying all of the terminal and nonterminal symbols that will be generated immediately from productions and place them in a set named BEGIN for the nonterminal on the right-hand side.

Computing FIRST(A), which we recall is the set of symbols appearing first in strings generated from A, involves taking the reflexive, transitive closure of BEGIN(A). This is done easily with a queue as follows.

Using the last grammar as an example we find the BEGIN and FIRST sets shown below for all of the nonterminal symbols.

Recall that A and c are in BEGIN(S) since they began productions and B had to join BEGIN(S) since A can generate the empty string.

Now we have all of the terminals that show up at the beginning of strings generated by each nonterminal. For completeness we state that for each terminal symbol a, FIRST(a) = {a}.

At last we have all of the information needed to compute FIRST(A ® a ) for each production. These sets are basically the union of the FIRST sets for all the symbols which can start a . Since these FIRST sets for productions will be used only to find SELECT sets they need only contain terminal symbols.

Here are the terminal symbols for the FIRST sets for the two productions that do not have right-hand sides beginning with terminals.

S ® ABA

{ a, b }

C ® AD

{ a, c }

Some more relations are needed to build the FOLLOW sets for each productions. We need to detect symbols that come after others and which end derivations. AFTER(A) is the set of all of symbols that immediately follow A and END(A) is the set of all symbols that are last in productions with A as a left-hand side.

Note that A can follow immediately after itself since B may generate the empty string. Here are the AFTER and END sets for the nonterminals.

If we set LAST(A) to be the reflexive, transitive closure of END(A) then it is the set of symbols which end strings generated from A. The same algorithm used to calculate the FIRST sets can be used here.

The next part is a little intricate. FOLLOW(N₁) is the set of all terminal symbols t such that there exist symbols N₂ and x where:

N₁ Î LAST(N₂) {N₁ ends a string derived from N₂}
and x Î AFTER(N₂) {x directly follows N₂ in some production}
and t Î FIRST(x) {t is the first terminal in string generated by x}

To compute the FOLLOW sets for the nonterminals, we shall fill in a chart with the symbols that correspond to the three relationships above.

N1	N2	x	t
S	S
A	S,A,C,D	A,B,D	a,b,c
B	S,B	A	a
C	S,C
D	S,C,D

At this point we have all of the information we need in order to define SELECT sets for each production. The definition is the following.

This provides the following select sets for the example grammar. After all of this work, we now know that it is not a LL(1) grammar because the two A productions do not have different select sets.

S ® ABA	{a,b}	S ® cC	{c}
A ® e	{a,b,c}	A ® a	{a}
B ® e	{a}	B ® bD	{b}
C ® AD	{a,c}	C ® b	{b}
D ® aA	{a}	D ® c	{c}

Here is another example, the grammar for arithmetic expressions. It appears in factored form on the right.

E ® T | T+E		E ® TA
		A ® +E | e
T ® F | F* T		T ® FB
		B ® * T | e
F ® x | (E)		F ® x | (E)

Our first task is to find the nonterminals that can generate the empty string. This is easy since only A and B can do this and it was obvious. Having no surprises is, by the way, a sign of good grammar design!

The chart below provides all of the relations that were described above for the nonterminals of the factored grammar.

	E	A	T	B	F
BEGIN	T	+	F	*	x, (
FIRST	E, T, F, x, (	A, +	T, F, x, (	B, *	F, x, (
AFTER	)		A		B
END	A,T	E	B, F	T	x, )
LAST	E,A,T,B,F,x,)	E,A,T,B,F,x,)	T,B,F,x,)	T,B,F,x,)	F,x,)

The FIRST sets for the interesting productions are the following.

E ® TA

{ x, ( }

T ® FB

{ x, ( }

Using the above information we can construct the chart for the FOLLOW sets (in the t column) as shown below.

N1	N2	x	t
E	E,A	)	)
A	E,A	)	)
T	E,A,T,B	A, )	+, )
B	E,A,T,B	A, )	+, )
F	E,A,T,B,F	A, B, )	+, * , )

Putting this all together we arrive at the following select sets and are able to construct a parser for the grammar. The general rule for LL(1) parsers is to pop a production's left-hand side and push the right hand side when reading the select set. Here is our example as figure 3.

Figure 3 - A Parser for Arithmetic Expressions

That wasn't so bad after all. We did a lot of work, but came up with a deterministic parser for a LL(1) grammar that describes arithmetic expressions for a programming language.

One more note on top-down parsers is needed. They're usually presented with instructions to either pop the top stack symbol (for an epsilon rule) or to replace the top stack symbol with a string (for other productions). No advance of the input is made in either case. It is always implicitly assumed that when the top of the stack matches the input then the parser pops the symbol and advances. These are called predict and verify operations based on leftmost derivations. Also, these parsers are often presented in a slightly different format. All of the match or verify operations with terminals on the input and stack are understood and a replace table is provided as the parser. This table shows what to place on the stack when the top symbol and the next input symbol are given. Here is our last example in this form.

See how the two formats describe the same parser? In the new form we just examine the input and the stack and replace the stack symbol by the string in the appropriate box of the parser table. By the way, the blank boxes depict configurations that should not occur unless there is an error. In a real parser one might have these boxes point to error message routines.

At this point we have defined a subclass (in fact a proper one) of the deterministic context free languages for which we know how to build parsers. We also have some tools that can be used to place grammars in the correct form if needed. These tools are:

• omitting useless nonterminals,
• omitting unreachable nonterminals,
• factoring,
• substitution, and
• recursion removal.

A further word about recursion is needed. It should be obvious that left recursion (immediate or cyclic) is not compatible with top-down parsing. The following result provides some confort for those who make sure that the grammars they design are not recursive.

Theorem. Every LL(1) language has a nonrecursive grammar.

Finally, if we wish to translate or parse something the following recipe should help to streamline the task.

1. Develop a grammar for it,
2. Convert the grammar to LL(1) form, and
3. Construct the parser.

This promises success since LL(1) grammars provide parsers which are nonrecursive and deterministic.