编译原理表达式的文法
⑴ 【编译原理】构造下述文法G[S]的确定有限自动机，并给出该文法的语言的正规表达式 S->Aa|ε A->Aa|Sb|a
通过联立方程组求正规表达式：
A = Aa|Sb|a = Aa|(Aa|ε)b|a= Aa+(Aa+ε)b+a=Aa+(Aab+b)+a=Aa+Aab+b+a=A(a+ab)+(b+a)
根据方程X=Xt+r 必有X=t*r解的论断，可得A=(a+ab)*(b+a)，进而可求得：
S = Aa|ε = Aa+ε = Aa = (a+ab)*(b+a)a = (a|ab)*(b|a)a
即文法的正规表达式为： (a|ab)*(b|a)a。
注意：以上求解的过程中“|”和“+”是等价的，都表示“或”的意思，它们的相互替换是为了描述的方便。
⑵ 【编译原理】第二章：语言和文法
上述文法 表示，该文法由终结符集合 ，非终结符集合 ，产生式集合 ，以及开始符号 构成。
而产生式 表示，一个表达式（Expression） ，可以由一个标识符（Identifier） 、或者两个表达式由加号 或乘号 连接、或者另一个表达式用括号包裹（ ）构成。
约定 ：在不引起歧义的情况下，可以只写产生式。如以上文法可以简写为：
产生式
可以简写为：
如上例中，
可以简写为：
给定文法 ，如果有 ，那么可以将符号串 重写 为 ，记作 ，这个过程称为 推导 。
如上例中， 可以推导出 或 或 等等。
如果 ，
可以记作 ，则称为 经过n步推导出 ，记作 。
推导的反过程称为 归约 。
如果 ，则称 是 的一个 句型（sentential form ）。
由文法 的开始符号 推导出的所有句子构成的集合称为 文法G生成的语言 ，记作 。
即：
例
文法
表示什么呢？
代表小写字母；
代表数字；
表示若干个字母和数字构成的字符串；
说明 是一个字母、或者是字母开头的字符串。
那么这个文法表示的即是，以字母开头的、非空的字符串，即标识符的构成方式。
并、连接、幂、克林闭包、正闭包。
如上例表示为：
中必须包含一个 非终结符 。
产生式一般形式：
即上式中只有当上下文满足 与 时，才能进行从 到 的推导。
上下文有关文法不包含空产生式（ ）。
产生式的一般形式：
即产生式左边都是非终结符。
右线性文法 ：
左线性文法 ：
以上都成为正则文法。
即产生式的右侧只能有一个终结符，且所有终结符只能在同一侧。
例：（右线性文法）
以上文法满足右线性文法。
以上文法生成一个以字母开头的字母数字串（标识符）。
以上文法等价于 上下文无关文法 ：
正则文法能描述程序设计语言中的多数单词。
正则文法能描述程序设计语言中的多数单词，但不能表示句子构造，所以用到最多的是CFG。
根节点 表示文法开始符号S；
内部节点 表示对产生式 的应用；该节点的标号是产生式左部，子节点从左到右表示了产生式的右部；
叶节点 （又称边缘）既可以是非终结符也可以是终结符。
给定一个句型，其分析树的每一棵子树的边缘称为该句型的一个 短语 。
如果子树高度为2，那么这棵子树的边缘称为该句型的一个 直接短语 。
直接短语一定是某产生式的右部，但反之不一定。
如果一个文法可以为某个句子生成 多棵分析树 ，则称这个文法是 二义性的 。
二义性原因：多个if只有一个else；
消岐规则：每个else只与最近的if匹配。
⑶ 四种文法的类型(编译原理)
乔姆斯基（Chomsky）按产生式的类型把文法分为四种类型：0、1、2、3型文法。
*在下文中的产生式中，箭头左边的大写字母为严格的非终结符，而其左边的小写字母不严格要求为非终结符，如[0型文法]中的第2条产生式。
【0型文法】
产生式形式：α→β
要求：箭头左边的α 至少 含有 一个非终结符 ， 其余 不加任何限制
例如，G：C→AaB
aA→a
B→b|Bb
【1型文法】
产生式形式：α→β
要求： |α|≤|β| (产生式左端的长度<=右端的长度)，S→ε除外。
例如G： C→aAB
aA→aBa
B→b|Bb
【2型文法】(上下文无关文法)
产生式形式：A→β，A∈VN(终结符) ，β∈V *(VN∪VT，即可为终结符也可为非终结符)
说明：当以β替换A时，与A的上下文环境无关；
大部分程序设计语言近似于2型文法。
【3型文法】(正规文法 / 右线性文法)
产生式形式：A→a，A→aB，
说明：a∈VT(终结符) ， A，B∈VN(非终结符)，即产生式右端的第一个符号必须为 终结符
例如 G：A→aB
B→b|bB
【其他说明】对于这四种类型的文法：
*包含关系：0 > 1 > 2 > 3 (以'>'代替包含符，'A>B'译为A包含B)
*严格程度：3 > 2 > 1 > 0
*判断文法所属类型的顺序：3 → 2 → 1 → 0
⑷ 编译原理的文法是什么
文法是描述语言规则的形式规则。实际上就是用一个四元组G=(VT,VN,S,P)定义的一个推理方式。其中VT是终结符，VN是非终结符，S是开始符号，P是一组产生规则。
⑸ 编译原理中的语法和文法一样吗
编译原理中的语法和文法是不一样的，但却融会贯通。
在计算机科学中，文法是编译原理的基础，是描述一门程序设计语言和实现其编译器的方法。
文法分成四种类型，即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型语言。上下文有关文法、上下文无关文法和正规文法产生的语言分别称为上下文有关语言、上下文无关语言和正规语言。
⑹ 什么是文法(编译原理)
【定义】
文法G定义为四元组（VN，VT，P，S）
其中 VN ：非终结符号(即语法变量)集
VT ： 终结符号集
VN∩VT =Φ，令V= VN∪VT，V称为文法G的字母表或字汇表。
P ：产生式(α→β)集
S ：开始符号，且S∈VN ，S至少要在一条规则的左部出现。
【约定】
一般地，文法G的 四元组 不用全部给出 ，而只将产生式写出。
约定：
（1）第一条产生式的左部是开始符号
（2）用尖括号括起来的（或 大写字母 ）是非终结符号
（3）不用尖括号括起来（或 小写字母 ）是终结符号
（4）还有一种习惯写法，即 G[S] ，其中 S 是 开始符号 。
【举例】
例: G=（VN，VT，P，S）
其中 VN={S}，
VT ={0，1}，
P={S→0S1，S→01}
S是开始符号
⑺ 编译原理-文法定义
文法定义公式如下:
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型文法。
⑻ 编译原理考试问题:已知表达式文法G(Exp)
简单起见，用E代表Exp，用T代表Term，用F代表Factor。下面是所求属性文法
（1）E→ E1 + T E.val:=E1.val+T.val /* 为了区别→两侧的E, →右侧的E用E1表示 */
（2）E→
T E.val:=T.val
（3）T→ T1 * F T.val:=T1.val*F.val
（4）T→
F T.val:=F.val
（5）F→（E） F.val:=E.val
（6）F→num F.val:=num.val