零、 程序语言的定义
一个程序语言是一个记号系统，其定义包含两部分：语法和语义
0.1 语法
语法：形成和产生合适程序的规则集，描述了该语言的程序的正确形式。
- 词法规则：形成单词符号的规则
- 语法规则： 形成语法单位的规则（语法树表示）
常用的语法描述方法（文法）：
- 用正规文法描述词法规则。
- 用上下文无关文法描述语法规则。
0.2 语义
语义：用以定义程序意义的规则集，即解释程序在运行时做什么
静态语义：标识符未声明、重复声明、类型不符、种类不符
动态语义：除零错误、下标越界、无效指针、死循环
在不同语言中完全相同的语法单位，含义却可能完全不同，例如：x=y 在C语言中表示赋值表达式，在Pascal语言中为关系表达式。
一、文法的直观概念
以定义描述英语句子的文法为例：He gave me a book
文法的规则如下：
代码语言：javascript复制(1)<句子>→<主语><谓语><间接宾语><直接宾语>
(2)<主语>→<代词>
(3)<谓语>→<动词>
(4)<间接宾语>→<代词>
(5)<直接宾语>→<冠词> <名词>
(6)<代词>→He|me
(7)<冠词>→a
(8)<动词>→gave
(9)<名词>→book|peach< > 表示该对象还需要进一步定义， -> 表示将左边的定义为右边。
应用上述语法规则进行推导：
代码语言：javascript复制句子
=>主语 谓语 间接宾语 直接宾语
=>代词 谓语 间接宾语 直接宾语
=>He 谓语 间接宾语 直接宾语
=>He 动词 间接宾语 直接宾语
=>He gave 间接宾语 直接宾语
=>He gave 代词 直接宾语
=>He gave me 直接宾语
=> He gave me 冠词 名词
=> He gave me a 名词
=> He gave me a book=> 表示应用某个规则进行推导（即将相应规则的右部进行替换），上述例子中，终结符号为He,me,book,gave等，非终结符号为句子,主语,谓语,动词等，开始符号为 句子，产生式依靠语法规则。
画出语法树：
二、符号和符号串
2.1 符号和字母表
符号(元素)： 可以相互区别的记号，例如 a b 0 1。
字母表： 符号的非空有穷集合，如 {0,1} 表示二进制数语言的字母表，程序设计语言的字母表是该语言的基本字符集。
C语言是C程序的集合，C程序是在C基本字符集上定义的，按一定规则构成的符号串。
2.2 符号串
定义：由字母表中的符号所组成的任何有穷序列称为该字母表上的符号串。
空串： (ε—空字) 长度为0的符号串，|ε|=0。
2.2.1 符号串的操作
运算：
- 连接（并置）：x = 123, y = 45, xy = 12345
- 方幂：x^0 = ε,x^1 = x, x ^ 2 = xx…
子字符串： 非空，原串从头和尾去掉 ge0 个字符得到。
头，尾： x是xy的头，y是xy的尾。
2.2.2 字符串集合
定义：若集合A中的一切元素都是某字母表上的符号串，则称A为该字母表上的符号串的集合。
例： ∑={0，1} 是字母表,其中 0,1 为符号，则D={0,1} 其中 0,1 为符号串，E= {ε, 0,1,00,01,10,11,000, …}是 ∑ 上的符号串集合。 特别：空集记为ф ={ } 注意与 ε 区别。
操作：
- 乘积： UV = {αβ|α∈U且β∈V}
- 方幂 ：V的n次方幂就是将n个V相乘
- 符号串集V的闭包 V^* =V^0∪ V^1 ∪ V^2 ∪ V^3 ∪… ，，即 V 上的所有符号串(包括空字ε)的集合。
- 符号串集V的闭包 V^ =V^1 ∪ V^2 ∪ V^3 ∪… ，，即 V 上的所有非空符号串(包括空字ε)的集合。
2.2.3 语言的概念
某个字母表 ∑ 上的符号串集合，是 ∑^* 的一个子集。
三、 文法和语言的形式定义（重点）
3.1 规则或产生式
形式: α→β或α::=β，α 称为产生式的左部，β称为产生式的右部，读作“α定义为β”。
举例：
- A→a 这是关于A的一条规则
- <标识符> →<字母>
- <字母> →a|b|……|z
3.2 文法的定义
定义：Ｇ = (Ｖ_T，Ｖ_N，S，P)，以四元式的形式表示。
Ｖ_T 非空有穷终结符集
Ｖ_N 非空有穷非终结符集 Ｖ_T ∩Ｖ_N = ф
S∈Ｖ_N 开始符号 ，S至少在产生式左部出现一次
P 非空有穷产生式集合 α→β
- α∈(Ｖ_T ∪Ｖ_N)^*，且至少含有一个非终结符
- β∈(Ｖ_T ∪Ｖ_N)^*，
令Ｖ=Ｖ_T ∪Ｖ_N ，称Ｖ为文法符号，是文法G的字母表
3.3 文法描述的约定
用大写字母A、B、C…或汉语词组<标识符>代表非终结符号
用小写字母a、b、c…代表终结符号
用希腊字母α、β、γ…代表终结符号和非终结符号组成的符号串
若干个左部相同的产生式可以合并为一个 P→α_1| α_2 |…| α_n，每个αi 称为P的一个候选式
3.4 推导
直接推导：
产生式右部代替左部，当Ａ→γ 是文法Ｇ的一个产生式，且α、β∈(Ｖ_T∪Ｖ_N)^*，则有α Ａ β => α γ βα γ β 是 α Ａ β的直接推导或称 α γ β 直接归约到 αＡβ ，G[E]:E→E E|E * E|( E )|i，i E => i E * E
特点：只能用一次产生式替换。
归约：
如果α_0=>α_1=>α_2=>…=>α_nα_0至α_n的一个推导
用α_0=^ >α_nα_0 出发，经一步或多步推导，可推出 α_n
用 α_0=^*>α_nα_0 出发，经零步或多步推导，可推出 α_n ，即 α_0=α_n或α_0=^ >α_n
3.5 句型
定义：设 G 是一个文法，S 是开始符号，若有 S =^*>αG(E):E→E E|E * E|( E )|i。
例如 E= >iEE 是文法 G(E) 的一个句型。
E=^ >iiii 是文法 G(E) 的一个句型。
句子： 完全由终结符组成的句型。例如 E=^ >iiii 是文法 G(E) 的一个句子。
合法句子的生成：u从Ｓ出发反复推导，每次得到一个句型，最终得到句子。
3.6 文法G描述的语言
由文法Ｇ产生的所有句子的集合为：Ｌ(Ｇ)＝{α｜Ｓ＝^ ＞α 且 α∈Ｖ_T^*}
文法G的作用：以有限的规则描述无限的语言现象。
- 有限：产生式集合、终结符集合、非终结符集合。
- 无限：由开始符号导出的句子。
例：G[E]:E→E E|E * E|( E )|i，文法G所描述的语言：含有 、*和括号的算术表达式
3.7 文法等价性
若L(G1)=L(G2)，则称文法G1和G2是等价的（它们产生的句子集合相同）
例子：
文法 G_1[E]:E→E E | E*E |(E)| i
文法 G_2[E]:E→E T | T，T→T*F | F，F→(E)| i
因为L(G_1)=L(G_2),所以文法G_1和G_2是等价的。
四、文法的类型
4.1 0型文法（短语文法 ）
对任一产生式α→β，都有α∈(Ｖ_N∪Ｖ_T)^*且α至少含有一个非终结符，β∈(Ｖ_N∪Ｖ_T)^*，此类文法的限制最少，描述能力最强。
4.2 1型文法（上下文有关文法）
对任一产生式α→β，都有|α|≤|β| 仅仅Ｓ→ε 除外，并且Ｓ不出现在其他产生式的右部。
例如： S→aSBA，AA’→AB 。
这里的上下文有关指的是，对于某个推导还限制了一定的条件，比如 AA’→AB ，直观来看就是 A’→B，但是替换有个“上下文限制”，即必须前面有一个 A 才能替换。
4.3 2型文法（上下文无关文法）
对任一产生式α→β，都有α∈Ｖ_N，β∈(Ｖ_N∪Ｖ_T)^*
例如 E→E T|T，足以描述大多数程序设计语言语法特征
4.4 3型文法（正规文法）
- 右线性文法：对任一产生式的形式都为Ａ→ａＢ或Ａ→ａ，其中Ａ，Ｂ∈Ｖ_N ，ａ∈Ｖ_T^* （ａ可为ε）
- 左线性文法：对任一产生式的形式都为Ａ→Ｂａ或Ａ→ａ，其中Ａ，Ｂ∈Ｖ_N ，ａ∈Ｖ_T^* （ａ可为ε）
4.5 四类文法的关系
由于四种文法是按照将产生式做进一步限制而定义的，所以它们之间是逐级“包含”的关系，由四种文法产生的语言也是逐级“包含”关系。
五、上下文无关文法及其语法树（重点）
5.1 上下文无关文法组成
终结符号：组成语言的基本符号，在程序语言中是单词符号。
非终结符号：用来代表语法范畴(语法概念)，每个非终结符号表示一定符号串的集合。
开始符号：一个特殊的非终结符号。
产生式：是定义语法范畴的一种书写规则。形式 A→α，A是一个非终结符，称为产生式的左部符号，α是一个符号串，称为产生式的右部
5.2 语法树（推导树）
构造特点：
- 每个结点都有一个V中的符号作标记
- 根结点——开始符S
- 中间结点——非终结符 A∈Ｖ_N
- 叶结点——非终结符或终结符(关于句型)，终结符a∈Ｖ_T (关于句子)
- 如果结点n标记为A， 其直接子孙从左到右的标记为A_1,A_2,…,A_k, 则 A→ A_1A_2…A_k ∈P
构造步骤：
- 步骤1 根结点为开始符号
- 步骤2 对于每一次推导使用的产生式A→α，找出A对应的结点(此时应该是末端结点)，从该结点向下画分支，子结点从左到右分别是α中从左到右的符号
- 重复步骤2直到推导的最后一步
语法树特点：
从语法树的构造过程可以看出，句型的推导过程不同，语法树的生长过程也不同，但最终生成的语法树结构是完全相同的。可以说，一棵语法树包括了一个句型所有可能的推导过程。整体上看不出推导的次序(即产生式使用的次序)，只能看出使用了哪些产生式。
5.3 最左（最右）推导
定义：在一个推导的过程中，如果每一步直接推导所被替换的总是最左(右)的非终结符号。最右推导常被称为规范推导。由规范推导所得到的句型称为规范句型，也称为右句型。
5.4 二义性文法
5.4.1 二义性定义
若一个文法存在某个句型对应两棵不同的语法树，则称这个文法是二义性文法。或者，若一个文法存在某个句型有两个不同的最左(最右)推导，则称这个文法是二义性文法。二义性一般是有害的，如果一个句子具有二义性，那么对这个句子的结构可能有多种“正确”的解释。通常情况下，我们希望对每个语句的分析是唯一的。但是,只要我们能够控制和驾驭文法的二义性,文法二义性的存在并不一定是坏事 。
例如：文法G：E→E E | EE | (E) | i，文法的句子: i ii，其语法树如下：
5.4.2 二义性的判定
这个问题是不可判定的。对某文法，若能找出一个句子对应两棵不同的语法树，则该文法必是二义性文法。
二义性文法可以改造为无二义性文法。
G1[E]: E → E E | E * E|( E )|i ，G1是二义性文法
G2[E]: E → E T|T，T → T*F|F，F →(E)|i，G2(E)是无二义性文法，两者等价。
六、 句型的分析（重点）
6.1 基本概念
句型分析问题：如何知道所给定的字符串是文法的句型。
句型的分析：就是识别一个符号串是否为某文法的句型，是某个推导的构造过程。或者说，是否能为一个符号串构造一颗语法树。
语法分析树（或分析树）：就是语法树。
分析程序（或识别程序）：完成句型分析的程序。分析算法又称为识别算法。
6.2 自上而下的分析方法
从开始符号出发，构造最左推导的过程。即从树根出发，利用推导生成语法树的过程。
例如：
文法G[S]: (1) S→cAd (2)A→ab (3)A→a，输入串w=cabd
6.3 自下而上的分析方法
从输入串出发，进行最左归约，直到开始符号。从叶子结点出发，修剪语法树直至只剩开始符。
还是以上面的文法为例：
首先选择ab，然后用A替换，即把 ab 归约到 A。
6.4 句型分析的有关问题
6.4.1 自上而下的句型分析
文法G[S]: (1) S→cAd (2)A→ab (3)A→a，输入串w=cabd，根据自上而下的推导，我们构造出第一个直接推导SRightarrow cAd，接着拓展非终结符A ，这时有多种选择，如果我们用产生式（3）推导，我们可以发现构造不出w = cabd ，所以是个错误推导。面对这种情况，需要退回去，试试另外一种选择，这种方式称为回溯，但是这种方法效率极低。
6.4.2 自下而上的句型分析
在归约的时候，同样也会遇到多种选择的情况，如果用（3）将 a 归约成 A，则会出错，必须用（2）进行归约。在一种叫做规范归约的分析方法中，我们将这些能够正确归约的子串称为可归约串，也称为句柄。
下面介绍三个重要的概念：
overset*Rightarrow 指左部可以经过0步或多步推导得到右部，overset Rightarrow 指左部可以经过1步或多步推导得到右部
- 短语： 若Ｓoverset*Rightarrow αＡδ，且Aoverset Rightarrowβ，则称 β 是句型 αβδ 相对于非终结符号 A 的短语。
- 直接短语：若Ｓoverset*Rightarrow αＡδ 且 ARightarrowβ，则称β是句型 αβδ 相对于非终结符号A的直接短语。
- 句柄： 一个句型的最左直接短语称为该句型的句柄。（此概念只适用于右句型）
6.4.3 利用语法树寻找短语、句柄等方法
句型η的语法树有若干个内部节点（包括根节点）每个内部节点对应一棵以该内部节点为根的子树。
如果一棵子树只有父子两代（两层节点），则称该子树为直接子树。
如果一棵子树的根标记为A，且将此子树的叶节点 标记自左至右排列所形成的符号串为β，则β是句型 η 相对于A的一个短语。
如果子树是一棵直接子树，则β是句型 η 相对于A的一个直接短语，最左直接子树对应该句型的句柄。
