Compilers & Interpreters
Compilers & Interpreters CS 4240
Popular in Course
Popular in ComputerScienence
This 0 page Class Notes was uploaded by Alayna Veum on Monday November 2, 2015. The Class Notes belongs to CS 4240 at Georgia Institute of Technology - Main Campus taught by Nathan Clark in Fall. Since its upload, it has received 15 views. For similar materials see /class/234075/cs-4240-georgia-institute-of-technology-main-campus in ComputerScienence at Georgia Institute of Technology - Main Campus.
Reviews for Compilers & Interpreters
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: 11/02/15
Exam 1 Review Logistics a When Where In class 108 9 Type Open booknote 9 What to bring Text book reference books lecture notes 0 But must print these out Pencilspens gtgt No laptops or cell phones Topics Covered a Lexical analysis 25 a Syntax analysis 50 9 Semantic analysis 25 gtgt Percentages are VERY approximate 9 Not covered Detailed ll bis sJ ntax General questions about exbison are possible Open Book Exams 9 OPEN BOOK DON T STUDY 9 Open book means Memorizing things is not that important If you forget something you can look it up 9 But gtgt If 39 ou are tr39 in to learn or relearn stuff during the test you won t nish gtgt Assume the test is not open book 0 Don t rely on booknotes 0 Treat them as a backup 3 How to Study a Refamiliarize yourself with all the material Where to nd things if you get confused a Practic solving problems Do them Wo looking at the answer gtgt Class problemsexamples from lectures Examples in book 0 Ifyou are ambitious mums wt m we or mh chapter gtgt Practice so that you can do them Without thinking much Exam Format oz Short answer 40 Explain something gtgt Short problems to work out oz Longer design problems 60 E g construct a parse table ozo Range of questions Simple Were you conscience in class Grind it out Can you solve problems Challenging How well do you really understand things oz My tests tend to be long so move on if you get stuck Lexical Analysis aka Scanning a Regular expressions How to write an RE from a textual description 9 How does lex ex work Regular Expressions COHSU UCt a regular CXpI CSSlOl l OVCI the alphabet abc that are at least 3 characters in length and end with an a NFAs Construw W l Fl l lor the following regular expression 21 ba e Syntax Analysis aka Parsing 9 Context free grammars Derivations ambiguity associatiVity a Parsing Topdown LL1 building parse tables FIRST FOLLOW Bottomup LRO LR1 SLR LALR 0 Building parse tables Closure Goto shiftreduce 9 Abstract syntax tree Context Free Grammars A context free grammar is ca able of re resenting more languages than a regular expression What is the major reason for this Context Free Grammars Write a Vrarnrnar t0 1 arse all strinvs consistinv 0f the symbols abcde 0f the form anbzmcmdneO Where m n 0 are gt 0 LL 1 Grammars sage EeEmnEmHm Is the above Grammar LLl Explain your answer Recall Computing FIRSTFOLLOW O 00 l 2 3 4 De 1 2 O 00 3 Determining FIRSTX if X is a terminal then add X to FIRSTX if X9 8 then add 8 t0 FIRSTX if X is a nonterminal and X 9 Y1Y2Yk then a is in FIRSTX if a is in FIRSTYi and 8 is in FIRSTYj forj 1i1 if 8 is in FlRSTY1Y2Yk then 8 is in FIRSTX termining FOLLOWX if S is the start symbol then is in FOLLOWS ifA 9 ocBB then add all FIRSTB 8 t0 FOLLOWB if A 9 ocB or ocBB and 8 is in FIRSTB then add FOLLOWA t0 FOLLOWB 13 FirstFollow Computation Construct FirstFollow sets for the following LL1 grammar for each nonterminal S A B C S AB A bC B aABle C9Sc Recall Closure and Goto 9 Closure of a parser state gtgt Start with ClosureS S Then for each item in S X90cYB 0 Add items for all the productions Y 9 y to the closure of S Y 9 y 9 Goto operation describes transitions between parser states which are sets of items gtgt Ifthe item X 9 on Y 3 1s1n 1 then gtgt GotoI Y Closure X 9 on Y B 15 DFA Construction for LRO Construct the LRO DFA for the following grammar E 9 E T T T 9 TF F F 9 Fgtxlt I a I b NOIG IS not the closure operator Are there any shiftreduce con icts in table that you would construct from the DFA How do you know Bottomup Parsing Which is ca able of A arsinv a larger set of languages LRO 0r SLR Abstract Syntax Trees Draw the AST for the following C function int foo int 21 b c i a 20 D Zl d for i0 ilt10 i c10ab caib Semantic Analysis 9 Syntaxdirected translation gtgt Semantic actions building the AST 9 Scope information Hierarchy of symbol tables a Type checking gtgt Staticd7 namic stronvWeak gtgt Static semantics type judgments proof tree Static Semantics Consider the following language that manipulates ints bools and stacks T 9 int bool stackT E9idnumEE E 9 topE popE pushEE newstackT emptyE Notes 1 Add can only be applied to ints or stacks intl int2 sum stackl stack2 stack of concatenation of elements note elements must be same type 2 topb39 top element of stack b 3 popE resultant stack after removing top element 4 ush E E add E to stack returns resultin stack 5 newstackT produces new empty stack of type T 6 emptyE is true if E has no elements false otherwise 20 Static Semantics 2 a Write the static t A echecking rules for all expressions in this language b Is the followin well t ed in an context p0ppushxy5 c Is the following well typed in any context pushnewstac1xuu LOpKX pushyemptyz 21
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'