哈工大编译原理4-2课件.ppt

第四章 语法分析;4.3 自底向上; 移入归约分析法为输入串构造分析树时从叶节占点（底端）开始，向根节点（顶端）前进。;句子abbde的归约过程(最左归约）;存在的问题： 在第 步归约时，;a b b d e;二、句柄; S;定义4.2 直接短语 若A→ β为一产生式，则称β为相对于A的、句型αβw 的直接短语;在第②步归约中，相对于句型aAbde来说，Ab是句柄，其上一级句型为aAde；而b根本就不是短语，因为不存在上一级句型aAAde;例：证明T/（E-T）*F+i是句型，并指出其所包含的短语、直接短语和句柄;考虑文法4.1： S→aABe A→Ab A→ b B→d abbde的最右推导和最左归约如左;E;三、用栈实现移进归约分析;考虑文法4.2： E→E+T|T T→T*F|F F→(E)|id id1*id2+id3的分析 过程如下： ;步骤;移进：把下一个输入符号移进栈;四、句柄的识别;4.3.1 算符优先分析 ;② a b:当且仅当存在产生式A→…aT…， 且T=b…，或T=Rb…，称a后 于b归约;注意： ? 1. 算术关系“”,“=”和“”与优先关系具有十分不同的性质。例如，a＜·b并不一定意味着b·a，;4、算符优先文法;二、算符优先关系（矩阵）;定义4. 6 FIRSTVT和LASTVT集;LASTVT(E)={+，-，*，/，)，I, ↑ } LASTVT(T)={*，/，)，i , ↑} LASTVT(F)={)，i , ↑} LASTVT(P)={)，i }; 求FIRSTVT和LASTVT集的算法;⑵求FIRSTVT算法;PROCEDURE INSERT（P，a) IF F[P,a]=0 THEN BEGIN F[P,a]=1; PUSH(P,a); END;For 每个a∈VT, P∈VN do F[P,a]=0 For 每个P→a...或P→Qa…的产生式 do INSERT [P,a]; WHILE 栈不为空 DO POP （Q，a）； FOR 每个P→Q…产生式 DO INSERT(P,a); END WHILE;上述算法的运行结果为数组F，从它可以得到任何非终结符P的FIRSTVT;;算法4.3 构造算符优先关系的算法;; S →（A） ;表4.1 文法4.2对应的算符优先矩阵;三、算符优先算法;/*a为栈顶终结符，b为当输入符号*/? ?? ?if (a??b) or (a?b) then begin /* 移进* / ?????? ????? 把b推入栈中； ????????????? ip指向下一符号 ?end if a·?b then /* 归约* / ???? ????repeat ?????????????从栈中弹出符号 ????? ????until 栈顶终结符号??最近弹出的终结符号 else error; 栈 关系 输入 动作 序号;不难看出，算符优先分析过程中，归约的不是真正的句柄，也不是规范归约。;E;句柄和素短语的区别： G[E]:E?E+T?T T ?T*F?F F ?(E) ?id;相对于句型F+F*id3;练习：有文法G（S）： S →（L）|aS|a L →L ,S|S 1、??画出句型 (S,(a，S))的语法树 2、求出所有短语、直接短语、句柄和最左素短语 ;有文法G（R）： R→i|(T) T→T,R|R 试构造其算符优先分析表;4.3.2 优先函数? 为了节约存储空间和便于执行比较运算?，用两个优先函数f和g来表示优先关系，它们是从终结符映射到整数的函数。对于终结符号a和b选择f和g,使之满足： 1．当a＜·b时, f(a)＜g(b); ????2. 当a = b时, f(a)= g(b); ???3. 当a · b时, f(a) g(b)。