编译原理 教学课件 作者 康慕宁 林奕 讲稿_2.ppt

《编译原理 教学课件 作者 康慕宁 林奕 讲稿_2.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第2章扫描器与正规语言编译程序的前端工作是读取并解析源程序文件。这一工作是由词法分析程序（称为扫描器Scanner）完成的。我们将用语法来定义编译程序的扫描器。由扫描器语法定义的语言是扩展字母表上的字符串的集合，该字母表可构造被定义语言所有标记（Tokens，也称为单词）。例如，所有的标识符是一个标记，因此，它是扫描器语言中的一个句子。扫描器工作时，从输入流上读取一个标记后就返回到扫描器的调用点。一般来说，扫描器语言是十分简单的，它可由正规文法来定义其所有的句子。相应地，我们可以用一个有限状态自动机（FSA：Finit-

2、StateAutomaton，也简称为有限自动机FA：FinitAutomaton）来实现扫描器。本章中，我们将介绍从正规式自动构造有限状态自动机(FSA)，以及从FSA的形式描述构造扫描程序的方法。我们还将介绍如何在文法中附加便于编译程序识别出单词的语义动作，并介绍这些动作在扫描器中是如何工作的。2.1正规表达式（RegularExpression）我们可以定义整型常数是“由最少一个数字，后跟零个或多个数字组成的符号串”。在形式描述时，我们用“d”表示数字，用“*”表示零个或多个连接运算（称为闭包运算），则整型常数可以

3、简单地记为“dd*”。类似地，常见程序设计语言中的标识符可由一个字母（用l表示），后跟零个或多个字母或者数字构成。在形式化描述中，我们用“

4、”表示可选择（either...or，也称为或者）运算，则标识符可以表示为“l(l

5、d)*”。这种用表示一类符号串的表达式，我们称为正规表达式（有些教材中称为正则表达式）。我们可以用文法来形式化描述正规表达式的结构：RE=({"

6、"，"*"，"·"，"）"，r},{R,T,B,F},P,R)，其中，产生式集P：R→R"

7、"R

8、R·R

9、R"*"

10、("R")"

11、r这里，“r”表示字母表中

12、的任意符号。上面定义中我们引入双引号，目的是为了区分作为正规表达式符号的竖线“

13、”与文法定义中所使用的竖线。在不至于引起混淆时，我们有时可以省略双引号。从正规表达式的定义可以看出，它有五个运算符“

14、”，“*”，“·”,“（”，“）”，我们规定，它们的优先级别是不同的。其中，左右括号的级别最高，星号“*”级别次之，连接运算“·”再次，或者“

15、”运算的级别最低。括号用于改变运算顺序，“*”表示闭包运算（零到任意次重复），“·”表示连接运算，“

16、”表示可选择运算等等。通常，“·”运算往往被省略。例如，前面定义的“数字”表达式为

17、"d·d*"，可以简写为"dd*"。为了描述方便，我们还可以引入两个新的运算符“+”及“？”:R→R“+”

18、R“？”其中，“+”表示正闭包运算（一到任意次重复）；“？”表示取零到一次运算。显然，a+等价于aa*，a?等价于a

19、，这里表示空符号串。进一步，我们不难得到：(a+)?=(a?)+=a*2.1.1正规表达式代数若我们把全体正规表达式构成一个集合R，则

20、","'·,"*">构成了一个代数系统.其中，

21、”>交换半群，是其幺元；是半群（不可交换），且是幺元。三种运算间有关系：r

22、s

23、=s

24、rr

25、(s

26、t)=(r

27、s)

28、tr

29、r=rr(st)=(rs)tr(s

30、t)=rs

31、rt(s

32、t)r=sr

33、trr=r=rr*r*=r*r*=

34、r

35、rr

36、…(r*)*=r*rr*=r*r(r*

37、s*)*=(r*s*)*=(r

38、s)*(rs)*r=r(sr)*【例2．1】利用上述等价关系式，我们可以将正规式a(ba

39、ca)

40、(ac

41、ab)a化简为：a(ba

42、ca)

43、(ac

44、ab)a=(aba

45、aca)

46、(aca

47、aba)(6,7)=aba

48、(aca

49、(aca

50、aba))(2)=aba

51、((aca

52、aca)

53、ab

54、a)(2)=aba

55、(aca

56、aba)(3)=aba

57、(aba

58、aca)(1)=(aba

59、aba)

60、aca(2)=aba

61、aca(3)=a(b

62、c)a(6,7)2.1.2正规表达式的性质我们将正规表达式（以下用~表示）用于描述语言：把~视为是描述同一字母表上的一些符号串之集的压缩表示。我们把~所表示的符号串集称为正规集（或正规语言）。例如，字母表{0，1}上定义的~：(0

63、1)*表示了{0，1}上的所有符号串之集。~的形式化定义如下：【定义3·1】一字母表上的正规表达式（简称为正规式）及相应的正规集可递归地定义如下：（

64、1）φ是一个正规表达式，相应的正规集为空集。（2）ε是一个正规表达式，相应的正规集为{ε}。（3）对于每个a∈Σ，a是正规表达式，相应的正规集为{a}。（4）若r,s为正规表达式，且相应的正规集分别记为Lr和Ls，则(i)(r)·(s)为正规表达式，相应的正规集为Lr·Ls={xy

65、x∈Lr,y∈Ls}(ii)(r)