编译原理中空字符也是短语吗

‘壹’ 【编译原理】第二章：语言和文法

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

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

产生式

可以简写为：

如上例中，

可以简写为：

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

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

推导的反过程称为 归约 。

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

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

例
文法

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

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

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

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

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

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

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

例：（右线性文法）

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

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

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

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

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

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

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

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

‘贰’ 编译原理，设文法G[E]如下，句型T＋T * F＋a的素短语是__

试给出句型T－T／F＋a和T＋T＊F－F↑a的短语、句柄、素短语：

句型1：短语TT／F＋a， T－T／F， T， T／F， a

句型T

素短语： T／F，a

句型2：短语E＋T＊F＿F↑a， E＋T＊F， T＊F，F↑a， a

句型T＊F

素短语： T＊F，a

(2)编译原理中空字符也是短语吗扩展阅读

文法：以有穷的集合描述无穷的计划的工具。

字母表：元素的非空有穷集合，其中的元素称为符号，因此也叫符号集。

符号串：由字母表中的元素组成的任何有穷序列，串中的元素个数叫做符号串的长度，空符号串ε，长度为0。

符号串的运算：

连接－符号串x ＝ ab，y＝cd， xy ＝ abcd

方幂－z＝xn，当n ＝ 0， z ＝ ε，当 n ＝ 2， z ＝ xx

集合的闭包－∑＊ ＝ ∑0 ∪∑1 ∪∑2 ∪…∪∑n

∑＋ 为正闭包 ＝ ∑1 ∪∑2 ∪…∪∑n

‘叁’ 短语、简单短语、句柄如何区分(编译原理)

刚开始学编译原理的时候，我对这三个概念真的很懵逼→_→

因为资料上的文字说明太不直观了，看了半天愣是很懵逼，于是往下看，看到了例子之后，就觉得明朗了许多！

上图!

这是一颗语法树，那如何求它的短语、简单短语和句柄呢？

我们按照 [句柄→简单短语→短语] 的顺序来找

首先：句柄(整棵树 最左 边的 叶子 ，共1个)

          a1

其次：简单短语(所有 叶子 ，共6个)

          a1, ε, b1, b2, a2, a3

最后：短语(所有的叶子+每个中间节点所包含的叶子 序列 ， 共9个)

a1, ε, b1, b2, a2, a3, 

a2a3, εb1b2, a1εb1b2a2a3

包含关系：短语 > 简单短语 > 句柄

‘肆’ 编译原理有关语法的题

短语：E+F*（E+i），F*(E+i),(E+i),E+i,i

直接短语：i（能直接推出来的）

句柄：i（最左直接短语）

素短语：i（并且至少含有一个终结符并除自身之外不含任何更小的素短语)

这些你根据语法树看，就比较好找了啊~

语法树如图：

‘伍’ 编译原理-文法定义

文法定义公式如下:

Chomsky 文法分类将文法分为四种，0型文法( PSG )、1型文法( CSG )、2型文法( CFG )和3型文法( RG )。

又被称为无限制文法(Unrestricted Grammar), 或者短语结构文法（Phrase Structure Grammar）
定义: 对于产生式 α→β ， α 至少包含一个非终结符。

为什么要叫无限制文法，明明它要求产生式的左部必须包含一个非终结符。

又被称为上下文有关文法(Context-Sensitive Grammar)
定义：对于产生式 α→β , |α| <= |β| , 仅仅 S→ε 除外

为什么叫做上下文有关文法？

一般情况下，这种产生式的形式为 α1Aα2→α1βα2

又被称为上下文无关文法(Context-Free Grammar)
定义：对任一产生式 α→β ，都有 α∈VN，β∈(VN∪VT)*

为什么叫上下文无关文法？

又被称为正则文法（Regular Grammar，RG），分为右线性（Right Linear）文法和左线性（Left Linear）文法。

定义: 对任一产生式 α→β ，都有 α∈VN，β最多两个字符元素，如果有二个字符必须是（终结符+非终结符）的格式，如果是一个字符，那么必须是终结符。

根据产生式右部非终结符位置不同，分为右线性文法和左线性文法。

可以看出，不同文法就是对产生式进行逐层的限制，所以各个文法是包含关系，即0型文法包含1型文法；1型文法又包含2型文法；2型文法最后包含3型文法。

‘陆’ 编译原理中的短语、直接短语、句柄

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

‘柒’ 编译原理：空字符串可以是短语吗

ε可以是短语

‘捌’ 编译原理空字符ε与空集区别

不知你说的空集是为何指？据我所猜应该是指某个文法所能推导的语句的集合为空，这里的空集意思是不存在匹配该文法的句子。而ε则是指某个包含非终结符号的文法符号串的推导为空，例如A->ε。咋看上去好像差不多，其实它们却有本质的区别，空集是面向结果的，即一个文法所有可能推导的最终语句；而ε则是面向定义的，即某个非终结符号可以推导为空，这样的定义可以在推导过程重复使用。
最后给你来点哲学的。为什么会存在ε？古代有句话叫，其大无外，其小无内，大小之间转化的奥秘在编译原理中真实的被呈现了出来，就看你有没有发现。可以肯定的说，ε的存在正是应了无穷的需要。例如：A->aA|ε，这里ε既可以A可以表达任意多的a串，又可以动态的将其终止，不至无休止的无限下去。
你终会明白，理解了ε，就是理解了形式语言的整个灵魂。

‘玖’ 请教几个有关编译原理的习题！

答:
一
1. S -> aS | ε
2. S -> aS | Sb | ab
二
设 有字符串序列 abc, 而字符串 abc 符合是文法S.
abc 有两种推导 ① S -> Ac, A -> bc
② S -> aB, B -> bc
有两语法树,二义文法
三
不好意思忘记了短语、直接短语和句柄
课本上应该有

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

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

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

假设有一个文法

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

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

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

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

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

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

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

运行结果: