Compiler Dsgn&implem CS 5810
Popular in Course
verified elite notetaker
54158, Introduction to Public and Community Health
verified elite notetaker
Popular in ComputerScienence
This 7 page Class Notes was uploaded by Lisette Hodkiewicz on Wednesday September 30, 2015. The Class Notes belongs to CS 5810 at Western Michigan University taught by Staff in Fall. Since its upload, it has received 23 views. For similar materials see /class/216895/cs-5810-western-michigan-university in ComputerScienence at Western Michigan University.
Reviews for Compiler Dsgn&implem
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 09/30/15
BottomUp Parsing Chapter 4 Part III Bottom Up Parsing varm ssmaswr n5 2m 2192008 Topdown vs Bottomup Topdown parsers Start at the root of the parse tree and grow toward leaves Pick a production amp try to match the input Bottomup parsers Start at the leaves and grow toward root As input is consumed encode possibilities in an internal state 11511 manning 2m BottomUp Parsing A more powerful parsing technology LR grammars more expressive than LL Construct rightmost derivation of program Leftrecursive grammars virtuall all programming languages are leftrecursive Easierto express syntax Shiftreduce parsers Parsers for LR grammars Automatic parser generators yacc bison yinTA no mg m BottomUp Parsing Rightmost derivation Backward Start with the tokens End with the start symbol Match substring on RHS of production replace by LHS 12345 e E2345 e s2345 e SE345 S 9 51 l E e s34 5 6 5 45 e ss45 E 9 um i S e SSE5 e ss5 e sE5 e s5 BottomUp Parsing rE HE E 9 numl s 12345 e E2345 e s2345 e sE345 amp S E Advantage of bottornup parsing I can postpone the selection of I productions until more of the 1 input is scanned earm ramp in m TopDown Parsing E i E E 9 numl s l s 9 sE 9 EE 9 sE 9 sEE 9 sEEE 9 EEEE 9 1EEE 9 1 2EE ag n m In le most derivation entire tree above token 2 has been anded when encountered H H m so than in mm m m TopDown vs BottomUp Boll omup Don r need ro guxe om as much of ie parse nee for a given amounl ofinpul 9 More lime I0 decide whar rules to apply spanned unseanned spanned unseanned Topdown Bottomup warm ssxj as we use 2192008 Terminology LL vs LR Llel e Leftrtorright scan or input Leftrmost derivation e k symbol lookahead e Toprdown pr predictive parsing pr LL parser e Perlorms preprder traversal pr parse nee Llel e Lefrrtorrlghr scan or input n e Performs ppsrprder traversal pr parse nee mam maasnrr 2m Another example Consider the following grammar s aABe AaAbc i b Bgt d Consider sentence abbcde abbcde gt aAbcde gt aAde gt aABe gt S The parser must find a substring 3 of the tree s frontierthat matches some production A9 Bthat occurs as one step in the rightmost derivation Informally we call this substring 3a handle yinTA man mg m Handles A handle ofa string is a substring which matches the RHS ofa production and whose reduction represents one step along the reverse of a rightmost derivation A handle ofa sentential form y is a production Aa and a position ofy where the string 3 may be found and replaced by A to produce the previous sentential form in a rightmost derivation ofy mam L JeringDi ShiftReduce Parsing Parsing actions A sequence of shift and reduce operations Parser state A stack of terminals and non terminals grows to the right Current derivation step stack input stack Unconsumedinput 123M5 e 12345 E23M5 e E 2345 S23M5 e s 2345 SE3M5 e sE 345 ensm men n m ShiftReduce Actions Parsingisasequence ofshiftsand reduces Shift move lookrahead token to stack input 12345 2345 Reduce Replace symbols 3 from top of slackwith none terminal symbol X corresponding to the production X9 3 legr mm L push Xl action reduce S 9 SE 345 11an in mi m m n ShiftReduce Parsing s9sEiE E9num s un stack tnputstxeam achun 12 345 1z345 stun 1z345 1Z345 Slut 1z345 t z345 lt Ht E lt Ne 5z34s 5 z345 5 z345 5 z3 s 5z34s 52 34s SE345 55 34s 534s 5 34s t 534s 5 345 mm 5 5 3 4s slu 534s 5 4s reduce E9 num mm as as 2m Potential Problems How do we know which action to take whether to shift or reduce and which production to apply Issues Sometimes can reduce but should not Sometimes can reduce in different ways mam c sdasnmi 2m Action Selection Problem Given stack B and lookahead symbol b should parser Shift b ontothe stack making it 3b Reduce X 9 y assumingthatthe stack has the form 3 my making it CLX If stack has the form my should apply reduction X 9 y or shift depending on stack prefix a CL is different for different possible reductions since y s have different lengths mm rltun mg m i LR Parsing Engine Basic mechanism Use a set of parser states Use stack with alternating symbols and states 5415 5 MM 5 lblue state ntlmhersl Use parsing table to Determine what action to apply lshiftreducel Determine next state The parser actions can be precisely determined from the table mam wmwgm LR Parsing Table Terminals Nonterminals Next action State and next state Action table Goto table ensm mm m m r LR Parsing Table Example s 9 L id L 9 s ts Input terminal Nonterminals id t 5 L 53 52 59m 59m 59m 59m 59m 53 52 g7 g5 accept 56 58 59L 59L 59L 59L 59L L95 L95 L95 L95 L95 State wwqmmLWN 53 s g9 L9Ls L9Ls L9Ls L9Ls L9Ls 11 am as mm m m 2192008 LRk Grammars Building LRO Parsing Tables LRk Lefttoright scanning rightmost e oerine states or the parser derlvatlonl k l00ka head Cha rs 9 Build a DFA to describe transitions between states 0 Main cases 7 Use the DFA to build the parsing tap mm mm Each LRiOi state is a set of mm items 39 e n LRO item x gt a pwhere x gt op is a production in the To build the parsing table e Some variations SLR and LALR1 Parsers for LRO Grammars grammar e The LRO items keep track or the progress on all or the possible upcoming productions r The item X 9 a pabstracts the the string eat the top of the stac Determine the actions without any lookahead tact thatthe parser already matched k Will help us understand shiftreduce parsing warm Example LRO State LRO Grammar An LRiOi item is a production from the languagewith a Nested lists Pars tree for separator quot somewhere inthe RHS ofthe production 5 L I rd M WW 7 L9 s LS A Examples AK state 1 aw L s iem a aibh camera A d a a bred g Subrstring before lsalreadv onthestacklbeginnings of possible y39sto be reducedl w u mxrl A L s Subestring after what we might see next ls L b yawTm rltx1napiiii nt 1 Mu Wm unwilch an 11 Start State and Closure Closure Example Start state Augment grammar with production S39 9 S S Start state of DFA has empty stack S39 9 S S DFA start state a s 9 s 3 Closure ofa parser state 5 953 31 Start with ClosureS S Then for each item in S Set oipossible plodudious lo beieduced next X 9 a 3 ddediiemshavelhe located atthe beginning 39 no symbols fol these items on the stac 39y t Add items for athe productionsv 9 yto the closure of S V 9 alarm mm 1V 1391 um in mm 1V ii 2192008 The Goto Operation Exercise Goto operation describes transitions between parser states which are sets of items Algorithm for state S and a symbol Y If the item X 9 on Y 3 is in I then 1 HI E9 39E hel Closmemjw Gotol Y Closure X 9 on Y 3 2 HI E gt E 1 E gt L T then GotoIl M 5111 parm Shift Terminal Symbols Goto Nonterminal Symbols Grammar S 9 L l id L S l LS In new state include all items that have appropriate input symbol just an dot Mm do in 1056mm and take dome sarne algorithm for transitions on nontenninals winning 77 ymm twinning mnm Full DFA Applying Reduce Actions Glammnr I s 9 as i id states Causing reductions L 9 s l L s dot has reached the end Pop RHS off stack replace with LHS X X a p then rerun DFA e g x minMr m Sanrr in m h um varm 2192008 Computed LR Parsing Table Building the Parsing Table States in the table states in the DFA Input terminal Nonterminals y For transmon S 9 S on terminal C d S s L 1 53 Zr 4 TableSC ShiftS 2 sea sea said 59d said 3 s 52 g7 g5 For transmon S 9 S on nonterminal N 3 4 t g 5 55 Sr amp TableSN GotoS 59L 59L 59L 59L 59L 7 L9 5 If S is a reduction state X 9 3 then a 53 52 g9 9 L9Ls L9LS L9Ls L9LS L9LS TabeS ReduceX 913 blue shi red reduce mm m 2 mm m a Parsing Algorithm Parsing Example ab s a L l 1 Algorithm look at entry for current state 5 33112quot Tank 1255 33 ng 3 L s i Ls 39 39 ab 6 1 ab shi gain 3 and input terminal a abe 133 3in sht gutu2 ab e 13KaZ b reduce said If Tablesa shift t then shift Sm may ms reduce HS 39 pusht let a be the next input symbol own 6 1 my sht gain 6 Lb 133L5 b reduce S9L lf Tablesa X9 otthen reduce Sb 6 1357 m reduce L95 Lin 6 13L5 b sht g t 8 I pop l otl t top pushGOTOtX output Lin 6 13L58 m sht gum 9 Lin 6 13L58b2 3 reduce said 391 Ls e 13L5859 t a L9LS L 6 13L5 3 sht gain 6 L e 13L5 3 reduce S9L S 6 154 S dune yaw1m m mmrm m n Reductions LR0 Summary On reducing X 9 3 with stack 043 LR0 parsing recipe Pop 3 off stack revealing prefix ot and state Start with LR0 grammar Take single step in DFA from top state Compute LR0 states and build DFA Push X onto stack with new DFA state Use the closure operation to compute states Example Use the 3010 operation to compute transitions de ation stack input action Build the LR0 parsing table from the DFA ab 6 133 201 shimgotol This can be done automatically ab e 1 3 3 a 2 b reduce s 9 id sb e 1 3 3 57 b reduceL a 5 mm m x mm mums 2192008 The Parser Generator Yacc A Yacc source program has three parts Dec ara ions 83 Translation rules 83 orting c routines supp Uan system command yacc fooy transforms fooy into ytabc gcc ytabc y obtains binary file aout mm as as we 2m y Yacc Example H include ltctype hgt 8 Btoken DIGIT line exp n pint dnquot 51 exp exp 39 tem 55 51 53 term term term m factor 55 51 53 I factor factor exp 39 55 52 DIGIT Wm mum 2m p Yacc Example 33 yylexO int c c getchazor if isdigitC y 1 y val c return DIGIT l etun c mm rltnnwu ni w Using Yacc with Ambiguous Grammars Unless otherwise instructed A reducereduce conflict is resolved by choosing the conflicting production listed first A shiftreduce conflict is resovled in favor of shift mm mm Mg m 9 Yacc With Ambiguous Grammars H E E E E E 8 IE E IE E IE Hoken 3mm Inumbe heft i ir might quotMINUS lines lines exp n printf dn 52 l empty exp exp ir exp 55 exp w exp 55 nu gt4 uu ensm num m m n Yacc With Lex number 09e7 I 09e os m 1 l number sscanfyytext 31 Eyylval return NUMBER nl return yytextmrl m yylexO int c 83 c etcharo if Eedigiucn nclude lex39yy39cn yylval c 039 return DIGIT return C l 1391 rxm m imp m m A
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'