SYLLABUS Compiler Design (CS601PC) UNIT-1 Introduction : Language Processors, the structure of a compiler, the sclence of building a compiler, Programming language basics. Lexical Analysis : The Role of the Lexical Analyzer, Input Buffering, Recognition of Tokens. The Lexleal-Analyzer Generator Lex, Finite Automata, From Regular Expressions to Automata, Design of a Lexical-Analyzer Generator, Optimization of DFA-Based Pattern Matchers. (Chapter - 1) UNIT - It ‘Syntax Analysis: Introduction, Context-Free Grammars, Writing a Grammar, Top-Down Parsing, Bottom-Up Parsing, Introduction to LR Parsing : Simple LR. More Powerful LR Parsers, Using Ambiguous Grammars. Parser Generators. (Chapter - 2) UNIT - III ‘Syntax-Directed Translation : Syntax-Directed Definitions, Evaluation Orders for SDD’s, Applications of ‘Syntax-Directed Translation, Syntax-Directed Translation Schemes, and Implementing L-Attributed SDD's. Intermediate-Code Generation : Varlants of Spntax Trees, Three-Address Code, Types and Declarattons. Type Checking, Control Flow, Back patching, Switch-Statemeits, Intermediate Code for Procedures. (Chapter -5) UNIT-IV . Run-Time Environments Storage organization, Stack Allocation of Space, Access to Nonfocal Data on the Stack, Heap Management, Introduction to Garbage Collection, Introduction to Trace-Based Collection. Code Generation : Issues in the Design of a Code Generator. The Target Language, Addresses in the Target Code, Basic Blocks and Flow Graphs, Optimization of Basic Blocks, A Simple Code Generator. Peephole Optimization, Register Allocation and Assignment, Dynamic Programming Code-Generation. (Chapter - 4) UNIT-V. ‘Machine-Independent Optimizations : The Principal Sources of Optimization, Introduction to Data-Flow ‘Analysis, Foundations of Data-Flow Analysis, Constant Propagation, Partial-Redundancy Elimination, Loops In Flow Graphs. (Chapter -5) wy ‘Seamed nth CamScannerTABLE OF CONTENTS Chapter-1 Basic Introduction and Lexical Analysis (1-1) to (1-28) 1.1 Language Processors...» 1.2 The Structure of Compi 1.3. Science of Building a Compiler ......++ +--+ 1-5 1.4 Programming Language Basics. . 1-7 1.5 The Role of Lexical Analyzer. 1.6 Input Buffering . seceseeerereT=1O 1.7 Recognition of Tokens .......+ w1- 1.8 Lexical Analyzer Generator . . 1-22 1.9 Optimization of DFA based Pattern Matchers 1 - 23 ‘Multiple Choice Questions for Mid Term Exam. ........+---++ 1-27 Fill in the Blanks for Mid Term Exam 1-27 Chapter-2 Syntax Analysis (2-1) to (2-40) 2.1 “Introductioin to Syntax Analysis .... 2-1 22° Context Free Grammar .. 23° Writing a Grammar 2.4 Parsing Techniques... 2.5 TopDownParsing........0..00c00t+008 2.6 Bottom Up Parsing sees Ded 2.7 Introduction toLR Parsing ......+-406+0402-17 2.8 Using Ambiguous Grammar.........6.+++ 2-34 2.9 Parser Generators . 2-36 Chapter-3 Syntax 3a 32 33 34 35 36 37 38 39 3.10 3.1 342 3.43 3.4 Multiple Choice Questions for Mid Term Exam Fill in the Blanks for Mid Term Exam 2-49 irected Translation and Intermediate Code Generation (3-1) to (3-32) Syntax Directed Definition ......2...6..06.3-1 Evaluation Orders for SDD......- 33 Applications of Syntax Directed Translation . 3-6 Syntax Directed Translation Schemes, ee) Implementing L Attributed SDD......... Concept of Intermediate Code. . Variants of Syntax Trees Three Address Code ... ‘Types and Declarations ‘Type Checking . Control Flow... Backpatching. . ‘Switch Statement. . Intermediate Code for Procedures... ‘Multiple Choice Questions for Mid Term Exam... . Fill in the Blanks for Mid Term Exam Chapter-4 Run-Time Environment and Code 44 42 Generation (4-1) to (4-32) Storage Organization. ..... wel Stack Allocation of Space w ‘Seamed nth CamScanner43 Multiple Choice Questions 44 Heap Management........... | See a ent Wee 4g Inroduction to Garbage Colleton. | Fill in the Blanks for Mid Term Exani 4-32 4.7 _ Issues in Design of Code Generator ........ 4-12. | Chapter-5 Machine Independent | Optimizatic 5 - 1) to (5 - 15) 48. The Target Language. . e413 | een eae d = | 8.1 Principal Sources of Optimization ....-.+-++ 49) A the Target ° sses in the Target Code.............4-13 | §.2 Introduction to Data Flow Analysis . 4.10 Basic Blocks and Flow Graphs . se4=14| 53 Foundation Data Flow Analysis . 4.11 Optimization of Basic Blocks.............4-15 | 5.4 Constant Propagation 5-6 4.12 A Simple Code Generator. . ses4-21 | 5.5 Partial Redundancy Elimination ......-++++.5-7 4.13. Peephole Optimization ..........:..606-4-27 5.6 Loops in Flow Graphs. . 4.14 Register Allocation and Assignment... 24-28 Multiple Choice Questions 4.15. Dynamic Programming Method of Code Generation | ae 54 oa coeeaiee | Fill in the Blanks for Mid Term Exam ...... 5-14 | Solved University Question Papers (8-1) to(S-9) Solved Model Question Paper (S - 10) to (S - 11) TECHNICAL PUBLICATIONS - An ptt or knoe ‘Seamed nth CamScannerUNIT Basic Introduction and Lexical Analysis fa 4.4 Language Processors Q.1 What is translator ? Give examples of translators. OS [INTU : Part A, Marks 2) Ans. : + Translator is a kind of program that takes one form of program as input and converts it into another form. The input program is called source language and the output program is called target language. * For example - There are two types of translators compiler and assembler. Q2 Explain the roles of linker, loader and Preprocessor. USP [INTU : Part B, Marks 5] Ans. : Skeleton source program ~™ Preprocessed Source program a ‘Target assembly program Relocatable ‘machine code Loadertink-editor . Library, relocatable Execuable machine See Fig, Q.2.1 (a) Process of execution of program a-1) * The compiler takes a source program written in high level language as an input and converts it inty a target assembly language. The assembler then takes this target assembly code as input and produces a relocatable machine code as an output Then a program 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. Executable 12 The Structure of Compiler Q.3 What is compiler ? c&{JNTU : Part A, Marks 2] * 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 Tepresented as follows. (Refer Fig. Q.3.1) * The compiler takes a source program as highet evel languages such as C, PASCAL, FORTRAN and converts it into low level language or 2 ‘machine level language such as assembly language. ‘Seamed nth CamScannerCompiler Design Input on Target program Fig. Q.3.1 Compiler Q.4 What are two parts of a compilation ? Explain briefly. SS [INTU : Part A, May-18, Marks 2] Ans.:¢ The compilation is done in two parts - Analysis and Synthesis. In analysis part the source program is read and broken down into constituent pieces. The syntax and 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. During this process if certain code has to be optimized for efficient execution then the required code is optimized. The analysis and synthesis model is as shown in Fig. Q-4.1. Compiler ‘Analysis }=[Synthesis] Source program| Fig. Q.4.1 Analysis and synthesis mode! Q.5 Explain the various phases of a compiler with an Illustrative example. [GP LINTU : Part B, Nov 15, 16, Marks 10] Ans, : 1. 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. “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. ‘ln 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 TBF recuicas PUBLICATIONS- Anup trust for knowedga Basie Introduction and Lexical Analysis hierarchical structure generated in this phase is called parse tree or syntax tree. 3. Semantic Analysis * Once the syntax is checked in the syntax analyser phase the next phase ie. 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. LY». “UN 2 tale int 19 float | 10 Fig. Q.5.1 Semantic analysis + 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, 5. Code Optimization * The code optimization phase attempts to improve the intermediate code. © This is necessary to have a faster executing code or less consumption of memory. © Thus by optimizing the code the overall running time of the target program can be improved. ‘Seamed nth CamScannerCompiler Design 6, Code Genoration «In code generation phase the target code gets generated. «The intermediate code instructions are translated into sequence of machine instructions. Example - Consider input a» btc #60 get processed in compiler, The output at each stage of compiler follows is as Input processing In compiler Output a=btc*60 Texter anaiyzor Token stream ‘Syntax tree uf aS Semantic tree aN ids” int to float Intermediate code ‘Symbol table Code optimizer ty Id 60,0 idy sida + ty Optimized code MOVF id, Ry MULF #60.,R, MOVE dg, E ADDF RoR, lachine code MOVE Ry, —__ "Fresca. puscarions'- an up oat tr mownsne sicooe ‘Seamed nth CamScannercompe Det ee asletnrluction an Leste Ants ‘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. + 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. Then during code generation typically information about how much storage is allocated to identifier is seen. Error detection and handling ‘+ 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. ra Source program Lexical alysis phase analyzer Coil ‘Syntax analyzer Error detection Sse nn and handling management code generator Code optimizer Code generator Fig. @.5.2 Phases of compller «Normally, the errors are reported in the form of messages. + 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. Q6 Define compiler. Explain brief about the syntax and semantic analysis of compiler with example. SGP [INTU : Part B, March 16, Marks 5] Ans. : Definition of compiler - Refer Q3. Syntax and Semantic analysis - Refer Q6. [SF recta PuBLicATiONS" Anup trust for rowed brcoor ‘Seamed nth CamScannerCompaen Design QT Show the output generated by each phase for the following expression xm (esb)t(c+d). PPNTU: Jan-10, Marks 8] Ans: rears Te + sep ree Be) Mov i. Re 400 i Re Mov ig Ry ADD ity, Ry MUL RR MOV Re Fig. Q7.4 The first operand represents source and second operand represents the destination. —| Q8 Define bootstrapping. ERLINTU : Part A, March 16, maces 35 OR Write brief note on bootstrap process. FH DNTU : Fart A, Deen, Harts 2] Ans. : Bootstrapping is 2 process in which simple language is used to translate more complicated Program which in tum may handle far more complicated program. This complicated program can further handle even more complicated program and 50 on. Q9 Explain the concept of Bootstrapping with example. EGP (INTU : Part 8, March-17, Marks 6] Ans. : Bootstrapping - Refer Q3 Suppose we want to write a cross compiler for new language X The implementation language of this compiler is say Y and the target code being generated is in language Z That is, we create XyZ. Now if existing compiler Y [Le. compiler written in language Y] nuns on machine M and generates code for M then it is denoted as YyM Now if we run XyZ using YyM then we get a compiler XyZ. That means a compiler for source language X that generates a target code in language Z and which mms on machine M. Following diagram illustrates the above scenario. Fig. 09.4 Example - We can create compilers of many different forms. Now we will generate compiler which takes C language and generates an assembly language as an output with the availability of a machine of assembly language. TECRNCAL PUBLICATIONS » An up test kr troutezgn ‘Seamed nth CamScannerCompiler Design 1-6 Basic Introduction and Lexical Analysis Step 1 : First we write a compiler for a small subset of C in assembly language. Co ASM ' ———> compiler 1 asm Step 2: Then using this small subset of C i.e. Cy, for the source language C the compiler is written. c ASM ——> compiler 2 & Step 3: Finally we compile the second compiler. Using compiler 1 the compiler 2 is compiled. Step 4: Thus we get a compiler written in ASM which compiles C and generates code in ASM. c ash] Co fo Compiler 2 uu Compiler 1 Q.40 Define cross compiler. EGE [INTU : Part A, Nov 15, Marks 2] ‘Ans, : There may be a compiler which run’on one machine and produces the target code for another machine. Such a compiler is called cross compiler. Thus by using cross compilation technique platform independency can be achieved. To represent cross compiler T diagram is drawn as follows Implementation language Fig. 4.10.1 (a) T diagram with S as source, T as target and 1 For source language L the target language N gets generated which runs on machine M. Fig. 1.10.1 (b) Cross compiler FF recive puaucaTiOns"- an ve tat towne contd ‘Seamed nth CamScannereg Basic Introduction and Lexi _— Basi Introduction and Lesiel Anat, 1.4 Programming Language Basics 11 What are the advantages of front end and back end model of compiler ? Ans: 1. By Keeping the same front end and attaching different back ends one can produce a compiler for same source language on different machines. 2 By keeping different front ends and same back end one can compile several different languages on the same machine. Fig. Q.11.1 Front end back end model Q42 What is pass of a compiler ? Explain how compiler works in passes ? ESP [ONTU : Part B, Marks 5] ‘Ans.: Definition : One complete scan of the program is called pass. Working of Pass : ‘In the first pass the source program is scanned completely and the generated output will be an easy to use form which is equivalent to the source program along with the additional information about the storage allocation. ‘It is possible to leave a blank slots for missing information and fill the slot when the information becomes available. Hence there may be a requirement of more than one pass in the compilation process. +A typical arrangement for optimizing compiler is one pass for scanning and parsing, one pass for semantic analysis and third pass for code generation and target code optimization. C and PASCAL permit one pass compilation, Modula-2 requires two passes. 43 What fs a pass in a compiler ? What Is the effect of reducing the number of passes ? ‘Ans. : «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. Q.14 Compare one pass and two pass compilers. Ff TecinICA.PUDLICATONS = An op Prat fe oniage a ‘Seamed nth CamScannerOne pass compilers ‘One pass compiler scans the source program only once. In this one pass Compiler has to perform some tasks | such as collecting the labels, resolving forward references and doing the actual compilation, For example : Pascal can be implemented with ‘pass compiler. ‘Merit : It is faster than multi-pass compilers Demerit : It has limited scope for compilation. Q.45 Distinguish between Pass and Phase. Ans. : Baste Introduction and Lexical Analysis. ‘Two pass compilers ‘A two pass compiler does two scans over the source | file, The second pass can be over a file generated in | the first pass In the first pass all it does is looks for label | definitions and insert them in the symbol table. In the second pass, after the symbol table is complete, | it does the actual compilation. For example : Java Requires multi-pass compilation. Merit : Two-pass compilers have wider scope for compilation due to two passes. | =| Demerit tis slower than one pass compilers. BSP [INTU : Part A, May-13, Marks 3] | Phase | The processing of compilation is carried out in various | steps. These steps are referred as phases. The phases of ‘compilation are lexical analysis, syntax analysis, intermediate code generation, code generation and code optimization. ‘The task of compilation is carried out in analysis and synthesis phase. ‘The phases namely lexical analysis, syntax analysis and semantic analysis are machine independant phases and the phases such as code generation and code optimization are machine dependant phases. Various phases are logically grouped together to {form a pass. The process of compilation can be carried out in single pass or in multiple passes. ‘The task of compilation is carried out in single or multiple passes. ‘Due execution of program in passes the compilation model can be viewed as front end and back end model. Pera iei cot TW.Uriaey Q.16 Explain the role of lexical analyser. ‘Ans: : + Lexical analyzer is the first phase of compiler. * The lexical analyzer reads the input source program from sequence of tokens. xical Analyzer] 1.5 The Role of Lexical Analyzer’ BF [UNTU : Part A, Marks 3] left to right one character at a time and generates the * 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 i Demands Tokens |“ Retume L tokens. Fig. Q. cess of compilation is as » Syntax tee | Rest or | Target ee compiler |~coda Role of lexical analyzer ) ae eres ‘Seamed nth CamScannerCompiler Design ae * As the lexical analyzer scans the source program to | recognize the tokens it is also called as scanner. | Q.17 What are the features of a Lexical analyser? FSP [ONTU : Part A, Dec.-17, Marks 2) Ans, : 1. It produces stream of tokens. 2. It eliminates blank and comments. | 3. It generates symbol table which stores the information about identifiers, constants encountered in the input. It keeps track of line numbers. / It reports the error encountered while generating the tokens. 6 The lexical analyzer works in two phases. In first phase it performs scan and in the second phase it does lexical analysis; means it generates the series of tokens. Q.18 Explain in detail about the role of lexical analyzer with the possible error recovery actions ‘SGP[INTU : Part B, May-18, Marks 10] Ans. : Role of lexical analyser - Refer Q.16 Recovery actions : Various possible error recovery actions in lexical analyzer are - i) Deleting extra characters that might appear in the source statement. ii) Inserting missing character ii) Interchanging two adjacent characters. iv) Replacing an incorrect character by the correct character. Q.19 Define lexeme, token and pattern. Identify the lexemes that make up the tokens in the following program segment. Indicate corresponding token and pattern. void swap(int a,int b) { } SGP [INTU : Part B, Marks 5] Ans, Tokens : It describes the class or category of input string. For example, identifiers, keywords, constants are called tokens. Lexomes : Sequence of characters in the sug Program that are matched with Pattern of the token. For example, in, num, ans, choice. o Lexeme Patterns D Identifier 4) Identifier is a collection of letters. ii) Identifier is a collection of alphanumeric chracters. iii) The first character of identifier must be a letter. 2) Operator i) Operator can be arithmetic, logical, relational operators. 4i) The parenthesis are considered as operators. iii) Comma is treated as separation operator. iv) Assignment is denoted by operator. AF" recsnncas Pusuicarions®- An treat or owecpe ‘Seamed nth CamScannerCompiter Design 3) Keyword i) Keyword are special words to which some meaning is associated with. ii) int, void are keywords for denoting data types. Q.20 Consider the following conditional statement : If(x>3) then y=5 else y=10; How does lexical analyzer help the above statement in process of compilation ? SQPLINTU + Part B, March 17, Marks 6] Ans.: The lexical analyser will scan each programming statement and break it down into group of tokens such as identifiers, keywords, operators, constants and s0 on. It is as follows = Lexeme Token constant I operator Now we will consider encoding of tokens as follows an ee | ‘Token L Code ‘The symbol table for identifier and constants is as follows - [ tocation Now using hypothetical encoding we get the stream of tokens in encoded form as follows - 1, (91), (6100), (8,3), 2 (6,101), (10,1), (7,104), 3, (6,101), (10,1), (7,105) In above encoding, the value 1 indicates the if then comes the pair (9,1) in which 9 is for parenthesis and 1 is for opening bracket. Then the pair (6,100) indicates that the code 6 is for identifier and 100 is a location of identifier x in the symbol table. Continuing in this fashion, we get the above encoded form. 1.6 Input Buffering | Q.21 What is input buffering ? How is input buffering implemented ? [@P[INTU : Part A, March 17, Marks 3) Ans. © A block of data is first read into a buffer, and then scanned by lexical analyzer. There are two TAF recricas PUBLICATIONS'- Anup str kronedoe ‘Seamed nth CamScannerCompiler Designs 1-11 methods used in this context : one buffer scheme and | twvo buffer scheme. 4. One buffer scheme Fig. Q.21.1 One buftfer scheme storing input string In this one buffer scheme, only one buffer is used to store the input string. But the problem with this | scheme is that if lexeme is very long then it crosses the buffer boundary, to scan rest of the lexeme the | buffer has to be refilled, that makes overwriting the first part of lexeme. 2. Two buffer scheme i Fig. Q.21.2 Two buffer scheme storing Input string To overcome the problem of one buffer scheme, in | this method two buffers are used to store the input string, The first buffer and second buffer are scanned alternately. When end of current buffer is reached the other buffer is filled. The only problem with this | method is that if length of the lexeme is longer than | length of the buffer then scanning input cannot be scanned completely. | ‘Initially both the bp and fp are pointing to the first | character of first buffer. ‘© Then the fp moves towards right in search of end | of lexeme. As soon as blank character is recognized, | the string between bp and fp is identified as | corresponding token. | = _____ Basic Introduction and Leis aig #To identify the boundary of first bulfer end op buffer character should be placed at the end of fing buffer. + Similarly end of second buffer is also recognized by the end of buffer mark present at the end of second buffer. When fp encounters first eof, then one can recognize end of first buffer and hence filling up of second butfer is started. ‘In the same way when second eof is obtained then it indicates end of second buffer. « Alternatively both the buffers can be filled up until end of the input program and stream of tokens is identified. © This eof character introduced at the end is called sentinel which is used to identify the end of buffer. Recognition of Token: Q.22 Define regular expression. Write about the nntity rules for regular expressions. EGE [ONTU : Part B, Nov.-17, Marks 5] OR Define regular expression. Explain about properties of regular expression. GP [ANTU : Part B, March 16, Marks 5] Ams,; Regular expressions are__-mathematical symbolisms which describe the set of strings of specific language. Here are somerules that describe definition of the regular expressions over the input set denoted by 5. 1. e is a regular expression that denotes the set containing empty string. 2. If RI and R2 are regular expressions then R = Rl + R2 (same can also be represented as R = R1IR2) fs also regular expression which represents union operation. 3. IF R1 and R2 are regular expressions then R = RLR2 is also a regular expression which represents concatenation operation. 4. TERI is a regular expression then R = RI is also @ regular expression which represents Kleen dlosure. FF reciwcas PUBLICATIONS - An up tut fe hnowodge ‘Seamed nth CamScanner a Q2 27 37 4am a25 Ans, T fmCompiter Desi. eo _ a Algebraic Properties : 1 eR= Re=R 2 ene € is null string 3. o is empty string. 4 OR = Ro=6 5. O+R=R 6. R+R=R 7 RR* = R'R= Rt : wy eR 9 e+RR” = R” 10. (P+Q)R= PR+QR nn @+Q" =P Q")= e+ O77 12 Ri (e+ R) = (e+ R)R 3B +9" = RT 1“. e+R’ =R" 18. PQ)" P = PP)” RR 1 RR+R one . ‘SGP INTU : Part A, March 17, Marks 2] 23 Write regular expression over alphabet {a,b,c} containing at least one ‘a’ and at lea ‘Ans, : Regular expression = (a(atb#c)*b(a*b#c)"c(atb+c)")" Q.24 Find the regular expression corresponding to given statement, subset of { 0,1}* The language of all strings containing at least one 0 and at least one 1. 2.The language of all strings containing 0's and 1's both are even. 3.The language of all strings containing atmost one pair of consecutive 1's. 4.The language of all strings that do not end with 01. Ans. : 1. RE = (0+1)* 2 RE = (00+11)* 3. RE = 0* 110° 4, RE = 1 +0"+ (10)* Q25 Write down the regular expression for the binary strings with even length. [@ [INTU : Part A, Marks 2) Ans. (aatabtbatbb)* PF rechncan PuBuicaTions”- An up tht for krowedoe pico ‘Seamed nth CamScannerCompt ripe nn 3-3 O25 Wrtse 2 remiar exprewice for identiier and keprord and design 2 transition Ciogrem for is FRDOO Pet he 2 Asa: re = Leter (Lemer + Gig O27 Witte 2 requiar expremicn for defining constants (unsigned xmmbers). Design the transition gravis fy tem. BE DNTU: Peet 8 acts Ase : The constant com be defined by three diterent ways - Cena st =©O=O=*O rem (Ege) «(cee re ore =©O*O--O#O=© BB) te = Cigt” (odigit” HEL+ | rege” 2 22 Virite 2 regular expression for relation operators. Design a transition diagram for them. SEE PNTD : Part A, Marks 21 Aras 120 (<\ 2 | State B Dtran [A, b] Followpos (2) (1, 2, 3} ie. state A Dtzan [B, a] = Followpos (1) U Followpos (3) = (1, 2,3, 4) = State B Dtran [B, b] = Followpos (2) = (12,3) ie. state A As no new state getting generated. DFA will be The state B is a final state as it contains final state (4). b 34 Construct the NFA using Thompson's notation for following regular expression and then convert It to DFA. (a/b)*ab# ‘Ans. : Step 1: We will construct syntax tree. (INTU : Part B, Marks 5] ON LN ZN 4 ic oN “ 73 o firstpos ©) or firstpos (C2) cof lastpos (C2) ‘Seamed nth CamScanner<= — Compiler Design itt Basic Introduction and Lexical Anaya, | nullable (©) If nullable C}) If nullable ©) | end then firstpos | then lastpos (,) U I nullable (C2) eu lastpos ©) firstpos (Cz) else else firstpos (©), latpos C3) : true firstpos (%) __lastpos (¢1) (1.2.34) (9) W234), @ (5 # (5) a 123). {Yb () 4 (12) j 62 20 {0.2} 7 (1.2) —_ mei b 1 2 ‘The left value written in curly bracket is firstpos and that written to the right is lastpos. ‘The firstpos is computed as follows. Step 3: The transition graph will be Qa 7 O—-© (2) g Step 4: Assume firstpos(root) « (1, 2, 3) = A Diram [A, a] = Followpos (1) U Followpos (3) = 2,3} 0 14) = (23,4) > StateB WP rec aLcaTONS Ao tee rece — ‘Seamed nth CamScannerCompiler Design * Diran [A. b] = Followpos (2) ~ (123) + State a =B Dtran [B, a] Dtran [B, b] = Followpos (2) U Followpos (4) 1,2 3} U5} (,2,3,4,5) + State C Followpos (3) U Followpos (1) State B B Dtran [C, a] = Dtran [C, a] Dtran [C, b] = Followpos (2) Duran [Cb] = A ‘The DFA will be shown in. Fig. Q34.1 ‘The state C contains final state (5). Hence C is a final state in DFA. b Qa b B+-OL SY B Fig. 0.34.1 18 Lexical Analyzer Generator SS el 35 What Is LEX ? Explain it In detail. GP [NTU : Part B, Marks 5] ‘Ans.: © Basically LEX is a unix utility which generates the lexical analyzer. «LEX scans the source program in order to get the stream of tokens and these tokens are related together so that various programming constructs such as expressions, block statements, procedures, control structures can be realised. * The LEX specification file can be created using the extension J(often pronounced as dot L). For ‘example, the specification file can be x.1 *This x1 file is then given to LEX compiler to Produce lexyy.c. the lexyy.e. representation of Basic Introduction and Lexical Analys constructed for the regular expression. The lexemes can be recognized with the help of this tabular representation of transition diagram. «Finally the compiler compiles this generated Jexyy.e and produces an object program a.out. When some input stream is given to aout then sequence of tokens get generated. Lex specifeaton fie ex exe xh compiler | Tuexical analyzer program) perez] co ae compiler | executable program Inout am pu a Stream of, ‘rings | tokens from source program Fig. Q.35.1 Generation of lexical analyzer using LEX Q.36 Give the structure of LEX. WGP [ANTU : Part B, Marks 5] ‘Ans.: The LEX program consists of three parts - 1. Declaration section 2. Rule section and 3. Procedure section. we Declaration section %} %% Rule section, *% ‘Auxiliary procedure section In the declaration section declaration of variable constants can be done. Some regular definitions can also be written in this section. The regular definitions are basically components of regular expressions appearing in the rule section. ‘©The rule section consists of regular expressions with associated actions. These translation rules can be given in the form as - | Ry {action,) * This lexyy.c. is a C program which is actually a | R, {action} lexical analyzer program. The LEX specification file stores the regular expressions for the tokens and | file consists of the tabular I . the transition diagrams |, {action,} eaoey TF Tecra PuaUGATIONS'- An op tanto konto ‘Seamed nth CamScannerCompiter Design 1-23 Sc Where each R, is a regular expression and each action, is a program fragment describing what action ig to be taken for corresponding regular expression. These actions can be specified by piece of C code. And third section is a auxiliary procedure section in which all the required procedures are defined. Q.37 Define compiler. Explain in brief about the LEX compller. EE [INTU = Part B, Nov 17, Marks sy ‘Ans, : Compiler - Refer Q3. LEX Compiler - Refer Q.35. 1.9 Optimization of DFA based Pattern Matchers 0.38 Explain the process of building the lexical analyzer generator. {EG [INTU : Part B, Marks 5] ‘Ans. : Design of Lexical Analyzer Generator + To design lexical analyzer generator, the pattern of regular expressions are designed first. + These pattems are for recognizing various tokens form input string, + From these pattems it is easy to design a Non-deterministic Finite Automata (NFA). * But the simulation of DFA is easier by program. Hence we convert the NFA drawn from these patterns to DFA. Lexical analyzer generator Regular Fig. @.38.1 Bullding of lexical analyzer generator 39 A LEX program Is given below - ‘Auziliary Definitions (none) Translation rules a abb a’bt Implement the LEX Program as DFA. Ans. : We will implement the given LEX program as DFA in following steps - Stop 1 : For each regular expression first we will build the Finite Automata (FA). Pattern 1: =O-© SFP reopen puaticaTions’ Anup tt er inowiedze é ecco Pattern 2 : ‘Seamed nth CamScannerPattern 3 : Step 2: Now we will combine all these pattems by designing NFA with € Step 3 : The above drawn combined NFA can recognize the pattern in the given LEX Program. Fig. @.39.1 Combined NFA For instance String a matches with pattern 1. 7 4 2 he input a 7 7 GI States String abb matches with pattern 2. EEEE States String aab matches with pattem 3. Vas | input next states. § GEER] FF recuican PUBLICATIONS” Anup trust fer krowiedoe ‘Seamed nth CamScanner7 asic Introduction and Levee Ang, ee Compiler Design eA 125 — ‘Step 4: Now we will convert the combined NFA to DFA. First of all we will obtain eclosure {0} = {0,1,3,7} = [0137] new state. ([0137], a) = (8( 0,a )U 8(1,a )U 8(3,a )U8(7,a)) =(@U2vV4a7 = (24,7) = (24,7) new state. 5((0137], b) = (6(0,b)U5 (Lb)u 6 (3,b) U6 (7,b)) "(@UeveEeUvs = [8] > new state The pattern announced for [ 0137 } will be none because 0, 1, 3 or 7 all these states are non-final states, As in above computation two new states ie. [ 2, 4,7] and [ 8 ] are formed, we will find input transitions for these states. 8([247], a) = (8(2,a)U8(4.a)U8(7,a)) -oueU7 =U] > newstate 8([247], b) = (8 (2,b)U.8(4,)U8(7,b)) “@uU5u8 = [58] > newstate. Thus we will obtain the input transitions for the new states that are getting generated. Finally the transition table can be Input | Patten: convenient. P, The set of words having 2,¢,.0,u appearing in that order, although not necessarily consecutively. il) Comments as in C, S&P [INTU : May-09, 12, Marks 8] Ans. : i) The word may contain some consonant and vowels. The condition is that these vowels must appear in the order ae,ou. These vowels may be consecutive or not. AF TecHicas Puacicarions’- Anup ont er inowtedpe sont ‘Seamed nth CamScannerCompt Design Auxillary definition ~ con [a ei o ult ne = (con|a)"(con|e)" (con| i)’ (con|o)" (con|u)" ‘The NFA will be ii) A single line comment is given by //. Aurilliary definitions letter [a-zA-Zp digit [0-9]+ Whitesp —[\t]+ operators. [>< Regular expression = // (letter! digit whitesp loperators)" The NFA will be Lettr | digit | whitesp | operators ‘A multiline comment can be given by ed Auxilliary definitions letter [a-zA-Z} digit fo-9]+ Whitesp —[\t]+ operators [<><=>=+- */]+ The regular expression = ‘(letter | digit | whitesp operators)’ */ The NFA will be {otter | cigit | whitesp | operators Q =@)-O—-O)-©)--© SF recuwicat PUBLICATIONS - An up tras fr knowndge ‘Seamed nth CamScannerUNIT - I Syntax Analysis 2.4 Introduction to Syntax Analysis | Q.1 Explain the term - syntax analysis ESP [DNTU : Part A, Marks 2] Ans. : Syntax analysis is a process which takes the input string w and produces a syntax tree. If there exists any error in the syntax of the programming construct then the syntax error messages are generated. Q2 Explain the reasons for separating lexical analysis phase from syntax analysis. ESTINTU : Part A, Marks 2] ‘Ans. : The lexical analyzer scans the input program and collects the tokens from it. On the other hand parser builds a parser tree using these tokens. These are two important activities and these activities are independently carried out by these two phases. Separating out these two phases has two advantages - Firstly it accelerates the process of compilation and secondly the errors in the source input can be identified precisely. | 2.2 Context Free Grammar — 3 Define a context free grammar. GF [ONTU : Part A, May-18, March-16, Marks 3] Ans, : Definition : The context free grammar can be formally defined as a set denoted by G=(V,T,P,S) where V and T are set of non-terminals and terminals respectively. P is set of production rules, where each production rule is, in the form of non-terminal ~> non-terminals or non-terminal — terminals S is a start symbol. For example, P= [(S>S+S S3s*s S38) $34) If the language is 4 + 4 * 4 then we can use the production rules given by P. The start symbol is §. ‘The number of non-terminals in the rules P is one and the only non terminal ie. S. The terminals are +, (and We are using following conventions. 1. The capital letters are used to denote the non-terminals. 2. The lower case letters are used to denote the terminals. Q4 Explain concept of derivation tree. Ans.:Let G = (V, T, P, S) be a Context Free Grammar. The derivation tree is a tree which can be constructed by following properties. i) The root has label S. fi) Every vertex can be derived from (V UT U ®. fii) If there exists a vertex A with children Ry, Ry) ~ Ry then there should be _ production AR RyRy. iv) The leaf nodes are from set T and interior nodes are from set V. Q.5 Explain in brief about left most and rightmost derivations. SGP [INTU : Part A, Dec-17, Marks 3] Ans. :If the leftmost non terminal in a sentential form is chosen for derivation then that derivation called leftmost derivation. ‘Seamed nth CamScanner| | compe son a Jf the rightmost non terminal in a sentential form is chosen for derivation then that derivation is called rightmost derivation. For example - Refer Q.6, Q.6 Consider the grammar given below - EDE+E|E-E|E*E| E/E | alb Obtain leftmost and rightmost derivation for the string a+ b* a+b, ESPLINTU May-09, April-t1, Deco11, Marks 8] ‘Ans. : Leftmost derivation aN E E+e JIN Bbe atese JN | SEB atbrEsE ES atbrare a gee atbrard tot >a Rightmost derivation £ E+E a E*E+E E+Esb JN JN Era+b +e Eretatb femetinlemmiee cscs: a bab atbearb Q7 Consider SalI) TT, S|S 4) Draw parse trees for (aja) and (a, (a, a)) D) Construct leftmost and rightmost derivation for (a, €) and (a, (a, €)) ©) What language does the grammar generate. EG LINTU + Dec.-14, Marks 16] Ans. : a) i) Parse tree for (a, a) is AN JN i Se 2 i | | fi) Parse tree for (a, (a, a)) is ANN YIN : YIN (ee JIN e—o—4 b) i) Leftmost and rightmost derivation for (a, e) we will put e= a. 8 s @ mM as ms 5) (a) @s a) (aa) (a) ii) Leftmost and righmost derivation for (a, (a, e)) We will put e= a. s |s foo) om a9 m9 69 Gm) 6m Gas) @o) (ma) @@9) (69) 69) Gea) (a (@ 9) i G (a) (@ @a)) | (@ @a)) © This grammar generates all strings with well formedness of parenthesis. TBF recrnwcas PUBLICATIONS = Ah vp treat or owieoe icone ‘Seamed nth CamScanner| 2.3 Writing a Grammar QB Write a CFG for the ‘while’ statement in ’C’ language. HEP[INTU ¢ Jan-10, Marks 9) Ans. : The CFG G = {V,T,P,S} where V is a set of nonterminals, T is a set of terminal symbols, P is a set of Production rules and S is a start symbol. The set of production rules P = { $— while (condition) stmt condition -> id relop id relop >< I> | cal alt= S— while (condition) { L} L- stmt Listmt ) V = (S, condition, relop, L); T = (while, (,),6,>, <=>) ===, id, stmt) Q.9 What is the string generated by the grammar A—>(A)A. US [BNTU + April-t1, Marks 8] ‘Ans, : Let the production rule for the CFG is AS(A)A as there is no terminal symbol generation by this grammar, we can not derive any string from it Hence we will assume the rule to be A (ADA ASOA Av()le » The strings that will get generated willbe {(), (YC (()) (QO), -} Hence the language denoted by this grammar is for well formedness of parenthesis. A Parsing Techniques Q.10 Explain various parsing techniques used in compiler. ES [ONTU = Part B, Marks 5] ‘Ans.:When the parse tree can be constructed from root and expanded to leaves then such type of parser is called Top-down parser. The name itself tells us that the parse tree can be built from top to bottom. Raa fea When the parse tree can be constructed from Teaves to root, then such type of parser is oe called as bottom-up parser. Thus the parse ESS tree is built in bottom up manner. Ff recunrcat PUBLICATIONS" An up trust er nowiodge ‘Seamed nth CamScannerCompilerDesign Qi What Is the difference between top down parser and bottom up parser ? ‘EST [INTU : Part B, March-16, Marks 5) | Bottom up parser | Parse tree is built from leaves to toot. ‘This complex to to 2 | This is simple to parsing techniques. Various problems that | ambiguous grammar cccur during top down conflicts occur in parse | table, ne qpliatide mall toaplanwe lass of languages. broad class of _ languages. 5. Various parsing Various parsing techniques are 1) techniques are 1) Shift Recursive descent reduce 2) Operator parser 2) Predictive precedence 3) LR 2.5 Top Down Parsing 42 What are problems in top down parsing ? ‘Ans.: There’ are certain problems in top-down parsing. In order to implement the parsing we need to eliminate these problems. These problems are - (1) Backtracking (Q) Left Factoring (@) Left Recursion (4) Ambiguity. Q13 Write a rule of left factoring a grammar and sive example, ESLDNTU : Part B, Marks 5] Ans, : In general if A= aBylaB, factored as, _. Syntax Analysie Aaaa’ ABB For example : Consider the following grammar. S > iEtS | iBtSeS | a Eb The left factored grammar becomes, S —iBISs'la Ss +esle Eb | Q.14 Define left recursive grammar. UGP[INTU : Part A, Dec.-17, Marks 2] ‘Ans. : Left Recursion : The left recursive grammar is a grammar which is as given below. ataa Here + means deriving the input in one or more steps. To eliminate left recursion we need to modify the grammar. Let, G be a context free grammar having a production rule with left recursion. AAG ae =) Then we eliminate left recursion by re-writing the production rule as : Aspa’ A’ aA Aloe +@) Q.15 Eliminate left recursion for the following grammar E> E+T|T Torr IF Fe> (E) | id USPLINTU : Part A, Nover5, Marks 3] Ans: E>E+TIT We can map this grammar with the rule A > A al B. ‘Then using equation (2) (in Q.14) we can say, is a production then it is not possible for us to take a AE decision whether to choose first rule or second. In | ae such a situation the above grammar can be left | i B=T {GHNIGAL PUBLICATIONS” An up thrust for knowlege preooe ‘Seamed nth CamScannerCompiler Design _ Then the rule becomes, ETE’ Es+Tble Similarly for the rule, TOT+FiF We can eliminate let recursion as ToFT Toaseirie ‘The grammar for arithmetic expression can be equivalently written as - ESE+TIT ETE EstTele Torr TOT+FIF > To+Frle Fs@ lid = FI@®lid Q46 Discuss in brief about left recursion and left factoring with examples. ESE [INTU : Part B, Nov-17, Marks 5] Ans. : Left Recursion : Refer Q.14. Left Factoring : Refer Q.13. Q17 Define : Left recursive state the rule to remove left recursive from the grammar. Eliminate left recursive from following grammar. Ss Aalb A Ac |Sd[f S[ANTU : Part 8, Marks 5] Ans.: The left recursive grammar is a grammar which is as given below : AL Aa To eliminate left recursion we apply following rule, AW Acy!Acey|IBy [Bp is a rule then AW B,AIB A’ A’ say A'[ a2 A'le If we replace S by Aalb then there exists only one rule a Syntax Analysis A AclAad|bd] After eliminating left recursion the grammar becomes As bdA‘| fA’ AacA'lada’le To summerize S— Aalb As bdA’ EA’ Al > cAladA’le Q.48 Check the following grammar is left recursive or not. Justify your answer. If left recursive then make grammar as non - left recursive. $3 Qla L-Ls|s USP [ANTU : Part B, Marks 5} Ans, : The following rule is left recursive LoLs|s We will use following formula - If A + Aa|B then A > BA’, A’ aA’|e. Hence we can eliminate the left recursive rule using above formula 5 ! en Lo sv Lo |St'le a 8 por bor Q.19 What Is backtracking ? Explain it with sultable example, USP[INTU : Part B, Marks 5] Ams. : Backtracking is a technique in which for expansion of non-terminal symbol we choose one alternative and if some mismatch occurs then we try another alternative if any. AB reciicat Pus.icaTions’- An up nvst ter knowledge For example : So xPz Poywly Then Q g g SOO GOOD © ®®o © @ © Fig. ates eet! ‘Seamed nth CamScannerEN Compiler Design If for a non-terminal there are multiple production rules beginning with the same input symbol then to get the correct derivation we need to try all these alternatives. Secondly, in backtracking we need to move some levels upward in order to check the possibilities. This increases lot of overhead in implementation of parsing. And hence it becomes necessary to eliminate the backtracking by modifying the grammar. Q.20 Define ambiguous grammar. Check whether the grammar S->aAB, A->bC|cd, C->ed, B->c/d Is ambiguous or not. ES[INTU : Part B, March-16, Marks 5] ‘Ans: Definition : A grammar G is said to be ambiguous if it generates more than one parse trees for sentence of language L(G). Consider the string abedd. It can be derived as - As there is only one possible parse tree that can be generated for deriving the given string, the given — grammer is not ambiguous. i Q21 Consider the following grammar, ESE+E[E%E| €) | id Show that it is ambiguous. Eliminate ambuigity from this grammar. TSLINTU + May-08, 09, Aug-08, ‘April-09, Marks 8, Jan.-14, Marks 7] Ans. : We will derive the string id + id * id. i Parse tree 1 the © Syntax Analysis ‘As two different parse trees’ can be drawn for deriving the same string. Hence given grammar is ambiguous. To eliminate ambiguity, observe that given grammar has left associative operators. Hence we will make use of left recursive production rules to climinate ambiguity. The unambiguous grammar will be, ESE+TIT TOT*FIE F(@) lid ‘The parse tree for id + id * id will be, A YIN e+ To AN 1 TF Loid FoF id ood id id Q.22 Implement the following grammar using recursive descent parser. S-> Aa | bAc| bBa, A> d,B-> d SGP [NTU : Part B, Marks 5] ‘Ans. : Procedure S( ) { if Qookahead =p) { B(); /7or A() because both gives 'd! ‘else if (lookahead = 'a') match (a) @ QO © OO © © © @) Parse tree -2 Fig. 0.24. Parse Traes SP recunicat PUBLICATIONS” An up thrust for knowiedpe prcoor' ‘Seamed nth CamScannerCompiler Design ne eso if (loohahoad = '$) { declare SUCCESS ; } else { AQ): if (lookahead = 'a!) ‘match (4!) ; } + Procedure A() { if (lookahead = '¢’) ‘match (4!) else ‘error ( } Procedure B( ) { if lockahead = 'd') match (4!) else error( ); + Advantages of Recursive descent parser 1. Recursive descent parsers are simple to build. 2. Recursive descent parsers can be constructed with the help of parse tree. Limitations of Recursive descent parser 1. Recursive descent parsers are not very efficient as compared to other parsing techniques. 2. There are chances that the program for RD parser may enter in an infinite loop for some input. 3. Recursive descent parser can not provide good error messaging 4. It is difficult to parse the string if lookahead symbol is arbitrarily long. Q.23 Explain non-recursive predictive parsers. Draw the block diagram of it. US [INTU : Part B, Marks 5) Ans.: The predictive LL(I). top-down parsing algorithm is of non-recursive type. In this type of parsing a table is built, fF recucat PUBLICATIONS An up tust for kowiedge - - - Sunt Analy * For LL(1) - the first L means the input is scanney, from left to right. The second L means it leftmost derivation for input string. And thy number 1 in the input symbol means it uses ony ‘one input symbol (lookahead) to predict th, parsing process. The simple block diagram for LL(1) parser is as shown in Fig. Q23.1. Input token L2] st] 0 Top-+{—S ee cs] Stack Parsing table *[e Ss A 8 c Fig. 0.23.1 Model for LL(1) parser ©The data structures used by LL(1) are i) input buffer ii) stack iii) parsing table. ©The LL(1) parser uses input buffer to store the input tokens. The stack is used to hold the left sentential form.The symbols in RHS. of rule are pushed into the stack in reverse order ie. from right to left. Thus use of stack makes this algorithm non-recursive. The’ table is basically a two dimensional array. The table has row for non-terminal and column for terminals. The table can be represented as M[Aa] where A is a non-terminal and a is current input symbol. Q.24 List out the rules for FIRST and FOLLOW. EGP LINTU : Part A, Dec.-17, Marks 3] OR List the rules for computing FOLLOW set. ESP LINTU : Part A, Novi-15, Marks 2] ‘Ans. : FIRST function FIRST(a) is a set of terminal symbols that are first symbols appearing at RH.S. in derivation of « If a=9¢ then ¢ is also in FIRST (0). ‘Seamed nth CamScanner| Compile sion 2-8 Following are the rules used to compute the FIRST functions. 1. If the terminal symbol a the FIRST(a) = {a}. 2. If there is a rule X—+e then FIRST(X)=(e) 3. For the rule A — X, Xp X, ...X, FIRST(A) = (FIRST(X,) U FIRST) U FIRST(X3)..-U FIRST). Where k X} Sn such that 1sjsk-1. FOLLOW function FOLLOW (A) is defined as the set of terminal symbols that appear immediately to the right of A. In other words FOLLOW(A) = { a |S = a Aa B where a and B are some grammar symbols may be terminal or non-terminal. The rules for computing FOLLOW function are as given below - 1. For the start symbol S place $ in FOLLOW(S). 2 If there is a production A-+aBB then everything in FIRST(B) without e is to be placed in FOLLOW@). 3. If there is a production AaB B or A-+aB and FIRST(B)= {e} then FOLLOW(A) = FOLLOW(B) or FOLLOW(8)-FOLLOW(A). That means everything in FOLLOW(A) is in FOLLOW@). Q25 Construct FIRST and FOLLOW for the grammar. E> ET |T Rael Eee eae Ans.: FIRST(E) = (Cid) FIRST(T) = {Cid} FIRST) = {Cid} FOLLOW) = &), 4 FOLLOW() = (5) 4%} FOLLOWG) = { $+") Q26 Construct predictive parsing table for grammar. EDEsTIT T> TIF F> (&) id Ans, : The given grammar contains left recursion. We will eliminate left recursion first. Refer 0.15 for elimination of left recursion from given grammar. On eliminating left recursion we get - ESr[UNTU : Part B, May-16, Marks 5] EOTE c E> 4TEle ToiT ee TP recrnecas PUBUATIONS'- Anup tat oie coor ‘Seamed nth CamScannerCompiler Desien Tore F @lid First create the table as follows. 2-9 MIE, $]=E' >e Torr Ada A=E,as9rT FIRST(FT’) = FIRST(F) = ((id} Hence M[F(] = T — FT” And M[Fjid] = T > FT” Tor Now we will fll up the entries in the table using the above given algorithm. For that consider each rule | Aa ‘one by one. AsTa="T EoTr | IRSTCFT) = (1 Ava | Hence M{T] = T > ‘Fr A=Ea=TE | FIRST(TE) if B’ =e then FIRST(T) = ((id) Toe MEE, ()= E-sTE Ana MIE, id] = ETE” | AsTiace | FOLLOW(T) = (+8) Este | | Hence M[T'4] = Te | oe My) =Te AeE,a=4TE MITS]=T3e FIRST(+TE’) = {+} Hence MIE,#] = E'—> «TE F5@ A sa Ee AsEa=() Ave IRST(E)) ={(} . A=E, a=e then Hence MIF,(Ie F-XE) FOLLOWE)) = (),$} MIE, ))=B' +e TF Tecra PUBLICATIONS"- Anup trust fr inowlodge ‘Seamed nth CamScannerer Design 2-10 Syntax. F id Asa A=Fasid FIRST(id) = {id } Hence M[F,id] = F — id ‘The complete table can be as shown below. 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 [idvia wid $ Now symbol E is at top of the stack and input pointer is at first id, hence M[E.id] is referred. This entry tells us E > TE’, so we will push E’ first then T. OB Tecrcnt nimucaTons” An rt town ‘Seamed nth CamScannerQ.27 Construct predictive parsing table for the following grammar : So la L>Ls |S Check whether the (a,a) belong to that grammar or not. ESP[ONTU : Part B, Nov.-15, Narch-17, May-18, Marks 10] Ans: As the given grammar is left recursive ‘because of LL sis. We will first eliminate left recursion. As A — A oil can be converted as AsBA A oa We can write LL, SIS as L+su L Stile Now the grammar taken for predictive parsing is - soMla Lost LU, SLile Now we will compute FIRST and FOLLOW of non-terminals FIRST(S) = (¢ ab FIRST(L) = (( a} FIRST(L) = (4 FOLLOWS) = {',) $) FOLLOW(L) = FOLLOW(L)) = [)} ‘The predictive parsing table can be constructed as 1 T T j | a ¢ ) ‘ s S Sse sou Li L+st’ L+st’ ett Syntax Analy We will parse the string (a, a) using that table Q.28 Show that following grammar : 'S — AaAb|BbBa Awe Boe Is LL (1). SGP [INTU : Part B, May-13, Marks 8] Ans. : Consider the grammar : S— AaAb S — BbBa Ave Boe Now we will compute FIRST and FOLLOW functions. FIRST(S) = (a, b} if we put ‘Seamed nth CamScanner‘Also S— BbBa | Sakb When Ase S—bBa When Be FIRST(A) = FIRST(B) = {e} FOLLOW(S) = {$} FOLLOW(A) = FOLLOW() = {a, b} ‘The LL(1) parsing table is Now consider the string "ba’. For parsing - —_——— Action & ‘This shows that the given grammar is LL(1) Q.29 Consider the grammar S + iESS'| a S' eSle E>b | Whether it is LL(1) grammar. Give the explanation whether (I, t, e, b, a) are terminal symbols. BaP [NTU : Part B, Dec.-14, Marks 16] Ans. : Let the given grammar will be, $+ iCISS'la S > eSle E+b Now we will compute FIRST and FOLLOW for given nonterminals. FIRST(S) = {a} FOLLOW(S) = {eS} FIRST(S) = {e,¢} FOLLOWS) = {5} FIRST(E) = {b} FOLLOW@) = {t} ‘The predictive parsing table will be ‘As we have got multiple entries in M[A,<] given grammar is not LL(1) grammar. The (, te, a, b) are the terminal symbols because they do not derive any production rule. .30 For the following grammar. Do Th LoL, id | id T= int | float 1) Remove left recursion (if required) 2) Find first and follow for each non-terminal for resultant grammar 3) Construct LL (1) Parsing table 4) Parse the following String (Show Stack actions Clearly) and drawe parse Parse tree for the input : Int id, 1d; PLANT : Part B, Marks 5] Ans. : 1) Formula for removing the left recursion is as follows : if A> A a [Bis the rule. Then it can be converted to A= pa’ A's aA'fe DTL; No action as the rule is not left | recursive. | —_ aa LoL id lid Lidl’ ] Ls, id L? | Uo Tint | Float | No action as the rule rule has no left DF recrwicat pus.icaions’- Anup trust forkrowledze ‘Seamed nth CamScannerTn Compiler Design 2B _ 7 Syntax Ana, 2) The first and follow functions : FIRST (D) = {int, float) FOLLOW (D) = (S) FIRST (L) = {id} FOLLOW (L) 3} FIRST (L) = (.€) FOLLOW (L’) = {3} FIRST (1) = {int, oat) FOLLOW (1) = (id) 3) Construction of Parsing table : : Q34 Verify the following grammar Is LL(1) : Sas# SAB Aaale Bo ble Give a trace of the parser for each of the following Input strings a) aab # 1b) ced # separ Ans. : Let S57 IAB Avale Boble ‘be the given grammar. We will eliminate left recursion, A Aa|ByBp, «> AB, A’, A’] .. rt B, May-12, Marks 15] TECHNICAL PUBLICATIONS" An up Oreste ooniadpe (8) ‘Seamed nth CamScannerCompiler Asaa'le SS#IAIB becomes $— AS’|BS° SeSile Hence we get, SAS’ |BS’ SF Sie Anale Boble We will now compute FIRST and FOLLOW for each non terminal symbol. FIRST (8) = {a, b, #}_ FOLLOW () = {$} FIRST (S')={#,e} FOLLOW(S‘)- {$} FIRST (A)={a,2} FOLLOW (a) = {7,8} HIRST (B)= {be} FOLLOW (B) = {#8} The parsing table will be Hence aab # does not belong to this grammar. b) As c d are not generated by any of the non terminal symbols. This string can not be derived from given grammar. Q.32 Construct LL (1) parse table for the following grammar. S Aa | bAc | Be | bBa Asd Bod 5 [INTU : Part B : Dec.-12, Marks 8] ‘Ans. : The FIRST and FOLLOWS can be as follows Syntax Analysis 2.6 Bottom Up Parsing " @33 What are the actions performed by shift ‘A, March-16, Marks 2] reduce parser ? ES [JNTU ‘Ans. : Shift reduce parser attempts to construct parse tree from leaves to root. Thus it works on the same principle 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 L.HLS. and RHS. of rules. ‘The initial configuration of Shift reduce parser is as shown in Fig. Q33.1 ‘The parser performs following basic operations. Stack Input buffer $8 vs, Fig. 0.33.1 Initial configuration 1. 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. FFE recricat PUBLICATIONS" An up trust for krowiodge ‘Seamed nth CamScannerCompiter Design Handle Pruning # Handle pruning is a process detecting the handles and using them in reduction, 4. Error: A shift or redi luce the symbols, it cannot even Perform the accept action is called as error. For example = EsE-E | Consider the grammar ESE+E | > Eid eee Perform Shift-Reduce parsing of the input string eae . ‘Idl-td2v1d3”, ESLONTU : Part B, Marks 5] | Now consider the string id + id + id and the rightmost derivation is So ESE+E Input buffer | Parsing action m mek | ES E+E+E idi-id2*id3$ Shit pa = Eo Exp id) wa2rid3s | Reduce by E> id Bo E+id id) ‘The bold strings are called handles. Right sentential form | Handle Prod | E= id+id+id | Reduce by E> EE | Reduce by E-> E-E Here we have followed two rules. | 1. If the incoming operator has more priority than | | | in stack operator then perform shift. Shift Reduce Parsing - Refer Q.33. 2. If in stack operator has same or less priority : than the priority of incoming operator then | 38 What is operator precedence grammar ? Give parte ers | anexample, ESP [ONTU : Part A, March 17, Marks 2] Ams.: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 tight hand side, Q.35 Define handle and handle pruning. Explain ‘the stack implementation of shift reduce parser with the help of example. (3 [JNTU : Part B, Marks 5) Ans. : Handle : Handle is a string of substring that matches the right side of the production and we can reduce such a string by non-terminal on left hand side production. Formally it can be defined as - Defination of Handle : “Handle of right sentential form ¥ is a production A->B and a position of y where the string B may be found and replaced by A to produce the previous right sentential form in Fi rightmost derivation of 7. This grammar is not an operator precedent grammat as in the production rule, my apiivoeene nese anne ei meicion ig a ‘rcoot Consider the grammar for arithmetic expressions. EEAE | (&)1-B 1 id Aselarsiyia ‘Seamed nth CamScannerSyntax Analysis 2-16 E EAE It contains two consecutive non-terminals. Hence first we will convert it into equivalent operator precedence grammar by removing A. Es E+EIE-EIE*EIE/EIE*E Es @®l-klid In operator precedence parsing we will first define precedence relations <- terminals. The meaning of these relations is. ‘and-> between pair of pod P gives more precedence than q. p+a P has same precedence as q. p> P takes precedence over q. ‘These meanings appear similar to the less than, equal to and greater than operators. Now by considering the precedence relation between the arithmetic operators we will construct the operator precedence table. The operators precedences we have considered are id,t,*,$. Fig. @.36.1 Precedance relation table Now consider the string. id+ideid We will insert § symbols at the start and end of the input string, We will also insert precedence operator by referring the precedence relation table. Scid p+cid ->e$ We will follow following steps to parse the given string - i) Scan the input from left to right until first -> is encountered. i) Scan backwards over = until <: is encountered. iii) The handle is a string between <:and +> ‘The parsing can be done as follows. Gald-s4<-id->§ | Handle id is obtained between <: -> | Reduce this by E> id Evcid s+$ | Handle id is obtained between <- -> | Reduce this by E> id E+E® > | Handle id is obtained between <--> | | Reduce this by E> id WF conven runscarons anon tet tr ondpe ; ‘Seamed nth CamScanner———————————————eeE 2-17 Syntax Analy, Compiter Design = | Remove all the non-terminal, Insert § at the beginning, at the endl, Also Inwert the precedence operators, ‘The * operator Is surrounded by <> > «S and all the items whose dots are not at the leftmost end of RHS. of the rule. Non-Kemel items : The collection of all the items in which * are at the left end of RH. of the mule, 4) Functions closure and goto : These are two important functions required to create collection of canonical set of items. 5) Viable prefix : It is the set of prefixes in the right sentential form of production A- a. Tris set can appear on the stack during shift/reduce action. Q42 Define CLOSURE(). [GP [NTU : Part A, Novi-15, Marks 3] ‘Ans. +: For a context free grammar G, if I is the set of items then the function closure(l) can be constructed using following rules. 1. Consider I is a set of canonical items every item 1 is added to closure(!). 2. If rule A+ aeBP is a rule in closure(1) and there is another rule for B such as By then and initially closure(l) : A °BB Boey This rule has to be applied until no more new items can be added to closure(|). ‘The meaning of rule A-a*BB is that during derivation of the input string at some point we may require strings derivable from BB as input. A non-terminal immediately to the right of + indicates that it has to be expanded shortly. Q.43 Explain GOTO function In LR parsing. ‘Ans. : The function goto can be defines as follows. If there is a production A-ceBB then goto( ‘A-3cBB) = A aBeB. That means simply shifting of * one position ahead over the grammar symbol (may be terminal or non-terminal). The rule ‘A> BB is in I then the same goto function can be written as goto(1B). 44 Construct SLR parsing table for the following grammar E> E+T|T T->T*F|F F->(E)|id? March-16, Nov.-17, Marks 5, Novi-16, Marks 10] ae [UNTY : Part ‘Ans. : We will first construct a collection of canonical set of items for the above grammar. The set of items generated by this method are also called SLR(O) items. As there is no lookahead symbol in this set of items, zero is put in the bracket. FF recnowcat PUBLICATIONS" Anup ts! or rontedoo ‘Seamed nth CamScannerEse EoeE+T Eset To eT Taek Fou) Feld ‘90t0 (lg, E) ‘goto (la, #) 1:65 B+ YyiTo Teak E+Es+T F+ *(E) Foe 991605, 7) IES te ‘oto (1, E) ToT Fo Es) EQ Eee GOO (Ip, F), iTsFe | 9010 (6.7) EsE+To 900 (Ip.() Ta Teor 1:76) ESeEsT fieeerne] Escre Peo Teter pe eE Tae Foe) Foci Consider the rules with numbering as : DE +ET QE 3T 3T +T+F QT 3F )F ~® OF id Input string : id « idvid We will consider two data structures while taking the parsing actions and those are - Stack and input buffer. | Stack ___Inpnt buffer_—_—_Action table |__ Parsing action [9 idsidsids _| [oid ess 3 | Reduce by F> id $01d5 _— SFE reconncat PuELICATIONS'- An up nt for tnowtecgo bacoor’ ‘Seamed nth CamScannerSyntax Analysis | Reduce by T-9 F SGP[INTU : Part A, Dec.-16, Marks 3] Q45 Construct the LR(0) Items for the dangling-else grammar. ‘Ans. : Step 1: The dangling else grammar is as given below - stmt-> if expr then stmt | 4€ expr then stmt else stmt lother Step 2 : The simplified version of above grammar can be written as S2iSliSeSlo Step 3 : The canonical set of LR(0) items is as given below - ‘Seamed nth CamScannerCompiler Design Q.46 Find the LR(0) set of items for the following grammar, Describe state diagram and construct parse table of that S->cc C>eCld SP (INTU : Part B, March-17, Marks 10] Ans. : We will construct canonical set of LR(0) items hi Soes Ty: goto (ly d) ance cia | Q47 Construct the collection of LR(0) item sets Coecc and draw the goto graph for the following Cea | grammar $= SS [ale - Indicate the conflicts (If any) in the various states q goto (I S) goto (Ly, C) | of the SLR parser. SSP INTU : Part B, Marks 5) SaSe S>CCe | Ans.: We will number the production rules in the bh: goto, Q Ig: goto (ly C) | grammar. S3cec CocCe 1S 488 Coece ] 2Sa Coed : 3)Se goto (ly ¢) Now let us construct canonical set of items - Cre0c i Ses This is augmented grammar, mein | Sess Coed | Sea ‘The state diagram is, Se goto (Ty S) Sos S508 Sess i. | ) Sea i Soe | goto (ly a) I Srae goto (I, S) | SSS | SSeS | S— ess | Soea | Soe 3 | TP recica PuaLcATONS'- an wo eter owen mont ‘Seamed nth CamScannerCompiter Design ‘The goto graph will be meres ees El FOLLOW) = {2,5} ‘The construction of SLR(1) table will be. In I, state there is a production rule $ + « a . If we apply goto (Ly a) then we will get I, state. Hence MB, a] = $2. In 1, there is a production S > SS | which matches with Aas Rule S> $5 is rule | number 1. And FOLLOW(S) = {a,$} MB, a] = MI3, $] = Hence conflict occurs in state Iy- Q.48 Construct SLR parsing table for the following grammar S— As|b A= SAla ‘Ans. ; We will construct a collection of canonical set of items for the given grammar. 1G [INTU ¢ Part B, April-11, Marks 10] so8 To: Tg : goto (Io,a) $9AS Ava Seb Ig : goto (11,4) A>sSA A—SAS Ava AGAS Ty: goto (LoS) Seas 8’ Se Soeb ASA AveSA Aw>eSA Avea Asea 1g : goto (1.8) SAS ASA Seb AweSA Avea Ig: goto (lo, A) SAS S3AS Seb $ AS Ty : goto (12,8) Sob SAS A>eSA A SSA Avea AweSA Asea So3eAS Tg: goto (fo, b) Sob S—be We will list out the given rules 1 S3AS FOLLOW 6) = {a,b,$} 2 Sob FOLLOW (A) = {a,b} 3. ASA 4, Asa ‘The parsing table will be FP conan pomrcatons mo eno ‘Seamed nth CamScannerQ.49 Construct the collection of non empty sets of LR(Q) Items for the following augmented grammar, SAE EsTET Ans: Tp:S ek GP[INTU : Part B, Dec.-11, Marks 16] EseTE EseT Ty : goto (Tos) SEe Tz goto (Ip,7) ESTE Es=Te EseTE Eset Ta :goto (fa. B) ETEe Q50 Check whether the following grammar is ‘SLR(1) or not. Explain your answer with reasons. S+L=ER Sak La+R Lia RsL ES [INTU : Part-B, Marks 5] Ans: We will first build a cenonical set of items. ‘Hence a collection of LR(0) items is as given below. I: Ses S+eL-R S3eR LoetR Loeid RoeL qe somes) IP races Pesucanons- aon et er nouncge Site ay gotofl, R) SoL=Re Now we will build the parsing table for the above * of items. State | Action | Goto b- i+ tals fs i uk ‘Seamed nth CamScannerAs we are getting multiple entries in Action (2, +] =56 and 5. That means shift and reduce both a shift/reduce conflict occurs on input symbol =, Hence given grammar is not SLR(1) grammar. -— QSt Construct a DFA whose states are the canonical collection of LR(1) items for the following augmented grammar, SoA A= Bale B—aBlb Ans. : Initially we will start with the rule SoA, $ S [INTU : Part B, Jan.-10, Marks 16] We will add the rules A +*BA and As tol. Now let us map the rule [A >aeXB,a] SA, & with Such that A=S, a=e X=A, Boe a=S. Then second component of A>*BA and A+ Will be = FIRST (Ba) = FIRST (6,8) = FIRST ($) -@ S6A,$ AsBA,$ Aves As there is a rule A>*BA we must add the rules BeaB and B-+eb to Ig. Now to compute second component of B'S rule we will use A+6BA, $ for mapping with [A XB, a] AcA, a=e X=B, B=A, aS ‘Then second component of B—+ea Band B- +b will be = FIRST (Ba) = FIRST (AS) FIRST (A) TTECHICAL PUBLICATIONS" Anup tt fo knowlecoe ou | | | | ‘Syntax Analysis = fabs} = {a,b} BoeaB a/b Boob a/b Ip will be S0A,$ A—eBA,$ Ases Boab a> Boeb ab {goto (Tp, A) S308 goto (Ip, B) ABeA,S AeBA, $ Ase Ss BoeaB afb Boob a/b goto (Ip, a) BoaeB afb BoeaB ap Bosh afb goto (To, b) Bobs a/b goto (12, A) AWBALS goto (Ip, B) BoaBe a/b ‘Seamed nth CamScannerCompiler Design The DFA can be constructed as follows = Q.52 Construct the LR(I) parsing table for the following grammar. 1) § =¢C 2) © 3 3) C aa Ie S468,s S42CC,8 Ca ecc.ed Coedes 1y: g0t0 (lg, 8) S848 1p 90! (Ip. C) S40+,S C900, Caeas Ig 90% (1p, ¢) C4e4C, old Crecc.eld Coded 149040 (lg. d) Code.cld Ans. : First we will construct the set of LR(1) items, Now consider Ip in which there is a rule matching with [A ccecB,b] as C-+©G, od and if the goto is applied on a then we get the state I. Hence we will create entry action{0, a] = shift 3. Similarly, BGP [INTU : Part B, Marks 5] Ts: goto (fC) SocCes, Tg goto (Z, ¢) Cones C400, Coeds Fy: goto (lp. Cordes 1 got, ©) Cece, eld Ig: goto (lg, C) Cee, "TECHNICAL PUBLICATIONS" An up trust or knowtedpe Syntax Analy In, Coed old Avacahd AnGazge gotolly d) =I, hence action(0, d] = shift 4 For state I, Co dada A tase A=Ga=dcndd action[4, c] = reduce by Cd ie, rule 3 S4S+,$ ink, ©—-—® Q——-@® O——- So we will create actionf1, $] = accept. The goto table can be filled by using the goto functions. For instance goto(ly $) = I,. Hence goto[0, $] = Continuing in this fashion we can fill up the LR(l) parsing table as follows. ‘Seamed nth CamScannerThe remaining blank entries in the table are considered as syntactical error. Parsing the Input using LR(1) parsing table Using above parsing table we can parse the input string “aadd” as ‘Action table __action(3 dost action{4.d]=13 | Reduce by C> aC action{8,d]}=12 action{8,d]=12 | ‘Reduce by C+ aC | action(5,S}=r1 0st $s | accept | ‘Thus the given input string is successfully parsed using LR parser or canonical LR parser. 53 Construct CLR parsing table for the following grammar E> E4T | T, TTF [F, F>(E) | id EBINTU : Part B, Nov.-17, Marks 5] ‘Ans. : We will construct canonical set of LR(1) items. be | frgoto dy B | Fo +ES (ESO ESS E> sE+T$ | BoEeens | E> oT$ | To + THES | | To 6k | 3 +@.S | 11: g0to (dy F — ( ToRas | Lo TECHNICAL PUBLICATIONS" Anup bust fo dowd =x ‘Seamed nth CamScannerBO ES TS To +THES To BS Fo @S E> E+T#,$ To Tek | Ty # goto (ig. )) E> @+$ Let us number out the original grammer rules as these rule numbers are used for shift and reudce operations in parsing table. i) E> E+T 2) EoT 3) To T*F 4) TOF 5) F> ©) 6) Foid ‘The parsing table can be given below - State | Action | Goto ‘ T [ow [oe [+ [ic ‘Seamed nth CamScanner“gst Construct LALR parser table for the following grammar for CLR parser. g2L-R, S9RLO*R, R51 re paNTy , May-18, Marks 10] “ans.: To derive the given grammar using LALR method we have to build the canonical collection of items using 1rd) items. ‘The LR() items are hs S3+5$ S3+L=RS S>+R$ LoerR=1$ L «id, +1 Ro+L$ 1, : goto (ly $) S3548 1 g0t0 (ly L) SoL+=RS RLS Ig: goto (ly R) SoR+,$ 1, goto (ly *) Lo+eR=18 1, : goto (ly id) Loids,=1$ hy? hs # goto (ly =) S>L=-RS RoL$ LoeRS Lid, $ goto (ly R) L eRe=ls goto (ly L) RoLy=1$ goto (ly R) SOL=R+,S goto ly 1) RoLs,$ goto (I, *) Lo*eR$ RoL$ LotR S$ Leid $ goto (ly id) Lids $ goto (ly, R) Lo*Re$ ‘Seamed nth CamScannerFrom above set of items we have got | i) I and 1, give same production but lookheads are different. Hence merge them to form yyy ii) Ip" hy Hence Igy iii) y= hy Hence Iy,5, iv) I= ho Hence Ipio ‘Therefore the set of items for LALR are hi S358 Sa+L=-R$ Ing Lae Re 216 S2+R$ Is Igy RL LoeR als Lid, =1$ S> L=R+$ R>-L,$ S3S+,$ SoL+,-R$ RoL+,$ I: SoR+$ Loe. Reals RoLe,=18 LoeR as Leld,= 18 Tg Lid «= Is Ig: SIL=-R$ RLS Lo+*RS$ Lo + id$ From above set of items we have got qian asoaeeae Syntax Anaiyy ‘The parsing table can be constructed as follows - 3 “an [52 [sat Q.55. Give CLR parsing table for the grammar S->L=R |R L->*R |id R->L se [an Ans. : Refer Q.54. art, B, March-16, Marks 5) Q.56 Write an algorithm for computing iat items sets. ESINTU : Part B, Novi-16, Markt Ans. : 1. For the grammar G initially add Se S in tht set of item C. 008 ‘Seamed nth CamScannerFor each set of items I, in C and for each grammar symbol X (may be terminal or nonerminal) add closure (I, X). This process should be repeated by applying goto(I, X) for each X in J, such that goto((I, 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. ‘The closure function can be computed as follows. For each item A->aeX Ba and rule X-+y and bc FIRST a) such that X + y and b is not in I then add X eybtol 4. Similarly the goto function can be computed as : For each item [A > aeXB, a] is in I and rule[A > aXeB,a] is not in goto items then add [A > aX eB, a] to goto items. procedure to construct LALR SGP [INTU + Part B, March-17, Marks 5] Q57 Write a parsing table. ‘Ans.: The algorithm for construction of LALR parsing table is as given below. Step 1: Construct the LR(1) set of items. | Stop 2: Merge the two states I, and J if the first component (ie. the production rules with dts) are matching and create a new state replacing one of the older state such as Rrkey ‘The parsing actions are based on each item I, The actions are as given below. a) ¥ [A aa b] is in |, and goto(ly a) = J then create an entry in the action table action, a] = shift j- b) If there is a production [A> ce, a] in I, then in the action table action Ily,al= reduce by Aa. Here A should not be 8. ©) If there is a production S'S $ in I, then action[i, $] = accept. ‘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) = J, then gotolly Al = j- Stop 3: Stop 4: "FF recrnncat PuBLIGATIONS'- An up Unset or inowedoe =o __ Syntax Analysis. If the parsing action conflict then the algorithm fails to produce LALR parser and grammar is not LALR(1). All the entries not defined by rule 3 and 4 are considered to be “error”. Step Q58 Give LALR parsing table for the following grammar E> E4T | TT->TF [F F->(E) | td [EGYINTU + Part B,.Nov.-25, Marks 10] Ans: Refer Q.53. Q.59 Show that the following grammar. § — Aal bAc| Be| bBa Aod Bod is LR (1) but not LALR(1). ‘Ans. : We will number out the production rules in given grammar. So Aa 2) S+bAc 05 [INTU = Part 8] 3) S3Be 4) S>bBa 53) Aad 6 Bod Now we will first construct canonical set of LR(1) items. S3-S$ Initially for the augmented grammar the second component is $. As this rule [S' > «S,$] is matching with [A > 0X, a] where a is ¢ X is S. B is © and a is $. We will apply closure on S and add all the production rules deriving S. The second component in these production rules will be $. This is because for [S’ +S,$] the B= © and a= $ -.FIRST ( a) = 8, FIRST (¢ $) ~ FIRST (S) = $. Hence we will get S368,$ 1coor ‘Seamed nth CamScannerCompiter Design Now we have got one rule [S -> «Aa, $] which is matching with [A > a«XB, a] and [X — y]. Hence We will add the closure on A. Hence [A —>+d] will be added in this list. Now the second component of A ~ ed will be decided. As [$ > «Aa, $]is matching with [A > AX B, a] having X as A, Bas a and a as 8. Then FIRST (Ba) = FIRST (a8) = FIRST (a) = a, Hence rule [A > +d, a] will be added. Now, S58 SreAa $ SbAGS S—+bBa, $ Aveda Now notice the rule $ > #Bc, $ It suggest to apply closure on B (As after dot B comes immediately) This rule is matching with [A + aX B, a] and [X + Hence we will add rule deriving B. Hence B +d will be added in the above list. Now S ~+Be, $ can be mapped with [A a+X B, a]. Where = a=e X=B Bec a=$ ) ‘Hence FIRST @ a) = FIRST (c $) = FIRST (c) = c. Hence rule [B —> ed, c] will be added. Hence finally 1p will be - Boedc Continue with applying goto on each symbol. 1, : goto (Ip,8) There is no chance of applying | closure or goto in this state, S'> S*,$ Hence it will have only one rule, “Ig + goto ([o/A) Applied goto on A. But as after ! ‘dot a terminal symbol comes we Si Aca $ cannot apply any rule further. ‘The second component is “carried as it is, |After dot A comes hence mule for A—ed will be “1g + goto (Ig, b) S—beAGS$ aaded. As [5 > beAc $]is “matching with SH beBa, $ [As aX B, a and X>y} (Asa FIRST @ a) = FIRST (6) = Geen FIRST (c) = ¢ The second L imenesies [component of A — «dis c aint inmate goto (Ig,B) The goto on B is applied and ‘second component is carried as ‘The goto on d in state Ip is ‘applied with corresponding second components as itis. Continuing in this fashion we will get further states. eee | [anecoce | fee | S-Aas 1 ot Saas KS aere:,| S+bAc $ | | Boarteh S++ Be, $ re = Bn $+ bBa,§ | Tf Tecra PUBLICATIONS An up test er mowncpe senot ‘Seamed nth CamScannerNow using the above set of LR(I) items we will | "construct LR(1) parsing table as follows. | Now we will construct a set of LALR(1) items. In this construction we will simply merge the states deriving same production rules which differ in their second components only. In above set of LR(1) items state Is and Ig are such states i. Ip + goto (13, a) At dec Is + goto (lg, 4) Atdsa Bodec Bods,a We will form only one state by merging state 5 and 9 Tgp goto (lor d) Avds,a/c Bods+,a/c Hence the LALR(1) set of items are given as : pt S988 Ig + goto (I, a) So +Aa$ S Aas, $ S+bAc $ I : goto (Iz, A) S+B,$ S bAcc, $ Aveda Ig : goto (13, B) Boede S— bBea, $ 1, + goto (Io, 8) Tyo # goto @y, ©) S3S,8 S Bee, $ 1, + goto (Ip, A) Ty; + goto (17, 0) Sa Aca $ S— bAce, $ T3 + goto.(Ig, b) Tyg goto (Ig, a) S> beAc $ S— bBas, $ TF recrnncas puBLicaTions- np thus fer inowndoe = ‘Seamed nth CamScanner“Ans. and number it out. L $38 2 Sradd 3 SabBd 4, SraBe 5. S+bAc 6 Aste Bods,a/e 7 Boe ‘The LALR parsing table will be - Now, let us generate LR (1) Canonical set of items, Ig: SSS SoeaAd$ S++bBas i Sr+aBo$ 1 Sra+bAGS goto (Iy,S) > Ig : goto Q,e) | S'3S+,8 Avtesd | Broesc | Ta: goto dp, a) I;: goto (15,B) ) Sa-Ad,$ S>bBed $ fay | ef Ssa+Bo$ — Ig: goto(ls,A) Ri Lud | Avved S>bA+Gs The parsing table shows multiple entries in Action | Boeec + Ip: goto(s,e) [59, a] and Action [59, c]. This is called reduce/reduce | conflict. Because of this conflict we cannot parse | I: goto (Ig, b) Atesc input. | Sob +Bd,$ Boewd ‘Thus it is shown that given grammar is LR(1) but not | Aaah | S> d+AGS —Iyp:goto(y,d) 60 Deslgn LALR (1) parser for following aaa eee grammer | Bo. : S+aAd| bBdlaBe|bAc| meee Tir goto (s,0) Ave 1 i goto (lz, A) S$ aBe Boe ‘SGP [INTU : Part B, June-14, Marks 8) I Z | S-aAed,$ —Iyp : goto (17d) Wf owen pavcmont mmerenonnae aa ‘Seamed nth CamScannerCompiler Design tg: soto /) Saunas s Itis an easiest | This method This method So Bec Mysetoy.g | | mM EERE a a i fens SER. and SsbAce$ Lo | function. 3. tnis method | Most of the This method exposes less syntactic exposes less syntactic features of a syntactic features than language are features than that of LR expressed in that of LR parsers. LALR. parsers. From above construction we can combine Tg and to from Iggstate as, i: ' / ' ' i Ii Aes cddandB> ve od ‘The parsing table can be constructed as follows = Error Error Immediate detection is detection is error not immediate not immediate detection is in SLR. It. requires | The time and The time and less time and space space space complexity is complexity is Lcomplexity. more = in. more for LALR but canonical LR parser. Lt i Using Ambiguous Grammar Q.62 Find the SLR parsing table for the given | grammar. | EDE+E | E*E | (E) lid. ‘As we get Table [69] as reduce/reduce conflict given And parse the sentence (a+b)*e grammar is not LALR. ESPINTU : Part B, Nove-35, Marks 10] Q.61 Compare and contrast between SLR, LALR and LR parsers CS[INTU : Part A, May-18, Marks 10] LR parser or canonical LR parser is | Fargest in size | | TF Tecnrca puaucaTons™ Ano tt or iowedoe z digas RS ts i ‘Seamed nth CamScanner