Principles of Compiler DTTC A. A. Puntambekar Technical Publications Pune”Principles of Compiler Design First Edition : August 2006 = Alf rights reserved with Technical Publications, No part of this book should be repotuced in any form, Electronic, Mechanical, Photocopy or any information storage and Jetneval systems without prior permission in writing. from Technical Publications, Pun ISBN 81 - 8431 - 064 Published by : Technical Publications Pune’ #1, Amit Residency, 412, Shaniwar Peth, Pune - 411 030, india. Phone : (020) 24495496 , Tele/Fax : (020) 24495497 Email : [email protected] Head office ‘Technical Publications Printer : Alert DTPrinters, ‘Omkar Compound, Seno. 10/3, Pune Simages Rea, Pung 441 O44 4.4, Amit Residency, 412 Shaniwar Path, Pune -411030. India (026) 24495496, 66023831 Tole*Fax - (020) 24495497 Bangalore Pragati Book House 1676-140, Main Road, Prakash Nagar. Bangalore - 560021. Incia Phone : (080) 23324037, Fax : 23324848 Mumbai Pragati Books Pvt. Ltd. 385, SVP. Road, Rasohara, Co-op, Society, Gigaum, Mumbal - 400 004 india. Prone :(022} 23869876, 23656339 Hyderabad Nirali Book House 22,Shivam Endiave, 4-5 947, Bad: Chavadi, Hyderabad ~ 500095 India. Phone (040) 9545313 Chennai Pragati Books 1#9/1, Monticth Road, Behind Teas Mehal Egnore, Chennai -600 008, Inia. Ph = (044) 9918 3935 Mobile - 94440 01782 ‘Technical Books Distributor BB - Ground floor QUANTA ANAM’ 24m Stret, H-965/966, Opp, UC MAS ‘Anna Nagar (), Chennai - 800040, india Phone : (044) 26161903, Mobile No. : 9849324819 Jalgaon Pragati Books Pvt. Ltd. 24..V. Colani Marka, Navi Path, “Jalgaon = (02587) 425 (01, ica Prone 220395 Nagpur Pratibha Book Distributors ‘Shop No. 3, 1st Floor Lokratna, Commercial Gompiex, Zansi Rani Square, Stabuidi, Nagpur - 440012, india. Phone "(0712) 247123 Nasik Pragati Books Pvt. Lid. 741, Gaydhani Soak, Frat Flor, Ravine Kararja, Nasik «422001 India, Phone : (0259) 2500498 Func Pragati Books Pvt. Ltd. 119, Budhwar Poth, Jogestmari Mand lane, Pune - 411 002, tao ‘one (020) 24452044 Pragati Impex (Export Division) #21, Ami Residency, 412, Snanivar Path Pune - 411030, india 4919645021852, «919370286000 This edition can be exported from India only.Table of Contents Chapter-1__ Introduction to Compiling “7 1.2 Why to Write Compiler ? .. 1.2.1 Compiler: Analysis - Synthesis Model weaided 1.2.2 Execution of Program ............ 1.3 Compilation Process in Brief.......... 1.3.1 The Phases of Compiler ...........00.. ee 1.4 Cousins of the Compiler... 1.5 Concept of Pass..... 1.6 Types of Compiler..... 1.7 Bootstrapping of Compiler ..... 1.8 Interpreter ..... 1.9 Comparison of Compilers and Interpreters..... 1.10 Compiler Construction Tools.... Chapter-2 Lexical Analysis pote iE 2.1 Introduction 2.2 Role of Lexical Analyzer ..... 224 Tokers Paaine LANNE: oon nner nnn eens cement nRteRKSENNTeN RED 2-2 2.3 Input Buffering... Ae Bs : oa2.4 Specification of Tokens... 2.4.1 Strings and Language 2.4.2 Operations on Language. ...........60ccseeees ‘ oo 26 2.4.3 Regular Expressions ...... a divin anes meus ney bw e eee cee eee ney 2-7 2.4.4 Notations used for Representing Regular Expressions... Beste BSF 2.4.5 Non Regular Language _. ia rere ‘6 se unk 2.5 Recognition of Tokens .. 2.6 Block Schematic of Lexical Analyzer... 2.7 Automatic Construction of Lexical Analyser......-......-ccce-ceeeesseeeeeeeeee 2 14 2.8 LEX Specification and Features. 2.8.1 Pattern Matching based on NFA'S... 2... 2.8.2 DFA for Lexical Analyzers Chatper-3. Syntax Analysis 7 3.1 Introduction 3.1.1 Basic Issues in Parsing 3.1.2 Role of Parser... 3.1.3 Why Lexical and Syntax Analyzer are Separated Out’ 3.1.4 Types of Grammar....................45 3.2. Concept of Derivation ... 3.3 Ambiguous Grammar.. 3.4 Parsing Techniques ... 3.5 Top-Down Parser..... 3.5.1 Problems with Top-Down Parsing 3.5.2 Recursive Descent Parser . . 3.5.2.1 Predictive LL(1) Parser—. . 3.5.2.2 Construction of Predictive LL(1)Parser-. ee 3-20 LSA3.6 Bottom Up Parser —..... 3.6.1 Shift Reduce Parser — 3.6.2 Operator Precedence Parser— oo... sveee ese EOS 3.7 LR Parser-..... S71 SLR Paraet s.cavisemnenerereneseeuees 3.7.2 LR(k) Parser BTS LALR PARE 0005 .ceveevenvervases 3.8 Comparison of LR Parsers ~.. 3.9 Using Ambiguous Grammar -.. 3.10 Error Recovery in LR parser.. 3.11 Automatic Construction of Parser (YACC) ....... 3.11.1 YACC Specification... eee eee eeteeeeeeeeees Review Questions... Chapter-4’ © Semantic Analysis" 4.1 Need of Semantic Analysis —... 4.2 Type Analysis and Type Checking... 4.2.1 Type Expression 4.3 Simple Type Checker... 4.3.4 Type Checking of Expression... 0... ce cee cece stevereenees seecoeeoi 38 4.3.2 Type Checking of Statements 4.4 Equivalence of Type Expressions... 4.4.1 Structural Equivalence of Type Expressions . cee wD 4.4.2 Name Equivalence of Type Expressions. 4.5 Type Conversions Review Question: winesChapter-5 Syntax Directed Translation” 5.1 Syntax Directed Definitions(SDD).... 5.2 Construction of Syntax Trees..... 5.2.1 Construction for Syntax Tree for Expression. . picid. 5-10 5.2.2 Directed Acyclic Graph for Expression... 5-12 5.3 Bottom-Up Evaluation of S-Attributed Definitions ...... 5.3.1 Synthesized Attributes on the Parser Stack ................... ‘ 5-15 §.4 | -attributed Definitions 5-19 5.44 | attriputed Definition 5-19 5.4.2 Translation Scheme. az amaRER aa enone 2 --6-20 5.4.2.1 Guideline for Designing the Translation Scheme . scene © a were « ASE 5.5 Top-Down Translation... 5.5.1 Construction of Syntax Tree for the Translation Scheme . . 5.6 Bottom Up Evaluation of Inherited Attributes... Review Questions..... Chapter-6 _ Intermediate Code Generation 6.1 Benefits of Intermediate Code Generation 6.2 Intermediate Languages 6-2 8.2.1 Types of Three Address Statements..........0.2.ccecceereeee feces 83 6.2.2 Implementation of Three Address Code / “i on * . 6-4 6.3 Generation of Three Address Code... 6.4 Declarations... 6.5 Assignment Statements 6.5.1 Type Conversion . 6.6 Arrays....... AY. IS “i % RAE6.7 Boolean Expressions 6.7.1 Numerical Representatio 6.7.2 Flow of Control Statements. ...... 2... ...00eeceee ee eee eee eee seer etree 6-19 6.8 Case Statements ... 6.9 Backpaiching ... 6.9.1 Backpatching using Boolean Expressions. 6-23 6.9.2 Backpatching using Flow of Control Statements. 2... 0... 0eev ev eeeeeeeeee +1 6-29 6.10 Procedure Calls ..... 6.11 Intermediate Code Generation using YACC...... Review Questions Chapter-7_ Run Time Storage Organization 7.1 Source Language Issues... 7.2 Storage Organization ... 7.2.4 Sub Division of Run Time Memory ......... 0. 6.0.000cc cesses eens cece THD 7.3 Activation Record... 7.4 Storage Allocation Strategies... 7.4.1 Static Aliocation . cee 2 THB 7.4.2 Stack Allocation.......... oes . — as eau acxans TOE 7.4.3 Heap Allocation... 7.5 Variable Length Data 7.6 Access to Non Local Names.. 7.8.1 Static Scope or Lexical Scope... . Te SNES RTA RNR wave 7.6.2 Lexical Scope for Nested Procedures . eee Ce seam nN 7.7 Parameter Passing ...7.8 Symbol Tables 7.8.1 Symbol - Table Entries 7.8.2 How to Store Names in Symbol Table?........... 00... 0se eee eee eee e ee eee ee 7-20 7.8.3 Symbol Table Management. Review Questions Chapter-8. Code Generation 8.1 Introduction 8.2 Issues in Code Generation . 8.3 Target Machine Description.... 8.3.1 Cost of the Instruction .... . 8.4 Basic Blocks and Flow Graphs... 8.4.1 Some Terminologies used in Basic Blocks 6.2... ee eee rece eseee teens 8-7 8.4.2 Algorithm for Partitioning into Blocks 8.4.3 Flow Graph 8.5 Next-use Information. 8.5.1 Storage for Temporary Names. . 8.6 Register Allocation and Assignment.... 86.1 Global Register Allocation ................+5 renee — sone We 86.2 Usage Count 8-12 8.6.3 Register Assignment for Quter Loop .........5.0000.ceeeeeeseeeeeeeeeeeeeee 8.6.4 Graph Coloring for Register Assignment ......... 6.2.2.2 2... 8.7 DAG Representation of Basic Blocks ..... 8.8 Peephole Optimization .. 88.1 Characteristics of Peephole Optimization. .... . 8.9 Generating Code from a DAG... 8.9.1 Rearranging Order......... 8.9.2 Heuristic Ordering ...... ace mires B218.9.3 Labeling Algorithm ....... bee beet eb cceecveseeteteseeeuseees 2 BB 8.10 Dynamic Programming 8.10.1 Principle of Dynamic Programming ............... 8.10.2 Dynamic Programming Algorithm...” Bisse see SEER 8 See 8.11 Code Generator Generator Concept... 9.2 Classification of Optimization 9.3 Principle Sources of Optimization ..... 9.4 Optimizing Transformations .. 9.4.1 Compile Time Evaluation... 0... 6... 0. ce eee cere eee eee cove 93 9.4.2 Common Sub Expression Elimination.........0..0.ce000eeeeeeeese eee eee ee 993 9.4.3 Variable Propagation 9.4.4 Code Movement 9.4.5 Stength Reduction 0.000 cisvsiwseweseereesaavassenenea aan aewesuneseas’ 9-5 9.4.6 Dead Code Elimination 9-6 9.5 Optimization of Basic Blocks... 9.6 Loops in Flow Graphs... 9.7 Locai Optimization .... 9.7.1 DAG Based Local Optimization. . . 9.8 Global Optimizatior 9.8.1 Control and Data Flow Analysis ...... 9.9 Computing Global Data Flow Information... 9.9.1 Data Flow Analysis ........00.00eeseeeeeeereeee 9.9.2 Data Flow Properties. .............0.0.5 9.9.3 Representing Data Flow Information... 20.2... .2004 ent seep . capri wi)9.9.4 Meet Over Paths ............. cee cee ener es 9.9.5 Data Flow Equations .. 2... 266s e cee eee cnet cess eneeeeeeeeee 9.10 Iterative Data Flow Analysis...Introduction to Compiling 1.1 Introduction Compilers are basically translators. Designing a compiler for some language is a complex and time consuming process. Since new tools for writing the compilers are available this process has now become a sophisticated activity. While studying the subject compiler it is necessary to understand what is compiler and how the process of compilation can be carried out. In this chapter we will get introduced with the basic concepts of compiler. We will see how the source program is compiled with the help of va phases of compiler. Lastly we will get introduced with various. compiler construction tools. 1.2 Why to Write Compiler ? Compiler is a program which takes one language (source program) as input and translates it into an equivalent another language (target program). During this process of translation if some errors are encountered then compiler displays them as error messages. The basic model of compiler can be represented as follows - The compiler takes a source program as higher level languages Target program such as C, PASCAL, FORTRAN and converts it into low level language or a machine level language such as assembly language. Source program Fig. 1.1 Basic model of compiler 1.2.1 Compiler: Analysis - Synthesis Model The compilation can be done in to parts: analysis and synthesis. In analysis part the source program is read and broken down into constituent pieces. The meaning of the source string is determined and then an intermediate code is created from the input source program. In synthesis part this intermediate form of the source language is taken and converted into an equivalent target program. The analysis and synthesis model is as shown in fig. 12 (1-4)Principles of Compiler Design 422 Introduction to Compiling Fig. 1.2 Analysis - Synthesis model of compiler The analysis part is carried out in three sub parts - 1. Lexical Analysis ~ In this step the source program is read and then it is broken into stream of strings. Such strings are called tokens. Hence tokens are nothing but the collection of characters having some-meaning, 2. Syntax Analysis - In this step the tokens are arranged in hierarchical structure that ultimately helps in finding the syntax of the source string. 3. Semantic Analysis — In this step the meaning of the source string is determined In all these analysis steps the meaning of the every source string should be unique. Hence actions in lexical, syntax and semantic analysis are uniquely defined for a given language. 1.2.2 Execution of Program To create an executable form of your source program only a compiler program is not sufficient. You may require several other programs to create an executable target program. The target program generated by the compiler is processed further before it can be run which is as shown in the Fig. 1.3 (see Fig. 1.3 on next page). The compiler takes a source program written in high level language as an input and converts it into a target assembly language. The assembler then takes this assembly code as input and produces a relocatable machine code as output. Then a program called loader is called for performing the task of loading and link editing. The task of loader is to perform the relocation of an object code. Relocation of an object code means allocation of load time addresses which exist in the memory and placement of load time addresses and data in memory at proper locations. The link editor links the object modules and prepares a single module from several files of relocatable object modules to resolve the mutual references. These files may be library files and these library files may be referred by any program.Principles of Compiler Design 1-3 Introduction to Compiling Skeleton source program Preprocessor Relocatable machine code Fig. 1.3 Language processing Model 1.3 Compilation Process in Brief 1.3.1 The Phases of Compiler As we have discussed earlier the process of compilation is carried out in two parts: analysis and synthesis. Again the analysis is carried out in three phases: Lexical analysis, syntax analysis and semantic analysis. And the synthesis is carried out with the help of intermediate code generation, code generation and code optimization. Let us discuss these phases one by one. 4. Lexical Analysis - . The lexical analysis is also called scanning. It is the phase of compilation in which the complete source code is scanned and your source program is broken up into group of strings called token. A token is a sequence of characters having a collective meaning, For example if some assignment statement in your source code is as follows,Principles of Compiler Design 1-4 Introduction to Compiling total = count + rate *10 Then in lexical analysis phase this statement is broken up into series of tokens as follows- 1. The identifier total The assignment symbol eo The identifier count The plus sign The identifier rate ae The multiplication sign 7. The constant number 10 The blank characters which are used in the programming statement are eliminated during the lexical analysis phase. 2. Syntax Analysis - The syntax analysis is also called parsing. In this phase the tokens generated by the lexical analyser are grouped together to form a hierarchical structure. The syntax analysis determines the structure of the source string by grouping the tokens together. The hierarchical structure generated in this phase is called parse tree or syntax tree. For the expr mn total = count + rate *10 the parse tree can be generated as follows. Lo SN OS. rate 10 Fig. 1.4 Parse tree for total = count + rate + 10 In the statement ‘total = count + rate *10’ first of all rate*10 will be considered because in arithmetic expression the multiplication operation should be performed before the addition.And then the addition operation will be considered. For building such type of syntax tree the production rules are to be designed.The rules are usually expressed by context free grammar. For the above statement the production rules are - (1) expression — identifier (2) expression > numberPrinciples of Compiler Design 1-5 Introduction to Compiling (3) expression — expression1 + expression2 (4) expression -» expression* expression? (5) expression > (expression!) By rule (1) count and rate are expressions and by rule(2) 10 is also an expression. By rule (4) we get rate*10 as expression. And finally count +rate*10 is an expression. 3. Semantic Analysis Once the syntax is checked in the syntax analyser phase the next phase ic. the semantic analysis determines the meaning of the source string. For example meaning of source string means matching of parenthesis in the expression, or matching of if ..else statements or performing arithmetic operations of the expressions that are type compatible, or checking the scope of operation. i SN 40 Fig. 1.5 Semantic analysis For example, Thus these three phases are performing the task of analysis. After these phases an intermediate code gets generated. 4. Intermediate code generation — ‘The intermediate code is a kind of code which is easy to generate and this code can be easily converted to target code. This code is in variety of forms such as three address code, quadruple, triple, posix. Here we will consider an intermediate code in three address code form. This is like an assembly language. The three address code consists of instructions each of which has at the most three operands. For example, ty: = int to float (10) to: = rate*t ty: = count + ty total: = tyPrinciples of Compiler Design 1-6 Introduction to Compiling There are certain properties which should be possessed by’ the three address code and those are, a. Each three address instruction has at the most one operand in addition to the assignment. Thus the compiler has to decide the order of the operations devised by the three address code. b. The compiler must generate a temporary name to hold the value computed by each instruction. «. Some three address instructions may have fewer than three operands for example first and last instruction of above given three address code. 5. Code optimization - The code optimization phase attempts to improve the intermediate code. This is necessary to have a faster executing code. Thus by optimizing the code the overall running time of the target program can be improved. 6. Code generation - In code generation phase the target code gets generated. The intermediate code instructions are translated into sequence of machine instructions. MOV rate, Rj MUL #100, R, MOV count, Ry ADD — Ry, Ry _ MOV R;, total. Symbol table management To support these phases of compiler a symbol table is maintained. The task of symbol table is to store identifiers (variables) used in the program. The symbol table also stores information about attributes of each identifier. The attributes of identifiers are usually its type, its scope, information about the storage allocated for it. The symbol table also stores information about the subroutines used in the program. In case of subroutine, the symbol table stores the name of the subroutine, number of arguments passed to it, type of these arguments, the method of passing these arguments(may be call by value or call by reference) return type if any. Basically symbol table is a data structure used to store the information about identifiers. The symbol table allows us to find the record for each identifier quickly and to store or retrieve data from that record efficiently. During compilation the lexical analyzer detects the identifier and makes its entry in the symbol table. However, lexical analyzer can not determine all the attributes of an identifier and therefore the attributes are entered by remaining phases of compiler.Principles of Compiler Design 1-7 Infroduction to Compiling Various phases can use the symbol table in various ways. For example while doing the semantic analysis and intermediate code generation, we need to know what type of identifiers are. The during code generation typically information about how much storage is allocated to identifier is seen. Error detection and handling To err is human. As programs are written by human beings therefore they can not be free from errors. In compilation, each phase detects errors. These errors must be reported to error handler whose task is to handle the errors so that the compilation can proceed. Normally, the errors are reported in the form of message. When’ the input characters from the input do not form the token, the lexical analyzer detects it as error. Large number of errors can be detected in syntax analysis phase. Such errors are popularly called as syntax errors. During semantic analysis; type mismatch kind of error is usually detected. Example of compilation For statement a = b + c * 60; write all compilation phases with input and output to each phase. Fig. 1.6 see on Next Page . Front end back end Front end Intermediate Fig. 1.6(a) Front end-Back end model Different phases of compiler can be grouped together to form a front end and back end. The front end consists of those phases that primarily dependant on the source language and independent on the target language. The front end consists of analysis part. Typically it includes lexical analysis, syntax analysis, and semantic analysis. Some amount of code optimization can also be done at front end. The back end consists of those phases that are totally dependent upon the target language and independent on the source language. It includes code generation and code optimization. The front end back end model of the compiler is very much advantageous because of following reasons - 1. Keeping the same front end and attaching different back ends one can produce a compiler for same source language on different machines.Principles of Compiler Design 1-8 Introduction to Compiling 7 Input processing in compiler Output a= bye +60 id= i +60 Token stream Syntax tree ZN, ia TS ‘Semantic tree id aN 45° intto float 60 Symbol table t, : = intlofloat (60) 1 :=idg*t, MOVE ida, Ry MULF #60.0, R, MOVF idy,Ry ADDF 2. R; MOVF R,, idy Intermediate code Optimized code Machine code Fig. 1.6Principles of Compiler Design 1-9 Introduction to Compiling 2. Keeping different front ends and same back end one can compile several different languages on the same machine. 1.4 Cousins of the Compiler Sometimes the output of preprocessor may be given as input to the compiler. Cousins of compiler means the context in which the compiler typically operates. Such contexts are basically the programs such as preprocessor, assembiers, loaders and link editors. Let us discuss them in detail. 1. Preprocessors — The output of preprocessors may be given as the input to compilers. The tasks performed by the preprocessors are given as below- © Preprocessors allow user to use macros in the program. Macro means some set of instructions which can be used repeatedly in the program. Thus macro preprocessing task is be done by preprocessors. * Preprocessor also allows user to include the header files which may be required by the program. For example #include By this statement the header file stdio.h can be inclided and user can make use of the functions defined in this header file. This task of preprocessor is called file inclusion. Skeleton, Byoproceonor: i Machine pea cree ed rogram Fig. 1.7 Role of preprocessor For a macro there are two kinds of statements macro definition and macro use. The macro definition is given by keyword like “define” or “macro” followed by the name of the macro. For example : # define P 3.14 2. Assemblers - Some compilers produce the assembly code as output which is given to the assemblers as an input. The assembler is a kind of translator which takes the assembly program as input and produces the machine code as output.Principles of Compiler Design 1-10 Introduction to Compiling Source [program] program Fig. 1.8 Role of assembler An assembly code is a mnemonic version of machine code. The typical assembly nstructions are as given below - MOV a, RI MUL #5,R1 ADD #7,RE MOV R1b The assembler converts these instructions in the binary language which can be understood by the machine. Such a binary code is often called as machine code. This machine code is a relocatable machine code that can be passed directly to the loader/linker for execution purpose. The assembler converts the assembly program to low level machine language using two passes. A pass means one complete scan of the input program. The end of second pass is the relocatable machine code. 3. Loaders and Link Editors - Loader is a program which performs two functions: loading and link editing. Loading is a process in which the relocatable machine code is read and the relocatable addresses are altered. Then that code with altered instructions and data is placed in the memory at proper location. The job of link editor is to make a single program from several files of relocatable machine code. If code in one file refers the location in another file then such a reference is called external reference. The link editor resolves such external references also. 1.5 Concept of Pass One complete scan of the source language is called pass. It includes reading an input file and writing to an output file. Many phases can be grouped one pass. It is difficult to compile the source program into a single pass, because the program may have some forward references. It is desirable to have relatively few passes, because it takes time to read and write intermediate file. On the other hand if we group several phases into one pass we may be forced to keep the entire program in the memory. Therefore memory requirement may be large. In the first pass the source program is scanned completely and output will be an easy to use form which is equivalent to the source program along with the additionalaa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.Pi jof Compiler Design 1-13 Introduction to Compiling 1.9 Comparison of Compilers and Interpreters In interpreter the analysis phase is same as compiler i.e. lexical, syntactic and semantic analysis is also performed in interpreter. In compiler the object code needs to be generated whereas in interpreter the object code needs not to be generated. During the process of interpretation the interpreter exists along with the source program. Binding and type checking is“dyniamic in case of interpreter. The interpretation is less efficient than compilation. This is because the source program has to be interpreted every time it is to be executed and every time it requires analysis of source program. The interpreter can be made portal as they do not produce the object code which is not possible in case of compiler. Interpreters save time in assembling and linking. Self modifying program can be interpreted but can not be compiled. Design of interpreter is simpler than the compiler. Interpreters give us improved debugging environment as it can check the errors like out of bound array indexing at run time. Interpreters are most useful in the environment where dynamic program modification is required. 1.10 Compiler Construction Tools Writing a compiler is tedious and time consuming task, There are some specialized tools for helping in implementation of various phases of compilers. These tools are called compiler construction tools. These tools are also called as compiler-compiler, compiler-generators, or translator writing system. Various compiler construction tools are given as below- 1. Scanner generator - These generators generate lexical analysers. The specification given to these generators are in the form of regular expressions. The UNIX has utility for a scanner generator called LEX. The specification given to the LEX consists of regular expressions for representing various tokens. 2. Parser generators - These produce the syntax analyzer. The specification given to these generators is given in the form of context free grammar. Typically UNIX has a tool called YACC which is a parser generator. 3. Syntax-directed translation engines - In this tool the parse tree is scanned completely to generate an intermediate code. The translation is done for each node of the tree. 4, Automatic code generator - These generators take an intermediate code as input and converts each rule of intermediate language into equivalent machine language. The template matching technique is used. The intermediate code statements are replaced templates that represent the corresponding sequence of machine instructions.Principles of Compiler Design 1-14 Introduction to Compiling 5. Data flow engines - The data flow analysis is required to perform good code optimization. The data flow engines are basically useful in code optimization. In this chapter we have discussed the fundamental concept of compiler. Now we will discuss every phase of compiler in detail in further chapters. Review Questions What 1s compiler? Explain analysis -synthesis mode! of compiler? With a neat block diagram, explain various phases of compiler. What are the advantages of front-end and back end of compiler ? Explain the concept of compiler-compiler. nk ON goaLexical Analysis 2.1 Introduction The process of compilation starts with the first phase called lexical analysis. In this phase the input is scanned completely in order to identify the tokens. The token structure can be recognized with the help of some diagrams. These diagrams are popularly known as finite automata. And to construct such finite automata regular expressions are used. These diagrams can be translated into a program for identifying tokens. In this chapter we will see what the role of lexical analyzer in compilation process is. We will also discuss the method of identifying tokens from source program. Finally we will learn a tool, LEX which automates the construction of lexical analyzer. 2.2 Role of Lexical Analyzer Lexical analyzer is the first phase-of compiler. The lexical analyzer reads the input source program from left to right one character at a time and generates the sequence of tokens. Each token is a single logical cohesive unit such as identifier, keywords, operators and punctuation marks. Then the parser to determine the syntax of the source program can use these tokens. The role of lexical analyzer in the process of compilation is as shown below ~ Fig. 2.1 Role of lexical analyzer As the lexical analyzer scans the source program to recognize the tokens it is also called as scanner. Apart from token identification lexical analyzer also performs following functions. (2-1)aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.Principles of Compiler Design 2-7 Lexical Analysis © L* is a set of strings having all the strings including «. + L' is a set of strings except «. 2.4.3 Regular Expressions Regular are mathematical symbolisms which describe the set of strings of specific language. It provides convenient and useful notation for representing tokens. Here are some rules that describe define the regular expressions over the input set denoted by = «is a regular expression that denotes the set containing empty string. Rp If RI and R2 is regular expression then R = R1 + R2 (same can also be represented as R = R1}R2 ) is also regular expression which represents union operation. 3. If RI and R2 is regular expression the R = R1.R2 is also a regular expression which represents concatenation operation. 4. If RI is a regular expression then R = R1* is also a regular expression which represents kleen closure. A language denoted by regular expressions is said to be a regular set or a regular language. Let us see some examples of regular expressions. mm Example 2.4: Write a Regular Expression (R.E) for a language containing the strings of length too over S = 10, U. Solution: RE. = (0+1) (041) nm) Example 2.2: Write a regular expression for a language containing stings which end with “abb” over ? = {a, b} Solution: RE. = (a+b)*abb mm Example 2.3 : Write a regular expression for a recognizing identifier.} Solution : For denoting identifier we will consider a set of letters and dij identifier is a combination of letters or letter and digits but having first character as letter always. Hence R.E. can be denoted as, RE letter (letter+digit)* Where letter (A, B,...Z, a, b,...2) and digit = (0,1,2,...9). 2.4.4 Notations used for Representing Regular Expressions Regular expressions are tiny units, which are useful for representing the set of strings belonging to some specific language. Let us see notations used for writing the regular expressions.Principles of Com r Design = 2-8 Lexical Analysis 1. One or more instances - To represent one or more instances + sign is used. If r is a regular expression then r * denotes one or more occurrences of r. For example set of strings in which there are one or more occurrences of ‘a’ over the input set {a} then the regular expression can be written as a”. It basically denotes the set of {a,aa,aaa,aaaa,...}. 2. Zero or more instances - To represent zero or more instances * sign is used. If r is a regular expression then r* denotes zero or more occurrences of r. For example, set of strings in which there are zero or more occurrences of ‘a’ over the input set {a} then the regular expression can be written as a*. It basically denotes the set of {e, a, aa, aaa,...}. . Character classes — A class of symbols can be denoted by [ ]. For example [012] means 0 or 1 or 2. Similarly a complete class of a small letters from a to z can be represented by a regular expression [a-z]. The hyphen indicates the range. We can also write a regular expression for representing any word of small letters as [a-z]". 2.4.5 Non Regular Language A language which can not be described by a regular expression is called a non regular language and the set denoted by such language is called non regular set. There are some languages which can not be described by regular expressions. For example we cannot write a regular expression to check whether the given language is palindrome or not. Similarly we cannot write a regular expression to check whether the string is having balanced parenthesis. Thus regular expressions can be used to denote only fixed number of repetitions. Unspecific information cannot be represented by regular expression. 2.5 Recognition of Tokens For a programming language there aré various types of tokens such as identifier, keywords, constants, and operators and so on. The token is usually represented by a pair token type and token value. Fig. 2.7 Token representation The token type tells us the category of token and token value gives us the information regarding token. The token value is also called token attribute. During lexical analysis process the symbol table is maintained. The token value can be a pointer to symbol table in case of identifier and constants. The lexical analyzer reads the input program and generates a symbol table for tokens.Principles of Compiler Design For example — We will consider some encoding of tokens as follows. Token Code Value it 1 - else 2 - while 3 - for, 4 “ identifier 5 | Ptr to symbol tabie constant 6 _| Ptr to symbol table < 7 1 < 7 2 Consider, a program code as iffas10) 42; else i=i-2; Our lexical analyzer will generate following token stream 1,{8,1), (5,100), (7,1), (6,105), (8,2), (5,107), 10, (5,107), (9,1), (6,110), 2,(5,107), 10, (5,107), (9,2), (6,110). Lexical Analysis The corresponding symbol table for identifiers and constants will be,aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.Principles of Compiler Design 2-18 { print£("Usage:'s radius\n", argv[0]); exit (1); double radius = atof(argv(11): doubie area = area _of_circle(radius); printf ("Area of circle with radius $£ = %£\n", radius, area); return 0;//Returaing 0 The program Area.C can be taken as input test program. This program can be scanned by generated lex.yy.C (We have now generated lexyy.C using LEX tool). Hence the output obtained using following commands irvuot@localhost}# lex lexprog.1 {[email protected]]}# cc lex.yy.c {root@lovalhost]# ./a.Out Area.c 2.8 LEX Specification and Features To generate the lexical analyzer the automation tool like LEX is the efficient way. The specification file for LEX is based on the pattern-action structure as shown below : RK. {action} R, {action} Where each R; is a regular expression and each action ; is a program fragment describing what action is to be taken for corresponding regular expression. Each a¢ is a piece of program code that is to be executed whenever lexeme is matched by R, Regular expression Meaning e Matches with zero or more occurrences of preceeding ‘expression. For example 1* occurrence of 1 for any number of times. Matches any single character other than new line character. ul A character class which matches any character within the bracket, For example [a-z] maches with any alphabet in lower case. 0 Group of regular expressions together put into a new regular expression. “ The string written in quotes matches literally. For example “Hanuman” matches with the string Hanumaan. Matches with the end of line as last character.Principles of Compiler Design 2-19 Lexical Analysis + Matches with one or more occurrences of preceeding expression For example [0-9]+ any number but not empty string. ? Matches zero or one occurrence of preceding regular expression For example {+-]7(0-9}+ @ number with unary operator. & Matches the beginning of a line as first character. “ Used as for negation. For example [*verb] means except verb match with anything else. \ Used as escape metacharacter, For example \n is a newline character, \# prints the # literally I To represent the or i.e. another altemative. For example a | b means match with either a or b. We have to construct recognizer that looks for the lexemes stored in the input buffer. It works using these two rules - 1. I more than one pattern matches then recognizer has to choose the longest lexeme matched. 2. If there are two or more patterns that match the longest lexeme, the first listed matching, pattern is chosen. Lexical analysis is essentially a process of recognizing different tokens from the source program. This process of recognition can be accomplished by building a classical model called Finite State Machine (FSM) or a Finite Automaton (FA). The characteristics of token can be represented by certain mathematical notation called “regular expressions”. We have already discussed how to describe the strings belonging to certain language using regular expressions. We will see shortly that the finite state machines can be built for the regular expressions describing certain languages. The design of lexical analyzer involves three tasks (i) _ Representation of tokens by regular expression. Representation of regular expressions by finite state machines. Simulation of the behavior of finite state machine. These three steps lead to the design of lexical analyzer. The LEX compiler constructs a transition table for a finite state machine from regular expression patterns in the LEX specification. The lexical analyzer itself consists of finite automaton simulator that uses the transition table. This transition table basically looks for the regular expression patterns from the input string stored in the input buffer. The finite automata can be deterministic or non-deterministic in nature. A deterministic automaton is said to be deterministic if for each state S for every input a © Z at the most one edge is labeled a.Principles of Compiler Design 2-20 Lexical Analysis For example : Start Fig. 218 DFA A non deterministic finite automaton (NFA) is a set of states including. start state and few or more final state and for a single input there can be multiple transitions. For example: Stan Fig. 2.19 NFA To design the lexical analyzer generator first design the patterns of regular expressions for the tokens and then from these patterns it is easy to design a non-deterministic finite automata. But it is always easy to simulate the behavior of a DFA with a program; hence we have to convert the NFA drawn from the patterns to DFA. The design of lexical analyzer generator is based on two approaches — Pattern matching using NFA. * Using DFA for lexical analyzer. Let us discuss these approaches one by one. 2.8.1 Pattern Matching based on NFA’s In this method the transition table for each NFA can be drawn and each NFA is designed based on the pattern mentioned in the specification file of LEX. Hence there can be n number of NFA’s for n number of patterns. A start state is taken and with ¢ transitions all these NFAs can be connected together as shown below ;aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.Principles of Compiler Design 2-22 Lexical Analysis =O--O Fig. 2.21 (a) “(9+ Fig. 2. 21 (b) oO i Stat o Q 1 =O Fig. 2.21 (c) Pattern 1: Pattern 2: Pattern 3: The NFA can be drawn as a combination of pattern 1, pattern 2 and pattern 3 transition diagrams. Fig. 2.21 (d) NFA with patterns for matching of input string To summarize this one can say that LEX tries to match the input string with help of patterns one by one and it tries to match the longest lexeme.Principles of Compiler Design 2223 Lexical Analysis 2.8.2 DFA for Lexical Analyzers In this method the DFA is constructed from the NFAs drawn from patterns of regular expressions. Then we try to match the input string with each of the DFA. The accepting states are recorded and we go on moving on the transitions until. the input string terminates. If there are two patterns matching with the input string then the pattern which is mentioned first in the LEX specification file is always considered. For example consider the LEX specification file consists of 0 t) on 4 om" ui Now we have already built a NFA in earlier discussion for the above pattern. Let us design the DFA from NFA. State} Input —_/ Pattern matched o | 4 0137 | 248 | - - 243 | 8 | 59 ° a |s| 9 - sa | - | 69 ont 9|-| 9 oe es | - | 9 ont For constructing DFA from the given NFA we begin with all the ¢ reachable states from state 0. These ¢ reachable states are grouped together to form a state 0137. Then we obtain the a and b transition for state 0137 then we obtain state 248 and NIL respectively. Thus we proceed with newly generated states. And the complete DFA can be designed. To match the string 011 we get two matched pattern and those are 011 and 0*1*. But the pattern 011 will be considered as the matched pattern because it appears before 0*1* in the translation rules of the specification file. ‘As we have seen in the input buffer is used to store the input string. To recognize the lexeme actually two pointers are used: beginning pointer and forward pointer. The forward pointer moves in search of end of the current string (that can be white spaces or tabs or newline characters or some delimiters). This forward pointer when reaches to such termination mark it retracts and return the string between beginning pointer and forward pointer as token value. Thus the forward pointer is very much useful forPrinciples of Compiler Design 2-24 Lexical Analysis identifying the token. This pointer is also called as lookahead pointer. In the lexical analysis the lookahead operators are used in order to search the token from the input strings. Review Questions Wiat are the tasks of lexical analyzer? Write a short note on : input buffering. What is the role of regular expressions in lexical analyzer. Giew the block schematic of lexical analyzer? Explain, how lexical analyzer is generated using LEX. 6. Write a LEX program to count number of characters, number of words and total number of lines from input text. 7. Write a LEX program to reverse the given input string. Qaaaa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.Principles of Compiler Design 3-4 Syntax Analysis 3.1.4 Types of Grammar The context free grammar G is a collection of following things 1. V isa set of non terminals 2. 1 isa set of terminals 3. S isa start symbol 4. Pisa set of production rules. Thus G can be represented as G=(V,T.S,P) The production: rules are given in following form- Non Terminal > (V U T)* > Example 3.4: Let the language L = a"b" where n= 1 Let G = (VTS Where V=1S), T= lab] And § isa start symbol then > ack ~ ab The production rules actually defines the language ab” The non terminal symbol occurs at the left hand side . These are the symbols which need to be expanded.The terminal symbols are nothing but the tokens used in the language. Thus any language construct can be defined by the context free srammar. For example if we want to define the declarative sentence using context free grammar then it could be as follows- State -» Type List Terminator Type = int | float List > Listid List + id Terminator > ; Using above rules we can derive,Principles of Compiler Design 3-5 Syntax Analysis State Type List Terminator int List © ig i list ' Ya ts Fig. 3.4 Parse tree for derivation of int id, id, id; Hence int id, id, id; can be defined by means of above Context Free Grammar. Following rules to be followed while writing a CFG- 1) A single Non terminal should be at LHS. 2) The rule should be always in the form of LHS + RHS where RHS may be the combination of non terminal and terminal symbols. 3) The NULL derivation can be specified as NT = «. 4) One of the non terminals should be start symbol and conventionally we should write the rules for this non terminal. 3.2 Concept of Derivation Derivation from $ means generation of string w from §S. For constructing, derivation two things are important. i) Choice of Non terminal from several others. ii) Choice of rule from production cules ior corresponding, non terminal Instead of choosing the arbitrary Non terminal one can choose either i) Fither leftmost Non terminal in @ sentential form then: it is caliet leftmost derivation ii) Or rightmost Non terminal in a sentential form, then it is called rightmost derivation. For example: Let G be a context free grammar for which the production rules are given as below. IPrinciples of Compiler De: { 3-6 Syntax Analysis S +aB | bA A > alaS|bAA B -> b|bS|aBB We have to derive the string aaabbabbba using above grammai. Leftmost Derivation S + aB aaBB aaaBBB aaabSBB aaabbABB aaabbaBB aaabbabB aaabbabbS aaabbabbbA. aaabbabbba Rightmost Derivation S + aB aaBB aaBbS. aaBbbA aaBbba aaaBBba aaaBbbba aaabSbbba aaabbAbbba aaabbabbba The Parse Tree for the above derivations is as given belowaa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.jes of Compiler Design 3-14 Syntax Analysis We can eliminate left recursion as Torr Toerl je The grammar for arithmatic expression can be equivalently written as — ESE+T|T EoTE E>+TE je TFT ToT+F | F => Tort fe Fo CE > F3(E) | id 3) Left factoring If the grammar is left factored then it becomes suitable for the use. Basically left factoring is used when it is not clear that which of the two alternatives is used to expand the non terminal. By left factoring we may be able to re-write the production in which the decision can be deferred until enough of the input is seen to make the right choice. In general if A > aBjloBe is a production then it is not possible for us to take a decision whether to choose first rule or second. In such a situation the above grammar can be left factored as A saa A> bilB> For example consider the following grammar - S — iEtS | iEtSeS | a E+b The left factored grammar becomes S > iEtSS'[a S > Sle E>b 4) Ambiguity The ambiguous grammar is not desirable in top down parsing. Hence we need to remove the ambiguity from the grammar if it is present. For example : E3E4 | E*E fidPrinciples ofCompiler Design 3-15 ‘Syntax Analysis = is an ambiguous grammar. We will design the parse tree for id-+idsid as follows © © SOR Zoo O Sd%y GO O eo © © ® (a) Parse tree 1 (b) Parse tree 2 Fig. 3.12 Ambiguous grammer For removing the ambiguity we will apply one rule :if the grammar has left associative operator( such as +, -*, /) then induce the left recursion and if the grammar has right associative operator (exponential operator) then induce the right recursion. The unambiguous grammar is E> E+T ET ToT TOF Pid Note one thing that the grammar is unambiguous but it is left recursive and elimination of such left recursion is again a must. Top down parsers Predictive parsers LL(1) Parser Fig. 3.13 Types Top-down parsers BacktrackingPrinciples of Compiler Design 3-16 ‘Syntai Analysis There are two types by which the top down parsing can be performed 1. Backtracking 2. Predictive Parsing A backtracking parser will try different production rules to find the match for the input string by back tracking each time. The backtracking is powerful than predictive parsing. But this technique is slower and it requires exponential time in general. Hence Backtracking is not preferred for practical compilers. As the name suggests the predictive parser tries to predict the next construction using one or more lookahead symbols from input string. There are two types of Predictive parsers 1. Recursive Descent 2. LL) Parser. Let us discuss these types along with some example 3.5.2 Recursive Descent Parser A parser that uses collection of recursive procedures for parsing the given input string is called Recursive Descent (RD) Parser. In this type of parser the CFG is used to build the recursive routines. The RHS of the production rule is directly converted to a program. For each non terminal a separate procedure is written and body of the procedure (code) is RHS of the corresponding non terminal. Basic Steps for construction of RD parser The RHS of the rule is directly converted into program code symbol by symbol. 1. If the input symbol is non terminal then a call to the procedure corresponding to the non terminal is made. 2. If the input symbol is terminal then it is matched with the lookahead from input. The lookahead pointer has to be advanced on matching of the input symbol. 3. If the production rule has many alternates then all these alternates has to be combined into a single body of procedure. 4. The Parser should be activated by a procedure corresponding to the start symbol, Let us take one example to understand the construction of RD parser.Consider the gramntar having start symbol E, E >numT T >*numT |eaa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.Principles of Compiler Design 3-26 FIRST(FT’)=FIRST(F)={(id} Hence MIF,( And M[Fid]= TFT’ T72 "FT Ava A=T. FIRSTC*FT’)=(*) Hence M[T,"] = T > *FT’ Te Axa AT ase FOLLOW(T}={+,),$} Hence M[T,4] = Te MIT’) = Te MIT’,S] = Te F -4(E) Ava A=F, a=(E) FIRST((E))={ (1 Hence M[F,(= F-(E) Foid Asa A=FRa=id FIRST(id)=| id } Hence M[F,id]= F id The complete table can be as shown below — Syntax AnalysisPrinciples of Compiler Design 3-27 Syfitax Analysis E |G >TE| Err | Eror |E-»TE'| Error | Error Este} enor | enor | Ese | Ee ESFT| Error | Error | TFT] Error | Error e ir Tr | eror | Toe [TST] Ero | Toe | Toe F Fid | Eor | Error | F-»(E)| Error | Error Now the input string id + id * id $ can be parsed using above table. At the initial configuration the stack will contain start symbol E, in the input buffer input string is placed Stack Input Action SE id +id tid $ Now symbol E is at top of the stack and input pointer is at first id hence MIE,id] is referred. This entry tells us E -> TE’, so we will push E’ first then T. Input Action idtid*id$ | ETE idtideids | E-FT id+idtidgs | Fo id tid +idtids | Toe +idtid§ | Bete dts tid$ | TFT idtid$ | Eid cia s ‘id$ | ToT ig $ id §Principles of Gampiler Design 3-28 Syntax Analysis Thus it is observed that the input is scanned from left to right and we always follow left most derivation while parsing the input string. Also at a time only one input symbol is referred to taking the parsing action. Hence the name of this parser is LL(1).The LLC) Parser is a table driven predictive parser. The left recursion and ambiguous grammar is not allowed for LL(1) parser. 3.6 Bottom Up Parser — In bottom up parsing method, the input string is taken first and we try to reduce this string with the help of grammar and try to obtain the start symbol. The process of successfully as soon as we reach to start symbol. parsing halts ‘The parse tree is constructed from bottom to up that is from leaves to root. In this process, the input symbols are placed at the leaf nodes after successful parsing.The bottom up parse tree is created starting from leaves, the leaf nodes together are reduced further to internal nodes, these internal nodes are further reduced and eventually a root node is obtained. The internal nodes are created from the list of Terminal and non terminal symbols. This involves - Non Terminal for internal node = Non terminal U terminal In this process, basically parser is tries to identify RHS of production rule and replace it by corresponding LHS. This activity is called reduction. Thus the crucial but prime task in bottom up parsing is to find the productions that can be used for reduction. The bottom up parse tree construction process indicates that the tracing of derivations are to be done in reverse order. For example Consider the grammar for declarative statement , STL; T > int | float L Lid | id The input string is float id, id,id; Step 1: We will start from leaf node Parse Tree Step 1: Fig.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.Principles of Compiler Design 3-34 Syntax Analysis “Handle of right sentential form y is a production A ->f and a position of 7 where the string B may be found and replaced by A to produce the previous right sentential form in rightmost derivation of 7" For example Consider the grammar E > E+E E > id Now consider the string id+id+id and the rightmost derivation is => EtE >E+E+E => E+ E+ id => E+ id + id = id +id+id mm mmm The underlined strings are called handles. Right sentential Form Handie Production id + id + id id Eid E+id+id id Eid E+e+id id Exid E+E+E E+E E>E+E Be EE E>E+E E Thus bottom parser is essentially a process of detecting handles and using them in reduction. 3.6.1 Shift Reduce Parser — Shift reduce parser attempts to construct parse tree from leaves to root. Thus it works on the same principal of bottom up parser. A shift reduce parser requires following data structures — 1. The input buffer storing the input string. 2. A stack for storing and accessing the LHS and RHS of rules. The initial configuration of Shift reduce parser is as shown belowPrinciples of Compiler Design 3-32 Syntax Analysis Stack Input buffer The parser performs _ following ss ws basic operations Fig. 3.17 Initial Configuraiton 4. Shift: Moving of the symbols from input buffer onto the stack, this action is called shift 2. Reduce : If the handle appears on the top of the stack then reduction of it by appropriate rule is done. That means RHS of rule is popped of and LHS is pushed in. This action is called Reduce action. 3. Accept : If the stack contains start symbol only and input buffer is empty at the same time then that action is called accept. When accept state is obtained in the process of parsing then it means a successful parsing is done. 4. Error A_ situation in which parser can not either shift or reduce the symbols, it can not even perform the accept action is called as error. Let us take some examples to learn the shift-reduce parser p> Example 3.3: Consider the grammar E> E-E E> E*E Eid Perform Shift-Reduce parsing of the input string “id1-id2*id3” Solution : Stack Input Buffer Parsing Action s id1-ia2"id 3S Shift sid -1d2"ia3$ Reduce by E-> id Aa21d3$ Shift ia2rid3$ Shift "i038 Reduce by E-> id "id3$ Shift id3s Shift SE-E*id3 $ Reduce by E-> id SE-EE s Reduce by E> E°E SEE $s Reduce by E+ E-E SE $ AcceptPrinciples of Compiler Design 3-33 Syntax Analysis Here we have followed two rules 1, If the incoming operator has more priority than in stack operator then perform shift 2. If in stack operator has same or less priority than the priority of incoming operator then perform reduce. ww» Example 3.4: Consider the following grammar Sot T > int | float L > Lid | id Parse the input string int id,id; 1 Solution : ing shift reduce parser. Stack Input Buffer Parsing Action $s int id.ia:$ Shitt Sint ids Reduce by T- int st ides Shift STid ids Reduce by L— id STL ids Shift st, ids Shift STLid is Reduce by L -» L, id stl s Shift stu: s Reduce by S-» TL. ss $ Accept 3.6.2 Operator Precedence Parser — A grammar G is said to be operator precedence if it posses following properties — 1. No production on the right side is ¢ 2. There should not be any production rule possessing two adjacent non terminals at the right hand side. Consider the grammar for arithmetic expressions E> EAE | (B) | -E | id A>el-ith/ 1%aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.Principles of Compiler Design 3-39 ‘Syntax Analysis goto operation - The function goto can be defines as follows - If there is a production A >a #BB then goto(A >a * BBB) = A —>aBeB -That means simply shifting of © one position ahead over the grammar symbol(may be terminal or non terminal). The rule A +a BB is in | then the same goto function can be written as goto(B). um Example 3.5: Consider the grammar X > Xba Compute closure(1) and goto(1), Solution: Let 1: X 3Xb Closure(I) = X« Xb =Xoea The goto function can be computed as goto(I,X) = X > Xeb X > Xeb Similarly goto (I, a) gives X + ae Construction of canonical collection of set of item — 1. For the grammar G initially add S'S in the set of item C. 2. For each set of items 1; in C and for each grammar symbol X(may be terminal or non terminal) add closure(1,X).This process should be repeated by applying goto(I,X) for each X in I; such that goto(1;,X) is not empty and not in C, The set of items has to constructed until no more set of items can be added to C. Now we will consider one grammar and construct the set of items by applying closure and goto functions. Example : Eo EsT EoT ToaTF TOF FE) F idPrinciples of Compiler Design 3-40 ‘Syntax Analysis In this grammar we will add the augmented grammar E'->+E in the I then we have to apply closure(!) Ip: E 3eE E >eEsT EseT T eT Toor F +e(E) F oeid The item Ip is constructed starting from the grammar E’->« E, Now immediately right to is E. Hence we have applied closure(ig) and thereby we add E-productions with » at the left end of the rule. That means we have added E->« E+T and E->6T in Ip But again as we can see that the rule E> T which we have added, contains non terminal T immediately right to * So we have to add T-productions in I T- «TF and Took, In T-productions after ¢ comes T and F respectively. But since we have already added T productions so we will not add those. But we will add all the F-productions having dots. The F-+ (E) and F-+6 id will be added. Now we can see that after dot (and id are coming in these two productions. The ( and id are terminal symbols and are not deriving any rule. Hence our closure function terminates over here. Since there is no rule further we will stop creating Ip, Now apply goto(ly,E) Ese E Shit dotto E+E. E+eE+T fight E> Bort Thus I, becomes goto( lp, E) HEE E>EesT Since in I, there is no non terminal after dot we can not apply closure(1;) By applying goto on T of IpPrinciples of Compiler Design 3-41 Syntax Analysis goto(ly, T) bEoTe Totter Since in J) there is no non terminal after dot we can not apply closure(/) By applying goto on F of Ip goto(lo, T) Ix ToFe Since after dot in Iy there is notinghence we can not apply closure(|3). By applying goto on ( of lp, But after dot E comes hence we will apply closure on E,then on T,then on F. Boto(ly,( ) IT (¢ E) E-eEsT EoeT ToelTrF T+eF F->0(E) Foeid By applying goto on id of Ig gotollyid) Is: F > id « Since in Is there is no non terminal to the right of dot we can not apply closure function here. Thus we have completed applying gotos on Ip. We will consider 1; for applying goto. In Ip there are two productions E’'> E* and E — Ee + T.There is no point applying goto on E’> E+, hence we will consider E’> E« +T for application of goto.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.Principles of Gompiter Design 3-45 Syntax Analysis We can design a DFA for above set of items as follows - To state y Fig. 3.22 DFA for set of itemsPrinciples of Compiler Design 3-46 Syntax Anal ial state. Note that the In the given DFA every state is final state. The state I,, is DFA recognizes viable prefixes. For example - For the item 1, : goto (Ig) EsEe E> Bett fg goto (I,.+) 3 ESE teT Ig: goto (Ig,T) EE+T. ‘The viable prefixes E, E+ and E+T are recognized here continuing in this fashion The DFA can be constructed for set of items. Thus DFA helps in recognizing valid viable prefixes that can appear on the top of the stack. Now we will also prepare a FOLLOW set for all the non terminal as we need FOLLOW according to rule 2.b of parsing table algorithm. [Note for readers: Below is a manual method of obtaining FOLLOW. We have already discussed the method of obtaining FOLLOW by using rules.This manual method can be used for getting FOLLOW quickly] FOLLOW(E’) =As E’ is a start symbol $ will be placed ={$) FOLLOW(E) F’-+E_ that means E’=E =start symbol. -. we will add $. E—E+T the + is following E +. we will add +. F->(E) the ) is following E_ -.we will add ) -- FOLLOW(E) = {+,),$} FOLLOW(T) As E’ > E, ET the E’ B+ Ber =start symbol. -.we will add $. E>T+T ESOT The + is following T hence we will add +.Principles of Compiler Design 3-47 Syntax Analysis Tot As * is following T we will add * F~ (B) F(T) LET As ) is following T we will add ) FOLLOW(T) =(+,*,),$) FOLLOW(F) : As E> E, E> T and T + F the F’= E> E+T =start symbol. We will add §, E> T+T vEoT E> FT wToF The + is following F hence we will add +. ToT‘F ToOPT TOF As * is following F we will add * Fo (E) F(T) EoT F>(F) ToF As ) is following F we will add ) FOLLOW(F) =(+7,)51 Building of parsing table Now From canonical collection of set of items Consider Ip Ip: E! >+eE BE +eE+HT EeTaa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.Principtes,of Compiler Design Syntax Ana FOLLOW(E)=|+,)$} Hence add rule E ~ T in the row of state 2 and in the column of +,) and $. In the given example of grammar E ~ T is rule number 2 .. action[2,+] = 12, action[2,)]=12,action[2,$]=r2. Similarly, Now in state Iz Toke A>ae rule 2b AsT, a= F FOLLOW(F)=|+,"),$} Hence add rule T— F in the row of state 3 and in the column of +,%,) and $. In the given example of grammar T °F is rule number 4.Therefore action[3,+]=r4, action[3,)]=r4, action[3,$]=14.Thus we can find the match for the rule A+a « from remaining states Iq to 1) and fill up the action table by respective “reduce” rule. The table with all the action[ | entries will be State action goto fe] er} oto] s feftrie o | ss s4 1 sé Accept 2 m s7 2 m2 3 cs 4 4 4 4 SS S4 5 6 | 6 6 | 6 6 SS S4 7 | $5 84 8 86 sit 9 a | s7 adoa 10 3 3 8 3 Wt 6 6 Ss 6Principles of Compiler Design 3-50 Syntax:Analysis Now we will fill up the goto table for all the non terminals. In state Ip, goto(ly, E)=h Hence goto[0,EJ=1similarly goto(Ig, T)=lp, Hence goto[0,T]=2.Continuing in this fashion we can fill up the goto entries of SLR parsing table. Finally the SLR(1) parsing table will look as - State action goto io} +] el cf) s [ETF o | s5 s4 112] 3 1 sé Accept | s7 2 | 2 3 r4 | ra 4 | rd 4 | ss 84 e|2]{3 5 ro | 16 6 | 16 6 | ss s4 9 | 3 7 | $5 s4 10 8 sé sit 9 a | s7 nj 10 3 | 3 a] «2 " 56 | 5 6 | 5 Remaining blank entries in the table are considered as syntactical errors. Parsing the Input using parsing table - Now it’s the time to parse the actual string using above parsing table. Consider the parsing algorithm Input; The input string w that is to be parsed and parsing table. Output: Parse w if w ¢ L(G) using bottom up. If w ¢ L(G) then report syntactical error. Algorithm: 1. Initially push 0 as initial state onto the stack and place the input string with $ as end marker on the input tape. 2. If s is the state on the top of the stack and a is the symbol from input buffer pointed by a lookahead pointer then a) If action{sal=shift j then push a,then push j onto the stack.Advance the input lookahead pointer.Principles of Compiler Design b) If action{sa}=reduce A then pop 2*{B| symbols.f i 3-51 Syntax Analysis on the top of the stack then push A,then push gotofi,A] on the top of the stack. ¢) If action[s,a]=accept then halt the parsing process. It indicates the successful parsing. Let us take one valid string for the grammar (1) E> BT QEOT Q TOT @ TOF (5) F > (E) (©) F id Input string : id*id+id We will consider two data structures while taking the parsing actions and those are — stack and input buffer Stack Input buffer action table | goto table | Parsing action $0 i Shift S0id5 10F}3 Reduce by F ->id $0F3 U3si4 to.7}=2 Reduce by T > F sore [2-57 Shift $oT2'7 [Tid)=s5 Shift $0T2"7id5, (5.416 (7.F}=10 Reduce by F ->id $0 T2*7F10 Reduce by T > T'F soT2 Reduce by E ->T SOE1 Shift [ $OE1+6 igs. [6id}=s5 Shift SOE1+6105 $ (5.8)=6 [6.F}-3 Reduce by F rid S0E1+6F3 $ L3s}er4 (6.19 Reduce by TF _S0E1+6T9 $ (9sien (0.E]=1 ESET SOE1 s accept Accept In the above table at first row we get action(0,id]=s5,that means shift id from input suffer onto the stack and then push the state number 5. On the second row we get action[5,*] as 16 that means reduce by rule 6,F- id, hence in the stack id is replaced oy F. By referring goto[0,F] we get state number 3 hence 3 is pushed onto the stack.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.Principles of Compiler Design 3-56 ‘Syntax Analysis Ig:goto(1,C) Co aCe asd For Iy and Is there is no point in applying gotos. Applying gotos on a and d of Ig gives I, and [7 respectively. Hence we will apply goto on I, for C for the rule. Craec,$ Iy:goto(IgC) Coale, $ For the remaining states I7lg and Ig we can not apply goto.Hence the process of construction of set of LR(1) items is completed.Thus the set of LR(1) items consists of Ih to Ig states. Construction of canonical LR parsing Table - To construct the Canonical LR Parsing table first of all we will see the actual algorithm and then we will learn how to apply that algorithm on some example. The parsing table is similar to SLR parsing table comprised of action and goto parts. Input: nn Augmented grammar G’. Output : The canonical LR parsing table. Algorithm: 1. Initially construct set of items C=[Ip,I,12...I,} where C is a collection of set of LR(1) items for the input grammar G’. 2. The parsing actions are based on each item Ij, The actions are as given below- a) If[ Aa «a8, BI i table action|la]=shift j. b) If there is a production [A a © , al in I, then in the action table in I, and goto([,, a)= I, then create an entry in the action action{I,a] = reduce by A a. Here A should not be $’. ©) If there is a production S' — Se, $ in I; then actionfi,$] = accept. 3. The goto part of the LR table can be filled as :The goto transitions for state i is considered for non terminals only. If goto(l;,A)=I; then gotofl;,A]=). 4. Alll the entries not defined by rule 2 and 3 are considered to be “error”. ump Example 3.8: Construct the LR(1) parsing table for the following grammar ~Principles of Compiler Design 3-57 SyntaxiAnalysis @ sacc (2) C- ac G) Cd Solution: First we will construct the set of LR(1) items - ty Ig: goto (12,0), SoeS 8 S+CC+,$ S46Cc$ Cat, ald Ig-goto (I7.a) Cred, ald Cr acs C+ eads 1): goto (1.5) Coeds So Ses 1,:90t0 (Ip) 1h: goto (Ip,C) Coa. = oe Iygoto (14C) Coeds Cale, ald 1,: goto (Ip,8) tggoto (Ig,C) C+aeC,ald Crace,$ C+ eat, ald Coed, ald Ig: goto (Ig,) C+de,aid The DPA for the set of items can be drawn as follows. See Fi; .23 on next page Now consider I) in which there is a rule matching with [A >a *ap,b] as C- «aC, a/d and if the goto is applied on a then we get the state Is, Hence we will create entry action{0,al=shift 3. Similarly, In Ip Cred a/d Asa eaB,b A=C, a =6, a=d, B=s, b=a/d goto(lyd) hence action[0,dJ=shiét 4 For state ty3-58 Syntax Analysis Fig. 3.23 DFA [goto graph] Co dasa Avaea AzC,a. = d, aza/d action[4,a] = reduce by C+ d ie, rule 3 S'> Se Sink So we will create action[1,$]=accept. The goto table can be filled by using the goto functions.For instance goto(lg,S)=h.Hence goto[0,S]= up the LR(1) parsing table as follows - . Continuing in this fashion we can fill action goto a d $ s c ° 83 84 1 2 1 Accept 2 86 s7 5 3 83 sa 8 4 8 3 5 A 6 sé sT 9 7 8 8 2 2 9 2 The remaining blank entries in the table are considered as syntactical error. Parsing the Input using LR(t) parsing table - Using above parsing table we can parse the input string”aadd” as Thus the given input string parser. is successfully parsed using LR parser or canonical LR Stack Input buffer] action table | goto table} Parsing action $0 adds. action Oa J253 $0a3 adds action(3,a}=s3 Shit $0a3a3_ | ads action{3,d)=s4 Shift S0ada3d4 | 4S action(4.d]=13 13,c}=8 Reduce by C->d $0a3a3ce| 4s action{8,d}=12 B.C=8 Reduce by C> aC soasca_| as action{® d]=12 (0,0=2 Reduce by C-> aC soca 4 action(2,d]=s7 Shift socad7_| $ action(7,$]=13 [2.c}=5 Reduce by Cd soczcs | $ actionlS,$]=r4 Reduce by S + CC $0st 8 acceptPrinciples of.Compiler Design 3-60 ‘Syntax Analysis 3.7.3 LALR Parser In this type of parser the lookahead symbol is generated for each set of item. The table obtained by this method are smaller in size than LR(k) parser. In fact the states of SLR and LALR parsing are always the same. Most of the programming languages use LALR parsers. We follow the same steps as discussed in SLR and canonical LR parsing techniques and those are 1. Construction of canonical set of items along with the lookahead. 2. Building LALR Parsing table 3, Parsing the input string using canonical LR Parsing table Construction set of LR(1) items along with the lookahead.. The construction LR(1) items is same as discussed in. section 3.7.2. But the only difference is that: in construction of LR(1) items for LR parser, we have differed the two states if the second component is different but in this case we will merge the two states by merging of first and second components from both the states. For example in section 3.7.2 we have got I; and I, because of different second components, but for LALR parser we will consider these two states as same by merging these states.ie. 15 + 1, = Ise Hence Tyg :goto(ly a) Cae, a/d/§ Co ea, a/d/$ Cred ,a/d/$ Let us take one example to understand the construction of LR(1) items for LALR parser. ‘mp ~Example 3.8 : s$—>cc Cal Cod Construct set of LR(1) items for LALR parserPrinciples of Compiler Design 3-61 Syntax! Analysis Iai gz goto (12,0) S984 S4CC+$ S4sccs Cea, ald Igg'goto (I5,C) Coed, ald Coal + aldls 1}; goto (Ip.S) S488 Iz: goto (Ig.C) SC+CS C+ eats Coeds gg: goto (15,8) C+ asc, aids C+ 6aC, ald’ C3 +d, aldlS Ley! G00 (lg) Cade, ald/$ We have merged two states Iz and Ig and made the second component as a or d or $. The production rule will remain as it is. Similarly in ly and Iy .The set of items consist of states { Ip, ly, lo, 136, 147, Is, Igol- Construction of LALR Parsing Table — The algorithm for construction of LALR parsing table is as given below - 1. Construct the LR(1) set of items. 2. Merge the two states I, and J, if the first component (ic. the production rules with dots) are matching and create a new state replacing one of the older state such as Iy=I, U I}. 3. The parsing actions are based on each item |; The actions are as given below- a) If [ Aa eB, b] is in J; and goto(f, a)= I, then create an entry in the action table action|I.a]=shift j. b) If there is a production [Aa ©, a] in I, then in the action table actionfl,a] = reduce by Ara. Here A should not be S’. c) If there is a production S’ § ¢, $ in Ij then action|i,$] = accept. 4. The goto part of the LR table can be filled as :The goto transitions for state i is considered for non terminals only. If goto(1;,A)=I, then goto[l,,A]=).aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.Principles of Compiler Design 3-64 Syntax Analysis | Soas6as6cs9 | dS action(89,d}=r2 (36,C]=89 | Reduce by C- aC $0236C89 ds action{89,d]=r2 (0.C]=2 Reduce by C-> aC soce as. action{2.d}=s47 Shift $0C2d47 § action[47,$}r36_| [2,C]=5 Reduce by Co d | soc2cs 5 action[5.$]=r1 Reduce by S > CC $081 accept Thus the LALR and LR parser will mimic one another on the same input. 3.8 Comparison of LR Parsers — It’s the time to compare SLR, LALR and LR parser for the common factors such as size, class of CFG, efficiency and cost in terms of time and space. 1. SLR parser is smallest in size. It is easiest method of LR parsers. This method is based on FOLLOW function. The LALR and SLR have the same size. v w Canonical LR parser or LR parser is largest in size. LALR is applicable to a wider class of context free grammar than that of SLR. we LR parsers are most powerful then LALR and then SLR in the LR family. But most of the syntactic features can be expressed in the grammar of LALR. 6. LALR reacts differently than LR on erroneous inputs. Error detection is immediate in LR but not immediate in LALR. 7. The time and space complexity in LALR and LR is more. But efficient methods exist for constructing LALR parsers directly. 3.9 Using Ambiguous Grammar — As we have seen various parsing methods in which if at all the grammar is ambiguous then it creates the conflicts and we can not parse the input string with such ambiguous grammar. But for some languages in which arithmetic expressions are given ambiguous grammar are most compact and provide more natural specification as compared to equivalent unambiguous grammar. Secondly using ambiguous grammar we can add any new productions for special constructs. While using ambiguous grammar for parsing the input string we will use all the disambiguating rules so that each time only one parse tree will be generated for that specific input. Thus ambiguous grammar can be used in controlled manner for parsing the input. We will consider some ambiguous grammar and let us try to parse some input string.Principles of Compiler Design 3-65 Syntax Analysis Using precedence and associativity to resolve parsing action conflicts Consider an ambiguous grammar for arithmetic expression - E> E+E ESEE E> (BE) Eid Now we will build the set of LR(0) items for this grammar. 1 Ig3goto (1).*) Evee ES Ete Es eE+E E+ eE+E E> eEE E> sEE E> «(E) E> e(E) Es eid E->eid 1y2goto (Ip,E) Iggoto (1,,E) E+ (Es) E> Bete E> EWE 1p:9010 (Ip.() 172goto (14. E> (+E) ESE+Es E+ E+E E>sEo+e Eo eEE E>Ee E+ +(e) Es eid Igigoto (Is,E) 13:9010 (Ip\id) EGR Es E-seid ED Este E> Eee 149010 (1y.#) ESEteE —-——_ E>eE+E Fe:goto (Ie,)) Es eEE E+(E)e E> 0) E-seid Here FOLLOW(E)=(+,*,),$}. We have computed FOLLOW (E) as it will be required while processing. Now using the same rules of building SLR(0) parsing table we will generate the parsing table for above set of itemsPrinciples of Compiler Design . 3-66 Syntax Analysis. As we can see in the parsing table the shift/reduce conflicts occure at state 7 and 8. We will try to resolve it,how? Let us consider one string “id+id*id”. SOEt SOE1+4 $0 E1+4id3 SOE1+4E7 The conflict can be resolved by shit 5] « $0 E1+4E7°5 Shift $0 E1+4E7*5id3 Reduce by E > id $0 E1+4E7*5E8 Reduce by E + E°E SOE1+4E7 Reduce by E — E+E SOEt As * has precedence over + we have to perform multiplication operation first. And for that it is necessary to push * on the top of the stack. The stack position will be *aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.Technical Publications Pune || | | Rs. 230/- Cea us ACU ed ‘@ (020) 24495496/97, Email : [email protected] Aare WU AL Lele Coeel i)