编译原理第2讲

1、第第1 1讲作业题讲作业题1.1.解释下列术语：解释下列术语：翻译程序、汇编程序、编译程序、解释程序、源程序、目标程序、翻译程序、汇编程序、编译程序、解释程序、源程序、目标程序、编译程序的前端和后端和趟编译程序的前端和后端和趟2.2.编译程序与解释程序的根本区别在于？编译程序与解释程序的根本区别在于？3.3.一般来说，编译程序分为哪一般来说，编译程序分为哪5 5个阶段，同这个阶段，同这5 5个阶段都要打交道的个阶段都要打交道的是？是？4.4.错误处理的主要任务是什么？对下列错误信息，请指出可能是编错误处理的主要任务是什么？对下列错误信息，请指出可能是编译的哪个阶段报告的？译的哪个阶段报告的？E

2、lseElse没有匹配没有匹配ifif数组下标越界数组下标越界使用的函数没有定义使用的函数没有定义在数中出现非数字字符在数中出现非数字字符5.5. 高级语言书写的源程序只有被高级语言书写的源程序只有被 或者或者 后后才能执行。才能执行。6.6.语言处理程序分为语言处理程序分为 、 和和 。习题答案习题答案1 1、翻译程序翻译程序即语言处理程序，是把以汇编语言或高级语言编即语言处理程序，是把以汇编语言或高级语言编写的源程序翻译成机器语言目标程序的工具。写的源程序翻译成机器语言目标程序的工具。2 2、汇编程序汇编程序是把汇编语言书写的程序翻译成与之等价的机器是把汇编语言书写的程序翻译成与之等价的机

3、器语言程序的翻译程序。语言程序的翻译程序。3 3、编译程序编译程序是将高级语言程序等价地转换成另一种低级语言是将高级语言程序等价地转换成另一种低级语言程序程序( (如汇编语言或机器语言程序如汇编语言或机器语言程序) )的程序。的程序。4 4、解释程序解释程序是把源语言书写的源程序作为输入，对源程序逐是把源语言书写的源程序作为输入，对源程序逐条解释，解释一条就提交计算机执行一条，直至执行完整个条解释，解释一条就提交计算机执行一条，直至执行完整个程序。就像外语翻译中的程序。就像外语翻译中的“同声翻译同声翻译”一样，说一句翻一句，一样，说一句翻一句，不产生全文的翻译文本。不产生全文的翻译文本。5 5

4、、源程序源程序：未经语言处理程序处理的以汇编语言或高级语言：未经语言处理程序处理的以汇编语言或高级语言编写的程序。编写的程序。6 6、目标程序目标程序：源程序经过语言处理程序处理后翻译成的另一：源程序经过语言处理程序处理后翻译成的另一种等价的程序。种等价的程序。编译各阶段的分组编译各阶段的分组前端和后端前端和后端前端前端依赖于源程序并在很大程度上独立于目标机器。前端依赖于源程序并在很大程度上独立于目标机器。前端与源语言有关，包括词法分析、语法分析、语义分析与中与源语言有关，包括词法分析、语法分析、语义分析与中间代码产生，以及相关的错误处理和符号表的建立。间代码产生，以及相关的错误处理和符号表的

5、建立。源语言源语言中间语言中间语言目标语言目标语言前端前端后端后端后端后端主要包括代码优化、代码生成和相关错误处理，后端主要包括代码优化、代码生成和相关错误处理，后端依赖于目标机器。后端处理对象是由前端产生的结果，即依赖于目标机器。后端处理对象是由前端产生的结果，即中间代码。中间代码。所谓所谓趟趟，是对源程序或其等价的中间语言程序从头到尾扫，是对源程序或其等价的中间语言程序从头到尾扫视并完成规定任务的过程。每趟扫视可完成编译过程中一视并完成规定任务的过程。每趟扫视可完成编译过程中一个阶段或多个阶段的工作。个阶段或多个阶段的工作。u编译程序与解释程序的根本区别在于编译程序与解释程序的根本区别在于

6、是否生成目标代码。是否生成目标代码。u一般来说，编译程序分为一般来说，编译程序分为词法分析，语法分析，语义分词法分析，语法分析，语义分析和中间代码生成，代码优化，目标代码析和中间代码生成，代码优化，目标代码生成生成5 5个阶段，个阶段，同这同这5 5个阶段都要打交道的是个阶段都要打交道的是符号管理表程序符号管理表程序和和错误处理错误处理器器。错误处理的主要任务是：错误处理的主要任务是：把检测到的错误局部化，尽可能多把检测到的错误局部化，尽可能多地编译源程序代码，以便发现更多的错误，有可能的话地编译源程序代码，以便发现更多的错误，有可能的话进行适当的错误校正。进行适当的错误校正。对下列错误信息，

7、请指出可能是编译的哪个阶段报告的？对下列错误信息，请指出可能是编译的哪个阶段报告的？ElseElse没有匹配没有匹配ifif（语法分析语法分析）数组下标越界（数组下标越界（语义分析语义分析）使用的函数没有定义（使用的函数没有定义（语法分析语法分析）在数中出现非数字字符（在数中出现非数字字符（词法分析词法分析）p高级语言书写的源程序只有被高级语言书写的源程序只有被编译编译或者或者解释解释后才能后才能执行。执行。p语言处理程序分为语言处理程序分为编译程序编译程序、汇编程序汇编程序和和解释程序解释程序。编译器各阶段编译器各阶段源程序：高级程序设计语言源程序：高级程序设计语言词法分析器词法分析器错错误

8、误处处理理器器符符号号管管理理表表语法分析器语法分析器语义分析器语义分析器中间代码生成器中间代码生成器代码优化器代码优化器代码生成器代码生成器词法单元词法单元语法分析树语法分析树中间代码：三地址码或四元式中间代码：三地址码或四元式中间代码中间代码目标代码：汇编语言或机器语言目标代码：汇编语言或机器语言必要必要必要必要必要必要可选可选可选可选可选可选编译器是分阶段执编译器是分阶段执行的。每个阶段将行的。每个阶段将源程序从一种表示源程序从一种表示转换成另一种表示转换成另一种表示一、词法分析程序（词法分析器）的一、词法分析程序（词法分析器）的功能功能输入源程序，对构成源程序的字符串进行扫描和分解，识

9、输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个别出一个个单词（词素）单词（词素）符号并添加到符号表中符号并添加到符号表中, ,并用并用词法词法单元单元方式表示识别出的单词，生成并输出一个词法单元序方式表示识别出的单词，生成并输出一个词法单元序列。同时还可检查出源程序中的词法错误，如拼写错误。列。同时还可检查出源程序中的词法错误，如拼写错误。源程序源程序词法分析器词法分析器词法单元序列词法单元序列符号管理表符号管理表错误处理器错误处理器输入输入输出输出报错报错一、词法分析程序（词法分析器）的一、词法分析程序（词法分析器）的功能功能= =8 80 0; ;e en ni iL L L

10、 Li in ne e= =8 80 0; ;= = = =; ; ; ;输入输入 25 , Line25 , Line 3636, , 27, 8027, 80 4545, , 输出输出若标识符词类编码为若标识符词类编码为2525，等号词类编码为，等号词类编码为3636，数字常量，数字常量词类编码为词类编码为2727，分号词类编码为，分号词类编码为4545概念概念1 1：单词（词素）：单词（词素） 单词是一个程序设计语言的基本字符。单词是一个程序设计语言的基本字符。 保留字保留字是程序语言定义的具有固定含义的英文单词，有时是程序语言定义的具有固定含义的英文单词，有时称为关键字或基本字。保留字

11、不能作为变量名或过程名使称为关键字或基本字。保留字不能作为变量名或过程名使用。用。 例如：例如：c c语言的保留字包括：语言的保留字包括：auto auto ：声明自动变量：声明自动变量 double double ：声明双精度变量或函数：声明双精度变量或函数 intint： 声明整型变量或函数声明整型变量或函数 structstruct：声明结构体变量或函数：声明结构体变量或函数 breakbreak：跳出当前循环：跳出当前循环 等等 在现今多数程序设计语言中，单词符号一般分为：在现今多数程序设计语言中，单词符号一般分为： 保留字、标识符、常量、运算符和分界符等保留字、标识符、常量、运算符和

12、分界符等概念概念1 1：单词（词素）：单词（词素） 标识符：标识符：在编程语言中在编程语言中，标识符标识符是是用户编程用户编程时用来时用来表示表示各种名字的字符串各种名字的字符串例如：例如：C C语言标识符由字母（语言标识符由字母（A-A-Z,aZ,a-z-z）、数字（）、数字（0-90-9）、下）、下划线划线“_”_”组成，并且首字符不能是数字，但可以是字母或组成，并且首字符不能是数字，但可以是字母或者下划线。例如，正确的标识符：者下划线。例如，正确的标识符：abcabc，a1a1，prog_toprog_to。概念概念1 1：单词（词素）：单词（词素） 常量：常量：指在程序运行过程中指在程

13、序运行过程中, ,其值不可改变的量其值不可改变的量例如：在例如：在C C语言中语言中, ,常量分为如下类型常量分为如下类型整型常量：整型常量：100、-200、32767字符常量：字符常量：b 、y字符串常量：字符串常量：how do you do.,CHINA,a,$123.45浮点型常量：浮点型常量：+1.2E+5、1.5e-9、-5.0e10符号常量：在使用之前必须先定义，其一般形式为：符号常量：在使用之前必须先定义，其一般形式为： #define 标识符标识符 常量，如：常量，如：#define PRICE 30概念概念1 1：单词（词素）：单词（词素） 运算符运算符：包括算术运算符、

14、关系运算符、逻辑运算符、：包括算术运算符、关系运算符、逻辑运算符、赋值号和等号等。赋值号和等号等。例如：例如：C C语言把除了控制语句和输入输出以外的几乎所有语言把除了控制语句和输入输出以外的几乎所有的基本操作都作为运算符处理，包括：的基本操作都作为运算符处理，包括：指针运算符：指针运算符：* *和和& &求字节数运算符：求字节数运算符：sizeofsizeof强制类型转换运算符：强制类型转换运算符：( (类型类型) )分量运算符：分量运算符：. -. -下标运算符：下标运算符： 其他：如函数调用运算符其他：如函数调用运算符:():()算术运算符：算术运算符：* * - + /

15、- + /关系运算符：关系运算符： = = =逻辑运算符：逻辑运算符：! & |! & |位运算符：位运算符： | & | &赋值运算符：赋值运算符：= =及扩展赋值运算符及扩展赋值运算符条件运算符：条件运算符：?:?:逗号运算符：逗号运算符：, ,概念概念1 1：单词（词素）：单词（词素） 分界符分界符: : 包括逗号，分号，括号，结束符等分界符包括逗号，分号，括号，结束符等分界符请将以下请将以下C C程序中的词素进行分类？程序中的词素进行分类？float match0(char *s if (!strncmp(s, 0.0, 3) return 0; 请将以

16、下请将以下C C程序中的词素进行分类？程序中的词素进行分类？float match0(char float match0(char * *s s if (! if (!strncmpstrncmp(s, 0.0, 3)(s, 0.0, 3) return 0; return 0; 保留字保留字运算符运算符分界符分界符标识符标识符常量常量floatfloatmatch0match0( (charchar* *s s ifif! !strncmpstrncmp0.00.0 , ,3 3) )returnreturn0 0; ; 一旦语言确定，这三一旦语言确定，这三类符号就确定，与具类符号就确定，与

17、具体的程序无关。而且体的程序无关。而且这些符号是有限的。这些符号是有限的。这些符号是变化的。这些符号是变化的。与具体的程序有关。与具体的程序有关。词法分析器在读取源程序的时候，还有一个任务是过滤词法分析器在读取源程序的时候，还有一个任务是过滤掉源程序中的注释和空白。掉源程序中的注释和空白。注释：注释： / /* * try again try again * */ /空格：空格： blanksblanksTabTab键：键： tabstabs换行符号：换行符号： newlinesnewlines概念概念2 2：词法单元：词法单元（token字）字） 词法单元：又称记号，由词法分析程序生成的逻辑

18、单词法单元：又称记号，由词法分析程序生成的逻辑单元。元。 词法单元格式：词法单元格式： 词类编码：词法单元词类编码：词法单元种别种别名称。名称。词法单元属性值词法单元属性值: :一个可选的属性值一个可选的属性值, ,用来区分该类用来区分该类 单词中哪一个单词。单词中哪一个单词。 25 , Line25 , Line 词类编码原则词类编码原则: :关键字关键字: :所有的关键字分成一类所有的关键字分成一类（一类一码）（一类一码） 也可以一个关键字分成一类也可以一个关键字分成一类（一字一码）（一字一码）标识符标识符：所有的标识符分为一类：所有的标识符分为一类（一类一码）（一类一码）运算符：运算符：

19、一个符号分成一类一个符号分成一类（一符一码）（一符一码） 也可按类型（关系运算、算术运算等），每个类型也可按类型（关系运算、算术运算等），每个类型 的运算划分成一类的运算划分成一类（一类型一码）（一类型一码）分界符分界符: :一个符号分成一类一个符号分成一类（一符一码）（一符一码）常量常量：所有的统归为一类：所有的统归为一类（一类一码）（一类一码） 也可按类型（整型、实型、布尔型等），每个类型的也可按类型（整型、实型、布尔型等），每个类型的 常数划分成一类常数划分成一类（一类型一码）（一类型一码）词类编码原则词类编码原则: :例：例：以以a=b+ca=b+c* *d d为例为例a a、b b、

20、c c、d d都是标识符，都是标识符，统一归为一类统一归为一类可以将、可以将、* *运算符，运算符，统一归为一类，统一归为一类，也可以赋值运算符也可以赋值运算符= =归为一类，算术运算符归为一类，算术运算符+ +、* *归为归为一类一类一类对应一个编码值一类对应一个编码值例如：某种语言词类编码编码如下表例如：某种语言词类编码编码如下表请书写出此段源程序中各单词的词类编码请书写出此段源程序中各单词的词类编码if ij then i0 else j=1if ij then i0 else j=1对应的词类编码如下：对应的词类编码如下：词法单元属性值词法单元属性值关键字、界符、运算符关键字、界符、运

21、算符：属性值：属性值通常为空通常为空对对于关键字（一字一码）、界符和运算符（一符一码）于关键字（一字一码）、界符和运算符（一符一码）来说，它们的词类编码就可以表示其完整的信息，故对来说，它们的词类编码就可以表示其完整的信息，故对于这类单词，其单词自身的属性值于这类单词，其单词自身的属性值通常为空通常为空。标识符：标识符：属性常用其属性常用其在符号表中的入口指针来表示在符号表中的入口指针来表示对于对于标识符（一类一码）标识符（一类一码），词类编码所反映的信息不够，词类编码所反映的信息不够充分，标识符的具体特性还要通过充分，标识符的具体特性还要通过单词自身的属性单词自身的属性进行进行互相区分，标识

22、符的单词自身的属性常用其互相区分，标识符的单词自身的属性常用其在符号表中在符号表中的入口指针来表示。的入口指针来表示。常数：常数：属性常用其属性常用其在常数表中的入口指针来表示在常数表中的入口指针来表示对于常数（一类型一码），其单词自身的属性常用其对于常数（一类型一码），其单词自身的属性常用其在在常数表中的入口指针来表示常数表中的入口指针来表示if ij then i0 else j=1例如：写出下述语句例如：写出下述语句中词法单元的属性值中词法单元的属性值以语句子以语句子a=b+ca=b+c* *d d为例，假设按表中的单词编码，词法分析为例，假设按表中的单词编码，词法分析后的结果（即：生成

23、并输出一个词法单元序列）为：后的结果（即：生成并输出一个词法单元序列）为：TokenToken字字 符号表符号表 a = b + c a = b + c * * d da 25a 25b 25b 25c 25c 25d 25d 25生成并输出一个词法单元序列：生成并输出一个词法单元序列：, , , , 解题思路提示：解题思路提示：根据根据C+C+程序设计语言的五种分类对号入座程序设计语言的五种分类对号入座词法分析器的词法分析器的设计思路设计思路 按照词法分析程序的任务和作为一个独立子程序的要求来考按照词法分析程序的任务和作为一个独立子程序的要求来考虑词法分析程序的设计。虑词法分析程序的设计。1

24、 1、组织源程序的输入、组织源程序的输入5 5、识别单词，转换成词法单元表示形式、识别单词，转换成词法单元表示形式3 3、删除注释行、空格及无用符号、删除注释行、空格及无用符号2 2、查填符号表、查填符号表4 4、检查词法错误、检查词法错误词法分析器的词法分析器的设计思路设计思路 词法分析的第一任务是输入源程序，过滤掉源程序中的注释词法分析的第一任务是输入源程序，过滤掉源程序中的注释和空白。和空白。 设计思路：可设计一个设计思路：可设计一个预处理子程序预处理子程序，用以完成此项任务。，用以完成此项任务。将源程序输入串放在输入缓冲区中，借助预处理子程序过滤将源程序输入串放在输入缓冲区中，借助预处

25、理子程序过滤掉源程序中的注释和空白，将处理后的源程序输入扫描缓冲掉源程序中的注释和空白，将处理后的源程序输入扫描缓冲区，词法分析器即可对此缓冲区中的字符串进行单词符号的区，词法分析器即可对此缓冲区中的字符串进行单词符号的识别。识别。词法分析器的词法分析器的设计设计 第第1 1步：将源程序语言词素模式用步：将源程序语言词素模式用正则表达式正则表达式描述描述 第第2 2步：将正则表达式转换成等价的步：将正则表达式转换成等价的状态转换图（状态转换图（NFANFA图）图） 第第3 3步：将步：将NFANFA图用子集法转换成图用子集法转换成DFADFA图图 第第4 4步：将步：将DFADFA图简化为图简

26、化为最小化的最小化的DFADFA图图 第第5 5步：将最小化的步：将最小化的DFADFA图作为词法分析程序的框图，借助词图作为词法分析程序的框图，借助词 法分析程序的自动构造工具（如：法分析程序的自动构造工具（如：LEXLEX等）等）设计词法设计词法 分析程序分析程序正则表达式正则表达式 NFA DFA min DFA 词法分析程序词法分析程序字母表的概念字母表的概念 程序是语句的集合，而程序语句也是由保留字、变量名程序是语句的集合，而程序语句也是由保留字、变量名、运算符运算符、常量等单词组成，而这些单词又是、常量等单词组成，而这些单词又是由一些基本由一些基本符号（如字母、数字、运算符和标点符

27、号）符号（如字母、数字、运算符和标点符号）按一定规则按一定规则组成。组成。 字母表字母表（alphabetalphabet）包含了程序设计语言中所允许的所包含了程序设计语言中所允许的所有符号，是一个有穷的非空符号集合。有符号，是一个有穷的非空符号集合。 例如：二进制语言的字母表是例如：二进制语言的字母表是0,10,1英文的字母表是英文的字母表是azaz，AZAZ 字母表通常用希腊字母字母表通常用希腊字母（Sigma）表示。C C语言的字母表：语言的字母表：最简单的方法：查询最简单的方法：查询C C语言用户手册语言用户手册笨办法：自己分析笨办法：自己分析分析思路：分析思路：从保留字、标识符、常量

28、、运算符和分界符的从保留字、标识符、常量、运算符和分界符的构成分析构成分析C C语言的语言的保留字保留字包括：包括：auto auto ，double double ，intint，structstruct，breakbreak，else else ，long long ，switch switch 等，都由英文字母构成，等，都由英文字母构成，而且区分大小写。而且区分大小写。所以字母表中应该包括所以字母表中应该包括AZAZ，azazC C语言的字母表：语言的字母表：C C语言的语言的标识符标识符C C语言标识符由字母、数字、下划线组成。语言标识符由字母、数字、下划线组成。所以字母表中应该包括所

29、以字母表中应该包括A-ZA-Z，a-za-z，0-90-9，_C C语言的常量包括语言的常量包括整型常量：整型常量：100、-200；字符常量：；字符常量：b 、y；字符串常量：；字符串常量：how do you do.,CHINA,$123.45浮点型常量：浮点型常量：+1.2E+5、1.5e-9、-5.0e10所以字母表中应该包括所以字母表中应该包括0-90-9，+，-，,“, A-Z,“, A-Z，a-za-z，.,$.,$C C语言的字母表：语言的字母表：C C语言把除了控制语句和输入输出以外的几乎所有的基本操语言把除了控制语句和输入输出以外的几乎所有的基本操作都作为运算符处理，包括：

30、作都作为运算符处理，包括：指针运算符：指针运算符：* *和和& &求字节数运算符：求字节数运算符：sizeofsizeof强制类型转换运算符：强制类型转换运算符：( (类型类型) )分量运算符：分量运算符：. -. -下标运算符：下标运算符： 其他：如函数调用运算符其他：如函数调用运算符:():()算术运算符：算术运算符：* * - + /- + /关系运算符：关系运算符： = = =逻辑运算符：逻辑运算符：! & |! & |位运算符：位运算符： | & | &赋值运算符：赋值运算符：= =及扩展赋值运算符及扩展赋值运算符条件运算符：条件运算符

31、：?:?:逗号运算符：逗号运算符：, ,所以字母表中应该包括所以字母表中应该包括 * *,-,+, /, , ,a-z|, ,?,:,(,),.,-,a-z C C语言的字母表：语言的字母表：C C语言的分界符包括逗号，分号，括号，结束符等分界符所语言的分界符包括逗号，分号，括号，结束符等分界符所以字母表中应该包括以字母表中应该包括 ，, ,；, ,（, ,），）， ， ， ， ，# #， C C语言的字母表是语言的字母表是 A-ZA-Z，a-za-z0-90-9，+，-，,“, .,$,“, .,$ * *,-,+, /, ,-,+, /, ,A-ZA-Z，a-za-z，0-90-9，_ ，

32、, ,；, ,（, ,），）， ， ， ， ，# #， 的集合的集合 串是由字母表中的符号组成的任何有穷序列。串是由字母表中的符号组成的任何有穷序列。例如：例如：0000， 11 11， 10 10是字母表是字母表=0=0，11上的串上的串练习一下：练习一下：请写出字母表请写出字母表=a,b,c=a,b,c上的串上的串解答：有解答：有a a，b b，abab，acac，baba，caca，abbabb，accacc，abcabc等等。等等。串串（stringstring）的概念的概念在串中，符号是有顺序的，在串中，符号是有顺序的，例如例如abab和和baba是不相同的是不相同的！存在的问题！存

33、在的问题：如果不约定串的长度，这个序列：如果不约定串的长度，这个序列将无穷的写下去。将无穷的写下去。 用用|s|s|表示串表示串s s的长度，是指的长度，是指s s中有多少个符号中有多少个符号例如：例如：bananabanana是长度为是长度为6 6的串，即的串，即|banana|=6|banana|=6注意：注意：允许出现空串，用允许出现空串，用（艾普西隆）（艾普西隆）表示表示空串中不包含任何符号，长度为空串中不包含任何符号，长度为0 0即即| |=0|=0串的长度串的长度和串有关的术语和串有关的术语 串的前缀：串的前缀：从串的尾部删除从串的尾部删除0 0个个或多个符号后得到的串。或多个符号

34、后得到的串。 串的后缀：串的后缀：从串的开始处删除从串的开始处删除0 0个或多个符号后得到的串。个或多个符号后得到的串。 串的子串：从串中删除一个前缀串的子串：从串中删除一个前缀和一个后缀所余下的串。和一个后缀所余下的串。 串的真前缀、串的真后缀、串的串的真前缀、串的真后缀、串的真子串：真子串：既不等于原串，也不等既不等于原串，也不等于空串的前缀、后缀、子串。于空串的前缀、后缀、子串。 串的子序列：串的子序列：从原串中删除从原串中删除0 0个个或者多个符号后得到的串。或者多个符号后得到的串。（bananabanana、bananbanan、banabana、banban、baba、b b、）以

35、以bananabanana串为例串为例（bananabanana、ananaanana、nananana、anaana、nana、a a、）（、a a、nana、anaana、nananana、ananaanana、bananabanana、b b、baba、bnabna、banban、banabana、bnanabnana、bannabanna、bananbanan）前面例子的红色部分前面例子的红色部分（baanbaan、bnnbnn、aaaaaa）求出串求出串abcdabcd的前缀、后缀和子串的前缀、后缀和子串解答：解答：前缀为：前缀为：abcdabcd、abcabc、abab、a a、后

36、缀为：后缀为：abcdabcd、bcdbcd、cdcd、d d、子串为：子串为： 、d d、c c、cdcd、b b、bcbc、bcdbcd、 a a、abab、abcabc、abcdabcd解答：前缀为解答：前缀为n+1n+1 后缀为后缀为n+1n+1 子串为子串为1+n+1+n+（n-1n-1）+1=1+n+1=1+n（n+1n+1）/2/2 真前缀为真前缀为n-1n-1 子序列为子序列为1+C1+Cn n1 1+C+Cn n2 2+C+Cn n3 3+C+Cn nn n=2=2n n串的运算串的运算p 连接运算连接运算(concatenation)：记作：记作xyp x和和y连接是把连接

37、是把y y的符号写在的符号写在x x的符号之后得到的串的符号之后得到的串例如：例如：x=dog，y=house，xy=doghousep 指数运算（幂运算）：记作指数运算（幂运算）：记作s0，s1，si；pSn表示把表示把s自身自身连接连接n次得到的串次得到的串p例如：例如：x=dogx=dog，x x0 0= =，x x1 1=dog=dog，x x3 3=dogdogdog=dogdogdog语言的概念语言的概念定义：若集合定义：若集合A A中的一切元素都是某字母表上的符号串，则中的一切元素都是某字母表上的符号串，则称称A A为该字母表上的为该字母表上的符号串集合符号串集合。串集合通常用大

38、写字母串集合通常用大写字母A A、B B、C C等表示等表示语言语言（languagelanguage）的定义的定义字母表字母表上的一个上的一个语言是该语言是该字母表上字母表上的一些的一些串集合串集合。例如例如C C语言就是语言就是c c语言字母表上的一些符号串的集合。语言字母表上的一些符号串的集合。语言通常用大写字母语言通常用大写字母L L、M M等表示等表示语言的运算语言的运算u语言语言L和语言和语言M的的合并合并运算运算，记作：，记作： L M定义为定义为L M = s | s L 或或 s M 读作：所有属于语言读作：所有属于语言L或属于语言或属于语言M的符号串的符号串s所组成的集合所组成的集合例如：例如： 令令L=A,B,Z,a,b,z 令令M M=0,1,9 语言语言L中包含中包含52个串，每个串是一个字母（即长度为个串，每个串是一个字母（即长度为1） 语言语言M中包含中包含10个串，每个串是一个数字（即长度为个串，每个串是一个数字（即长度为1） LM=A,B,Z,a,b,z,0,1,9， LM表示的集表示的集合是：包含合是：包含62个串，每个串是一个字母或一个数字（即长个串，每个串是一个字母