编译中的短语原理

⑴ 一个编译原理问题

首先写出指定句型的规范推导：

S→(L)→(L,S)→(L,(L))→(L,(S))→(L,(a))→(S,(a))

然后画出分析树如下图

根据分析树的叶子结点可以找出该句型的所有短语：

aS(a)S,(a)(S,(a))

直接短语，就是经过一次非终结符替换得到的短语：

aS没了

句柄就是最左直接短语，要进行规约的部分，根据分析树我们找到最左直接短语为：

S

⑵ 【编译原理】第二章：语言和文法

上述文法 表示，该文法由终结符集合 ，非终结符集合 ，产生式集合 ，以及开始符号 构成。
而产生式 表示，一个表达式（Expression） ，可以由一个标识符（Identifier） 、或者两个表达式由加号 或乘号 连接、或者另一个表达式用括号包裹（ ）构成。

约定 ：在不引起歧义的情况下，可以只写产生式。如以上文法可以简写为：

产生式

可以简写为：

如上例中，

可以简写为：

给定文法 ，如果有 ，那么可以将符号串 重写 为 ，记作 ，这个过程称为 推导 。
如上例中， 可以推导出 或 或 等等。

如果 ，
可以记作 ，则称为 经过n步推导出 ，记作 。

推导的反过程称为 归约 。

如果 ，则称 是 的一个 句型（sentential form ）。

由文法 的开始符号 推导出的所有句子构成的集合称为 文法G生成的语言 ，记作 。
即：

例
文法

表示什么呢？
代表小写字母；
代表数字；
表示若干个字母和数字构成的字符串；
说明 是一个字母、或者是字母开头的字符串。
那么这个文法表示的即是，以字母开头的、非空的字符串，即标识符的构成方式。

并、连接、幂、克林闭包、正闭包。
如上例表示为：

中必须包含一个 非终结符 。

产生式一般形式：
即上式中只有当上下文满足 与 时，才能进行从 到 的推导。

上下文有关文法不包含空产生式（ ）。

产生式的一般形式：
即产生式左边都是非终结符。

右线性文法 ：
左线性文法 ：
以上都成为正则文法。
即产生式的右侧只能有一个终结符，且所有终结符只能在同一侧。

例：（右线性文法）

以上文法满足右线性文法。
以上文法生成一个以字母开头的字母数字串（标识符）。
以上文法等价于 上下文无关文法 ：

正则文法能描述程序设计语言中的多数单词。

正则文法能描述程序设计语言中的多数单词，但不能表示句子构造，所以用到最多的是CFG。

根节点 表示文法开始符号S；
内部节点 表示对产生式 的应用；该节点的标号是产生式左部，子节点从左到右表示了产生式的右部；
叶节点 （又称边缘）既可以是非终结符也可以是终结符。

给定一个句型，其分析树的每一棵子树的边缘称为该句型的一个 短语 。
如果子树高度为2，那么这棵子树的边缘称为该句型的一个 直接短语 。

直接短语一定是某产生式的右部，但反之不一定。

如果一个文法可以为某个句子生成 多棵分析树 ，则称这个文法是 二义性的 。

二义性原因：多个if只有一个else；
消岐规则：每个else只与最近的if匹配。

⑶ 编译原理中的短语、直接短语、句柄

如果给出短语等名词的形式化的定义，便较难理解，不好求。我们通过构造语法树来求解。首先你应该会根据文法将所给句型构造成语法树的形式，即根据文法怎样推导出句型E+T*F。如果你有数据结构二叉树基础的话这很简单就构造出来了。构造出语法树后，求短语看根节点，有T，和E。则短语为：E+T*F,T*F，而直接短语是指能直接推出叶子节点的根所对应的短语，可知该节点为T，直接短语为：T*F。句柄是最左直接短语，可知为：T*F。

⑷ 编译原理的题目：对于文法G(E):E→T|E+T|E-T T→F|T*F|T/F F→(E)|i

终极符集合Vt={+,-,*,/,(,),i}
非终极符集合Vi={E,T,F}
最右推导：E => E-T => E-F => E-(E) => E-(T) => E-(T+F) => E-(T+i) => E-(T*F+i)
直接短语：T*F,i

⑸ 编译原理-句型、句子、短语、直接短语、句柄、素短语、最左素短语

在进行语法分析的时候，有时候会对这些词语的概念不清晰，这里我们就详细归纳总结一下。

可以看出这个里面，最需要理解的概念就是短语，其他大部分概念都是在短语基础上延伸的，从概念上可以看出：

假设有一个文法

针对文法的一个特定句型 (Sd(T)db) , 其推导过程如下:

这个句型 (Sd(T)db) 对应的 CFG 分析树如下：

那个这个句型 (Sd(T)db) 有多少个短语呢？

还记得短语的定义么， S ⇒* αβδ ， αβδ 代表句型就是这里的 (Sd(T)db) 。

因此这个句型 (Sd(T)db) :

算法非常简单，就是通过分析树的后序遍历，先将子树的叶节点从左到右排合并成字符串(即一个短语)，然后用它代表子树的根节点的值，再和与子树根节点同一层节点值合并，得到新的短语。就这样从分析树的最底层，一路合并到分析树的根节点，就能得到所有的短语了。

通过递归的方法，获取短语列表 phraseList , 直接短语列表 directPhraseList 和 素短语列表 plainPhraseList 。

运行结果: