A lex program to find sum of N numbers.

Example15:A lex program to find total vowels from the

Solution: input.
%{
# include<stdio⋅h>
Solution:
int sum, x, a [50]; %{
%} # include<stdio⋅h>
%% int w=0, vc=0;
[0 – 9]+ %}
{ x=atoi(yy text);
sum=0; printf ("\n");
%%
for (i=0; i<x; i++) [\t]+
{ printf ("\enter number"); {w++;]
scanf ("%d", &a[i]); [a e i o u A E I O U] {vc ++;}
sum + = a[i]; [⋅]
}
printf ("sum is /n=", sum);
+
return (0); {
} printf ("\n\n Total vowels %d is", vc;}
%% ⋅;
main() %%
{
printf ("enter how many numbers");
main()
yylex(); {
} printf ("enter input \n");
yyerror() yylex();
{ }
printf ("error");
}
yywrap() Example10:A lex program to count number of vowels
{ and number of words per line
return (1); and total number of lines ending with '·'.
} Solution: Solution: Solution:
Compiler Construction Lexical Analysis (Scanner)
% { # include <stdio·h>
2.26
Now compile this program as: int lcnt = 0, vcnt = 0, wno = 0;
$ lex sum·l %}
$ cc lex·yy·c - ll %%
$ ·/a·out [ · ]+ {lcnt ++; wno ++; printf ("lcnt = % d vowel = % d
enter how many numbers
word = % d \n", lcnt, vcnt, wno);
3
enter number 10 vcnt = 0; wno = 0;}
enter number 20 [ ]+ {wno ++;}
enter number 30 [aeiouAEIOU] {vcnt ++;}
→ sum is 60 ·;
We can also change the a·out file name that is we can use our own
%%
executable file.
$ lex sum·l main()
$ cc lex·yy·c - 0 sumout - ll { printf ("Enter input : \n");
$ ·/sumout yylex();
enter how many numbers printf (" \n Total lines = % d", lcnt);
2
}
enter number 5
enter number 10 sum is 15.
Example12: A lex program to find factorial of a given number. Example13:A lex program to find sum of first n numbers.
Solution: Solution:
%{ %{
# include<stdio⋅h>
# include<stdio⋅h>
int i, fact, n;
int i, x, sum = 0;
%}
%% %}
[0 – 9]+ %%
{ n = atoi (yytext); [0 – 9]+
for (i=1; i<=n; i++) {
fact = fact * i; x=atoi (yytext);
printf ("Factorial do no. % d is %d\n", n, fact); for (i=0; i<=x; i++)
return (0) {
%% sum=sum+i;
main() printf ("%d", i);
{ printf ("\n Enter number");
}
yylex();
} prinft ("The sum of first %d numbers is %d /n"; x, sum);
Output: return (0);
$ lex fact ⋅ l }
$ cc ⋅ lex ⋅ yy ⋅ c –ll %%
$ ⋅/a⋅out main()
Enter number {
5 printf ("\enter number \n");
Factorial of number 5 is 120 yylex();
enter number
}
4
Output:
factorial of number 4 is 24.
$ lex sum ⋅ l
Example18:A lex program that identifies tokens like id, if and $ cc lex ⋅ yy ⋅ c – 0 sumofn –ll
for. $ ⋅/sumofn
Solution: Enter number
%{ 5
include <stdio.h> 12345
%} The sum of first 5 numbers is 15
%% $ ⋅/ sumofn
[a-zA-z] [a-zA-z0-9]* {return id;} enter number
[iI] [fF] {return if;} 10
[Ff] [Oo] [Rr] {return for;} 1 2 3 4 5 6 7 8 9 10
%% The sum of first 10 numbers is 55.
main()
{ Recursive Descent Parsing (RDP) : A parse that uses a set of
printf ("\n Enter word"); recursive procedures to recognize its input without
yylex(); backtracking
}
Annotated parse tree
Handle A parse-tree, with values of its attributes at each node is called
The sentential form (string) which matches the RHS of annotated parse tree
production rule while reduction, then that string is called
"handle".
S-attributed Syntax-directed translation(SDT) fundamentally works by
The SDD is S-attributed if every attribute is synthesized. A adding actions to the productions in a context-free grammar,
syntax-directed translation is called S-attributed if all its resulting in a Syntax-Directed Definition (SDD)
attributes are synthesized. Syntax-directed translation (SDT) refers to a method of
For S-attributed SDD, the attributes are evaluated in bottom-up compiler implementation where the source language
order of the nodes of the parse tree. translation is completely driven by the parser.
The attributes are evaluated by using postorder traversal of the The main idea behind syntax-directed translation is that the
parse tree. semantics or the meaning of the program is closely tied to its
Since, bottom-up parsing uses postorder traversal, S-attributed syntax.
definitions can be implemented during bottom-up parsing or LR
parsing. Syntax-directed definition (SDD)
Synthesized attributes can be evaluated by a bottom-up parser A context-free grammar in which the productions are shown
as the input is being parsed. along with its associated semantic rules is called as a syntax-
directed definition.(SDD)
L-Attributed A SDD is a context-free grammar together with attributes and
L-Attributed Definitions contain both synthesized and inherited rules, where attributes are associated with grammar symbols
attributes but do not need to build a dependency graph to and rules are associated with production.
evaluate them. If S is a symbol and a is one of its attributes then we write S.a
The idea behind L-Attributed Definitions, between the which is value of a at a particular node of tree labeled S.
attributes associated with a production body, dependency-
graph edges can go from left to right, but not from right to left There are two classes of SDD's to construct translators:
(hence "L-attributed"). 1. S-attributed (LR-parsable)
The classes of syntax-directed definitions whose attributes can 2. L-attributed (LL-parsable)
always be evaluated in depth-first order are called L-Attributed
Definitions. BOOTSTRAPPING
Bootstrapping is a process in which simple language is used to
Some Lex Library functions are translate more complicated program which in turn may handle
1. yylex(): This function is used to start or resume scanning. The for more complicated program.
next call in program1 to yylex() will continue from the point Bootstrapping is an approach for making a self-compiling
where it left off. All codes in rule section are copied into yylex(). compiler that is a compiler written in the source programming
2. yytext(): Whenever a lexer matches a token, the text of the language that it determine to compile
token is stored in the null terminated string yytext. (work just A bootstrap compiler can compile the compiler and thus we can
like pointers in C). Whenever the new token is matched, the use this compiled compiler to compile everything else and the
contents of yytext are replaced by new token. future versions of itself.
3. yywrap():The purpose of yywrap() function to additional
processing in order to "wrap" things up before terminating. Recursive Decent Parser
When yylex() reaches the end of its input file, it calls yywrap( ), Left recursive grammars are not suitable. It accepts LL (1)
which returns a value of 0 or 1. If the value is 1, indicates that grammar. It uses recursive procedures. Parser requires more
no further input is available. By default it always return 1. space in memory since it is recursive. Precise error indication is
4. yyerror():The yyerror( ) function is called which reports the not possible. First and follow functions are not required.
error to the user.
Predictive Parser
Global optimization : The optimizing transformations are Left recursive grammars are not suitable.
applied over a program unit i.e. over a function or a procedure. It accepts LL (1) grammar.
It uses parser table.
Local optimization : The optimizing transformations are applied This parser requires less space in memory.
over small segments of a program consisting of a few It detects the errors using parse table.
statements. FIRST and FOLLOW functions are required.
A compiler is a program that reads a program written in one PARSERS
language - the source language and translates it into an The program performing syntax analysis is known as parser.
equivalent program in another language - the target language The main objective of the parser is to check the input tokens to
analyze its grammatical correctness.
CROSS COMPILER Parser is one of the components in a complier, which
A compiler which may run on one machine Definition: and determines whether if a string of tokens can be generated by a
produce the target code for another machine is known as cross grammar.
compiler.
Definition of Parsing
Sentinels Parsing takes input from the lexical analysis and builds a parse
The sentinel is a special character that cannot be part of the tree, which will be used in future steps to develop the machine
source program, and a natural choice is the character eof. code.
In sentinels we use special character that is not the part of To determine the syntactic structure of an input from lexical
source program. This character is at the end of each half. So analysis is called as parsing.
every time look ahead pointer checks this character and then The goals of parsing are to check the validity of a source string
the other half is loaded and to determine its syntactic structure.

Dead code PARSER GENERATOR (YACC)

Dead code is the code which can be omitted from a program YACC stands for "Yet Another Compiler – Compiler". YACC
without affecting the results. assists in the next phase of the compiler.
Dead code is detected by checking whether the value assigned YACC creates a parser which will be output in a form suitable
in an assignment statement is used anywhere in the program. for inclusion in the next phase.

Synthesized Attributes Attribute grammar

An attribute is said to be synthesized attribute if its parse tree Attribute grammar is a special form of context-free grammar
node value is determined by the attribute value at child nodes. where some additional information (attributes) is appended to
A synthesized attribute at node n is defined only in terms of one or more of its non-terminals in order to provide context-
attribute values at the children of n itself sensitive information.
Synthesized attributes pass on information up the parse tree.
Synthesized attributes can be contained by both the terminals Dependency Graph
and non-terminals. The inter-dependencies among the inherited and synthesized
attributes at the nodes in a parse tree can be shown by a
Inherited Attributes directed graph called a dependency graph.
An attribute is said to be inherited attribute if its parse tree
node value is determined by the attribute value at parent Code optimization involves improving the performance of
and/or siblings node. code in terms of speed, memory usage, or efficiency. Here
A Inherited attribute at node n is defined only in terms of are several key optimization techniques:
attribute values of n’s parent, n itself, and n’s siblings.
Inherited attributes pass on information down the parse tree. Loop Optimization, Inline Expansion, Minimizing
Inherited attributes can’t be contained by both but it is only Function Calls, Memory Optimization, Data Structure
contained by non-terminals. Optimization.

Definition of Basic Block : Loop optimization is the process of improving the performance
A basic block is a sequence of consecutive statement in which of loops in your code. Since loops are often executed
flow of control enters at the beginning and leaves at the end repeatedly, optimizing them can significantly reduce execution
without halting or branching except at the last instruction. time, especially when dealing with large datasets.
Top-down Parsing SLR Parser
Top-down parser uses derivation. SLR parser is very easy and cheap to implement
Parsing start from starting symbol and derive the input string. SLR parser is the smallest in size. Error detection is not
Left-recursion and backtracking are two problems occurring in immediate in SLR parser. SLR parser fails to produce a parsing
this parsing. table for a certain class of grammars.
Ambiguous grammars are not suitable for top-down parsing.
Precise error indication is not possible. LALR Parser
This uses LL(1) grammar. LALR parser is also easy and cheap to implement. LALR and SLR
have the same size. Error detection is not immediate in LALR
Bottom-up Parsing parser. It is intermediate in power between SLR and CLR i.e.,
It uses reduction. SLR ≤ LALR ≤ CLR.
Parsing start from input string and reduce to the starting
symbol. CLR Parser
No left-recursion and backtracking problems CLR parser is expensive and difficult to implement. CLR parser
It accepts ambiguous grammar. is the largest. Error detection can be done immediately in CLR
Precise error indication is possible. parser. It is very powerful and works on a large class of
This uses LR grammar. grammar.

LLParser Single Pass Compiler

The first L in the LL parser is for scanning the input from left to A one-pass complier is that passes through the source code of
right, and the second L is for the leftmost derivation. each compilation unit only once.
LL follows the leftmost derivation. A one-pass complier does not "look back" at code it previously
An LL parser amplifies non – terminals. processed.
LL parser constructs a parse tree in a top-down manner It is less efficient code optimization and code generation.
It ends whenever the stack in use becomes empty. It is also called as narrow compiler
It starts with the start symbol. Single-pass compiler requires large memory for compilation
It is easier to write. They are faster speed in compilation process.

LRParser Multi-Pass Compiler

The L in LR parser is for the left to right, and R stands for A multi-pass compiler is a type of complier that processes the
rightmost derivation in the reverse order. source code of a program several times
LR follows rightmost derivation in reverse order. Each pass takes the result of the previous pass as the input and
Terminals are condensed in LR parser creates an intermediate output.
LR parser constructs a parse tree in a bottom-up manner. Better code optimization and code generation.
It starts with an empty stack. It is also called as wide compiler.
It ends with the start symbol. Multi-pass compiler requires small memory for compilation.
It is difficult to write. They are slower speed in compilation process. As more number
of passes means more execution time.
APPLICATIONS OF SDT
The main application of syntax-directed translation is DAG for Expressions
construction of syntax trees. The use of syntax trees as an A Directed Acyclic Graph (DAG) for an expression identifies the
intermediate representation in many compilers. common subexpressions in the expression.
DAG is constructed similar to syntax tree. A DAG has a node for
every sub-expression of an expression; an interior node
Flow Graphs
represents an operator and its children represent its operands.
A graph representation of three address statement, called a
The difference between syntax tree and DAG is a node N in a
flow graph.
DAG has more than one parent if N represents a common sub-
expression.