【编译原理】⾼级语⾔及其语法描述
⽂章⽬录
⾼级语宫及其语法描述
（⼀）程序语⾔的定义
编译程序要对程序进⾏正确的翻译，⾸先要对程序设计语⾔本⾝进⾏精确地定义和描述。对语⾔的描述是从三个⽅⾯来考虑（精简地说）：
语法：是对语⾔结构的定义（什么样的符号序列是合法的）；定义语⾔的词法和语法的形式规则;
语义：是描述语⾔的含义；定义语⾔的单词符号和语法单位的意义;
语⽤：是从使⽤的⾓度去描述语⾔。定义程序设计技术和语⾔成分的使⽤⽅法，它使语⾔的基本概念与语⾔的外界（如数学概念或计算机的对象和操作）联系起来
⽐如说赋值语句 s = 2* 3.1416* r* (r+ h)的⾮形式化的描述如下：
语法：赋值语句由⼀个变量、后随赋值号“＝”、后跟⼀个表达式构成；
语义：⾸先计算语句右部表达式的值，然后把所得结果送⼊左部变量中；
语⽤：赋值语句可⽤来计算和保存表达式的值。
程序设计语⾔的定义是语⾔编译程序实现的基础，是语⾔使⽤者的⽤户⼿册；程序语⾔是符号语⾔，即⼀个记号系统，它主要有语法、语义和语⽤等三⽅⾯定义。
1.语法
任何语⾔程序都可看成是⼀定字符集（字母表）上的⼀字符串（有限序列）。
语⾔的语法规则定义了程序的形式结构，语法规则是指这样的⼀组规则，⽤它可以形成和产⽣⼀个格式（合法）的程序。这些规则的⼀部分称为词法规则，另⼀部分称为语法规则（或产⽣规则）。
字母表是⼀个有限的字符集，字符集中的字符是语⾔程序中可能出现的字符，它们是语⾔程序单词的组成部分。
词法规则定义了语⾔程序中单词符号的形成规则。即什么样的字符串是⼀个合法的单词。如标识符、数值常量、运算符等单词的构成规则。描述词法规则和进⾏词法分析的有效⼯具是正规式、正规⽂法和有限状态⾃动机理论。
语法规则定义了语⾔程序中语法单位的形成规则。⼀般语⾔的语法单位有表达式、语句、分程序、函数、过程和程序等。描述语法规则和进⾏语法分析的有效⼯具是`上下⽂⽆关⽂法。
语法规则和词法规则定义了程序的形式结构，定义语法单位的意义属于语义问题。
2.语义
对于⼀个语⾔来说，不仅要给出它的词法、语法规则，⽽且要定义它的单词符号和语法单位的意义。这就是语义问题。离开语义，语⾔只不过是⼀堆符号的集合。
语⾔的语义是指这样的⼀组规则，使⽤它可以定义⼀个程序的意义。这些规则称为语义规则。
程序语⾔的每个组成成分（语法范畴）均有抽象逻辑和计算机实现两⽅⾯的意义。前者描述在数学上的逻辑意义，后者注重其在计算机内的表⽰和实现的可能性与效率。
语义的描述⽅法有两种。⼀种是⾃然语⾔描述，但是其存在隐藏错误、⼆义性和不完整性的缺陷。另外⼀种是形式描述。
形式语义学有操作语义学、代数语义学、公理语义学、指称语义学等许多分⽀，它们分别⽤不同的形式系统来描述语义问题，但是⽬前还没有⼀种公认的形式系统，因此也还没有实⽤的语义⾃动分析⽅法。
⽬前编译程序中常⽤的语义分析⽅法是⼀种基于属性⽂法的语法制导翻译。
即在语法分析的同时对其中识别出的语法单位进⾏语义的分析与翻译⼯作；在描述⽂法的同时为定义的语法范畴加上它们的属性计算规则，属性可以是语法范畴的类型、地址、取值、执⾏动作等信息。
不过在本科⽣阶段，编译原理不会过多涉及到形式语义学，但是属性⽂法是需要学习的。其他内容，研究⽣阶段可能会需要学习。
（⼆）⾼级语⾔的⼀般特性
阿凡提和皮皮驴1、⾼级语⾔的分类
⾼级语⾔可分为以下⼏类：
⼀、强制式语⾔（Imperative Language）也称过程式语⾔，特点是命令驱动，⾯向语句。如C、pascal属于这类语⾔。
⼆、应⽤式语⾔（Applicative Language）也称函数式注重程序所表⽰的功能，程序的开发过程是从已有的函数出发构造更复杂的函数，程序的执⾏即函数的嵌套或递归调⽤。如LISP、 ML属于这类语⾔。练瑜伽的注意事项
三、基于规则的语⾔（Rule-based Language）也称逻辑程序设计语⾔，程序的执⾏过程是检查⼀定的条件（谓词逻辑表达式），条件满⾜则执⾏适当的动作。如Prolog属于这类语⾔。
四、⾯向对象语⾔（Object-Oriented Language）特点是⽀持抽象、封装性、继承性、多态性和动态绑定。程序设计的⽅法是将数据和操作封装在⼀起构成对象，对简单对象进⾏扩充、继承从⽽构造更复杂的对象，通过向对象发送消息获得动作的执⾏。如C++、Java、C#属于这类语⾔。我为祖国添光彩
2、数据类型与操作
⼀个数据类型通常包括以下三个要素：
⽤于区别类型的数据对象的属性；
这种类型的数据对象可以具有的值；
可以作⽤于类型的数据对象的操作。
程序设计语⾔从初始到复杂：
⼀、初等数据类型
数值数据、逻辑数据（布尔类型）、字符数据、指针类型。
⼆、数据结构
1. 数组：由同⼀类型数据所组成的 n 维矩形结构。可分为确定数组和可变数组；数组的内情向量包括：⾸地址、维数、各维的上下限及
元素类型。
2. 记录：由已知类型（可以不同）的数据组合起来的结构。记录中每个域的 OFFSET 是它相对于记录⾸地址的地址位移量。
3. 字符串、表格、栈和队列：数组或记录组合的访问受限的复合结构。
关于标识符和名字:
虽然名字和标识符在形式上往往难于区分，但这两个概念是有本质区别的。例如，对于‘PI’，我们有时说它是⼀个名字，有时⼜说它是⼀个标识符。标识符是⼀个没有意义的字符序列，但名字却有明确的意义和属性。作为标识符的PI，⽆⾮是两个字母的并置，但作为名字的PI，常常被⽤来代表圆周率。在髙级语⾔中常⽤“局部名”、“全局名”之称，但 少有“局部标识符”、“全局标识符”之分。
3、语句与控制结构
除了提供数据的表⽰、构造及运算机制外，程序设计语⾔还有可执⾏的语句。控制结构定义了语句的执⾏次序，语⾔所提供的控制结构的集合对可读和可维护的软件的编写有很⼤影响。
（1）表达式
藏族风俗习惯
表达式是由运算量和运算符组成的。运算量亦称操作数，可以是数据引⽤或函数调⽤；运算符有算术运算符、逻辑运算符、关系运算符等，运算符之间有规定的优先级和结合律。
（2）语句
1、赋值句：变量名 = 表达式
2、控制语句：⽆条件转移语句、条件语句、循环语句、过程调⽤语句、返回语句
3、说明语句：⽤于定义名字的性质。
4、简单句和复合句：语句1；语句2；语句3；……
（三）程序语⾔的语法描述
1、⼏个重要概念
这⼏个概念为后⾯的内容做出了铺垫。
（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*