06-04-recursive-descent-algorithm-annotated

《06-04-recursive-descent-algorithm-annotated》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、CompilersRecursiveDescentAlgorithmAlexAikenRDAlgorithm•LetTOKENbethetypeoftokens–SpecialtokensINT,OPEN,CLOSE,PLUS,TIMES•LettheglobalnextpointtothenextinputtokenAlexAikenRDAlgorithm•Definebooleanfunctionsthatcheckforamatchof:–Agiventokenterminalboolterm(TOKENtok){retur

2、n*next++==tok;}–ThenthproductionofS:boolSn(){…}–TryallproductionsofS:boolS(){…}AlexAikenRDAlgorithm•ForproductionETboolE(){returnT();}1•ForproductionET+EboolE(){returnT()&&term(PLUS)&&E();}2•ForallproductionsofE(withbacktracking)boolE(){TOKEN*save=next;return(next=s

3、ave,E())1

4、

5、(next=save,E());}2AlexAikenRDAlgorithm•Functionsfornon-terminalTboolT(){returnterm(INT);}1boolT(){returnterm(INT)&&term(TIMES)&&T();}2boolT(){returnterm(OPEN)&&E()&&term(CLOSE);}3boolT(){TOKEN*save=next;return(next=save,T())1

6、

7、(next=save,T())2

8、

9、(next=save,T

10、());}3AlexAikenRDAlgorithm•Tostarttheparser–Initializenexttopointtofirsttoken–InvokeE()•EasytoimplementbyhandAlexAikenRDAlgorithmET

11、T+E(int)Tint

12、int*T

13、(E)boolterm(TOKENtok){return*next++==tok;}boolE1(){returnT();}boolE2(){returnT()&&term(PLUS)&&E();}boolE(){TOKEN*sa

14、ve=next;return(next=save,E1())

15、

16、(next=save,E2());}boolT1(){returnterm(INT);}boolT2(){returnterm(INT)&&term(TIMES)&&T();}boolT3(){returnterm(OPEN)&&E()&&term(CLOSE);}boolT(){TOKEN*save=next;return(next=save,T1())

17、

18、(next=save,T2())

19、

20、(next=save,T3());}AlexAikenWhichlines

21、areincorrectintheRDAlgorithmrecursivedescentimplementationofthisgrammar?1boolterm(TOKENtok){return*next++==tok;}EE’

22、E’+idE’-E’

23、id

24、(E)2boolE1(){returnE’();}3boolE2(){returnE’()&&term(PLUS)&&term(ID);}4boolE(){Line35TOKEN*save=next;6return(next=save,E1())&&(next=save,

25、E2());7}Line58boolE’1(){returnterm(MINUS)&&E’();}9boolE’2(){returnterm(ID);}10boolE’3(){returnterm(OPEN)&&E()&&term(CLOSE);}Line611boolE’(){12TOKEN*next=save;return(next=save,T1())13

26、

27、(next=save,T2())Line1214

28、

29、(next=save,T3());15}