正规集：正规式表示的集合称为正规集．
• 例：令∑={a，b},∑上的正规式和相应的正规集的例子有：
正规式
正规集
a
{a}
a|b
{a,b}
ab
{ab}
a*
{ ,a,aa,…..任意个a的串}
(a|b)(a|b)
{aa,ab,ba,bb….所有a,b组成的串}
(a|b)*
｛ ,a,b,aa,bb,….. ｝
• 通过语法树，可以得到文法G的句型。
• 从下面的例子说明语法树的构造。 例：G=（{S，A}，{a，b，}，P，S），其中P为
： （1）S—>aAS （2）A—>SbA （3）A—>SS （4）S—>a （5）A—>ba 构造G的语法树。
注意：如果在推导的任何一步, 都是对其 中的最左（最右）非终结符进行替换，则称这 种推导为最左（最右）推导。
第2章 程序语言基础知识
2.1 程序设计语言基础知识
2.2 编译系统基本原理 2.2.1 文法 2.2.2 文法分析 2.2.3 词法分析
2.3 C语言基础
2.1 程序设计语言概述
低级语言(面向机器的语言) 面向对象程序设计语言 (C++，Java，
Smalltalk)
程序设计语言
og ）
逻辑程序设计语言（ Prol
A. 从S 出发推导的、仅包含T 中符号的符号串 B. 从N 中符号出发推导的、仅包含T 中符号的符号
串 C. 从S 出发推导的、包含V 中符号的符号串 D. 从N 中符号出发推导的、包含V 中符号的符号
串
2.上下文无关文法及其语法树（推导树） • 语法树或推导树：是一种描述上下文无关文法的句型推导的直观方法。
• 例：文法G=（{E}，{+，*，i，(，)}，P，E）其中 P为： E—>i E—>E+E E—>E*E E—>(E)
• 今后，对“文法”一词若无特别说明，则均指上下 文无关文法。
• 例（2007年下半年上午第50）：程序语言的大
多数语法现象可用上下文无关文法描述。对于
一个上下文无关文法 G=(N，T，P，S)，其中N
• 例（软设2008年5月上午试题21）：已知某文法G[S]：S→0S0
的符号串可用
(n≥0)描述。
A．(010)n
B．0n10n
C．1n
D．01n0
S→1，从S推导出
• 例（2008年下半年上午第50）：设 某上下文无关文法如下：S→11 | 1 001 | S0 |SS，则该文法所产生的 所有二进制字符串都具有的特点是_ ______。
1.确定的有穷自动机（DFA） • 一个确定的有穷自动机（DFA）M是一个五元组：M
=（K，∑，f，S，Z） 其中
（1）K是一个有穷集，它的每个元素称为一个状态； （2）∑是一个有穷字母表，它的每个元素称为一个
输入字符，所以也称∑为输入符号字母表； （3）f是转换函数，是在K×∑—>K上的映像，即，
∪... 其中，∑n表示 ∑的方幂。假设∑是个符号串，
∑n表示把∑自身连接n次得到的符号串。
• 例如∑=AB，求∑*。 ∑*=∑0∪∑1∪∑2∪…∑n∪... 其中：
∑0= ，表示不包含任何符号的符号串，即空
符号串，其长度为0。 ∑1=AB ∑2=ABAB ……
• 定义：设G[S]是一文法，如果符号串x是从识别符号推导出来的，即有S=>x，则称
一般情况，大写字母表示非终结符； 小写字母表示终结符。
• 例：文法G=（VN，VT，P，S），其中VN={S}，VT ={0，1}，P={S—>0S1，S—>01}.
总结： 一个文法定义的语言是终结符号串的
集合，这些终结符号串应能从文法的起始符号 出发推导出来。
2．∑*： • ∑*称为集合∑的闭包。∑*=∑0∪∑1∪∑2∪…∑n
• 自动机到正规式的转换过程如图所示:
对于
代之
1 R1 2 R2
3
对于
代之
对于
R1
1
R2
代之
2
R2
1 R1
2 R3 3
1
R1 R2
3
1
R1| R2 2
1 R1 R2* R3 3
• 例（2006年下半年上午第45-46）：下图是一有限自动
机的状态转换图，该自动机所识别语言的特点是 （1
）ห้องสมุดไป่ตู้
，等价的正规式为 （2）
经过词法分析后，源程序就转换为单词串。
• 例（软设2005年11月上午试题27）：编译程序进行词法分析时不能________.
A.过滤源程序中的注释 B.扫描源程序并识别句号 C.指出出错的行号 D.查出拼错的保留字
考点2：正规式和正规集 ①正规式和正规集
正规式：用正规表达式（简称正规式）可表示程序语言的单词．
②正规文法到正规式的转换规则
表 正规文法到正规式的转换规则
文法产生式 规则一 A—>xB B—>y
正规式 A=xy
规则二
A—>xA|y
A=x*y
规则三 A—>x A—>y
A=x|y
• 例（2007年下半年上午第48）：正则表达式1*(0|01)*表示的集合元素的特点是__ ______.
A.长度为奇数的0、1串 B.开始和结尾字符必须为1的0、1串 C.串的长度为偶数的0、1串 D.不包含字串011的0、1串
（4）S属于K，S是一个非空的初态集；
（5）Z包含与K，Z是一个终态集。
• 例2：一个NFA M=（{0，1，2，3，4}，{a，b}，f，{0}，{2，4}）其中f定义为 ：
f（0，a）={0，3} f（0，b）={0，1} f（1，b）={2} f（2，a）={2}
f（2，b）={2} f（3，a）={4}
。
（1）A．由符号a、b构成且包含偶数个a的串 B．由符号a、b构成且开头和结尾符号都为a的
串 C．由符号a、b构成的任意串 D．由符号a、b构成且b的前后必须为a的串
• 例（软设2008年5月上午试题20）：编译器对高级语言源程序的处理过程可以划分
为词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成等
几个阶段，其中，
并不是每种编译器都必需的。
A．词法分析和语法分析 B．语义分析和中间代码生成 C．中间代码生成和代码优化 D．代码优化和目标代码生成
• 例（2009年上半年上午第49）：由a、b构造且仅包含偶数个a的串的集合用正规式 表示为__________。 A. (a*a)*b*
B. (b* (ab*a)*)*
C. (a* (ba*)*b)*
D. (a|b)* (aa)*
考点3：自动机 有穷自动机分为两类： 1.确定的有穷自动机（Deterministic Finite Automata） 2.不确定的有穷自动机（Nondeterministic Finite Automata）。
•
对0型文法产生式的形式作某些限制，就是1型、2型、3型文法。
（2）1型文法或上下文有关文法 • 定义：设G=（VN，VT，P，S）为一文法，若P中的每一个产生式a—>b均满足|b|
≥|a|,仅仅S—> 除外，则G是1型文法或上下文有关文法。
（3）2型文法或上下文无关文法 • 定一∪义个VT）产：*生设，式G则=（ a此—V文N>，b法满V为T足，2：P型，a文是S）法一为或非一上终文下结法文符，无，若关b属P文中于法的（。每VN
A．a
B．a、[
C．a、[和]
D．a、[、]和，
2.2.4 词法分析 考点1：词法分析的功能 词法分析阶段的主要功能如下： （1）识别出源程序中意义独立的最小词法单位——单词，并且确定其类型（例如表示符
、关键字、操作符还是数字等）。 （2）删除无用的空格、回车和其它与输入介质有关的无用符号以及程序注释。 （3）报告分析时的错误。
f（4，a）={4} f（4，b）={4}
• 请画出该NFA的状态转换图。
补充：
对于∑*中的任何一个串t，若存在一条从某一初态结点到某一个终态结点 的道路，且这条道路上所有弧的标记符依序连接成的串等于t，则称t可为NFA M所 识别（读出或接受）。
• 例2中的NFA M所能识别的是那些含有相继两个a或相继两个b的串。
2.2 编译系统基本原理 2.2.2 文法 1．文法定义
文法G定义为四元组（VN，VT，P，S），其中： （1）VN为非终结符号（或语法实体，或变量）集； （2）VT为终结符号集； （3）P为产生式（也称规则）的集合； （4）S称为识别符号或开始符号，它是一个非终结符
。一般约定，第一条产生式的左部是开始符号（识 别符号）。
x是文法G[S]的句型。若x仅有终结符号组成，即S=>x，x属于VT*，则称x为G[S]的 句子。
2.2.3 文法分析 1.文法的类型 （1）0型文法
（2）1型文法或上下文有关文法
（3）2型文法或上下文无关文法
（1）0型文法
• 定义：设G=（VN，VT，P，S）为一文法，如果它的每个产生式a—>b是这样一种结 构：a属于（VN∪VT）*且至少含有一个非终结符，而b属于（VN∪VT）*，则G是一 个0型文法。
如态；f为(kkii， ,输a入)=k字j（符k在i属a时于，K，将k转j属换于为K下）一表个示状当态前k状j （4）S属于K，S是唯一的一个初态； （5）Z包含与K，Z是一个终态集，终态也称为可接受
状态或结束状态。
• 例：DFA M=（{S，U，V，Q}，{a，b}，f，S，{Q}）其中f定义为：
是非终结符号的集合，T是终结符号的集合，P