Scribd
Upload
26 views

Compiler Design Assignment 1

Uploaded by

Saurabh Verma
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
26 views

Compiler Design Assignment 1

Uploaded by

Saurabh Verma
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
You are on page 1/ 13
Nome > Garotadty Naina Ryeantr & “Trfessnolefin “Technde a: Rell No +b ~ Q0643370) 20053, Sobfesk ¢- Oanaet 2 Puig —- AAsstenimen7 ob L ft. Define the following Uy_ Pre; Bee pl processor and Assembles . 5 A preprocessor. generally considwied ' 0 a’ pode 16f compilen 5 iS a tool the | preduces inpuk tor Compiles. Ib deals toith Mocro- processing augmulation stile fuclusiou.s ; language iextensie An assembles transkt: assembly language program into madre tece -The output gf an assembles: FR called an obpcttille, Which contains a combination ef machine ,, tstruchion a8 voll as He data vtequirec| -to place these Fnstruchions in Mmermory (ti) Types of Compiles : ya © Single —pass compiles: GIn this complies jtohen a line Source fs precesses| fs Scanned and the tokens asie extracted. ' ; G Then He syntax of te ling IS enalyred and “tree Altucluse gome tables, containing infor matte Jabout eaclt token. are bulb. ; { ® Matt ~ pass Comp less “ST Stan Hu inpul source once and produces Hrst modifred v term Aomiliosily again andl again, Vili» Loodess ond Linke ‘ a loades ‘fs a pank of og ‘and fs sespansible,, bor | executable files : oodirg into memory ancl execute them Linkeer Ps a computeet rogram that links and mye ee ebyect files together in order +o make an executable le, ® Grouping _ ¢| Phases into passes Grouping o] pases is divided in too Passes, o Gres Pass @®_Tho - sg Lextea] Analisis Lexfcal Rralyzis Syntax Pralyeis |. Frontend Syntax Analysis SIS { Semantic Aralysig Passes Thteinadiak Code aaa Cade [Bede Gensation | © Lex and ynce Tools i ana lexe This tool fs a Atancased comPponenk gf most UNE OS . The GRU kk Lexical anelyzess LLEK) ts genesiactad voit the help ol regular ee pression, Yace? - (Yer Anotus Compiles — ~Compilet) fs the Alandasid passes Qenesatow for Hue UNDS Ofesiating Syste , LAW oper Aource Progrou ,YACK genesiater, cede for the lava fn © Pregromming language. @) BNF and CNE i @. Backus-Naur form fs a nolation — technique for CF. Expl.) Exp2-] Expo ++ 2 CNE = Chomasky Nowmol Fom fs a grammas i¢ all produchow ane the form — ) a's ® Whot is language Processing System? Bxplatn phases iin delar', Lyn a language processing Ayton a The rock Fiend source, progran Jem Hee fangeh axenbly prearam aagemblen +0 creat pra impuk fhe the seurce code is first preprocessecl is processed by the cempilen +O which fs then franslatel by Wu he denget program - Tt Is basecl OM Jronslator tokes ancl the Gubpak Tt produces sand a { e Jronsiatos ca" be defined oS CS gj wu fellovals high bee [Reapecsio= Frc CES Post i a macelsnc Cocky, Preprocessoy_ 3 ~ A preproc esso™ + generally considiecdl OS & compiler 3S reol thet procluces postr 3 tnpuk lor compiler Tnteipretet 3 - An. intesipretor slike @ compiles hiql lwel language into low - level, machine translates fanguaqe+ Assembluiy - An assembles tronslobis assembly languaae Programs ilo madaiur Cock. Linkest 2 - Linkess Ts a Computes: program That Unks ancl nuge Vasiious obgeck files — -togeltuss in ors to make an@) executable He. Loadtnt - Leaciey Ts a part | OS and is wiesponsible. bor leading execcitable Mles into mumory and exeutte {hem . Ous Whe are the ditterent phases of the compiles 2 Explain | phases in detail . Write doon the Phases in detall. Write. down “the outpur @} each phase for the expression = Ubte y* (btc)4a A compiles contains 6 phases which ovte follow , - 1. Phase 1 Clerical _firalyzest) Lexical Pralyzer phase take Source program as an input cud Aepeviates chanactesis eG) Aourco language) inte groups tring calltel token, 2. Phase 2 (Syntox Analyzes ) The syntax qnalyzess greups tokens Mig Abrucluses Cporse Tree) Apastpel Wis siping 3. Phase 3 (Somonttc Rralycen) Checks the source program fer Semantic ensiosis and gatlwis. type Informaton for Subsequent cede gen~ esakion — PRase- A. ek CIntuinediak Code genvration © Takes input (Surtax tree) for — Remanti has and generabs Trtesnudiatr Code. “press 5. Phage 5 (bode OpHmization ) Destqneol +o improve ty _ intesimediate code go Hhod- ul Hmerbe. obsect Program owns taster aural Jakes less space. G. Phase 6 Cole _generiatton) SY @ generates Ho cissembly, codes G8 ange} language. code is trarslatts| @ We address in the bineeyy from logital address r Linput brecessing ‘In Compile Oubpak a a=a(btc) & (bic) + 2 — NE Wy =Cido+ ids) * Uda tidste [Taken Stream a Paso. 4 ey ; i N\, f es \S Firskty lee teal analyzes: creates @ program lex-1 in theLex Language - Then Lex compiler oiun the lexd program anel preduces a CG program lex.yyee \S Finally C compiles oruns the lex gyre program ancl produces ON Object program a-oub & ‘ + > aout Ys lexical Analyzer that doanstams an input stream to a Sequence. oc} tokens. Lex Source, Program tex 7 [Lec Gonpitesr] leryyc Vex -yy.c, —> ——> aout fnput Steam —>[ aout] YACC 2 - > Sequence. o} -fokens * Yacc stands for Yet Anothesy Compiles Compiles. * Yace provides a tool to produce a passes bor a Qlven — Qrammas - ~ Yace” Specitication Y ace R translate J > | dompiten foes Ytab-c — > —> aout Trpuk = © Convent Ambiggus, Girammas, +o Dnombigour Grrowmiman . Exe E— Ete) ete E— Id Kia Convert from NFA -to BFA uring Thompson's oul e fo~ larb)* abb a b oO) o2o-® NFA for (atb)tabb 2 E-dlosure (op 72 15254,13 ——letA e7 move (Aa) = 83,84 e-closure. (move (A,a)) = 21,2 ,3,4,6,1,83 ——lebB * Move CA jb) = YS% E-closune (Moe (A,b)) = &1,2,4,5,6,14 —let Cc « Move (8.4) =83,83 €-closune (Move (8, a)) =01,2,3,4,6,7,94 ——LetB * Move (6,b).= 25,94 Eclosune (move (8,b)) = €1.24,S56,1,9§ ——leb D * Move €C,4) = 23,83 E-Closunc Cmove Cot} = T1234 ,6,7,84 —lel B ® Moele,bl- ist, €-closure Cmovet¢,b)) = L 1,2,4,8,6,74 —c 2 Move(P 1a) =t3,84 €- clasune (Move (Da) =E1,2,304,6,7,84 —8 eMovel(D rb) = LS, 1% E-closune (Move (D1b)) 224 eMovel€,a) = $3,384 €-Cosere Cmove LE G)1=814,2,3,4,6,% 84 —¥8 (2,4, 86,7; 104 —E oMovelE.b) sUsh E-vlosune LMove (Eb) = L122,4,8,6,18 eS EQN usta GC + > eode tn PDP-\) | for bext formaltey Qed Creat a Cross compiles for tompiler , voritten fn PDP-3L, producing and a EQN language producing ode. TROFF written in ce — EQN TROFF wo Qu Solutions ¢ Em EsTlIT TOPelF F—> fd i e E @_ td+ Id tid =) we J% T 2 A\- “AN Tr hos 2 opesctor on ef thers E+E Bae Bide git. , | io | Wuielr operator should I! ia id id id iq Avociate this with ? \S Tp we wee associat Lolth leit operates —> [lee a%80- ® fa+ tartd YE Ldatiaa) Fuaiorio Uasta)etd f & eee \S Pex [ahh _axtcclalivily } Ee 4 E \ VAN is \, \ | 4 id oe td +Utd +f > + O-— lett associative So ISt panse Wee Corre Kg Precedence deosnth fake cane e 2. tp we taken core o} Prececdlance then — grammasi Now , Hote +e do that ? & © asscdakvity AG can be unaubigeuns. Qu Why are we getlns oth asrocialy sHea - Wune ? bIcG we one defini Aho Gromman vol houk any ordi, a for fd +d rid € E JIN J\\ E +e 1 AN /\ \ | él £ ett \4 i | | | ia id wi Lidatdd tid éd +tideid) leH- aecalve Right arsociative When we Say Six Ap we con grow fh any direckon® To achieve Left associativity , we have to gro tn Lett DirecHow only. So we will otestrict the growth oJ parsee tree . Note we aie grotoing only in lett dlirection » BG grammoss fs dedinesl as Left Recwnsive. S for For _brecenclance problem we eat Jake | cone Hot highest precedance opescter Should be ak Me least level. So, we will fntreduce seveial AIF aymbelS like 76-7 eo From Hus hws Nave. reached T, we cannot pos Tele qenerckt OW F. rot Noo fd std *fd /t\ So, we aie taking ettrT Corre. o precerlence 1 7IN by detining AIF Gu \ lwels. | ' dd ia td G Converting Re +o DirecHy +o DFA's > First we oun The given wtegulas: expression by wncate - haking tr with & Aptcial Aymbol ts ClAlete — augnunted srequlor expression éxe (a |b)* abb 4 Aug rented Requlass Expression 4 Calby ~bt Steps Ve & Converting a Ayntax tree for (a) > Travesise. the tree to construct function nlngplentestes. lastpos and follow pos. \& Computing — Followpos Ls tonveiting a RE Directly +o a DFA. nePules, Fox Computing tre Eunchou Node n nullable tn) Hrstpos th) laskpos(n) Rice | ee b b led by © A leak with ae LB Sis position i . vullable Ca) Hestpos( ww loxtres ca) i he yutlabletG,) — Hrstpesteo) lastpes C2) < nullable qECnullableced) TF Cnutlabl Ca) ond first post) & lost pes(cd 0" cy c= wullable (2) Hirst pesca) laskpos(@) » Sn else. Hrskpstery else laatpos( 2) ec, ue. HrstposCc) taskpos CG J ————— Slax Bee 9 \ ot Lab) 9. a-beb He mullable * Finding Fixstpos and Lastpos bee te} atl nods for Syntax the! Tree was fdas \ uy atin b \ Final Syntexx 4 | Pay 423 Ree Kirst past pos pos % For Finding tdloco pos enly Atan(*) and concad. (Le) pods will consicuerad|, =a Sharn-nede) TF O(n 1s +2 a for Ceach fin last pos ny) tollowoposCid = follotopos ci) O fiestpostn)y for « > fk(nee Cy-C2C concatenation ~nek)) for Ceach f in lastpos Ccr)) Follow posti? = follow pos li) U Fixst pos Cea) 5 % Cowotting RE to DEA fo Te ED | A Nambytec Firedt Stabe

You might also like