wploalansa UMiT=4 D Lrboducion Shuclare of Compiler Dp Lranslatey 5. D Iranslalers ¢ ° to low conver + high level language program level language programe Cov) machine code: | | The different translaters are 2 0%) Compi lev : et) Interpreter | © Cornpfler s- | Compiler takes complete Progvam ata tere ard converts ‘into machine code: () Dalerpreter;- Dnterpreter Ys also a translator which takes Vine by Ife ond converts into machine code-lt = Skuclue of Compiler (or) Rhases ofa Conpt ley Source Code J ficial lee \ TIntemrediate cede] \V evvow genterator ae | “Taxget code (etachine code) Dhesfeat traliger,- w DE takes an Instruction and divides # ° Ito ao small untts known as lexemes.tortokens. 1 Given Tehruction C—> Tdentifier / ce at => assignment Operator A~> Identifier 3 + > Addition operator b> TdentifieyHD Sygtan Aoalyrey & Syntax analyrer te also known as evcer, Dy aakes the nctruction and converts nto syntax tree cor) provse bree: tAlTh tne help of “his syntat tree e707 ean be Identified Ex Giver Insbuction ¢=atb “The syntax vee tor the given staternent 's OD Semantic salyeer?- Pe scans the syntae tree and checks: cheney wales of meang semantfe analyzer language fs followed oy not That checks che errors im the syntax tees. Tt also verifies “ig, st *ypes uf Sdentifiers. Semantic Record nfo > Ne mm S | Float sum toot oe ant 1° ws) [ctor bb | tint) cehas) “theve 43 an er eve $s an evroy fn -the syntor Avee, because chosacte Snteqer Cannnt he odded.es Gu Dntermediate Code generator 3- TH+ generates the code w variables: : ; V6los}ao%a. u sing Lempovary a tempt = 4 temp 2 = b&temp 4 temp = Ut temp 2 c=temp3 Petermediate code generator uses tempermy - () Code optimizer;— Code optimizer tries to veluce temporary variables andl number of [?nes $n the Intermediate code- B doing othe execution performance can be- *neveased-and memory will ts also be saved: Gr a4 c=athe _ da “the aboie intermediate code can be optimized as follows? | by tempi =b% 4 temp2 =ar temp 4d az temp 2 Here Only 2 temporarty variables ane used onlay, altnes al ABe there in jhe proqgyam- — Se eeWw) Code generator :- Code qenevater takes the qfven assembly code Coy) Preumonic Sretruction & converts Into Salo code: ThAttey Anat; assembly code ‘s ¢ known as onvevted : 8 code « machine. This machine code % “Target 0 Assembly code (Preurronic code) Mathine co? Mo Rib ul 4 toto Wino Mov Ro, % oo10l To. Add Ra sRy Wott sTR CR \aloalaoag Compiler Fee aciknce of Building 2 A\ compiler must accept any length of source code toch ts Weg stall oY lange and transformation should be performed without changing the meaning of the program. Modeling In Comer design ond Tenplementalion 5 |? Design > The compilers ane design koued on, mathematical models like finite Stote mrathines ond Requlan eXpYEsion: > These'mathermatical madelss.are cused 46) Mdentify3) Context ree quanto Tre context yee grammar which is used to describe Syntadtical ervovs in given exprersions W) Scterve of Trees Reh Te % compiler he science of are which Is wed fm compiley used fo detect ervers in given exprewion Science of code optimization, ) oO ptimixation The word opttimmcation amnenns Inreasing sthe efficiency ond performance « QD Tries to veduce unwanted cade The science of code eptimfeation ties to veduce unwanted cade fr given program ¢ Improves expression speed —> Data abstraction ¢fohenitance concepts can be use to, optimize the code fr a program. . f | aaloz)oor2 y 5 “Tregiarirniag Language Castes: (evolution of compters , : : _. History of Computers) | “The history of pregrammingy languages gto -frore mechanital’ computers to eedern fools fey software development. , ‘ is done using pnaamonics acdes. ke add, sub emul efe., Q wn only, 1950's, assembly Vanquage Se used. Here programminySh later half of 1950's , development of feritin Fs done | for wrrting engineering castienifie applicatton y and Cobal was developed for wrrting business oslentecl prepreg Afte volt [7 ¥ 1950's, many move languages were creeted wrth Tonovative features which helps easy po" natural qmnoxe yobbst- ari Og , roe Clertfation of Larquaqa by qenenalion! Ts fixst generation, machine lanquage 4s used fox eorting Program, an a4 Xi te used for writi generation ,assemboly lar ets Use y ng prapen: 4 longyeg Th a generation, high level languages Uke fortvan, cokal, ¢, C+ were developed for urvHting preqyamant Ts uw queraton ; languages dasign for specific applications We AOMAT , foxpro Sql: All these languages ane used to Store dotate database. Dy 5” ginerertion, logical constrained based languages We proleq and ops 5 (official Reduction System Version 3). were developed which were urecl In expert stystem:Wet Oriented Langue yes Object Oriented Languages support object oriented Programming “This pregyamming eonsicts of objecls whe tommunicate. with each eltineg Abrroughs mensege Ping technique Satetng Languoge, - Swipting languages are developed for wrrling web applicaHons . q Sark eva script pest, phe, yuby, TUL.vertical Analysis. [the Role of Levicat Aroliz.er Read charactors oo Tokens Vrput y Lexical a Syntax | Analyzer =| pater | Push Back ae Lo to Exba Tokens “Tokens Tt 4s hexical analysis Is the -fiyst phase of the compiler algo known as Scanner. Tt veats characters from the lenpuk staterent and borne a meanidfel tokens (ord vexemes and hese tokens ave given 40 Syntax analyrey tunelion of Lexical Aralyrer 1) Divide aire proqiam feito valid tokens: M1) Remove white space choacters: Sit) Remove comments. WW) Tt also provides help fn generating exror messages’ by providing row number and column nunbey- bat ® Suppose we pass & ‘statement d=b+e ,it token sequence as. giuen below: + identifier = -vassignment operator bp -7 Idemtifier 4-7 add operator co identifier will generateThe above data te given to syntax, amalyrer exo f Weve ave printf ("ots ), | PrinlP <> keyword SD dre & © ~s@pen brackel), operator CAST —olmessaqed, Pdentifiey mi ek D — ~Slelose braked), operator 5 —pleem? colon), separator Quloglacra Doput Belfering : vt Generally, lexical analyzer yeads chavacey & 3 Character of the Gen program & produtes stream of tokens- . . Ou Te wead characters & produce token ytwo punters ase vequived they ane j (8) bexim begin pointer f Git) Forword pointer . Generally, bbp fs. placed at stating polot of ane teksen while yeading the characters: FP weads chavactey by character until Ht sees ahite Ek. Peis considered wy as end of +token- End OF File Space 0¥ comma, ov gerrt colon ovHere axe too schemes of ‘input buffering. U) One butfer Scheme Ui) Two buffer Scheme GD One buffer Scheme Sint maine > int —Token 1 » main — Token 2 { — “Token 3 3 — Token 7 agit UID e-betfer Shene [eas], navite | fe fea | Trpct |r oFPy= if je jas jeer . (i) Rec Cute Ge int - Token 4 ® ; folle 1 — Token 2 T= “Token 3 m4 P= Token y a? = - Tokens b {5 “Token 6 Alo + = Token + mn A = Token g By uging soo - buffer g¢heme system pevformance Sneveases compared with one buffer scheme- | The asloslaoaa Recogateation of Tokens “Tokens ave vecognized with the help of transition diegpams, Aloal: 2 There ave 5 types Foe Ch) Recvgrization of Tdentifiey 3 Git) Recogntzation of Delimiter . wi) Recogntzation of Relational Dperaloy. tv) Recogn xation of keywords W Recogrization of numbers:‘zation of “Identifier j- Generally 40 C lanquage theve axe some qules to be followed for Sdentifiers+ | with fetter: Lladacfelernent 244 ty Ddentifier should stort mext ahecvachew k Gd Atter first character, be charatley Covdnumbey- low, the production sule for vee ognixing for the identifier ©, fs * letter ( Lett number) gutter le ts “Re tansiton diagvam tov abovenvt letter/number ofa oO Initial state WD Resegrter of of De-tiniter Blank Space (1h) tab space (\t), new bine character (\nd axe Known as De-limtter- These detimiter creates white space- | The lucki production tule for secogricalion of De-Wertler ts ster (dt yr The hand's 1 bansition diagrarn fo de-limtters feCT) Recmpizalion of Reliom! Opersiors ! The! YelcHonal opevators one oy FAP SSE FS s The transition diagram tor >) 7 =) 18 f = }) b f ) aoey 9-4 > wR A La es ‘Gita! | Pro | The The aaeslavo iets eee Uv) Recogetzatton of Keuvoords 5 and) Keyoords ave also known as pre-defined words + Some of they Kewoords ave Hf else, for. def “Ke tranition dltagram or above keywords 38 oe te7 , ) Recegte atin of numbers Qhamber ts defined at a drgit ov ene of di EX- 6,29 Paoduttion nite. of mimbers nunber = agit faigy* The fansifion diagram -for swmbes % aiat Qabit tet yey “The hevica) Analyser Generator hex: dso ler gun Veadevties eG and Macros mater | defination | Mat, | maint | ‘ion | — { YY HOSFlew yy, 4 otl lewyie —s qe F Co- comgilen) | out Leper teve after woth ‘the Tex program if should be saved wHh aL ovtensiod Sep oa : - Lex Poyam should be ven to lex compilen- TY genomes ac program known as Dox-¥y.¢ GP e32 Aloe the ¢ ogra (Lex-yy.c’) ghould be given bo Cternpiley, low, she C- compiler grote on By wrecuting avout file we get output : Commands > Fler Lins t, L ' Sq Dewy e > Lo -out } “TRS heww ae can tun lex Program wth Prax. Bide Adora, : Finite Aulomota fs used -to vec nize set of patterns. Fite automata has 5 elemenk or Staples. Tt has set of slads and voles.otlotelaoa a. Fintle Atlomata consists of tne -follownng elements FA -$0,,4,9,F 85 G > Finite cet of states. 4, —> sek of input symbole 4, —> Tritial sate fF —sset of final states. £ —s Transition func tion. Sate ° ° Yo BR on OR ° ‘The transition table for above diagram 7s Jd huge ee Present | Input | Inpat | state | co) | cy pvr ae | om | | Yo | % } % | | | | | if { + w | MaMa) Ge is —_ vy pe q | odCy edicliue faxsing (LLC) panser oi Tet TL compares the ‘slotement with the ghee grammer tells whether the given statement ts correct ox not. LL) | no Tt dake: ont Left torfght Left Horoost che fava wud deniva ton Pet Symbol Data shracure wed % LLCO paren anes DToput butler / * Ransiing table _ Wi) Stack “fu UTnput puters LUC1) parser stoves the given statement fo foput buffer: 1D Ravsing able 2 “14 converts given qramman ‘ols parsing table. Shack + Gleth the help of parsing table g stack concept LU 4 parsen telle eshethen “the g?ven statements i fs correct wr nots Teslave eet oe 7 pick C2 obe b yt : é sre Evargle | ven gravee fe “inst rT) ataoterr) ETE tach (toh Ea TELE vey os 7 183 Tr fic} 4) Top ee TIE Be7 Bt} EZ ala lceD,| itd, Bes Pxeetp Ov > “Te convért a gramran solo pausing table we have fo | find out irstColonTermsteal’) ard JetlocoCalon-Teominels) | geFist (Ce) Past (Q=T Fivst (T= F Fist (F>= fia | Rast Ce") jig ied Fist UT) Fast(T) =F Fastl> ={i4,C} Post) Fixst Cr) = fae} First (ED Fst F)=f34,c} e os? : fateste') “fallow (ED — > one -bilow value of starting son terminal is $ — Fist we have do check the Nho- terminal ‘gn RNS fF id \ced Follow (E ) - Fist (0) 7 ) Follow( €') E' lies in 2 statements gn RHS Pere’ D elag tte \e case is Follow ( 6) =Fottow(E) ={$s23 m4 Cose Mi j- Follow (E') =Fatto we) = $4, of Brewer) DOT Mes tn astabemends gn RS yvEsTe Des tte'le i Case gap %e ‘ Fetowte y= boule 24433 Caseui (CO Foltow(T)= Fist(€) ee quired a low substit ES Fottow (or) Final ance: © Geto ES Follow (1 dsbostit we qe Follow — 1. fina) Follow vt lie OT ratalt)=roteat E859} n0> al 27 tio balAtow substitute € fn Eb of given slalement Est Fottay (‘T= Follow (€) 7 { $) a Final answwey Fm case a is §4,$ rt e's 4 tele Fellow(r) = Fivst CE") = {te} Gubstitule € ta & of givin statement: we qet Bott Followlr)> Follow le > = 48,0} final Arswa =$+4,$)>4 Foltow Cr!) Ti lia In rstalemen’ gm RUS OT Ft' 7 > were Coyetid. Follow (TD \= Fo\low(T) 443,94; Case Ui)» Foltowl T") = ae (1) 4,4} Fival answer is £4, 4, a F lies in 2 stalements in RNS Orser 2) yyarrle fellow (FE) = fist (T? = fae} Alow substitute € 89 “Tn given statement TF Follow F) = fellow (1) = {54>} Final answer's $8,458, 9f follow (F) = Fest(T') = feet Aloo substitue € % To gen statement To4F Follow| EF) = Folloro( T') = fbn} 1 a Tate See— ——t —— Final answer in cased (x43 nwo “Constnuction of Predictive Pagsing stable 4 * ( ) ‘id $ E ete Erte! ES ely ate ge Eee T ort TFT Tortse xe ri é r-9¢ F Force) poid Rules: HF the praduction wute is in A- jot Aen find Prstte>. te gt -termimnl statues the coor of as ANSWweEYS: Bo he table at -tenetnal ceils it the sale Noe Rater 9. DF re production vule is A} Shen find faltow (A), we get term athe form of Ave. mal values answer: Th the table ak terminal cals ,filt the wule APE: Jeste Firstlrd= {id Ch, Fil cere at 4 C19 Arable E> a Tele yarek (yA Fivst 4) =fag Gf EETE ak + in tableEye Fotlow(t' = {4} oth Eloe at $ and al) tn table, Der Fast Heft, c} Gy ty THrETi at WG at C fo Aable Wrigney Wr oxFrle roar Fist R= 283 So fil Tye Fri at + To table Toe Follow( T') =f, $ 4 Sa fil ty © at 44442. tn, table: SF id \CED Frid Fast Gad id} So, fil! Paid ed, td iin jable F(E) Find () = (c ) Sorfill Fle) Bt C In table — ——t “soraple weid #'%d- Stork [Deikiatny stare $ rym) te | ager | girs $E'34 {| sey get rk i$e'v re belt's | fer? | gee $e - gate BET | } } tot $e'T'e‘xample we=id xid +i Stack pest Syebol Production rule orn table | (Poitialty stack contain rataridd | $ symbol) § | a | $€ ltde fdeid $ | e-»TE! oe Reverse __t times eT fdatdtid | er! beer tap tert | rof gelt'r Gdxideidd Foid ges de tdaid $ be A tdtidh | flee FT! \ get ex iavidg | | | } dette Maid € 1 RLS id | | | | belr'sd | avid | | felt pid g te ge'¢ +iag$ | | | $e- tid gi | Elssere! | [oe Red | Ww — bet HY xd $ bey ona $ TFT! | Sele ‘d$ F-yid' TOE avlou|»0>> From ® lor Expressions to Automata 4 : bab > bath, balb, ba®b, barb, — bb, bab, baab, baadhbaaaab-—- =~ Aer expanding regular cxpremion 4s drown above The Ante Automala for above regulary erprersion ig Witid e Real glale LO Dlade Mier expanding vegplas exprension “ry a follows We qjven expression tor also oe enritten as (a ov -bye The tne He ‘Aulorate for -the above vegilar etpres GPO sion fsbt = a AC "gale fg Werical Honlyze" Generale (leprae) f om 3} Lea Compiley Seine fst L a a] targa’ 3s compiler} —— sacout Inptt system __ ot Sequente °F a a eer Step Generally, lex program ie cave with eulensien iwen to leM $49 The lew prpar ahould be 4 proyram to Cpregree compiler: Lex Compiler envers Lee pith te fa the deern dA tewegyee Stop er, 7 Tr this phose C program is gwen ao C coropilex which 5 converted Santo 7 executable file g.olpals Step od:- 1 . . Ty his phase on enpul sheeans (C=orb)'s geen “oon exeatarle tile o- out Hee arout erates 0 beq,rerne of tokens atealtergiven fnpat Shear: Sorte apolpt & eHpid fanfii eta — bpereclov aati + ~operater 44! lb —td Astoy|soo Mi OpHization of DEA based paltero aaldhess ted 4s Maal Hep ols- . Set fg = f4 | : fron above set | dates Final state i Interrediate | | jy Be | Conpresing, sthe above finite automata % also known as Find od the Optimicodt 1. Ptimization of finite automata. : tat. cp State by apply! “Transition table for. tne above DFA is. Stote ° 1 290 PVG ot ae {a} fe0t Thy we qt pte ath Baye faa5 fet Ve “erOy Ve Vo qt tepols- Set & 6 = {40,411 92193, 94 5) Ve a} fon above scl of 6 seperote final states ond Skates: : enter mediate Final state is feo} Fntermediate states are Senda tes Veith ors Find out the Stermediate states whith axe veaching firal State by applying any type of Snput and sepanacte. them » Mea} feo tuts, du, t6 be} bo werd wy 4 2 0 0 4 Ths we qt tna} 10%, 96h £904,45, 45)Step 03 + set of intermediade Free the above “mpd states separate the shale Hit ane Weaching final slates toy applying some tnput fast 140% Th fa % 4, Thus we get fos} feoay 4} {4a} faz %5$ Step ou $- Let us take set fay %y 4,4 04 subdivide tt by ¥n one step. considering reaching the final stale Fa one S\ep ot we 1 4%, —>% ° So-fom “Ine AP Hfevent« (So, the Snter 1s far} fret “The transition T° Stotes a —7 leery} { {ota} c {3 as} ain} p fas Optimized DFF vet ws state >A 8 & ee D —yeEEeSoi-from the above diagvom Yo Vy attfevent: So, the Snier mediate cocles we 4 fas} {roa} feat irra} fos %) e bet of ct ane The transition table -fov the abov fs: Stotes 7 & 4. rivety} fora] lagis§ ots} tech ts) inst} t Ww} $4, 4 Kin} fata} fan} See vue} rm faeh Optimized DEA transition table vel ws State 6 i >A a C g® Oo EB a E D RE A E DB D KK totermnediat ane siilan and Ve % 6 codesClow tet us draw the optimized transition ctiag tan ae sowlaor3 Tabs %3, de &3\ou203> Uait2 Tot A Syotet Analyst. Ch Tatraduction K Oyntar analysis 95 the second phase of the compiley design - Tt checks syntactical shiucture of giver fp We, Tt checks whether quer Roput %s correct ov not: KX Syntax analysts generates a syntax. yee oF parse tee to find the gue Spat fs correct pr mot: i The syntort Ss generated fromm the gen grammer Exe- Given qrenenar S—>CAd Ab cla Given Tmput skiing &s Cad Check whether Dnput string Pe correct ov not for given qramman- S>CAd oc A C > -As per the obtained syntax tree the given | mad ching with dhe leat mode: So, backtvackog and eubetitute Aa oh Cad * Goput> Sothe given foput ke syntactically Valo ror Contert-free Grammar ena eee A Contert-free grammar 78 0. formal Th the above tree the output Is rrectehing Ftomplee rook a's sith the qren covsect Input: eae, Lach, “is used to generate all the possible patterns, of stangs. Th fs defined as a b tuples. G=CwT, P,s) ughhené Vt set of non- terminal symbols T te cet of terminal ayreools. ' P % set of pu = Naat” ee G is gxaininan, which consists of set of procuction vules eduction vules which axe used to repoee, Gob @ 45 starting syrrbol used “to derive ‘the sting.Examples. Constyuct CFG for “the language Favlag any moo a's over the set S-{a}. Se peat production rules tor above RE is Sas —> rule S54 € ules The sebies of a® is By AA, AAALAAAA /AAAAA Sox above Qremnar® Let us devive aaaaa 4s cosvect 8S —>stort symbol as—> tule aas —> wulet aaas —> rule 4 aaaas —>vule 4 aaaaas—? tule 4 aqaaaé ruler . aaaaa %s correct. TRe string aaaaa %s correct for above given qranmanTB da Ps Ro dewn parsing ar Bens, -» Top-down parsing technique parse “ is rsh Botton ° % ead for [2 ‘uaa 721m top to bottorm: Here he Input % wead Lorry loly | Pay vieht 4 rove « Here parse tree % generated Prom stating agree 1 let us consider an example where gromman fs given and ba et Youmneed to construct 9 parse tree by using Top—dowsn, and _ Parsing technique to obtain given input sting, ox Given arammar > S-s0ABe Gi i A> Abe|L S i : B-s4 A | Given Spat string ® t i abbede Give Te down Parsing to obtain Prpat shring. f Stayt aad Symbol —_—-* SsBoltors Up. parsing 3 Bottoms Up parsing will slavt ‘from ‘pul sting and ve do he start sybol of tne qromwnar’ TA with follow rightmost derivation In revense ovden. Let us consider an example uwhene qiomnar is given and you need +0 consiruct a parse tree by using Bottom up parsing technique » Given grammar S—aABe A—> Abe|b Bod Given Input sbing abbede SkLolouloo> > 9 Vv d_ntroduution to LR Paving Faasnp| ST % also known as shift Reduce bolom up pring Given ~ 9 Th cee) — L means teft to night scanning Aten) — S- means construction of ight enost devin) A , om Reverse orcley ing 2 | Shep! & mmeang Look a head value 2 PLR parsing % classified toto 4 Hypee- i} t I LR Co) lows |2 ps 2) Simple LR (sia) J 7 ekzea! BD Look-a-head LR (LALRD) & | © Canonteal LR (evr) °C? f vad | DLRO parsing > Cheek -the given grammer is Conte Pee quarmer to) > He nots se > Check ambiguity of she gram” anes | —s Add augument production wrule 40 given grammer’ | —» Convert grammer 'nte canonical LR items Fe Stato ada ow diag ram cor qiven gram oinn —> From DFO construct LR parsing table: Ruler Rale 3:Exarnple (riven qrarnmen SSAA Asaflb StepoleAdI agument production wile to qiver qo X sis > auguument production yale S— AA A-—>oaAl|b Shepor- Convert qrarrrar tote canonica LR iters. SS SAA Aaa +b : aaa Mene + %g used Yo tndicate how much of Input % Scanned+ Skep02%- Draw the dota How diagram for the above canonical qramman: Riles 2- DE 6 4 befre monterminal expand! -the non ~ terminal. Ruler 3 CF SA before terminal) ro need to expand Rule 3: EF + avrives at end kt Snalicates scanning *s completectA ~ersing Table 3- + Rute tt D4 a state is qoing to onotner stote by appling is called as go-to * & parsing table: I a non—tereninal then TE at Ruler % Tf a stale is going to another state by applying “ ermine then tt is called as shift ae >It « -Rale 3 Thao stote t hein Pinod Tern write weduce Laie node completed: tabl >In pro f| states | shit | goto | | Ctemirals) (ron- Fermirals) \ | | | | a bh g DPS A | To |T, Ty | 4 2 a | aiept | | Ib iy Ty | 5 Simple Lg CSUR) Th Ys: Abie kndion as: Simple LR parser: “Ek works on Simplest class of qrammax Te containg fer ro-of states | SiR parser technique Ye (Ala Step o1y- Add augumend production ante to the fro " A—> A —sanguinent production nul A>(A) on Ao 1 s- d Sep 022- Conver! grammar Sato janarnital LA theme . NA | A+ +(A) step 0% wid Ao a Qule 1" Tere «2% 5 PRU scanned 8 used -to Pndfeate how much of Trpud % Step 032 Draw the data Mow diagron coy the. above eit canonical grammar: al expand the Rules Tf « is before mon-termin aoe : non- terminal. State Ruler i- TF 6 is before terminal ro need t0 expand. al “Rube 3:-"TP « avvives ab end TH Tedieatea scanning ts a completed =2) Step 04s Constvuct a passing table Rusing table Rule 4% Tt a state Fs going athen a. non terminal Rule 2 orf a stale B going ; terminal her ut Fs das ontft: Rules 2 Tt a slate &s having Zinal tem write Leliseerotes _ completed: State shift ; || thetion go cov Sa Tc | ) | | To Ty i | rz | 1] | EEE | os = Te bs (ee a Ts |Feduce value at Tz am _§ Fellow( A) - fo, 3} Gle have to place x al Jand $ 248 0+ Con weduce valuc al Ty 2 3 wd Follow (a) - f 4} Ey. we heave to place v, al Dan $- Eg Why ror B «ce Canonical Le (cLr) g- 8 4, “> CLR Ps a powerful passing technique Here 2 ¢ | STH fs also knotwon ag LRU) parsing tedimue- Scared. ; > LRUD= Ly (0) + Look-a-head value s Sos a i “> Here, we place reduce Shem at Lock-a- head terdied, a ‘ fo the paysing table: bet TF } Given grommox non Ep7 6b aber. If k : B—>cBld eee comp Stepol t- Add ougument production wale “le che given grommay « p el ge —pauquenent produutton yale. E—>bB BcB BodStep 02% Convert grammar tno canortcal LR ems Along d with Look-a head values a-heod value | EY>.E,4$ ane E—>-8B,$ B seBycld BS +d, cld ‘4 Here © % used to tndfeale how routh of Trp’ Scanned: Blep od4- Draw the dala tow dtagram for dfagyam “for the above gyarmmay + Rule tt TH te before nme terminal expand he non- terminal . ilano > >: Raters Tt, + & loefre terminal wo need to expand Rule gf + arrives at end ?t Indicates seaming Pe completed7 t 2 é th V ; 1 E3.6.$ 5 t q a | x 7 | i ; Bed ld 5 : I a | H - a I \ I wv bs r Ss = 8 4. ef E ; hae Ablow. $ I 7 ; EP OY Conghaal porsing table: oes Leo Faxsing, table ap Rules s-T?a state f gory another staté by ppliing > @ nOn-tereninal} then wt % called as gets: 4 i tien b>! Ruleas- TF a stale fe going to anciner slate ty avrlying Aeverinal then Ht Pe called as shift: 5) Rules s-TF a state ts having Final Here write vediice nate completed:Mite Shift go-to State | 4 } : a [3 > | Ty 1 | 2 atcept | |t. | ry 5 Ty | Tu g Ry Ry | a | Teo | ty 4 Rs | | Ra Ro | Rr | a Lool-a-head LR CLALR) parsing techefepte (ERO) LR(1)=1R 0) + Look-o-head value + LALR is powerful parsing technique tran olmer parsing techritques- 3 Gihen LALR i componed: with €LR yLALR contains few roof stotes: As q yesutt, execution spect will be increased.a TS Given grorenan Esp, b> cBld 7 Akte Step ov Aci augumentation production tule tothe given vin « grammy, E re Wal Da E->eapR Bscg “e Bad os tule ~ REP 222 Conwert grammar Yate canonical Le eens allow wit) ti look-a-head values - e 7 Ed, Fhe AE : ” 5-88 ~ E> -B8,4 ask B> -cB,eld - Bo deld 3 Se _ Foo to caliulate look-a-head values » ELH Eb De The aloove gule ty ow mart production wilt. « Sorby default look-ahead value ts §, De+-6,4 Cle opt Ssetond ule a3 gen below - ‘dl i e AHer non teratinnl E “6 present, so write production vtget toot a~ head valu. th: second vule as Solteros, After £, we have do fad tivst (non -tevmnined) 4 there 7 me ons ternal took—a- head value 4s $, 5° eS: op Dole get 34 wule trom a™ production sule E> Be, $ Atter « non- terminal B fs present sow rule © vite B producton 6-0 Bod Now we get leok-o- heed value ag fottorcs | | | \ MH second vule oer & qencterainal % prasert , 36 409 jcok-a-hee! value we have to fd frst) Fret (B= eld So eld %& he took -a~ head value in ae rele B—>cB,cld Bed,cld~ 24 oy}032 ~ LALR parsing table fr before merging Tn DEO We fo Ai event nq look a- hea Wey ane D)Iy ond Is DI, ond Tq c | Je |ts |: cy Tm it Tay. \Tae Retore § Mier meg effi dieny 08 aod Th DFO, the following slates have Same wlesshaving differen} looks a~ head values Trey ane '- VY) Tg ond Te = Tay aT, and Ts = Tus DTg and Tq = T gq Clow , me vale 4, LAR pansing [ states | pic | | Te (33 2 above same states, having farne production atHferent produdion su tea alole otter merging rife a | { los com Is | Tg | Ra Refove mer Re Ry | . | pss 4 ‘ ying ctrene ane wo state the parsing ~tabe - After rrenging “there ane only 4 States. goby dota “Hs, efficiency ty PexePormance oP the LALR algexthm all bE cosy:galoni™ ~~ Ambiguous Grammars ~ A grammay fs said 40 be anblquous Wsthere evita. Mat : CW move -tha one lett epost derivation QDmove than one right mast adenivation (himore than one parse tree for the qv shiogs \ f 4z TF a grammar has ambiguity thers FERS wot geet fyc3) = compiter construction, 3 | 1 7 Let us consider & grormman with production wales. / i r E—-E+E a c EEX E % E-> (ED ‘ E>r ar elolile---79 Given string “ 3x 245 \ _ for he given sbing “he above, grammar grecis ] ponse trees on given belowE E J ce Ea E \ ~ Deere . & e)) | : \ Loe | ei xy m+ (2)* @ ‘i Bx U5 3x a5 yen skiing “the above Stree: thee ane & parse trees for § grammer ig sald to be ombiquity i len Constructions - is Grae” Xe not good cbr opi° ) Eyottaived ted Trapelation Qyrtar-Dh Asc Syntax Dheded definahons (500i a es ie les PS knoe SDD= Context free qramenan + Semante sules. é Ex . A ‘ An sOD te a context fee givounmnan togetnen voit, valu i A: volue = Semantic: yules A-value wee da Reduction Ruleg 5, Sermante Rates Th the abou | fer) E— Er cr E-value-p Evalue +T value atritute. Qee ae EoT €. value TF value © onte Bevalue 7 cet wate Thlenited al rl Covert mide Oh —Atbibules ene ke numbers, Stings, reference dalalype \->ée Otte ~~ TP a child wc ” Tgpes of attributess. Siblings nodes Thee ane a types of atvibutes. “They ane ( attributes DSyerthesized attributes &» B- value = 2)Tnhenited attributes. orale ®-value = | Th the above ati bute Bec JAnalue (si ——————Synthesized attributes, A=+3BCD | . ary Hert Wo parent node gels value Rom child aodercan hn ode 1S know os Synthesized attribales d fx» Avvalue = B.walue As value = C value A-valtee = Ovvatue Ih the above example, A-value ig known as gyntoesized jatteibute- Because » A+ value is deh obtainedt From child Me Bevalue, C value, Dvolue, henited ottvibute on Lilacs Papert node childngles 7 Any A—~BCD PTF a child nade apts uatues Fionn parent nodes (ov) it's | Siblings nodes. then that necle is known as “mheri ted! | attributes, & Be value = A-value Bevalue © ¢.valye B-value = D. value A the above example, B-vatue is known a “Arheri tet otiibute. Because Bogle obtained bor FH ponent node Arvalue ®t stittng nodey cs vabire q D: valuesDependen AHotoutes ¢ “YF qraph determine ne evalualigg *y @ panse tree Taf Dependeny qrephs, Consid ey an example Prediction Rile Serrantic Rule ESE yy E.value~ Eve «Tl Case hee or by production wale E Eee ot y 1 yperdenuy gvork ; \ \ cependen } 1 Esato bs Tvalue Gitar giremenas +200 Trp string» 3X5 ow find out the Euluation ovchn of gro Trput shang » given qareman Rane tree for given. Thput shin digit Kp OF Fw SH digit € \ T 945° Uw oy 3 rotated parse yee for given Trout staing -—pe Vedy aoe sor( Syptax Dieled Translation) SOT fs usd for semantic analysis SOT % Redt used to sonstyued the panse thee widh Fo Semante action: Soywe ear say thal ve SOT = Gromman + Semantic Aebiony Ql Exe O. (Es e4T + Evaluet Tvelue) . & 4 Trout > a434y. Co: oudpud iy - Ge to ey Serrantie Ackion iy Stet |r se Eval eq: ‘eal ic tr | 1 Tx FL ao val F T.val al Gi Tall er | * Posty val = Fival val e Fival-¥d 38 ene i Ste pin ZY | AE | an y t 1 4 Torn 3d: D>: l, Dt oO:dase bet B43 ly Ag lication s sor % used foy executing acrithen elie expresions « D+ % used Sy conversion chom Sofix, expression to prefix expression oy past fix expression. DT % alto used for binary to degrral convension. T+ ts used fo creating a syptax trees DI % used to gererate eaterrnediate cocle DTA ® commmronty used for “hype checking.oF loslorg 2 N\ Syntax directeal transla ti lion sehernes | &: plete oe SOTS Grammar Semantic rules Mi, TT 5 used oto evaluate the order of semanti, val SDT fe implemented by constructing a 2 parse i 0 Ayo left to right. 1 performing he atHons Fro 7 5 fe dE Grammpan Semantic 14 leya Actions a fer T fe.val = E* valtT val} i” E>sr evval= tval } & Tae frvals Fal #F oval} 4 TF val = Feval } oA F —snum frval enum lecvalues te e Tis aL Gi ' SO" Given str} 4 2) Tah Itagg aan T. 2 TH a Ne sibling AINe Sohesife a : o ‘\ ar 4 ! — tof JN \ child bff fg =] Bue I. Fy] num | cw OL | Fo | @/ rf} [TY peal | em | | eum - L\O/ \@ : \Tete ee a ee ing S- attribute and Leaitribules ane} There ave a Aypes of atlriloules. They i) Synthesi ved atinlouled 2) Inhenited attribules Xf pavent altvibule depends on D Synthesized attribute :- J parent attribute Fs childyen attributes then that d attribute: pal = Paval 7 nwal = eval Avval = 0-va ive, “th tne chore” exampleriA.% Knew © syonest J ’ 2D ativibutes because A Ye depending °P GB lord Chor known as synthesize 2 erent children Ext A —>8cD wh Values» “This pavent attribute % alio known as Sattvibulé- 2) nhevited attribute '- 7m 3 TPF cy attribute depends on parent attribute or sibling oltyibutes then that attribute % known as Sohenited attribute: | tr As acd child—> panert or sibling Bvdl - Arual eval = gavel p.voll = @.valLeatiibete BMhenited egltvibules then th i kN ASL athit fe & Graveney A>ecD p Crvalu =p val 2 val - B-val Deval ~Arval wArval = B- val Lealtribu tes rome 4 6, attributes. ~ RK dhe above example Qand % statement elongs chatemends will N24 depend iutioat hw sbuihy potbane i a Teh an athitate depends on leet side cgolbietired 109)jor TVatermediate Code (neneralor axjants of Synlox Trees, Theve ave Bypes of Syetow trees. They ane t d 1 ) Directed Acyclic gvaphs (DAG) method a) The value~ Slumber Medtod -for constructing DAG Directed Acyelic qyaph (DAG s- A Divected Acyelic graph fdlentifies the common ao expression In a given expression. A DAG -Hee contains operands %n,-the leaves ard operators fh the Fntevioy nodes of the tree: Here a node can have move than one parent « €12- ara#(b-c) +(b-0) ¥d )& Syston tree Or Ox xa th-Oad a ? + in A a a¥(b-O) (v-O Part -2.3) AN + Ee 7 ‘ay a xe AI a wo b ¢ 9 Awe rahe Ai cm + a A Let Us convert Soto DAG. DAG + D4 % derived fom cypla trees +. aie ( 7 a 7S be lodeee le ee lene mode can have move than ene ponent - The vate mumbey method for constructing DAG 3- “he nodes of 6Y of secord ntac tree (ord Dh value number methed + DAt dee ane stored to a9 array do stove “he data of Here we may use hash talole Synton dyee known as rode value number. Here array Ander fs ope Tee a vN\ 1 10 Nodes of DAG for %=%+10 % allocated %m an array. evrayindex Meaning4- x t | Seneteaeo Mi wo /™ Lee? wath TN Is cco (GO He f= 4 c DAa \s \S le ie \ i.odes of DAt toy mzath—(¢-d) + (Cd) fe alterated nan avvay. arvauyinder Aeaning Vl Ndentify | ¢ Sdeotity | = be Sdentify oa | identify | 5 | ] | — [are Sdentify | a tkes- OL Convert the given expression ‘Into postin. expression 02 + Genenate Syntoe tree using stack | €p 03 - Convert syria ‘ree Fro PAG se (ant) & (ed) + (Celd) # Cate) ale (tape) (ed 2) UCD 4 tabt)) & (abecd x) +11) (ab+)) => (abe cdem ef fab+X + (Postfix expremion) w