编译原理5.1自下而上语法分析概要.ppt

由数组布尔元素值知文法中每个非终结符的FIRSTVT(A)集合为： FIRSTVT(E`)＝｛＃｝ FIRSTVT(E)＝｛+，*，↑，(，i｝ FIRSTVT(T)＝｛*，↑，(，i｝ FIRSTVT(F)＝｛ ↑，(，i ｝ FIRSTVT(P)＝｛(，i｝　　 5 构造优先表方法 ① 对形如 P-…ab…和形如P-…aQb…，有a b； ②对形如 P-…aR…，而b∈FIRSTVT(R)，有a b； ③对形如 P-…Rb…，而a∈LASTVT(R)，有a b； ④对文法开始符号S，有# FIRSTVT(S)，LASTVT(S) #， 且对 #S#，有# #。 Ch5 语法分析 5.2 算符优先分析法 5.2.2 算符优先分析与分析器 算法5.3 构造文法G的优先关系表 输入：文法G及G的FIRSTVT(G)和LASTVT(G) 输出：文法G的优先关系表 方法： for G中的每条规则 P→ｘ1ｘ2…ｘn { ① 置相邻的两个终结符ｘi和ｘi+1(或只隔一个 非终结符)为“?”，即ｘi?ｘi+1； ② if ｘi∈ＶT而ｘi+1∈ＶN 则 for FIRSTVT(Xi+1) 中的每个a置ｘi?a； ③ if ｘi∈ＶN而ｘi+1∈ＶT 则 for LASTVT(ｘi) 中的每个a置a ?ｘi+1。 } P →… aR… 且 FIRSTVT(R) P →… Ra… 且 LASTVT(R) 上例的算符优先关系表 = # ) = ( i ↑ * + # ) ( i ↑ * + 6 算符优先分析算法的设计 定义 1）文法G，开始符号S，若S α β δ，如果 S αβδ 且 A β， 则称β是句型αβδ的一个短语。 2）所谓素短语是指这样一个短语,它至少含有一个终结符,并且,除自身之外,不再含任何更小的素短语。 3）句型最左边的那个素短语叫最左素短语。 Ch5 语法分析 5.2 算符优先分析法 5.2.3 算符优先分析法理论探讨 例5.7 设文法G(Ｅ) E→ E＋T│T T→ T*F│F F→ (E)│i 考察句型 T＋T*F＋i 给出它的素短语及最左素短 语。 E F T 最左 素短语 Ch5 语法分析 5.2 算符优先分析法 5.2.3 算符优先分析法理论探讨 E E + T + T T * F E T F i 素短语 最左素短语 句型 T+T*F+i 的语法树 但不是素短语 Ch5 语法分析 5.2 算符优先分析法 5.2.3 算符优先分析法理论探讨 句型 T+i*i+i 的语法树 最左素短语 E E + T E + T T T F i F i * F i 素短语 i*i ? T ? 是短语 最左素短语满足以下条件的最左子串 Njaj… NiaiNi+1， aj-1 aj aj aj+1 , … , ai-1 ai ai ai+1 定理 算符优先文法的句型一般形式： #N1a1N2a2…NnanNn+1# 其中，ai ∈VT，Ni ∈VN|^ 算法分析： 也即： aj-1 Nj aj … … ai Ni+1 ai+1 2 例5.5 i1 *( i2 + i3) # ∵# i1 * ( i2 + i3 ) # ∴i1，i2，i3是素短语；i1是最左素短语。 Ch5 语法分析 5.2 算符优先分析法 5.2.3 算符优先分析法理论探讨 算法5.4 算符优先分析器的总控程序。 ① 初始化。将“＃”压入栈，栈顶指针p＝1； ② 当前输入符号=a； ③ 比较符号栈顶项 b(b∈VT)与a的优先级； 若 b?a或 b= a转④ ； 若 b ?a转⑤ ； 否则 error; ④ a入栈( p++)转② ； //还没形成最左素短语，移进 ⑤ 在栈中寻找满足bn+1?bn＝bn-1…?b1?a的bn， 即寻找最左素短语的头； ⑥ 将 bn bn-1… b1及有关的非终结符归约到Ｑ，Ｑ 入栈；若栈中为＃S与a＝“＃”，则end，否则 (a)=栈顶转② ； Ch5 语法分析 5.2 算符优先分析法 5.2.3 算符优先分析法理论探讨 例5.9 设有文法G(Z) 和输入串b (aa)b Z