第五章LL(1文法及其分析程序.ppt

第五章 LL(1)文法及其分析程序 5.1 预测分析程序 5.2 LL(1)文法 ? FIRST和FOLLOW集定义和计? ?????? 算 ? LL(1) 文法定义 ? LL(1)分析程序的生成 5.3 非LL(1)文法的改造 自上而下分析算法 要点： .由根向下构造语法树 .构造最左推导 .推导出的终结符是否与当前输入符匹配 S aaab A B a A S – AB A – aA | ? B – b | bB aaab. S ?AB S – AB ?aAB A – aA ?aaAB A – aA ?aaaAB A – aA ?aaa ? B A – ? ?aaab B – b 带回溯的自上而下分析 S – AB A – aA | ? B – b | bB a a a b b. S (1) ?A... S – AB (2) ?aA... A – aA (3) ?aaA... A – aA (4) ?aaaA... A – aA (5) ?aaa ? B... A – ? (6) ?aaab B – b aaabb. S (1) ?A... S – AB (2) ?aA... A – aA (3) ?aaA... A – aA (4) ?aaaA... A – aA (5) ?aaa ? B A – ? (6’) ?aaa b B B – bB (7) ?aaabb B – b 预测分析程序Predictive parser无回溯的自顶向下分析程序 特征——根据下一个输入符号为当前要处理 的非终结符选择产生式 要求——文法是LL(1)的 第一个L 从左到右扫描输入串 第二个L 生成的是最左推导 1 向前看一个输入符号（lookahead) 预测分析程序的实现技术 1 递归下降子程序 2 表驱动分析程序 PL/0语言的EBNF 〈程序〉∷=〈分程序〉. 〈分程序〉∷=[〈常量说明部分〉][〈变量说明部 分〉][〈过程说明部分〉]〈语句〉 〈常量说明部分〉∷=CONST〈常量定义部分〉{，〈常量 定义〉}； 〈变量说明部分〉∷=VAR〈标识符〉{，〈标识符〉}； 〈过程说明部分〉∷= PROCEDURE 〈标识符〉〈分程序〉 {；〈过程说明部分〉}； 〈语句〉∷= 〈标识符〉：=〈表达式〉 |IF 〈条件〉 then〈语句〉|CALL…|READ…|BEGIN 〈语句〉{；〈语句〉} END|WHILE…|… begin(*statement*) if sym=ident then (*parsing ass.st.*) begin getsym; if sym=becomes then getsym else error(13); expression(fsys); end else if sym=readsym then (* parsing read st.*) begin getsym; if symlparen then error(34) else repeat getsym; if sym ident then error(35) else getsym until symcomma; if symrparen then error(33); end 递归下降子程序 program – function_list function_list – function function_list | ? function – FUNC identifier ( parameter_list ) statement void ParseFunction() { MatchToken(T_FUNC); ParseIdentifier(); MatchToken(T_LPAREN); ParseParameterList(); MatchToken(T_RPAREN); ParseStateme