第三章
语 言 翻 译
3.1 语言的语法
?语法：单词作为语句中元素的显示它们之间关系的布局 。 描述
了构成有效程序的符号序列 。 如 C中, x=y+z是有效的符号序列,
而 xy+－则不是 。
?语法提供了理解程序需要的有意义的信息 。 也提供了大量源程
序到目标程序翻译所需的信息 。
?单 靠 语 法 并 不 足 以 无 二 义 地 刻 划 语 句 的 结 构 。 如：
x=2.45+3.67,语法并不能告诉我们 x是否被声明或是否声明为
实数 。 x=5,6或 6.12均是可能的 。
?因此, 对语言的完整描述单靠语法结构是不够的, 还需涉及语
义 。 如：声明的使用, 操作, 顺序控制和引用环境等影响变量,
并不总是由语法决定 。
?虽然如此, 语法仍是语言描述中的重要属性 。
?现在, 语法描述已是一个解决了的问题, 源程序的语法理解阶
段是相当机械的, YACC等工具可自动生成给定程序的语法描
述 。
一般语法准则
?语法的主要目的是为程序员和语言处理器间通讯提供一套
注记方法 。 而特殊语法结构的选择被限制于特殊的信息项
通讯 。
例如：某特定变量有类型实数, 可以用多种方式表达 。
可以是显示声明或隐含的命名约定, 等 。
?语法细节的选择大部分是基于第二准则, 如可读性, 它和
通讯的主要目标无关 。
?有很多二级准则, 通常可按其目标分类, 分为：易读, 易
写, 易翻译, 无二义等目标 。 这些目标间有时会有冲突 。
?易读性 （ Readabitity）
程序是易读的, 如果程序表示的算法和数据的结构可从程
序文本的检查明显了解 。 一个易读的程序, 通常称为自文
档的 （ 不需其他用于理解的辅助文档 ） 。
增加易读性的方式：自然的语句格式, 结构化语句, 关键
字和噪音字的自由使用, 嵌入式注释机制, 不限长标识符,
记忆操作符, 自由域格式, 完全的数据声明等 。
易读性并不能由语言设计保证, 最好的设计也可能由于糟
糕的编程而破坏 。 当然, 语法设计也可能使最有意识的程
序员写出难理解的程序, 如 APL。 COBOL强调易读, 但其
代价是牺牲了易写和易翻译 。
增加易读性 — 语法不同应反映语义不同, 做相似事的程序
结构是相似的 。 做不同事的程序其结构需有明显不同 。 语
言如只提供了少数不同语法结构, 通常导致程序易读性差 。
如 APL,SNOBOL4等, 只提供一种语句格式, 赋值, 子程
序调用, 简单 GOTO,子程序返回, 多路条件分支, 及其它
常见程序结构的差异只能通过个别操作子的不同来反应 。
?易写性
易写性 （ 使用简明的, 规则的语法结构 ） 通常和易读性 （ 冗
余结构是有帮助的 ） 相冲突 。
隐含的语法约定允许声明和操作不需刻划, 从而使程序更短,
更易写, 但不易读 。 其他特性对两个目标均有增强：如结构
化语句, 简单自然语句格式, 记忆操作符, 未限制标记符等
通常使程序易写, 通过允许在程序中直接表示问题的算法和
数据的自然结构 。
语法称为冗余的, 如果以多种方式传达同样的信息 。 有些冗
余性有用的, 因它允许程序易读, 并允许翻译时错误检测 。
缺点是不易写 。
大多数缺省规则 （ 针对语言结构含义 ） 试图减少冗余, 通过
删去某些显式的含义陈述, 因为这些含义可从语境中导出 。
例, Fortran中约定, I-N打头的变量为整型, 其他为实数,
这样不需声明, 但缺点是有副作用, 如：拼写错误不能被编
译器检测到, 例如,INDEX被写成 INDX→ 则变成新变量 。
?易验证性
和易读, 易写相关的概念是程序正确性或程序验证 。
多年经验表明, 理解每条程序语言语句是容易的, 创建正
确程序的整个过程却是困难的 。
因此, 需有技术, 使得能数学地证明程序是正确的 。
?易翻译性
即易于翻译成可执行形式 。
易读性和易写性是面向程序员的需要 。 易翻译性 （ 关键是
结构的正则性 ） 是面向翻译器 （ 处理被写成的程序 ） 的需
要 。
如 LISP程序, 不易读, 也不易写, 但易于翻译, 主要由于
其语法简单且正则 。
当特殊语法结构增加, 将导致翻译困难, 如 COBOL,允许
大量的语句和声明形式 。
?没有含混性
含混性是语言设计中的一个中心问题 。
一个语言定义理想地为每个语法结构提供唯一的意义 。
而含混性结构允许两个或多个不同解释 。 通常不是由个体
程序元素的结构产生, 而是由于不同结构的交迭 。
例如,
if Boolean exp then statement1 else statement2,
If Boolean exp then statement1
当两种形式组合时, 有可能出现二义情况 。
Fortran中, A（ I,J） 可能是数组元素, 也可能是函数调用 。
事实上, 上面提到的含混在语言中均有解决方案 。
条件语句的两种不同解释,
例：因组合而形成的悬空 else,
If Boolean exp1 then if Boolean exp2 then stat1 else stat2
Algol解决方案：改变语法，引入分界符 begin…end 。
Ada解决方案：每个 if语句必须以 end if分界符结尾。
C和 Pascal解决方案：从二义结构中任选一种解释。对本例
而言，最后的 else总是和最近的 then配对。
FORTRAN中函数调用和数组引用的二义性由规则解决：
A(I,J)被视为函数调用，如果没有数组 A的声明。但这个假
定只能在程序装载、链接时被检查。
Pascal中区分二者的方法是使用不同的括号，如,[…] 用于
界定数组参数,(…) 用于界定函数调用的参数。
语言的语法元素
语言的语法风格由各种基本语法元素的选取所决定。
?字符集
字符集的选择是语言设计的第一件事 。
已有一些标准字符集, 如,ASCII码 。 通常是选择一个标
准的字符集 。 但也有不标准的, 如 APL。
字符集的选择对确定可被用于语言实现的 I/O设备的类型
是非常重要的 。 如,C的字符集可用于大多数 I/O设备 。
而 APL的字符集则不能直接用于大多数 I/O设备 。
通常用 8位来表示字符 （ 60年代早期用 6位 ）, 这似乎是
足够的 。 但是, 随着计算机产业的国际化进程, 可能 16
位表示是必需的 （ 可有 65536个字符 ） 。
?标识符
字和数字串, 以字母开头 —— 常用的选择 。
也可能使用特殊字符, 如用,或 -来改善易读性和长度限
制 。
?操作符符号
+,-,*,/表示基本算法操作 。
通常原操作可完全使用特殊符号 。
当然, 也可以使用标识符来表示原操作, 如 LISP中的
PLUS,TIMES。
大多数语言采用二者的组合 。
?关键字和保留字
关键字 —— 用于语句语法中固定部分的标识符 。
保留字 —— 不能被程序员使用的关键字 。
大多数语言使用保留字以改善翻译器的错误检测能力,
使语法分析更为容易 。
?噪声字
可选的字, 被插入语句中以改善易读性 。
如,COBOL中 Go语句可写为 GO TO
?注释
是文档中的重要部分, 几种注释方式,
1,分别的注释行, Fortran
2,特殊标志界定, /* */,界定字符丢失可能导致大面积
出错 。
3,在行中任意地方开始, 但在行末结束, 如 C++的 //
?空白 （ 空格 ）
语言中常使用空白规则, 通常都是作为分隔符 。
也有的语言中空格有其他用途 。
?界定符 （ 分界符 ） 和括号
用于标记语法单位的开始和结束
括号是一对分界符 。
?自由和固定域格式
自由域 —— 语句可写在任何地方
固定域 —— 在输入行中通过位置来传递信息 。 Fortran是
典型例子 。
当前固定域越来越少 。
?表达式
访问程序中数据对象并反回值, 是基本的语法建筑块 。
在命令型语言中, 表达式形成基本操作, 状态被语句所
改变 。
在作用型语言中, 表达式形成了驱动程序执行的基本顺
序控制 。
?语句
是命令型语言中最主要的语法部件 。 语句的语法对语言
整体的正则性, 易读性和易写性有着关键影响 。
有的语言采用单一语句格式, 强调正则性；而其它语言
对不同语句类型使用不同语法, 着重于易读性 。
语句结构中的一个更重要的差异是：结构性 （ 或嵌套 ）
语句和简单语句 。
程序 —— 子程序结构
?分开的子程序定义
Fortran中, 每个子程序定义被处理为分开的语法单元,
每个子程序被分别编译, 被编译程序在装载时链接 。
这种组织方式主要是针对这样一种情况：每个子程序均
需含所有数据元素的完整数据声明, 即使是对那些在
COMMON块中的或与其它子程序共享的数据 。 需要这
些声明主要是由于分开编译的需要 。 基本的子程序单元
用于表示通常提供相关功能的结构 。
?分开的数据定义
把所有操作于给定数据对象之上的操作组合在一起, 如
C++中类 。 主要是基于数据抽象的原则 。
?嵌套的子程序定义
如 PASCAL,子程序定义在主程序中作为声明出现, 子
程序本身又可含有其他子程序定义 。
其目标是强调结构化的语句, 但事实上产生了不同用途 。
结构化语句的引入主要是为算法结构的常见的层次划分
提供一种自然的注记方式, 但嵌套子程序定义为编译时
定义的子程序提供了非局部的作用环境 。 从而允许静态
类型检查, 和有效的可执行代码的生成 。
没有子程序定义的嵌套, 则必须为每个在子程序定义中
的非局部变量提供声明, 或将所有非局部引用的类型检
查推迟到运行时 。
嵌套的另一好处是作用域管理 。 允许子程序名具有较少
的作用域 。
? 分开的接口定义
FORTRAN的结构允许分开子程序的非常容易的编译, 但
缺点是不同子程序共享的数据可能有不同的定义, 而这
种不同是编译器在编译时无法检测到的 。
PASCAL允许编译器访问所有这样的定义以帮助发现错
误, 缺点是全部程序, 即使其有上千条语句, 必须在每
次修改后重新编译 。
结合上面的技术可以改善编译行为 。
程序实现由几个相互交互的子程序构成, 这些部件称为
模块, 将被连接在一起以创建可执行程序, 但每次只有
修改的模块被重编译 。 而在一个部件中的过程间传送的
数据必须具有公共声明, 从而允许编译器的高效检查 。
为了在分开的编译模块间传递数据, 引入了规约部件,
如 C中,h文件 。 Ada中的 Package（ 接口定义规约 +实现
体 ） 。
?数据描述和可执行语句分离
COBOL包含了早期的部件结构形式 。 在 COBOL中, 所
有子程序的数据声明和可执行语句被分入不同的程序中,
即数据段和过程段, 而用环境段包含关于外部操作环境
的声明 。
一个程序的过程段被组织为子单元, 以对应子程序体,
但所有数据对所有子程序均是全局的, 没有东西对应于
通常子程序中的局部数据 。
中心化数据段的优点是：强迫形成数据格式和过程段中
算法的逻辑独立性, 数据结构的细小修改可只修改数据
段而不需修改过程段 。 同时将数据描述搜集到一个地方,
而不是散布在子程序中也是方便的方式 。
这适合于大量数据的处理 。 在某种意义是, 数据库应用
是这种形式的扩展 。
?未分离的子程序定义
不分开主程序和子程序语句, 如 SNOBOL4中, 程序是
一个语句表 。
子程序间没有语法分隔, 函数调用开始新的子程序执行,
返回语句结束该子程序 。
程序作为是动态的 。 事实上, 任意语句可以同时是主程
序的一部分, 也可以是子程序的一部分 。 这体现在该语
句可在主程序的执行中某点被执行, 而后又在某子程序
的执行中某点被执行 。 这种混沌结构仅仅对允许运行时
翻译和相对简单的新语句和子程序执行机制具有价值 。
?BASIC
简单的语法, 和前述设计目标均有冲突 。
主要面向非科学家用户 。
3.2 翻译的阶段
?逻辑上, 翻译可分为两个主要部分 （ 输入源程序的分析, 可执
行目标程序的综合 ）, 两个阶段又可细分 。
?大多数翻译器的中这些逻辑阶段不是可以明确划分开的, 而是
混合在一起使得分析和综合交替进行 （ 通常逐条语句进行 ） 。
? 编译器通常对源程序扫描两遍
第一遍将程序分解为部件并从程序中导出信息 。
第二遍根据这些收集的信息生成目标程序 。
?如果编译速度是重要的考虑 （ 如教学用编译器 ）, 一遍扫描是
常用方式, 在程序被分析时, 立即被翻译为目标代码 。
?如果执行速度是重要考虑, 三遍甚至更多遍扫描也是可能的 。
第一遍分析源程序 。
第二遍使用各种定义好的优化算法将源程序重写为更多效
的形式 。
第三遍生成目标代码 。
源程序的分析
?语法分析
将源程序字符流分隔, 分组, 成为一些基本的构成成分,
如,标识符, 分界符, 操作符, 数, 关键字, 噪音字,
空白, 注释等 。
这些称为语法项, Token。
?语法分析 （ parsing）
标识大的程序结构 （ 语句, 声明, 表达式等 ） （ 基于前
面得到的 Token） 。
通常语法分析和语义分析交替进行 （ 使用栈作为通讯工
具 ） 。
语法分析器向栈中输入各种语法单元元素, 语义分析器
检索并处理 。
需要高效的语法分析技术, 主要基于形式化文法的应用 。
?语义分析 —— 翻译的中心阶段
处理语法分析器识别的语法结构, 并开始形成可执行目
标码的结构, 语义分析是分析和综合间的桥梁 。
这阶段的工作包括一些重要工作, 如符号表维护, 大多
数错误检测, 宏扩展以及编译时语句的执行 。
在简单情况下, 语义分析器直接生成可执行代码, 但大
多数情况下, 是产生最终可执行程序的某种内部格式,
然后被优化处理 。
语义分析器可分为一些小的语义分析器, 各自处理一特
殊类型的程序结构 。 它们之间通过存放在各种数据结构,
特别是中心符号表中的信息而进行交互 。
?常见的语法分析功能,
1,符号表维护
符号表 （ 最早由词法分析形成 ） 含有对程序中不同标识
符的表项 （ 不仅含标识符, 还包含涉及标识符属性的附
加数据, 如：标识符类型, 值类型, 引用环境等 。 ）
语义分析器在处理声明, 子程序头, 语句等时, 填入相
关信息 。
编译型语言的符号表在翻译结构后通常丢弃 。
但有的语言在执行时仍保留, 如：允许运行时创建新标
识符的语言 （ ML,LISP等, 符号表是运行时的中心数
据结构 ）, 以及辅助调试 （ dbx使用运行时符号表来调
试 C程序 ） 。
2、隐含信息的插入
在源程序中, 有的信息经常是隐含的, 必须在低级目标
程序中显式化 。
这类隐含信息包括：一些缺省约定信息, 类型推导信息
等 。
3,错误检测
语法和语义分析器必须能够处理不正确的和正确的程序 。
语法分析器可能会接受到和当时语境不相容的词法项,
如：表达式中出现分界符, 语句序列中出现声明等 。
更微妙的错误有：实数变量出现在需要整数的地方, 对
声明只有二维的数组出现三维下标引用等 。 属语义错 。
语义分析器不仅需要能够识别这样的错误并产生适当的
出错消息, 还必须能够在大多数情况下, 确定合适的方
式以继续剩余程序的语法分析工作 。
4,宏处理和编译时操作
并非所有语言具有宏特征和编译时操作 。 但如果具备,
通常在语义分析中处理 。
语义分析器必须识别宏调用并处理宏替换 。 通常, 该任
务需要中断词法和语法处理, 而让它们去处理宏体中的
字符流 。 另一个方法是宏体可能已预先被部分翻译, 语
义分析器可以直接处理, 在继续源程序分析前插入适当
的目标码并建立合适的表项 。 用于控制翻译 。
编译时操作是在翻译中完成的操作，用于控制源程序的
翻译。 C中提供了大量这样的操作。如,
#define允许常量或表达式在程序被编译前计值。
#ifdef允许不同的代码序列被编译，根据某些变量的存在
与否。
这些设施允许程序员修改被编译的语句序列。
目标程序的综合
翻译的最后阶段是根据语义分析的结果, 构造可执行程序 。
?优化
语义分析器通常以某种中间形式来产生可执行程序, 中
间形式可以是操作符和操作数的串, 也可以是操作符和
操作数序列的表 。 在代码生成前, 对中间形式进行优化
处理是必要的 。
?代码生成
在中间形式被优化后, 必须产生最后的输出结果：可执
行程序 。 它可能是汇编语言语句, 机器代码序列或其它
目标形式 。 它可能能够直接执行, 也可能需要链接装载
后才可执行 。
?连接和装载
形成最终可运行程序 。
3.3 形式翻译模型
?编译器理论的语法识别部分是相当标准的, 通常基于上下文
无关理论 。
?语言语法的形式定义通常称为文法 （ grammar）
?一个文法由一个规则集合组成, 规则被称为产生式, 刻划了
形成允许程序的字符序列 。
?一个形式文法是用严格定义的记号体系刻划的文法 。
?编译技术中常用两类文法 。
BNF文法 （ 上下无关文法 ）
正则文法
BNF文法
Backus-Naur Form。 John Backus开发，用于 Algol语言的语法
定义。 Peter Naur是开发 Algol委员会的主席。几乎同时，语
言学家 Noam Chomsky设计了上下文无关文法来定义自然语
言的语法。在能力上，二者是等价的，差异只是符号体系不
同。
?语法
BNF文法包含一个 BNF文法规则的有限集合, 它定义了一
个语言 。
语法仅仅涉及形式而不涉及含义, 一个语言从语法上考
虑, 由一个语法正确的程序集合构成, 每个程序只简单
地是一个字符序列 。
语法正确的程序不一定有语义, 即可能不一定计算出什
么结果, 甚至没有结果 。
不考虑语义, 语言是任意有限字符串的集合, 这些字符
选自某固定符号集 。
因此，下面均为语言
1、所有 C中赋值语句的集合
2、所有 C程序的集合
3、所有 LISP原子的集合
4,a,b.构成的序列的集合，所有 a在所有 b之前。
语言可包含有限的串集合，也可能包含无限的串集合。
考虑上面例子，可发现用自然语言描述语言带来了一些
问题，如,4例中,b是否是语言的成员？是否串上必须
有 a？因此，描述并不完整。
解决这个问题的方法：给出形式的数学规则集合，准确
地确定语言中的串是什么？
最简单的文法规则是列出有限语言的所有元素，如,
<digit>:=0|1|2|3… 8|9
这里 <digit>表示一个非终结符或语法范畴, 0－ 9为终结
符 。
一旦定义了基本的语法非终结符集合, 可以构造更复杂
的串, 如,
<conditional statement>::=
If <Boolean exp> then <statement> else <statement>
| if <Boolean exp> then <statement>
规则定义的非终结符可本身被用在规则中, 从而形成递
归规则 。
<unsigned integer>::= <digit> |
<unsigned integer><digit>
一个更复杂的文法，定义一组简单赋值语句。
?语法分析树（ parse tree）
给定文法，可使用单替换规则生成语言的串。
如：下面文法生成平衡的括号序列,
S→SS| （ S） |（）
一个推导过程,
S→ （ S） → （ SS） → （（） S） → （（）（））
推导中的每个项称为语句形式。语言是语句形式的集合，
每个语句形式只含有终结符，并可从文法的初始符号推
导出来。
为了确定是否一给定串是一个文法定义的语言的语法合
格程序。我们必须使用文法规则去构造串的语法分析，
如成果地分析，则是该语言的程序。
赋值语句 W=Y*(U+V)的语法分析树,
BNF文法将一个结构赋给语言中的每个串。
注意，被赋的结构实质上是一棵树，这是由于 BNF文法
的限制。树的叶节点是单个字符或词法项，中间的分叉
点是一个语法范畴，由非终结符标记，根节点是表示整
个语言的非终结符。
分析树为程序提供了大部分的直觉的语义结构。
同样的语言可被很多不同文法定义，如图 3.5定义的语
言和图 3.3是一样的。
不能用 BNF文法定义的语法是那些涉及上下文依赖的语
法，如：如下限制不能用 BNF刻划。
同样的标识符不能在相同块中声明两次。
每个标识符必须声明在包括其使用点的块中。
一个用二维声明的数组不能用三个下标引用。
此类限制必须用对显式化 BNF的补遗来定义。
赋值语句的另一个 BNF定义,
?含混性（二义性）
多义性通常是文法中的问题，而不一定是语言的问题。
如,G1,S→SS|0|1
具有二义性，如图 3.6所示。
如果对给定语言的每个文法均是含混的，则称语言是固
有含混的。
然而上面 G1文法描述的语言不是含混的，因为可以为它
写出不含混的文法。
G2,T→0T|1T|0|1
?BNF记号法的扩展
BNF文法比较简单，但用于描述语言却有诸多不便。
将其适当扩展后更易用。
可选性元素用 [……] 表示。
选择用 |表示。
重复用 {……}* 表示。
图 3.7给出了简单赋值语句的扩展 BNF文法。
?语法图
也称铁道图，是扩展 BNF的图形表示。
图 3.7中的描述可用图 3.8等价表示。
有限状态自动机
语言由 Token构成,Token具有简单的结构。
这里主要给出识别 Token的机器模型，有限状态自动机或状
态机。这是一种有效的识别 Token的工具，只要知道当前所
处状态，就可以确定现有输入是否为 Token的一部分。
图 3.9,FSA，识别奇数个 1构成的串。
输入 100101的机器操作如下处理,
输入 当前状态 接受串否？
Null A no
1 B yes
10 B yes
100 B yes
1001 A no
10010 A no
100101 A yes
通常, FSA有一个开始状态, 一个或多个终态, 以及一组从
状态到状态的变迁 。 任何串, 只要能使机器从初态到终态
（ 通过一系列变迁 ）, 则该串为机器所接受 。
图 3.10,识别带符号整数 。
?非确定型有限自动机
确定型 FSA—— 对其每个状态，每个输入符号，有唯一的
变迁到相同或不同状态。
非确定型 FSA具有,
1、一个状态集合
2、一个初始状态
3、一个终止态集合
4、一个输入符号集合
5、一个从状态到状态的变迁集合，每个变迁接受来
自输入符号集的一个元素。
非确定性是指：从一个状态有多个具有相同标记的弧线
连出，从而必须作出选择。
一个串称为可接受的，如果存在从初始结点到终止结点
之一的路径，即使其他路径可能不能到达某终态。
?正则文法
是 BNF文法的特例，等价于 FSA，形式为,
<nontrerminals>::=<terminal><nonterminal>|<terminal>
例,A→0A|1A|0 产生以 0为结尾的 01串。
?正则表达式
正则表达式是语言定义的另一种形式，等价于 FSA和正
则文法。
定义,
1、单个终结符是正而表达式
2、如 a,b是正则表达式，则 a?b,ab,(a),a*也是正则表
达式。
3、除 1,2外，没有其他是正则表达式。
可以用正则表达式来表示任何用正则文法或 FSA定义的语
言，虽然将任意 FSA转换为正则表达式并不总是明显的。
下面两图为到 FSA的转换,
压栈自动机 Pushdown Automata
PDA是类似于 FSA的抽象模型机，等价于 BNF文法，它具有
有限个状态，有一个下压栈，其移动规划如下,
1、读输入符号，并读栈项符号
2、基于两个输入，机器进入一个新状态，并写 0个或多
个符号在栈顶。
3、如果栈空，则串被接受（或 PDA处于终态）
易于看出 PDA比 FSA具有更强大的能力。
如,anbn不能被 FSA识别，但可以被 PDA识别。
PDA接受的语言等价于上下文无关语言。
考虑产生串的最左推导的过程, 在这种情形, 语句形式存放
在栈中, PDA的操作如下,
1,如栈顶是终结符, 将其和下一输入比较, 如相同, 则
弹出栈 。 如不相匹配, 则出错 。
2,如栈顶是非终结符 X,用串 а替代 X,а是产生式 X→а
的右端 。
这样 PDA模拟了上下文无关文法的最左推导, 这种构造实际
上形成了一个非确定型 PDA,等价于对应的 BNF文法 。
在第二步中, 可能有多个 X→α 样式的规则, 规则的选用需
人来选择 。
确定型 PDA和非确定型 PDA间关系, P94-95的回文例子 。
确定型 PDA等价于 LR（ K） 文法, 对实际的编译器设计是非
常重要的 。
高效的语法分析算法
文法描述语言是自顶向下，而语法分析则是自底向上，从
个体字符开始。
?一般的分析策略,
每种类型的形式文法总是和某类型的自动机紧密相关 。
自动机是一种抽象机, 读一个输入带, 产生一个输出带 。
然而, BNF文法可能是含混的, 因此, 自动机必须是非
确定的 。 非确定型压栈机能识别任何上下文无关文法,
通过使用猜测策略 。
对语言翻译而言, 不需猜测的确定型自动机是需要的 。
对正则文法, 总有对应的确定型自动机 。 对 BNF文法则
没有, 除非文法无二义并满足某些其他限制 。
对无二义 BNF文法, 已找到直接的语法分析技术 。 最早
的技术是递归下降法 。
主要的进展是 Knuth的 LR文法 （ left to right parsing
algorithms）, 可描述所有可用确定型压栈机识别的 BNF
文法 。
LR（ 1） —— 为了确定分析决策, 只需向前看一个符号 。
SLR—— simple LR,LR的子类
LALR—— lookahead LR
LL—— 自顶向下技术, 是递归下降的推广
语义建模
语言的手册必须定义语言中每个结构的含义，包括单独结
构的含义以及和其他结构组合时的含义。
语言提供了不同结构，用户（为了写正确的程序，预测语
句的执行效果）和实现者（正确地实现语言）需要这些结
构的精确定义。
大多数语言中，形式文法用于定义语法，一段文字或例子
用于定义语义，但定义是不精确的，有二义性，不同作者
可能有不同理解。
语义定义问题还是理论研究的目标，但至今没有令人满意
的解答。
已有各种形式方法用于语义定义。
?文法模型
对定义语言的 BNF文法进行扩展，给出程序的语法分析
树，从树中抽取出附加信息。属性文法便是抽取附加信
息的一种方式。
?命令或操作模型
定义程序如何在某虚拟机上执行。通常描述为一自动机，
但比语法用的简单自动机远为复杂。
自动机有内部状态 —— 对应程序执行时的内部状态，包
括所有变量的值、执行程序本身、以及各种系统定义的
数据结构。
一组形式定义的操作用于刻划自动机内部状态如何改变。
此外还需定义程序文本如何翻译成自动机的初始状态。
语言的操作定义对语言如何实际执行给出了相当直接的
抽象。
也可能提出一个更抽象的模型，作为语言的软件解释的
基础。
70年代的 VDL（ Vienna Definition Language）是一个操
作方法。
它扩展语法分析树以包含机器解释器。
计算的状态是程序树加上描述机器中所有数据的树。
每条语句的执行使树的状态发生变化。
?作用型模型
试图直接构造每个程序的功能的定义, 采用层次式的构
造方式 。
程序中每个基本的或程序员定义的操作代表一个数学函
数 。
语言的程序控制结构用于将这些函数复合为更大的序列,
代表表达式和语言 。
语句序列和条件分叉表示为个体函数构造而成的函数 。
循环通常表示为递归函数 。
最终, 为整个程序导出一个完整的功能模型 （ 函数模
型 ）, 指称语义归于此类 。
?公理模型
使用谓词演算，每个语法结构的语义被描述为公理或推
导规则，用于导出结构的执行效果。
从一个初始假设开始,
假设输入变量满足一定的约束,
在程序语句执行后，使用公理和推导规则来推导其
他变量值需满足的限制,
最终，程序的结果被证明满足希望的约束（描述了
它们的值和输入值的关系）。
如 Hoare的公理语义。
?规约模型
描述实现程序的各个函数的关系，只要我们可以证明一
个实现符合任意两个函数间的关系，则称实现相对于规
约是正确的。
代数数据类型是形式规约的一种形式。
例如：实现栈的程序,S表示栈，则有公理,
pop(push(S,x))=S
任何一个实现如果能保持这种关系，则称是栈的正
确实现。
?上述各种形式语义模型各有优点，但均不能称为完全实用
的和适用的，各有其适合范围。
?属性文法
这是最早的开发语义模型的工作之一。
其思想是对分析树中的每个结点关联一个函数，从而给
出结点的语义内容。
属性文法的创建是通过加函数（属性）到文法中的每一
条规则。
继承属性是一个函数，它将树中非终结符值和树中更高
层的非终结符值相关联。换言之，任何规则右端的非终
结符的函数值是左端非终结符的函数。
综合属性是一个函数，它将左端非终结符和右端非终结
符的值相关联，这些属性在树中向上传递信息，即从树
中下层信息进行“综合”。
例：考虑算术表达式的简单文法。
E→T|E+T
T→P|T × P
P→I|(E)
其语义通过文法中非终结符间的关系集合定义。如：下
面函数生成该文法生成的任意表达式的值,
产生式 属性
E→E+T Value(E1)=V(E2)+V(T)
E→T V(E)=V(T)
T→T × P V(T1)=V(T2)× V(P)
T→P V(T)=V(P)
P→I V(P)=数 I的值
P→(E) V（ P） =V（ E）
下图是一个属性树，它给出了表达式 2+4× （ 1+2）值
属性文法可用于在语法树中传递语义信息。例如，声明
信息可以通过语言的声明产生式收集。沿树向下传的符
号表信息可用于生成表达式代码。
下面属性可加到非终结符 <decl>和 <declaration>来创建一
个程序中声明的名字集合。
产生式 属性
<declaration>::=<decl><declaration> decl_set(declaration1)=declaname(decl)
∪ decl_set(declaration2)
<declaration>::=<decl> decl_set(declaration)=decl-name(decl)
<decl>::=declare x decl-name(decl)=x
(decl)::=declare y decl-name(decl)=y
(decl)::=declare z decl-name(decl)=z
这是综合属性，包含程序中声明的名字集合。该属性可
以沿树向下传递，成为继承属性，用于正确地生成数据
的代码。
语 言 翻 译
3.1 语言的语法
?语法：单词作为语句中元素的显示它们之间关系的布局 。 描述
了构成有效程序的符号序列 。 如 C中, x=y+z是有效的符号序列,
而 xy+－则不是 。
?语法提供了理解程序需要的有意义的信息 。 也提供了大量源程
序到目标程序翻译所需的信息 。
?单 靠 语 法 并 不 足 以 无 二 义 地 刻 划 语 句 的 结 构 。 如：
x=2.45+3.67,语法并不能告诉我们 x是否被声明或是否声明为
实数 。 x=5,6或 6.12均是可能的 。
?因此, 对语言的完整描述单靠语法结构是不够的, 还需涉及语
义 。 如：声明的使用, 操作, 顺序控制和引用环境等影响变量,
并不总是由语法决定 。
?虽然如此, 语法仍是语言描述中的重要属性 。
?现在, 语法描述已是一个解决了的问题, 源程序的语法理解阶
段是相当机械的, YACC等工具可自动生成给定程序的语法描
述 。
一般语法准则
?语法的主要目的是为程序员和语言处理器间通讯提供一套
注记方法 。 而特殊语法结构的选择被限制于特殊的信息项
通讯 。
例如：某特定变量有类型实数, 可以用多种方式表达 。
可以是显示声明或隐含的命名约定, 等 。
?语法细节的选择大部分是基于第二准则, 如可读性, 它和
通讯的主要目标无关 。
?有很多二级准则, 通常可按其目标分类, 分为：易读, 易
写, 易翻译, 无二义等目标 。 这些目标间有时会有冲突 。
?易读性 （ Readabitity）
程序是易读的, 如果程序表示的算法和数据的结构可从程
序文本的检查明显了解 。 一个易读的程序, 通常称为自文
档的 （ 不需其他用于理解的辅助文档 ） 。
增加易读性的方式：自然的语句格式, 结构化语句, 关键
字和噪音字的自由使用, 嵌入式注释机制, 不限长标识符,
记忆操作符, 自由域格式, 完全的数据声明等 。
易读性并不能由语言设计保证, 最好的设计也可能由于糟
糕的编程而破坏 。 当然, 语法设计也可能使最有意识的程
序员写出难理解的程序, 如 APL。 COBOL强调易读, 但其
代价是牺牲了易写和易翻译 。
增加易读性 — 语法不同应反映语义不同, 做相似事的程序
结构是相似的 。 做不同事的程序其结构需有明显不同 。 语
言如只提供了少数不同语法结构, 通常导致程序易读性差 。
如 APL,SNOBOL4等, 只提供一种语句格式, 赋值, 子程
序调用, 简单 GOTO,子程序返回, 多路条件分支, 及其它
常见程序结构的差异只能通过个别操作子的不同来反应 。
?易写性
易写性 （ 使用简明的, 规则的语法结构 ） 通常和易读性 （ 冗
余结构是有帮助的 ） 相冲突 。
隐含的语法约定允许声明和操作不需刻划, 从而使程序更短,
更易写, 但不易读 。 其他特性对两个目标均有增强：如结构
化语句, 简单自然语句格式, 记忆操作符, 未限制标记符等
通常使程序易写, 通过允许在程序中直接表示问题的算法和
数据的自然结构 。
语法称为冗余的, 如果以多种方式传达同样的信息 。 有些冗
余性有用的, 因它允许程序易读, 并允许翻译时错误检测 。
缺点是不易写 。
大多数缺省规则 （ 针对语言结构含义 ） 试图减少冗余, 通过
删去某些显式的含义陈述, 因为这些含义可从语境中导出 。
例, Fortran中约定, I-N打头的变量为整型, 其他为实数,
这样不需声明, 但缺点是有副作用, 如：拼写错误不能被编
译器检测到, 例如,INDEX被写成 INDX→ 则变成新变量 。
?易验证性
和易读, 易写相关的概念是程序正确性或程序验证 。
多年经验表明, 理解每条程序语言语句是容易的, 创建正
确程序的整个过程却是困难的 。
因此, 需有技术, 使得能数学地证明程序是正确的 。
?易翻译性
即易于翻译成可执行形式 。
易读性和易写性是面向程序员的需要 。 易翻译性 （ 关键是
结构的正则性 ） 是面向翻译器 （ 处理被写成的程序 ） 的需
要 。
如 LISP程序, 不易读, 也不易写, 但易于翻译, 主要由于
其语法简单且正则 。
当特殊语法结构增加, 将导致翻译困难, 如 COBOL,允许
大量的语句和声明形式 。
?没有含混性
含混性是语言设计中的一个中心问题 。
一个语言定义理想地为每个语法结构提供唯一的意义 。
而含混性结构允许两个或多个不同解释 。 通常不是由个体
程序元素的结构产生, 而是由于不同结构的交迭 。
例如,
if Boolean exp then statement1 else statement2,
If Boolean exp then statement1
当两种形式组合时, 有可能出现二义情况 。
Fortran中, A（ I,J） 可能是数组元素, 也可能是函数调用 。
事实上, 上面提到的含混在语言中均有解决方案 。
条件语句的两种不同解释,
例：因组合而形成的悬空 else,
If Boolean exp1 then if Boolean exp2 then stat1 else stat2
Algol解决方案：改变语法，引入分界符 begin…end 。
Ada解决方案：每个 if语句必须以 end if分界符结尾。
C和 Pascal解决方案：从二义结构中任选一种解释。对本例
而言，最后的 else总是和最近的 then配对。
FORTRAN中函数调用和数组引用的二义性由规则解决：
A(I,J)被视为函数调用，如果没有数组 A的声明。但这个假
定只能在程序装载、链接时被检查。
Pascal中区分二者的方法是使用不同的括号，如,[…] 用于
界定数组参数,(…) 用于界定函数调用的参数。
语言的语法元素
语言的语法风格由各种基本语法元素的选取所决定。
?字符集
字符集的选择是语言设计的第一件事 。
已有一些标准字符集, 如,ASCII码 。 通常是选择一个标
准的字符集 。 但也有不标准的, 如 APL。
字符集的选择对确定可被用于语言实现的 I/O设备的类型
是非常重要的 。 如,C的字符集可用于大多数 I/O设备 。
而 APL的字符集则不能直接用于大多数 I/O设备 。
通常用 8位来表示字符 （ 60年代早期用 6位 ）, 这似乎是
足够的 。 但是, 随着计算机产业的国际化进程, 可能 16
位表示是必需的 （ 可有 65536个字符 ） 。
?标识符
字和数字串, 以字母开头 —— 常用的选择 。
也可能使用特殊字符, 如用,或 -来改善易读性和长度限
制 。
?操作符符号
+,-,*,/表示基本算法操作 。
通常原操作可完全使用特殊符号 。
当然, 也可以使用标识符来表示原操作, 如 LISP中的
PLUS,TIMES。
大多数语言采用二者的组合 。
?关键字和保留字
关键字 —— 用于语句语法中固定部分的标识符 。
保留字 —— 不能被程序员使用的关键字 。
大多数语言使用保留字以改善翻译器的错误检测能力,
使语法分析更为容易 。
?噪声字
可选的字, 被插入语句中以改善易读性 。
如,COBOL中 Go语句可写为 GO TO
?注释
是文档中的重要部分, 几种注释方式,
1,分别的注释行, Fortran
2,特殊标志界定, /* */,界定字符丢失可能导致大面积
出错 。
3,在行中任意地方开始, 但在行末结束, 如 C++的 //
?空白 （ 空格 ）
语言中常使用空白规则, 通常都是作为分隔符 。
也有的语言中空格有其他用途 。
?界定符 （ 分界符 ） 和括号
用于标记语法单位的开始和结束
括号是一对分界符 。
?自由和固定域格式
自由域 —— 语句可写在任何地方
固定域 —— 在输入行中通过位置来传递信息 。 Fortran是
典型例子 。
当前固定域越来越少 。
?表达式
访问程序中数据对象并反回值, 是基本的语法建筑块 。
在命令型语言中, 表达式形成基本操作, 状态被语句所
改变 。
在作用型语言中, 表达式形成了驱动程序执行的基本顺
序控制 。
?语句
是命令型语言中最主要的语法部件 。 语句的语法对语言
整体的正则性, 易读性和易写性有着关键影响 。
有的语言采用单一语句格式, 强调正则性；而其它语言
对不同语句类型使用不同语法, 着重于易读性 。
语句结构中的一个更重要的差异是：结构性 （ 或嵌套 ）
语句和简单语句 。
程序 —— 子程序结构
?分开的子程序定义
Fortran中, 每个子程序定义被处理为分开的语法单元,
每个子程序被分别编译, 被编译程序在装载时链接 。
这种组织方式主要是针对这样一种情况：每个子程序均
需含所有数据元素的完整数据声明, 即使是对那些在
COMMON块中的或与其它子程序共享的数据 。 需要这
些声明主要是由于分开编译的需要 。 基本的子程序单元
用于表示通常提供相关功能的结构 。
?分开的数据定义
把所有操作于给定数据对象之上的操作组合在一起, 如
C++中类 。 主要是基于数据抽象的原则 。
?嵌套的子程序定义
如 PASCAL,子程序定义在主程序中作为声明出现, 子
程序本身又可含有其他子程序定义 。
其目标是强调结构化的语句, 但事实上产生了不同用途 。
结构化语句的引入主要是为算法结构的常见的层次划分
提供一种自然的注记方式, 但嵌套子程序定义为编译时
定义的子程序提供了非局部的作用环境 。 从而允许静态
类型检查, 和有效的可执行代码的生成 。
没有子程序定义的嵌套, 则必须为每个在子程序定义中
的非局部变量提供声明, 或将所有非局部引用的类型检
查推迟到运行时 。
嵌套的另一好处是作用域管理 。 允许子程序名具有较少
的作用域 。
? 分开的接口定义
FORTRAN的结构允许分开子程序的非常容易的编译, 但
缺点是不同子程序共享的数据可能有不同的定义, 而这
种不同是编译器在编译时无法检测到的 。
PASCAL允许编译器访问所有这样的定义以帮助发现错
误, 缺点是全部程序, 即使其有上千条语句, 必须在每
次修改后重新编译 。
结合上面的技术可以改善编译行为 。
程序实现由几个相互交互的子程序构成, 这些部件称为
模块, 将被连接在一起以创建可执行程序, 但每次只有
修改的模块被重编译 。 而在一个部件中的过程间传送的
数据必须具有公共声明, 从而允许编译器的高效检查 。
为了在分开的编译模块间传递数据, 引入了规约部件,
如 C中,h文件 。 Ada中的 Package（ 接口定义规约 +实现
体 ） 。
?数据描述和可执行语句分离
COBOL包含了早期的部件结构形式 。 在 COBOL中, 所
有子程序的数据声明和可执行语句被分入不同的程序中,
即数据段和过程段, 而用环境段包含关于外部操作环境
的声明 。
一个程序的过程段被组织为子单元, 以对应子程序体,
但所有数据对所有子程序均是全局的, 没有东西对应于
通常子程序中的局部数据 。
中心化数据段的优点是：强迫形成数据格式和过程段中
算法的逻辑独立性, 数据结构的细小修改可只修改数据
段而不需修改过程段 。 同时将数据描述搜集到一个地方,
而不是散布在子程序中也是方便的方式 。
这适合于大量数据的处理 。 在某种意义是, 数据库应用
是这种形式的扩展 。
?未分离的子程序定义
不分开主程序和子程序语句, 如 SNOBOL4中, 程序是
一个语句表 。
子程序间没有语法分隔, 函数调用开始新的子程序执行,
返回语句结束该子程序 。
程序作为是动态的 。 事实上, 任意语句可以同时是主程
序的一部分, 也可以是子程序的一部分 。 这体现在该语
句可在主程序的执行中某点被执行, 而后又在某子程序
的执行中某点被执行 。 这种混沌结构仅仅对允许运行时
翻译和相对简单的新语句和子程序执行机制具有价值 。
?BASIC
简单的语法, 和前述设计目标均有冲突 。
主要面向非科学家用户 。
3.2 翻译的阶段
?逻辑上, 翻译可分为两个主要部分 （ 输入源程序的分析, 可执
行目标程序的综合 ）, 两个阶段又可细分 。
?大多数翻译器的中这些逻辑阶段不是可以明确划分开的, 而是
混合在一起使得分析和综合交替进行 （ 通常逐条语句进行 ） 。
? 编译器通常对源程序扫描两遍
第一遍将程序分解为部件并从程序中导出信息 。
第二遍根据这些收集的信息生成目标程序 。
?如果编译速度是重要的考虑 （ 如教学用编译器 ）, 一遍扫描是
常用方式, 在程序被分析时, 立即被翻译为目标代码 。
?如果执行速度是重要考虑, 三遍甚至更多遍扫描也是可能的 。
第一遍分析源程序 。
第二遍使用各种定义好的优化算法将源程序重写为更多效
的形式 。
第三遍生成目标代码 。
源程序的分析
?语法分析
将源程序字符流分隔, 分组, 成为一些基本的构成成分,
如,标识符, 分界符, 操作符, 数, 关键字, 噪音字,
空白, 注释等 。
这些称为语法项, Token。
?语法分析 （ parsing）
标识大的程序结构 （ 语句, 声明, 表达式等 ） （ 基于前
面得到的 Token） 。
通常语法分析和语义分析交替进行 （ 使用栈作为通讯工
具 ） 。
语法分析器向栈中输入各种语法单元元素, 语义分析器
检索并处理 。
需要高效的语法分析技术, 主要基于形式化文法的应用 。
?语义分析 —— 翻译的中心阶段
处理语法分析器识别的语法结构, 并开始形成可执行目
标码的结构, 语义分析是分析和综合间的桥梁 。
这阶段的工作包括一些重要工作, 如符号表维护, 大多
数错误检测, 宏扩展以及编译时语句的执行 。
在简单情况下, 语义分析器直接生成可执行代码, 但大
多数情况下, 是产生最终可执行程序的某种内部格式,
然后被优化处理 。
语义分析器可分为一些小的语义分析器, 各自处理一特
殊类型的程序结构 。 它们之间通过存放在各种数据结构,
特别是中心符号表中的信息而进行交互 。
?常见的语法分析功能,
1,符号表维护
符号表 （ 最早由词法分析形成 ） 含有对程序中不同标识
符的表项 （ 不仅含标识符, 还包含涉及标识符属性的附
加数据, 如：标识符类型, 值类型, 引用环境等 。 ）
语义分析器在处理声明, 子程序头, 语句等时, 填入相
关信息 。
编译型语言的符号表在翻译结构后通常丢弃 。
但有的语言在执行时仍保留, 如：允许运行时创建新标
识符的语言 （ ML,LISP等, 符号表是运行时的中心数
据结构 ）, 以及辅助调试 （ dbx使用运行时符号表来调
试 C程序 ） 。
2、隐含信息的插入
在源程序中, 有的信息经常是隐含的, 必须在低级目标
程序中显式化 。
这类隐含信息包括：一些缺省约定信息, 类型推导信息
等 。
3,错误检测
语法和语义分析器必须能够处理不正确的和正确的程序 。
语法分析器可能会接受到和当时语境不相容的词法项,
如：表达式中出现分界符, 语句序列中出现声明等 。
更微妙的错误有：实数变量出现在需要整数的地方, 对
声明只有二维的数组出现三维下标引用等 。 属语义错 。
语义分析器不仅需要能够识别这样的错误并产生适当的
出错消息, 还必须能够在大多数情况下, 确定合适的方
式以继续剩余程序的语法分析工作 。
4,宏处理和编译时操作
并非所有语言具有宏特征和编译时操作 。 但如果具备,
通常在语义分析中处理 。
语义分析器必须识别宏调用并处理宏替换 。 通常, 该任
务需要中断词法和语法处理, 而让它们去处理宏体中的
字符流 。 另一个方法是宏体可能已预先被部分翻译, 语
义分析器可以直接处理, 在继续源程序分析前插入适当
的目标码并建立合适的表项 。 用于控制翻译 。
编译时操作是在翻译中完成的操作，用于控制源程序的
翻译。 C中提供了大量这样的操作。如,
#define允许常量或表达式在程序被编译前计值。
#ifdef允许不同的代码序列被编译，根据某些变量的存在
与否。
这些设施允许程序员修改被编译的语句序列。
目标程序的综合
翻译的最后阶段是根据语义分析的结果, 构造可执行程序 。
?优化
语义分析器通常以某种中间形式来产生可执行程序, 中
间形式可以是操作符和操作数的串, 也可以是操作符和
操作数序列的表 。 在代码生成前, 对中间形式进行优化
处理是必要的 。
?代码生成
在中间形式被优化后, 必须产生最后的输出结果：可执
行程序 。 它可能是汇编语言语句, 机器代码序列或其它
目标形式 。 它可能能够直接执行, 也可能需要链接装载
后才可执行 。
?连接和装载
形成最终可运行程序 。
3.3 形式翻译模型
?编译器理论的语法识别部分是相当标准的, 通常基于上下文
无关理论 。
?语言语法的形式定义通常称为文法 （ grammar）
?一个文法由一个规则集合组成, 规则被称为产生式, 刻划了
形成允许程序的字符序列 。
?一个形式文法是用严格定义的记号体系刻划的文法 。
?编译技术中常用两类文法 。
BNF文法 （ 上下无关文法 ）
正则文法
BNF文法
Backus-Naur Form。 John Backus开发，用于 Algol语言的语法
定义。 Peter Naur是开发 Algol委员会的主席。几乎同时，语
言学家 Noam Chomsky设计了上下文无关文法来定义自然语
言的语法。在能力上，二者是等价的，差异只是符号体系不
同。
?语法
BNF文法包含一个 BNF文法规则的有限集合, 它定义了一
个语言 。
语法仅仅涉及形式而不涉及含义, 一个语言从语法上考
虑, 由一个语法正确的程序集合构成, 每个程序只简单
地是一个字符序列 。
语法正确的程序不一定有语义, 即可能不一定计算出什
么结果, 甚至没有结果 。
不考虑语义, 语言是任意有限字符串的集合, 这些字符
选自某固定符号集 。
因此，下面均为语言
1、所有 C中赋值语句的集合
2、所有 C程序的集合
3、所有 LISP原子的集合
4,a,b.构成的序列的集合，所有 a在所有 b之前。
语言可包含有限的串集合，也可能包含无限的串集合。
考虑上面例子，可发现用自然语言描述语言带来了一些
问题，如,4例中,b是否是语言的成员？是否串上必须
有 a？因此，描述并不完整。
解决这个问题的方法：给出形式的数学规则集合，准确
地确定语言中的串是什么？
最简单的文法规则是列出有限语言的所有元素，如,
<digit>:=0|1|2|3… 8|9
这里 <digit>表示一个非终结符或语法范畴, 0－ 9为终结
符 。
一旦定义了基本的语法非终结符集合, 可以构造更复杂
的串, 如,
<conditional statement>::=
If <Boolean exp> then <statement> else <statement>
| if <Boolean exp> then <statement>
规则定义的非终结符可本身被用在规则中, 从而形成递
归规则 。
<unsigned integer>::= <digit> |
<unsigned integer><digit>
一个更复杂的文法，定义一组简单赋值语句。
?语法分析树（ parse tree）
给定文法，可使用单替换规则生成语言的串。
如：下面文法生成平衡的括号序列,
S→SS| （ S） |（）
一个推导过程,
S→ （ S） → （ SS） → （（） S） → （（）（））
推导中的每个项称为语句形式。语言是语句形式的集合，
每个语句形式只含有终结符，并可从文法的初始符号推
导出来。
为了确定是否一给定串是一个文法定义的语言的语法合
格程序。我们必须使用文法规则去构造串的语法分析，
如成果地分析，则是该语言的程序。
赋值语句 W=Y*(U+V)的语法分析树,
BNF文法将一个结构赋给语言中的每个串。
注意，被赋的结构实质上是一棵树，这是由于 BNF文法
的限制。树的叶节点是单个字符或词法项，中间的分叉
点是一个语法范畴，由非终结符标记，根节点是表示整
个语言的非终结符。
分析树为程序提供了大部分的直觉的语义结构。
同样的语言可被很多不同文法定义，如图 3.5定义的语
言和图 3.3是一样的。
不能用 BNF文法定义的语法是那些涉及上下文依赖的语
法，如：如下限制不能用 BNF刻划。
同样的标识符不能在相同块中声明两次。
每个标识符必须声明在包括其使用点的块中。
一个用二维声明的数组不能用三个下标引用。
此类限制必须用对显式化 BNF的补遗来定义。
赋值语句的另一个 BNF定义,
?含混性（二义性）
多义性通常是文法中的问题，而不一定是语言的问题。
如,G1,S→SS|0|1
具有二义性，如图 3.6所示。
如果对给定语言的每个文法均是含混的，则称语言是固
有含混的。
然而上面 G1文法描述的语言不是含混的，因为可以为它
写出不含混的文法。
G2,T→0T|1T|0|1
?BNF记号法的扩展
BNF文法比较简单，但用于描述语言却有诸多不便。
将其适当扩展后更易用。
可选性元素用 [……] 表示。
选择用 |表示。
重复用 {……}* 表示。
图 3.7给出了简单赋值语句的扩展 BNF文法。
?语法图
也称铁道图，是扩展 BNF的图形表示。
图 3.7中的描述可用图 3.8等价表示。
有限状态自动机
语言由 Token构成,Token具有简单的结构。
这里主要给出识别 Token的机器模型，有限状态自动机或状
态机。这是一种有效的识别 Token的工具，只要知道当前所
处状态，就可以确定现有输入是否为 Token的一部分。
图 3.9,FSA，识别奇数个 1构成的串。
输入 100101的机器操作如下处理,
输入 当前状态 接受串否？
Null A no
1 B yes
10 B yes
100 B yes
1001 A no
10010 A no
100101 A yes
通常, FSA有一个开始状态, 一个或多个终态, 以及一组从
状态到状态的变迁 。 任何串, 只要能使机器从初态到终态
（ 通过一系列变迁 ）, 则该串为机器所接受 。
图 3.10,识别带符号整数 。
?非确定型有限自动机
确定型 FSA—— 对其每个状态，每个输入符号，有唯一的
变迁到相同或不同状态。
非确定型 FSA具有,
1、一个状态集合
2、一个初始状态
3、一个终止态集合
4、一个输入符号集合
5、一个从状态到状态的变迁集合，每个变迁接受来
自输入符号集的一个元素。
非确定性是指：从一个状态有多个具有相同标记的弧线
连出，从而必须作出选择。
一个串称为可接受的，如果存在从初始结点到终止结点
之一的路径，即使其他路径可能不能到达某终态。
?正则文法
是 BNF文法的特例，等价于 FSA，形式为,
<nontrerminals>::=<terminal><nonterminal>|<terminal>
例,A→0A|1A|0 产生以 0为结尾的 01串。
?正则表达式
正则表达式是语言定义的另一种形式，等价于 FSA和正
则文法。
定义,
1、单个终结符是正而表达式
2、如 a,b是正则表达式，则 a?b,ab,(a),a*也是正则表
达式。
3、除 1,2外，没有其他是正则表达式。
可以用正则表达式来表示任何用正则文法或 FSA定义的语
言，虽然将任意 FSA转换为正则表达式并不总是明显的。
下面两图为到 FSA的转换,
压栈自动机 Pushdown Automata
PDA是类似于 FSA的抽象模型机，等价于 BNF文法，它具有
有限个状态，有一个下压栈，其移动规划如下,
1、读输入符号，并读栈项符号
2、基于两个输入，机器进入一个新状态，并写 0个或多
个符号在栈顶。
3、如果栈空，则串被接受（或 PDA处于终态）
易于看出 PDA比 FSA具有更强大的能力。
如,anbn不能被 FSA识别，但可以被 PDA识别。
PDA接受的语言等价于上下文无关语言。
考虑产生串的最左推导的过程, 在这种情形, 语句形式存放
在栈中, PDA的操作如下,
1,如栈顶是终结符, 将其和下一输入比较, 如相同, 则
弹出栈 。 如不相匹配, 则出错 。
2,如栈顶是非终结符 X,用串 а替代 X,а是产生式 X→а
的右端 。
这样 PDA模拟了上下文无关文法的最左推导, 这种构造实际
上形成了一个非确定型 PDA,等价于对应的 BNF文法 。
在第二步中, 可能有多个 X→α 样式的规则, 规则的选用需
人来选择 。
确定型 PDA和非确定型 PDA间关系, P94-95的回文例子 。
确定型 PDA等价于 LR（ K） 文法, 对实际的编译器设计是非
常重要的 。
高效的语法分析算法
文法描述语言是自顶向下，而语法分析则是自底向上，从
个体字符开始。
?一般的分析策略,
每种类型的形式文法总是和某类型的自动机紧密相关 。
自动机是一种抽象机, 读一个输入带, 产生一个输出带 。
然而, BNF文法可能是含混的, 因此, 自动机必须是非
确定的 。 非确定型压栈机能识别任何上下文无关文法,
通过使用猜测策略 。
对语言翻译而言, 不需猜测的确定型自动机是需要的 。
对正则文法, 总有对应的确定型自动机 。 对 BNF文法则
没有, 除非文法无二义并满足某些其他限制 。
对无二义 BNF文法, 已找到直接的语法分析技术 。 最早
的技术是递归下降法 。
主要的进展是 Knuth的 LR文法 （ left to right parsing
algorithms）, 可描述所有可用确定型压栈机识别的 BNF
文法 。
LR（ 1） —— 为了确定分析决策, 只需向前看一个符号 。
SLR—— simple LR,LR的子类
LALR—— lookahead LR
LL—— 自顶向下技术, 是递归下降的推广
语义建模
语言的手册必须定义语言中每个结构的含义，包括单独结
构的含义以及和其他结构组合时的含义。
语言提供了不同结构，用户（为了写正确的程序，预测语
句的执行效果）和实现者（正确地实现语言）需要这些结
构的精确定义。
大多数语言中，形式文法用于定义语法，一段文字或例子
用于定义语义，但定义是不精确的，有二义性，不同作者
可能有不同理解。
语义定义问题还是理论研究的目标，但至今没有令人满意
的解答。
已有各种形式方法用于语义定义。
?文法模型
对定义语言的 BNF文法进行扩展，给出程序的语法分析
树，从树中抽取出附加信息。属性文法便是抽取附加信
息的一种方式。
?命令或操作模型
定义程序如何在某虚拟机上执行。通常描述为一自动机，
但比语法用的简单自动机远为复杂。
自动机有内部状态 —— 对应程序执行时的内部状态，包
括所有变量的值、执行程序本身、以及各种系统定义的
数据结构。
一组形式定义的操作用于刻划自动机内部状态如何改变。
此外还需定义程序文本如何翻译成自动机的初始状态。
语言的操作定义对语言如何实际执行给出了相当直接的
抽象。
也可能提出一个更抽象的模型，作为语言的软件解释的
基础。
70年代的 VDL（ Vienna Definition Language）是一个操
作方法。
它扩展语法分析树以包含机器解释器。
计算的状态是程序树加上描述机器中所有数据的树。
每条语句的执行使树的状态发生变化。
?作用型模型
试图直接构造每个程序的功能的定义, 采用层次式的构
造方式 。
程序中每个基本的或程序员定义的操作代表一个数学函
数 。
语言的程序控制结构用于将这些函数复合为更大的序列,
代表表达式和语言 。
语句序列和条件分叉表示为个体函数构造而成的函数 。
循环通常表示为递归函数 。
最终, 为整个程序导出一个完整的功能模型 （ 函数模
型 ）, 指称语义归于此类 。
?公理模型
使用谓词演算，每个语法结构的语义被描述为公理或推
导规则，用于导出结构的执行效果。
从一个初始假设开始,
假设输入变量满足一定的约束,
在程序语句执行后，使用公理和推导规则来推导其
他变量值需满足的限制,
最终，程序的结果被证明满足希望的约束（描述了
它们的值和输入值的关系）。
如 Hoare的公理语义。
?规约模型
描述实现程序的各个函数的关系，只要我们可以证明一
个实现符合任意两个函数间的关系，则称实现相对于规
约是正确的。
代数数据类型是形式规约的一种形式。
例如：实现栈的程序,S表示栈，则有公理,
pop(push(S,x))=S
任何一个实现如果能保持这种关系，则称是栈的正
确实现。
?上述各种形式语义模型各有优点，但均不能称为完全实用
的和适用的，各有其适合范围。
?属性文法
这是最早的开发语义模型的工作之一。
其思想是对分析树中的每个结点关联一个函数，从而给
出结点的语义内容。
属性文法的创建是通过加函数（属性）到文法中的每一
条规则。
继承属性是一个函数，它将树中非终结符值和树中更高
层的非终结符值相关联。换言之，任何规则右端的非终
结符的函数值是左端非终结符的函数。
综合属性是一个函数，它将左端非终结符和右端非终结
符的值相关联，这些属性在树中向上传递信息，即从树
中下层信息进行“综合”。
例：考虑算术表达式的简单文法。
E→T|E+T
T→P|T × P
P→I|(E)
其语义通过文法中非终结符间的关系集合定义。如：下
面函数生成该文法生成的任意表达式的值,
产生式 属性
E→E+T Value(E1)=V(E2)+V(T)
E→T V(E)=V(T)
T→T × P V(T1)=V(T2)× V(P)
T→P V(T)=V(P)
P→I V(P)=数 I的值
P→(E) V（ P） =V（ E）
下图是一个属性树，它给出了表达式 2+4× （ 1+2）值
属性文法可用于在语法树中传递语义信息。例如，声明
信息可以通过语言的声明产生式收集。沿树向下传的符
号表信息可用于生成表达式代码。
下面属性可加到非终结符 <decl>和 <declaration>来创建一
个程序中声明的名字集合。
产生式 属性
<declaration>::=<decl><declaration> decl_set(declaration1)=declaname(decl)
∪ decl_set(declaration2)
<declaration>::=<decl> decl_set(declaration)=decl-name(decl)
<decl>::=declare x decl-name(decl)=x
(decl)::=declare y decl-name(decl)=y
(decl)::=declare z decl-name(decl)=z
这是综合属性，包含程序中声明的名字集合。该属性可
以沿树向下传递，成为继承属性，用于正确地生成数据
的代码。
