欢迎来到天天文库
浏览记录
ID:51498534
大小:284.50 KB
页数:48页
时间:2020-03-25
《编译原理 第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.SABS–>ABaABA–>aAaaABA–>aAaaaABA–>aAaaaBA–>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)aaaB...A–>(6)aaabB–>baaabb.S(1)A...S–>AB(2)aA...A–>aA(3)aaA...A–>aA(4)aaaA...A–>aA(5)aaaBA–>(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#总
此文档下载收益归作者所有