Compilers - Bottom Up Deduction

Terminologies

• 短语: 句型中某非终结符通过不少于一步推导得出的字串。

• 简单短语: 句型中某非终结符通过一步推导得出的字串。

• 句柄: 句型中第一个简单短语。

求短语

• 法一：定义法

• 法二：用语法树

对于所有子树，把所有叶结点连起来，即为简单短语。

An example

对于文法：

\[\begin{align} Z &\to aBd \\ B &\to c \\ \end{align}\]

自底向上文法分析操作如下：

Stack	Input stream	Operation
$	a b c d $	移入
$ a	b c d $	移入
$ a b	c d $	移入
$ a b c	d $	用 \(B \to c\) 规约
$ a B	d $	移入
$ a B d	$	用 \(Z \to aBd\) 规约
$ Z	$	结束

如果栈顶出现了句柄，则规约；否则移入。

Symbols

优先关系（推导距离）

推导距离是指一个符号离推导它出来还要多少步。

相邻，X在Y左边且同时出现：$X \doteq Y \Leftrightarrow \dots XY \dots$

相邻，且推导距离不同，符号的方向定义了推导距离：

• X 先出现：$X \lessdot Y$
• Y 先出现：$X \gtrdot Y$

Note that you can’t swap the two operands because the position in expression implies their relative position in productions.

For example, with given grammar:

\[\begin{align} S &\to bMb\\ M &\to a \end{align}\]

Their relationships are:

\[\begin{align} b &\doteq M\\ M &\doteq b\\ b &\lessdot a\\ a &\gtrdot b \end{align}\]

Another example (优先关系矩阵):

	zyx	…
yyx		…
…	…	…

若某个格子为空，则说明两符号永远不会相邻。

With derivation distance, another example (简单优先分析文法)

$\$ \lessdot \text{EVERY SYMBOL}$

Algorithm:

Repeat:

1. Determine the relationship between Stack Top and first symbol in Input Stream.
2. If $S_{i-1} \lessdot S_i \doteq \dots \doteq S_n \gtrdot I_0$ structure shows up, then 规约 $S_i \dots S_n$。Otherwise, 移入。

Note that the number of $\doteq$ can be zero.

条件：

• 任意两个产生式的右部不能相同。
• 任意两个符号至多成立一种优先关系。