清华大学：《编译原理》课程教学资源（PPT课件）第五章 LL（1）文法及其分析程序

第五章LL（1)文法及其分析程序 5.1预测分析程序 5.2LL(1)文法 ● FIRST和FOLLOW集定义和计 算 LL(1) 文法定义 ● LL(1)分析程序的生成 5.3 非LL(1)文法的改造

1 第五章 LL(1)文法及其分析程序 5.1 预测分析程序 5.2 LL(1)文法 • FIRST和FOLLOW集定义和计 算 • LL(1) 文法定义 • LL(1)分析程序的生成 5.3 非LL(1)文法的改造

自上而下分析算法 要点： S->AB A->aA|ε .由根向下构造语法树 B->b|bB .构造最左推导 aaab. 推导出的终结符是否与 S 当前输入符匹配 →AB S->AB →aAB A->aA aaab →aaAB A->aA →aaaAB A->aA →aaa s B A->8 →aaab B->b 2

2 自上而下分析算法 要点： .由根向下构造语法树 .构造最左推导 .推导出的终结符是否与 当前输入符匹配 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 aaabb. A->aAε S B->bbB (1)→A. S->AB aa ab b. S (2)→aA. A->aA (1)→A. S->AB (3)→aaA.. A->aA (2)→aA. A->aA (4)→aaaA.. A->aA (3)→aaA.. A->aA (5)→aaaεB A->8 (4)→aaaA.A->aA (6)→aaa bB B->bB (5)→aaaεB.A->e (7)→aaabb B->b (6)→aaab B->b 3

3 带回溯的自上而下分析 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 无回溯的自顶向下分析程序 特征一一根据下一个输入符号为当前要处理 的非终结符选择产生式 要求一一文法是L(1)的 第一个L从左到右扫描输入串 第二个L生成的是最左推导 1向前看一个输入符号(lookahead) 预测分析程序的实现技术 1递归下降子程序 2表驱动分析程序 4

4 预测分析程序Predictive parser 无回溯的自顶向下分析程序 特征——根据下一个输入符号为当前要处理 的非终结符选择产生式 要求——文法是LL(1)的 第一个L 从左到右扫描输入串 第二个L 生成的是最左推导 1 向前看一个输入符号（lookahead) 预测分析程序的实现技术 1 递归下降子程序 2 表驱动分析程序

PL/O语言的EBNF 冬〈程序〉：=〈分程序〉 冬〈分程序〉：：=[〈常量说明部分〉][（变量说明部 分〉][过程说明部分〉]〈语句〉 〈常量说明部分〉：=C0NST〈常量定义部分〉{，〈常 量定义〉}； 〈变量说明部分)：=VAR〈标识符){，〈标识符〉}； 〈过程说明部分〉：=PROCEDURE 〈标识符〉 (分程序) 〈过程说明部分〉}； 冬〈语句〉= 〈标识符》：=〈表达式)IF〈条件) then〈语句〉|CALL..READ..BEGIN〈语句〉{；〈语 句〉}END WHILE... 5

5 PL/0语言的EBNF ❖〈程序〉∷=〈分程序〉. ❖〈分程序〉∷=[〈常量说明部分〉][〈变量说明部 分〉][〈过程说明部分〉]〈语句〉 ❖〈常量说明部分〉∷=CONST〈常量定义部分〉{，〈常 量 定义〉}； ❖〈变量说明部分〉∷=VAR〈标识符〉{，〈标识符〉}； ❖〈过程说明部分〉∷= PROCEDURE 〈标识符〉〈分程序〉 {；〈过程说明部分〉}； ❖〈语句〉∷= 〈标识符〉：=〈表达式〉 |IF 〈条件〉 then〈语句〉|CALL…|READ…|BEGIN 〈语句〉{；〈语 句〉} END|WHILE…|…

begin (*statement*) begin if sym=ident getsym; then (*parsing ass.st.* if sym<>lparen begin then error(34) getsym; else if sym=becomes repeat then getsym getsym; else error(13); if sym comma; then if sym<>rparen (parsing read st.*) then error (33); end 6

6 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 sym<>lparen then error(34) else repeat getsym; if sym <> ident then error(35) else getsym until sym<>comma; if sym<>rparen then error(33); end

递归下降子程序 program -function_list function list -functionfunction list s function->FUNC identifier parameter_list statement void ParseFunction ( { MatchToken (T FUNC); ParseIdentifier(); MatchToken (T LPAREN); ParseParameterList () MatchToken (T RPAREN); Parsestatement ()

7 递归下降子程序 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); ParseStatement(); }

void MatchToken (int expected) { if (lookahead !expected){ printf("syntax error \n"); exit（0); else /if match,consume token and move on lookahead yylex(); } 8

8 void MatchToken(int expected) { if (lookahead != expected) { printf("syntax error \n"); exit(0); } else // if match, consume token and move on lookahead = yylex(); }

例：递归子程序实现 表达式的语法分析 表达式的EBNF (表达式〉：=[+-]〈项〉{（+-)〈项〉} (项〉：=〈因子〉{(*/)〈因子〉} 〈因子〉：=ident number(’〈表达式》 )’ 9

9 例：递归子程序实现 表达式的语法分析 表达式的EBNF 〈表达式〉∷=[+|-]〈项〉{（+|-）〈项〉} 〈项〉∷=〈因子〉{（*|/）〈因子〉} 〈因子〉∷=ident|number|‘（’〈表达式〉 ‘）’

procedure expr; begin if sym in plus,minus then begin getsym;term; end else term; while sym in [plus,minus]do begin getsym;term; end end; 10

10 procedure expr; begin if sym in [ plus, minus ] then begin getsym; term; end else term; while sym in [plus, minus] do begin getsym; term; end end;