第09章自上而下的语法分析详解.pptx

1 第9章 自上而下的语法分析 9.1 引言 9.1.1 语法分析的任务 语法分析对源程序经过词法分析后转换成的符号串（即单词符号的序列），按文法规则进行判断，对能构成正确句子的符号串，给出相应的语法树；对不能构成正确句子的符号串，判定其出现了语法错误，并作出适当的处理。 2 语法分析程序的功能 3 9.1.2 语法分析的分类 (1) 自上而下的语法分析 对给定的上下文无关文法G(Vt,Vn,S,P)及符号串ω（ω∈Vt*），按照以下方法判断ω是否是文法G的一个合法句子： 从根结点S开始，根据最左推导，看能否向下构造一棵语法树，使得该语法树的边缘正好是ω。 4 (2) 自下而上的语法分析 对给定的上下文无关文法G(Vt,Vn,S,P)及符号串ω（ω∈Vt*），按照以下方法判断ω是否是文法G的一个合法句子： 从语法树边缘ω开始，根据最左规约，看能否向上构造一棵语法树，使得该语法树的根结点正好是S。 5 9.1.3 语法分析的方法 自上而下的语法分析方法 回溯分析法 递归下降分析法 预测分析法 自下而上的语法分析方法 算符优先分析法 LR分析法 6 9.2.1 回溯分析实例 实例1. 文法G(S)： S → xAy A → ab│a 对输入串 xay 的分析过程为 9.2 回溯分析法 7 8 实例2. 文法G(S)： S→Sa S→b 对输入串 baa 的分析过程为 9 10 9.2.2 引起回溯的原因 (1) 存在公共左因子 A→1 | 2 (2) 存在左递归 直接左递归：A→Aα 间接左递归：A →Bα和 B→A 11 当选用一个候选式来试探与输入串的匹配可能时，很可能会遇到匹配失败的情况，这时需回溯到这一次试探前的现状，包括注销已生长的子树，输入串的待匹配指针指针回退到失败前的位置，以便选取其它的候选式。 12 回溯分析法实际上是一种试探的方法，其分析效率是非常低的。特别是当匹配失败发生在多级试探后，逐级回溯的开销是令人难以忍受的。 为避免回溯，可对文法进行等价改造，消除公共左因子和左递归。 13 9.2.3 公共左因子的消除 将A→1 | 2 | δ 改写为 A→B |δ B→ 1| 2 一般形式： 将A→1 | 2 | ... | m | δ1 | δ2 | ... | δn 改写为 A→B | δ1 | δ2 | ... | δn B→ 1| 2| ... |m 14 例如文法 S→xAy A→ab│a 可改写为 S→xAy A→aB B→b│ 15 9.2.4 左递归的消除 (1)直接左递归的消除 将P→Pα|β 改写为 P→P’ P’→αP’│ε 一般形式： 将A→A1 | A2 | … | Am | 1 | 2 | … | n （I ε，j不以A开头） 改写为 A→1P’│ 2P’│. . .│ nP’ P’ →1P’│2P’│. . .│mP’│ε 16 (2)间接左递归的消除 对存在间接左递归的文法G： Ax → Ay… … Ay → Az… … Az → Ax… 按以下算法消除间接左递归： 17 消除间接左递归算法 1) 将文法G的所有非终结符按任一给定的顺序排列，设为A1，A2，…，An 2) 改造产生式，消除左递归 for i:=2 to n do for j:=1 to i-1 do 消除形如AiAj的产生式； 3) 去掉无效的符号和产生式 18 消除形如AiAj的产生式的方法 1) 将 AiAj 改写为 Ai1 | 2 | … | k （Aj1 | 2 | … | k是Aj的所有产生式） 2) 消除新引入的直接左递归。 19 例子：消除间接左递归 S→Qc│c Q→Rb│b R→Sa│a 文法产生的语言：{ c, bc, abc, cabc, bcabc, abcabc, cabcabc, bcabcabc, abcabcabc, …} 20 按R、Q、S排列，改造文法 R→Sa│a Q→Sab│ab│b S→Sabc│abc │bc│c 消除S中的直接左递归 S→abcS’│bcS’│cS’ S’→abcS’│ 文法产生的语言： { c, bc, abc, cabc, …} R→Sa│a Q→Rb│b S→Qc│c 21 按S、Q、R排列，改造文法 S→Qc│c Q→Rb│b R→