编译原理之 句型&句子&短语&直接短语&句柄&素短语&最左素短语 定义实例详解

叮嘟！这里是小啊呜的学习课程资料整理。好记性不如烂笔头，今天也是努力进步的一天。一起加油进阶吧！

一、定义详解

1、句型&句子

概念：

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

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

2、短语&直接短语

概念：

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

理解：

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

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

语法树： 在语法树中表示为直接短语只有上下相邻父子两代。
1
2
3
4
5
6
7
8
9

3、句柄

概念：

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

理解：

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

4、素短语&最左素短语

概念：

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

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

理解：

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

最左素短语：
从素短语集合中找出最左边的素短语。
1
2
3
4
5
6
7

二、 实例巩固理解

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

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

证明(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
1
2
3
4
5
6

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

故直接短语有：
① S
② a
1
2
3

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

故句柄为：
① S
1
2

步骤五：判断素短语
由后往前对短语进行判断，如果短语中至少含有一个终结符，而且除它自身之外不再含任何更小的素短语，那么称该短语为素短语。
① 对于短语 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
1
2

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

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

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

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

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

求解句型的短语，直接短语，句柄。
1
2
3
4
5
6
7
8
9
10

题目解析：

推导步骤为：
T ⇒ T*F
  ⇒ T*F↑P
  ⇒ T*P↑P
  ⇒ T*P↑(T)
  ⇒ T*P↑(T*F)
1
2
3
4
5
6

该语法树的 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
1
2
3
4
5

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

就酱，嘎啦！
1

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