LL1文法及其分析程序教学课件.ppt

*第五章LL(1)(1)文法•FIRST和FOLLOW集定义和计算•LL(1)•LL(1)(1)文法的改造*自上而下分析算法要点:.–>ABA–>aA|B–>b|ABS–>ABaABA–>aAaaABA–>aAaaaABA–>aAaaaBA–>aaabB–>b*带回溯的自上而下分析S–>ABA–>aA|B–>b|(1)A...S–>AB(2)aA...A–>aA(3)aaA...A–>aA(4)aaaA...A–>aA(5)aaaB...A–>(6)aaabB–>(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生成的是最左推导1向前看一个输入符号(lookahead)预测分析程序的实现技术1递归下降子程序2表驱动分析程序*PL/0语言的EBNF〈程序〉∷=〈分程序〉.〈分程序〉∷=[〈常量说明部分〉][〈变量说明部分〉][〈过程说明部分〉]〈语句〉〈常量说明部分〉∷=CONST〈常量定义部分〉{,〈常量定义〉};〈变量说明部分〉∷=VAR〈标识符〉{,〈标识符〉};〈过程说明部分〉∷=PROCEDURE〈标识符〉〈分程序〉{;〈过程说明部分〉};〈语句〉∷=〈标识符〉:=〈表达式〉|IF〈条件〉then〈语句〉|CALL…|READ…|BEGIN〈语句〉{;〈语句〉}END|WHILE…|…*begin(*statement*)ifsym=identthen(*.*)begingetsym;ifsym=esthengetsymelseerror(13);expression(fsys);endelseifsym=readsymthen(*parsingreadst.*)begingetsym;ifsym<>lparenthenerror(34)elserepeatgetsym;ifsym<>identthenerror(35)elsegetsymuntilsym<>comma;ifsym<>rparenthenerror(33);end*递归下降子程序program–>function_listfunction_list–>functionfunction_list|function–>FUNCidentifier(parameter_list)statementvoidParseFunction(){MatchToken(T_FUNC);ParseIdentifier();MatchToken(T_LPAREN);ParseParameterList();MatchToken(T_RPAREN);ParseStatement();}*voidMatchToken(intexpected){if(lookahead!=expected){printf("syntaxerror\n");exit(0);}else//ifmatch,consumetokenandmoveonlookahead=yylex();}*例:递归子程序实现表达式的语法分析表达式的EBNF〈表达式〉∷=[+|-]〈项〉{(+|-)〈项〉}〈项〉∷=〈因子〉{(*|/)〈因子〉}〈因子〉∷=ident|number|‘(’〈表达式〉‘)’*procedureexpr;beginifsymin[plus,minus]thenbegingetsym;term;endelseterm;whilesymin[plus,minus]dobegingetsym;term;endend;