第五章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…|…