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

Compiler Construction

by: Allie West II

Compiler Construction CSCI 4555

Allie West II

GPA 3.51


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

Class Notes
25 ?




Popular in Course

Popular in ComputerScienence

This 26 page Class Notes was uploaded by Allie West II on Thursday October 29, 2015. The Class Notes belongs to CSCI 4555 at University of Colorado at Boulder taught by Staff in Fall. Since its upload, it has received 18 views. For similar materials see /class/231990/csci-4555-university-of-colorado-at-boulder in ComputerScienence at University of Colorado at Boulder.

Popular in ComputerScienence


Reviews for Compiler Construction


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: 10/29/15
Syntax Amer Diwan What is syntax Syntax 7 Determines the form of programs Semantics 7 Determines the meaning of programs 7 Not all syntactically correct programs are meaningful 7 eg int i im is syntactically correct but semantically meaningless Comnilati on and syntax CharaCter Stream Scanner lexical anal Syntax Token stream Parser syntax analysis Dar fr Semantic analysis and IR eneration Ab l Machineindependent o timizations Target code generation Assembly or machine language Machinespecific Modified a emhlv Otlmlzatl m Modified intermediate form Lexical analysis What are tokens 7 Variables x i theCount 7 Keywords w beg 7 Numbers 10 1 5E10 7 Other symbols How do languages specify legal tokens What is a legal variable name Specifying tokens with regular expressions What is a regular expression 7 A character eg openingibrace 7 An empty string denoted 7 Two regular expressions next to each other eg autoiincr plus plus 7 Two regular expressions separated by a vertical bar eg binaryiop plus l minus 7 A regular expression followed by a kleenestar eg integer digit digit Examples of regular expressions variablename alblzABZabzABZO9 What kinds of variable names does this allow digit Ol9 unsignedinteger digit digit unsignednumber unsignedinteger unsignedinteger Recognizing tokens Adhoc approach small grammars getWordInputStream is getNumberInputStream is matchKeywordString s if sequal BEGINquot else if sequal ENDquot o if isnumnextphar return new NumbergetNumber else word getWord if matchKeywordword then else return new Identifierword Recognizing tokens larger grammars Build or have a tool build a scanner based on a DFA start 0 digit Want the longest token myVar and not In or my or myV or Language choices may complicate lexical analysis FORTRAN pre 90 7 DO 517 125 assigns a value 125 to variable DO5I spaces are ignored 7 May lead to programmer errors Pascal is 4 7 Start of a oating point number 451 7 Half way through a subrange 420 7 Need to look ahead 2 characters Parsing What are the possible statements of a language 7 Addition ab 7 While loop while b 7 For loop for i 0 i lt 10 i 7 Class declaration class S extends T How do languages specify legal statements Contextfree grammars regular expressions recursion eXpr gt identifier number eXpr eXpr operator expr operator gt Symbols that appear on lhs are nonterminals Symbols that appear only on rhs are terminals 7 A scanner returns a stream of terminals to the parser Parse tree for xy exprgt identi er l number l expr A l 63pr operator expr operator gt l l l GXK operrtor BXK identifierx identi e1y Does this match what you would mean with xy Another parse for Xy exprgt identi er l number l expr eXpr l expr Operator expr Aoperator gt l l eXpr operator eXpr 39 ex r identi ery identi e1X Does this match what you would mean with xy Ambiguity in grammars When more than one production can be used 7 Resolution mechanisms Precedence has higher precedence than AssociatiVity 10 4 3 means 10 4 3 Let s rewrite the grammar to eliminate ambiguities 1043 Desired parse a nonterm1nal a nonterminal number 10 number4 number3 groups to the left left associative instead of expr gt expr operator expr have eXpr gt eXpr operator term l term term gt identi er l number lO43 Desired parse a non 1nal a no inal number3 number 10 number4 Note how the higher precedence operators come lower in the derivation tree eXpr gt eXpr addiop term l term term gt term multiop factor l factor factor gt identifier l number l factor l expression Parsing using the grammar Top down parsing Predlct nonterminal and match 7 idilist gt id idilistitail idilistitail gt id idilistitail l matchidlist match idO match id list tail match i5 list tail if m match commaO match id Inatch id list tail I else If burtoken semicolon match semicolor1 else eror l 7 More intuitive when grammar is suitable Parsing What next What does the parser in the previous slide do 7 X y z Yup e X y zN0pe e X y z Nope What else needs to happen in a parser 7 Build a parse or abstract syntax tree for later use Building an AST Eg AST for ltulgtltligt item 1 ltligtltligt item 2ltligtltulgt ListNode Li stItem PlainT extNo de String Top down parsing When is the grammar suitable When you can predict the next production with a fixed small number of lookaheads How many lookaheads do we need 7 idilist gt id idilistitail idilistitail gt id idilistitail l 7 idilist gt idilist id l id 7 expr gt expr addiop term l term term gt term multiop factor l factor factor gt identifier l number l factor l expression An example AgtAaAabc Another example S gt a S a epsilon Bottomup parsing Look at token stream and construct nonterminals 7 idilist gt id idilistitail idilistitail gt id idilistitail 7 Parsing AB A doesn t match the rhs of any production A ditto AB ditto AB matches a rhs of idilistitail A B idilistitail ditto A id list tail matches rhs of idilist Done More on bottomup parsing Can handle more grammars than topdown since there is no prediction We will look at only topdown in this course Language design and parsing Language design can have a significant effect on the complexity of parsers 7 Languages that are not amenable to straightforward parsing may also interfere with human readability 7 eg Pascal ifthen else statements if X then if y then write y s then else write whose else Relationship to other courses CSCI 4555 7 More emphasis on using parser generation tools for larger grammars than we will use here Relationship to readings Reading covers parsing and lexical analysis in more detail 7 Gives more examples for both 7 Discusses how to resolve ambiguities in grammars You will need to know the above for homework and quizzes Reading for next class Sections 31 32 33 35 36 we will cover Section 3 4 with Chapter 8 Semantic Analysis Amer Diwan ScanningParsing versus semantic analysis In the syntax section we looked at how to recognize syntactically correct programs But you need to do more than that 7 Check types 7 Pick overloaded operators 7 Resolve scopes 7 Generate code Type checking example char pl p2 int i p1 p2 i expr gt expr 0p term term term gt identi er number assign identifierp1 expr expr op term term identifier i identifierp2 Type checking example 2 int p1 char p2 int i p1 p2 i expr gt expr 0p term term term gt identi er number ERROR int char a k 4 1dent1f1erp1 e r A V A e r op te X T V V ter39m identifieri V identifierp2 Type checking example 3 char pl p2 int i pl p2 i expr gt term expr expr gt op term expr l epsilon term gt identi er l number asmgn identifierpl expr term expr 1dent1f1erp2 op term expr identifier i epsilon Overload resolution example oat f int i pl p2 i expr gt expr op term l term term gt identi er l number V 5 ex r op te Y int addition or rim float addition 1dent1f1er 1 lt a E identifier f Building AST Egt E1 T Enptr mknode E1nptr Tnptr E1 T Enptr mknode E1nptr Tnptr T Enptr Tnptr T gtT1 F Tnptr mknode T1nptrFnptr F Tnptr Fnptr F gt E Fnptr Enptr id Fnptr mkleafid symtab entry of id const Fnptr mkleafconst value of const Example continued 4 56 I Tquot F1 14 MH I IFquot npfrT7 npfrp1 npfr A gt II I L Type checking with the AST char pl p2 int i p1 p2 i program gt stmt assign stmt gt id eXpr stmt eXpr gt node node eXpr gt node node assign id eXpr gt epsilon num eXpr gt epsilon program idpl a idp2 idi Typechecking with the AST cont program 7 mig 39d 1 39 gt0 1 p A idp2 idi Static versus dynamic semantics Static semantics 7 Enforced at compile time 7 Examples in previous slides are that of static semantics Dynamic semantics 7 Enforced at run time Example of dynamic semantics Array bounds check 7for i 0 i lt 100 i Ai 0 7 In safe languages this translates into 7for i 0 i lt 100 i if i in A firstA last then Ai 0 else error The check happens as the program is running An aside on dynamic semantics Compilers try hard to minimize effort to enforce dynamic semantics at run time eif 0100 in A firstA last for i 0 i lt 100 i Ai 0 else for i 0 i lt 100 i if i in A firstA last Ai0 else error H How to do semantic analysis Use attribute grammars e A formal system 7 Can generate code to propagate attributes automatically Adhoc action routines e Sprinkle pieces of code that are executed when a terminalnon terminal is matched 7 More operational than attribute grammars Attribute grammars Productions propagation of attributes 7 eXpr1 gt eXpr2 eXpr3 op selectOp eXpr2ty eXpr3ty eXpr1ty opty 7 selectOp operator X type X type gt type 7 ty is an attribute that the above propagates Attribute grammars type of rules Copy 7 F gt E Fval Eval Invoke semantic functions 7 eXpr1 gt eXpr2 eXpr3 op selectOp eXpr2ty eXpr3ty eXpr1ty opty selectOp operator X type X type gt type 7 Semantic functions primitives speci ed by the language designer When to compute the attributes expr1 gt expr2 expr3 expr1ty opty op selectOp expr2ty expr3ty The attribute grammar processor figures out the order in which to compute attributes 7 eg opty before expr1ty Attribute grammars Use them on abstract syntax or concrete syntax Concrete syntax has many details that are irrelevant to semantics 7 eg F gt E useful for parsing With the correct precedence but otherwise useless Abstract syntax 7 eliminates all the useless syntactic details 7 attribute grammar can be more concise Book incorrectly emphasizes AG on concrete syntax Using action routines An adhoc alternative to attribute grammars 7 Interleave code action routines with parsing 7 Often used to build AST during a parse Example 39 E gt T EEarg Tptr Eptr EEptr 39 EEI gt T EElarg makejlusEElarg Tptr EE2 EE1ptr EElptr epsilon EE1ptr EE1arg 39 T gt TptrEptr I number Tptr makeilea numberval Note that programmer has to specify order of evaluation Relationship to reading Reading gives additionallonger examples of both attribute grammars and action routines 7 Helpful for project 1 and 2 Discusses the differences between different kinds of attribute grammars in more detail Relationship to other classes 39 CSCI 4555 7 You will get experience with action routines when you use a parser generator 7 You will get to use attribute grammars for a compiler generator Next topic Control flow Read chapter 6 except 653 and 67 Example building an abstract syntax tree El gt E2 T Elptr makeibiniopC Jr E2ptr Tptr E gt T Eptr Tptr Tl gt T2 F Tlptr makeibin70p T2ptr Fptr T gt F Tptr Fptr F gt E Fptr Eptr F gt const Fptr makeilea constval


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!"

Kyle Maynard Purdue

"When you're taking detailed notes and trying to help everyone else out in the class, it really helps you learn and understand the I made $280 on my first study guide!"

Jim McGreen Ohio University

"Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."


"Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

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.