《编译原理》求短语，直接短语，句柄，素短语，最左素短语 - 例题解析

笔记

（一）明确概念：

例题1：求短语，直接短语，句柄

给定句型：

T*P↑(T*F)

给定文法：

G[T]:
T → T*F|F
F → F↑P|P
P → (T)|i

解析：

推导步骤为：

T ⇒ T*F
⇒ T*F↑P
⇒ T*P↑P
⇒ T*P↑(T)
⇒ T*P↑(T*F)

画出语法树为：

该语法树的 5 个子树及 5 个短语为：

求直接短语方法： 该句型的语法树有两颗直接子树（最左边的两颗子树），由这两颗直接子树的叶子结点组成的符号串（或者说只包含两层的子树叶子结点对应的），就是句型的两个直接短语，直接短语 P 和 T*F。

求句柄： 因为 P 相对 T*F，在语法树上的左侧，所以句柄是 P

最终结果：

例题二：求素短语，最左素短语

给定句型：

FF↑*a*

给定文法：

G[T]:
T → T*F|F
F → F↑P|P
P → (T)|i

解析：

推导步骤为：

T ⇒ TF*
⇒ TF*F*
⇒ TF↑*\F*
⇒ TF↑*a*

画出语法树：

最终结果：

根据定义可以找出素短语有：

一般先根据句型写出语法树，然后再根据语法树进行求解。
举个例子：

先画出语法树（最左推导）：

短语：在语法树中，先找出所有的非终结符，然后用叶子节点去替换他们，最后得到的集合就是短语的集合。
这里的非终结符从上到下为：E、E、T、E、T、F、T、T、F。我们用叶子节点全部替换这些非终结符。所以短语有：T、T * F、i、T+T * F、T+T * F+i。（重复的去掉了）

直接短语:在语法树中，一步就能够用叶子节点替换掉非终结符的短语。
在这个例子，我们可以用叶子节点T一步替换掉E，那么T就是一个直接短语，然后我们发现T * F这个短语也能一步替换掉T这个节点，因此T*F也是直接短语。同理可以知道i也是直接短语。
所以直接短语有：T、T * F、i。

句柄：语法树中最左边的直接短语。
这里很明显是T。

素短语：短语中的包含终结符的短语，同时不被其他素短语包含的短语。
这里很拗口，因此仔细说一下。
在这个例子中，我们看包含终结符的短语有：T*F、i、T+T * F、T+T * F+i。然后我们发现T+T * F+i包含了i和T+T * F和T * F，所以这个肯定不是。然后我们发现T+T * F包含了T * F，所以这个也不是。
因此素短语有：i、T * F。

最左素短语：顾名思义。
这里是：T * F

一、定义详解

1、句型&句子

概念：

如果 S⇒* α，α∈(VT∪VN)*，则称α是G的一个句型 (sentential form)。
一个句型中既可以包含终结符，又可以包含非终结符，也可能是空串。

如果 S⇒* w，w ∈VT*，则称w是G的一个句子(sentence)。
    句子是不包含非终结符的句型。

2、短语&直接短语

概念：

如果 S⇒* αＡβ 且 A ⇒+ γ，则称γ是句型αγβ的相对于非终结符A的`短语` 。
如果 S⇒* αＡβ 且 A ⇒ γ，则称γ是句型αγβ的相对于规则A→γ的`直接(简单)短语`。

理解：

短语：
一个句型的分析树中的每一棵子树的边缘(所有叶节点)所组成的符号串称为该句型的一个短语(phrase)。 

直接短语：
如果子树只有父子两代结点，那么这棵子树的边缘称为该句型的一个直接短语(immediate phrase)；
所有子树中，深度为2的子树的叶子节点串就是直接短语（因为直接短语必须是由子树根节点用一步推出来的，所以深度为2）；
即如果子树中不再包含其他的子树，即A只能推导出b，而b不能再推出其他的式子，则b为此句型的直接短语。

语法树： 在语法树中表示为直接短语只有上下相邻父子两代。

3、句柄

概念：

直接短语中的最左直接短语为该句型的句柄。

理解：

“可规约串”，句柄对应某个产生式的右部，是某个，但不是任意一个。
作为一种规约对象，句柄表示最左直接短语。
语法树： 在语法树上，则表示为最左边的只包含相邻父子节点的短语（最左直接短语）

4、素短语&最左素短语

概念：

素短语：
是指一个短语至少包含一个终结符，并且除它自身之外不再包含其他素短语。

最左素短语：
最左素短语就是句型最左边的素短语，是算符优先分析法的规约对象。
语法树：通过语法树分析时，要注意先判断是否为素短语，再找相对最左端的素短语。

理解：

素短语 ：
指一个短语至少包含一个终结符，并且除它自身之外不再包含其他素短语。
从短语集合中找出所有含有终结符的短语，然后选出除它自身之外不再含更小的素短语。
（这个小的概念是集合中没有被包含的元素，如有两个短语aAA和aAAA，aAA含于aAAA，所以aAA比aAAA小）

最左素短语：
从素短语集合中找出最左边的素短语。

二、 实例巩固理解

1、实例一求解短语、直接短语、句柄和素短语详解

令文法 G1 为：
①S−>(L)∣aS∣a 
②L−>L,S∣S 

证明(S,(a)) (S,(a))(S,(a))是它的一个句型，指出这个句型的所有短语，直接短语，句柄和素短语。

题解：

步骤一：画出语法树如下图

步骤二：判断短语
一个句型的语法树中任一子树的叶节点所组成的符号串都是该句型的短语。
对于第一层的非终结符 S ，其叶节点所组成的短语是(S,(a))
对于第二层的非终结符 L ，其叶节点所组成的短语是S,(a)
对于第三层的非终结符 L ，其叶节点所组成的短语是S
对于第三层的非终结符 S ，其叶节点所组成的短语是(a)
对于第四层的非终结符 L ，其叶节点所组成的短语是a
对于第五层的非终结符 S ，其叶节点所组成的短语是a

故短语有：
① (S,(a))
② S,(a)
③ S
④ (a)
⑤ a

步骤三：判断直接短语
一个句型的语法树中任一最小子树的叶节点所组成的符号串都是该句型的直接短语。

故直接短语有：
① S
② a

步骤四：判断句柄
句柄是最左边的直接短语。

故句柄为：
① S

步骤五：判断素短语
由后往前对短语进行判断，如果短语中至少含有一个终结符，而且除它自身之外不再含任何更小的素短语，那么称该短语为素短语。
① 对于短语 a ，a不含其他任何更小的素短语。故短语 a 为素短语
② 对于短语 (a) ，(a) 含素短语 a。故短语 (a) 不是素短语
③ 对于短语 S ，S 不含终结符。故短语 S 不是素短语
④ 对于短语 S,(a) ，S,(a) 含素短语a。故短语 S,(a) 不是素短语
⑤ 对于短语 (S,(a)) ，(S,(a)) 含素短语a。故短语 (S,(a)) 不是素短语

故素短语为：
① a

2、实例二求解短语、直接短语、句柄、素短语和最左素短语详解

3、实例三求解短语、直接短语、句柄、素短语和最左素短语详解

4、实例四求解短语，直接短语，句柄详解

给定句型：
T*P↑(T*F)

给定文法：
G[T]:
T → T*F|F
F → F↑P|P
P → (T)|i

求解句型的短语，直接短语，句柄。

题目解析：

推导步骤为：
T ⇒ T*F
  ⇒ T*F↑P
  ⇒ T*P↑P
  ⇒ T*P↑(T)
  ⇒ T*P↑(T*F)

该语法树的 5 个子树及 5 个短语为：

求直接短语方法： 该句型的语法树有两棵直接子树（最左边的两颗子树），由这两棵直接子树的叶子结点组成的符号串（或者说只包含两层的子树叶子结点对应的），就是句型的两个直接短语，直接短语为 P 和 T*F。

求句柄： 因为 P 相对 T*F，在语法树上的左侧，所以句柄是 P。

综上：

短语         P，T*F，(T*F)，P↑(T*F)，T*P↑(T*F)
直接短语 	P，T*F
句柄	        P

Ending！
更多课程知识学习记录随后再来吧！

就酱，嘎啦！

注：
人生在勤，不索何获。