【编译原理】高级语言及其语法描述
编译程序要对程序进行正确的翻译，首先要对程序设计语言本身进行精确地定义和描述。对语言的描述是从三个方面来考虑（精简地说）：
语法：是对语言结构的定义（什么样的符号序列是合法的）；定义语言的词法和语法的形式规则; 语义：是描述语言的含义；定义语言的单词符号和语法单位的意义; 语用：是从使用的角度去描述语言。定义程序设计技术和语言成分的使用方法，它使语言的基本概念与语言的外界（如数学概念或计算机的对象和操作）联系起来比如说赋值语句 s = 2* 3.1416* r* (r+ h)的非形式化的描述如下：
语法：赋值语句由一个变量、后随赋值号“＝”、后跟一个表达式构成；
语义：首先计算语句右部表达式的值，然后把所得结果送入左部变量中；
语用：赋值语句可用来计算和保存表达式的值。
程序设计语言的定义是语言编译程序实现的基础，是语言使用者的用户手册；程序语言是符号语言，即一个记号系统，它主要有语法、语义和语用等三方面定义。
1.语法
任何语言程序都可看成是一定字符集（字母表）上的一字符串（有限序列）。
语言的语法规则定义了程序的形式结构，语法规则是指这样的一组规则，用它可以形成和产生一个格式（合法）的程序。这些规则的一部分称为词法规则，另一部分称为语法规则（或产生规则）。
字母表是一个有限的字符集，字符集中的字符是语言程序中可能出现的字符，它们是语言程序单词的组成部分。
词法规则定义了语言程序中单词符号的形成规则。即什么样的字符串是一个合法的单词。如标识符、数值常量、运算符等单词的构成规则。描述词法规则和进行词法分析的有效工具是正规式、正规文法和有限状态自动机理论。
语法规则定义了语言程序中语法单位的形成规则。一般语言的语法单位有表达式、语句、分程序、函数、过程和程序等。描述语法规则和进行语法分析的有效工具是`上下文无关文法。
语法规则和词法规则定义了程序的形式结构，定义语法单位的意义属于语义问题。
2.语义
对于一个语言来说，不仅要给出它的词法、语法规则，而且要定义它的单词符号和语法单位的意义。这就是语义问题。离开语义，语言只不过是一堆符号的集合。
语言的语义是指这样的一组规则，使用它可以定义一个程序的意义。这些规则称为语义规则。
程序语言的每个组成成分（语法范畴）均有抽象逻辑和计算机实现两方面的意义。前者描述在数学上的逻辑意义，后者注重其在计算机内的表示和实现的可能性与效率。
语义的描述方法有两种。一种是自然语言描述，但是其存在隐藏错误、二义性和不完整性的缺陷。另外一种是形式描述。
形式语义学有操作语义学、代数语义学、公理语义学、指称语义学等许多分支，它们分别用不同的形式系统来描述语义问题，但是目前还没有一种公认的形式系统，因此也还没有实用的语义自动分析方法。
目前编译程序中常用的语义分析方法是一种基于属性文法的语法制导翻译。
即在语法分析的同时对其中识别出的语法单位进行语义的分析与翻译工作；在描述文法的同时为定义的语法范畴加上它们的属性计算规则，属性可以是语法范畴的类型、地址、取值、执行动作等信息。
不过在本科生阶段，编译原理不会过多涉及到形式语义学，但是属性文法是需要学习的。其他内容，研究生阶段可能会需要学习。
高级语言可分为以下几类：
一、强制式语言（Imperative Language）也称过程式语言，特点是命令驱动，面向语句。如C、pascal属于这类语言。
二、应用式语言（Applicative Language）也称函数式注重程序所表示的功能，程序的开发过程是从已有的函数出发构造更复杂的函数，程序的执行即函数的嵌套或递归调用。如LISP、 ML属于这类语言。
三、基于规则的语言（Rule-based Language）也称逻辑程序设计语言，程序的执行过程是检查一定的条件（谓词逻辑表达式），条件满足则执行适当的动作。如Prolog属于这类语言。
四、面向对象语言（Object-Oriented Language）特点是支持抽象、封装性、继承性、多态性和动态绑定。程序设计的方法是将数据和操作封装在一起构成对象，对简单对象进行扩充、继承从而构造更复杂的对象，通过向对象发送消息获得动作的执行。如C++、Java、C#属于这类语言。
2、数据类型与操作一个数据类型通常包括以下三个要素：
用于区别类型的数据对象的属性；
这种类型的数据对象可以具有的值；
可以作用于类型的数据对象的操作。
程序设计语言从初始到复杂：
一、初等数据类型
数值数据、逻辑数据（布尔类型）、字符数据、指针类型。
二、数据结构
数组：由同一类型数据所组成的 n 维矩形结构。可分为确定数组和可变数组；数组的内情向量包括：首地址、维数、各维的上下限及元素类型。 记录：由已知类型（可以不同）的数据组合起来的结构。记录中每个域的 OFFSET 是它相对于记录首地址的地址位移量。 字符串、表格、栈和队列：数组或记录组合的访问受限的复合结构。关于标识符和名字:
虽然名字和标识符在形式上往往难于区分，但这两个概念是有本质区别的。例如，对于‘PI’，我们有时说它是一个名字，有时又说它是一个标识符。标识符是一个没有意义的字符序列，但名字却有明确的意义和属性。作为标识符的PI，无非是两个字母的并置，但作为名字的PI,常常被用来代表圆周率。在髙级语言中常用“局部名”、“全局名”之称，但 少有“局部标识符”、“全局标识符”之分。
除了提供数据的表示、构造及运算机制外，程序设计语言还有可执行的语句。控制结构定义了语句的执行次序，语言所提供的控制结构的集合对可读和可维护的软件的编写有很大影响。
（1）表达式
表达式是由运算量和运算符组成的。运算量亦称操作数，可以是数据引用或函数调用；运算符有算术运算符、逻辑运算符、关系运算符等，运算符之间有规定的优先级和结合律。
（2）语句
1、赋值句：变量名 = 表达式
2、控制语句：无条件转移语句、条件语句、循环语句、过程调用语句、返回语句
3、说明语句：用于定义名字的性质。
4、简单句和复合句：语句1；语句2；语句3；……
这几个概念为后面的内容做出了铺垫。
（1）字母表和符号串
1.字母表（alphabet）
2.符号（字符）（symbol）
3.符号串（string）
（2）符号串的运算
1.符号串的连结
2.集合的乘积
3.符号串的幂运算
4.集合的幂运算
5.集合 A 的正闭包 A+ 与闭包 A*
下面依次看这些内容：
字母表和符号串
（1）字母表 alphabet
字母表是元素的非空有穷集合
【例如】 ∑ = {a,b,c}
∑是字母表，由 a,b,c 三个元素组成。
字母表中至少包含一个元素，字母表中的元素，可以是字母、数字或其他符号。
不同的语言有不同的字母表。
英文的字母表是26个字母、数字和标点符号的集合；C 语言的字母表是字母、数字和若干专用符号组成。
（2）符号（字符）symbol
字母表中的元素称为符号，或称为字符。
【例如】 ∑ = {a,b,c}
a,b,c 是字母表 ∑ 中的符号。
（3）符号串（字）string
符号的有穷序列称为字符串。
【例如】设有字母表 ∑ = {a,b,c}，
则有符号串 a,b,ab,ba,cba,abc,…
(a,b,ab,ba,cba,abc 等都是字母表∑上的符号串)
符号串总是建立在某个特定字母表上的且只能由字母表上的有穷多个符号组成。
符号串中符号的顺序是很重要的，如 ab 和 ba 是字母表∑上的两个不同的符号串。
不包含任何符号的符号串，称为空符号串，用 ε (epsilon)表示，即空符号串由 0 个符号组成，其长度 |ε| = 0
下面看看符号串的运算
（1）符号串的连结 catenation
设 x 和 y 是符号串，则串 xy 称为它们的连结。即 xy 是将 y 符号串写在 x 符号串之后得到的符号串。
【例如】设 x ＝ abc，y = 10a，
则 xy ＝ abc10a
则 yx ＝ 10aabc
特别，对任意一符号串 x 有：
εx ＝ xε ＝ x
（2）集合的乘积 product
设 A 和 B 是符号串的集合，则 A 和 B 的乘积定义为：
AB = {xy | x ∈ A, y ∈ B}
即集合 AB 中的符号串是由 A 和 B 的符号串连接而成的。
【例如】设 A = {a,b}, B = {c,d}
则 AB ＝ {ac,ad,bc,bd}
因为对任意一符号串 x 有：
εx ＝ xε ＝ x
所以，对任意集合 A，有 {ε}A = A{ε} = A
这里要说一下 空集 Φ empty set
Φ 表示不含任何元素的空集 { }
Φ = { }
注意： ε是符号串，不是集合
{ ε} 表示由空符号串 ε 所组成的集合，但这样的集合不是空集Φ， 即Φ不包含空串。 ε ∈ Φ
（3）符号串的幂运算 power
（4）集合的幂运算
（5）集合A的正闭包A+与闭包A*
正闭包：Positive closure
闭包 ：Star closure（星闭包）
（1）形式语言
序列(字符串)的集合称为形式语言。
每个形式语言都是某个字母表上按某种规则构成的所有符号串的集合；任何一个字母表上符号串的集合均可定义一个形式语言。
【例如】
C 语言是具有基本符号字母表上的符号串的集合。每个 C 语言程序是基本符号的符号串。
形式语言的描述有两种方法：
第一种方法是当语言为有穷集合时，用枚举法来表示语言。
【例】设有字母表 A={a,b,c},则
L1 ＝ {a,b,c}
L2 ＝ {a,aa,ab,ac}
L3 ＝ {c,cc}
均表示字母表 A 上的一个形式语言。
由于这三个语言均是有限符号串的集合，可以枚举出其全部句子来表示该语言。
第二种是 当语言为无穷集合时，需要设计文法来描述无穷集合的语言。
文法是一种形式规则
（2）文法的形式定义
1、规则
规则的作用是告诉如何用规则中的符号串生成语言中的序列。一组规则规定了一个语言的语法结构。
产生式中的符号
非终结符：非终结符号（也称语法变量）用来代表语法范畴。例如，“算术表达式”、“布尔表达式”、“賦值句”、“分程序”、“过程”等，它们都是现今程序语言常见的语法范畴。出现在产生式左部能派生出符号或符号串的那些符号，即每个非终结符表示一定符号串的集合。用大写字母表示或用尖括号把非终结符括起来。
终结符：是不属于非终结符的那些符号，它是组成语言的基本符号，是一个语言的不可再分的基本符号，只出现在产生式右部。通常用小写字母表示。
2、文法
VT 可以理解成一个符号的集合，就像英语的单词。
VN 可以理解成语法单位的集合 就像英语的语法单位，比如主语、谓语。
S是文法的开始符号
每一条规则是一条产生式，所有的规则的集合记成P。
产生式（也称产生规则或简称规则）是定义语法范畴的一种书写规则。
简化写法的约定：
3、语言的形式定义
（1）直接推导
（2）推导
4、广义推导
直接推导的长度为1，推导的长度大于等于1，广义推导的长度大于等于0
5、句型和句子
仅含终结符号的句型是一个句子。文法G所产生的句子的全体是一个语言。
6、语言
7、规范推导和规范归约
文法所定义的任一句型和句子，都可以根据文法推导出来，但同一个句型(句子)可以通过不同的推导序列推导出来，这是因为在推导过程中所选择非终结符的次序无关。
最左推导是指对于一个推导序列中的每一步直接推导 α=>β，都对 α 中的最左非终结符进行替换。
最右推导是指对于一个推导序列中的每一步直接推导 α=>β，都对 α 中的最右非终结符进行替换。
最右推导也称为规范推导，用规范推导推导出的句型称为规范句型。
每个句子都有规范推导，但对句型此结论并不成立。
归约是推导的逆过程，归约是与推导相对的概念，推导是把句型中的非终结符用规则的一个右部来替换的过程，而归约是句型中的某个子串用一个非终结符来替换的过程。
规范推导的逆过程，称为最左归约，也称为规范归约。
8、递归规则与文法的递归性
所谓递归规则，是指在规则的左部和右部具有相同的非终结符的规则。
如果文法中有规则 A→A… 称为规则左递归
如果文法中有规则 A→…A 称为规则右递归
如果文法中有规则 A→…A… 称为规则递归
文法的递归性，是指对文法中任一非终结符，若能建立一个推导过程，在推导所得的符号串中又出现了该非终结符本身，则文法是递归的，否则是无递归性的。
文法中使用递归规则，使得能用有限的规则去定义无穷集合的语言。
下面的情况比较特殊
文法中使用了递归规则，使得可用有限的规则去刻画无穷集合的语言。
若不用递归规则来定义文法，需要用无穷多条规则去表示无穷集合的语言。
当一个语言是无穷集合时，则定义该语言的文法一定是递归的。
程序设计语言都是无穷集合，因此描述它们的文法必定是递归的。
9、短语、直接短语和句柄
短语、直接短语和句柄 是后面章节的内容，这里不懂没关系
首先看一下短语和直接短语
短语是句型的一部分
句柄
一个句型的最左直接短语称为该句型的句柄。
句柄特征：
(1)它是直接短语，即某规则右部
(2)它具有最左性。
注意：
短语、直接短语和句柄都是针对某一句型的，特指句型中的哪些符号串能构成短语和直接短语，离开具体的句型来谈短语、直接短语和句柄是无意义的。
1、推导树的生成
（1）语法树的生成
语法树的构造是从文法的开始符号出发，构造一个推导的过程，因为文法的每一个句型(句子)都存在一个推导，所以文法的每个句型(句子)都有一棵对应的语法树。
举个例子：
方法一：
以识别符号作为根结点，从它开始对每一步直接推导向下画一分支，分支结点的标记是直接推导中被替换的非终结符的名字，按此方法逐步向下，画出每一步直接推导对应的分支直到对该语法树再无分支可画时，构造过程结束。
方法二：
语法树中从左到右的末端结点构成了有该语法树所表示的那个推导推出的符号串。
句型 (i+i)*i-i 的最左、最右推导得到的语法树完全相同，
也就是说，一棵语法树表示一个句型的种种可能的(但未必是所有的)不同推导过程。
（2）子树
语法树的子树是由某一个结点连同所有分支组成的部分。
参考上面的推导树
（3）简单子树
语法树的简单子树是指只有单层分支的子树。
（4）子树与短语的关系
根据子树的概念，句型的短语、直接短语和句柄的直观解释如下：
短语：子树的末端结点形成的符号串是相对于子树根的短语。
直接短语：简单子树的末端结点形成的符号串是相对于简单子树根的直接短语。
句柄：最左简单子树的末端结点形成的符号串是句柄。
【例】对文法G[E]，用语法树求句型(T+i)*i-F 的短语、直接短语和句柄。
2、文法的二义性
对应文法 G 中任一句型的推导序列，总能构造一棵语法树。
文法 G[E]：E→ E + E | E﹡E | (E) | i
该文法的一个句子 i*i+i 有两个不同的最左推导，对应两棵不同的语法树。
如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。也就是说，若一个文法存在某个句子，它有两个不同的最左推导或有两个不同的最右推导，则称这个文法是二义的.
二义性的文法将给编译程序的执行带来问题。对于二义性文法的句子，当编译程序对它的结构进行语法分析时，就会产生两种甚至多种不同的理解。语法结构上的不确定性，必将导致语义处理上的不确定性。
解决方法之一：利用文法的等价性来消除文法的二义性。
3、文法二义性的消除
(1) 不改变文法中原有的语法规则，仅加进一些语法的非形式规定。
【例】文法 G：E → E + E | E﹡E | (E) |i
不改变已有的四条规则，仅加进运算符的优先顺序和结合规则，即 * 优先+，+、* 服从左结合。
这样，对于文法 G[E] 中的句子 i*i+i 只有唯一的一棵语法树，从而避免了文法的二义性。
(2) 构造一个等价的无二义性文法；即排除二义性的规则，改写原有的文法。
例如，文法 G：E → E + E | E﹡E | (E) |i
1、想要让一个规则结合性弱；就让它出现在推导序列前面（语法树的上层）；
2、想要让一个规则结合性强；就让它出现在推导序列后面（语法树的下层）；
具体做法：引入非终结符
语言的二义性是指不存在一个无二义的文法 G，使得L(G)就是语言本身。
注意：文法的二义性和语言的二义性是两个不同的概念。可能有两个不同文法的 G 和 G’，其中一个是二义的而另一个是无二义的，但是有 L(G) = L(G’)。
对于一个程序语言来说，常常希望它的文法是无二义的，因为希望对它的每个语句的分析是唯一的。
二义性问题是不可判定的。即不存在一个算法，能在有限步骤内确切的判定一个文法是否为二义的。
4、文法和语言的分类
Chomsky 于 1956 年建立形式语言的理论，形式语言的理论发展得很快。
对计算机科学有着深刻的影响；特别是对如下方面有重大的作用：
Chomsky把文法分成四种类型，即 0型、1型、2型和3型。这几类文法的差别在于对产生式的形式施加的限制从 0型到 3型依次增强，但它们表达语言的能力则依次减弱。
0 型文法(无限制文法，短语文法)
由定义可见，α 和 β 均是文法的终结符和非终结符组成的符号串，且 β 可能为空，而 α 不能为空，即允许 |α|>|β|
由于 0 型文法没有加任何限制条件，故又称为无限制文法，相应的语言称为无限制语言。
非终结符 A 永远消不掉，不能终结。
1 型文法(上下文有关文法)
在推导过程中，连续 n 个 a 一直是最前面，不能生成连续 n 个 b 和紧跟 n 个 c，但是可以生成相互间隔的 n 个 B 和 c。
使用规则 cB→Bc 可以将所有穿插的 c 中的B 向前移。
然后使用规则 bB→bb 消除掉所有的 B。
aaabbbccc 的推导过程
最左推导：
规则 cB→cc和 bB→bc 是把 B 换成 c
规则 cA→Ac 是把穿插的 c 中的 A 向前移。
最终使用规则 bA→bb 消除掉所有的 A，换成 b。
2 型文法(上下文无关文法)
由定义可见，利用规则将 A 替换成 β 时，与 A 的上下文环境无关，即无需考虑 A 在上下文中出现的情况。
故又称为上下文无关文法，相应的语言称为上下文无关语言。
通常定义程序设计语言的文法是上下文无关文法，因此，上下文无关文法及相应语言是我们主要的研究对象。
有 a 就有 B
有 b 就有 A
或： S → aB | bA A → a | aS | Sa B → b | bS | Sb
3 型文法(正规文法)
右线形文法和左线形文法都称为 3 型文法或正规文法，3型文法描述的语言称为 3 型语言或正规语言。
通常定义程序设计语言词法规则的文法是正规文法。
通过几个特殊的例子来体会语言与文法的关系。
有关文法的使用限制和变换
作为程序语言的上下文无关文法，对它们限制以下几点：
第二点限制的解释
(2’)
每个非终结符 P 必须都有用处。这一方面意味着，必须存在含 P 的句型；也就是从开始符号 S 出发，存在推导 S > αPβ
以后所讨论的文法均假定满足上述两个条件。这种文法称为化简了的文法。
若程序设计语言的文法含有多余规则，其中必定有错误存在，因此检查文法中是否含有多余规则是很重要的。
最后附上一个读音表。
作者：沉晓
