资源描述：
《编译原理 第03章 词法分析与有穷自动机.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第三章词法分析与有穷自动机◇词法分析程序功能◇词法分析程序的编写方法◇正规文法与有穷自动机◇正规式与有穷自动机◇语言单词符号的两种定义方式◇单词符号及输出单词的形式回顾：词法分析的任务字符串表示的源程序词法分析器字符单词符号取下一个单词符号语法分析器3.1词法分析程序的功能3.2单词符号及输出单词的形式关键字也称基本字，例如，C语言中的if，else，while,do等。标识符表示各种名字，如变量名、常量名、数组名和函数名等。语言的单词符号是指语言中具有独立意义的最小语法单位。3.2单词符号及输出单词的形式常数整型常数125、实型常数0
2、.718、布尔型常数TRUE等。运算符如＋、－、*、/、＜等。分界符如，、；、（、）、：等。3.2单词符号及输出单词的形式词法分析程序所输出的单词符号通常表示成如下的二元式：（单词种别，单词自身的值）单词种别：单词的种类3.2单词符号及输出单词的形式常数:可统归为一种，也可按类型（整型、实型、布尔型等）划分。关键字:可全体视为一种，也可一字一种。标识符:一般统归为一种。运算符和界符:可一符一种类，也可统归为一种。3.2单词符号及输出单词的形式单词自身的值一个种别只含一个单词符号一个种别含有多个单词符号(1)对于标识符其自身值是标识符自身
3、的字符串；(2)常数自身值是常数本身的二进制数值。3.2单词符号及输出单词的形式(3)用指向某类表格一个特定项目指针值来区分同类中不同的单词。例如,对于标识符用它在符号表的入口指针作为它自身值;常数用它在常数表的入口指针作为它自身的值。3.2单词符号及输出单词的形式常数自身的值用常数本身的值表示；例如:if(a＞1)b=100；假定:关键字、运算符和界符都是一符一种；标识符自身的值用自身的字符串表示；3.2单词符号及输出单词的形式假设:标识符的种别编码为整数10；常数的种别编码为整数11；基本字if种别编码为2；赋值号的种别编码为17；
4、大于号的种别编码为23；分号的种别编码为26；左括号的种别编码为29；右括号的种别编码为30；则程序段：3.2单词符号及输出单词的形式if(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
5、Il
6、Id或I→l
7、lTT→l
8、d
9、lT
10、dT以标识符为例:l(l
11、d)*正规文法设有字母表Σ
12、={a1,a2,…,an}，在字母表Σ上的正规式和它所表示的正规集(正规式描述的语言)用如下规则定义：1.Φ是Σ上的正规式，它所表示的正规集是Φ，即空集{}。2.ε是Σ上的正规式，它所表示的正规集仅含一空符号串，即{ε}。3.ai是∑上的一个正规式，它所表示的正规集是由单个符号ai所组成，即{ai}。3.3.1正规式和正规集4.如果e1和e2是∑上的正规式，它们所表示的正规集分别为L(e1)和L(e2)，则：(1)e1
13、e2是∑上的一个正规式，它所表示的正规集为L(e1
14、e2)=L(e1)∪L(e2)(2)e1.e2也是∑上的一个正规式
15、，它所表示的正规集为L(e1.e2)=L(e1)L(e2)(3)(e1)*也是∑上的一个正规式，它所表示的正规集为L((e1)*)=(L(e1))*3.3.1正规式和正规集3.3.1正规式和正规集运算符的优先级：闭包“*”>连接“·”>或“
16、”。连结符“·”一般可省略不写。运算符均是左结合的。3.3.1正规式和正规集例1设有字母表Σ={a,b}，有：a和b是正规式，相应正规集为2.a
17、b是正规式，相应正规集为3.ab是正规式，相应正规集为L(a)={a},L(b)={b}L(a
18、b)=L(a)∪L(b)={a,b}L(ab)=L(a)L
19、(b)={a}{b}={ab}3.3.1正规式和正规集4.(a
20、b)*是正规式，相应正规集为需要指出的是，{a,b}*的任一子集不一定是正规集。如：{a,b}*的子集{anbn
21、n≥1}L((a
22、b)*)=(L(a
23、b))*={a,b}*={ε,a,b,aa,ab,ba,bb,…}5.ba*是正规式，相应的正规集为L(ba*)=L(b)L(a*)={b,ba,baa,baaa,…}(a
24、b)*(aa
25、bb)(a
26、b)*是正规式，相应正规集为即Σ上所有含两个相继a或两个相继b组成的串。L((a
27、b)*(aa
28、bb)(a
29、b)*)=L((a
30、
31、b)*)L(aa
32、bb)L((a
33、b)*)＝{a,b}*{aa,bb}{a,b}*3.3.1正规式和正规集3.3.1正规式和正规集例2设Σ={a,b,c},则aa*bb*cc*是∑上的一个正规式,它所表示
