program to find sum of N find sum of first n numbers

numbers.
%{ %{
# include<stdio⋅h> # include<stdio⋅h>
int sum, x, a [50]; int i, x, sum = 0;
%} %}
%% %%
[0 – 9]+ { [0 – 9]+
x=atoi(yy text); {
sum=0; printf ("\n"); x=atoi (yytext);
for (i=0; i<x; i++) for (i=0; i<=x; i++)
{ printf ("\enter number"); {
scanf ("%d", &a[i]); sum=sum+i;
sum + = a[i]; printf ("%d", i);
} }
printf ("sum is /n=", sum); prinft ("The sum of first %d
return (0); numbers is %d /n"; x, sum);
} return (0);
%% }
main() %%
{ main()
printf ("enter how many {
numbers"); printf ("\enter number \n");
yylex(); yylex();
} }
yyerror() {
printf ("error"); }
yywrap() {
return (1);
}
count number of vowels and number of words per line
%{ # include <stdio·h> [ ]+ {wno ++;}
int 1cnt = 0, vcnt = 0, wno = 0; [aeiouAEIOU] {vcnt ++;}
%} ·;
%% %%
[ · ]+ {1cnt ++; wno ++; printf main() {
("1cnt = % d vowel = % d printf ("Enter input : \n");
word = % d \n", lcnt, vcnt, yylex();
wno); printf (" \n Total lines = % d",
vcnt = 0; wno = 0; } 1cnt); }
A lex program to find area of identifies tokens like id, if and
square. for.
%{ %{
# include<stdio⋅h> include <stdio.h>
int a; %}
%} %%
%% [a-zA-z] [a-zA-z0-9]*
[0 – 9]+ { return id; }
{ [iI] [fF]
s = atoi (yytext); { return if; }
a=s*s [Ff] [Oo] [Rr]
printf ("\n area of square is { return for; }
\n%d", a); %%
return (0); main()
} {
%% printf ("\n Enter word");
main() yylex();
{ }
printf ("enter side \n");
yylex();
}

%{ getchar();
#include<stdio.h> retrun 0;
int number, cube; }
%} int yywrap(void)
%% {
[0-9]+ { return 0;
number-atoi(yytext); }
cube=number* number*
number;
printf("\n Cube of given number
% is = %d", number,cube);
retum (0);
}
%%
int main()
{
printf("\n Please enter any
integer value: ");
yylex();
SLR Parser LALR Parser CLR Parser
1. SLR parser is 1. LALR parser is 1. CLR parser is
very easy and also easy and cheap expensive and
cheap to implement. to implement. difficult to
implement.
2. SLR parser is the 2. LALR and SLR
smallest in size. have the same size. 2. CLR parser is the
largest.
3. Error detection is 3. Error detection is
not immediate in not immediate in 3. Error detection
SLR parser. LALR parser. can be done
immediately in CLR
4. SLR parser fails 4. It is intermediate parser.
to produce a in power between
parsing table for a SLR and CLR i.e., 4. It is very powerful
certain class of SLR ≤ LALR ≤ CLR. and works on a
grammars. large class of
5. LALR parser grammar.
5. SLR parser requires more time
requires less time and space 5. CLR parser also
and space complexity. requires more time
complexity. and space
complexity.

Recursive Decent Parser PredictiveParser

1. Left recursive grammars are 1. Left recursive grammars are
not suitable. not suitable.

2. It accepts LL (1) grammar. 2. It accepts LL (1) grammar.

3. It uses recursive 3.It uses parser table.

procedures.
4. This parser requires less
4. Parser requires more space space in memory.
in memory since it is recursive.
5.It detects the errors using
5. Precise error indication is parse table.
not possible.
6. First and follow functions are 6. FIRST and FOLLOW
not required. functions are required.
LL Parser LR Parser
1] The first L in the LL parser is 1] The L in LR parser is for the
for scanning the input from left left to right, and R stands for
to right, and the second L is for rightmost derivation in the
the leftmost derivation. reverse order.

2] LL follows the leftmost 2] LR follows rightmost

derivation. derivation in reverse order.

3] An LL parser amplifies non 3] Terminals are condensed in

terminals. LR parser.

4] LL parser constructs a parse 4] LR parser constructs a

tree in a top-down manner. parse tree in a bottom-up
manner.
5] It ends whenever the stack in
use becomes empty. 5] It starts with an empty stack.

6] It starts with the start symbol. 6]It ends with the start symbol.

7] It is easier to write. 7]It is difficult to write.

8] Pre-order traversal of the 8]Post-order traversal of the

parse tree. parse tree.

9] Reads the terminals when it 9]Reads the terminals while it

pops out of the stacks. pushes them into the stack.

10] Builds the parse tree top- 10] Builds the parse tree
down. bottom-up.
(a) What is cross compiler.
 a compiler which can convert instructions into machine code or
low-level code for a computer other than that on which it is run.
(b) What is the purpose of flow graph?
 Flow graph shows how control is flowing between basic blocks.
ii) It is also used to detect loops and can be used for global code
optimization
(c) List any two lex library functions.
 yyerror(): Indicates the error in lex programs.
yylex(): It scans number of lines from the keyboard
yywrap(): If the value returned from yywrap() is 1, it indicates that
no further input is available.
(d) Define Memory Binding.
 A data item is associated to some address of a memory area is
called memory binding.
(e) Define the term Dead Code.
 Code which can be omitted from a program without affecting its
results is called dead code.
(f) Terminals can have synthesized attributes, but not inherited
attributes. State true or false.
 True Terminals are tokens which are recognized by lexical
analyzer. So attributes of terminal is synthesized by lexical
analyzer.
(g) Define the term lexeme.
 A lexeme is a sequence of characters in the source program
that is matched by the pattern for a token.
(h) Define SDD. (Syntax Directed Definitions)
 A SDD is a context free grammar in which the productions are
associated with semantic rules.
(i) List the different types of conflicts that occur in LR Parser.
 Shift Reduce conflict. ii )Reduce Reduce conflict
(b) List the phases of compiler.
 Lexical analysis, Syntax analysis, Semantic analysis,
Intermediate code generation, Code optimization, Target code
generation.
(c) Which parser is more powerful parser in Bottom up parser ?
 CLR is most powerful parser among bottom up parser
(d) What is the purpose of augmenting the grammar?
 Purpose of augmenting the grammar is to indicate parser where
to stop parsing and announce acceptance of input sentence
(e) Define the term Token.
 Token is a sequence of fcharacters that can be treated as a
single logical entity. Typical tokens are, 1) Identifiers 2) Keywords
3) operators 4) special symbols 5) constants
(g) State any two functions of Lex Library.
 yyerror): Indicates the error in lex programs
yyles(): It scans number of lines from the keyboard.
yywrap(): If the value returned from yywrap() is 1. it indicates that
no further input is available.
(h) Define the term Bootstrapping.
 Bootstrapping is the technique for producing a self-compiling
compiler i.e, it is a process in which we write a compiler for a
language L using same language L
(1) Name the conflict which is not possible in LR Parser.
 Shift-Shift Conflict
(1) What is handle pruning?
 Handle pruning is a parsing process where input sentence is
reduced to starting not terminal (NT) of grammar. ii )If A→B is a
production then reducing ẞ to A by the given production is called
handle pruning i.e., removing the children of A from the parse
tree.
1) What is translator? Give one example.
 Translator is a Program that converts program/text from one
language to another. Example: Ccompiler, Assembler
2) What are the advantages of bootstrapping?
-To Improve quality of compiler -We need to know only 1
language as same language is used for writing compiler and
source language to be translated. - It also helps in implementing
cross compiler
3) Define cross compiler.
 A compiler running on one machine and generating code for
other machine.
4) What is boot strapping?
 It is a process in which we write a compiler for a language L
using same language L
5) State true or false: symbol table is not required in all phases of
compilers.
 False, it can be required for all phases of compiler.
6) List all the phases of compiler in sequence.
 Lexical analysis, syntax analysis, semantic analysis,
intermediate code generation, code optimization, target code
generation.

8) Define Self Compiler.

 Self compiler is a compiler running on one machine generating
target code for same machine.

9) Which one is faster in terms of execution? One pass or two pass

compiler?
 One pass compiler is faster than two pass compiler as it take
less passes for translation
8) Write the purpose of lex library functions-yylex() and yyerror()
 yylex(): this function starts or resumes scanning input
statement and discovers tokan. It is the main function of LA and
contain all translation rules. ii) yyerror(): as the name suggest
this function is called when an lexical error is detected while
recognizing tokens. .
10) List LEX library functions.
 yyerror(), yylex(), yywrap()
11) What is sentinel?
 Sentinel is a special character used to indicate end of input
buffer
Q] What is use of looakahead pointer?
 Lookahead pointer is used to recognize token. scan input
statement from beginning pointer and discover token using token
recognizing rules called pattern. Look ahead pointer looks
ahead(forwarded) until a match for pattern is found
Define: 1) Parser -
The syntax analysis is performed by a module in the compiler
called as parser.
ii) Handle-
Solution: During Reduction, the substring that gets replaced by
its equivalent left side of the production is called handle.

3) What is left factoring?

 Left factoring is a grammar transformation that is useful for
producing a grammar suitable for predictive parsing(top down
parsing). Left factoring can be observed in grammar when we find
a rule of type A->ax/aß Such rule Can be left factored as: i)A->aX
ii )Χα/β
4) List actions taken by shift reduce parser.
 Shift symbol on stack, Reduce, Accept (success), Error (Reject)
1) What are classes of SDD?
SDD is Syntax Directed Definition and It has 2 types: 8-
Attributed Definition and L- Attributed Definition
2) Define Dependency Graph. Solution:
Dependency graph is a directed graph that shows
dependencies between attributed nodes.
3) Define Syntax Directed Definition.
A syntax-directed definition is a context-free grammar whose
productions are associated with 1 or more semantic rules. In SDD,
each grammar symbol can be associated with a set of attributes
(synthesized, inherited attributes)
4) Define Attribute Grammar.
An attributed grammar is a SDD in which function in the
semantics rules cannot have side effects.
6) Define L-attributed grammar.
 L-attributed grammar is an attribute grammar in which
grammar symbols can have synthesized or inherited attributes
with restriction (value of a node can be obtained from paront or
loft sibling)
7) Define synthesized and Inherited attribute.
 Synthesized attribute of a node is a value computed from its
children or associated with meaning of token. Synthesized
attribute at node N is defined only terms of attributed value at the
children of N and at N itself. Inherited attribute of a node is a value
computed from attribute values of its parent or siblings. An
inherited attribute at node N is defined only in terms of attribute s
values at N's parent, N itself and N's siblings.

8) What is annotated parse tree?

A parse tree showing the values of attributes at each node is
called annotated parse tree or decorated parse tree.
6
Top-down Parsing Bottom-up Parsing
1. Top-down parser uses 1.It uses reduction.
derivation.
2.Parsing start from input
2. Parsing start from starting string and reduce to the
symbol and derive the input starting symbol.
string.
3.No left-recursion and
3. Left-recursion and backtracking problems.
backtracking are two problems
occurring in this parsing. 4.It accepts ambiguous
grammar.
4. Ambiguous grammars are
not suitable for top-down 5.Precise error indication is
parsing. possible.

5. Precise error indication is 6.This uses LR grammar.

not possible.
7. It scans input from left-to-
6. This uses LL(1) grammar. right and generates rightmost
deviation.
7. It scans the input from left-
to-right and generates leftmost 8. Bottom-up parsers are
derivation. • Operator precedence parser.
• LR parser (SLR, LR (1), LALR)
8. Top-down parsers are
• Recursive descent parser 9.Shift-reduce and reduce-
• Predictive parser. reduce conflict occurs.

9. No conflict occur.
Single-Pass Compiler Multi-Pass Compiler
1]. A one-pass complier is that 1. A multi-pass compiler is a
passes through the source type of complier that processes
code of each compilation unit the source code of a program
only once. several times.

2]. A one-pass complier does 2. Each pass takes the result of

not "look back" at code it the previous pass as the input
previously processed. and creates an intermediate
output.
3]. In a single-pass compiler all
the phases of compiler design 3.In a multi-pass complier the
are grouped in one pass. different phases of a complier
design are grouped into
4]. It is less efficient code multiple passes.
optimization and code
generation. 4. Better code optimization and
code generation.
5. It is also called as narrow
compiler. It is also called as 5. It is also called as wide
wide compiler. compiler.

6. Single-pass compiler 6.Multi-pass compiler requires

requires large small memory for compilation.
memory for compilation.
7.They are slower speed in
7. They are faster speed in compilation process. As more
compilation process. number of passes means more
execution time.
8. One pass compiler reads the
code only once and then 8. A multi-pass compiler
translates/compile it so modifies the program into one
there is no modification of or more intermediate
code. representations.

9. Pascal and C languages 9. C++ and Modula-2 languages

compilers are the compilers are the examples of
examples of single-pass multi-pass compiler.
compiler.

4
2
find factorial of a given total words, lines and characters
number. from input end with $.
%{ %{
# include<stdio⋅h> # include<stdio⋅h>
int i, fact, n; int c=0, w=0, 1=0;
%} %}
%% %%
[0 – 9]+ [\t]+
{ n = atoi (yytext); {
for (i=1; i<=n; i++) w++; c+=strlen (yytext); }
fact = fact * i; [⋅\n] {
printf ("Factorial do no. % d is l++, w++}
%d\n", n, fact); [$] {
return (0) printf ("\n\n\t total characters :
%% % d \n
main() \t Total words : \t%d\n Total
{ printf ("\n Enter number"); lines : %d
yylex(); \t \n", c, w, l);
} return (0);
}
%%
main()
{
yylex();
}
find total vowels from the input.
%{ %%
# include<stdio⋅h> main()
int w=0, vc=0; {
%} printf ("enter input \n");
%% yylex();
[\t]+ }
{w++;]
[a e i o u A E I O U] { vc ++; }
[⋅] +
{
printf ("\n\n Total vowels %d
is", vc;}
⋅;
Q] Define Directed Acyclic Graph (DAG). 12
 a Directed Acyclic Graph (DAG) is a special kind of abstract
syntax tree (AST) where a unique node is present for every unique
value. ii) DAG is a directed acyclic graph used to represent
intermediate code in efficient way by eliminating common sub
expressions.
Q] What is an operator grammar?
A grammar with following characteristics is called operator
grammar: No E-transition i.e. E is not present on right hand side
of any production. ii) No production has two adjacent non-
terminals
Q] Write a short note on SDD (Syntax Directed Definitions).
 A context free grammar, in which the productions are shown
along with its associated semantic rules, is called as a Syntax
Directed Definition (SDD). ii) Attributes are associated with
grammar symbols and rules are associated with productions. The
attributes can be written as the grammar symbol followed by a dot
and attribute name.e.g., the 'type' attribute of identifier list can be
written as identifier_list.type iii)The value of attribute may be
numbers, types, tables or strings. e.g., the 'type' attribute of the
identifier list can be an integer, a character or real. We can
associate a semantic rule "identifier_list.type =
type_spec.data_type". iv)Types of attributes:-
a) Inherited attributes:-
1) It is defined by the semantic rule associated with the production
at the parent of node. 2) Attributes values are confined to the
parent of node, its siblings and by itself. 3) The non-terminal
concerned must be in the body of the production.
b) Synthesized attributes:-
It is defined by the semantic rule associated with the production at
the node. 2) Attributes values are confined to the children of node
and by itself. 3) The non terminal concerned must be in the head of
production. 4) Terminals have synthesized attributes which are
the lexical values (denoted by lexval) generated by the lexical
analyzer. 5) A SDD that uses only synthesized attribute is called S-
attributed.
(j) What is the use of dynamic pointer. 10
 Dynamic Pointers are sued for deallocating Activation Record
(AR).

Q] Explain in detall any two code optimization techniques with

appropriate examples.
 1) Common sub-expression elimination:-
The expression which has been already computed before and
appears again and again in the code for computation is known as
a common sub-expression. ii) As the name suggests, this
technique involves eliminating the redundant expressions to avoid
their computation again and again. The already computed result is
used in the further program wherever its required. Example:-
Code before Optimization Code after Optimization
S1= 4 x i S1=4 x i
S2=a[S1] S2=a[S1]
S3=4 x j S3=4 x j
S4=4 x i // Redundant Expression S5= n
S5=n S6= b[S1]+S5
S6=b[S4]+S5

2) Strength Reduction:-
As the name suggests, this technique involves reducing the
strength of the expressions by replacing the expensive and costly
operators with the simple and cheaper ones.
Example:
Code before optimization Code after optimization
B=Ax2 B=A+A
Here, the expression “A * 2 “ has been replaced with the
expression "A+A" because the cost of multiplication operator is
higher than the cost of addition operator.
(a) What is the output of the lex program?
 Lex program generates a lexical analyzer program in file
"lex.yy.c", which is a lexical analyzer program fof your program
Synthesized Attributes Inherited Attributes
1] An attribute is said to be 1] An attribute is said to be
synthesized attribute if its inherited attribute if its parse
parse tree node value is tree node value is determined
determined by the attribute by the attribute value at parent
value at child nodes. and/or siblings node.

2.] The value of the translation 2] Translation of a non-terminal

of the non-terminal on the left on right- hand side of a
side of the production as a production is determined in
function of translation of non- terms of a non-terminal on the
terminal on the right-hand side left-hand which side is called
(RHS) is called a synthesized an inherited attribute.
attribute (translation).
3] A Inherited attribute at node
3.] A synthesized attribute at n is defined only in terms of
node n is defined only in terms attribute values of n's parent, n
of attribute values at the itself, and n's siblings.
children of n itself.
4] Inherited attributes pass on
4.]Synthesized attributes pass information down the parse
information up the parse tree. tree.
on
5] Inherited attributes can't be
5] Synthesized attributes can contained by both but it is only
be contained by both the contained by non- terminals.
terminals and non-terminals.
6] Inherited attributes are
6] S-attributes are also called called value attributes (call by
reference attributes (call by value).
reference).
7] Example:
7] Example:
E→E1 + E2 (E.val = E₁.val + A→ XYZ (Y.val = 2*A.val)
E2.val) States that the translation in
Semantic action enclosed in RHS is determined by
parentheses states that translation associated with
translation in Left-Hand Side LHS of production.
(LHS) of production is
determined by adding together
translations associated on RHS
of production. 8
9) Define L-attributed definition. 18
 L-attributed definition is a type of SDD in which grammar
symbols can have synthesized or inherited attributes with
restriction(value of a node can be obtained from parent or left
sibling)
10) List the different evolution orders for SDDs
Bottom up order of evaluation in case of S-attributed definition
and arbitrary traversal in case of L- attribute definition.
11) State two steps to implement SDT's.
 1. Build parse tree and decorate it by assigning attribute values
to grammar symbols as per semantic rules. 2. From annotated
parse tree, build a dependency graph and determine evaluation
order.
1) Define activation record.
 Every time procedure/function(block of code) is invoked,
information about that function call is recorded on stack. The
block of information about activation of that function is called
activation record. It contains returning address, local data,
pointer to non local data of other blocks, actual parameter values,
etc.
2) What is dynamic binding?
 When binding of symbol/function with address is done at
runtime, it is referred as dynamic binding.
3) Define Static pointer.
Static pointer is a pointer present in activation record of a
function that points to nonlocal data present in other activation
record.
4) What is the use of display?
 Display is used to access nonlocal data in faster way. Each
activation record can have non local data and it is normally
accessed using chain of static pointers, which is a slow method.
Instead of static pointers, display is used which is array of
 Shift symbol on stack, Reduce, Accept (success), Error (Reject)

6) State the need of augmenting grammar. 16

 A grammar with additional unique starting rule S'S is referred
as augmented grammar. While augmenting any grammar, we just
add 1 extra rule S’->S where S is old starting symbol of Grammar
and S' is now new Starting symbol.
This will achieve unique success entry in table [1,$] as it's starting
rule finishes in Item 1. Purpose of augmenting grammar is to
indicate Parser where to stop parsing and announce acceptance
of input sentence (SUCCESS)
8) Define: Handle Pruning.
Solution:Handle pruning is a parsing process where input
sentence is reduced to starting non terminal of grammar. For
reduction we choose handle(substring) from sentential form) and
reduce it to left hand side NT of production.
11) Define closure (I) operation in LR parsers.
If I is a set of items for grammar G, then the set of items in
CLOSURE(I) is constructed from I by the rules: a) Every item in I is
in CLOSURE(1).
15) What do you mean by augmerited grammar? Solution:
 If G is a grammar with start symbol S, then G' the augmented
grammar for G, with new start symbol S' and production S' -> S

Q] State the configuration of LR Parser.

It's first component is stack contents and second component is
unexpanded input: 1) A configuration of LR parser is: (So X1
S1...Xm Sm, ai ai+1...an $). ii) Sm and ai decides the parser action
by consulting the parsing action table. iii) A configuration of a LR
parsing represents the sentential form: (X₁...Xm, aj ai+1... an $)
Q] What is preliminary scanning? 14
 There are certain task which needs to be performed on source
program before scanning starts for generating tokens, these tasks
are distinguished as preliminary scanner activities and can be
performed by a separate program Preliminary scanner. It's
activities include: removing comments from source program,
removing extra void spaces, counting lines, etc.
2) Define term token.
 A input sentence is broken down into series of primitive units
called tokens. These lexical units are generated by Lexical
analyser phase of compiler. Tokens are further used for checking
syntax of a statement.

3) What is the output of a LEX program?

 Lex program generates a lexical analyser program in file
"lex.yy.c", which is a lexical analyzer program of your language.

4) State the use of function 'retract ()’

 While recognizing tokens, sometimes lookahead pointer reads
one extra character to recognize token, but that extra character
read is not a part of current token (it may be starting part of next
token), so lexical analyser need to adjust position of lookahead
pointer by decrementing it and this adjustment is done in function
retract(). retract() function is used to recognize tokens properly.
5) Define lexeme
 Lexeme is a series of characters found in the input statement
and recognized as token.

7) State the pattern for regular expression" set of all strings of a's
and b's of length 2", in lex language notation.
 [ab][ab]
L-Attributed Definition
• L-Attributed Definitions contain both synthesized and inherited
attributes but do not need to build a dependency graph to evaluate
them. • The idea behind L-Attributed Definitions, between the
attributes associated with a production body, dependency-graph
edges can go from left to right, but not from right to left (hence "L-
attributed"). • The classes of syntax-directed definitions whose
attributes can always be evaluated in depth-first order are called
L-Attributed Definitions. • The L in the L-Attributed Definitions
stands for left because attribute information appears to flow from
left to right.
S-Attributed Definition
• The SDD is S-attributed if every attribute is synthesized. A
syntax-directed translation is called S-attributed if all its attributes
are synthesized. • For S-attributed SDD, the attributes are
evaluated in bottom-up order of the nodes of the parse tree. • The
attributes are evaluated by using postorder traversal of the parse
tree. • Since, bottom-up parsing uses postorder traversal, S-
attributed definitions can be implemented during bottom-up
parsing or LR parsing. • Synthesized attributes can be evaluated
by a bottom-up parser as the input is being parsed. • The parser
can keep the values of the synthesized attributes associated with
the grammar symbols on its stack.