New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

Be part of our community, it's free to join!

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here

Programming Languages

by: Mrs. Carolyne Abbott

Programming Languages CS 4610

Mrs. Carolyne Abbott
GPA 3.71

Westley Weimer

Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Westley Weimer
Class Notes
25 ?




Popular in Course

Popular in ComputerScienence

This 67 page Class Notes was uploaded by Mrs. Carolyne Abbott on Monday September 21, 2015. The Class Notes belongs to CS 4610 at University of Virginia taught by Westley Weimer in Fall. Since its upload, it has received 33 views. For similar materials see /class/209660/cs-4610-university-of-virginia in ComputerScienence at University of Virginia.

Similar to CS 4610 at UVA

Popular in ComputerScienence


Reviews for Programming Languages


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/21/15
Outline Review of bottomup parsing Computing the parsing DFA Closures LR1 Items States SPOILER ALERT Transitions R Using parser generators Handling Conflicts SNAPE KILLS TRINITY WITH ROSEBUD In One Slide An LR1 parsing table can be constructed automatically from a CFG An LR1 item is a pair made up of a production and a lookahead token it represents a possible parser context After we extend LR1 items by closing them they become LR1 DFA states Grammars can have shift reduce or reduce reduce conflicts You can fix most conflicts with precedence and associativity declarations LALR1 tables are formed from LR1 tables by merging states with similar cores 3 Bottomup Parsing Review A bottomup parser rewrites the input string to the start symbol The state of the parser is described as on gt 39y 0c is a stack of terminals and nonterminals 39y is the string of terminals not yet examined o Initially gt x1x2 x n 4 Shift and Reduce Actions Review Recall the CFG E gt int E E o A bottomup parser uses two kinds of actions Shift pushes a terminal from input on the stack Egt int gtEintgt Reduce pops O or more symbols off of the stack production RHS and pushes a nonterminal on the stack production LHS EEEgt gtEEgt 5 Key Issue When to Shift or Reduce Idea use a finite automaton DFA to decide when to shift or reduce The input is the stack The language consists of terminals and nonterminals We run the DFA on the stack and we examine the resulting state X and the token tok after gt If X has a transition labeled tok then shift If X is labeled with A gt B on tok then reduce 6 LR1 Parsing An Example gt int int int shift int gt int int E gt int E gt int int shiftx3 E int gt int E gt int E E p int shift E E p int E gt EE E gt int shift x3 Eintgt E gtint E E p 5 shift EEgt E gtEE V E gt accept T E E E on 7 End of review l W l39 WWW PHDICDHICS OOH Key Issue How is the DFA Constructed The stack describes the context of the parse What nonterminal we are looking for What production rhs we are looking for What we have seen so far from the rhs Edit View Isert Debugger Project Run Window Help W New cram ra l ilE39W39p ino ii ahlg ljl II New document from template New gt will be populated by IDRFILENEW at run me l a Open cmo Close CtrlW Q3 Emaire inns Save As Sam395 Item 9 h x frxgrth fifmquot J W Md If Mme tau m J L 1 4m 2 Quay 10 u MM M m new Ls 5mm ku aln w w n 4 a 14 h L 1 43 y I rm l 43 h 75 bAlA m 5 3 1r LR 1 Table Construction Three hours later you can nally parse E p E E int 0 Parsing Contexts E Consider the state int int int The stack is E Context WearelookingforanE gtEo E Have have seen E from the righthand side WearealsolookingforE gtointh n E E Have seen nothing from the righthand side One DFA state describes several contexts gtint int Red dot where we are LR1 Items An LR1 item is a pair X gt ocoB a X gt cup is a production a is a terminal the lookahead terminal LR1 means 1 lookahead terminal X gt ocoB a describes a context of the parser We are trying to find an X followed by an a and We have oc already on top of the stack Thus we need to see next a prefix derived from 3a 12 Note The symbol gt was used before to separate the stack from the rest of input on gt y where on is the stack and y is the remaining string of terminals n LR1 items o is used to mark a prefix of a production rhs X gt out a Here 3 might contain nonterminals as well In both case the stack is on the left 13 Convention We add to our grammar a fresh new start symbol S and a production S gt E Where E is the old start symbol No need to do this if E had only one production The initial parsing context contains S o E S Trying to find an S as a string derived from ES The stack is empty 14 LR1 Items Cont In context containing E gt E o E f follows then we can perform a shift to context containing E gt E o E o In context containing E gt E E o We can perform a reduction with E gt E E But only if a follows LR1 Items Cont Consider a context with the item E gt E o E We expect next a string derived from E There are two productions for E E gtint and E gtEE We describe this by extending the context with two more items E gtoint E gtEE 16 The Closure Operation The operation of extending the context with items is called the closure operation Closureltems repeat for each X gt ocoYIS a in Items for each production Y gt 39y for each b e FirstBa add Y gt 7 b to Items until Items is unchanged 17 Constructing the Parsing DFA 1 Construct the start context ClosureS gt E s gt oE E gt oEE E gt oin l39 E gt oEE E gt int We abbreviate as S 0E E 0EE E oin l39 18 PLANNING You have a plan right Constructing the Parsing DFA 2 An LR1 DFA state is a closed set of LR1 items This means that we performed Closure The start state contains S gt oE S o A state that contains X gt on b is labeled with reduce with X gt on on b And now the transitions 20 The DFA Transitions A state State that contains X gt ocoyB b has a transition labeled y to a state that contains the items TransitionState y y can be a terminal or a nonterminal TransitionState y Items lt for each X gt ocoyB b e State add X gt ocyoB b to Items return Closureltems LR1 DFA Construction Example S gt 0E E E gt oEE E gt oin l 22 LR1 DFA Construction Example S gt 0E E E oEE mf E gt oin l E 23 LR1 DFA Construction Example 5 E gt 0EEI inf E gt oin l E 24 LR1 DFA Construction Example S gt0E E E gtin r E gt oEE inI on E gt oin l E LR1 DFA Construction Example M E EgtEEI inf E gtm r on gln E gtoin 39 2 E S gtE0 E gt EoE LR1 DFA Construction Example S gt0E E E gtin r E gt oEE inI on E gt oin l 2 E S gt E E EoE accepT on 27 LR1 DFA Construction Example S gt 0E E gt oEE E gt oin l E m r 0 39 S gt E E gt E0E E E E accepT on 28 LR1 DFA Construction Example 5H E 545 M W onl O E gt mi EgtE EI E S gt E0 E gt EoE accepT on 29 LR1 DFA Construction Example S gt0E E E gtin r E gt oEE inI on E gt oin l E E E E S gtEo E gt E E quot39 E gt EoE accem E oEE 0n E gtoin 39 30 LR1 DFA Construction Example S gt0E E E gtin r E gt oEE inI on E gt oin l E E E E S gt E0 E gt E E quot39 E gt EoE ClCC IP r E E gt oEE 0 E gt oin r inf LR1 DFA Construction Example S gt0E E E gtin r E gt oEE inI on E gt oin l E E E E S gt E0 E gt E E quot39 E gt EoE ClCC IP r E E gt oEE 0 E gt oin r inf E gt in ro 32 LR1 DFA Construction Example S gt 0E E gt 0EE E gt oin l E S gt E E gt EoE m r on on E E E 1lt E gt EoE E gt oEE accepT E gt oin l in r E gt in ro I on E gtin r 33 LR1 DFA Construction Example Mm L E EEl inf on I E 0 139 m E gtEoE E S gt E E gt E E quot39 E gt EoE accem E E oEE 0 E gt oin r E E gt EEo in r E gtEoE Egtin 39 E gtin r and so on on 34 Q Movie Music 420 842 In a 1995 Disney movie that has been uncharitably referred to as quotHokeyHontasquot the Stephen Schwartz lyrics quotwhat I love most about rivers is you can39t step in the same river twicequot refer to the ideas of which Greek philosopher Q Games 522 842 In this 1982 arcade game features lancewielding knights mounted on giant flying birds and dueling over a pit of lava Destroying an enemy knight required ramming it such that your lance was higher than the enemy39s LR Parsing Tables Notes Parsing tables the DFA can be constructed automatically for a CFG The tables which cannot be constructed are constructed automatically in response to a CFG input You asked for a miracle Theo I give you the LR1 Hans Gruber Die Hard But we still need to understand the construction to work with parser generators eg they report errors in terms of sets of items What kind of errors can we expect 37 Sometimes you should back down ShiftReduce Conflicts If a DFA state contains both X gt ocoaB b and Y gt yo a Then on input a we could either Shift into state X gt Ola3 b or Reduce with Y gt y o This is called a shiftreduce conflict 39 ShiftReduce Conflicts Typically due to ambiguities in the grammar Classic example the dangling else S gt if E then S if E then S else S OTHER Will have DFA state containing S if E then So else S gt if E then So else S x o If else follows then we can shift or reduce Default bison CUP etc is to shift Default behavior is as needed in this case 40 More ShiftReduce Conflicts Consider the ambiguous grammar E gtEE EE int We will have the states containing E gtEoE E gtEEo E gt0EE gtEE gtE0E Again we have a shiftreduce on input We need to reduce binds more tightly than Solution declare the precedence of and More ShiftReduce Conflicts In bison declare precedence and associativity 1eft 1eft high precedence Precedence of a rule that of its last terminal See bison manual for ways to override this default Resolve shift reduce conflict with a shift if no precedence declared for either rule or terminal input terminal has higher precedence than the rule the precedences are the same and right associative 42 Using Precedence to Solve S R Conflicts Back to our example E gtEoE E gtEEo E gtoEE gtEE gtEoE Will choose reduce on input because precedence of rule E gt E E is higher than of terminal 43 Using Precedence to Solve S R Conflicts Same grammar as before E gtEE EE int We will also have the states E gtEoE E gtEEo E gtoEE gtE E gt EoE Now we also have a shiftreduce on input We choose reduce because E E E and have the same precedence and is leftassociative 44 Using Precedence to Solve S R Conflicts Back to our dangling else example S gt if E then So else S gt if E then So else S x Can eliminate conflict by declaring else with higher precedence than then Or just rely on the default shift action But this starts to look like hacking the parser Avoid overuse of precedence declarations or you ll end with unexpected parse trees The kiss of death Reduce Reduce Conflicts If a DFA state contains both X gt on a and Y gt 30 a Then on input a we don t know which production to reduce This is called a reducereduce conflict 46 Reduce Reduce Conflicts Usually due to gross ambiguity in the grammar Example a sequence of identifiers s gt e id id 5 There are two parse trees for the string id S gt id S gt id S gt id How does this confuse the parser 47 More on Reduce Reduce Conflicts Consider the states S gt id 0 S S oS S idoS S 0 S gtid S gt 0 S S oid S S oid S S oidS S oid Reduce reduce conflict on input 5 S gt S gt id 5 gt S gt id S gt id Better rewrite the grammar S gt e id S 48 Can s someone learn this for me 1 1m Nu ynu can39t have a neural netwnrk HGT EFEIU H E Using Parser Generators Parser generators construct the parsing DFA given a CFG Use precedence declarations and default conventions to resolve conflicts The parser algorithm is the same for all grammars and is provided as a library function But most parser generators do not construct the DFA as described before Why might that be 50 Using Parser Generators Parser generators construct the parsing DFA given a CFG Use precedence declarations and default conventions to resolve conflicts The parser algorithm is the same for all grammars and is provided as a library function But most parser generators do not construct the DFA as described before Because the LR1 parsing DFA has 10005 of states even for a simple language LR1 Parsing Tables are Big But many states are similar eg E 39 w gtmo onl and E gtIn ro on Idea merge the DFA states whose items differ only in the lookahead tokens We say that such states have the same core We obtain E gt into En i 52 The Core of a Set of LR Items Definition The core of a set of LR items is the set of first components Without the lookahead terminals Example the core of X gt ocoB b Y gt 78 d is X gt 43 Y gt 78 53 LALR States Consider for example the LR1 states X gt on a Y gt B0 c X gt on b Y gt 3 d They have the same core and can be merged And the merged state contains X oco ab Y gt Bo cd These are called LALR1 states Stands for LookAhead LR Typically 10x fewer LALR1 states than LR1 54 LALR1 DFA Repeat until all states have distinct core Choose two distinct states with same core Merge the states by creating a new one with the union of all the items Point edges from predecessors to new state New state points to all the previous successors 0 G 93933 Example LALR1 to LR1 in r E gtinT on on T EEE on 56 The LALR Parser Can Have Conflicts Consider for example the LR1 states X gt one a Y gt Bo b X gt on b Y gt 30 a And the merged LALR1 state X gt one ab Y gt Bo ab Has a new reducereduce conflict In practice such cases are rare 57 LALR vs LR Parsing LALR languages are not natural They are an efficiency hack on LR languages Any reasonable programming language has a LALR1 grammar LALR1 has become a standard for programming languages and for parser generators 58 A Hierarchy of Grammar Classes Unambiguous Grammars Ambiguous Grammars From Andrew Appel Modern Compiler Implementation in Java Notes on Parsing Parsing A solid foundation contextfree grammars A simple parser LL1 A more powerful parser LR1 An efficiency hack LALR1 LALR1 parser generators Now we move on to semantic analysis 60 Take a bow you survived Supplement to LR Parsing Strange Reduce Reduce Conflicts Due to LALR Conversion from the bison manual 62 Strange Reduce Reduce Conflicts Consider the grammar S gtPR NL gtNNNL P gtTNLT R gtTNT N gt id T gt id P parameters specification R result specification N a parameter or result name T a type name NL a list of names 63 Strange Reduce Reduce Conflicts In P an id is a N when followed by or T when followed by id In R an id is a N when followed by T when followed by o This is an LR1 grammar But it is not LALR1 Why FOF obscure reasons 64 99 P lt N we Plt N JN lt EI 17 39Plt L 392 J lt E P lt N 39P P 9 Jaw mm W 390 i P lt N P lt N op N 1N N39lt 39IN o lt uo mm P e N LP N 1 aonpaJaonpaa Env l g p p L P L 1 IN lt d I P L lt d 591215 Um Med v What Happened Two distinct states were confused because they have the same core Fix add dummy productions to distinguish the two confused states Eg add R gt id bogus bogus is a terminal not used by the lexer This production will never be used during parsing But it distinguishes R from P 66 L9 P39lt N P39lt L sn oqopu a Isn oqplt t 39Plt NL a LNIa 17 39 39Plt L I i39ea P P39lt L Eug aaua a lv l ou lt 9109 U9J9JJQ P lt N P lt N opglt N 39IN39N lt 39IN 39Plt N4 p N lt 39IN 5 pg opglt P Li39lNquot d I m ied X13 Jam 591215 Um Med v


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.


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'

Why people love StudySoup

Bentley McCaw University of Florida

"I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

Anthony Lee UC Santa Barbara

"I bought an awesome study guide, which helped me get an A in my Math 34B class this quarter!"

Steve Martinelli UC Los Angeles

"There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

Parker Thompson 500 Startups

"It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

Become an Elite Notetaker and start selling your notes online!

Refund Policy


All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email


StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here:

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.