Module -II

LL(k)
LL(k) grammar performs a top-down, leftmost parse after reading the string from left-to-right
Here, kk is the number of look-aheads allowed.
With the knowledge of kk look-aheads, we
calculate FIRSTkFIRSTk and FOLLOWkFOLLOWk where:
If the parser looks up entry in the table as synch, then the non terminal on top of the stack is
popped in an attempt to resume parsing. If the token on top of the stack does not match the
input symbol, then pop the token from the stack.

The moves of a parser and error recovery on the erroneous input) id*+id is as follows:
 FIRSTkFIRSTk: kk terminals that can be at the beginning of a derived non-terminal
 FOLLOWkFOLLOWk: kk terminals that can come after a derived non-terminal
The basic idea is to create a lookup table using this information from which the parser can then
simply go and check what derivation is to be made given a certain input token.

Now, the following text from here explains strong LL(k)LL(k):

In the general case, the LL(k)LL(k) grammars are quite difficult to parse directly. This is due to the
fact that the left context of the parse must be remembered somehow.
Each parsing decision is based both on what is to come as well as on what has already

been seen of the input.

The class of LL(1)LL(1) grammars are so easily parsed because it is strong. The strong
LL(kLL(k) grammars are a subset of the LL(k)LL(k) grammars that can be parsed without
knowledge of the left-context of the parse. That is, each parsing decision is based only on the
next k tokens of the input for the current nonterminal that is being expanded.
Formally,

A grammar (G=N,T,P,S)(G=N,T,P,S) is strong if for any two distinct A-productions in the grammar:
A→αA→α
A→βA→β
FIRSTk(αFOLLOWk(A))∩FIRSTk(βFOLLOWk(A))=∅ FIRSTk(αFOLLOWk(A))∩FIRSTk(βFOL
LOWk(A))=∅
That looks complicated so we‟ll see it another way. Let‟s take a textbook example to understand,
instead, when is some grammar “weak” or when exactly would we need to know the left -context of
the parse.

S→aAaS→aAa
S→bAbaS→bAba
A→bA→b
A→ϵA→ϵ
Here, you‟ll notice that for an LL(2)LL(2) instance, baba could result from either of
the SSproductions. So the parser needs some left-context to decide whether baba is produced by
S→aAaS→aAa or S→bAbaS→bAba.
Such a grammar is therefore “weak” as opposed to being a strong LL(k)LL( k) grammar.
BOTTOM UPPARSING:
Bottom-up parser builds a derivation by working from the input sentence back towards the start
symbol S. Right most derivation in reverse order is done in bottom-up parsing.

(The point of parsing is to construct a derivation. A derivation consists of a series of

rewrite steps)
Sr0r1r2- - - rn-

1rnsentence Bottom-up

Assuming the production A, to reduce ri ri-1 match some RHS  against ri then replace  with its
corresponding LHS, [Link] terms of the parse tree, this is working from leaves to root.
Example – 1:
Sif E then S else S/while E do S/ print
E true/ False/id
Input: if id then while true do print else print.
Parse tree:
Basicidea: Given input string a, “reduce” it to the goal (start) symbol, by looking for
substring that match production RHS.
S

E then S Clse
If S

While do S
E
true |

 if E then S elseS
lm
 if id then S elseS
lm
 if id then while E do S elseS
lm
 if id then while true do S elseS
lm
 if id then while true do print elseS
lm
  if id then while true do print elseprint
lm
 if E then while true do print elseprint
rm
 if E then while E do print elseprint
rm
 if E then while E do S elseprint
rm
 if E then S elseprint
rm
 if E then S elseS
rm
 S
rm

HANDLE PRUNING:

Keep removing handles, replacing them with corresponding LHS of production, until we reach S.

Example:

EE+E/E*E/(E)/id

Right-sentential form Handle Reducing production

a+b*c A Eid

E+b*c B Eid

E+E*C C Eid

E+E*E E*E EE*E

E+E E+E EE+E

The grammar is ambiguous, so there are actually two handles at next-to-last step. We can use parser-
generators that compute the handles for us

LR PARSINGINTRODUCTION:
The "L" is for left-to-right scanning of the input and the "R" is for constructing a
right most derivation in reverse.
WHY LR-PARSING:
1. LRparsers can be constructed to recognize virtually all programming-

language constructs for which context-free grammar scan be written.

2. TheLRparsing method is the most general non-backtracking shift- reduce parsing

method known, yet it can be implemented as efficiently as other shift-reduce

methods.

3. The class of grammars that can be parsed using LR methods is a proper subset of

the class of grammars that can be parsed with predictive parsers.

4,AnLR parser can detect a syntactic error as soon as it is possible to do so on a left- to-
right scan of theinput.
The disadvantage is that it takes too much work to constuct an LR parser by hand
for a typical programming-language grammar. But there are lots of LR parser
generators available to make this task easy.

LR-PARSERS:
LR(k) parsers are most general non-backtracking shift-reduce parsers. Two cases of interest are k=0
and k=1. LR(1) is of practical relevance.

„L‟stands for “Left-to-right” scan of input.

„R‟ stands for “Rightmost derivation (in reverse)”.

K‟ standsfornumber of input s ymbols of look-a-head that are used in making pars ing [Link]
(K) is omitted, „K‟is assumed to be 1.
LR(1) parsers are table-driven, shift-reduce parsers that use a limited right context (1 token) for
 LR(1) parsers recognize languages that have an LR(1) grammar.
A grammar is LR(1) if, given a right-most derivation

Sr0r1r2- - - rn-1rnsentence.
We can isolate the handle of each right-sentential form ri and determine the production by which
to reduce, by scanning ri from left-to-right, going atmost 1 symbol beyond the right end of the
handle of ri.
Parser accepts input when stack contains only the start symbol and no remaining input symbol
areleft.
LR(0)item:(no lookahead)
Grammar rule combined with a dot that indicates a position in its
RHS. Ex– 1: SI .S$
S.
x S.(L)

Ex-2: AXYZ generates 4LR(0) items

A.XYZ
AX.
YZ AXY.
Z AXYZ.
AXY.Z indicates that the parser has seen a string derived from XY and is looking for one
derivable from Z.
 LR(0) items play a key role in the SLR(1) table construction algorithm.
 LR(1) items play a key role in the LR(1) and LALR(1) table
construction algorithms. LR parsers have more information available
than LL parsers when choosing a production:
* LR knows eve rything derived from R HS plus„ K ‟lookahea d symbols.
* LL just kno ws„K‟lookahead symbols into whatsderived from RHS.
* Deterministic context free languages:
*
*
* LR (1) languages
*
*

LALR PARSING:
Example:

Construct C={I0,I1, ............ ,In} The collection of sets of LR(1)items

For each core present among the set of LR (1) items, find all sets having that core, and replace
there sets by their Union# (clus them into a single term)
 I0 same asprevious
I1 “
I2 “
I36 – Clubbing item I3 and I6 into one I36
item. C cC,c/d/$
CcC,c/d/$
Cd,c/d/$
I5some as previous
I47Cd,c/d/$
I89CcC, c/d/$

LALR Parsing table construction:

Action Goto
State
c d $ S C

Io S36 S47 1 2

1 Accept

2 S36 S47 5

36 S36 S47 89

47 r3 r3

5 r1

89 r2 r2 r2

Ambiguous grammar:

A CFG is said to ambiguous if there exists more than one derivation tree for the given input string
i.e., more than one Left Most Derivation Tree (LMDT) or Right Most Derivation Tree (RMDT).

Definition: G = (V,T,P,S) is a CFG is said to be ambiguous if and only if there exist a string in T*
that has more than on parse tree.
where V is a finite set of
variables. T is a finite set of

P is a finite set of productions of the form, A -> α, where A is a variable and α ∈ (V 𝖴 T)* S is a
terminals.

designated variable called the start symbol.

For Example:

1. Let us consider this grammar : E ->E+E|id

We can create 2 parse tree from this grammar to obtain a string id+id+id :
The following are the 2 parse trees generated by left most derivation:
 Both the above parse trees are derived from same grammar rules but both parse trees are different.
Hence the grammar is ambiguous.

YACC PROGRAMMING
A parser generator is a program that takes as input a specification of a syntax, and produces
as output a procedure for recognizing that language. Historically, they are also called
compiler- compilers.
YACC (yet another compiler-compiler) is an LALR(1) (LookAhead, Left-to-right, Rightmost
derivation producer with 1 look ahead token) parser generator. YACC was originally designed for
being complemented by Lex.

Input File:
YACC input file is divided in three parts.
/* definitions */
....

%%
/* rules */
....
%%

/* auxiliary routines */

....
Input File: Definition Part:
 The definition part includes information about the tokens used in the syntax definition:
 %token ID
 Yacc automatically assigns numbers for tokens, but it can be overridden by
%token NUMBER 621
 Yacc also recognizes single characters as tokens. Therefore, assigned token numbers should
no overlap ASCII codes.
 The definition part can include C code external to the definition of the parser and
variable declarations, within %{and %} in the first column.
 It can also include the specification of the starting symbol in the grammar:
%start nonterminal
 The rules part contains grammar definition in a modified BNF form.
 Actions is C code in { } and can be embedded inside (Translation schemes).
Input File: Auxiliary Routines Part:
 The auxiliary routines part is only C code.
 It includes function definitions for every function needed in rules part.
 It can also contain the main() function definition if the parser is going to be run as a program.
 The main() function must call the function yyparse().
Input File:
 If yylex() is not defined in the auxiliary routines sections, then it should be included:
#include "[Link].c"
 YACC input file generally finishes with:
.y
Output Files:
 The output of YACC is a file named [Link].c
 If it contains the main() definition, it must be compiled to be executable.
 Otherwise, the code can be an external function definition for the function intyyparse()
 If called with the –d option in the command line, Yacc produces as output a header
file [Link].h with all its specific definition (particularly important are token definitions to be
included, for example, in a Lex input file).
 If called with the –v option, Yacc produces as output a file [Link] containing a textual
description of the LALR(1) parsing table used by the parser. This is useful for tracking
down how the parser solves conflicts.

Semantics
Syntax Directed Translation:
• A formalist called as syntax directed definition is used fort specifying translations for
programming languageconstructs.
• A syntax directed definition is a generalization of a context free grammar in which each
grammar symbol has associated set of attributes and each and each productions is
associated with a set of semantic rules

Definition of (syntax Directed definition) SDD:

• SDD is a generalization of CFG in which each grammar productions X->α is associated with it a
set of semanticrules of the form

a: = f(b1,b2…..bk)
 Where a is an attributes obtained from the function f.

A syntax-directed definition is a generalization of a context-free grammar in which:

• Each grammar symbol is associated with a set of attributes.

• This setof attributes for a grammar symbol is partitioned into two subsets
called synthesized and inherited attributes of that grammar symbol.

• Each production rule is associated with a set of semanticrules.

• Semantic rules set up dependencies between attributes which can be represented by a
dependency graph.
• This dependency graph determines the evaluation order of these semantic rules.
• Evaluation of a semantic rule defines the value of an attribute. But a semantic rule may
also have some side effects such as printing avalue.

The two attributes for non terminalare :

The two attributes for non terminalare :

Synthesized attribute (S-attribute) :(↑)
An attribute is said to be synthesized attribute if its value at a parse tree node is determined
from attribute values at the children of the node

Inherited attribute:(↑,→)

An inherited attribute is one whose value at parse tree node is determined in terms of attributes at
the parent and | or siblings of thatnode.

 The attribute can be string, a number, a type, a, memory location or anything else.
 The parse tree showing the value of attributes at each node is called an
annotated parse tree.

The process of computing the attribute values at the node is called annotating or decorating the
parse [Link] can have synthesized attributes, but not inherited attributes.

Annotated Parse Tree

• A parse tree showing the values of attributes at each node is called an Annotated parse tree.

• The process of computing the attributes values at the nodes is called

annotating(or decorating) of the parse tree.
• Of course, the order of these computations depends on the dependency graph induced by
the semantic rules.
Ex1:1) Synthesized Attributes : Ex: Consider the CFG :
S→ EN
E→E+T
E→E-
T

E→ T
T→
T*F
T→T/F
T→F
F→(E)
 Solution: The syntax directed definition can be written for the above grammar by using semantic
actions for each production
Production rule Semantic actions

S→EN [Link]=[Link]
E→E1+T [Link] =[Link] +[Link]
E→E1-T [Link] = [Link] –[Link]
E→T [Link]=[Link]
T→T*F [Link] = [Link] *[Link]
T→T|F [Link] =[Link] | [Link]
F→ (E) [Link]=[Link]
T→F [Link]=[Link]
F→digit [Link] =[Link]
N→; can be ignored by lexical Analyzer as;I
is terminating symbol
For the Non-terminals E,T and F the values can be obtained using the attribute “Val”.

The taken digit has synthesized attribute “lexval”.

In S→EN, symbol S is the start symbol. This rule is to print the final answer of

expressed. Following steps are followed to Compute S attributed definition

Write the SDD using the appropriate semantic actions for corresponding production rule of the
given Grammar.

The annotated parse tree is generated and attribute values are computed. The Computation is done in
bottom up manner.

The value obtained at the node is supposed to be final output.

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
Intermediate Code
An intermediate code form of source program is an internal form of a program created by the
compiler while translating the program created by the compiler while translating the program from
a high –level language to assembly code(or)object code(machine code).an intermediate source form
represents a more attractive form of target code than does assembly. An optimizing Compiler
performs optimizations on the intermediate source form and produces an object module.

Analysis + syntheses=translation

Createsan generate targetcode Intermediatecode

parser Static intermediate intermediat code

e
Checker code generator Generato
code r
In the analysis –synthesis model of a compiler, the front-end translates a source program into an
intermediate representation from which the back-end generates target code, in many compilers
the source code is translated into a language which is intermediate in complexity between a HLL
and machine code .the usual intermediate code introduces symbols to stand for various temporary
quantities.

We assume that the source program has already been parsed and statically checked..the various
intermediate code forms are:

a) Polishnotation
b) Abstract syntax trees(or)syntaxtrees
c) Quadruples
d) Triples three address code
e) Indirecttriples
f) Abstract machinecode(or)pseudocopde
postfix notation:
 The ordinary (infix) way of writing the sum of a and b is with the operator in the middle: a+b. the
postfix (or postfix polish)notation for the same expression places the operator at the right end,
asab+.

In general, if e1 and e2 are any postfix expressions, and Ø to the values denoted by e1 and e2 is
indicated in postfix notation nby e1e2Ø.no parentheses are needed in postfix notation because the
position and priority (number of arguments) of the operators permits only one way to decode a
postfixexpression.

Syntax Directed Translation:

• A formalist called as syntax directed definition is used fort specifying translations for
programming language constructs.
• A syntax directed definition is a generalization of a context free grammar in which each
grammar symbol has associated set of attributes and each and each productions is
associated with a set of semantic rules

Definition of (syntax Directed definition ) SDD :

SDD is a generalization of CFG in which each grammar productions X->α is associated with it a set
of semantic rules of the form

a: = f(b1,b2…..bk)
Where a is an attributes obtained from the function f.

• A syntax-directed definition is a generalization of a context-free grammar in which:

• Each grammar symbol is associated with a set of attributes.

This set of attributes for a grammar symbol is partitioned into two subsets called
synthesized and inherited attributes of that grammar symbol.

• Each production rule is associated with a set of semantic rules.

• Semantic rules set up dependencies between attributes which can be represented by a

dependency graph.

Annotated Parse Tree

• A parse tree showing the values of attributes at each node is called an Annotated parse tree.

• The process of computing the attributes values at the nodes is called annotating(or
decorating) of the parse [Link] course, the order of these computations depends on
the dependency graph induced by the
 Syntax tree:

Annotated parse tree :

ASSIGNMENT STATEMENTS

Suppose that the context in which an assignment appears is given by the following grammar. P M
D
M ɛ
D D ; D | id : T | proc id ; N D ; S
N ɛ
Nonterminal P becomes the new start symbol when these productions are added to those in the
translation scheme shown below.

Translation scheme to produce three-address code for assignments

S id := E { p : = lookup ( [Link]);

ifp≠nil then
emit( p ‘ : =’ [Link])
elseerror }

E  E1 + E2 { [Link] : = newtemp;
 emit([Link] ‘: =’ [Link] ‘ + ‘ [Link] ) }
E  E1 * E2 { [Link] : = newtemp;
emit([Link] ‘: =’ [Link] ‘ * ‘ [Link] ) }

E - E1 { [Link] : = newtemp;
emit ( [Link] ‘: =’ ‘uminus’ [Link] ) }

E ( E1 ) { [Link] : = [Link] }

E  id { p : = lookup ( [Link]);

ifp≠nil then
[Link] : = p
elseerror }
Flow-of-Control Statements

We now consider the translation of boolean expressions into three-address code in the context of if- then,
if-then-else, and while-do statements such as those generated by the following grammar:

S if E then S1
if E then S1 else
| S2
| while E do S1
In each of these productions, E is the Boolean expression to be translated. In the translation, we
assume that a three-address statement can be symbolically labeled, and that the function newlabel
returns a new symbolic label each time it is called.
• [Link] is the label to which control flows if E is true, and [Link] is the label to which control
flows if E is false.

• The semantic rules for translating a flow-of-control statement S allow control to flow from
the translation [Link] to the three-address instruction immediately following [Link].
• [Link] a label that is attached to the first three-address instruction to be executed after the
code for Code for if-then , if-then-else, and while-do statements

[Link]: [Link]

[Link]: ..

[Link]: ...

(a) if-then (b) if-then-else

 [Link]: [Link] to [Link]

to [Link]
[Link]: [Link]

[Link]

[Link]: ...
(c) while-do

PRODUCTION
SEMANTIC RULES

S if E then S1 [Link] : =
newlabel; [Link] :
= [Link]; [Link] :
= [Link];

S if E then S1else [Link] : = [Link] || gen([Link] „:‟) || [Link]
S2
[Link] : =
newlabel; [Link] :
= newlabel;
[Link] : =
[Link]; [Link] :
= [Link];
 [Link] : = [Link] || gen([Link] „:‟) || [Link] ||
S whileE do S1 gen(„goto‟ [Link]) ||
gen( [Link] „:‟) || [Link]

[Link] : =
newlabel; [Link] : =
newlabel; [Link] :
= [Link];
[Link] : = [Link];
[Link] : = gen([Link] „:‟)|| [Link] ||
gen([Link] „:‟) || [Link]
|| gen(„goto‟ [Link])