① 【编译原理】第二章：语言和文法
上述文法 表示，该文法由终结符集合 ，非终结符集合 ，产生式集合 ，以及开始符号 构成。
而产生式 表示，一个表达式（Expression） ，可以由一个标识符（Identifier） 、或者两个表达式由加号 或乘号 连接、或者另一个表达式用括号包裹（ ）构成。
约定 ：在不引起歧义的情况下，可以只写产生式。如以上文法可以简写为：
产生式
可以简写为：
如上例中，
可以简写为：
给定文法 ，如果有 ，那么可以将符号串 重写 为 ，记作 ，这个过程称为 推导 。
如上例中， 可以推导出 或 或 等等。
如果 ，
可以记作 ，则称为 经过n步推导出 ，记作 。
推导的反过程称为 归约 。
如果 ，则称 是 的一个 句型（sentential form ）。
由文法 的开始符号 推导出的所有句子构成的集合称为 文法G生成的语言 ，记作 。
即：
例
文法
表示什么呢？
代表小写字母；
代表数字；
表示若干个字母和数字构成的字符串；
说明 是一个字母、或者是字母开头的字符串。
那么这个文法表示的即是，以字母开头的、非空的字符串，即标识符的构成方式。
并、连接、幂、克林闭包、正闭包。
如上例表示为：
中必须包含一个 非终结符 。
产生式一般形式：
即上式中只有当上下文满足 与 时，才能进行从 到 的推导。
上下文有关文法不包含空产生式（ ）。
产生式的一般形式：
即产生式左边都是非终结符。
右线性文法 ：
左线性文法 ：
以上都成为正则文法。
即产生式的右侧只能有一个终结符，且所有终结符只能在同一侧。
例：（右线性文法）
以上文法满足右线性文法。
以上文法生成一个以字母开头的字母数字串（标识符）。
以上文法等价于 上下文无关文法 ：
正则文法能描述程序设计语言中的多数单词。
正则文法能描述程序设计语言中的多数单词，但不能表示句子构造，所以用到最多的是CFG。
根节点 表示文法开始符号S；
内部节点 表示对产生式 的应用；该节点的标号是产生式左部，子节点从左到右表示了产生式的右部；
叶节点 （又称边缘）既可以是非终结符也可以是终结符。
给定一个句型，其分析树的每一棵子树的边缘称为该句型的一个 短语 。
如果子树高度为2，那么这棵子树的边缘称为该句型的一个 直接短语 。
直接短语一定是某产生式的右部，但反之不一定。
如果一个文法可以为某个句子生成 多棵分析树 ，则称这个文法是 二义性的 。
二义性原因：多个if只有一个else；
消岐规则：每个else只与最近的if匹配。
② 编译原理：构造产生此语言的上下文无关文法G
对于文法G=(V, T, S, P)，如果产生式的形式如下：
A -> xB
A -> x
其中A, B属于V，x属于T*，则称为右线性文法；相似的，如果产生式的形式如下：
A -> Bx
A -> x
则称为左线性文法。右线性文法和左线性文法统称为正则文法。
正则表达式的表达能力等价于正则文法，正则表达式的定义如下：
字母表中的任意字母是正则表达式，空串和空集也是正则表达式；
如果r, s是正则表达式，那么r|s, rs, r*, (r)也是正则表达式。
正则表达式的扩展：
r+：一个或多个重复
. ：任意字符
[a-z]：字符范围
[^abc]：不在给定集合中的任意字符
r?：可选
正则表达式只能使用终结符（字母表中的字符），因而很容易变得复杂又难懂，实际中，经常使用正则描述，正则描述允许使用非终结符定义表达式，很像EBNF，但是它限制在未完全定义之前，不能使用非终结符，也就是说不允许递归或自嵌套。
像正则表达式的表达能力等价于正则文法一样，BNF范式的表达能力等价于上下文无关文法。BNF是“Backus Naur Form”的缩写。John Backus和Peter Naur首次引入一种形式化符号来描述给定语言的语法。
BNF的元符号：
::= 表示“定义为 ”，有的书上用-->
| 表示“或者”
< > 尖括号用于括起非终结符。
BNF的扩展EBNF：
可选项被括在元符号“[”和“]”中
重复项（零个或者多个）被括在元符号“{”和“}”中
仅一个字符的终结符用引号（"）引起来，以和元符号区别开来
上述操作符不是严格限定的，有的人喜欢直接使用扩展正则表达式的操作符描述EBNF。除了方便表达以外，引入EBNF的另一个主要原因是为了更紧密地把文法映射到递归下降分析程序的真实代码。当需要手动构造归下降分析程序的时候，通常把上下文无关文法改写为EBNF是必需的。
如果一个上下文无关文法G不是自嵌套或自递归的，即不存在如下推导：
U =>* xUy
那么L(G)是正则语言。自嵌套的上下文无关文法不一定是正则语言。事实上，一个上下文无关文法是严格的，既不可能由正则文法产生，当且仅当该语言的一切文法都是自嵌套的。
如果一个上下文无关文法G不是自嵌套或自递归的，即不存在如下推导：
U =>* xUy
那么L(G)是正则语言。自嵌套的上下文无关文法不一定是正则语言。事实上，一个上下文无关文法是严格的，既不可能由正则文法产生，当且仅当该语言的一切文法都是自嵌套的。
BNF的扩展EBNF：
可选项被括在元符号“[”和“]”中
重复项（零个或者多个）被括在元符号“{”和“}”中
仅一个字符的终结符用引号（"）引起来，以和元符号区别开来
上述操作符不是严格限定的，有的人喜欢直接使用扩展正则表达式的操作符描述EBNF。除了方便表达以外，引入EBNF的另一个主要原因是为了更紧密地把文法映射到递归下降分析程序的真实代码。当需要手动构造归下降分析程序的时候，通常把上下文无关文法改写为EBNF是必需的。
如果一个上下文无关文法G不是自嵌套或自递归的，即不存在如下推导：
U =>* xUy
那么L(G)是正则语言。自嵌套的上下文无关文法不一定是正则语言。事实上，一个上下文无关文法是严格的，既不可能由正则文法产生，当且仅当该语言的一切文法都是自嵌套的。
如上所述，上下文无关文法的递归性，对其分析方法也有很大影响。首先，用作识别这些结构的算法必须使用递归调用或显式管理的分析栈。其次，用作表示语言语义结构的数据结构现在也必须是递归的（通常是一颗分析树），而不再是线性的（如同用于词法和记号中的一样）了。
在程序设计语言中，通常用正则表达式描述词法规则。但是正则表示式的表达能力有限，她无法表达括号配对等语法形式，因而，需要引入表达能力更强的上下文无关文法。编译程序中常用正则文法表示词法，用上下文无关文法表示语法。那么程序语言中那些属于词法哪些属于语法呢？一个简单的办法，把所有能用正则文法表示的规则成为词法，即我们用尽可能的使用正则文法表示更多的东西，那些无法用正则表示式表示的成为句法，如C语言中的{ statement; }语法形式。语言中有些规则使用上下文无关文法仍然无法描述，例如变量的定义在使用之前，类型匹配等等，这些通常称为（静态）语义，它们在编译程序的静态语义检查阶段进行检测。
如果一个上下文无关文法G不是自嵌套或自递归的，即不存在如下推导：
U =>* xUy
那么L(G)是正则语言。自嵌套的上下文无关文法不一定是正则语言。事实上，一个上下文无关文法是严格的，既不可能由正则文法产生，当且仅当该语言的一切文法都是自嵌套的。
③ 编译原理中 文法 文法G定义为四元组（Vn ,Vt,P,S）这4个是什么意思 另外 终结符和非终结符是什么意思
文法G是一个四元式（Vt,Vn,S,P）
其中Vt是一个非空有限集，它的每个元素称为终结符号
Vn是一个非空有限集，它的每个元素称为非终结符号（Vt和Vn的交集为空）
S是一个非终结符号，称为开始符号
P是一个产生式集合（有限），每个产生式的形式是P-->a
开始S必须在某个产生式的左部出现一次
终结符指组成语言的基本符号（如基本字、标识符、常数、算符、界符）
非终结符号（也称语法变量）表示一定符号串的集合。
你看到小写字母一般是终结符，大写字母肯定是非终结符
不明白可以联系。
④ 编译原理题目：下列文法能否转换为等价的非二义文法
二义性文法【定义】 若文法中存在这样的句型，它具有两棵不同的语法树，则称该文法是二义性文法。二义性文法会引起歧义，应尽量避免之！ E E E + E E * E i E * E E + E i i i i i 都可以表示i+i*i 所以G(E)：E -> E+E | E*E | (E) | i ;文法具有二义性。文法二义性的消除：【方法1】不改变文法的原有规则,加进一些非形式规定。加进运算符的优先顺序和结合规则对G(E)，规定*优于+，*和+服从左结合【方法2】构造一个等价的无二义性文法，将排除 二义性的规则合并到文法中 G(E) -> G′(E) : E -> E+T | T T -> T*F | F F -> (E) | i ;
⑤ 编译原理中文法二义性问题
二义性文法
【定义】 若文法中存在这样的句型，它具有两棵不同的语法树，则称该文法是二义性文法。
二义性文法会引起歧义，应尽量避免之！
E E
E + E E * E
i E * E E + E i
i i i i
都可以表示i+i*i
所以G(E)：E -> E+E | E*E | (E) | i ;文法具有二义性。
文法二义性的消除：
【方法1】不改变文法的原有规则,加进一些非形式规定。
加进运算符的优先顺序和结合规则对G(E)，规定*优于+，*和+服从左结合
【方法2】构造一个等价的无二义性文法，将排除 二义性的规则合并到文法中
G(E) -> G´(E) : E -> E+T | T T -> T*F | F F -> (E) | i ;
⑥ 编译原理全部的名词解释
书上有别那么懒！。。。。
编译过程的六个阶段：词法分析，语法分析，语义分析，中间代码生成，代码优化，目标代码生成
解释程序：把某种语言的源程序转换成等价的另一种语言程序——目标语言程序，然后再执行目标程序。解释方式是接受某高级语言的一个语句输入，进行解释并控制计算机执行，马上得到这句的执行结果，然后再接受下一句。
编译程序：就是指这样一种程序，通过它能够将用高级语言编写的源程序转换成与之在逻辑上等价的低级语言形式的目标程序(机器语言程序或汇编语言程序)。
解释程序和编译程序的根本区别：是否生成目标代码
句子的二义性（这里的二义性是指语法结构上的。）:文法G[S]的一个句子如果能找到两种不同的最左推导(或最右推导)，或者存在两棵不同的语法树，则称这个句子是二义性的。
文法的二义性:一个文法如果包含二义性的句子，则这个文法是二义文法，否则是无二义文法。
LL(1)的含义：(LL(1)文法是无二义的； LL(1)文法不含左递归)
第1个L：从左到右扫描输入串 第2个L：生成的是最左推导
1 ：向右看1个输入符号便可决定选择哪个产生式
某些非LL(1)文法到LL(1)文法的等价变换: 1. 提取公因子 2. 消除左递归
文法符号的属性:单词的含义，即与文法符号相关的一些信息。如，类型、值、存储地址等。
一个属性文法(attribute grammar)是一个三元组A=(G, V, F)
G：上下文无关文法。
V：属性的有穷集。每个属性与文法的一个终结符或非终结符相连。属性与变量一样，可以进行计算和传递。
F：关于属性的断言或谓词(一组属性的计算规则)的有穷集。断言或语义规则与一个产生式相联，只引用该产生式左端或右端的终结符或非终结符相联的属性。
综合属性:若产生式左部的单非终结符A的属性值由右部各非终结符的属性值决定,则A的属性称为综合属
继承属性:若产生式右部符号B的属性值是根据左部非终结符的属性值或者右部其它符号的属性值决定的,则B的属性为继承属性。
(1)非终结符既可有综合属性也可有继承属性，但文法开始符号没有继承属性。
(2) 终结符只有综合属性，没有继承属性，它们由词法程序提供。
在计算时： 综合属性沿属性语法树向上传递；继承属性沿属性语法树向下传递。
语法制导翻译：是指在语法分析过程中，完成附加在所使用的产生式上的语义规则描述的动作。
语法制导翻译实现：对单词符号串进行语法分析，构造语法分析树，然后根据需要构造属性依赖图，遍历语法树并在语法树的各结点处按语义规则进行计算。
中间代码（中间语言）
1、是复杂性介于源程序语言和机器语言的一种表示形式。
2、一般，快速编译程序直接生成目标代码。
3、为了使编译程序结构在逻辑上更为简单明确，常采用中间代码，这样可以将与机器相关的某些实现细节置于代码生成阶段仔细处理，并且可以在中间代码一级进行优化工作，使得代码优化比较容易实现。
何谓中间代码：源程序的一种内部表示，不依赖目标机的结构，易于代码的机械生成。
为何要转换成中间代码:(1)逻辑结构清楚；利于不同目标机上实现同一种语言。
(2)便于移植，便于修改，便于进行与机器无关的优化。
中间代码的几种形式：逆波兰记号 ，三元式和树形表示 ，四元式
符号表的一般形式：一张符号表的的组成包括两项，即名字栏和信息栏。
信息栏包含许多子栏和标志位，用来记录相应名字和种种不同属性，名字栏也称主栏。主栏的内容称为关键字（key word）。
符号表的功能：（1）收集符号属性 (2) 上下文语义的合法性检查的依据： 检查标识符属性在上下文中的一致性和合法性。(3)作为目标代码生成阶段地址分配的依据
符号的主要属性及作用：
1. 符号名 2. 符号的类型 （整型、实型、字符串型等））3. 符号的存储类别（公共、私有）
4. 符号的作用域及可视性 （全局、局部） 5. 符号变量的存储分配信息 （静态存储区、动态存储区）
存储分配方案策略：静态存储分配；动态存储分配：栈式、 堆式。
静态存储分配
1、基本策略
在编译时就安排好目标程序运行时的全部数据空间，并能确定每个数据项的单元地址。
2、适用的分配对象：子程序的目标代码段；全局数据目标（全局变量）
3、静态存储分配的要求：不允许递归调用，不含有可变数组。
FORTRAN程序是段结构，不允许递归，数据名大小、性质固定。 是典型的静态分配
动态存储分配
1、如果一个程序设计语言允许递归过程、可变数组或允许用户自由申请和释放空间，那么，就需要采用动态存储管理技术。
2、两种动态存储分配方式：栈式，堆式
栈式动态存储分配
分配策略：将整个程序的数据空间设计为一个栈。
【例】在具有递归结构的语言程序中，每当调用一个过程时，它所需的数据空间就分配在栈顶，每当过程工作结束时就释放这部分空间。
过程所需的数据空间包括两部分
一部分是生存期在本过程这次活动中的数据对象。如局部变量、参数单元、临时变量等；
另一部分则是用以管理过程活动的记录信息(连接数据)。
活动记录（AR）
一个过程的一次执行所需要的信息使用一个连续的存储区来管理，这个区 (块)叫做一个活动记录。
构成
1、临时工作单元；2、局部变量；3、机器状态信息；4、存取链；
5、控制链；6、实参；7、返回地址
什么是代码优化
所谓优化，就是对代码进行等价变换，使得变换后的代码运行结果与变换前代码运行结果相同，而运行速度加快或占用存储空间减少。
优化原则：等价原则：经过优化后不应改变程序运行的结果。
有效原则：使优化后所产生的目标代码运行时间较短，占用的存储空间较小。
合算原则：以尽可能低的代价取得较好的优化效果。
常见的优化技术
(1) 删除多余运算(删除公共子表达式) (2) 代码外提 +删除归纳变量+ (3)强度削弱; (4)变换循环控制条件 (5)合并已知量与复写传播 (6)删除无用赋值
基本块定义
程序中只有一个入口和一个出口的一段顺序执行的语句序列，称为程序的一个基本块。
给我分数啊。。。
⑦ 编译原理 LR0文法的判定
设G1、G2是两个文法，若L(G1)=L(G2) ，则称G1与G2等价，记作G1≡G2。
即：文法的等价性是指他们所定义的语言是一样的。
文法的化简是指消除如下无用产生式：
⒈ 删除 A->A 形式的产生式(自定己)；
⒉ 删除不能从其推导出终结符串的产生式(不终结)；
⒊ 删除在推导中永不使用的产生式(不可用)。
⑧ 编译原理文法可以定义为四元集G(S)={Vn ,Vt,P,S},那么Vn* ,Vt*和Vn+ ,Vt+，即右上角加*或+是什么意思
右上角加*是集合的闭包，也称为克林闭包(Kleene Closure)，右上角加+是集合的正闭包
Vn* 是非终结符集的闭包，Vn+是非终结符集的正闭包
Vt* 是终结符集的闭包，Vt+是终结符集的正闭包
⑨ 编译原理的文法是什么
文法是描述语言规则的形式规则。实际上就是用一个四元组G=(VT,VN,S,P)定义的一个推理方式。其中VT是终结符，VN是非终结符，S是开始符号，P是一组产生规则。
⑩ 文法的定义
文法是一个汉语词汇，读音为wén fǎ ，即文章的书写法规，一般用来指以文字、词语、短句、句子的编排而组成的完整语句和文章的合理性组织。
定义
文法即文章的书写法规，一般用来指以文字、词语、短句、句子的编排而组成的完整语句和文章的合理性组织。[2]
组成规律
●最简单的语句组合一：主词及动词：
“我”“哭了”
“天气”“改变了”
“哭笑”“难分”
●最简单的语句组合二：主词、动词及受词：（括号内为隐藏语）
我爱你
“道”“可”“道”，“(这个道字)”“〈并〉非”“常道”。《道德经》老子
“打羽毛球”“是”“最好的(运动)”
“驾驶”“〈使我〉”“乐趣无穷”
●比较复杂的语句组合一：主语〈短句〉、谓语及宾语：
例：“我这个从来没有恋爱经验的少年人”、“竟然不知为了什么原因而喜欢了”及“一个黄毛小丫头”
●复杂的语句组合二：主语及复式谓语：
例：“有些头脑守旧而自以为是的读书人”、“认为如厕的动作不雅，”“所以写成出恭。”
在口语中，因为说话者或受话人都知道相方的关系和说话主题，所以大都隐去主词或受词。但在书写文章时，必须要清楚表明主和宾双方。
一般结构
●动宾结构：一般口语，多是动宾结构的，即前面是动词，后面是名词组成的。这是因为受话人明知语句的主语而不用说出来的关系。
〈你正在──主语不用说出来〉拍马屁、
〈你真的是〉痴线（广东惯用语）、〈你是在〉敲竹杠、〈你在〉泼冷水、〈你不要〉耍花招等。
●主谓结构，主谓（陈述）结构，即前面是主词或主语，后面加上一个描述或动作的单字、词语或词组组成的。这是因为说话语句中的受词或宾语不用说出来的关系 。
多为说话语句中的动词部分，主语和宾语也不用说出了。 例如：（这个）天晓得，、〈他的〉嘴巴软〈了〉等。
●复词结构
●偏正结构由两组〈或以上〉字词所组成的〈复合〉名词──用作主语部分，或宾语部分。
●形容词〈相当于英语的形容词〉及名词。
替罪羊、耳边风、糊涂虫、绊脚石等。
鬼画〈形容词〉符
由两组〈或以上〉字词所组成的短句，如谓语部分。
●动词及副词。
跳得很远、大声哭叫、清早起来
类型
文法形式
在计算机科学中，文法是编译原理的基础，是描述一门程序设计语言和实现其编译器的方法。文法的描述多用BNF(巴克斯范式)，而另一个重要的概念:正则表达式，也是文法的另一种形式。
文法分类
自从乔姆斯基(Chomsky)于1956年建立形式语言的描述以来，形式语言的理论发展很快。这种理论对计算机科学有着深刻的影响，特别是对程序设计语言的设计、编译方法和计算复杂性等方面更有重大的作用。
乔姆斯基把文法分成四种类型，即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:终结符号集；
P: 规则的集合；
VN，VT和P是 非空有穷集。
S:称作识别符号或开始符号的一个非终结符，它至少要在一条产生式中作为左部出现。
VN和VT不含公共的元素，即VN ∩ VT = φ
用V表示VN ∪ VT ，称为文法G的字母表或字汇表
规则，也称重写规则、产生式或生成式，是形如→或 ∷=的( ，)有序对，其中是字母表V的正闭包V+中的一个符号，是V*中的一个符号。 称为规则的左部， 称作规则的右部。
设G=(VN，VT，P，S)，如果它的每个产生式α→β是这样一种结构：α∈( VN∪VT )*且至少含有一个非终结符，而β∈( VN∪VT )*，则G是一个0型文法。
0型文法也称短语文法。一个非常重要的理论结果是，0型文法的能力相当于图灵机(Turing)。或者说，任何0型语言都是递归可枚举的；反之，递归可枚举集必定是一个0型语言。
对0型文法产生式的形式作某些限制，以给出1，2和3型文法的定义。
设G=(VN，VT，P，S)为一文法，若P中的每一个产生式α→β均满足|β|≥|α| ，仅仅S→ε除外，则文法G是1型或上下文有关的。
在有些文献给的定义中，将上下文有关文法的产生式的形式描述为α1Aα2→α1βα2，其中α1、α2和β都在( VN∪VT
)*中(即在V*中)，β≠ε，A在VN中。这种定义与前边的定义等价。但它更能体现"上下文有关"这一术语，因为只有A出现在α1和α2的上下文中，才允许用β取代A。
设G=(VN，VT，P，S)，若P中的每一个产生式α→β满足：α是一非终结符，β∈( VN∪VT )*则此文法称为2型的或上下文无关的。有时将2型文法的产生式表示为形如：A→β其中A∈VN，也就是说用β取代非终结符A时，与A所在的上下文无关，因此取名为上下文无关文法。
例4.1和例4.2中的文法都是上下文无关的，下面我们再给出一个例子(例4.4)，例中的文法G是上下文无关文法，G的语言是由相同个数的a和b所组成的{a，b}*上的串。
设G=(VN，VT，P，S)，若P中的每一个产生式的形式都是A→aB或A→a，其中A和B都是非终结符，a是终结符，则G是3型文法或正规文法。