编译原理文法简化

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

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

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

产生式

可以简写为：

如上例中，

可以简写为：

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

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

推导的反过程称为 归约 。

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

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

例
文法

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

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

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

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

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

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

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

例：（右线性文法）

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

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

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

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

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

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

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

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

⑵ 编译原理的文法

“文法是以有穷的集合刻画无穷的集合的一个工具”，有穷的集合应该是已经出现的，人们普遍接受的词、词组或句子，无穷的集合就是有穷的集合的词、词组或句子，创造新的集合过程和结果，有待进一步认识接受。
我们的文法规定内涵是已经明确定义的和正在定义（声明）的内容。反映到计算机语言程序中就是编程时已经定义的和正在定义（声明）的字符或字符串。文法可以以表的形式，或词典形式存放。

⑶ 编译原理简单文法归约计算

编译原理中的语法和文法是不一样的，但却融会贯通。
在计算机科学中，文法是编译原理的基础，是描述一门程序设计语言和实现其编译器的方法。
文法分成四种类型，即0型、1型、2型和3型。这几类文法的差别在于对产生式施加不同的限制。
形式语言，这种理论对计算机科学有着深刻的影响，特别是对程序设计语言的设计、编译方法和计算复杂性等方面更有重大的作用。
多数程序设计语言的单词的语法都能用正规文法或3型文法（3型文法G=(VN，VT，P，S)的P中的规则有两种形式：一种是前面定义的形式，即：A→aB或A→a其中A，B∈VN ，a∈VT*，另一种形式是：A→Ba或A→a，前者称为右线性文法，后者称为左线性文法。正规文法所描述的是VT*上的正规集）来描述。
四个文法类的定义是逐渐增加限制的，因此每一种正规文法都是上下文无关的，每一种上下文无关文法都是上下文有关的，而每一种上下文有关文法都是0型文法。称0型文法产生的语言为0型语言。上下文有关文法、上下文无关文法和正规文法产生的语言分别称为上下文有关语言、上下文无关语言和正规语言。

⑷ 在编译原理中： 文法S——>SS+|SS*|a能产生什么语言，并验证！ 求高人指导！

为了使问题简化，我们考虑文法S->ss+|a，考虑s->ss*时，只要把+换成*即可。
0层递归是，s->a,文法的语言是{a}。是后缀表达式。
1层以内递归时，文法语言是{a,aa+}。是后缀表达式。
2层以内递归时，文法语言是{a,aa+}.{a,aa+}.{+}。其中.表示连接，是后缀表达式。
依此类推，多少层的递归都是后缀表达式。
把表达式的+换成*后依然为后缀表达式。
下面证明文法产生的语言是所有的以a为变量，以+和*为运算符的后缀表达式。
因为每个表达式都对应一个常规的表达式（如1*2+3就是常规表达式），下面只需证明语言能产生的后缀表达式对应所有的常规表达式。当常规表达式只有一个运算符，对应aa+或aa*。当常规表达式有两个运算符，可写成(表达式1）.{+|*}.(表达式2），因为表达式1和2都只含一个运算符，所以可以用语言表示，上述常规表达式可用后缀表达式（表达式1）.（表达式2）.{+l*}表示。所以不管常规表达式有多少个运算符，都可以由语言的后缀表达式对应。