《编译原理》2.3第二章形式语言与自动机理论基础

《《编译原理》2.3第二章形式语言与自动机理论基础》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章形式语言与自动机理论基础2.32.3.1正规文法与有限自动机(FA)正规文法与有限自动机(FA)的等价性对于每一个正规文法都存在一个FAm，L(m)=L(G)每一个DFAm，都存在一个正规文法G，使L(G)=L(m)仅讨论右线性文法和有穷自动机的等价性问题22.3.1正规文法与有限自动机(FA)1、由NFANFA构造等价的正规文法正规文法有穷自动机的字母表为文法的终结符号集字母表终结符号集有穷自动机的状态集为文法的非终结符号集有穷自动机的初态对应于文法的开始符号状态集非终结符号集对有穷自动机的转换函数初

2、态f(A,t)=B,开始符号可写成文法的一个产生式A→tB对有穷自动机的终态f(A,t)=BZ，增加一个产生式A→tBZ→终态ZZ→3NFA的状态图如图所是，求其等价的正规文法（右线性）aabSAaZbG[S]:S→aS

3、bSS→aAA→aZ

4、bZZ→42.3.1正规文法与有限自动机(FA)2、由正规文法构造等价的NFA文法的终结符号集为有穷自动机的字母表文法的非终结符号集为有穷自动机的状态集文法的开始符号作为有穷自动机的初态对文法中形如A→tB的产生式，构造有穷自动机的一个转换函数f(A,t)=B,对文

5、法中形如A→t的产生式，构造有穷自动机的一个转换函数f(A,t)=Z5NFA的状态图如图所是，求其等价的正规文法（右线性）G[S]:S→aS

6、bSS→aAA→a

7、baabSAaZb62.3.2正规式与正规集定义2.31(正规式与正规集)设Σ为有限字母表，在Σ上的正规式与正规集可递归定义如下：1.ε和Ф是Σ上的正规式，它们表示的正规集分别为{ε}和Ф；2.对任何a∈Σ,a是Σ上的正规式,它的正规集为{a}；3.若r,s都是正规式,它们的正规集分别为R和S,则(r

8、s)、(r·s)、(r)*也是正规式，它们分别表示的正规

9、集是：R∪S，RS，R*。4.有限次使用上述三条规则构成的表达式，称为Σ上的正规式，仅由这些正规式表示的集合为正规集。72、有关正规式及正规集的说明说明：1.正规式与相应的正规集是等价的，正规集给出了相应正规式所描述的全部单词（句子）；2.正规式的运算结果是正规集；3.正规式不是集合，其运算结果正规集是集合。Ф是特例。8正规表达式及正规集正规表达式的定义是字母表正规表达式正规表达式表达的语言1.，{}，{}2.a,a{a}3.若r,sL(r),L(s)则(1)(r)(s)L(r)L(s)(2)(r)(

10、s)L(r)L(s)(3)(r)*(L(r))*(4)(r)L(r)92、有关正规式及正规集的说明注意：定义中的括号主要用于规定运算顺序。一般规定优先级从高到低依次为*,•,

11、，可省略某些括号例(r)•((s)*)

12、(r)——可简写：r•s*

13、r。•常常可省略不写，可写成rs*

14、r。10例题=a,b,上的正规式和对应的正规集是：正规式正规集(a)aba,b(b)(ab)(ab)aa,ab,ba,bb(c)a*,a,aa,aaa,aaaa,…(d)(ab)*{,a,b,aa,ab,ba

15、,bb,aaa,...(e)aab*{a,ab,abb,abbb,……11例2：令Σ={A,B,0,1},则：(A

16、B)(A

17、B

18、0

19、1)*={A,B,AA,AB,A0,A1,BA,BB,B0,B1,…}——Σ上的“标识符”的全体(0

20、1)(0

21、1)*={0,1,00,01,10,11,…}——Σ上“数”的全体12等价正规集注意：正规式和正规集间不是一一对应关系若两个正规式e和e所表示的正规集相同,则说e和e1212等价,写作e1=e2。例如：e=ab，e=ba12又如：e=b(ab),e=(ba)b

22、12e=(ab),e=(ab)12例：设PASCAL语言子集有如下单词①BEGIN②END③IF④THEN⑤ELSE⑥标识符⑧无符号整常数⑨>⑩>=⑾<⑿<=⒀=⒁<>14正规表达式的等价关系说明恒等式rs=sr“”是可交换的r(st)=(rs)t“”是可结合的r(st)=(rs)t连接是可结合的r(st)=rsrt分配律(st)r=srtrr=rr=r对连接，是单位元素r*=(r)*“*”和之间的关系r*=r**“*”是幂等的15正规文法与正规式回顾正规文法的定义

23、Ｇ=(Ｖ，Ｖ，S，P)TNＶ：终结符(Terminal)集TＶ：非终结符(Variable)集，Ｖ∩Ｖ=ΦNTNＳ：开始符号(StartSymbol)，S∈ＶNＰ：产生式的非空有穷集合正规文法转换成正规式对于Ｇ=(Ｖ，Ｖ，S，P)，存在一