编译原理—清华大学—第2版—第4章词法详解.ppt

第四章 词法分析;（1）分析和识别单词及属性， 包括识别语言的关键字、标识符、常数、运算符等； （2）跳过各种分隔符，如空格，回车，制表符等； （3）删除注释； （4）进行词法检查，报告所发现的错误； （5）建立符号表。;实现方案：基本上有两种;单词符号;词法分析程序的输出形式-----二元式;表3.1 int x=10,y=20,sum;词法分析的结果 ;4.2 单词的描述工具;几类单词正规文法的描述;二、正规式;例:令?={a，b}， ?上的正规式和相应的正规集的例子有： 正规式 正规集 a {a} a?b {a,b} ab {ab} (a?b)(a?b) {aa,ab,ba,bb} a ? {? ,a,aa, ……任意个a的串} (a?b)? {? ,a,b,aa,ab ……所有由a 和b组成的串} (a?b)?(aa?bb)(a?b)? {??上所有含有两个相继 的a或两个相继的b组成 的串} ;例 ?={l，d}，r=l(l?d)?定义的正规集: {l,ll,ld,ldd,……}（标识符） 其中：l代表字母,d代表数字,正规式即是 字母(字母|数字)? 它表示的正规集是“字母打头的字母数字串”。 例4.3 ?={d，.，e，+，-},则?上的正规式 ： d?(.dd??? )(e(+?-??)dd???) 表示的是无符号数的集合。其中：d为0-9的数字。;（二）两个正规式等价;（三）正规式的运算律;三、正规文法到正规式;例 r = a(a?d)? VT={a,d} S?a(a?d)? S?aA A?(a?d)? A?(a?d)B A?? B?(a?d)B B?? ;2. 将正规文法转换成正规式 使用如下规则，最后只剩下一个开始符号定义的产生式，并且右部不含非终结符。 规则1 ：A-xB,B-y = A=xy 规则2： A-xA|y = A=x*y 规则3： A-x, A-y = A=x|y ;例如：文法G[S]为： S-aA, S-a, A-aA, A-dA, A-a, A-d;4.3 有穷自动机;一、确定的有穷自动机（DFA） 1、定义: 一个确定的有穷自动机（DFA）M是一个五元组：M=（K，Σ，f，S，Z）其中 1.K是一个有穷集，它的每个元素称为一个状态； 2.Σ是一个有穷字母表，它的每个元素称为一个输入符号，所以也称Σ为输入符号字母表； 3.f是转换函数，是K×Σ→K上的映射，f(ki,a)=kj，(ki，kj∈K)表示：当前状态为ki，输入符为a时，将转换为下一个状态kj，把kj称作ki的一个后继状态； 4.S∈K是唯一的一个初态； 5.Z?K是一个终态集，终态也称可接受状态或结束状态。;例：;（1）DFA 的状态图表示;（2）DFA 的矩阵表示; α=aβ，a∈∑，β∈∑*，则有： f（Q，aβ）=f（f（Q，a），β），其中Q∈K。 ;例：证明α=baab被如下的DFA所接受。;DFA M所能识别的符号串的全体记为L(M) 结论： ?上一个字符串集V???是正规的，当且仅当存在一个?上的确定有穷自动机M，使得V=L(M)。;DFA M=（K，Σ，f，S，Z）的算法: R:=S； c:=getchar; while ceof and R∈K do {R:=f(R,c); c:=getchar; }; if R is in Z then return (‘yes’) else return (‘no’);二、不确定的有穷自动机NFA;例;表格表示;状态集合I的有关运算：;I={1}, ?-closure(I)={1,2}； I={5}, ?-closure(I)={5,6,2}； ?-closure({5,3,4})={5,3,4,6,2,8,7}； move({1,2},a)={5,4,3}; ?-closure(move({1,2},a)= ?-closure({5,3,4}) = {5,4,3,6,2,8,7}；;NFA→DFA的过程(子集法): 假设NFA N=(K,∑,f,K0,Kt)按如下办法构造一个DFA M,使得L(M)=L(N). 不失一般性，设∑={a,b}，我们构造一张表:;首先，置第1行第1列为?-closure(K0)求出这一列的