什么是句柄？

句柄是一个子字符串，它连接语法中产生式规则的右侧，并且将其归约到该语法规则左侧的非终结符是沿着最右推导的反向的一步。

在每一步中查找句柄

句柄可以通过以下过程找到：

• 它可以从左到右扫描输入字符串，直到遇到第一个 .>。

• 它可以向后扫描，直到遇到 <.

• 句柄是 <. 和 .> 之间的字符串。

示例1 - 考虑语法

E → E + E|E * E|(E)id。

使用运算符优先级解析，在每一步中查找归约字符串 id₁ + id₂ * id₃ 的句柄。

解决方案

首先，在字符串的开头和结尾附加 $，即 $id₁ + id₂ * id₃ $。

使用优先级关系表在运算符和符号之间放置优先级关系。

∴ $ <. id₁. > +<. id₂ >*<. id₃ > $

对字符串应用上述 3 个步骤。

示例2 - 计算以下语法中非终结符 E、T 和 F 的 FIRST 和 LAST 终结符。

E → E + T| T

T → T * F | F

F → (E)| id

解决方案

查看产生式，我们可以判断

+ 是 E 的第一个终结符

* 是 T 的第一个终结符

(, id 是 F 的第一个终结符。

但是 E → T → F

∴ F 的第一个终结符包含在 T 的第一个终结符中，T 的第一个终结符包含在 E 的第一个终结符中。

∴ First(F) = {(, id}

∴ First(T) =*∪ First (F) = {*, (, id}

First(E) = + ∪ First (T) = {+,*, (, id}

同样，可以找到 Last 终结符。

示例3 - 考虑语法

E → E + T|T

T → T ∗ F|F

F → (E)| id

使用运算符优先级解析对字符串 id + id * id 执行栈实现。

解决方案

栈顶和当前输入符号之间存在优先级规则 <. , .> 或 =. 。如果栈顶是非终结符，则将栈顶下方的终结符与当前输入符号进行比较。

Ginni

更新于： 2021-10-29

9K+ 浏览量

开启你的 职业生涯

通过完成课程获得认证

开始学习