### Create a StudySoup account

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

Already have a StudySoup account? Login here

# Programming Languages and Compilers COMPSCI 164

GPA 3.93

### View Full Document

## 36

## 0

## Popular in Course

## Popular in ComputerScienence

This 89 page Class Notes was uploaded by Mr. Hayley Barton on Thursday October 22, 2015. The Class Notes belongs to COMPSCI 164 at University of California - Berkeley taught by Staff in Fall. Since its upload, it has received 36 views. For similar materials see /class/226666/compsci-164-university-of-california-berkeley in ComputerScienence at University of California - Berkeley.

## Similar to COMPSCI 164 at

## Reviews for Programming Languages and Compilers

### 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/22/15

Macro Expansion Macro Languages Lec rur39e 26 Prof F ateman CS 164 Lecture 26 Lecture Ou rline Languages can be ex rended by Tex r Transforma rions C pr39epr39ocessor39 is a weak example Lisp macr39o definitions are stronger Examples Prof Fateman CS 164 Lecture 26 C Preprocessor include quotfienamequot define YES 1 define I39a J39d2 I39a 3 fokensfrng undef Idenfl39 39er if cansfanfexpresson ifdef iden fer ifndef Idenfl39 er else endif Iine consfcmf I39a renumber The nex r line re errors Prof Fateman CS 164 Lecture 26 3 C Pr39epr39ocessor39 Example We could do This define Then define begin define end if igtO Then begin 11 b2 end Becomes if igtO a 1b 2 Prof Fateman CS 164 Lecture 26 C Pr39epr39ocessor39 Strength IT does cer39Tain useful Things To make up for39 deficiencies in The language Condi rional compila rion subjec r To compileTime flags defifdef Java doesn39T have a pr39epr39ocessor39 Though Prof Fateman CS 164 Lecture 26 5 C Pr39epr39ocessor39 Weaknesses IT is a DIFFERENT language from C For39 example define fooab 2ab define foo ab 2ab mean en rir ely differen r Things Scope We don39T need no s rinking scope Or39 do we Prof Fateman CS 164 Lecture 26 6 Other Macro string processors M6 came wi rh original UNIX TeX Typese r ring program from D Knu rh Emacs Elisp perhaps s rre rching The form VB macros for Microsof r Word e rc no r jus r s rring processing Perl Tcl are scrip ring languages wi rh possible subs ri ru rion usages Prof Fateman CS 164 Lecture 26 7 Lisp Macro DefiniTions The idea IT is parT of The same language Change The inTer39pr39eTer39 before calling a funcTion foo a b c ask is foo defined as a macro if so r39eplace iT by iTs expansion Then conTinue For39 The compiler befor39e compiling a funcTion call foo a b ask is foo a macro Prof Fateman CS 164 Lecture 26 8 WhaT do we change To puT if Then elseif else in Common Lisp in lisp now if a b c This is clumsy WhaT if you wanT To change The code To do if a b1 b2 c1 c2 c3 You have To rewriTe as if a progn b1 b2progn c1 c2 c3 Harder To ediT musT inserT progn b2 noT jusT b2 Proposal A NEW language synTax if a Then b1 b2 else c1c2 or even if a Then b1 b2 elseif c1c2 Then d else e violaTes spiriT of lisp BUT if you are willing To agree ThaT b1 b2 eTc are never Then elseifeTc we can wriTe a macro To Transform To normal lisp Prof Fateman CS 164 Lecture 26 9 A definition of if including checking defvar ifkeywordlist 39quotthenquot quotthenretquot quotelsequot quotelseifquot defmacro if amprest args do xx reverse args state init elseses nil totalcol nil cdr xx lookat nil nil col nil null xx cond eq state compl cond totalcol t error quotif illegal form squot args cond and symbolp car xx member symbolname car xx ifkeywordlist test stringequal setq lookat symbolname car xx cond eq state init more on next slide Prof Fateman CS 164 Lecture 26 not for human consumption during lecture A definition including checking continued from previous cond lookat cond stringequal lookat quotthenretquot setq col nil state then t error quotif bad keyword aquot lookat t setq state col col nil push car xx col eq state col cond lookat cond stringequal lookat IIelsequot cond e1seseen error quotif multiples e1sesquot setq e1seseen t setq state init push t col totalcol stringequal lookat quotthenquot setq state then t error quotif bad keyword squot lookat t push car xx col even more see httpFYQamp Bgghy q ig txt 11 Lisp Macro Implementation Interpreter defun interp x ampoptiona env quotInterpret evaluate the expression x in the environment env This version handles macrosquot cond symbolp x getvar x env otom x x isitomocro first x interp macroexpand x env case first x Prof Fateman CS 164 Lecture 26 12 Rest of interpreter changes defun macroexpand x quotMacroexpand This Lisp expressionquot if and Iis rp x is Thisamacro firs r x macroexpand apply isThisamacro firs r x res r x x defun isThisamacroname ge r name macro defmacro defmacro name parmlis r ampbody body quotDefine a lisp macroquot se rf ge r 39name 39schememacro Iambda p riir zltisstlsbpdwt 13 Lisp Macro Definitions permeate language Used r39ou rinely even for39 par39Ts of The base language Ie r Ie rquot and or39 cond case THERE IS NO AND in LISP macroexpandl 39and a b c cond no r a nil no r b nil r c Used for39 defining NEW cons rr39uc rs in The language wi rh near39ly comple re freedom of semantics Mai n rai ns similar39 par39en rhesi zed appearance Prof Fateman CS 164 Lecture 26 14 Lisp Macro DefiniTion downside IT can become complex To define a macro ThaT is as general as possible and cor39r39ecT If macr39os ar39e r39epeaTedly expanded as They are in The inTer39pr39eTer39 They can slow down oper39aTion 39 Expanding macr39os once in placequot is possible Though Prof Fateman CS 164 Lecture 26 15 Lisp Macro DefiniTions don39T change lexical model If you wish To change The LEXICAL MODEL of Lisp eg allow xab no spaces To be 5 Tokens This cannoT be done wiTh The lisp macr39oexpansion There is however a lisp r39eader39 macroquot and r39eadTable faciIiTy ThaT is char39acTeror39ienTed By using a characTer39 macr39o we can swiTch sur39face synTax change lexer39 par39ser39 eTc so we can embed MJ code in lisp 23 inT x meThod fr39eTur39n x1 Prof Fateman CS 164 Lecture 26 16 You have already done macro expansions by hand for MCI And Lisp We don39T need AND and OR We can use IF BuT Then We don39T need IF We can use COND Do we have To make special checks for39 These oper a rions or39 can we make general faciliTies Of course we can defmacr39o anda b Iis r 39if a b or using no ra rion defmacr39o anda b if a b defmacr39o myor39 a b if a r b defmacr39o if pr ed Th el cond pr39ed ThT e Prof Fateman CS 164 Lecture 26 17 The magic and The mysTery From Time To Time we have used common lisp program segmenTs usually wiThouT commenT like incf x This compuTes yx1 sTores iT in x and reTurns y Can we wriTe a funcTion To do This defun myincf xseTf x x 1 no good seTf z 4 myincf z gt 5 buT z is sTill 4 We don39T have access To 2 inside myincf Prof Fateman CS 164 Lecture 26 18 Expansion in place The Trick is To expand in place The form incf z and replace iT wiTh seTf z z 1 defmacr39o myincfzisT 39seTq z IisT 39 z 1 or39 more succinchy defmacr39o myincfz seTf z z 1 macroexpand 39incf x 9 seTq x x 1 in facT This is whaT The common lisp sysTem does Too macroexpand 39incf x 9 seTq x x 1 Prof Fateman CS 164 Lecture 26 19 What do we expand exactly if is no r always so simple macroexpand 39myincf ar39ef z incf a 9 se rq ar39ef z 3 ar39ef z 3 1 looks OK z3z31 macroexpand 39myincf ar39ef z incf a se rq ar39ef z ian a ar39ef z ian a 1 NOPE za1za21 Here39s a quotbeTTerquot version macroexpand 39incf aref z ian a produces some rhing like This IeT Templ z TempZ ian a Temp3 aref Templ TempZ 1 inTernalseTarray Temp3 Templ Temp2 za1 remp3 Prof Fateman CS 164 Lecture 26 20 Problems with free variables rebound IT can39T do EXACTLY ThaT because look whaT happens here defparameTer Templ 43 macroexpand 39incf aref z Templ 1 IeT Templ z TempZ Templ 1 supposed To be 44 buT is no r Temp3 aref Templ TempZ 1 inTernalseTarray Temp3 Templ Temp2 LAMBDA CALCULUS EXPLAINS WHY THIS IS AN ERROR ABOVE Prof Fateman CS 164 Lecture 26 21 Problems with free variables rebound solved IT can39T do EXACTLY ThaT because look whaT happens here defparameTer Templ 43 macroexpand 39incf ar39ef z Templ 1 ac rually To avoid This kind of problem expansion generaTes new unique labels leT gZ3729 2 923730 Templ 1 923731 ar39ef 2923729 2923730 1 excinvsar39ef 2923731 2923729 9623730 Prof Fateman CS 164 Lecture 22 LOOPS LOOPs don39T have To be compiled because They are macroexpanded away macroexpand 39Ioop f x ian xprinT x block nil Tagbody 2923661 progn f x ian x prin r x 90 2923661 Prof Fateman CS 164 Lecture 26 23 LOOPS a fancier loop macr39o macroexpand 39Ioop for39 i from 1 by 2 To Iim collecT i Ie r i 1 2923666 im declare Type r39eal 9123666 Type real i exclwiThIoopIisTcollecTionhead 923667 923668 block nil Tagbody exclnexTIoop when gt i 2923666 90 excendIoop exclIoopcollecTrplacd 923667 923668 lisT i excloopreallydese rq i i 2 go excnex roop exclendIoop re rurnfrom nil exclIoopcollecTanswer39 923667 Prof Fateman CS 164 Lecture 26 24 SETF SETF is a fairly sub rle kind of program macroexpand 39seTf cadr x 39hello IeT 2923663 cdr x 2923662 39hello excl22invcar 2923663 2923662 macroexpand 39seTf aref cadar x 43 39hello IeT 2923664 cadar x 2923665 39hello excl22invsaref 2923665 2923664 43 Prof Fateman CS 164 Lecture 26 25 IF like IF buT wiTh key words in case you dislike The lack of keywords in an if use if macroexpand 39if 0 Then b c else d e 9 01C 0 pr39ogn b c cond T d e macroexpand 39if 0 Then b c elseif d Then e else f 9 if a pr39ogn b c cond d e T f macroexpand 39doTimes i 10 r39eTval f i 9 396 r i 0 declare Type inTeger39 O 10 0 block nil Tagbody Ta9608 cond gt i 10 reTurnfrom nil progn reTval Tagbody f 0 WW i 1 i 00 Ta0608ml Prof Fateman CS 164 Lecture 26 26 While Unless macroexpand 39while x y block nil Tagbody 923670 progn unless x r eTur n y wha r is unless 90 2923670 macroexpand 39unless x y if no r x pr39ogn nil y nil Prof Fateman CS 164 Lecture 26 27 Push macroexpand 39push x y simple version seTq y cons x y macroexpand 39push x ar ef s rackar39r39ay 1 full version IeT 2923678 x 2923676 sTackarray 2923677 cons 2923678 ar39ef 2923676 1 excl22invsar39ef 2923677 2923676 1 Prof Fateman CS 164 Lecture 26 28 Pop reminder here39s how if works seTf x 39a b c d a b c d P0P X a x 9 b c d could we do pop x This way IeT ans car39 x seTf x cdr39 x ans or in lisp idiom pr ogl car xseTf x Pcdr39 x rof Fateman CS 164 Lecture 26 29 Pop continued The real pop does This macroexpand 39pop x IeT 2923682 ni seTq 923682 x pr ogl car 2923682 seTq 923682 cdr39 2923682 seTq x 2923682 The moral Each objec r musT be evaluaTed aT mosT once Prof Fateman CS 164 Lecture 26 30 How far can macroexpansion be pushed WhaT more can be done 100000 lines of series code originally by Richard WaTers macroexpand 39collecTsum chooseif plusp scan 391 2 3 4 This means essenTially The same as This le r sum 0 reference dolis r i 3912 3 4 sum when plusp i se rq sum sum 0 bu r uses quotseriesquot Macroexpansion of The original Transla res series in ro loops like This Prof Fateman CS 164 Lecture 26 31 Series code as Loop How does i r wor39k ser39ies 39b 39c gt zb c b c self evaluaTing scan lisT 39a 39b 39c gt Z a b c scanr39ange upTo 3 scanrange from 1 by 1 above 4 scan reTurns a series con raining The elemenTs of i rs sequence in order39 op rional Type eg scan 39s rring quotBARquot gt Z B A R Prof Fateman CS 164 Lecture 26 32 Series code as Loop macroexpand 39collecTsum chooseif plusp scan 391 2 3 4 LET ELEMENTS198793 LISTPTR198794 3912 3 4 SUM198769 0 DECLARE TYPE LIST LISTPTR198794 TYPE NUMBER SUM198769 TAGBODY LL198859 IF ENDP LISTPTR198794 GO SERIESEND SETQ ELEMENTS198793 CAR LISTPTR198794 SETQ LISTPTR198794 CDR LISTPTR198794 IF NOT PLUSP ELEMENTS 198793 GO LL198859 SETQ SUM198769 SUM198769 ELEMENTS 198793 60 LL19885P9f 26 33 IO aeman ecure Series code as Loop Series expressions are Transformed inTo loops by pipelining Them The compuTaTion is converTed from a form where enTire series are compuTed one afTer The oTher To a form where The argumenTs To series funcTions are incremenTally referenced compuTed in parallel In The resulTing loop each individual elemenT is compuTed JusT once used and Then discarded before The nexT elemenT is compuTed For This pipelining To be possible a number of resTricTions have To be saTisfied basically requiring ThaT you can fix The amounT of The inpuT pipeline needed To compuTe The firsT elemenT and subsequenT elemenTs of The oquuTquot pipeline Prof Fateman CS 164 Lecture 26 34 Language definition extension Much more in CS 263 264 Vas r Ii rer39a rur39e on language ex rension Techniques Prof Fateman CS 164 Lecture 26 35 TopDown Parsing 65164 Lec rur39e 8 Prof F ateman CS 164 Lecture 8 Announcements Programming Assignment 2 due Thurs Sept 22 Midterm Exam 1 on Thursday Sept 29 In Class ONE handwritten page 2 sides Your handwriting No computer printouts no calculators or cellphones Bring a pencil Prof Fateman CS 164 Lecture 8 2 Review We can specify language syn rax using CFG A par39ser39 will answer whe rher39 G e LG and will build a par39se Tr39ee which is essen rially an AST and pass on To The r39es r of The compiler39 Nex r few lec rur39es How do we answer39 5 e LG and build a par39se rr39ee Af rer39 Tha r from AST To assembly language Prof Fateman CS 164 Lecture 8 3 Lecture Ou rline Implemen ra rion of parsers Two approaches Topdown Bo r romup Today TopDown Easier To unders rand and program manually Nex r Bo r romUp More powerful and used by mos r parser genera rors Prof Fateman CS 164 Lecture 8 4 Intro To TopDown Parsing Terminals are seen in order of appearance in The Token s rr39eam T2 T5 T6 T8 T9 The par39se Tree is cons rr39uc red From The Top Fr39om Ief r To ght Prof Fateman CS 164 Lecture 8 Recursive DescenT Parsing Consider The grammar 310 in TexT Sgt if E Then 5 else 5 S gt begin 5 L S gt pr39inT E L gt end L gt S L E gt num num Prof Fateman CS 164 Lecture 8 Recursive Descent Parsing Parsing defun s case car tokens Sgt if E Then 5 else 5 if 39if S gt begin 5 L eat 39then s S gt prmf E eat 39else L gt end 5 begin eat 39begins1 L 39gt I S L print eat 39print e E gt hum hum otherwise eat 39if cheap error can39t match if Prof Fateman CS 164 Lecture 8 7 Recursive Descent Parsing Parsing L defun 1 case car tokens sgt if E Then 5 else 5 end eat 39end lil eat39l s1 S gt begin 5 L otherwise eat 39end S gt print E L gt and L gt S L E gt num num Prof Fateman CS 164 Lecture 8 8 Recursive Descent Parsing parsing E Sgt if E Then 5 else 5 S gt begin 5 L defun e eat 39num S gt pr39In r E eat L gt and eat 39num L gt S L E gt num num Prof Fateman CS 164 Lecture 8 Recursive Descent Parsing utilities GetToken pop Parse checks for39 emp ry Token lis r defun eath condequa1 h car tokens pop tokenS pop x means setf x cdr x t error quotstuck at squot tokens defun parse tokenss if null tokens quotIt is a sentencequot Prof Fateman CS 164 Lecture 8 10 Recursive Descent Parsing Tests defparameter test 39begin print num num if num num then print num num else print num num end parse test It is a sentence parse if num then num Error stuck at then num Prof Fateman CS 164 Lecture 8 11 This grammar is very easy Why Sgt if E Then 5 else 5 S gt begin 5 L S gt print E L gt and L gt S L E gt num num We can always tell from the first symbol which rule to use if begin prin r end num Prof Fateman CS 164 Lecture 8 12 Recursive Descenf Parsing backtracking Example 2 Consider ano rher grammar E a T E I T Tein r Iin rTE Token s rream is in r5 ian S rar r wi rh Toplevel nonTerminal E Try The rules for E in order Prof Fateman CS 164 Lecture 8 13 Recursive Descem Parsing Backfmcking Tr39yEOaT EZ E TElT T gtInT mTTE Then Try a rule for39 11 E3 Bu r does no r ma rch i npu r Token i n5 Tr39y 11 in r Token ma rches Bu r af rer39 T1 does no r ma rch inpu r Token Tr39y 11 in r T2 This will ma rch in r bu r af rer39 T1 will be unma rched Par39ser39 has exhaus red The choices for39 T1 Back rr ack ro choice for39 E0 in r5 ian Prof Fateman CS 164 Lecture 8 14 Recursive Descent Parsing Backfmcking Follow same s reps as before for T1 And succeed wi rh T1 inf T2 and T2 inf Wi rh The following parse rr39ee E0 Tr ints gtxlt T2 mt2 Prof Fateman CS 164 Lecture 8 15 Recursive DescenT Parsing BackTracking 39 Do we have To backTrack Trick is To look ahead To find The firsT Terminal symbol To figure ouT for sure which rule To Try Indeed backTracking is noT needed if The grammar is suiTable This grammar is suiTable for predicTion SomeTimes you can come up wiTh a beTTer grammar for The same exacT language Prof Fateman CS 164 Lecture 8 16 Lookahead makes back rr39acking unnecessary defun E T case car tokens eat 39 E E gt TE otherwise nil defun T Lookahead resolves rule choice case car tokens eat 39 E eat 39 TgtE int eat 39int T gt int intT case car tokens look beyond int eat IT T gt int T otherwise nil T gt int otherwise eat 39end Prof Fateman CS 164 Lecture 8 17 When Recursive Descem Does Not Work Consider a pr39oduc rion S a S o l sugges rs a program some rhing like defun S S eo r o S will ge r info on infini re loop A lef rr39ecur39sive qr39ommor39 has a nonTerminal S 5 gt 06 for39 some 06 Recursive descen r does no r work in such cases Prof Fateman CS 164 Lecture 8 18 EliminoTion of LefT Recursion Consider The lefTr39ecur39sive grammar S gt 5 on I B S generoTes all sTr39ings sTorTing wiTh o B and followed by a number of 0c oc B are sTrings of Terminals in These examples Con rewriTe using righTrecursion S gt B 539 539 gt on 539 I 8 Prof Fateman CS 164 Lecture 8 19 More Elimination of LeftRecursion Ingener39al gta150 n31ll3m All s rr39ings derived from S s rar39T wi rh one of B1Bm and confinue wi rh several ins rances of 11Xn Rewr39i re as 5 4315 I I Bms39 39 gtoc139 I I anS39Ie Prof Fateman CS 164 Lecture 8 20 General Leff Recursion Thegr39ammar39 gtAocl8 A gtB is also lef rr39ecur39sive even wi rhou r a Ief rr39ecur39sive RULE because gtBoc This lefTr39ecur39sion can also be elimina red Prof Fateman CS 164 Lecture 8 21 Summary of Recursive Descent Simple and general parsing s rra regy LefTrecursion mus r be elimina red firs r bu r Tha r can be done au roma rically No r so opular because common parsergenera ror fools al ow more freedom in making up grammars False repu ra rion of inefficiency If handwri r ren powerful error correc rion and considerable flexibili ry Some rimes Rec Des is used for lexical analysis Balanced commen r delimi rers eg In prac rice back rracking does no r happen ever Prof Fateman CS 164 Lecture 8 22 Predictive Parsers generalizing ookahead Like recursivedescen r bu r parser can predic r which produc rion To use By looking a r The nex r few rokens No back rracking Predic rive parsers accep r LLk grammars L means lef rTorigh rquot scan of i npu r L means ef rmos r deriva rionquot k means predic r based on k rokens of ookaheadquot In prac rice LL1 is used Prof Fateman CS 164 Lecture 8 23 LL1 Languages In recursivedescent for39 each nonTerminal and inpu r Token There may be a choice of pr39oduc rion LL1 means Tha r for39 each nonTerminal and Token There is only one pr39oducTion Can be specified via 2D Tables One dimension for39 current nonTerminal To expand One dimension for39 nex r Token A Table en rr39y con rains one pr39oduc rion Prof Fateman CS 164 Lecture 8 24 Predictive Parsing and Leff Factoring Recall The grammar ETE I T Tein r Iin rTE Hard To predic r because For T rwo productions s rar r wi rh in r For E if is no r clear how To predic r A grammar mus r be Ief rfac rored before use for predic rive parsing Prof Fateman CS 164 Lecture 8 25 LefTFac ror39ing Example Recall The grammar ETE I T Tein r Iin rTIE Fac ror39 ou r common prefixes of pr39oduc rions E a T X X a E I 8 T a E I in r Y Y a T I 8 Prof Fateman CS 164 Lecture 8 26 LL1 Parsing Table Example Lef rfac ror39ed grammar EeTX XaEe TEih fy YaTe The LL1 parsing Table inT TX E E X T inT Y Y T Prof Fateman CS 164 Lecture 8 27 LL1 Parsing Table Example ConT Consider The E inT enTry When currenT nonTerminal is E and nexT inpuT is inT use producTion E a T X This producTion can generaTe an inT in The firsT place Consider The Y enTry When currenT nonTerminal is Y and currenT Token is geT rid of Yquot Y can be followed by only in a derivaTion in which Y 9 8 Prof Fateman CS 164 Lecture 8 28 LL1 Parsing Tables Errors Blank en rries indica re error si rua rions Consider The E en rry There is no way To derive a s rring s rar ring wi rh from nonTerminal Equot Prof Fateman CS 164 Lecture 8 29 Using Parsing Tables Me rhod similar To r39ecur39sive descen r excep r For39 each nonTerminal X We look a r The nex r Token a And chose rhe pr oduc rion shown a r Xa We use a s rack To keep Track of pending non Terminals We rejec r when we encoun rer39 an error s ra re We accep r when we encoun rer39 endof inpu r Prof Fateman CS 164 Lecture 8 30 LL1 Parsing Algorithm initialize stack ltS gt and next repeat case stack of ltX restgt if TXnextinput Y1Yn then stack 9 ltY1 Yn restgt else error 0 ltt restgt ift nextinput then stack 9 ltrestgt else error 0 until stack is empty Prof Fateman CS 164 Lecture 8 31 LL1 Parsing Example S rack Inpu r Ac rion E in r in r T X TX in rin r in ry in rYX in r in r Terminal Y X in r T T X in r Terminal T X in r in r Y in r Y X in r Terminal Y X 8 X 8 ACCEPT Prof Fateman CS 164 Lecture 8 32 Constructing Parsing Tables LL1 languages are Those defined by a parsing Table for The LL1 algori rhm No Table en rry can be mul riply defined We wan r To genera re parsing Tables from CFG Prof Fateman CS 164 Lecture 8 33 ConsTr39ucTing Parsing Tables ConT If A a 0c where in The line A do we place 0c 7 In The column of T where T can sTor39T o sTr39ing derived from 0c 0c T B We say ThoT T e Fir S I39oc In The column of T if 0c is e and T can follow on A s 9 B A 5 We say T e FollowA Prof Fateman CS 164 Lecture 8 34 Computing Fir39sf Sets Definition Fir39s rX T I X a Toe w e I X a e Algor39i rhm ske rch 1 Fir39s r r T 2 e e Fir39s rX if X a e is a pr39oduc rion 3 e e Fir39s rX if X a A1 An and e e Fir39s rAi for39 1 i S n 4 Fir39S l39oc Fir39s rX if X a A1 An 0c and e e Fir39s rAi for39 1 i S n Prof Fateman CS 164 Lecture 8 35 First Sets Example Recall The grammar EeTX XAE8 TEin ry YTe Fir39s rse rs Fir39s r Fir39s rTinT Fir39s r Fir39s r Ein r Fir39s r in r in r Fir39s r X e Fir39s r Fir39s rYe Fir39s r Prof Fateman CS 164 Lecture 8 36 Computing First Sets by Computer Recall The grammar EeTX XEe TEin ry YeTe Fir39s rse rs Fir39S l39 Fir39S l39Tin l39 Fir39s r Fir39s r Ein r Fir39s r in r in r Fir39s r X e Fir39s r Fir39s rYe Fir39s r Prof Fateman CS 164 Lecture 8 37 Compufing Follow Sets Defini rion FollowX r I Sa kBXTS In rui rion If X 9 A B Then Fir39s rB g FollowA and FollowX g FollowB Also if B 9 8 Then FollowX g FollowA If S is The s rar r symbol Then 6 FollowS Prof Fateman CS 164 Lecture 8 38 Computing Follow Sets Cont Algor39i rhm ske rch 1 6 FollowS 2 Fir39s rB e FollowX For39 each production A a 0c X B 3 FollowA FollowX For39 each production A a 0c X B where e e Fir39s rB Prof Fateman CS 164 Lecture 8 39 Follow Sets Example Recall The grammar EeTX XE I 8 TEin ry YT8 Follow se rs Followin r Followin r Follow in r Follow E D Follow X Follow T Follow Follow Y Follow in r Prof Fateman CS 164 Lecture 8 40 Construcfing LL1 Parsing Tables Cons rr39uc r a parsing Table T for39 CFG G For39 each production A a oc in G do For39 each rer39minal r e Fir S I39oc do TA r 0c If 8 e Fir39s r0c for39 each r e FollowA do TA r 0c If 8 e Fir39s roc and 6 FollowA do 39 TM 1 06 Prof Fateman CS 164 Lecture 8 41 Compufing with Grammars Step One Representing a grammar in Lisp defparameter lect8 here s one way IE gt T X T gt E T gt int Y X gt T X gt Y gt T Y gt Prof Fateman CS 164 Lecture 8 Computing some useful information defun rhsr cddr r eg r is E gt T E defun 1hsr first r defun nonterminalsg removeduplicates mapcar 1hs g defun terminalsg setdifference reduce union mapcar rhs g nonterminals g Prof Fateman CS 164 Lecture 8 43 Representing sefs defmacro First x x is a symbol gethash x First defmacro Followx x is a symbol gethash x Follow defmacro addintop1ace stuff setf place union place stuff alternatively if we have just one set like which symbols are nullable we might just assign setf nullable and push x nullable to insert x into that setm same as setf nullable cons x nullable you know this from your lexical analysis program though Prof Fateman CS 164 Lecture 8 44 See rstf011cl for details Compufe Nullable sef Compute nullable set of a grammar The nonterminal symbol X is nullable if X can derive an empty string X gtgt gt empty Given grammar g return a lisp list of symbols that are nullable defun nullablesetg let nullable nil changed t while changed setf changed nil dolist r g for each rule cond if X is already nullable do nothing member lhs r nullable nil for each rule X gt A B C X is nullable if every one of A B C is nullable every lambdazmember z nullablerhs r push lhs r nullable setf changed t sort nullable stringimfsgrg4Eg g e it look nice 45 See rstf011cl for details Compute FIPS I39SB I39 defun firstsetg g is a list of grammar rules let First makehashtable First is a hashtable in addition to a relation Firstx nullable nullableset g changed t for each terminal symbol j Firstj j dolist j terminals g setf First jlist j while changed setf changed nil dolist r g for each rule in the grammar X gt A B C see next slide did this First set or any other First set change in this run setf changed or changed lt setsize length First X exit from loop First Prof Fateman CS 164 Lecture 8 46 defun firstsetg g is a list of grammar rules let First makehashtable First is a hashtable in addition to a relation Firstx nullable nullableset g chantread t for each terminal symbol j Firstj j dolist j terminals g setf First jlist j while changed setf changed nil dolist r g for each rule in the grammar X gt A B C let X lhs r RHS rhs r setsize length First X FirstX FirstX U FirstA cond null RHS nil t addinto First XFirst car RHS while member car RHS nullable pop RHS addinto First XFirst car RHS end of inner while did this First set or any other First set change in this run setf changed or changed lt setsize length First X exit from loop First Prof Fateman CS 164 Lecture 8 47 See rstf011cl for details Followsef In Llsp defun followsetg g is a list of grammar rules let First firstset g Follow makehashtable nullable nullableset g changed t while changed setf changed nil dolist r g for each rule in the grammar X gt A B C D format t quotrule is squot r do RHS rhs rcdr RHS test to end the do loop null RHS Idone let RHS be in succession ABCD BCD C D n D if null RHS nil no change in follow set for erasing rule let A car RHS Blist cdr RHS eg B C D Asize length Follow A ifevery lambda er 2 e B 39st x gt A mu io l39 39iem nt it019555 48 mmore See rstf011cl for details Followsef In LISP continued defun followsetg g is a list of grammar rules I ifevery lambdazmember z nullable Blist X gt A ltnullablegt then anything following X can follow A FollowA FollowA U FollowX addinto Follow AFollow lhs r if Blist not empty FollowA FollowA U FirstB addinto Follow AFirst car Blist while and Blist member car Blist nullable false when Blist if X gt A B C and B is nullable then FollowAFollowA U FirstC pop Blist addinto Follow AFirst car Blist setf changed or changed lt Asize length Follow A Remove the terminal symbols in Follow table are uninteresting Return the hashtable quotFollowquot which has pairs like ltX a bgt mapc lambdavremhash v Follow terminals g printfols Follow print ft gamp h pnj m n1 ie tion 49 Follow for further process1ng Predictive parsing fable pptab lect8 First Sets Follow Sets symbol First symbol Follow E T x Y E int T int x Y int int Prof Fateman CS 164 Lecture 8 50 Predictive parsing fable htZgridpptab lect8 rows E T X Y cols int Prof Fateman CS 164 Lecture 8 E gtTX T gt intY 51 Notes on LL1 Parsing Tables If any en rry is mul riply defined Then G is no r LL1 If G is ambiguous If G is lef r recursive If G is noT lefTfacTored And in oTher cases as well Mos r programming language grammars are no r LL1 bu r could be made so wi rh a li r rle effor r Firs rfollcl builds an LL1 parser About 140 lines of Lisp code Wi rh commen rs debugging code res r da ra The file is abou r 550 lines Prof Fateman CS 164 Lecture 8 52 Review For some grammars languages There is a simple parsing s rra regy based on recursive descen r IT even can be au roma red Predic rive parsing Nex r a more powerful parsing s rra regy Prof Fateman CS 164 Lecture 8 53 Discussion 3 Top Down Parsing 1 LL1 parsing Directions For each of the following grammars7 EOE g a b d Identify the k for which the grammar is LLk parsablei If it s not LL parsable7 then explain why Rewrite the grammar if needed so that it is LL1 parsablei i Provide the LL 1 parse table7 rst using you intuitive understanding of how a predictive parser works7 and then using the more formal method of FIRST and FOLLOW setsi Identify the relationship between the two approaches i Provide the parse stack for some nontrivial inputi E A TE l T T A intlintTlE S A LHa L A LSl S E A TE E A TEle T A FT T A FTle F A l id 5 A iEtSSla 5 A eSle E A b

### 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

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

#### "I made $350 in just two days after posting my first study guide."

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

#### "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."

### Refund Policy

#### STUDYSOUP CANCELLATION 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 support@studysoup.com

#### STUDYSOUP REFUND POLICY

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: support@studysoup.com

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 support@studysoup.com

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.