编译原理 第5章(清华大学).ppt

《编译原理 第5章(清华大学).ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第5章LL(1)文法及其分析程序5.1预测分析程序5.2LL(1)文法FIRST和FOLLOW集定义和计算LL(1)文法定义LL(1)分析程序的生成5.3非LL(1)文法的改造自上而下分析算法要点：.由根向下构造语法树.构造最左推导.推导出的终结符是否与当前输入符匹配SaaabABaAS–>ABA–>aA

2、B–>b

3、bBaaab.SABS–>ABaABA–>aAaaABA–>aAaaaABA–>aAaaaBA–>aaabB–>b带回溯的自上而下分析S–>ABA–>aA

4、B–>b

5、bBaaabb.S(1)A...S–>AB

6、(2)aA...A–>aA(3)aaA...A–>aA(4)aaaA...A–>aA(5)aaaB...A–>(6)aaabB–>baaabb.S(1)A...S–>AB(2)aA...A–>aA(3)aaA...A–>aA(4)aaaA...A–>aA(5)aaaBA–>(6’)aaabBB–>bB(7)aaabbB–>b预测分析程序Predictiveparser无回溯的自顶向下分析程序特征——根据下一个输入符号为当前要处理的非终结符选择产生式要求——文法是LL(1)的第一个L从左到右扫描输入串第二个L生成的

7、是最左推导1向前看一个输入符号（lookahead)预测分析程序的实现技术1递归下降子程序2表驱动分析程序PL/0语言的EBNF〈程序〉∷=〈分程序〉.〈分程序〉∷=[〈常量说明部分〉][〈变量说明部分〉][〈过程说明部分〉]〈语句〉〈常量说明部分〉∷=CONST〈常量定义部分〉{，〈常量定义〉}；〈变量说明部分〉∷=VAR〈标识符〉{，〈标识符〉}；〈过程说明部分〉∷=PROCEDURE〈标识符〉〈分程序〉{；〈过程说明部分〉}；〈语句〉∷=〈标识符〉：=〈表达式〉

8、IF〈条件〉then〈语句〉

9、CALL…

10、READ…

11、BEGIN〈语句〉{；

12、〈语句〉}END

13、WHILE…

14、…begin(*statement*)ifsym=identthen(*parsingass.st.*)begingetsym;ifsym=becomesthengetsymelseerror(13);expression(fsys);endelseifsym=readsymthen(*parsingreadst.*)begingetsym;ifsym<>lparenthenerror(34)elserepeatgetsym;ifsym<>identthenerror(35)elsegetsymuntilsym<

15、>comma;ifsym<>rparenthenerror(33);end递归下降子程序program–>function_listfunction_list–>functionfunction_list

16、function–>FUNCidentifier(parameter_list)statementvoidParseFunction(){MatchToken(T_FUNC);ParseIdentifier();MatchToken(T_LPAREN);ParseParameterList();MatchToken(T_RPAREN);Pa

17、rseStatement();}voidMatchToken(intexpected){if(lookahead!=expected){printf("syntaxerror");exit(0);}else//ifmatch,consumetokenandmoveonlookahead=yylex();}例：递归子程序实现表达式的语法分析表达式的EBNF〈表达式〉∷=[+

18、-]〈项〉{（+

19、-）〈项〉}〈项〉∷=〈因子〉{（*

20、/）〈因子〉}〈因子〉∷=ident

21、number

22、‘（’〈表达式〉‘）’procedureexpr;beg

23、inifsymin[plus,minus]thenbegingetsym;term;endelseterm;whilesymin[plus,minus]dobegingetsym;term;endend;Procedureterm;beginfactor;whilesymin[times,slash]dobegingetsym;factorendend;Procedurefactor;beginifsym=identthengetsymelseifsym=numberthengetsymelseifsym=‘(‘thenbegi

24、ngetsym;expr;ifsym=‘)’thengetsymelseerrorendelseerrorend;表驱动予测分析程序模型Input#总