编译原理 第五章 自下而上语法分析

编译原理 第五章 自下而上语法分析

概述

将输入串从左至右逐一移入分析栈。移进过程中,一旦栈顶形成某产生式的右部,则将这部分替换为产生式的左部。替换过程称为归约

自上而下的关键问题就是寻找可归约串

  • 在规范归约中,用句柄来刻画可归约串;
  • 在算符优先分析中,用最左素短语来刻画可归约串。

规范归约

在形式语言中,最右推导通常被称为规范推导,由规范推导所得到的句型称为规范句型(右句型)。

最左归约:每次归约的都是最左侧的可归约串(称为句柄),是规范推导的逆过程,亦称为规范归约。

令 G 是一个文法,S 是文法的开始符号,假定 \(\alpha \beta \delta\) 是文法 G 的一个句型,如果有 \(S\overset{*}\Rightarrow \alpha A\delta \ 且 \ A\overset{*}\Rightarrow \beta\),则称 β 是句型 \(\alpha \beta \delta\) 相对于非终结符 A 的短语。特别是,如果有 \(A\Rightarrow \beta\) 则称 β 是句型 \(\alpha \beta \delta\) 相对于非终结符 A 的直接短语。一个句型的最左直接短语称为该句型的句柄

例如对于文法(后文简称文法 5.1) \[\begin{align}&S\rightarrow aAcBe \\ &A\rightarrow b \\ &A\rightarrow Ab \\ &B\rightarrow d \end{align}\]

的句子 abbcde 有如下归约过程:

精确的说,假定 α 是文法 G 的一个句子,称序列 \(a_n,a_{n-1},...,a_0\) 是 α 的一个规范归约,如果此序列满足:

  • \(a_n = \alpha\)
  • \(a_0\) 为文法的开始符 S
  • 对任何 i,\(0<i\leq n\)\(a_{i-1}\) 是从 \(a_i\) 经把句柄替换为相应生产式的左部符号而得到的。

实际上,可以建立句子的语法树。以语法树的一棵子树,是由该树的某个节点(作为子树的根)连同它的所有子孙(如果有的话)组成的。一棵子树的所有端末结点自左至右排列起来形成一个相对子树根的短语,一个句型的句柄就是这个句型语法树最左那棵子树端末结点的自左至右排列,这棵子树有且仅有父子两代。

树的图像参考教材页 p87。

算符优先分析

算符优先文法及优先表构造

算符优先分析过程是自下而上的归约过程,未必是严格的最左归约,即它不一定是一种规范归约法。

算符优先分析首先要定义算符(终结符)之间的某种优先关系,借助这种优先关系寻找“可归约串”进行归约。任意两个可能相继出现的终结符 a 和 b(中间可能会有一个非终结符)的优先关系有三种:

注:由于 latex 表示原因,在本文中,将三种符号简化为 <,=,>。但这三种符号并不同于其数学意思,a 的优先性低于 b,并不意味着 b 的优先性高于 a;a 的优先性等于 b,并不意味着 b 的优先性等于 a。

一个文法,如果它的任一产生式的右部都不含两个相继(并列)的非终结符,则称该文法为算符优先文法。

假定 G 是一个不含 ε- 产生式的算符文法。对于任何一对终结符 a、b,规定:

  • a = b,当且仅当 G 中含有 \(P\rightarrow ...ab...\)\(P\rightarrow ...aQb...\) 的产生式;
  • a < b,当且仅当 G 中含有 \(P\rightarrow ...aR...\) 的产生式,而 \(R\overset+{\Rightarrow} b...\)\(R\overset+{\Rightarrow} Qb...\)
  • a > b,当且仅当 G 中含有 \(P\rightarrow ...Rb...\) 的产生式,而 \(R\overset+{\Rightarrow} a...\)\(R\overset+{\Rightarrow} aQ...\)

如果一个算符文法 G 的任何终结符对 (a, b) 至多满足一下三关系之一: \[a=b,a<b,a>b\] 则称 G 是一个算符优先文法。

注:(a, b) 不等价于 (b, a),(a, b) 和 (b, a) 的优先关系没有任何关系。

为了构造算符优先表,要对 G 中每个非终结符 P 构造两个集合 FIRSTVT(P) 和 LASTVT(P)。

\[\begin{align} &FIRSTVT(P)=\{a|P\overset+{\Rightarrow} a... \ 或\ P \overset+{\Rightarrow} Qa...,a\in V_T,Q\in V_N \} \\ &LASTVT(P)=\{a|P\overset+{\Rightarrow} ...a \ 或\ P \overset+{\Rightarrow} ...aQ,a\in V_T,Q\in V_N \} \end{align}\]

有了这两个集合后,那么假定有个产生式的一个候选形为 \(...aP...\),那么对任何 \(b\in FIRSTVT(P)\),有 a < b;同样地,假定有个产生式的一个候选形为 \(...Pb...\),那么对任何 \(a\in LASTVT(P)\),有 a > b。

构造 FIRSTVT(P) 的算法:

  1. 若有产生式 \(P\rightarrow a... \ 或\ P \rightarrow Qa...\),则 \(a\in FIRSTVT(P)\)
  2. \(a\in FIRSTVT(Q)\),且有产生式 \(P \rightarrow Q...\),则 \(a\in FIRSTVT(P)\)

即 FIRSTVT(P) 是 P 所有产生式中的第一个终结符和第一个非终结符的 FIRSTVT 集合中的所有元素的集合。

构造 LASTVT(P) 的算法:

  1. 若有产生式 \(P\rightarrow ...a \ 或\ P \rightarrow ...aQ\),则 \(a\in LASTVT(P)\)
  2. \(a\in LASTVT(Q)\),且有产生式 \(P \rightarrow ...Q\),则 \(a\in LASTVT(P)\)

即 LASTVT(P) 是 P 所有产生式中的最后一个终结符和最后一个非终结符的 LASTVT 集合中的所有元素的集合。

现有如下文法:

\[\begin{align}&E\rightarrow E+T|T \\&T\rightarrow T*F|F \\ &F\rightarrow P\uparrow F|P \\ &P\rightarrow (E)|i \end{align}\]

构造其算符优先表。

首先对文法添加一个产生式 \(E'\rightarrow \#E\#\);

其次,求出各算符的 FIRSTVT 和 LASTVT 集合;

根据算法,填入优先表:

注:对于符号对 (a, b),优先表行是 a,列是 b。

算符优先分析算法

素短语:至少含有一个终结符,且除它自身之外不再含有更小的素短语。

最左素短语:句型最左边的素短语。

考虑算符优先文法,把句型的一般形式写为 \(\#N_1 a_1N_2 a_2 ...N_n a_nN_{n+1} \#\)。 其中,每个 \(a_i\) 都是终结符,\(N_i\) 是可有可无的终结符,两个终结符之间至多为一个非终结符。

一个算符优先文法 G 的任何句型的最左素短语是满足如下条件的最左子串 \(N_j a_j ... N_i a_i N_{i+1}\)

\[\begin{align}&a_{j-1}< a_j \\ &a=a_{j+1},...,a_{i-1}=a_i\\ &a_i > a_{i+1} \end{align}\]

优先函数

为了避免优先关系表占用的存储量过大,可以使用优先函数代替优先关系表。定义 f 为入栈优先函数,g 为比较优先函数。定义如下:

当然,对应一个优先关系表的优先函数 f 和 g 是不唯一的,也有很多优先关系表不存在对应的优先函数。

从优先表构造优先函数的一个简单方法是:

  1. 对于每个终结符 a(包括 #),令其对应两个符号 \(f_a\)\(g_a\),画一张以所有符号 \(f_a\)\(g_a\) 为结点的方向图,如果 a >= b,那么从 \(f_a\) 画一条箭弧至 \(g_b\),如果 a <= b,那么从 \(g_b\) 画一条箭弧至 \(f_a\)
  2. 对每个结点都赋予一个数,值为从该结点出发所能到达的结点个数(包括自身),\(f_a\) 的值给 f(a) , \(g_b\) 的数给 g(b)。
  3. 检查构造出来的函数 f 和 g 是否同原来的关系表矛盾。若没有矛盾,则 f 和 g 就是所求的优先函数。若有矛盾,则不存在优先函数。

LR 分析

LR 分析技术是一个有效的自上而下分析技术。L 表示从左至右扫描输入串,R 表示构造一个最右推导的逆过程。LR 分析器模型如下:

左侧栈的每一项内容包括状态 a 和文法符号 X 两部分。\((s_0,\# )\) 为预先放到栈里的初始状态和句子括号(句子开始)。

LR 的核心是分析表。这张表包括两部分 ACTION 表和 GOTO 表,都是二维数组。ACTION[s, a] 规定了当状态 s 面临输入符号 a 应该采取什么动作,GOTO[s, X] 规定了状态 s 面对文法符号 X 时下一状态是什么。

每一项 ACTION[s, a] 所规定的动作是以下四种可能之一:

  • 移进,把 (s, a) 的下一状态 s'=GOTO[s, a] 和输入符号推进栈,下一输入符号变为现行输入符号。
  • 归约,用某一生产式 \(A\rightarrow \beta\) 进行归约。假设 β 的长度为 r,归约的动作是 A,取出栈顶的 r 个项,然后把 \((s_{m-r},A)\) 的下一状态 $s'=GOTO[s_{m-r}, A] $ 和文法符号 A 推进栈。不改变现行输入符号。
  • 接受,宣布分析成功,停止分析器工作。
  • 报错,调用出错处理程序。

例如:

利用上图,假定输入串为 i*i+i,LR 的分析过程如下:

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×