吉大编译课件编译器开发.ppt

《吉大编译课件编译器开发.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、编译程序的面向对象设计与实现Dr.ZhengXiaojuanAssociateProfessorSoftwareCollegeofNortheastNormalUniversityApril.20091阶段三：语法分析器开发2项目需求读入词法分析的输出结果token序列；对token序列进行语法分析生成语法正确的与源程序结构相对应的语法分析树；能够指出语法错误所在位置。3一、编译原理内容4语法分析程序的功能5所需编译知识关联图DevelopaParserSyntaxdefinitionbasingonContextFreeGramma

2、rusingimplementTop-downBottom-up√√6Top-downparsingSyntaxdefinitionbasingonCFGusingcheckpreconditionPredict(A)first()follow(A)YesRecursive-descentLL(1)Implement所需编译知识关联图7一、ContextFreeGrammar(CFG)定义为四元组(VT,VN,S,P)VT是有限的终极符集合VN是有限的非终极符集合S是开始符，SVNP是产生式的集合，且具有下面的形式：AX1X

3、2…Xn其中AVN，Xi(VTVN)，右部可空。8二、Top-downparsing自顶向下语法分析方法的前提条件G=(VT,VN,S,P)ForanyAVN,ForanytwoproductionsofA,Predict(A1)Predict(A2)=(同一个非终极符的任意两个产生式的predict集合互不相交)这个条件保证:针对当前的符号和当前的非终极符,可以选择唯一的产生式来进行推导;9三、GrammarTransformation消除公共前缀(leftfactoring)公共前缀A1

4、…

5、n

6、1

7、

8、…

9、m提取公因子AA’

10、1

11、…

12、mA’1

13、…

14、n10消除左递归(leftrecursion)直接左递归:AA(1

15、…

16、n)

17、1

18、…

19、m消除方法:A(1

20、…

21、m)A’A’(1

22、…

23、n)A’

24、11消除左递归(leftrecursion)间接左递归:消除方法:Pre-conditionsAlgorithmSAbASa

25、b1:S2:AAAba

26、bAbA’A’baA’

27、12四、ThreeImportantSetsFirstSet(first集)forastringwithnon-termi

28、nalandterminalsymbols;First()FollowSet(follow集)foranon-terminalsymbolA;Follow(A)PredictSet(预测集)foraproduction;Predict(A)131FirstSet(first集)Definition:First()={a

29、*a,aVT},if*thenFirst()=First(){}HowtocalculateFirst()?=,First()={}=a,aVT,First()={a}=

30、A,AVN,First()=First(A)=X1X2……Xi-1Xi……Xn14S={A

31、A*,AVN}Foreachterminalsymbola,First(a)={a}ForeachsymbolX,calculateFirst(X)VN={A1,…,An},calculateFirst(Ai)初始化,First(Ai)={};fori=1ton对于Ai的每个产生式,-ifAi,First(Ai)=First(Ai){};-ifAiY1….Ym,{Y1,….,Ym}S,First(Ai)=First(

32、Ai)First(Y1)…..First(Ym)-ifAiY1….Ym,{Y1,….,Yj-1}S,YjSFirst(Ai)={First(Ai){First(Y1)…..First(Yj-1)-{}}First(Yj)(3)Repeat(2)until每个First(Ai)没有变化(收敛).15ExampleP:(1)ETE’(2)E’+TE’(3)E’(4)TFT’(5)T’*FT’(6)T’(7)F(E)(8)Fi(9)FnS={E’,T’}E{i,n,(}E’{+,}T{i,

33、n,(}T’{*,}F{i,n,(}162FollowSet(follow集)HowtocalculateFollow(A),AVN(1)初始化,AVN,Follow(A)={}(2)Follow(S)={#}(