6章自底向上语法分析.pptVIP

算符优先文法的定义 ? 算符优先关系表的构造 算符优先分析算法 算符优先分析法的局限性 分析程序模型 自下而上分析算法 模型----移进归约 算符优先分析不是规范归约 如何确定算符优先关系？ 人为确定： （1）i的优先级最高 （1） ?优先级次于i，右结合 （2）*和/优先级次之，左结合 （3）+和-优先级最低，左结合 （4）括号‘(’,‘)’的优先级大于括号外的运算符，小于括号内的运算符，内括号的优先性大于外括号 （5）#的优先性低于与其相邻的算符 6.3.2 算符优先文法的定义 定义：如果不含空产生式的上下文无关文法 G 中没有形如 A?…BC…的产生式，其中B，C∈VN 则称G 为算符文法（OG）。 例6.1 G[E]：E→E+E|E-|E*E|E/E|E?E|(E)|i 例6.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 = b G中有形如：A?…ab… 或A ? …aBb...的产生式。 a b G中有形如: A? …aB…的产生式, 而 B b… 或B Cb… a b G中有形如: A ? …Bb…的产生 式,而 B …a 或 B … aC 规定 若 S a…或 S Ca… 则 # a 若 S …a 或 S …aC 则 a # 在 OG文法 G 中，若任意两个终结符间至多有一种算符优先关系存在，则称G 为算符优先文法(OPG)。 注意：允许bc, cb; 不允许 bc, bc, b=c中任两个 同时存在。 b=c 不一定 c = b。 例6.1中：“（” = “）”，“）”“（”。 结论 : 算符优先文法是无二义的。 6.3.3 算符优先关系表的构造 首先定义如下两个集合： 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的FIRSTVT(B) 若A→…aB…,则?b∈FIRSTVT(B),则ab 3)’’关系 求出每个非终结符B的LASTVT(B) 若A→…Bb…,则?a∈LASTVT(B),则ab 计算算符优先关系 例6.3 文法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 (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 表达式文法G’[E’]的算符优先关表 6.3.4 算符优先分析算法 算符优先文法句型的性质 算符文法的任何一个句型应为如下形式： ＃N1a1N2a2 ... Nnan Nn+1＃ 其中N k(1≤k≤n+1)为非终结符或空，ak(1≤k≤n)为终结符 算符优先文法句型的最左素短语NiaiNi+1ai+1 ... Njaj Nj+1满足： ai-1 ＜ ai ai =ai+1 =…… =aj-1 =aj aj ＞ aj+1 即：ai-1ai=ai-1=...= aj-1 = aj aj+1 算符优先分析的可归约 串是句型的最左素短语 定义 cfg（上下文无关文法） G 的句型的素短语是一个短语，它至少包含一个终结符，且除自身外不再包含其他素短语。处于句型最左边的素短语为最左素短语 文法G[S]短语的定义 S αAδ且A ?则称?是句型α?δ相对于非终结符A的短语 分析程序模型 算符优先分析法 简单，直观，有利于表达式分析，易于手工实现 比规范归约快 可能导致把错误的句子得到正确的归约 例：