文法和语言的基本知识

时间：2021-09-29 01:50:45

本博文中，将概述高级程序语言的结构和主要的共同特征，并介绍程序语言的语法描述方法。主要内介绍内容是程序设计语言的定义，高级语言的一般特性，高级语言的语法描述，上下文无关文法，语法分析树和二义性，乔姆斯基文法体系。

程序语言的定义

语法

任何语言程序都可看成是一定字符集（称为字母表）上的一字符串（有限序列）。但是，什么样的字符串才算是一个合式的程序呢？所谓一个语言的语法是指这样的一组规则，用它可以形成和产生一个合式的程序。这些规则的一部分称为词法规则，另一部分称为语法规则（或产生规则）。

例如，字符串0.5*X1+C，通常被看成是常数0.5、标识符X1和C，以及算符“＊”和＋所组成的一个表达式。其中常数‘0.5’，标识符‘X1’和‘C’，算符‘*’和‘＋’称为语言的单词符号，而表达式‘0.5*X1+C’称为语言的一个语法范畴，或语法单位。

语义

**对于一个语言来说，不仅要给出它的词法、语法规则，而且要定义它的单词符号和语法单位的意义。这就是语义问题。离开语义，语言只不过是一堆符号的集合。在许多语言中有着形式上完全相同的语法单位，但含义却不尽相同。例如在ALGOL和FORTRAN中，符号串

X＋F（X）＋Y

都代表一个“算术表达式”，但含义有区别。ALGOL规定按左结合的规则计算这个表达式的值，FORTRAN容许使用交换律和结合律来计算其值；ALGOL容许函数F（X）的计值有副作用，但FORTRAN禁止对所在的表达式环境产生副作用。又例如，许多语言都具有如下形式的语句：
for i:=E1 step E2 until E3 do S

但其含义各有不同。对于编译来说，只有了解程序的语义，我们才知道应把它翻译成什么样的目标指令代码。所谓一个语言的语义是指这样的一组规则，使用它可以定义一个程序的意义。这些规则称为语义规则。阐明语义要比阐明语法难得多。现在还没有一种公认的形式系统，借助于它可以自动地构造出实用的编译程序。目前大多数编译程序普遍采用的一种方法，即基于属性文法的语法制导翻译方法，虽然这还不是一种形式系统，但它还是比较接近形式化的。

一个程序语言的基本功能是描述数据和对数据的运算。所谓一个程序，从本质上来说是描述一定数据的处理过程。

在现今的程序语言中，自上而下看层次结构：顶端是程序本身，它是一个完整的执行单位。一个程序通常是由若干个子程序或分程序组成的，它们常常含有自己的数据（局部名）。子程序或分程序是由语句组成的。而组成语句的成分则是各种类型的表达式。表达式是描述数据运算的基本结构，它通常含有数据引用、算符和函数调用。自下而上看上述层次结构：我们希望通过对下层成分的理解来掌握上层成分，从而掌握整个程序。在下节中我们将综述程序语言各层次的结构和意义。

程序语言的每个组成成分都有（抽象的）逻辑和计算机实现两方面的意义。当从数学上考虑每个组成成分时，我们注重它的逻辑意义。当从计算机这个角度来看时，我们注重它在机内的表示和实现的可能性与效率。例如，一个表示实数的名字，从逻辑上说，可以看成是一个变量或一个可用于保存实数的场所；从计算机实现上说，可看成是一个或若干个相继的存储单元，这些单元的每位都有特殊的解释（如符号位、阶码和尾数），它们能表示一个一定大小和精度的数值。

高级语言的一般特性

高级语言的分类

从不同的角度看，对高级程序设计语言有不同的分类方法。如果我们从语言范型分类，当今的大多数程序设计语言可划分为以下四类：

强制式语言

强制式语言(Imperative Languge)也称过程式语言。其特点是命令驱动，面向语句。一个强制式语言程序由一系列的语句组成，每个语句的执行引起若干存储单元中的值的改变。这种语言的语法形式通常具有如下形式：

语句1；
语句2；
…
语句n；

许多广为使用的语言，如FORTRAN、C、Pascal，Ada等等，属于这类语言。

应用式语言

与强制式语言不同的是，应用式语言（Applicative Language）更注重程序所表示的功能，而不是一个语句接一个语句地执行。程序的开发过程是从前面已有的函数出发构造出更复杂的函数，对初始数据集进行操作直至最终的函数可以用于从初始数据计算出最终的结果。这种语言通常的语法形式是：

函数n（…函数2（函数1（数据））…）

因此，这种语言也称函数式语言。LISP和ML属于这种语言。

基于规则的语言

基于规则的语言（Rule-based Language）程序的执行过程是：检查一定的条件，当它满足值，则执行适当的动作。最有代表性的基于规则语言是Prolog，它也称逻辑程序设计语言，因为它的基本允许条件是谓词逻辑表达式。这类语言的语法形式通常为：

条件1→动作1
条件2→动作2
…
条件n→动作n

面向对象语言

面向对象语言（Object-Oriented Language）如今已成为最流行、最重要的语言。它主要的特征是支持封装性、继承性和多态性等。把复杂的数据和用于这些数据的操作封装在一起，构成对象；对简单对象进行扩充、继承简单对象的特性，从而设计出复杂的对象。通过对象的构造可以使面向对象程序获得强制式语言的有效性，通过作用于规定数据的函数的构造可以获得应用式语言的灵活性和可靠性。

程序结构

一个高级语言程序通常由若干子程序段（过程、函数等）构造，许多语言还引入了类、程序包等更高级的结构。下面我们从FORTRAN、Pascal、Ada、Java为例，说明程序结构。

FORTRAN

一个FORTRAN程序由一个主程序段和若干个（可以是0个）辅程序段组成。

PROGRAM MAIN
…
END
SUBROUTINE SUB1
…
END
…
SUBROUTINE SUBn
…
END

辅程序段可以是子程序、函数段或数据块。每个程序段由一系列说明句和执行句组成。各段可以独立编译，这对于模块设计甚为方便。
一个FORTRAN程序的各个程序段所定义（说明）的各种名字通常是彼此独立的。同一个标识符在不同的程序段中一般都是代表不同的名字，也就是说，代表不同的存储单元，各程序段对它们的引用或赋值是彼此无关的。但是，不同程序段里的同名公用块（common block）却代表同一个存储区域（称为公用区，common area）。因此，出现在COMMON语句中的名字所代表的单元在其它程序段中也可以引用（通过该段中定义在同一个COMMON块里的相应单元的名字）。所以说，公用区具有全局性。不出现在COMMON中的名字所代表的单元具有局部性。

Pascal

Pascal是一个允许子程序嵌套定义的语言。一个Pascal程序可以看作是操作系统调用的一个子程序，而子程序中又可以定义别的子程序。

program main
…
procedure P1;
…
procedure P11;
…
begin
…
end;
begin
…
end;
procedure P2;
…
begin
…
end;
begin
…
end.

Pascal这种嵌套结构中允许同一标识符在不同的子程序中表示不同的名字。关于名字的作用域的规定是：
(1). 一个在子程序B1中说明的名字X只在B1中有效（局部于B1）；
(2). 如果B2是B1的一个内层子程序且B2中对标识符X没有新的说明，则原来的名字X在B2中仍然有效。如果B2对X重新作了说明，那么，B2中对X的任何引用都是指重新说明过的这个X。
换言之，标识符X的任一出现（除出现在说明句的名表中外）都意味着引用某一说明句所说明的那个X，此说明句同所出现的X共处在一个最小子程序中。这个原则称为“最近嵌套原则”。

Ada

在Ada中引入了程序包（package），它可以把数据和操作代码封装在一起，支持数据抽象。一个程序包分为两部分：
(1) 可见的规范说明部分，它定义了程序包外面可以访问的对象。
(2) 程序包体，它实际定义程序包的实现细节。

package STACKS is
type ELEM is private;
type STACK is limited private;
procedure push (S: in out STACK; E: in ELEM);
procedure pop (S: in out STACK; E: out ELEM);
…
end STACK;
package body STACK is
procedure push(S: in out STACK; E: in ELEM);
begin
……实现细节
end push;
procedure pop (S: in out STACK; E: out ELEM);
begin
……实现细节
end pop;
end;

在Ada程序包规范说明中，如果一个类型被定义为私有（private）类型，则它既不允许用户在该程序包外访问此类型，又对用户隐蔽此类型数据结构的具体细节。如果一个类型被定义为受限私有（limited private）类型，则对该类型对象的操作仅限于相应程序包规范说明部分说明的那些，连一般私有类型所允许的预定义赋值和测试相等的操作也不允许，以严格限制对该类型对象的访问。

Java

Java是一种面向对象的高级语言，它很重要的方面是类（Class）及继承(Inheritance)的概念，同时支持多态性(Polymorphism)和动态绑定(Dynamic binding)等特性。

class Car{
int color_number;
int door_number;
int speed;
…
push_break ( ) {
…
}
Add_oil ( ) {
…
}
}
class Trash_Car extends car {
double amount;
fill_trash ( ) {
…
}
}

一个类把有关数据及其操作（方法）封装在一起构成一个抽象数据类型。一个子类继承其父类的所有数据与方法，并且可以加入自己新的定义。
在Java中，变量和方法的定义之前可以加入public、protected、private等修饰字，以限制其它类的对象对于这些变量数据的存取以及类中方法的使用。如果一个类定义中的变量或方法前面加上public，那么就表示只要其它类、对象等可以看到这个类的话，它们就可以存取这个变量的数据，或者使用这个方法；如果一个类的变量或方法前面加上protected，那么只有这个类的子孙类可以直接存取这个变量数据或调用这个方法；如果在变量或方法前面加上private，那么任何其它的类都不能直接引用这个数据，或调用这个方法。

数据类型与操作

对大多数程序设计语言而言，“数据”这个概念是最基本的。强制式程序设计语言使用一系列的语句修改存储在计算机存储器中的数据值。在这里，变量的概念可以认为是计算机存储地址的抽象。程序设计语言所提供的数据及其操作设施对语言的适用性有很大影响。一个数据类型通常包括以下三种要素：

1. 用于区别这种类型数据对象的属性；
2. 这种类型的数据对象可以具有的值；
3. 可以作用于这种类型的数据对象的操作。

初等数据类型

一个程序语言必须提供一定的初等类型数据成分，并定义对于这些数据成分的运算。有些语言还提供了由初等数据构造复杂数据的手段。不同的语言含有不同的初等数据成分。常见的初等数据类型有：

  1. 数值数据 如整数、实数、复数以及这些类型的双长（或多倍长）精度数。对它们可施行算术运算（＋，－，*，/等）。
  2. 逻辑数据 多数语言有逻辑型（布尔型）数据，有些甚至有位串型数据。对它们可施行逻辑运算（and，or，not等）。
  3. 字符数据 有些语言容许有字符型或字符串型的数据，这对于符号处理是必须的。
  4. 指针类型 指针是这样一种类型的数据，它们的值指向另一些数据。尽管语法上可能不尽相同，但一般的意义是，假定P是一个指针，P:=addr（X）意味着P将指向X，或者说，P的值将是变量X的地址。有些语言中用P↑表示指针P的内容。在P:=addr（X）的情况下，如令P↑:=0.3，则意味着X的值为0.3.

程序语言所涉及的对象不外是数据、函数和过程等等。对于每个这种对象，程序员通常都用一个能反映它的本质的、有助于记忆的名字来表示和称呼它。例如，常常可以看到人们用WEIGHT来表示一个代表重量的实型数据，用INNERPRODUCT表示一个求内积的过程。在程序语言中各种名字都是用标识符表示的。所谓标识符系指由字母或数字组成的以字母为开头的一个字符串。
虽然名字和标识符在形式上往往难于区分，但这两个概念是有本质区别的。 例如，对于‘PI’，我们有时说它是一个名字，有时又说它是一个标识符。标识符是一个没有意义的字符序列，但名字却有明确的意义和属性。作为标识符的PI，无非是两个字母的并置，但作为名字PI，常常被用来代表圆周率。在高级语言中常用“局部名”、“全局名”之称，但少有“局部标识符”、“全局标识符”之分。

用计算机术语来说，每个名字可看成是代表一个抽象的存储单元，这个单元可含一位、一字节、一字或相继的许多个字。而这个单元的内容则认为是此名字（在某一时刻）的值。名字的值就是它所表示的一个具体对象。仅把名字看成代表一定的存储单元还是不够的，我们还必须同时指出它的属性。如果不指出名字的属性，它的值就无法理解。例如，设一个名字代表一个32位的存储单元，如果不指明属性，那么我们就不知道此单元的内容代表什么，不知道是代表一个整数、一个实数还是一个布尔值。名字的属性通常是由说明语句给出的。
有些名字似乎没有通常意义的值，例如过程名就是如此。但我们可以设想过程名具有某种代表输入－输出关系的“值”。

注意，在许多程序语言中，同一标识符在过程中的不同地点（如不同分程序）可用来代表不同的名字。在程序运行时，同一个名字在不同的时间也可能代表不同的存储单元（在递归的情形下）。反之，同一个存储单元也可能有好几个不同的名字（如FORTRAN中出现在EQUIVALENCE和COMMON语句里的名字）。

一个名字的属性包括类型和作用域。名字的类型决定了它能具有什么样的值，值在计算机内的表示方式，以及对它能施加什么运算。名字的作用域规定了它的值的存在范围。例如，一个Pascal名的作用域是那个包含此名的说明的过程，只有当这个过程运行时此名字才有对应的存储单元。
在多数的程序语言中，名字的性质是用说明句明确规定的。例如在Pascal中，说明句

X，Y：real；

规定了名字X、Y代表实型（简单）变量。即，X和Y各对应有一个标准长度的存储单元，其内容是浮点数，可对它们进行各种算术运算。

在某些语言中，名字的性质有时容许是隐约定的。例如在FORTRAN中，对未经说明句明显说明的名字，凡以I，J，…，N为首者均认为是代表整型的，否则为实型的。

某些语言既没有说明句也没有隐约定，如APL就是这样。在这种语言中，同一标识符在某一行中可能代表一个整型变量，而在另一行中则代表一个实型数组，因此，名字的性质只能在程序运行时“动态”地确定。也就是，“走到哪里，是什么，算什么”。

如果一个名字的性质是通过说明句或隐约定规则而定义的，则称这种性质是“静态”确定的。如果名字的性质只有在程序运行时才能知道，则称这种性质是“动态”确定的（我们以后常用“静态”和“动态”两词。凡编译时可以确定的东西称为“静态”的；凡必须推迟到程序运行时才能确定的东西称为“动态”的）。对于具有静态性质的名字，编译时应对它们引用的合法性进行检查。例如，假定I是整型变量，X是实型变量，混合加法运算I＋X在FORTRAN66中是不允许的，而在Pascal中则是认可的，但必须预先产生把I转换成实型量的代码。

对于具有动态性质的名字，应在程序运行时收集和确定它们的性质，并进行必要的类型转换。名字的动态性质对于用户来说是方便的，但对计算机实现来说则其效率较低。

数据结构

许多程序语言提供了一种可从初级数据定义复杂（高级）数据的手段。下面我们将概述几种常见的定义方式。
数组
从逻辑上说，一个数组是由同一类型数据所组成的某种n维矩形结构。沿着每一维的距离称为一个下标。每维的下标只能在该维的上、下限之内变动。数组的每个元素是矩形结构中的一个点，它的位置可通过给出每维的下标来确定。

数组的每个元素（也称下标变量）是由数组名连同各维的下标值命名的，如A[i1,i2,…,in]。根据数组的类型，每个数组元素在计算机中占有同样大小的存储空间。如果一个数组所需的存储空间大小在编译时就已知道，则称此数组是一个确定数组；否则，称为可变数组。

数组的存储表示有多种形式，最简单的一种是把整个数组按行（或按列）存放在一片连续存储区中。一般而言，假定对一个n维数组附上一个n位数码管显示器，每个管代表一个下标，每管显示的值在相应维的下限与上限之间变动。所谓按行存放意味着，当从数组的第一个元素开始扫描整个数组时，越是后面的下标（数码管）变化得越快。按列存放意味着越是前面的下标变化得越快。

有些程序语言，如FORTRAN，要求以列为序存放数组；另一些，如Pascal，通常以行为序；还有一些则取决于编译程序设计者的意愿。数组元素的地址计算和数组的存储方式密切相关。关于数组元素的地址计算公式，数据结构教材中有详细的介绍。编译程序要做的工作就是实现地址计算公式，使数组元素得到正确引用。

在编译过程中，当碰到数组说明时，必须把数组的有关信息记录在一个“内情向量”之中，以便以后计算数组元素的地址时引用这些信息。每个数组的内情向量必须包括：维数，各维的上、下限，首地址，以及数组（元素）的类型，等等。

对于确定数组来说，内情向量可登记在编译时的符号表中。对于可变数组，内情向量的一部（或全部）在编译时无法知道，只有在程序运行时才能计算出来。因此，编译程序必须为可变数组设置一定的空间，以便在运行时建立相应的内情向量。不论是对确定数组或可变数组，数组元素的地址计算公式都是一样的。
6. 记录
从逻辑上说，记录结构是由已知类型的数据组合起来的一种结构。一个记录结构通常含有若干个分量，每个分量称为记录的一个栏（或域field）。每个分量都是一个确定类型的数据，不同分量的数据类型可以不同。
记录结构是许多程序语言中的一类重要的数据结构。不同语言定义记录结构的方式也有不同。例如，Pascal语言采用下面形式定义记录：

CARD：record
NAME：array [1…20] of char;
AGE：integer;
MARRIED：boolean
end;

这个说明句定义了一个记录CARD。它是一个含有三个分量的记录结构：NAME，字符数组；AGE，整型量；MARRIED，布尔量。
当需要了解或更改某一卡片（如CARD）的某一栏信息时，一般可采用如下的复合名进行访问：CARD.NAME，CARD.AGE和CARD.MARRIED。例如，可使用下面三个语句来填写卡片：

CARD.NAME:=‘LI MING’;
CARD.AGE:=25;
CARD.MARRIED:=false

记录结构最简单的存储表示方式是连续存放。以上述的CARD为例，假定：目标机器按字节编址，每个字节存放一个字符；每个机器字包含四个字节，可存放一个整数，整数单元必须从字的边界开始（即地址码为4的倍数）；每个布尔量用一字节表示。那么，每张卡片（即CARD记录）需用25个字节。由于整型量AGE必须从字的边界开始，因此，每张卡片最好用28个字节，也就是7个字；NAME占5个字，AGE占1个字，MARRIED占1个字（浪费三个字节的零头）。这样一来1000张卡就需要7000个字。

记录结构的每个分量（域）所需占用的存储单元（字节）数称为该域的长度。当知道一个记录的地址后，通过每个域的长度就可算出各域的地址。因为我们容易推出每个域相对于记录结构起点的相对数OFFSET：此域之前各域长度的总和。例如，就CARD而言，NAME、AGE和MARRIED的相对数OFFSET分别为0、20和24。于是，假定CARD的首地址为a，那么，

  1. CARD·NAME 的地址为 a
  2. CARD·AGE 的地址为 a+20
  3. CARD·MARRIED 的地址为 a+24

7.字符串、表格、栈和队列

某些语言（如SNOBOL）把字符串作为一种基本数据类型，串的长度也不加限制。这种数据类型对于符号处理、公式处理是完全必须的。

有些语言（如LISP）特别适用于描述表格处理，因此表格就成为一种十分重要的数据类型。一个表格本质上是一组记录结构，它的每一栏可以是初等类型数据，也可以是一个指向别的记录结构的指示器。所谓线性表是指一组顺序化的记录结构。
有些语言提供了某种简易的手段，它使程序员可以方便地定义各式各样的栈和队列。有些语言，如Pascal虽没有明显地提供栈型的数据结构，但栈却是它的程序数据空间的基本组织形式。

三、抽象数据类型

为了增加程序的可读性和可理解性，提高可维护性，降低软件设计的复杂性，许多的程序设计语言提供了对抽象数据类型的支持。一个抽象数据类型包括：

  • 列表内容
  • 数据对象的一个集合；
  • 作用于这些数据对象的抽象运算的集合；
  • 这种类型对象的封装，即，除了使用类型中所定义的运算外，用户不能对这些对象进行操作。

在常用的程序设计语言中，Ada语言通过程序包（package）提供了数据封装的支持，Smalltalk、C++和Java语言则通过类（Class）对抽象数据类型提供支持。

语句与控制结构

除了提供数据的表示、构造及运算设施外，程序设计语言应该有可执行的语句。控制结构定义了语句在其中的执行次序，语言所提供的控制结构的集合对可读和可维护的软件的编写有很大的影响。

一、表达式

一个表达式是由运算量（亦称操作数，即数据引用或函数调用）和算符组成的。例如，算术表达式X＋Y是由二元（二目）算符‘＋’和运算量X、Y（数值数据）组成的。X和Y分别称为算符＋的左、右运算量（左、右操作数）。
在表达式中，一元算符通常写在它的运算量的前面，如－X和ØB，这种形式称为前缀形；但有些也写在运算量后面，如P↑（P为指示器），这种形式称为后缀形。在许多语言中，符号‘－’既用来表示一元算符“负”（如－X），又用来表示二元算符“减”（如X－Y）。
在多数程序语言中，二元算符一般都写在两个运算量中间，如X＋Y，这种形式称为中缀形式。但有的也采用后缀形式，即把算符写在运算量的后边，如把X＋Y写成XY＋。理论上说还有一种前缀形式，即把算符写在前面，把运算量写在后面，如把X＋Y写成＋XY。
对于多数程序语言来说，表达式的形成规则可概括为：

(1) 变量（包括下标变量）、常数是表达式。
(2)若E1、E2为表达式，q是一个二元算符，则E1qE2是表达式（一般采用中缀形式）。
(3)若E是表达式，q为一元算符，则qE（或Eq）是表达式。 (4) 若E是表达式，则（E）是表达式。

表达式中算符的运算顺序和结合性的约定大多和通常的数学习惯相一致。例如，对于算术表达式的计值过程一般都遵循：先乘除后加减，乘幂更优先。对于同级算符，优先的规则视具体情形而定，可采用先左后右（左结合）或先右后左（右结合）的运算顺序。例如

X＋Y*Z 等于X＋（Y*Z） *优先于＋
X-Y-Z 等于（X－Y）－Z 同级优先左结合
X-Y＋Z 等于（X－Y）＋Z 同级优先左结合
X**Y**Z 等于X**（Y**Z） 同级优先右结合

多数语言中，算术算符和逻辑算符的优先顺序一般规定如下（自高至低排列，同级算符列于同一行）：

算术算符 逻辑算符
乘幂 ( **或↑)
一元负 (－)
乘、除 （*，/，÷）
加、减 （＋，－）
关系符 （<, =, >, <=, <>, >=）
非 （Ø，not或·NOT·）
与 （Ù，&，and或·AND·）
或 （Ú，
隐含 （É或imp）
等值 （º，～或epui）

FORTRAN关于算符优先级的规定和上面所列的基本一致。事实上，不同的语言对算符优先级和结合性质的规定各有差异，有的甚至差异甚大。例如，APL规定所有算符都具有相同的优先级并一律服从右结合，于是，X－Y＋Z就意味着X－（Y＋Z）。ALGOL对于同级优先的算符要求严格服从自左至右运算规则，即左结合。例如X＋Y＋Z必须处理成（X＋Y）＋Z。FORTRAN对于满足左、右结合的算符可任取一种结合，例如，A＋B＋C可处理成（A＋B）＋C，也可处理成A＋（B＋C）；对于满足交换律的算符，左、右运算量的计算顺序也不加限制，例如A*B＋C*D也可处理成C*D＋B*A。

算符的代数性质（交换律、结合律和分配律）常常可用来优化目标程序的质量。但必须注意两点：

  • 第一，代数性质能引用到什么程度视具体语言的不同而不同。例如，在ALGOL中，若把A*B＋C*D处理成C*D＋B*A，则至少是对ALGOL不够忠实。
  • 第二，在数学上成立的代数性质在计算机上未必完全成立。交换律在计算机上一般是成立的，但结合律和分配律就未必成立（至少在结果的有效数位上常有差别）。例如，在计算机上，（A＋B）＋C＝A＋（B＋C）并不普遍成立。因此，在某些语言（如FORTRAN）中，为了保证运算结果的有效性，程序员应尽量用括号来组织表达式的计值顺序。

某些语言中容许对不同类型的数据进行运算，有些则禁止。例如0.5+3是一个正确的ALGOL表达式，但在标准FORTRAN（66）中是不能容忍的。如果容许对不同类型的数据进行运算，那就必须规定运算结果的性质，使得在编译时能够预先产生对运算量进行类型转换的目标代码。

二、语句

不同程序语言含有不同形式和功能的各种语句。从功能上说，语句大体可分执行性语句和说明性语句两大类。说明性语句旨在定义各种不同数据类型的变量或运算。执行性语句旨在描述程序的动作。执行语句又可分赋值句、控制句和输入/输出句。从形式上说，语句还可分为简单句、复合句和分程序等等。

1. 赋值句
不同语言的赋值句有不同的语法结构，但多数语言所定义的语义大体相同。我们考虑下面一个ALGOL赋值句

A:=B

其中，A、B为变量名。我们知道，每个名字有两方面的特征：一方面它代表一定的存储单元，另一方面它又以该单元的内容作为值。赋值句A:=B的意义是：“把B的值送入A所代表的单元”。也就是说，在赋值句中，赋值号‘:=’左、右两边的变量名扮演着两种不同的角色。对赋值号右边的B我们需要的是它的值；对左边的A我们需要的是它所代表的那个存储单元（的地址）。为了区分一个名字的这两种特征，我们把一个名字所代表的那个单元（地址）称为该名的左值；把一个名字的值称为该名的右值。直观上说，名字的左值指它所代表的存储单元的地址，右值指该单元的内容。

变量（包括下标变量）既持有左值又持有右值。常数和带有算符的表达式一般认为只持有右值。但对于指示器变量，如P，它的右值P­既持有左值又持有右值。出现在赋值号左边的表达式必须持有左值。出现在赋值号右边的表达式只需持有右值。对于在赋值号右边的表达式中出现的任何变量，我们要的是它的右值。但BLISS的情形甚为特别，在那里任何单独出现的名字均要其左值，欲使它代表右值，则需在名字之前加一圆点。因此，在BLISS中，A←B＋4和A←·B＋4代表两个不同意义的赋值句。

2. 控制语句
许多语言具有形式上很不相同的控制语句（控制程序的执行顺序），有的即使形式上相同，语义上也可能有很大差别。多数语言中所含的控制语句有：
无条件转移语句

goto L

条件语句

if B then S
if B then S1 else S2

循环语句

while B do S
repeat S until B
for i:=E1 step E2 until E3 do S

过程调用语句

call P (X1,X2,…,Xn)

返回语句

return (E)

重要的是，必须了解这些语句在不同语言中的不同语义。

3. 说明句
说明句旨在定义名字的性质。编译程序把这些性质登记在符号表中，并检查程序中名字的引用和说明是否相一致。许多说明句没有相应的目标代码。但有些说明句，如过程说明和可变数组说明则有相应的目标代码。

4. 简单句和复合句
简单句是指那些不包含其它语句成分的基本句，如赋值句，goto句等等。
复合句则指那些句中有句的语句。例如，

IF(X·EQ·Y)GOTO 15

是FORTRAN的一个复合句；而
if B then S1 else S2;
begin S1; S2; …; Sn end

是Pascal中的复合句。

程序语言的语法描述

上下文无关文法

文法是描述语言的语法结构的形式规则（即语法规则）。 这些规则必须是准确的，易于理解的，而且，应当有相当强的描述能力，足以描述各种不同的结构。由这种规则所形成的程序语言应有利于句子分析和翻译，而且，最好能通过这些规则自动产生有效的语法分析程序。

所谓上下文无关文法是这样一种文法，它所定义的语法范畴（或语法单位）是完全独立于这种范畴可能出现的环境的。下面，我们从一个具体英文例句的分析出发，引进有关上下文无关文法的基本概念。比如，我们写了这样一个句子：

He gave me a book.

显然这是一个语法上正确的句子，因为它满足英语中的基本语法规则。如果我们用“→”表示“由…组成”或“定义为”，那么，可以有下面语法规则：

<句子>→<主语><谓语><间接宾语><直接宾语>
<主语>→<代词>
<谓语>→动词
<间接宾语>→<代词>
<直接宾语>→<冠词><名词>
<代词>→He
<代词>→me
<冠词>→a
<动词>→gave
<名词>→book

把He gave me a book与上述规则进行对照，看其中的语法范畴是否处于适当位置，我们得出结论：它是一个语法上正确的句子。说得更确切一点，有了这些规则后，我们就可以推导或产生出上述句子（从<句子>出发，反复把上述规则中“→”左边的成分替换成右边的成分）：

<句子>Þ<主语><谓语><间接宾语><直接宾语>
Þ<代词><谓语><间接宾语><直接宾语>
Þ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, a,等，称为终结符号；<句子>、<主语>、<谓语>、<动词>、<代词>等，称为非终结符号；这个文法最终是要定义<句子>的语法结构，所以<句子>在这里称为开始符号；<间接宾语>→<冠词><名词>这种书写形式称为产生式。

归纳起来，一个上下文无关文法G包括四个组成部分：一组终结符号，一组非终结符号，一个开始符号，以及一组产生式。

所谓终结符号乃是组成语言的基本符号，在程序语言中就是以前屡次提到的单词符号，如基本字、标识符、常数、算符和界符等。从语法分析的角度来看，终结符号是一个语言的不可再分的基本符号。

非终结符号（也称语法变量）用来代表语法范畴。例如，“算术表达式”、“布尔表达式”、“赋值句”、“分程序”、“过程”等，它们都是现今程序语言常见的语法范畴。我们也可以说，一个非终结符代表一个一定的语法概念。因此，一个非终结符是一个类（或集合）记号，而不是一个个体记号。例如，“算术表达式”这个非终结符乃代表一定算术式组成的类。因而，也可以说，每个非终结符号表示一定符号串的集合（由终结符号和非终结符号组成的符号串）。开始符号是一个特殊的非终结符号，它代表所定义的语言中我们最终感兴趣的语法范畴，这个语法范畴通常称为“句子”。但在程序语言中，我们最终感兴趣的是“程序”这个语法范畴，而其它的语法范畴都只不过是构造“程序”的一块块砖石。

产生式（也称产生规则或简称规则）是定义语法范畴的一种书写规则。一个产生式的形式是

A→a

其中，箭头（有时也用::=）左边的A是一个非终结符，称为产生式的左部符号；箭头右边的a是由终结符号或|与非终结符号组成的一符号串，称为产生式的右部。我们有时也说，产生式A→a是关于A的一条产生规则。产生式是用来定义语法范畴的。
形式上说，一个上下文无关文法G是一个四元式 （VT，VN，S，Ρ） ，其中

  • VT 是一个非空有限集，它的每个元素称为终结符号；
  • VN 是一个非空有限集，它的每个元素称为非终结符号， VT∩VN＝f ；
  • S是一个非终结符号，称为开始符号；
  • Ρ是一个产生式集合（有限）， 每个产生式的形式是P®a， 其中， PÎVN ， aÎ（VT∪VN)∗ 。开始符号S至少必须在某个产生式的左部出现一次。

注意，为了书写方便，若干个左部相同的产生式，如

P→a1
P→a2
…
P→an

可合并为一个，缩写成

P→a1|a2|…|an

其中，每个 ai 有时也称为是P的一个候选式。
箭头‘→’读为“定义为”，直竖‘| ’读为“或”，它们是元语言符号。

在后面的讨论中，根据不同情况，我们将用大写字母A、B、C…或汉语词组（如，算术表达式）代表非终结符号，特别是用小写字母a、b、c…代表终结符，用a、b、g等代表由终结符和非终结符组成的符号串。为简便起见，当引用具体的文法例子时，仅列出产生式和指出开始符号。

严格地说，我们称aAb直接推出agb，即

aAbÞagb

仅当A→g是一个产生式，且a、 bÎ（VT∪VN）∗ 。如果 a1Þa2Þ…Þan ，则我们称这个序列是从 a1至an 的一个推导。若存在一个从 a1 至 an 的推导，则称 a1 可推导出 an 。我们用 a1an 表示：从 a1 出发，经一步或若干步，可推导出 an 。而用 a1an 表示：从 a1 出发，经0步或若干步，可推导出 an 。换言之， ab 意味着，或者 a＝b ，或者 ab 。

假定G是一个文法，S是它的开始符号。如果Sa，则称a是一个句型。仅含终结符号的句型是一个句子。文法G所产生的句子的全体是一个语言，将它记为L（G）。

L（G）＝{a | Sa & aΠ}

语法分析与二义性

前面我们提到过可以用一张图表示一个句型的推导，这种表示称为语法分析树，或简称为语法树。语法树有助于理解一个句子语法结构的层次。语法树通常表示成一棵倒立的树，根在上，枝叶在下。

语法树的根结由开始符号所标记。随着推导的展开，当某个非终结符被它的某个候选式所替换时，这个非终结符的相应结就产生出下一代新结，候选式中自左至右的每个符号对应一个新结，并用这些符号标记其相应的新结。每个新结和其父结间都有一条连线。在一棵语法树生长过程中的任何时刻，所有那些没有后代的端末结自左至右排列起来就是一个句型。

一棵语法树表示了一个句型种种可能的（但未必是所有的）不同推导过程，包括最左（最右）推导。这样的一棵语法树是这些不同推导过程的共性抽象，是它们的代表。如果我们坚持使用最左（最右）推导，那么，一棵语法树就完全等价于一个最左（最右）推导，这种等价性包括树的步步成长和推导的步步展开之间的完全一致性。

但是，一个句型是否只对应唯一的一棵语法树呢？也就是，它是否只有唯一的一个最左（最右）推导呢？不尽然。如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。也就是说，若一个文法中存在某个句子，它有两个不同的最左（最右）推导，则这个文法是二义的。

注意，文法的二义性和语言的二义性是两个不同的概念。我们可能有两个不同的文法G和G’，其中一个是二义的而另一个是无二义的，但是却有L（G）＝L（G’），也就是说，这两个文法所产生的语言是相同的。对于一个程序语言来说，常常希望它的文法是无二义的。因为，我们希望对它的每个语句的分析是唯一的。但是，只要我们能够控制和驾驭文法的二义性，文法二义性的存在并不一定是一件坏事。

人们已经证明，二义性问题是不可判定的。即，不存在一个算法，它能在有限步骤内，确切地判定一个文法是否为二义的。

最后，作为描述程序语言的上下文无关文法，我们对它有几点小小的限制。

  • 第一，文法中不含任何下面形式的产生式

    P→P

    因为，这种产生式除了引起二义性外没有任何用处。

  • 第二，每个非终结符P必须都有用处。这一方面意味着，必须存在含P的句型；也就是，从开始符号S出发，存在推导

    S→aPb

    另一方面意味着，必须存在终结符串gÎV，使得P→g；也就是，对于P不存在永不终结的回路。

我们以后所讨论的文法均假定满足上述两条件。这种文法亦称化简了的文法。

典型题解

例题2.1 是非题

  • 因名字都是用标识符表示的，故名字与标识符没有区别。（ ）
  • 正规文法产生的语言都可以用上下文无关文法来描述。（ ）
  • 上下文无关文法比正规文法具有更强的描述能力。（ ）

分析

  • 1.标识符是高级语言中定义的字符串，一般是以英文字母开头（包括大小写字母）的，由数字、字母和一些特殊字符（如下划线等）组成的一定长度（不同的高级语言对标识符的长度的规定不同）的字符串，它只是一个标志，没有其它含义。名字是用标识符表示的，但名字不仅仅是一个字符串，它还具有属性和值，就象一个人的名字不仅仅是一个符号，对于认识这个人的人来说，它还代表着这个人，因此本题错。
  • 2．乔姆斯基把文法分成4种类型，从4种文法的形式化描述来看，它们的差别主要在对规则形式的约束上。0型文法的规则形式是：每个产生式a→b都满足， aÎ（VN∪VT）∗ 且至少含有一个非终结符， bÎ（VN∪VT）∗ ，0型文法也叫短语文法。1型文法的规则形式是：每个产生式a→b均满足|a|£|b|，仅仅S→e例外，且S不得出现在任何产生式的右部，1型文法也称上下文有关文法，从两种文法的规则形式来看，1型文法对规则形式的约束比0型文法强，1型文法能描述的语言0型文法也能描述，而0型文法能描述的语言1型文法不一定能够描述，1型文法是0型文法的特例。2型文法的规则形式是A→b，其中 AÎVN ， bÎ（VN∪VT）∗ ，2型文法也称上下文无关文法，分析2型文法的规则形式不难发现，2型文法是1型文法的特例，也是0型文法的特例。3型文法的规则形式是A→aB或A→a，其中aÎ，A、 BÎVN ，3型文法也称正规文法，可以看出3型文法是前面3种文法的特例。从上面的分析可以，正规文法是上下文无关文法的特例，可以用正规文法描述的语言，其正规文法描述的形式也是上下文无关文法的描述形式，即可以用上下文无关文法描述，因此本题对。
  • 3．上下文无关文法是2型文法，正则文法是3型文法，从上题的分析可以看出，3型文法是2型文法的特例，3型文法可以描述的语言都可以用2型文法来描述，而2型文法可以描述的语言则不一定能用3型文法来描述。即2型文法比3型文法的描述能力强，因此本题对。

例题2.2 填空题

  • 1．程序语言是由 ( )和( )两方面定义的。
  • 2．常用了参数传递方式有（ ）、（ ）和（ ）。
  • 3．文法G所产生的句子的全体的（ ），将它记为（ ）
  • 4．一个上下文无关文法包含四个组成部分是（ ）。

解答

  • 1．如同自然语言一样，程序语言主要由（语法）和（语义）两个方面定义，有时，语言定义也包含语用信息，语用主要是有关程序设计技术和语言成分的使用方法。
  • 2．参数传递主要有三种不同的途径，（传地址（call by reference））、（传值（call by value））和（传名（call by name）），传名也常称为换名。
  • 3．假定G是一个文法，S是它的开始符号。如果Sa，则称a是一个句型。仅含终结符号的句型是一个句子。文法G所产生的句子的全体是一个（语言），将它记为（L（G））。
  • 4．一个上下文无关文法G包括四个组成部分：（一组终结符号），（一组非终结符号），（一个开始符号），（一组产生式）。

说明: 高级语言参数传递的方式通常有4种，传地址、得结果、传值和传名。早期的FORTRAN语言通常采用传地址或得结果的方式来实现参数的传递，这两种方法的不同给FORTRAN的标准化增加了难度，相比来说，传地址是一种常用的参数传递方式，而得结果则不是。

例题2.3

program  test (input, output)
var  i, j: integer;
procedure CAL(x, y: integer);
begin
           y:=y**2;  x:=x-y;  y:=y-x
end;  {CAL}
begin  {main}
         i:=2;  j:=3;  CAL(i, j)
         writeln(j:1)
end.  {main}

假定程序在语法上是正确的，采用哪一种参数传递方式使程序打印16。
（A）call by reference （B）call by name （C）call by value
（D）前述三种中的二种 （E）都不是 （**为乘幂运算）

解答
这是一道选择题，要知道正确结果，必须先对三种参数传递方式计算程序的运行结果。
1．传地址：传地址时在子程序中对形式参数的引用实际上是对实参地址的引用，也就是说，对形式参数的值的修改实际上就是对实参值的修改。程序中在调用CAL函数之前，首先对i和j赋值，即i=2，j=3，函数调用后，函数CAL先对y进行乘幂运算，也就是执行j:=j**2，执行后j的值为9，然后执行x:=x-y，即i:=i-j，执行后i的值为-7，最后执行y:=y-x，即j:=j-i，则最后j的值为16。所以采用传地址的参数传递方式时程序打印16。
2．传名：即名字替换，过程调用的作用相当于把被调用段的过程体抄到调用出现的地方，但把其中任一出现的形式参数都替换成相应的实在参数，那么程序的执行过程实际上是：

    i:=2;  
j:=3;
i:=i**2;  
i:=i-j;  
j:=j-i

其中，第一行是主程序中的语句，第二行是用子程序CAL中的语句替换函数调用CAL（i，j），然后用实参替换形式参数的结果（即用i替换x，用j替换y）。执行上面的程序语句，我们可以发现最后j的值为16，因此采用传名的参数传递方式程序的打印结果仍然是16。
3．传值：调用段把实在参数的值计算出来并存放在一个被调用段可以拿得到的地方。被调用段开始工作时，首先把这些值抄入形式单元中，然后就好像使用局部名一样使用这些形式单元。如果实在参数不为指示器，那么，在被调用段中无法改变实参的值。这里，实参都不是指针，采用传值的方式传递参数时，函数的执行不会改变实参的值，程序在函数调用前给i赋值2，给j赋值3，在函数执行完后，i和j的值将仍然是2和3，因此传值时打印值为3。
通过上面的分析，我们可以看到传地址和传名的打印结果都是16，正确答案是（D）。

说明: 针对不同的参数传递方式对程序的结果进行计值是一种类型的题，这几年的考题基本上都有一道该类型的题，但在今天，通用高级语言中应用最多的参数传递方式是传值和传地址，在语言学习中，其它两种参数传递方式已很少有人讨论，但出于应考的目的，掌握它们还是很有必要的。

本题只讨论了三种参数传递方式，如果是得结果呢？每个形式参数都对应两个单元，第1个单元存放实参的地址，第2个单元存放实参的值。在过程体中对形参的任何引用或赋值都是对它的第2个单元的直接访问。但在过程工作完毕返回前必须把第2个单元的内容存放到第1个单元所指的哪个实参单元之中。本题中的形参x和y就都有两个单元，它们的第一个单元分别存放i和j的地址，第二个单元分别存放i和j的值，进入子程序CAL之后，访问的都是x和y的第二个单元，CAL执行完后，x和y的第二个单元的值分别变为-7和16，然后在返回前将第2个单元的内容存放到第1个单元所指的哪个实参单元之中，即将-7抄给i，将16抄给j，所以本题如果选择得结果的参数传递方式，程序的打印结果仍然是16。

练习

  1. 写出下列程序设计语言所采用的输入字母表并进行比较：
    (1) Pascal (2) C (3) Ada (4) FORTRAN (5) Java
  2. 关于变量、数组说明，练习1中所列的各种语言有何相同或不同之处？
  3. 何谓“标识符”，何谓“名字”，两者的区别是什么？
  4. 令+、*和­代表加、乘和乘幂，按如下的非标准优先级和结合性质的约定，计算1+1*2↑*1↑2的值：

(1) 优先顺序（从高至低）为+，*和↑，同级优先采用左结合。
(2) 优先顺序为↑，+，*，同级优先采用右结合。

5.对你所熟悉的某种语言中的某种基本数据类型：
(1) 描述这种类型数据对象可以包含的值；
(2) 确定这种类型的值的存储表示；
(3) 定义这种类型的常量的语法表示；
(4) 确定对这种类型的数据对象可以进行哪些运算；
(5) 对每一种运算，确定它的实现是通过软件仿真还是仅用一条简单的硬件指令？
(6) 对这种类型的数据进行运算的合法性是静态确定还是必须动态确定？

6.令文法G6为

N→ D | ND
D→ 0 | 1 | 2 | 3 | 4 | 5 | 6| 7 | 8 | 9

(1) G6的语言L（G6）是什么？
(2) 给出句子0127、34和568的最左推导和最右推导。

7.写一个文法，使其语言是奇数集，且每个奇数不以0开头。

8.令文法为

E→ T | E + T | E - T
T→ F | T * F | T / F
F→ (E) | i

(1) 给出i+i*i、i*(i+i)的最左推导和最右推导。
(2) 给出i+i+i、i+i*i和i-i-i的语法树。

9.证明下面的文法是二义的：

S→iSeS | iS | i

10.把下面文法改写为无二义的：

S→SS | (S) | ( )

11.给出下面语言的相应文法

L1={anbnci | n³1，i³0}
L2={aibncn | n³1，i³0}
L3={anbnambm | n，m³0}
L4={1n0m1m0n | n，m³0}

*12. 假定已知语言{anbncn | n³1}不是上下文无关的，请证明上下文无关语言对于交和补这两个运算是不封闭的。（提示：利用练习11那两个语言集L1和L2作媒介）

*13. 证明任何上下文无关语言都可由仅含下述三种形式的产生式的文法所产生：

A→BC
A→a
S→e

其中，A、B、C、S为非终结符，S为开始符号。

*14. 证明：对任何上下文无关文法G，存在一个正整数p，使对任何aÎL(G)，若| a | ³p，则a可表示成xuwvy，使得| uwv | £p，| uv | > 0，且对任何i ³ 0，xuiwviyÎL(G)。

参考文献

  1. 郭浩志. PASCAL语言结构程序设计. 国防科技大学出版社，1988.
  2. 郭浩志. 程序设计语言概论. 国防科技大学出版社，1989.
  3. 易文韬，陈颖平. Java手册. 科学出版社，1997.
  4. Donald E. Knuth. The Art of Computer Programming, Volume 1/Fundamental Algorithms. Addison_Wesley, Reading, Massachusetts, Second Edition, 1973.
  5. Donald E. Knuth. The Art of Computer Programming, Volume 2/Seminumberical Algorithms. Addison_Wesley, Reading, Massachusetts, Second Edition, 1981.

关于编译原理博文更多讨论与交流，敬请关注本博客和新浪微博songzi_tea.

标签：

相关文章