第五章LL(1)文法及其分析程序 5.1预测分析程序 5.2LL(1)文法 FIRST和FOL0W集定义和计 算 LL(1)文法定义 L(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|e 由根向下构造语法树 B→>b|bB 构造最左推导 aaab 推导出的终结符是否与s 当前输入符匹配 →AB S→>AB →aAB A→>aA S aaab →aaAB A→>aA → aaaAB A→>aA → aaa e b A→>g →aaab B→>b
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|ε B->bbB (1)→A S→>AB aa ab b (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 eb A->E 4)→aaaA..A→>aA (6)→ aaabb B->bB (5)→aaaεB..A→>E (7)→ aaabb B=>b (6)→aaab B→>b
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 预测分析程序Predictive parser 无回溯的自顶向下分析程序 特征——根据下一个输入符号为当前要处理 的非终结符选择产生式 要求——文法是LL(1)的 第一个L 从左到右扫描输入串 第二个L 生成的是最左推导 1 向前看一个输入符号（lookahead) 预测分析程序的实现技术 1 递归下降子程序 2 表驱动分析程序
PL/0语言的EBNF ◆〈程序〉∴=〈分程序 ◇〈分程序〉∷三[〈常量说明部分〉][〈变量说明部 分〉][〈过程说明部分〉]〈语句〉 ◇〈常量说明部分〉∷= CONST〈常量定义部分〉{,〈常 量定义〉}; ◇〈变量说明部分〉∷=VAR〈标识符〉{,〈标识符〉}; ◆〈过程说明部分〉∴= PROCEDURE〈标识符〉〈分程序 ;〈过程说明部分〉}; 〈语句〉∷=〈标识符〉:=〈表达式〉|IF〈条件〉 then〈语句〉|CALL|READ| BEGIN〈语句〉{;〈语 句〉}END|WILE
5 PL/0语言的EBNF ❖〈程序〉∷=〈分程序〉. ❖〈分程序〉∷=[〈常量说明部分〉][〈变量说明部 分〉][〈过程说明部分〉]〈语句〉 ❖〈常量说明部分〉∷=CONST〈常量定义部分〉{，〈常 量 定义〉}； ❖〈变量说明部分〉∷=VAR〈标识符〉{，〈标识符〉}； ❖〈过程说明部分〉∷= PROCEDURE 〈标识符〉〈分程序〉 {；〈过程说明部分〉}； ❖〈语句〉∷= 〈标识符〉：=〈表达式〉 |IF 〈条件〉 then〈语句〉|CALL…|READ…|BEGIN 〈语句〉{；〈语 句〉} END|WHILE…|…