词法分析与有穷自动机

《词法分析与有穷自动机》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、有穷自动机是构造词法分析程序的理论基础。本章主要介绍词法分析程序的设计原理和构造方法，重点介绍有穷自动机的基本概念以及正规文法、正规表达式与有穷自动机之间的相互关系。第三章词法分析与有穷自动机第三章词法分析与有穷自动机◇词法分析程序功能◇词法分析程序的编写方法◇正规文法与有穷自动机◇正规式与有穷自动机◇语言单词符号的两种定义方式◇单词符号及输出单词的形式词法分析的任务是对字符串表示的源程序从左到右地进行扫描和分解，根据语言的词法规则识别出一个一个具有独立意义的单词符号。字符串表示的源程序词法分析器字符单词符号取下一个单词符号语法分析器3.1词法分析程序的功

2、能3.2单词符号及输出单词的形式关键字也称基本字，例如，C语言中的if，else，while,do等,这些字在语言中具有固定的意义，一般不作为标识符使用。标识符表示各种名字，如变量名、常量名、数组名和函数名等。语言的单词符号是指语言中具有独立意义的最小语法单位。3.2单词符号及输出单词的形式常数各种类型的常数，如整型常数125、实型常数0.718、布尔型常数TRUE等。运算符如＋、－、*、/、＜等。分界符如，、；、（、）、：等。3.2单词符号及输出单词的形式词法分析程序所输出的单词符号通常表示成如下的二元式：（单词种别，单词自身的值）3.2单词符号及输出单

3、词的形式单词种别单词种别表示单词的种类，它是语法分析需要的信息。为处理方便通常让每种单词对应一个整数码。3.2单词符号及输出单词的形式常数:可统归为一种，也可按类型（整型、实型、布尔型等）划分。关键字:可将其全体视为一种，也可以一字一种。标识符:一般统归为一种。运算符和界符:可采用一符一种类的分法，也可以统归为一种。3.2单词符号及输出单词的形式单词自身的值一个种别只含一个单词符号一个种别含有多个单词符号(1)对于标识符其自身值是标识符自身的字符串；(2)常数自身值是常数本身的二进制数值。3.2单词符号及输出单词的形式(3)用指向某类表格一个特定项目指针值

4、来区分同类中不同的单词。例如,对于标识符用它在符号表的入口指针作为它自身值;常数用它在常数表的入口指针作为它自身的值。3.2单词符号及输出单词的形式常数自身的值用常数本身的值表示；例如:if(a＞1)b=100；假定:关键字、运算符和界符都是一符一种；标识符自身的值用自身的字符串表示；3.2单词符号及输出单词的形式假设:标识符的种别编码为整数10；常数的种别编码为整数11；基本字if种别编码为2；赋值号的种别编码为17；大于号的种别编码为23；分号的种别编码为26；左括号的种别编码为29；右括号的种别编码为30；则程序段：3.2单词符号及输出单词的形式if

5、(a＞1)b=100；在经词法分析程序扫描后，它所输出的单词符号串是：（2，）基本字if（29，）左括号(（10，‘a’）标识符a（23，）大于号＞（11，1）常数1（30，）右括号)（10，‘b’）标识符b（17，）赋值号=（11，100）常数100（26,）分号；3.3单词符号的两种定义方式正规式以标识符为例:I→l

6、Il

7、Id或I→l

8、lTT→l

9、d

10、lT

11、dT以标识符为例:l(l

12、d)*正规文法设有字母表Σ={a1,a2,…,an}，在字母表Σ上的正规式和它所表示的正规集可用如下规则来定义：1.Φ是Σ上的正规式，它所表示的正规集是Φ，即空集{}。2

13、.ε是Σ上的正规式，它所表示的正规集仅含一空符号串，即{ε}。3.ai是∑上的一个正规式，它所表示的正规集是由单个符号ai所组成，即{ai}。3.3.1正规式和正规集4.如果e1和e2是∑上的正规式，它们所表示的正规集分别为L(e1)和L(e2)，则：(1)e1

14、e2是∑上的一个正规式，它所表示的正规集为L(e1

15、e2)=L(e1)∪L(e2)(2)e1e2也是∑上的一个正规式，它所表示的正规集为L(e1e2)=L(e1)L(e2)(3)(e1)*也是∑上的一个正规式，它所表示的正规集为L((e1)*)=(L(e1))*3.3.1正规式和正规集3.3.1正

16、规式和正规集正规式中包含三种运算符：连接“·”，或“

17、”和闭包“*”。其中闭包运算的优先级最高，连接运算次之，或运算最低。连结符“·”一般可省略不写。这三种运算符均是左结合的。3.3.1正规式和正规集例1设有字母表Σ={a,b}，根据正规式与正规集的定义，则有：a和b是正规式，相应正规集为2.a

18、b是正规式，相应正规集为3.ab是正规式，相应正规集为L(a)={a},L(b)={b}L(a

19、b)=L(a)∪L(b)={a,b}L(ab)=L(a)L(b)={a}{b}={ab}3.3.1正规式和正规集4.(a

20、b)*是正规式，相应正规集为例如，{a,b}*

21、的子集{anbn

22、n≥1}就不是一个正规集，不能用正规式来描述，也