编译原理 第二部分
文法，推导/归约；
句型，句子，语言；
文法的类型，正规文法，上下文无关文法，文法等价；
语法树与二义性
程序设计语言的描述
- 语法(Syntax):涉及语言的构成规律，即程序的结构或形式；
- 语义(Semantics): 指语言所代表的含义；
- 语用(Pragmatics): 涉及到实际应用。
程序设计语言的形式描述
不考虑语义和语用，即只从语法这一侧面来看语言，这种意义下的语言称作==形式语言==
“形式”是指：语言的所有规则只以什麽符号串能出现的方式来陈述。形式语言理论是对符号串集合的表示法、结构及其特性的研究。是程序设计语言语法分析研究的基础。
形式语言
符号和符号串
【字母表】有穷非空符号（元素）集。用大写字母表示。
【符号】可以相互区别的记号（元素）。用小写字母或数字
【符号串】由字母表中的符号组成的任何有穷序列称为该字母表上的符号串。简称为串、行
【空串】不含任何符号的串。用 ε 表示
符号串和符号串集合的运算
【长度】符号串中符号的个数。串β的长度记为|β |。特别地有：|ε| ＝0
【连接】串x、y的连接,是把y的符号写在x的符号之后得到的符号串xy 。记为xy 或x·y 。特别地有：εx = xε = x
【串的方幂】串x自身连接n次。记为$x^n$。特别的有 $x^0=ε$
【积】设A、B为两个符号串集合，其乘积A·B是x∈A且y∈B的所有符号串xy构成的集合。记为AB或A·B。即AB＝｛xy | x∈A，y∈B｝。特别地有：｛ε｝A＝A｛ε｝＝A
注意：ε，｛ε｝，$\emptyset$ 三者之间的区别
【集合的方幂】设A为符号串集合，则串集合A的幂运算
递归定义如下：$ A^0＝｛ε｝, $ $A^n ＝AA ……AA ＝A^{n－1}A ＝AA^{n－1} （n＞0）$
【闭包】设A为符号串集合，则串集合A的闭包表示为$A^$，定义为：$$A^＝A^0∪A^1∪…… ∪ A^k ∪ ……$$
【正闭包】串集合A的正闭包表示为$A^+$，定义为：
具有以下性质：
==形式语言==是一个字母表上按某种规则构成的所有符号串的集合。
字母表∑， $∑^*$包含由∑上符号构成的所有符号串
∑上每个语言是$∑^*$ 的一个子集
∑上按某种规则构成的符号串称为句子
如何来描述一种语言
如果语言是有穷的（只含有有穷多个句子），可以将句子逐一枚举出来表示;
如果语言是无穷的，找出语言的有穷表示。语言的有穷表示有两个途经：
- 生成方式 （文法）：语言中的每个句子可以用严格定义的规则来构造。
- 识别方式（自动机）：用一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就会停止并回答“是”，若不属于，要么能停止并回答“不是”，（要么永远继续下去。）
文法的形式定义
【非终结符号】一系列需要定义的语法成分，即规则中用尖括号括起来的，由它们可推出其它句子成分。例如：＜主语＞，＜谓语＞ 等。
【终结符号】若干基本符号，是组成句子的最基本符号。例如：张三，是，学生。
【产生式】一组产生句子的规则：P→α 或 P ::＝α
【开始符号】语言中的句子只能从它开始推导。 ＜句子＞是开始符号，是语言的目标，而其它语法成分只是构造语言目标时的中间变量。
文法定义
文法定义为四元组 $G＝(V_N，V_T，P，S )$。其中：
$V_N$为非终结符号(或语法实体，或变量)集；
$V_T$为终结符号集；$ V_N ∩ V_T = \emptyset$，通常用$V$表示$V_N ∪ V_T$，称为文法$G$的字母表；
$P$为产生式或规则$（α→β或α∷=β）$的集合， 其中$α∈V^+$，且 $α$ 中至少要包含一个非终结符，$β∈V^*$
$S$是识别符号或开始符号，它是一个非终结符，至少要在一条产生式中作为左部出现。
产生式
规则，也称重写规则、产生式或生成式，是形如：
$$ α→β 或 α∷=β$$
的$(α，β)$有序对，其中$α$是字汇表$V$的正闭包$V^+$中的一个符号$(即α∈V^+)$， $β$中至少要包含一个非终结符，是$V^$中的一个符号$(即β∈V^)$。
α称为产生式的左部，β称作产生式的右部（候选式）
文法的多种写法
记号
元符号：$\rightarrow \\ ::= \\ | $
习惯表示： 大写字母：非终结符 小写字母：终结符
推导
直接推导 $\Rightarrow$ 给定文法$G=（V_N，V_T，P，S）$，如果$α→β$是文法$G$的产生式，若有$v,w$满足：$v=γαδ,w= γβδ$, 其中 $γ∈V^,δ∈V^ $, 则称$v$直接推导到$w$,记作 $v \Rightarrow w$, 也称$w$直接归约到$v$
多步推导
$\stackrel{+}{\Rightarrow}$ 若存在$v\Rightarrow w_0 \Rightarrow w_1 \Rightarrow … \Rightarrow w_n=w,(n>0)$则记为$v \stackrel{+}{\Rightarrow} w$，$v$推导出$w$，或$w$归约到$v$
$\stackrel{}{\Rightarrow}$ 若有$v \stackrel{+}{\Rightarrow} w$，或v=w，则记为$v \stackrel{}{\Rightarrow} w $
【最左推导】如果在推导每一步过程中总是考虑对句型中最左的非终结符进行替换，则称这种推导为最左推导。
【最右推导】如果在推导每一步过程中总是考虑对句型中最右的非终结符进行替换，则称这种推导为最右推导。
【规范推导】即最右推导。
【规范句型】由规范推导推导出的句型。
句型和句子
【句型】若$S\stackrel{*}{\Rightarrow} α $，则称$α$是文法$G$的句型。
【句子】若$S\stackrel{}{\Rightarrow} α $，且$α∈V_T^$，则称$α$是文法$G$的句子。(即仅含终结符的句型称为句子)
语言的形式定义
文法$G$所描述的全部句子的集合称为语言，记为$L(G)$。
即 $L(G)=\{α|S \stackrel {}{\Rightarrow} α，$ 其中S为文法的开始符号，且$α∈V_T^$}
【文法等价】若$L(G1)=L(G2)$ ，则称文法$G1和G2$是等价的。
注意：属于$V_T^$的符号串，不一定属于$L(G)$,即$L(G)$是$V_T^$的子集，故$L(G)$是定义于字母表$V_T$上的。
文法与语言的关系不是一对一的关系由文法推导出语言
文法与语言的分类
0型文法（短语文法）
$产生式α→β中α∈ (V_N∪V_T)^+,且至少含有一个非终结符，而β∈(V_N∪V_T)^*。$
0型文法对应的语言称为0型语言。
0型文法对应的自动机称为图灵机(Turing)。
1型文法（上下文有关文法）
$产生式 α→β 中 |α|≤ |β| $
等价定义为：
对于产生式$α_1Aα_2 → α_1 β α_2(β≠ ε， α1与α2不同时为ε)$，当用$β$替换$A$时，只能在上下文为$α_1$和$α_2$时才可进行 。
1型文法对应的语言称为1型语言（上下文有关语言）
1型文法对应的自动机是线性界限自动机
2型文法（上下文无关文法）
$产生式A→β，都有A∈V_N ， β∈(V_N∪V_T)^*$
2型文法对应的语言称为2型语言（上下文无关语言）
2型文法对应的自动机是下推自动机。
上下文无关文法用来描述高级语言的语法规则。
3型文法（正规文法）
右线性文法： $A→aB或A→a$
左线性文法： $A→Ba或A→a$
其中，$A、B ∈V_N ，a ∈V_T $。
3型文法对应的语言称为3型语言(正规集)
3型文法对应的自动机是有穷自动机。
正规文法用来描述高级语言的词法规则。
四种文法之间是逐级包含的
四个文法类的定义是逐渐增加限制的，因此每一种正规文法都是上下文无关的，每一种上下文无关文法都是上下文有关的，而每一种上下文有关文法都是0型文法。
语法树
设文法$G=(V_N ，V_T ，P，S)$下的语法树具有以下特征：
1.根结点是S；
2.每个结点上的$标记符∈V＝V_N∪V_T$ ；
3.若一结点$A$至少有一个后代，则有$A∈V_N$ ；
4.若一棵子树的根结点标记为$A$,且其所有直接后代结点从左向右排列的顺序分别为$A_1，A_2，…，A_k，$则$A→A_1A_2…A_k∈P$。
5.若树的所有叶子上的标记从左向右排列为串$ω$，则$ω$是$G$的句型；若$ω$中仅含终结符，则它是$G$所产生的句子
从左到右读出叶子的标记而构成的串是该语法树识别的句子
推导过程（最左推导，最右推导，一般推导）不同，语法树的生长过程也不同，但最终生成的语法树完全相同
文法的二义性
若文法$G$中存在某个句子对应两棵不同的语法树，则称该文法具有二义性。
或者，若文法$G$中存在某个句子有两个不同的最左（右）推导，则称该文法具有二义性。
注意：判定任给的一个上下文无关文法是否具有二义性，或它是否产生一个先天二义性的上下文无关语言，这两个问题是递归不可解的，但可以为无二义性寻找一组充分条件。
二义性的解决办法有两个：
根据提出的条件修改编译算法
根据预先提出的条件直接修改文法
如果产生上下文无关语言的每一个文法都是二义性的，则说此语言是先天二义性的。对于一个程序设计语言来说，常常希望它的文法是无二义性的，因为希望对它的每个语句的分析是唯一的。