ch2 词法分析.ppt

《ch2 词法分析.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第2章词法分析数计学院张晓红2021/9/181词法分析第一阶段：保证构词的正确输入：字符流输出：单词流分析的依据：词法规则（如：标识符被定义为字母开头的字母数字串）主要任务：分离并输出单词（保证单词符合词法规则）；输出单词的值和种类。构造符号表、常量表；发现并报告词法错误。概述构造编译程序,必须了解源语言的词法规则、语法规则、语义规则。正则表达式（2.1）是一种描述词法规则的有效工具。有穷自动机（2.2）是一种识别正则表达式所描述单词的有效工具。单词识别的过程(1）把单词的结构用正规式表达式描述；(2）把正规式转换为一个不确定的有穷自动机NFA；(3）把NFA转换为相应的确定的有穷自动机D

2、FA；(4）基于DFA构造词法分析程序。本章内容正则表达式FA概述DFA定义NFA定义NFA的确定化（NFA到DFA的转换）DFA的最小化正则表达式与NFA的转换DFA在计算机中的表示模拟DFA模拟NFA词法分析的实现正规文法某种程序设计语言中的所有单词构成一种语言。正规表达式是描述词法分析所要识别的单词的结构和好、集合一种工具。有关概念字母表/符号集：是符号的有穷非空集合。汉语符号表包括：汉字、数字、标点符号等Ｃ语言符号表包括：字母、数字、若干专用符号以及main、if等保留字。符号：符号表中的元素。符号串：符号表的符号组成的任何有穷序列。例：∑={0，1}—符号集符号串有：0，1，00，

3、01，10，11例：∑={a，b，c}—符号集符号串有：a，b，c，ab，aaca有关概念符号串的长度：符号串x有m个符号，则长度就为m，表示

4、x

5、=m。如：ababa则长度是5空符号串：不含任何符号的符号串，用ε表示

6、ε

7、=0。符号串的运算(1)符号串的头（前缀）和尾（后缀）设z=xy，则x是z的头，y是z的尾。例：设z=abc则z的头是：ε，a，ab，abc则z的尾是：ε，c，bc，abc(2)符号串的固有头和固有尾设z=xy符号串，若x非空，则y是固有尾；若y非空，则x是固有头。例：设z=abc则z的固有头是：ε，a，ab则z的固有尾是：ε，c，bc符号串的运算(3)符号串的连接（并置

8、）设x,y是符号串,连接xy是y符号写在x符号之后。例：x=ab,y=MN则xy=abMN显然：εx=xε=x(4)符号串的方幂设x是符号串，则z=xx…xx，称z为x的方幂,记z=xn。因此,x0=ε,x1=x,x2=xx,x3=xxx显然,n>0时,有xn=xxn-1＝xn-1x符号串的运算(5)符号串的集合若集合A中的一切元素都是某符号集上的符号串，则称A为该符号集上的符号串集合。(6)符号串集合的乘积（笛卡尔积）A▪B=AB={xy

9、x∈A且y∈b}例：A={a,b}，B={c,d}则AB={ac，ad，bc，bd}(7)符号串集合的方幂同一符号串集合的乘积。A0={ε},A1=A,

10、A2=AA,A3=A2A……符号串的运算(8)闭包（∑*）符号表∑，用∑*表示∑上所有有穷长的串集合，∑*称为∑的闭包。∑*=∑0∪∑1∪∑2∪.…∪∑n例：符号表∑={0,1}则∑*={ε,0,1,00,01,10,11,000,001,010……}符号串的运算(9)正闭包(∑+)∑+=∑1∪∑2∪.…∪∑n∑+称∑的正闭包。用∑+表示∑上所有非空有穷长的串集合。显然：∑*＝∑0∪∑+∑+＝∑∑*＝∑*∑例：符号表∑={0,1}则∑*={0,1,00,01,10,11,000,001,010……}正规表达式正规式正规集和{}和a（aΣ）{a}e1和e2(e1)e1

11、e2e1·e2

12、e1*L(e1)和L(e2)L(e1)L(e1)∪L(e2)L(e1)L(e2)(L(e1))*正规式与正规集的定义：设字母表为Σ，辅助字母表Σ‘={、、

13、、·、*、（、）}正规表达式{}a{a}b{b}-----------(a){a}一个正规式可以表示若干个符号串,(b){b}其正规集就是这些符号串的集合a

14、b{a,b}ab{ab}a*{,a,aa,aaa,aaaa,….}b*{,b,bb,bbb,bbbb,….}-------------------(a

15、b)*a和b组成的所有串a*

16、b*{,a,aa,aaa,aaaa,….,b,bb,bbb,bbbb,….}aba*

17、以ab开头后接若干个(包括0个)a组成的串(a

18、b)*(aa

19、bb)(a

20、b)**上所有含有两个相继的a或两个相继的b的a和b组成的串。正规表达式例：令＝｛d、、e、＋、－｝，则上的正规式d*(.dd*

21、)(e(+

22、-

23、)dd*

24、)表示的是所有无符号数。其中：d为0～9中的数字。比如：2,12.59,3.6e2,471.88e-1等都是正规式表示集合中的元素。正规表达式设A，B，C为正规式，正规