清华大学：《编译原理》课程教学资源_第六章 补充算符优先分析

第6章补充算符优先分析 算符优先文法的定义 算符优先关系表的构造 算符优先分析算法 算符优先分析法的局限性

1 第6章 补充 算符优先分析 算符优先文法的定义 算符优先关系表的构造 算符优先分析算法 算符优先分析法的局限性

算符优先分析 自下而上分析算法模型--移进归约 算符优先分析不是规范归约 算符优先分析的可归约串是句型的最左素短语 定义cfg(上下文无关文法)G的句型的素短语 是一个短语,它至少包含一个终结符,且除自 身外不再包含其他素短语。处于句型最左边的 素短语为最左素短语 文法G[S] s→aA且A称是句型aβ相对于非终 结符A的短语

2 算符优先分析 • 自下而上分析算法 模型----移进归约 • 算符优先分析不是规范归约 算符优先分析的可归约 串是句型的最左素短语 定义 cfg（上下文无关文法） G 的句型的素短语 是一个短语，它至少包含一个终结符，且除自 身外不再包含其他素短语。处于句型最左边的 素短语为最左素短语 文法G[S] S αAδ且A 则称是句型α  δ相对于非终 结符A的短语 *   +

文法GE] 句型T+TF (1)E→E+T 2)E→T 其短语有 (3)T-T*F T+TF+ (4)T→F T+TF (5)F→P个F|P (6)P→(E) TT☆F (7)P TF E 素短语为:TF,i E 最左素短语为:TF E+T 句型T+T+的素短语为:T+T,i 句型T+T+F的素短语为:T+T

3 文法G[E]： (1) E→E+T (2) E→T (3) T→T*F (4) T→F (5) F→PF|P (6) P→(E) (7) P→i 句型T+T*F+i 其短语有： T+T*F+i T+T*F T T*F i E E + T E + T F T T * F i 最左素短语为：T*F 句型T+T+F的素短语为：T+T E + + T F E 句型T+T+i的素短语为：T+T, i 素短语为：T*F， i E T T i

分析程序模型 输入串# 总控程序 输出 # 将符优先关系表产生式

4 分析程序模型 总控程序 算符优先关系表 产生式 输入串# # 输出

如何确定算符优先吳系? 文法GE]:E→EEE-E|EEEE|ETE|E)i 人为确定: (1)的优先级最高 (1)个优先级次于i,右结合 (2)*和/优先级次之,左结合 《《《《 《《《 《《《《《《 (3)+和-优先级最低,左结合 (4)括号‘()的优先级大于括号外 的运算符,小于括号内的运算符 内括号的优先性大于外括号 (5)#的优先性低于与其相邻的算符 算符优先吴系表

5 如何确定算符优先关系？ 人为确定： （1）i的优先级最高 （1） 优先级次于i，右结合 （2）*和/优先级次之，左结合 （3）+和-优先级最低，左结合 （4）括号‘(’ , ‘)’的优先级大于括号外 的运算符，小于括号内的运算符， 内括号的优先性大于外括号 （5）#的优先性低于与其相邻的算符 文法G[E]：E→E+E|E-E|E*E|E/E|EE|(E)|i + - * /  ( ) i # + > > - > > * > > > > / > > > >  > > > > ( > > > > > > i > > > > > > > # < < < < < < < = 算符优先关系表

算符优先文法的定蚁 定义:如果不含空产生式的上下文无关文法G中没 有形如A→BC…的产生式,其中B,C∈VN则称 G为算符文法(OG)。 例1GE]:E→E+EE-| E"EIE/EIETE|Eli 例2G[E]:E→E+TTr T→T*F|F F→P↑F|P P→(E)i 性质1:在算符文法中任何句型都不包含两个相邻的非终结符 性质2:如Ab或bA出现在算符文法的句型中,其中 A∈VN,b∈V,则中任何含b的短语必含有A

6 算符优先文法的定义 • 定义：如果不含空产生式的上下文无关文法 G 中没 有形如 A→…BC…的产生式，其中B，C∈VN 则称 G 为算符文法（OG）。 例1 G[E]：E→E+E|E-|E*E|E/E|EE|(E)|i 例2 G’[E]: E→E＋T|T T→T*F|F F→P↑F｜P P→(E)|i 性质1：在算符文法中任何句型都不包含两个相邻的非终结符. 性质2：如 Ab 或 bA 出现在算符文法的 句型  中，其中 A∈VN，b∈VT， 则  中任何 含 b 的短语必含有A

算符优先关系 在OG中定义(算符优先关系) a=bG中有形如:A→…ab 或A→>…aBb.的产生式。 a…aB.的产生式, 而B→b….或BCb a>bG中有形如:A→>.Bb.的产生 式而B…或B C 规定若S+a.或S→Ca.则#

7 算符优先关系 在OG中 定义 （算符优先关系） a = b G中有形如：A→…ab… 或A → …aBb...的产生式。 a b G中有形如: A → …Bb…的产生 式,而 B …a 或 B … aC 规定 若 S a…或 S Ca… 则 # #  +  +  +  +  +  +  +  +

在OG文法G中,若任意两个终结符间至多有 种算符优先关系存在,则称G为算符优先文 法(OPG) 注意:允许b>c,C>b; 不允许b>c,b“(”。 结论:算符优先文法是无二义的

8 在 OG文法 G 中，若任意两个终结符间至多有 一种算符优先关系存在，则称G 为算符优先文 法(OPG)。 注意：允许b>c, c>b; 不允许 b>c, b“（”。 结论 : 算符优先文法是无二义的

算符优先关系表的构造 首先定义如下两个集合: FIRSTVT(B)={b|B→b.或B→Cb…} LASTVT(B)={aB→a或B→…,aC} 按如下算法计算出给定文法中任何两个终结符对(a,b)之间的 优先关系 )'=关系 直接看产生式的右部,若出现了 A b或A→.aBb,则a=b 2)关系 求出每个非终结符B的 LASTVT(B 若A→.Bb.则a∈ LASTVTI(B〕,则ab

9 算符优先关系表的构造 首先定义如下两个集合： FIRSTVT(B)=｛b｜B b… 或 B Cb…｝ LASTVT(B)=｛a｜B …a 或 B …aC｝ 按如下算法计算出给定文法中任何两个终结符对(a,b)之间的 优先关系： 1) ‘= ‘关系 – 直接看产生式的右部，若出现了 A →…ab…或 A →…aBb,则a=b 2)’’关系 – 求出每个非终结符B的LASTVT(B) – 若A→…Bb…,则a∈LASTVT(B),则a>b  +  +  +  +

计算算符优先关系 例文法G[E]: FIRSTVT(E)= (0)E→ FIRSTVT(E)={+,*,个,( (1)E→E+ T FIRSTVT(T)=,个 (2)E→T FIRSTVT(F)=个( F工 RSTVT(P)={. (3)T→ TF LASTVT(E)= (4)T→ F LASTVT(E)=+,,个,), (5)F→PF| P LASTVTT) LASTVT(F)=个,),号 (6)P→(E) LASTVT(P)=0 (7)P→i

10 计算算符优先关系 例文法G’[E’]： (0) E’→#E# (1) E→E+T (2) E→T (3) T→T*F (4) T→F (5) F→PF|P (6) P→(E) (7) P→i FIRSTVT(E’)={#} FIRSTVT(E)={+ , * ,,(,i} FIRSTVT(T)={* ,,(,i} FIRSTVT(F)={,(,i} FIRSTVT(P)={(,i} LASTVT(E’)={#} LASTVT(E)={+ , * ,,),i} LASTVT(T)={* ,,),i} LASTVT(F)={,),i} LASTVT(P)={),i}