Scribd
Upload
3 views152 pages

Document From Ritam Datta

The document outlines the course structure and syllabus for Compiler Design, which has been moved from the 7th to the 5th semester at MAKAUT. It includes topics such as lexical analysis, parsing, type checking, and code optimization, along with chapter-wise solutions to university questions. Additionally, it provides insights into the compilation process, including analysis and synthesis phases, and discusses various compiler errors and optimizations.

Uploaded by

Aritra Das
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
3 views152 pages

Document From Ritam Datta

The document outlines the course structure and syllabus for Compiler Design, which has been moved from the 7th to the 5th semester at MAKAUT. It includes topics such as lexical analysis, parsing, type checking, and code optimization, along with chapter-wise solutions to university questions. Additionally, it provides insights into the compilation process, including analysis and synthesis phases, and discusses various compiler errors and optimizations.

Uploaded by

Aritra Das
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
[Link] COMPILER DESIGN Introduction to Compiler 2 Lexical Analysis i 15 Parsing and Context Free Grammar 7 31 Operator Precedence Parsing : 43 Top-Down Parsing 49 Bottom-Up Parsing and LR Parser Generation Theory 62 Syntax Directed Translation 83 Type Checking 99 Runtime Environment 100 Intermediate Code Generation 108 Code Optimization 124 NOTE: MAKAUT course structure and syllabus of 5" semester has been changed from 2020. Previously COMPILER DESIGN was in 7" Semester. This subject has been shifted in 5" semester in present curriculum. Subject organization has been changed slightly. Taking special care of this matter we are providing chapterwise relevant MAKAUT university solutions along with the complete solutions of new university papers, so that students can get an idea about university questions pattems. [Link] =e[Link] POPULAR PUBLICATIONS INTRODUCTION TO COMPILER 1. Which one of the following error will not be detected by the compiler? [WBUT 2010, 2042, 2016) a) Lexleal error b) Syntactic error c) Semantic error 4d) Logical error Answer: (d) 2. Which is used to keep track of currently active activations? [WBUT 2012) a) control stack 6) activation c) execution d) symbol Answer: (a) 3. A compiler that runs on one machine and produces code for a different machine Is called [WeuT 2013) a) Cross compilation b) One pass compilation ¢) 2pass compilation . d) none of these Answer: (a) 4. Which of the following translation program converts assembly language program to object program? [WBUT 2014) a) assembler b) compiler ¢) macro-processor d) linker Answer: (a) 5. Role of preprocessor is to [WBUT 2015] a) produce output data b) produce output to compilers ¢) produce input to compilers d) none of these Answer: (c) 6. Consider the program statement = 2 where bis a B stage of compilation can detect this error? waRoolean vee au 2018) a Lexlal naive ; b) Syntax analysis ¢) Semantic analysis a) ce hier (6) l) Code generation 7. Cross-compileris a compiler [weUuT 2017] a) which Is written in a language that Is. different fr language b) that generates object code for host machine nn Source aneua ¢) which is written in a language that is same as the source language 4) that runs on one-machine but produces object code for another machine Answer: (d) CMD-2 ps://www.instagrdroxehPFanjan_mahato_rkmi/ [Link] +, SQMPILER DESIGN 8. An ideal compiler should IWBUT 2017] a) be smaller in size b) take less time for compilation ¢) be written in a high level language: d) produce object code that is smaller in size and executes faster Answer: (d) 9. Compiler can check .......... Error. + [WBUT 2018] a) logical b) syntax c) content 4) both (a) and (b) Answer: (b) 40. A compiler running on computes with a small memory would normally be : [WBUT 2027] Answer: compiler with several passes 41. A garbage is [WBUT 2022] Answer: allocated storage with all across path to it destfoyed 12. phase of compilation process is an optional phase. ’ [WBUT 2023] Answer: Code optimization 4. With the help of a block diagram, show each phase including symbol table and error handler of a compiler. i -- [WBUT 2007] Using a block diagram Indicate the phases. of compilation explaining their activities. [WBUT 2014} OR, Describe analysis phase of a Compiler with a block diagram. [WBUT 2013] : Ry Describe the errors encountered in different phases of compiler. - [WBUT 2019] Answer: Various Stages of Compiler: Generally we have treated a compiler as a ‘dide box that maps a source program into a semantically equivalent target program. If we open up this box a little, we see that there are two paris to this mapping: analysis and synthesis, The analysis part breaks up the source program into constituent pieces and imposes a grammatical structure on them. Jt then uses this structure to create an intermediate representation of the source program. If the analysis part detects that the source program is either, syntactically ill formed or semantically unsound, then it must provide informative messages, so the user can take corrective action. The analysis part also collects information about the source program and stores it in a data structure called a cMD-3 [Link] a[Link] POPULAR PUBLICATIONS symbol table, which is passed along with the intermediate representation to the synthesis part. If we examine the compilation process in more details, we see that it operates as a sequence of phases, each of which transforms one representation of the source program to another. A typical [Link] a compiler into phases in show in figure below. In practice, several phases may be grouped together, and the intermediate representations between the grouped phases need not be constructed explicitly. The symbol table, which stores information about the entire source program, is used by all phases of the compiler, o cence ‘stream Lexical Analyzer Theva Syntax Analyzer T Syntax tree Syntax Analyzer Syntax tee Symbol Table Intermediate Code Generator Parente ah 4 —- fy Intermediate eae stisca ‘ Tqna -nolficttmere ‘Machine-Independent 4 Code Optimizer 98 USI ratgels teins pecemton * ‘Code Generator T target-machine Code, Machine-Dependent Code Optimizer tgetmabine Code 1 Phases of a compiler Some compilers have a machine-independents optimization phase-between the front end and the back end, The'purpose of this optimization pliase is to perform transformations on the intermediate representation, so that the back end can produce a better target program than it would have otherwise produced from an optimization intermediate CMD-4 hi tps://www.instagriiroxahbFanjan_mahato_rkm/ — [Link] ‘ . . COMPILER DESI representation. Since optimization is jn above figure may be missing. All phases are described using an example: : 1 optional, one or the two optimization phases shown Position = initial +rata* 60 Lexical Analyzer (id,1) want id.3)¢#) (60) ‘Syntax Analyzer “i 1 [postion Gita uN —— id, 2 [itt Me este 3 [te ‘Semantic Analyzer ’ —T id) t Seem, th URS Ps «a3 Brogoa © Code Optimizer + t1=id3 * 60.0 id) =id2+t1 Code Generator LDF R2,id3 MULF R2, R2, #6000 LDF RI, id2 ADDF RI, RI, R2 STFid1, RI fan assignment statement phase of an assemblo?. [WBUT 2010] Translation © 2. What are the analysis phase and synthesis ‘swer: thesis, There are two main stages in the compiling process — analysis and syn D-5 https: liwww: instagriraFanjan_| mahato_| rkm/ —[Link] POPULAR PUBLICATIONS The analysis stage breaks up the source program into pieces, and creates a generic (language-independent) intermediate representation of the program, Then, the synthesis siage constructs the desired target program from the intermediate representation. Usually, the analysis stage of a compiler is called its front-end and the synthesis stage is its back- end. There are four phases in the analysis stage of compiling: Here, the stream of characters making up a source program is read from left to right and grouped into fekens -- sequences of characters having a collective meaning. Here, the tokens found are grouped together using a context-free grammar. The output of this parsing phase is called a parse tree. Here, the parse tree is checked for semantic errors i.e., detection of such things like the use of undeclared variables, function calls with [Link], access violations, incompatible operands, type mismatches, etc. Here, the intermediate representation of the source program is created, usually in a form like three-address code. : The synthesis stage can have up to three phases: Here, code in the intermediate representation (e.g., Three Address Code) is converted into a streamlined version, still in the intermediate representation, but with attempts to produce the smallest, fastest and most efficient running result (collectively called optimization). Here, the target program is generated, as machine code or assembly code. Memory locations ae selected for each variable and instructions are chosen for each operation. This is an optional optimization pass following code generation and transforms the object code into tighter, more efficient object code by considering features of the hardware to make efficient usage of processor(s), registers, specialized instructions, pipelining, branch prediction and other peephole optimizations. - 3. Describe analysis phase of a compiler in respect of the following exam, position = initial + rate * 60 [WBUT 2011) Answer: The analysis phase of a compiler, also known as its “front-end”, breaks up the source Program into pieces, and creates a generic (language independent) intermediate representation of the program. There are four stages in the analysis phase of compiling: Lexical Analysis: Here, the stream of characters making up a source program is read fon. ae to right and grouped info tokens—sequences of characters have a collective For the given example, lexical analysis will break the sentence into a stream of seven toker idl = id2 + id3 _ ida id}, id2 and id3 will be ‘bound’ to Symbol Table entries corresponding to variables Position, initial, and rate, respectively, while id4 will be bound to the constant 60. Syntax Analysis or Parsing: Here, the tokens found are grouped together using 2 context-free grammar. The output of this parsing phase is called a parse tree. The parse tree for the given example will be: . CMD-6 ps://www.instagrdoahhFanjan_mahato_rkm! - = [Link] COMPILER DESIGN: Wh i fit id; * ZN td, tds Semantic Analysis: Here, the parse tree is checked for semantic errors i.e., detection of. such things like the use of undeclared variables, function calls with improper arguments, access violations, incompatible operands, type mismatches, etc. Assuming that in our code the variables are of float type, the semantic analysis will insert a int-to-float conversion of the constant 60 to give OS a + af LN id; inttofloat tidy the intermediate representation of the source Intermediate Code Generation: Here, hree-address code, The set of three-address program is created, usually in a form like 1 codes for the example will be tI = inttofloat(60) 4. ler? Create a cross-compiler for SML (Sensor Mark-up What Is a cross-compllert ren in ATOM-450, producing code In ATOM- Language) using Java compiler, PI 450 and a SML language producing code for XML written in Java. . [WBUT 2012] Answer: 7 : 4 A cross-compiler is a piece of software which runs on a particular environment de that can run on another environment. For example a (processor + OS) and generates co “C’ cross-compiler running on X86-Windows generating code for ARM-Linux. (in SML) Cross-compiler ‘Atom 450 system ‘Atom 450 system . . . ., CMD-7 [Link] tps://[Link]/ra njan_mahato_rkral~ POPULAR PUBLICATIONS 5, Describe the language processing system with a diagram. swert fhe compiler is an intelligent combination of software and hardware, Hardware is simply 2 piece of mechanical equipment and its functions are being compiled by the relevant software. The hardware considers instructions as electronic charge, which ig equivalent to the binary language in software programming. The binary language has only Os and Is. To enlighten, the hardware code has to be written in binary format, — tnput DWBUT 2023) Preprocessor which is just a series of Os and Is. Writing HLL such code would be an inconvenient and s Pate HLL complicated task for computer programmers, Comper) [Link] write programs in a high-level s language, which is Convenient for us to Assembly Language comprehend and memorize. These progtams are then fed into a series of devices and operating system (OS) components to obtain the desired code that can be used by the machine. This is known as a language processing system. Preprocessor: It iricludes all header files and also evaluates whether a macro(A macro is a . piece of code that is given a name. Whenever the name is used, it is replaced'by the Contents of the macro by an interpreter or compiler. The purpose of macros is either to automate the frequency used for sequences or to enable more powerful abstraction) is included. It takes source code as input and produces modified source code as output. The preprocessor is also known as a macro evaluator, the processing is optional that is if any language that does ot support Hinclude macros processing is not required. Compiler: The compiler takes the modified code as i input and producestthe target code as output. Assembler Otjecteode Linker/Loader ‘Absolute machine code Executible Code aa Error mesSages Warnings Assembler: The assembler takes the target code as input and produces real locatable machine code as output, Linker: Linker or link editor is a program that takes, a collection of objects (created by assemblers and compilers) and combines them into an executable program. Loader: The loader keeps the linked program in the main memory, CMD-8 s://[Link]\ahiFanjan_mahato_rkm/_ «tt jg low-level and machine-speci cote: It 18 low-t vachine-specific code. that i syne rand. ONCE the job of the linker and loader is done pantie cet ender ox sil) itinto executable code. pal converted Long Answer Type san the afferent phases of a compiler, showing the outout of mak: pli Ls) E12 ample of the following statement: : teat ot yeu 2000) pitt: zinitial + rate * 60 : OR, ing statement is translated via the different phases of compilation? itial + rate “70. {WBUT 2010] oR, gga diffrent stages of compiler with a suitable example. [WBUT 2013] | aaswers iyer'e Question No. 3 of Short Answer Type Questions. bjcompare compiler anc interpreter. [weUuT 2003] oR, Distinguish between interpreter and compiler. [WBUT 2012] Aswer: Compiler scans whole code'at once so it is fast on the other hand interpreter scans the be code line by line and converts in machine code so it is slow. Compiler creates executable file that runs: directly on: the CPU but interpreter does not rate direct executable file. : Gmpiter uses more memory - all the execution kr Inepreter uses less memory, source code only Remary ode needs to be loaded into memory. hae to be present one line at a time in nly all the phases of compiler and show the corresponding output in every or the follow rogram: wing code of the source prog tials wl Naswer: Mey 2 nyey—3 cal analysis ‘ Sine ‘ont generates the tokens ecb oe sid, Sm Sid,’ 3! and analysis stage generates the parse tree s AS AL 1 ' iy id 1 3 ww cMD-9 https :/www.instagrirocehhFanjan_mahato_rkm/ tps://[Link]/ranjan_mahato_rkm/ - POPULAR PUBLICATIONS ‘The intermediate code generates 3-address code as: 100 : if (y>=t) goto 102 tol 102 : T=y- 103: YT 104 : goto 100 The code optimizer optimized this code to 100 : if (y = <4> <*> -<109 Syniax Analyzer z a <7 Sos , ‘Semantic Analyzer “ee a PO 70 4 Intermediate Code Generator v 1) = int to float (70) ids * ids Code Optimizer ¥ ty ids * id waut700 id) = id: +t Code Generator LDF —Rs,idy LDF ,,[Link] MULF ‘ADDF LDF s ADDF STF tan |n detail the process of compilation. Develop the output of each phase of Aas marplation fortheinputa = (b +c) * (b+ c) *2 [WBUT 2019] Pen Refer to Question No. 1 of Long Answer Type Questions. ‘MD-11 https: IIwww. instagrdrmcaRh\Fanjan mahato_rkm/ hiitps://[Link]/ranjan_mahato_rkm/~ Tokens for the expression 1 Symbol‘ Category. A Identifier = operator Assignment( 1) B Identifier #2 : + operator Arithmetic( 1) c Identifier 8 * operator Arithmetic(2) ( operator Open parenthesis(1) ) operator Closed parenthesis(1) 2 Constant #4 Phase 2: Syntax Analysis inttoreal (2) zbtc T2 *. 72 13 * TL Phase 4: Intermediate Code generation >> MOV R2,b >> ADD R2,c >> MUL R2, R2 >> MUL R2, #2.0 >> MOV R2, a Phase 5: Code optimization >> MOV b,R2 >> ADD R2,c >> MUL R2, R2 >> SHL R2 >> MOV R2, a 5. a) What is a compiler? b) Explain the different phases of compilor with an example. ¢) Compare and contrast between a compiler and an interpreter. [WBUT 2022] Answer: a) A compiler is a special program that translates a programming language's source code into macine code, byte code or another programming language. 6. Write short notes on the following: a) Cross Compiler [WBUT 2008, 2010, 2013, 2016] b) Chomsky classification of grammar [WBUT 2012] CMD-12 . [Link] re [Link] COMPILER DESIGN Answer 2) Cross Compiler: : Across compiler is a compiler capable of creating executable code for a platfc ther than the one on which the compiler is run. Cross compiler tools are used t se ate executables for embedded system or multiple platforms. It is used to ‘compile “Tor a platorne ot wish it is not feasible to do the compiling, like microcontrollers that The fundamental use of a ctoss compiler is to separate the build environment from the target environment. This is useful in a number of situatior « Embedded computers where a device has extremely limited resources. © Compiling for multiple machines—a company supporting several different versions of OS, a single build environment can be set up to compile for each of these targets. © Compiling on a server farm. © Compiling native code for emulators. b) Chomsky classification of grammar: Type 0, Grammar is any phrase structure grammar without any restrictions. To define the other types we need a definition. In production of the form @Ay->da. y, where A is a variable, @ is called the left context vy, the right context and $a y the replacement string, , Example: (a) i) In abAbed->abABbcd, ab is the left context, bed is the right context, | a=ab i) In AC->A, A is the left context, is the right context. a: erases C when the left context is A and the right context is “. iti) a) In C-> , the left and right context are “.a=* The production simply erases C when in any context. Type 1, Grammars is a p' =" The production simply roduction of the form @Ay-rha y is called type | production if a# Intype | production erasing of A is not permitted. : : A grammar is’ called Type 1 or context sensitive ot context dependent if all the productions are Type 1 production. The production S> is also allowed in a Type 1 grammar, but in this case $ does not appear onthe R.H.S of. any production. Example: (6) i) \n aAbcD->abcDbcD is the type | production. a, beD are the left context, and right context. i) AB-> AbBc is a type | producti iii) A-> abA is atype | production. ‘on. The left context is A and right context is” The both left and right context is “. Type 2, Grammars is a production of the form A->at, where A,BeVx and e(Vyu 5)" In other words, the L.H.S has no left context or right context, ‘ A grammar is called Type 2 or context free grammur if all the productions are Type 2 Productions, * Example: (c) S >Aa, A ->a, B -Pabc, A -34, are type 2 productions, aa _. CMD-13 [Link] ~hittps://[Link]/ranjan_mahato_rkm/ POPULAR PUBLICATIONS Type 3, Grammars is a production S -> ‘is allowed in type 3 grammar, but in this case S does not appear on the right-hand side of any production. A grammar is called Type 3 or regular grammar if all the productions are Type 3 * productions. 2 Example: (d) S >aS, A ->a, A->aB, are type 3 productions. Language: A language L over an alphabet A is a collection of words on A, A" denotes the set of all words on A. Thus a language L is simply a subset of A’. eg. 2 {a,b} then = {A,a, b, aa, ab, ba, bb, aab, bbb...) The set {a, aa, aab} , is a language on £, Because it has a finite number of sentences, we call it a finite language. The set L= {a"b" : 120) is also a language on E, The string aabb and aaabbb are in the language L, but the string abb is not in L. This language is infinite. CMD-14 ps://www.instagrdroxehPFanjan_mahato_rkm/ [Link] SOMPILER DESIGN ' LEXICAL ANALYsis 4.1f.x Is a terminal then FIRST (x) is [WBUT 2007, 2008, 2010, 2012, 2014, 2016, 2017] ae ») {x} c) xt 4) none of these Answer: (b) 2. The regular expression(a|b)*abb denotes a) all possible combinations of a’s and b’s b) set ofall strings endings with abb c)_setofall strings starting with a and ending with abb d) none of these y IWBUT 2009, 2016] Answer: (b) ‘ : 3. The following productions of a regular grammar generates a language L. SsaS |bS]a|b The regular expression for Lis [WBUT 2008, 2015, 2016] a) a+b b) (a+5)" ©) (a+b)(a+b) — d)(aa+bb)a® Answer: (c) 4. White spaces and tabs are removed in [WBUT 2011, 2018] a) Lexical analysis: b) Syntax analysis ¢) Semantic analysis ) all of these Answer: (a) 5. Which of the following is used for grouping of characters into tokens? a) Parser b) Code optimization [WBUT 2013] c) Code generator d) Lexical analyzer ‘Answer: (d) .. or scanning is the process where the stream of characters making up rce program is read from left to right grouped into tokens. [WBUT 2013, 2019) 8) Lexical analysis , b) Diversion °c) Modeling d) None of these swer: (a) 7. Thé regular expression representing the set of all strings over (x, y) ending with beginning with yle . ~ _ [WBUT 2046} D)xx(x+y)*y py y(x+y) ax ©) yy (x+y)tx d) y(xy) * xx Answer: (b) CMD-15 https / www. instagriroxeehbFanjan_mahato_rkm/ tps://[Link]/ranjan_mahato_rkm/ POPULAR PUBLICATIONS 8. The basic limitation of Finite State Machine is that [WBUT 2016) a) it cannot remember arbitrary large amount of information b) it cannot recognize grammars that are regular c) it sometimes recognize grammars that are not regular d) all of these Answer: (a) [WBUT 2018} is {tput of lexical analyzer? 9. What is the, outpu oy HABUT 2048 a) A parse tree b) Alist oftokens —_¢) A syntax tree Answer: (b) 10. Regular expression (x/y) (x/y) denotes the set + [WBUT 2019] a) (xy, xv} b) fox xy, 1 WP ce) {x,y} D&W ‘Answer: (b) 44. The regular expressions denote zero or more instances of an x ory is $ [WBUT 2019} a) (x+y) b) (x +y)* c) (x* + y) ) (xy)* Answer: (b) 12, Input to LEX is [WUT 2022] Answer: string 13. Give a finite automation M = (Q, 5, 8, q0, F). If 5 maps Q x 5 to 2 Q, then [WBUT 2022] Answer! aNFA 14. If wis a string and |=” then the number of prefixes of w are [WBUT 2023] Answer: n+1 . 45. Given two DFA’s M1 and M2, They are equivalent if i. 4 [WBUT 2023] Answer: . MI, and M2 accepts the same language, i.e. L(M1) = L(M2) 46. The number of subsequences of a string w of length n are _' : TWBUT 2023) Answer: 2" 17. LEX isa yt, : [WBUT 2023] Answer: Computer program that generates lexical analyzers. CMD-16 ttps://[Link]\cahPFanjan_mahato_rkm/ r . [Link] . COMPILER DESIGN Short Answer Type Questions 4, What do you understand by terminal table and literal table? [WBUT 2006, 2008, 2010, 2011] Answer: x During lexical analysis, after a token is identified, first the terminal table is examined. If | the token is not found in the table, a new entry is made. Only the ‘name’ attribute of the token goes in, the remaining information is inserted in later phases. On the other hand, numbers, quoted character strings and other self-defining data are classified as ‘literals’ and go to the literal table, If the literal is not found in the table, anew entry is made. The lexical analyzer can determine all the attributes of a literal as well as its intemal representation, by looking at it. 2. What is a lookahead operator? Give an example. With the help of the look ahead concept show how identifiers can be distinguished from keywords. . [WBUT 2007, 2009, 2016] Answer: For certain programming languages, the lexical analyzers may have to look ahead a few symbols beyond the end of 2 lexeme before they can determine a token with certainty. In LEX, the lookahead operator is‘. 5 For example, in Fortran-77, the token IF can be the keyword “IF” or it can be the name of a function/array as in IF(10, 5). It is the keyword only if pair of parentheses has been seen, followed by a letter. Hence, in a Lexical : Analyzer for Fortran-77, we would specify the keyword IF as: IF/: {letter} where we assume that the definition {letter} means any letter. [Link] the NFA for the following Regular Expression. Then find a DFA for the same language. a (aby * abb [WBUT 2008, 2013] Answer: . The required NFA is: é https :/www.instagrfiaicaRBlFanjan_mahato_rkm/ =—[Link] POPULAR PUBLICATIONS t DFA directly from [not by menerstiny NFA] the regular expression : Sota ” [WBUT 2010, 2011, 2016) Answer: ie ‘The required DFA for the language L = (a|h)* ab [Link] given b OOS OHO th king process of lexical Analyzer. §. Describe with diagram the working pi Tr ants anvacatin below; Answer: ‘The operation of the Lexical Analyzer is explained in the diagram below. Token Stream, Source Code LA * Parser Get Token Symbol Table The Lexical Analyzer breaks down the source program into tokens like keywords, constants, identifiers, operators and other simple tokens. A token is the smallest piece of text that the language defines. Keywords are words the language defines, and which always have specific meaning in the language like if, else, int, char, do, while, for, struct, return, ete in C/C++, Constants are the literal valued items that the language can recognize, like numbers, strings, and characters, Identifiers are names the programmer has given to something, These include variables, functions, classes (in C++ and other object-oriented languages), enumerations, etc. Each language has rules for specifying how these names can be written. Operators are the mathematical, logical, and other operators that the language can recognize, For identifiers, the Lexical Analyze also uses'a "Symbol Table” — a data structure it shares with the Parser and subsequent phases of compilation, 6, Define ragular expression, Write the regular expression over alphabet {c,b,c} containing at least one 'g' and at least one ‘h', What Is dead state? Explain with sultable example, [WBUT 2012] Answer; A regular expression (RE) Is defined recursively as follows: e isan RE alsanRE, where ''a'ee | If R, and R, are REs, then so are CMD-18 ps://www.instagrdroxeFanjan_mahato_rkm/ [Link] Rt hy RR and R’. Required RE is: [(erbeealo¥ +6) ete) |(o+b+e) (04+) elasdsey) Ina finite state automata; a dead state is one such that = that input keeps the automata in that state is reached, any input keeps a state. Example: is reached, any jutomata in that Here, C is a dead-state, 7. How does lexical analyzer help in the process of compilation? Consider the following statement and find the number of tokens with type and value as applicable; void main () int x; x=3; t } * : [WBUT 2012] Answer: The lexical analyzer breaks down the source code into a stream of ‘tokens’. The grammar ofa language is expressed in tetms of tokens where similar types of | tities are treated similarly. For examples, variables and constants are considered as identifiers’ . This helps in the compiler being based on a language of token types, which is not dependent on the particular source code being compiled, There are total 13 tokens: Void: Keyword ou identifier ) { (3, yb ame dT Gui int: keyword \ ‘i X + identifier x ‘i Todt P cuiati 35 idemifier \ https :/www.instagrdfosaFanjan_mahato_rkm/ [Link] Popul JBLICATIONS, } 8. What is Token, Pattern and Lexeme? Answer: Lexeme: group of characters that form a token Token: class of lexervies that match a pattern «Token may have attributes, if more than one lexeme in token Pattern: typically defined using a regular expression « REsare simplest language class that’s powerful enough [WBUT 2013) 9. Convert the following NFA to an equivalent DFA. [WBUT 2015) Answer: To Remove Epsilon moves we follow following steps: © Find Closure of all states which have null moves ‘© Mark these states which have null moves Make a revised transition table without epsilon column and Find all possible transition for those marked states by using their Closures. © We will get nfa without null moves/epsilon moves Initial transition, table: 4 States fa [b Je epsilon QO { Qs, Qs} Q Qs Qe a QQ 2 & 3 { Qs, Qr} Q Qe a. Finding Closure of Qy, Qs, Qe Closure (Q1) = {Q1, Q2, Qs, Qs, Qz} Closure (Qs)= {Qs, Qe, Qi} Qa Closure (Qs) = {Qi, Qs} We find a transition table after following above steps which is: States Input a c Q Qs, Qe Qs Q Qu CMD-20 s://[Link]#Fanjan_mahato_rkm/ : [Link] COMPILER DESIGN Qs Qu Qe Qs Qs s : so if we change the nfa to a dfa the transition table and the comesponding dfa will be as follows: . States Input a c Q Qs. Qe Q Qs Q Qs Q Qe Q § Qs Qs Qs : i Q * 40. Find out regular expression corresponding to the finite automata: [WBUT 2016] pg [Next State Next State a at_| at.q2 = q2_| a3 g2, q2 q3_|q2 = 1 Answer: The DFA table is Present State | Next state on a_[ Next state on b” qi qi. q2 = @2 3 @ (ql. 42) Cal, 42, 43) q2 1 (ql. q2, 43) (ql. 2, 43) q2. 3 @ = Ifwe consider q3 as final wate then the state diagram be like below a So the regular expression is a*b*(a.a b*)*2. , (WBUT 2019) ° ‘1. Define NFA. ‘RSwer; ANon- deterministic Finite Automata or NFA has five states (Q, 2, 40, F, 6) where https: liwww. instagrifroxcaFanjan_| mahato_ rkm/ https ://[Link]/ranjan_mahato_rkm/- POPULAR PUBLICATIONS 1. Q: finite set of states 2. Zi: finite set of the input symbol 3. 0: initial state 4. F: final state 5. &: Transition function An NFA can be represented by digraphs called state diagram, In which: (i) The state is represented by vertices. (li) The are labeled with an input character show the transitions. (iii) The initial state is marked with an arrow. (iv) The final state'is denoted by the double circle. 12. Re nt the following sets by regular expression: [WBUT 2023) a. Th of all strings over {a, b} which consists of all words with exactly two a's b. The set of all strings over {a, b} which consists of all words that contain aza or bbb as substring. - Answer: a) bYab*ab* b) (¢+btbb)(atabtabb)*aaa(e+b+bb)(atabtabb)* + (etataa)(b+ba+baa)*bbb(eta+aa)(b+ba+baa)* 4. What do you mean by Thomson Construction? Explain with an example. [wel UT 2018] Answer: To construct an NFA from a regular expression, we present a technique that can be used as a recognizer for the tokens corresponding to a regular-expression. In this technique, & regular expression is first broken into simpler subexpression, then the corresponding NFA are constructed and finally, these small NFAs are combined with the help of regular expression operations. This construction is known as Thompson's construction. Thompson Construction Example: Develop an NFA for the RE: (xly)* First create NFA for (xly) Then add in the closure operator CMD-22 ps://[Link].ahPFanjan_mahato_rkm/ - [Link] COMPILER DESIGN 2. What Is Rogular Expression? Write the ragular expression for: a) R= R1 + R2 (Union operation) 8 6 re pemerantel b) R =R1.R2 (Concatenation operation) 1" (Kleen Clouser) d) R=R + (Positive Clouser) e) Write a regular expression for a langua: taining steht it ane sae guage containing strings which end with f) Construct a regular expression for the language containing all strings having any number of a’s and b's except the full string. Answer: 1" Part: Refer to Question No. 6(I" Part) of Short Answer Type Questions. 2" Part: a) If RI and R2 are regular expressions. then RI | R2 (also written as RI U RZ or RI + R2)is also a regular expression. L(RIIR2) = L(RT) U L(R2). b) If RI and R2 are regular expressions, then RIR2 (also written as RI.R2} is also a regular expression. L(RIR2) = L(R1) concatenated with L(R2). ©) If RI is a regular expression, then RI* (the Kleene closure of RI) is also expression. L(RI*) = epsilon U L(RI) U L(RER1) U L(RIRIRI) U.. Closure has the highest precedence, followed by concatenation, followed by union. M. R+ is a regular expression whose 2 regular d) RS is a regular expression whose language is L, language is Lt. €) The Regular expression for a language containing swrings which end with “ab” is: R.E.=(a+b)* abb A set of strings of a’s and b's ending with the string abb. So L = {abb, aabb. babb, aaabb, ababb, .. a f) The regular expression for the language which containi number of a’s and b’s except the full string is: Regular Expression (RE) = (a+ by. = {e, a, aa. b, bb, ab, ba, aba, bab, ..... } any combination of a bination with a and b even a null string. ing all strings having any This will give the set as L and b. The (a + b)* shows any com! 3. Consider [Link] expression (a+b)*a(a+b)(a+b) a) Augment the expression and construct the syntax tree for the above regular expression, . b) Find Firstpos() and Lastpos() for every internal node in the syntax tree ¢) Find Followpos() for every position in the syntax tree iven RE using followpos() d) Construct the corresponding DFA for the g| (WBUT 2022] https :/www.instagriroxaivFanjan_mahato_rkm/ _[Link] POPULAR PUBLICATIONS Answer: \. a) r'=(alb)*a(a\e)(al6)# b) Firstpost 1.2.3} + Lastpest6.7} 8 Firstpos{8} Lastpos{8} Firstpos|6, 7) Firsipost1, 2,3) Lasipos/6, 7} Lastposti 3} b 6 Firstpost6} 7 Firstpost7} Firsipos{ 1.2.3} Lastpos{6} —Lastpos{7} Lasipos(3} b ae 5 2” Firstpost4} ° Firstposis) Firstpos| 1, 2} ‘Lastpos{1, 2) 3 Lastpos{4} Lasipos|5)} Firstpost 3} Lastpos{3 Firapos(1,2) Lasposit, 2} * b ' 2 * Firsipos{)}—Firstpos{2 Lastpos{l} Lastpos}2) CMD-24 ps://www.instagrdroxehPFanjan_mahato_rkm/ ps://[Link]/ranjan_mahato_rkm/ COMPILER DESIGN Followpo ie a 9) — Followpo +23} Followpost 5} . Followpos(: 7 Followpos(5) 7 a F [Node Followpos a 1_{- (1.2.3) b 2 (1.2,3} a 3 (4.5) a 4 {67} b 3 {6.7} a 6 {8} b 7 {8} #8 —{} UT 202; 4.) What is LEX? wat ! ) Explain the working of LEX. ®) Show the step by step construction of a lexical analyzer with the following three tokens : ‘a * abb * abt Answer: i ‘Yani b) Refer 10 Questions No. 3.(b) of Long Answer Type Questions. D- j[Link] stagrifiticaRFanjan_mahato_rkm/ s:/[Link]/ranjan_mahato_rkm/ POPULAR PUBLICATIONS c) Design of a lexieal analyzer gencrator :RE to NFA to DFA Lex specification with NFA regular expressions p faction} pr; {action} > sn oye p, _ {action,} Ls construction DFA From Regular Expression to NFA (Thompson's Construction) é 0 D 2 O40 nin = Ke Ws “.ORTORDO . CMD-26 ps://www.instagrdroxehPFanjan_mahato_rkm/ rt https J/[Link]/ranjan_mahato_rkm/ COMPILER DESIGN Combining the NFAs of a Set of Regular Expressions 2.0.6 a {action} ab fection LH) %O++O2.O+O a*b+ {action} 2 b b, 5+ none action; action, When two or more accepting states are reached, the first action given in the Lex specification is executed a | I Sie] e \ EE] https :/www.instagrdiosetFanjan_mahato_rkm/ ps://[Link]/ranjan_mahato_rkm/ POPULAR PUBLICATIONS e-closure and move Examples e-closure({0}) = movet {0,1,3, 7s e-closure({2, 4,7} move({2,4,7}+4) ={7} e-closure({7})= {7} move( {7}, b)={8} e-closure( {8}) = {8} move( {8}, a)=2 A a o =—+ none z Also used to simulate NFAS Minimizing the Number of States of a DFA : : a SGP 5. Write short notes on the following: a) YAAC [WBUT 2006, 2007, 2009, 2012, 2013, 2014, 2016] b) LEX [WBUT 2007, 2009, 2012, 2013] ¢) Thompson's Construction Rule * [WBUT 2007, 2014] d) LEX and YAAC [WBUT 2010, 2011, 2018] Answer; a) YAAC: yace assumes that the user has supplied a lexical analyzer which is an. integer-valued function called yylex. The function returns an integer, the token number, representing the kind of token read. If there is a value associated with that token, it should be assigned !0 the external variable yylval. The parser and the lexical analyzer must agree on these token numbers in order for communication between them to take place, €MD-28 . tps:/)[Link]#lrowahiFanjan_mahato_rkm/ - [Link] In normal practice, one uses LEX to generate the lexical analyzer which is then piggybacked into the parser code generated by yacc. b)- LEX: ‘ Lex is a program that generates lexical analyzers. Lex is commonly used with the yace parser generator. Lex is the standard lexical analyzer generator on many Unix systems. Lex reads an input stream specifying the lexical analyzer and outputs source code implementing the lexical analyzer in the C programming language. The structure of alex file is intentionally’similar to that of a yace file: files are divided up into three sections, separated by lines that contain only two percent signs, as follows: Definition section %% Rules section %% Ccode section The definition section is the place to define macros and to import header files written in C. It is also possible to write any C code here, which will be copied verbatim into the generated source file. The rules section is the most important section; it associates patterns with C statements. Patterns are simply regular expressions. When the lexer sees some text in the input matching a given pattern, it executes the associated C code. This is the basis of how lex operates. The C code section contains C statements and functions that are copied verbatim to the generated source file. These statements presumably contain code called by the rules in the rules section. In large programs it is more convenient to place this code in a separate file and link it in at compile time. ¢) Thompson’s Construction Rule: Given any RE, it is possible to algorithmically construct an NFA such that the language accepted by the NFA is exactly the language expressed by the RE. This is done by systematically using the constructs for the basic primitives and operators ofan RE and building ups using Thompson's Construction process. The steps are: Step-1, Parse the given RE into its constituent sub-expressions. Step-2, Construct NFA-s for each of the basic symbols in the given RE. For ¢, construct the NFA as in Fig-1. Here i is a new start state and fis anew accepting state. It is clear that this NFA recognizes the RE {¢}- For every a [Link] alphabet S, construct the NFA as shown in Fig-2. Here again iis anew Start state and f is'a new accepting state. It is clear that this NFA recognizes the RE {a}. If a occurs several times in the given RE, a separate NFA is constructed for each Occurrence of a. Fig 1. NFA fore Fig 2. NFA for a character of the alphabet CMD-29 [Link] ttps://[Link]/ranjan_mahato_rkm/ POPULAR PUBLICATIONS Step-3, Combine the intermediate NFA-s inductively. until the NFA for the entire expression is obtained. Each intermediate NFA. produced during the course. of construction corresponds to a sub-expression of the given RE and has several important properties ~ it has exactly one final state, no edge enters the start state and no edge leaves the final state. P . Suppose N(s) and N(t) are the NFAc-s for regular expressions s and t, respectively. The NFA-s for regular expression sit, st and s*, the composite NFA-s N(s|t), N(st) and N(s*) are constructed as shown in Fig- 3, Fig-4 and Fig-5, respectively: Fig: 3 Fig.:5 4) LEX: Refer 10 Question No. 3(a) of Long Answer Type Questions. YAAC: Refer to Question No. 3(b) of Long Answer Type Questions. CMD-30 ps://www.instagrdroxehPFanjan_mahato_rkm/ [Link] SOMPILER DESIGN PARSING AND CONTEXT FREE GRAMMAR: ni 4, fall productions in a grammar G = (V,T,S,P) are of the form A->xB or A->x, ABe Vand x eT, then it is called: . a) Context-sensitive grammar b) Non-linear grammar eure ¢) Right-linear grammar d) Left-linear grammar 2. An inherited attributes is the one whose initial value at a parse tree node Is defined in terms of : [WBUT 2009, 2045] a) attributes at the parent and/ or siblings of that node b) attributes at children nodes only : . c) attributes at both children nodes and parent and / or siblings of that node d) none of these % Answer: (c) 3, The Intersection of a regular language and a contoxt free language is [WBUT 2008] a) always a regular language b) always a context free language c) always a context sensitive language d) none of these Answer: (b) 4, The grammar E E+E | E°E | ais [WBUT 2010, 2013] a) ambiguous ¢) not given sufficient information Answer: (2) b) unambiguous d) none of these 5, Parse tree is generated in the phase of [WBUT 2041, 2018] b) Semantic Analysis a) Syntax Analysis a Code: Gprvntzation d) Intermediate Code Generation Answer; (a) 6.{fthe attributes of the parent node depends on Its children, then its attributes are called . ’ » [WBUT 2012] a) TAC b) synthesized’ ¢) Inherited d) directed Answer: (c) 7. The expression wew where w belongs to {a, b} * Is {WBUT 2014] a) regular b) context free ¢) context sensitive d) none of these Answer: (b) https www. instagriroxshFanjan_mahato_rkm/ ee[Link] POPULAR PUBLICATIONS 8, The grammar S— Sa, [Sa |, [0 (WBUT 2045) a) is loft recursive 'b) has common left factor c) is left recursive and also has common left factor d)is a CFG Answer: (a) 9. An annotated parse tree is a parse tree [WBUT 2016] a) with values of only some attributes shown at parse tree nodes b) with attribute values shown at the parse node c) without attribute values shown at the parse tree nodes d) with grammar symbols at the parse tree nodes Answer: (b) 10. The output of the parser is [WUT 2017] a) tokens b) syntax tree ¢) parse tree, d) non-terminals Answer: (c) 4 [WBUT 2018] 44. The grammar S — aSa| bS | cis a) LL(1) but not LR (1) b) LR(1) but not LL(1), ¢) Both LL(1) and LR(1) 4d) None of these Answer: (c) 12. Grammar of the programing is checked at........ phase of compiler.{WBUT 2019] a) Semantic analysis b) Syntax analysis ¢) Code optimization 4) Code generation Answer: (b) 13. A grammar that produce more than one parse tree * [WBUT 2019] a) Ambiguous —b) Unambiguous _c) Regular ¢) All of these Answer: (a) af general phase structured grammar. [WBUT 2013] b) Regular ©) Context tree 4) All of these Answer: (a) 15. Given a grammar G = (V, T, P, S) and every production in P is of theform Aa where Ais in V and ais in (V UT)’, then G is_ [WBUT 2022) Answer: context free grammar 16. The intersection of a reguiar language and a context free language is gece BUT 2023) Answer: context free MY , 17. Aloft recursive grammar cannot be LL(1), (True / False). [WBUT 2023) CMD-32 ttps://[Link].caPFanjan_mahato_rkm/ : i [Link] COMPILER DESIGN ‘Answer Truc ‘ 4g. Ga, TPs S) is a context free grammar. The L(G) will be infinite iff . [WBUT 2023] Answer? . There exists w € L(G) with | <|w] Etn*nntntn . The handles are underlined. A predictive parser is a recursive descent parser that does not requiré backtracking Predictive parsing is possible only for the class of LL(k) grammars, which are the context-fteé grammars for which there exists some positive integer k that allows a recursive descent parser to decide which production to use by examining only the next k tokens of input. (The LL(k) grammars therefore exclude all ambiguous grammars, as well asall grammars that contain left recursion. Any context-free grammar can be transformed into an equivalent grammar that has no left recursion, but removal of left recursion does not always yield an LL(k) grammar.) A predictive parser runs in linear time. A table-driven non-recursive predictive parser (for an LL(1) grammar) uses an explicit - Parsing stack and a parsing table M[A;a] (where A is a nonterminal and a is‘a terminal) Where an entry M[A:a] is either a production rule or an error. A predictive parsing algorithm uses this table to carry out top-down parsing. 2. Consider the following context-free grammiar: [WBUT 2008, 2009] S— 88+ ss*|a : a Show how. the string aa+a* can be generated by this grammar. Construct a parse tree for the given string. ©) What language is generated by this grammar? nswer; 4) The string aa+a*’can be generated by the rightmost production: SSS" Sa* > 88 +a" Sa+a*—raatat CMD-33 ,nttps /www.instagrdroetiFanjan_mahato_rkm/ tps://[Link]/ranjan_mahato_rkm/- ILAS Is b) The required parse tree is: ‘ at ¢ ; “nt fol ae ©) This grammar generates Binary Postfix Expressions involving @ with + and * as the s only operators. 3, Consider the following left-linear grammar: [WBUT 2008] S—> Sub| Aa A> Abb| bb Find out an equivalent right-inear grammar. Answer: 2 . This grammar generates the regular language (bb)+a{ab)+ where + means “one or more occurrences”. An equivalent right-linear grammar is: S + bbS | bbad A-raba|ab 4, What is a handle? (WBUT 2008, 2016, 2017] Consider the grammar E>E+E\E*E|id Find the handles of the right sentential forms of reduction of the string id+id *id Answer: A handle of a right sentential form gamma is a production A—>b and a position in “gamma where the string beta may be found and replaced by.A to get the previous right- sentential form. The given grammar is ambiguous. There are two right-most derivations for the string id + id * id. We give both the rightmost derivations. underlining the handles in each case. EE+EE+E*E E+ E*id > E+id* id id +id* id EE*E > E*id +E+E*id +E +id*id > id vid *id 5. What is error handling? Describe the Panic Mode and Phrase level error recovery technique with example. [WBUT 2041, 2018) Answer: Programs submitted to a compiler ‘often have errors of various kinds. When a compiler detects an error, i.e. when the symbols in a sentence do not match the compiler's current position in the syntax diagram, the error handler is invoked. The error handler warns the Programmer by issuing an appropriate message and then attempts to recover from it so that it can detect more errors, . The simplest form of error recovery technique is “panic made”, A small set of ‘safe symbols* are used 10 delimit ‘clean points’ in the input. When an error occurs, a panic mode recovery algorithm’ deletes input tokens until it finds a safe symbol, then backs the CMD-34 tps://[Link].aFanjan_mahato_rkm/ [Link] ) SOMEULER DESIGN «out to. a contest in which that symbol might appear. In the Pascal code: ifa ee xelse y; ne ‘ompiler discovets the error at b and a panic-mode rec ori - ri Como the semicolon, thereby missing the the, ee aes ey ta ae again produces a spurious error message, . finds the else, it in phrase-level error recovery, the quality of recovery is improved by employing different ref safe symbols in different contexts. When compiler Aiseovsed ae Gear an expression, it deletes input tokens until it reaches something that is likely to follow an expression. This more local recovery is better than always backing out to the end of the current statement because it gives the compiler the opportunity to examine the parts of the statement that follow the erroneous expression. In our above example, a phrase level recovery Would use the then and else tokens as the next safe symbols and give a more realistic error message. 2 ae fovvowing fragment of * , Consider the following grammar G. Alternate the production so that it may free from backtracking. Statement -> if Expression then Statement else Statement Statement — if [Link] Statement ' ~ [WBUT 2012] Answer: : Statement — if Expression then Statement Trailer : Trailer — else Statement . Trailer > € 7. Explain left factoring with suitable example. [WBUT 2013, 2014] Answer: Refer to Question S(a) of Long Answer Type Questions: = 8. Consider the context-free grammar: [WBUT 2017] S+ss+|ss4e a) How the string aa+ a* can be generated by this grammar? b) Construct a parse tree for this string. Answer: : Similar to Question No. 2(a) of Short Answer Type questions. 9. Eliminate the left-recursion for the following grammar: . [WBUT 2017] S3(L)la L->LS|S ae ¢ https -/[Link]#BFanjan_mahato_rkm/ /[Link]/ranjan_mahato_rkm/ ~ POPULAR PUBLICATIONS ‘ Answer: S>(L)la L>LS|S) ap | Lefi recursion elimination d 7 4>dalp A> BA | (form of left recursion) A E\aA = After left recursion elimination + S3(L)la LSI’ (Ans) LS SL'\e LoS. Lose Long Answer Ty} estions 1. Construct a predictive parsing table for the grammar: [WBUT 2010) SiEtss'|a S'seS|ec Eb Here S is star symbol and S' are non-terminals and i, t, a, e, b are terminals. Explain the steps in brief. Answer: From rules S > iEtSS'|a., we get FIRST(S)= {i,q}. From rules S"— eS:|£, we-get FIRST(S') ={e,2} . From rule Eb, we get FIRST(E) = {b} . Using the FIRST sets and the rules, we get: FOLLOW(S)={$}U FIRST(S’)= {e,$} . FOLLOW(S')= {e,8}. FOLLOW (E)={t}. Suppose the predictive parsing table is the 2-dimensional array P[4,a], where A isa non-terminal and @ is a terminal. Since i ¢ FIRST(S), P[S,i] = $ — iEISS'. é Since a¢ FIRST(S), P{S,a]=S—>a. Since ¢€ FIRST(S'), P[S',e]=5'— eS. Also, since ee FIRST(S’), P[S'e]=5'F because e€ FOLLOW(S'). Hence, we have multiple entries for M[S'.e]. Since $¢ FOLLOW(S') and obviously ¢ € FIRST(e), we have P{S',$]=S' >. Since be FIRST(E), P[E,bl=E +b. CMD-36 httbs:/www. nstagri#iroxeehPFanjan_mahato_rkm/ ~ ey [Link] COMPILER DESIGN No otherrule is lefi to be scanned. So the predictive parsing table is: , [Now x Input Symbol terminal 1 t e ae b T Ss S— iE1SS" Sasa s SS cae S'me E Eb 2.2) Define LL(1) grammar. Consider the following grammar: [WBUT 2012] S— AaAb | BbBa Ave Boe Yest whether the grammar is LL(1) or not and construct a predictive parsing table fort Answer: 3 FIRST (A)= {2} , FIRST (B)={¢} FIRST (S)= {a, b} FOLLOW (A)={a, b}. FOLLOW (B)= {a,b}, FOLLOW (S)={5} The predictive parsing table is: i a b $ s S— AaAb | S—> BbBa A Ave A>+E B Boe Boe a Since there are no conflicts, the grammar is LL(1) b) Consider the following Context Free Grammar (CFG) G and reduce the grammar by removing all unit productions. Show each step of removal [WBUT 2012} SAB Asa Boc|b C+D DE E-~a Answer: State: S$ AB Asa BoC|b C+D DoE CMD-37 . |https :/Iwww.instagrfroxeRFanjan_mahato_rkm/

You might also like