编译原理 第二章词法分析

《编译原理 第二章词法分析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章词法分析词法分析器的作用读源程序，产生单词符号（主要任务）滤掉源程序中的无用成分，如空格、注释、换行符处理输入识别记号，交给语法分析器调用符号表管理器或出错处理器，进行处理字符串与集合表示、术语意义

2、S

3、字符串S的长度，即S中字符的个数ε空串，即长度为0的字符串S1S2字符串S1和S2的连接Sn字符串S的n次方，表示S自身连接n次例：x=ST，y=abu，则它们的连接xy=STabu，看出｜x｜=2，｜y｜=3，｜xy｜=5例：若x=AB则:x0=εx1=ABx2=ABABx3=ABABABxn

4、=xxn-1=xn-1x(n>0)表示、术语意义Ф空集合，即元素个数为0的集合{ε}空串作为唯一元素的集合X=L∪MX是集合L和M的并：X={s

5、s∈Lors∈M}X=L∩MX是集合L和M的交：X={s

6、s∈Lands∈M}X=LMX是集合L和M的连接：X={st

7、s∈Landt∈M}X=L*X是集合L的闭包：X=L0∪L1∪L2∪…X=L+X是集合L的正闭包：X=L1∪L2∪L3∪…∑＋＝∑*－{ε}＝∑1∑*＝∑1∪∑2∪∑3∪…例：Σ={a,b}Σ*={ε,a,b,aa,ab,ba,bb,aaa

8、,aab,…}Σ+={a,b,aa,ab,ba,bb,aaa,aab,…}正规式与正规集给定字母表为∑ε和Ф都是∑上的正规式，它们所表示的正规集分别为L(ε)={ε}和L{Ф}={}；任何a，a是上的一个正规式，它所表示的正规集为L(a)={a}；假定r和s都是上的正规式，它们所表示的正规集分别为L(r)和L(s)，那么，(r),r

9、s,r·s,r也都是正规式,它们所表示的正规集分别为L(r),L(r)∪L(s),L(r)L(s)和(L(r))仅由有限次使用上述三步骤而定义的表达式才是上

10、的正规式，仅由这些正规式所表示的集合才是上的正规集令∑={a，b}，∑上的正规式和相应的正规集的例子有：正规式正规集a{a}a

11、b{a,b}ab{ab}(a

12、b)(a

13、b){aa,ab,ba,bb}a*{ε,a,aa,……任意个a的串}(a

14、b)*{ε,a,b,aa,ab……所有由a和b组成的串}(a

15、b)*(aa

16、bb)(a

17、b)*{∑*上所有含有两个相连的a或两个相连的b组成的串}例：令={l，d}，则上的正规式r=l(l

18、d)定义的正规集为：{l,ll,ld,ldd,……},其中l代表字

19、母,d代表数字,正规式即是：字母(字母

20、数字),它表示的正规集中的每个元素的模式是“字母打头的字母数字串”,就是C和多数程序设计语言允许的的标识符的词法规则.定义：若正规式P和Q表示了同一个正规集，则称P和Q是等价的，记为P=Q例如：P=(a

21、b),Q=b

22、aP=b(ab),Q=(ba)bP=(a

23、b),Q=(a

24、b)设r,s,t为正规式，正规式服从的代数规律有:r

25、s=s

26、r“或”的交换律r

27、(s

28、t)=(r

29、s)

30、t“或”的可结合律(rs)t=r(st)“连接”的可结合律r(s

31、t)

32、=rs

33、rt(s

34、t)r=sr

35、tr分配律r=r,r=r是“连接”的恒等元素同一律r

36、r=rr=(r+

37、)=

38、r

39、rr

40、…“或”的抽取律r=r有限自动机有限自动机(也称有穷自动机)作为一种识别装置，它能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合，引入有限自动机这个理论，正是为词法分析程序的自动构造寻找特殊的方法和工具。有限自动机分为两类：确定的有限自动机(DFA)不确定的有限自动机(NFA)确定的有限自动机定义：DFA是一个五元组M=(S,,move,s0,F

41、)其中：①S是有限个状态的集合；②是有限个输入字符的集合；③move是状态转移函数，move(si,ch)=sj表示状态si下若遇到输入字符ch则转移到状态sj；且对每个状态s和每个字符ch，最多有一个下一状态；④s0是唯一的初态；⑤F是终态集，它是S的子集，包含了所有终态。例：DFAM=（{S，U，V，Q}，{a，b}，f，S，{Q}）其中f定义为：f（S，a）=Uf（V，a）=Uf（S，b）=Vf（V，b）=Qf（U，a）=Qf（Q，a）=Qf（U，b）=Vf（Q，b）=Q则状态图表示bSUVQ

42、aaaba，bb矩阵表示字符状态不确定的有限自动机定义：NFA是一个五元组M=(S,,move,Q,F)其中：①S是有限个状态的集合；②是有限个输入字符（包括）的集合；③move是状态转移函数，move(si,ch)=sj表示状态si下若遇到输入字符ch则转移到状态sj；④Q是非空初态集；⑤F是终态集，它是S的子集，包含了所有终态。例：NFAM=（{S，P，Z}，{0，1}，f，{S，P}，{Z}）其中f（S，0）={P}f（Z，0）={P}f（P