编译原理词法分析课件

第二章词法分析（1）——词法分析的若干问题与模式的形式化描述华侨大学计算机学院陈霞编译原理第二章词法分析（1）——词法分析的若干问题与模式的形式化描1内容简介0、回顾：词法分析1、词法分析中的若干问题词法分析器的作用和工作方式输入缓冲区记号、模式、单词记号的属性2、模式的形式化描述字符串与语言正规式与正规集记号的说明内容简介0、回顾：词法分析2编译原理词法分析课件30、回顾：词法分析词法分析是编译过程中将字符流转换成为符号流的一个工作阶段，是编译的第一步工作，其后续工作是语法分析。词法分析的输入是源代码；词法分析的输出是符号流；词法分析需要识别词法错误，即非法的符号、单词等等。但不识别语法错误。0、回顾：词法分析词法分析是编译过程中将字符流转换成为符号流40、回顾：词法分析的一些思考为什么不直接使用字符串进行后续工作，如语法分析？词法分析还有其他什么作用？词法分析中，把字符流转换成符号流存在着什么困难（什么样的字符串有利于/不利于词法分析的进行）？我们使用什么方法和工具来描述和解决词法分析中遇到的困难？0、回顾：词法分析的一些思考为什么不直接使用字符串进行后续工51.3词法分析器的作用源程序由单词组成，单词是最小的语义单位词法分析器的功能：扫描源程序字符流按照源语言的词法规则识别出各类单词符号产生用于语法分析的记号序列词法分析器的辅助功能跳过源程序中的注释和空白把错误信息和源程序联系起来（错误定位）宏预处理1.3词法分析器的作用源程序由单词组成，单词是最小的语义61.3.2词法分析器的工作方式一、词法分析器与语法分析器的关系1.词法分析器作为语法分析器的子程序2.词法分析器作为独立的一遍3.词法分析器与语法分析器作为协同程序二、分离词法分析器的好处三、词法分析的一些难点1.3.2词法分析器的工作方式一、词法分析器与语法分析器的关71.词法分析器作为语法分析器的子程序避免了中间文件省去了取送符号的工作有利于提高编译器的效率语法分析器词法分析器调用字符串源程序字符记号符号表1.3.2词法分析器与语法分析器的关系语法树1.词法分析器作为语法分析器的子程序避免了中间文件语法词8输出放入一个中间文件磁盘文件内存文件字符串源程序字符词法分析器记号记号流源程序2.词法分析器作为独立的一遍输出放入一个中间文件字符串源程序字符词法分析器记号记号流源程93.与语法分析器并行工作词法分析程序与语法分析程序在同一遍中，以生产者和消费者的关系同步运行。3.与语法分析器并行工作词法分析程序与语101.3.3分离词法分析器的好处可以简化设计可以改进编译器的效率可以加强编译器的可移植性1.3.3分离词法分析器的好处可以简化设计111.4输入缓冲区超前搜索：为了得到某一个单词符号的确切性质，需要超前扫描若干个字符。例：>和>=

例：有合法的FORTRAN语句：

DO99K=1,10和DO99K=1.10

为了区别这两个语句，必须超前扫描到等号后的第一个分界符处。方便实现读字符和退字符操作，提高词法分析器的效率。设置缓冲区的必要性1.4输入缓冲区超前搜索：为了得到某一个单词符号的确切性121.4.1单缓冲区一般使用两个指针标识当前扫描的位置，第一个指针表示当前被识别的记号的第一个字符，另一指针表示现在正在扫描的字符开始指针

向前指针……ifx=ythenj:=j+2;eof…1.4.1单缓冲区一般使用两个指针标识当前扫描的位置，第一个131.1记号、模式与单词记号：是指某一类单词符号的种别编码，如标识符的记号为id，数的记号为num等。（机内表示）模式：是指某一类单词符号的构词规则，如标识符的模式是“由字母开头的字母数字串”。（构词规则）单词：是指某一类单词符号的一个特例，如position是标识符。（外部表示）1.1记号、模式与单词记号：是指某一类单词符号的种别编码，如14示例：词法分析的输入和输出for(i=1;i<=100;i++)sum=sum+i;for(i=1;i<=100;i++)

sum

=

sum

+

i;<保留字,for><分隔符,(><标识符,i><算符,=><常量,1><分隔符,;><标识符,i><算符,<=><常量,100><分隔符,;><标识符,i><算符,++><分隔符,)><标识符,sum><算符,=><标识符,sum><算符,+><标识符,i><分隔符,;>示例：词法分析的输入和输出for(i=1;i<=1015词法分析器的输出——记号记号的种类：关键字：for,while,if等；标识符：position,rate等；常数：60特殊符号：算符：+-*/等；分隔符：分号，空格，引号等等；词法分析器的输出——记号记号的种类：16记号的属性词法分析器在识别出一个记号后，要把与之有关的信息作为它的属性保留下来。记号影响语法分析的决策，属性影响记号的翻译。在词法分析阶段，对记号只能确定一种属性关键字：一字一种或全体一种，前一种方法较好标识符：一般统归一种，也可分为若干种常数：一般统归一种，也可按类型分种运算符：一符一种或一类一种分界符：一般用一符一种记号的属性是指记号的特征或特性，反映特征或特性的值是属性值一种一符则种别值可以认为是属性值，一种多符则需给出属性值记号的属性词法分析器在识别出一个记号后，要把与之有关的信息作17输入的基本单位：单词一个被编译的源代码，以字符串的形式输入到词法分析器中，词法分析器的处理单位是“单词”每一个单词对应于词法分析的最终输出；单词的不同的构成方式，将产生不同的记号及属性；注意“单词”还包括程序中的各种特殊符号等。输入的基本单位：单词一个被编译的源代码，以字符串的形式输入到18识别单词的规则：模式如何判定一个单词的类型，以及该单词所对应的记号的相关属性，需要通过规则进行区别，这个规则就是模式。历史上存在过一些词法模式，对词法分析造成了很大的困难；形式化描述的词法模式具有严谨、准确的特性；当前，程序设计语言的词法模式通常使用正规表达式来进行描述；识别单词的规则：模式如何判定一个单词的类型，以及该单词所对应19历史上词法分析的一些难点位置对准Fortran要求某些结构出现在输入行的固定位置空白不作为分隔符Fortran中空格是无意义的，可以随便加入DO5I=1.25（赋值语句，DO5I是标识符）DO5I=1,25（循环语句，DO是关键字）关键字不保留PL/I语言的关键字不保留IFTHENTHENTHEN=ELSE;ELSEELSE=THEN历史上词法分析的一些难点位置对准201.术语

字母表（alphabet）：字母表是符号的非空有穷集合，用∑表示字符串/符号串/串（String）：符号串是由字母表中的符号所组成的有穷序列符号串的长度符号串中包含符号的个数，串s的长度记为|s|前缀（prefix）、后缀（suffix）、子串（substring）

语言（Language）：某个字母表上的符号串的集合2.模式的形式化描述1.术语字母表（alphabet）：2.模式的形式化描述212.1串和语言符号串的运算：连接（concatenation）：符号串x、y的连接，是把y的符号写在x的符号之后得到的符号串xy如x=ab,y=cd则xy=abcd注：εα=αε=α方幂（exponentiation）：符号串自身连接n次得到的符号串αn

定义为αα…ααn个α连接α1=α,α2=αα，注：α0=ε2.1串和语言符号串的运算：如x=ab,y=222.1串和语言连接（乘积）两个符号串集合A和B的乘积定义为：

AB={xy|xA且yB}例如：集合A={ab,cde}B={0,1}

则AB={ab1,ab0,cde0,cde1}{ε}L=L{ε}=LLL…L=LnL0={ε}2.1串和语言连接（乘积）例如：集合A={ab,cde}232.1串和语言*闭包（Kleeneclosure）L*=L0∪L1∪L2∪L3∪…

+闭包（Positiveclosure）L+=L1∪L2∪L3∪…L*=L+

∪ε2.1串和语言*闭包（Kleeneclosure）+242.1串和语言语言的运算（operationsonlanguages）：语言是符号串的集合，集合的运算有并、交、差等并运算—

两个集合的并；交运算—

两个集合的交；差运算—

两个集合的差；2.1串和语言语言的运算（operationsonl252.1串和语言注:后面通常是考虑字母表∑的*闭包和+闭包例：Σ={a,b} Σ*={ε,a,b,aa,ab,ba,bb,aaa,aab,…}Σ+={a,b,aa,ab,ba,bb,aaa,aab,…}2.1串和语言注:后面通常是考虑字母表∑的*闭包和262.1串和语言综合性的例子：例3.3L={A,B,C,…,Z,a,b,c,…,z}D={0,1,…,9}把L和D两个字母表看作长度为1的符号串集合，即语言1.L∪D2.LD3.L44.L*

5.L(L∪D)*6.D+2.1串和语言综合性的例子：例3.3把L和D两个272.2文法和语言的定义如何来描述一种语言？如果语言是有穷的（只含有有穷多个句子），可以将句子逐一列出来表示如果语言是无穷的，找出语言的有穷表示。2.2文法和语言的定义如何来描述一种语言？如果语言是有穷282.2文法和语言的定义语言的有穷表示有两个途经：生成方式（文法）：语言中的每个句子可以用严格定义的规则来构造。识别方式（自动机）：用一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就会停止并回答“是”，若不属于，要么能停止并回答“不是”，（要么永远继续下去。）文法即是以生成方式描述语言的，即语言中的每个句子可以用严格定义的规则来构造.2.2文法和语言的定义语言的有穷表示有两个途经：识别方式292.2文法和语言的定义文法G定义为四元组（VT，VN，S，P）：VT

：终结符（terminals）集，其中的元素一般用小写字母或数字表示（a,b,c…0,1..），代表语言中不可再分的基本符号，如汉语中的汉字、C语言中的标识符。VN

：非终结符（nonterminals）集，其中的元素一般用大写字母表示（A,B,C…），或者用尖括号括起，代表语法单位，如汉语中的语句、段落，C语言中的语句、表达式、函数等2.2文法和语言的定义文法G定义为四元组（VT，VN302.2文法和语言的定义S是一个特殊的非终结符号，称为开始符号（startsymbol）S至少要在一条产生式中作为左部出现P是一个产生式（production）的集合产生式（重写规则、生成式）：形如α→β的（α，β）有序对，且α∈V+，β∈V*，其中V=（VT∪VN）α称为产生式的左部，不能为空εβ称为产生式的右部，可以为空ε（如：A→ε）2.2文法和语言的定义S是一个特殊的非终结符号，称为开312.2文法和语言的定义例1：文法G=（VT，VN，S，P）

VN={S}VT={0,1} P={S→0S1,S→01}可以只写出产生式，通过产生式可以得到文法的其它部分左部相同的产生式可以写在一起，如: S→0S1|012.2文法和语言的定义例1：文法G=（VT，VN，322.2文法和语言的定义例2：文法G=（VT，VN，S，P）

VN={<标识符>，<字母>，<数字>} VT={a,b,c,…x,y,z,0,1,…,9} P={ <标识符>→<字母> <标识符>→<标识符><字母> <标识符>→<标识符><数字> <字母>→a,…,<字母>→z <数字>→0,…,<数字>→9} S=<标识符>2.2文法和语言的定义例2：文法G=（VT，VN，332.2文法和语言的定义推导（derivation）与归约（reduction）：直接推导与直接归约如果A→γ是G的一条产生式，则称用αγβ代替αAβ为一步直接推导，记为αAβ=>αγβ；称用αAβ代替αγβ为一步直接归约，记为αγβ<=αAβ推导是用产生式的右部代替左部，归约是用产生式的左部代替右部，归约是推导的逆过程2.2文法和语言的定义推导（derivation）与归约342.2文法和语言的定义语言的形式定义：可以从文法G的开始符号推导得到的所有终结符号串的集合称为该文法定义的语言，记为L（G）2.2文法和语言的定义语言的形式定义：可以从文法G的开352.2文法和语言的定义例子：G1：S→A A→0A1 A→01

是由一个或多个0开头，后跟同样数目的1的符号串构成的集合（语言），可记为：L(G)={0n1n|n≥1}2.2文法和语言的定义例子：是由一个或多个0开头362022/11/172.2文法和语言的定义G2： E→id E→E+E E→E*E E→（E）产生的是表达式的集合2022/11/112.2文法和语言的定义G2： 372.2文法和语言的定义G3：list→list+digit|list-digit|digitdigit→0|1|2|3|4|5|6|7|8|9由加减号分隔的数字列表的集合2.2文法和语言的定义G3：list→list+382.2文法和语言的定义一个文法对应一个语言，但一个语言可能有若干个文法产生它，这若干个文法是等价的，称为等价文法。2.2文法和语言的定义一个文法对应一个语言，但一个语言可392.3文法和语言的分类乔姆斯基（Chomsky）在1956年提出形式语言理论，他将形式文法分为四类(0,1,2,3)，对应四类形式语言(0,1,2,3)分类的方法是对文法的产生式进行不同的限制2.3文法和语言的分类乔姆斯基（Chomsky）在195402.3文法和语言的分类0型文法—|α|≠0，即α≠ε（α→β）1型（上下文有关）文法—|α|≤|β|（α→β）2型（上下文无关）文法—A∈VN，β∈（VT∪VN）*（A→β）3型（正规）文法A→a或A→aB（右线性）A→a或A→Ba（左线性）2.3文法和语言的分类0型文法—|α|≠0，即412.3文法和语言的分类0型文法产生的语言称为0型语言1型文法或上下文有关文法（CSG）产生的语言称为1型语言或上下文有关语言（CSL）2型文法或上下文无关文法（CFL）产生的语言称为2型语言或上下文无关语言（CFL）3型文法或正则（正规）文法（RG）产生的语言称为3型语言正则（正规）语言（RL）2.3文法和语言的分类0型文法产生的语言称为0型语言1型422.3文法和语言的分类四种文法（语言）之间的逐级“包含”关系2型文法（语言）1型文法（语言）0型文法（语言）3型文法（语言）2.3文法和语言的分类四种文法（语言）之间的逐级“包含”432.3文法和语言的分类识别各类语言的数学模型（自动机）图灵机（0型语言）有界图灵机、线性有界自动机（1型语言）下推自动机（2型语言）有限自动机（3型语言）2.3文法和语言的分类识别各类语言的数学模型（自动机）图443.2单词符号的描述正规表达式（RegularExpression）正规表达式是一个表示字符串格式的模式（pattern）可以用来描述单词符号的结构正规式（r）匹配的串集称为正规集（RegularSet），这是一个正规语言，记为L（r）3.2单词符号的描述正规表达式（RegularExpr453.2单词符号的描述（字母表∑上的）正规式与正规集的递归定义1.ε→L(ε)={ε}2.a→L(a)={a}a作为字符、字符串、正规式3.r、s→L(r)、L(s)(r)|(s)→L(r)∪L(s)(r)(s)→L(r)L(s)(r)*→(L(r))*对+也成立(r)→L(r)括号只起调整优先级的作用3.2单词符号的描述（字母表∑上的）正规式与正规集的递归463.2单词符号的描述正规式的运算（|

、连接、*、+）

——

字符串集合（语言）的运算正规式运算的优先级关系（*和+、连接、|

），可以省略（和）例如（a）|（（b）*（c））——

a|b*c3.2单词符号的描述正规式的运算（|、连接、*、+）4748

正规式的等价

不同算术表达式可以表示同一个数，如3+5、5+3、2+6等均表示8。

不同正规式也可以表示同一个正规集，即正规式与正规集之间是多对一的关系。定义2.3

若正规式P和Q表示了同一个正规集，则称P和Q是等价的，记为P=Q。 48正规式的等价不同算术表达式可以表示同一个数，48例2令

L(x)={a，b}，L(y)={c，d}，

则

L(x|y)={a，b，c，d}L(y|x)={a，b，c，d}例1

设字母表∑={a,b,c}，则∑上的部分正规式和正规集如下：正规式 对应正规集a，b，c {a}，{b}，{c}

a|b,b|a {a}∪{b}={a，b}a(a|b)*

{a,aa,ab,aba,abb...}，a为首的ab字符串∑*

{ε，a，b，c，aa，abc，...}

例2令L(x)={a，b}，L(y)={c，d}，例14950

正规式的代数性质r|s=s|r (rs)t=r(st) r|(s|t)=(r|s)|tεr=rε=r r(s|t)=rs|rt r*=(r+|ε)(s|t)r=sr|tr r**=r*50正规式的代数性质r|s=s|r r(s|t)5051简化正规式描述(a)正闭包

:

r+=rr*=r*r，r*=r+|ε(b)可缺省

:r?=r|ε(c)字符组

：枚举:[abc]，它等价于a|b|c

分段:[0-9a-z](d)非字符组

：

若∑={a,b,c,d,e,f,g}，

则L([^abc])={d,e,f,g51简化正规式描述(a)正闭包:513.2单词符号的描述a|b(a|b)(a|b)a*(a|b)*a|a*b3.2单词符号的描述a|b52正规表达式举例例1、以01结尾的二进制数串

（0|1）*01正规表达式举例例1、以01结尾的二进制数串53正规表达式举例例2、能被5整除的十进制整数

digit

=[1-9]digits=digit(digit|0)*digits(5|0)|0

正规表达式举例例2、能被5整除的十进制整数54正规表达式举例例3、不包含子串011的由01组成的符号串

1*(01|0)*正规表达式举例例3、不包含子串011的由01组成的符号串55正规表达式举例例4、每个a后面至少紧随两个b的ab串

(abb|b)*正规表达式举例例4、每个a后面至少紧随两个b的ab串56正规表达式举例例5、C的形如/*…*/的注释，其中…不包含*/的字符串

/*([^*]|*[^/])**/正规表达式举例例5、C的形如/*…*/的注释，其中…不包含57正规表达式举例例6、合法的日期表示有如下三种形式，请给出描述日期的正规式。

年.月.日，如1992.08.12

日月年，如12081992

月/日/年，如08/12/1992正规表达式举例例6、合法的日期表示有如下三种形式，请给出描58第二章词法分析（1）——词法分析的若干问题与模式的形式化描述华侨大学计算机学院陈霞编译原理第二章词法分析（1）——词法分析的若干问题与模式的形式化描59内容简介0、回顾：词法分析1、词法分析中的若干问题词法分析器的作用和工作方式输入缓冲区记号、模式、单词记号的属性2、模式的形式化描述字符串与语言正规式与正规集记号的说明内容简介0、回顾：词法分析60编译原理词法分析课件610、回顾：词法分析词法分析是编译过程中将字符流转换成为符号流的一个工作阶段，是编译的第一步工作，其后续工作是语法分析。词法分析的输入是源代码；词法分析的输出是符号流；词法分析需要识别词法错误，即非法的符号、单词等等。但不识别语法错误。0、回顾：词法分析词法分析是编译过程中将字符流转换成为符号流620、回顾：词法分析的一些思考为什么不直接使用字符串进行后续工作，如语法分析？词法分析还有其他什么作用？词法分析中，把字符流转换成符号流存在着什么困难（什么样的字符串有利于/不利于词法分析的进行）？我们使用什么方法和工具来描述和解决词法分析中遇到的困难？0、回顾：词法分析的一些思考为什么不直接使用字符串进行后续工631.3词法分析器的作用源程序由单词组成，单词是最小的语义单位词法分析器的功能：扫描源程序字符流按照源语言的词法规则识别出各类单词符号产生用于语法分析的记号序列词法分析器的辅助功能跳过源程序中的注释和空白把错误信息和源程序联系起来（错误定位）宏预处理1.3词法分析器的作用源程序由单词组成，单词是最小的语义641.3.2词法分析器的工作方式一、词法分析器与语法分析器的关系1.词法分析器作为语法分析器的子程序2.词法分析器作为独立的一遍3.词法分析器与语法分析器作为协同程序二、分离词法分析器的好处三、词法分析的一些难点1.3.2词法分析器的工作方式一、词法分析器与语法分析器的关651.词法分析器作为语法分析器的子程序避免了中间文件省去了取送符号的工作有利于提高编译器的效率语法分析器词法分析器调用字符串源程序字符记号符号表1.3.2词法分析器与语法分析器的关系语法树1.词法分析器作为语法分析器的子程序避免了中间文件语法词66输出放入一个中间文件磁盘文件内存文件字符串源程序字符词法分析器记号记号流源程序2.词法分析器作为独立的一遍输出放入一个中间文件字符串源程序字符词法分析器记号记号流源程673.与语法分析器并行工作词法分析程序与语法分析程序在同一遍中，以生产者和消费者的关系同步运行。3.与语法分析器并行工作词法分析程序与语681.3.3分离词法分析器的好处可以简化设计可以改进编译器的效率可以加强编译器的可移植性1.3.3分离词法分析器的好处可以简化设计691.4输入缓冲区超前搜索：为了得到某一个单词符号的确切性质，需要超前扫描若干个字符。例：>和>=

例：有合法的FORTRAN语句：

DO99K=1,10和DO99K=1.10

为了区别这两个语句，必须超前扫描到等号后的第一个分界符处。方便实现读字符和退字符操作，提高词法分析器的效率。设置缓冲区的必要性1.4输入缓冲区超前搜索：为了得到某一个单词符号的确切性701.4.1单缓冲区一般使用两个指针标识当前扫描的位置，第一个指针表示当前被识别的记号的第一个字符，另一指针表示现在正在扫描的字符开始指针

向前指针……ifx=ythenj:=j+2;eof…1.4.1单缓冲区一般使用两个指针标识当前扫描的位置，第一个711.1记号、模式与单词记号：是指某一类单词符号的种别编码，如标识符的记号为id，数的记号为num等。（机内表示）模式：是指某一类单词符号的构词规则，如标识符的模式是“由字母开头的字母数字串”。（构词规则）单词：是指某一类单词符号的一个特例，如position是标识符。（外部表示）1.1记号、模式与单词记号：是指某一类单词符号的种别编码，如72示例：词法分析的输入和输出for(i=1;i<=100;i++)sum=sum+i;for(i=1;i<=100;i++)

sum

=

sum

+

i;<保留字,for><分隔符,(><标识符,i><算符,=><常量,1><分隔符,;><标识符,i><算符,<=><常量,100><分隔符,;><标识符,i><算符,++><分隔符,)><标识符,sum><算符,=><标识符,sum><算符,+><标识符,i><分隔符,;>示例：词法分析的输入和输出for(i=1;i<=1073词法分析器的输出——记号记号的种类：关键字：for,while,if等；标识符：position,rate等；常数：60特殊符号：算符：+-*/等；分隔符：分号，空格，引号等等；词法分析器的输出——记号记号的种类：74记号的属性词法分析器在识别出一个记号后，要把与之有关的信息作为它的属性保留下来。记号影响语法分析的决策，属性影响记号的翻译。在词法分析阶段，对记号只能确定一种属性关键字：一字一种或全体一种，前一种方法较好标识符：一般统归一种，也可分为若干种常数：一般统归一种，也可按类型分种运算符：一符一种或一类一种分界符：一般用一符一种记号的属性是指记号的特征或特性，反映特征或特性的值是属性值一种一符则种别值可以认为是属性值，一种多符则需给出属性值记号的属性词法分析器在识别出一个记号后，要把与之有关的信息作75输入的基本单位：单词一个被编译的源代码，以字符串的形式输入到词法分析器中，词法分析器的处理单位是“单词”每一个单词对应于词法分析的最终输出；单词的不同的构成方式，将产生不同的记号及属性；注意“单词”还包括程序中的各种特殊符号等。输入的基本单位：单词一个被编译的源代码，以字符串的形式输入到76识别单词的规则：模式如何判定一个单词的类型，以及该单词所对应的记号的相关属性，需要通过规则进行区别，这个规则就是模式。历史上存在过一些词法模式，对词法分析造成了很大的困难；形式化描述的词法模式具有严谨、准确的特性；当前，程序设计语言的词法模式通常使用正规表达式来进行描述；识别单词的规则：模式如何判定一个单词的类型，以及该单词所对应77历史上词法分析的一些难点位置对准Fortran要求某些结构出现在输入行的固定位置空白不作为分隔符Fortran中空格是无意义的，可以随便加入DO5I=1.25（赋值语句，DO5I是标识符）DO5I=1,25（循环语句，DO是关键字）关键字不保留PL/I语言的关键字不保留IFTHENTHENTHEN=ELSE;ELSEELSE=THEN历史上词法分析的一些难点位置对准781.术语

字母表（alphabet）：字母表是符号的非空有穷集合，用∑表示字符串/符号串/串（String）：符号串是由字母表中的符号所组成的有穷序列符号串的长度符号串中包含符号的个数，串s的长度记为|s|前缀（prefix）、后缀（suffix）、子串（substring）

语言（Language）：某个字母表上的符号串的集合2.模式的形式化描述1.术语字母表（alphabet）：2.模式的形式化描述792.1串和语言符号串的运算：连接（concatenation）：符号串x、y的连接，是把y的符号写在x的符号之后得到的符号串xy如x=ab,y=cd则xy=abcd注：εα=αε=α方幂（exponentiation）：符号串自身连接n次得到的符号串αn

定义为αα…ααn个α连接α1=α,α2=αα，注：α0=ε2.1串和语言符号串的运算：如x=ab,y=802.1串和语言连接（乘积）两个符号串集合A和B的乘积定义为：

AB={xy|xA且yB}例如：集合A={ab,cde}B={0,1}

则AB={ab1,ab0,cde0,cde1}{ε}L=L{ε}=LLL…L=LnL0={ε}2.1串和语言连接（乘积）例如：集合A={ab,cde}812.1串和语言*闭包（Kleeneclosure）L*=L0∪L1∪L2∪L3∪…

+闭包（Positiveclosure）L+=L1∪L2∪L3∪…L*=L+

∪ε2.1串和语言*闭包（Kleeneclosure）+822.1串和语言语言的运算（operationsonlanguages）：语言是符号串的集合，集合的运算有并、交、差等并运算—

两个集合的并；交运算—

两个集合的交；差运算—

两个集合的差；2.1串和语言语言的运算（operationsonl832.1串和语言注:后面通常是考虑字母表∑的*闭包和+闭包例：Σ={a,b} Σ*={ε,a,b,aa,ab,ba,bb,aaa,aab,…}Σ+={a,b,aa,ab,ba,bb,aaa,aab,…}2.1串和语言注:后面通常是考虑字母表∑的*闭包和842.1串和语言综合性的例子：例3.3L={A,B,C,…,Z,a,b,c,…,z}D={0,1,…,9}把L和D两个字母表看作长度为1的符号串集合，即语言1.L∪D2.LD3.L44.L*

5.L(L∪D)*6.D+2.1串和语言综合性的例子：例3.3把L和D两个852.2文法和语言的定义如何来描述一种语言？如果语言是有穷的（只含有有穷多个句子），可以将句子逐一列出来表示如果语言是无穷的，找出语言的有穷表示。2.2文法和语言的定义如何来描述一种语言？如果语言是有穷862.2文法和语言的定义语言的有穷表示有两个途经：生成方式（文法）：语言中的每个句子可以用严格定义的规则来构造。识别方式（自动机）：用一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就会停止并回答“是”，若不属于，要么能停止并回答“不是”，（要么永远继续下去。）文法即是以生成方式描述语言的，即语言中的每个句子可以用严格定义的规则来构造.2.2文法和语言的定义语言的有穷表示有两个途经：识别方式872.2文法和语言的定义文法G定义为四元组（VT，VN，S，P）：VT

：终结符（terminals）集，其中的元素一般用小写字母或数字表示（a,b,c…0,1..），代表语言中不可再分的基本符号，如汉语中的汉字、C语言中的标识符。VN

：非终结符（nonterminals）集，其中的元素一般用大写字母表示（A,B,C…），或者用尖括号括起，代表语法单位，如汉语中的语句、段落，C语言中的语句、表达式、函数等2.2文法和语言的定义文法G定义为四元组（VT，VN882.2文法和语言的定义S是一个特殊的非终结符号，称为开始符号（startsymbol）S至少要在一条产生式中作为左部出现P是一个产生式（production）的集合产生式（重写规则、生成式）：形如α→β的（α，β）有序对，且α∈V+，β∈V*，其中V=（VT∪VN）α称为产生式的左部，不能为空εβ称为产生式的右部，可以为空ε（如：A→ε）2.2文法和语言的定义S是一个特殊的非终结符号，称为开892.2文法和语言的定义例1：文法G=（VT，VN，S，P）

VN={S}VT={0,1} P={S→0S1,S→01}可以只写出产生式，通过产生式可以得到文法的其它部分左部相同的产生式可以写在一起，如: S→0S1|012.2文法和语言的定义例1：文法G=（VT，VN，902.2文法和语言的定义例2：文法G=（VT，VN，S，P）

VN={<标识符>，<字母>，<数字>} VT={a,b,c,…x,y,z,0,1,…,9} P={ <标识符>→<字母> <标识符>→<标识符><字母> <标识符>→<标识符><数字> <字母>→a,…,<字母>→z <数字>→0,…,<数字>→9} S=<标识符>2.2文法和语言的定义例2：文法G=（VT，VN，912.2文法和语言的定义推导（derivation）与归约（reduction）：直接推导与直接归约如果A→γ是G的一条产生式，则称用αγβ代替αAβ为一步直接推导，记为αAβ=>αγβ；称用αAβ代替αγβ为一步直接归约，记为αγβ<=αAβ推导是用产生式的右部代替左部，归约是用产生式的左部代替右部，归约是推导的逆过程2.2文法和语言的定义推导（derivation）与归约922.2文法和语言的定义语言的形式定义：可以从文法G的开始符号推导得到的所有终结符号串的集合称为该文法定义的语言，记为L（G）2.2文法和语言的定义语言的形式定义：可以从文法G的开932.2文法和语言的定义例子：G1：S→A A→0A1 A→01

是由一个或多个0开头，后跟同样数目的1的符号串构成的集合（语言），可记为：L(G)={0n1n|n≥1}2.2文法和语言的定义例子：是由一个或多个0开头942022/11/172.2文法和语言的定义G2： E→id E→E+E E→E*E E→（E）产生的是表达式的集合2022/11/112.2文法和语言的定义G2： 952.2文法和语言的定义G3：list→list+digit|list-digit|digitdigit→0|1|2|3|4|5|6|7|8|9由加减号分隔的数字列表的集合2.2文法和语言的定义G3：list→list+962.2文法和语言的定义一个文法对应一个语言，但一个语言可能有若干个文法产生它，这若干个文法是等价的，称为等价文法。2.2文法和语言的定义一个文法对应一个语言，但一个语言可972.3文法和语言的分类乔姆斯基（Chomsky）在1956年提出形式语言理论，他将形式文法分为四类(0,1,2,3)，对应四类形式语言(0,1,2,3)分类的方法是对文法的产生式进行不同的限制2.3文法和语言的分类乔姆斯基（Chomsky）在195982.3文法和语言的分类0型文法—|α|≠0，即α≠ε（α→β）1型（上下文有关）文法—|α|≤|β|（α→β）2型（上下文无关）文法—A∈VN，β∈（VT∪VN）*（A→β）3型（正规）文法A→a或A→aB（右线性）A→a或A→Ba（左线性）2.3文法和语言的分类0型文法—|α|≠0，即992.3文法和语言的分类0型文法产生的语言称为0型语言1型文法或上下文有关文法（CSG）产生的语言称为1型语言或上下文有关语言（CSL）2型文法或上下文无关文法（CFL）产生的语言称为2型语言或上下文无关语言（CFL）3型文法或正则（正规）文法（RG）产生的语言称为3型语言正则（正规）语言（RL）2.3文法和语言的分类0型文法产生的语言称为0型语言1型1002.3文法和语言的分类四种文法（语言）之间的逐级“包含”关系2型文法（语言）1型文法（语言）0型文法（语言）3型文法（语言）2.3文法和语言的分类四种文法（语言）之间的逐级“包含”1012.3文法和语言的分类识别各类语言的数学模型（自动机）图灵机（0型语言）有界图灵机、线性有界自动机（1型语言）下推自动机（2型语言）有限自动机（3型语言）2.3文法和语言的分类识别各类语言的数学模型（自动机）图1023.2单词符号的描述正规表达式（RegularExpression）正规表达式是一个表示字符串格式的模式（pattern）可以用来描述单词符号的结构正规式（r）匹配的串集称为正规集（RegularSet），这是一个正规语言，记为L（r）3.2单词符号的描述正规表达式（RegularExpr1033.2单词符号的描述（字母表∑上的）正规式与正规集的递归定义1.ε→L(ε)={ε}2.a→L(a)={a}a作为字符、字符串、正规式3.r、s→