资源描述：
《编译原理334-RG和FA转换.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第三章词法分析3.1对于词法分析器的要求3.2词法分析器的设计3.3正规表达式和自动机3.4词法分析器的自动产生3.3正规表达式和自动机3.3.1正规式和正规集3.3.2确定有限自动机3.3.3非确定有限自动机3.3.4正规文法与有限自动机的等价性3.3.5正规式与有限自动机的等价性3.3.6确定有限自动机的化简3.3.4RG与FA的等价性(1).对每个右线性正规文法G或左线性正规文法G,都存在一个有限自动机(FA)M,使得L(M)=L(G)(2).对每个FAM,都存在一个右线性正规文法GR和左线
2、性正规文法GL,使得L(M)=L(GL)=L(GR)本节涉及到的左线性文法考试不考证明过程不考,但尽量理解如何证明两个集合相等?1.从正规文法直接构造等价的有穷自动机RG－>FA右线性正规文法G=(VT,VN,S,P)自动机M=(VN∪{f},VT,δ,S,{f})将VN中的每一个非终结符号视为状态符号,并增加一个新的终结状态符号f,fVN状态函数δ由以下规则定义产生式转换函数A→aδ(A,a)=fA→aA1
3、aA2
4、…
5、aAkδ(A,a)={A1,A2,…,Ak}在正规文法G中,Sw的充要条件是
6、:p52在M中,从状态S到状态f有一条通路,其上所有箭弧的标记符号依次连接起来恰好等于w,即w∈L(G)当且仅当w∈L(M),故L(G)=L(M)NFA+ffG[S]：S→aA，S→bB，S→ε，A→aB，A→bA，B→aS，B→bA，B→ε补充例：RG－>FASABababbaεε产生式的个数=弧的个数*RGL－>FAP52左线性文法G=(VT,VN,S,P)自动机M=(VN∪{q0},VT,δ,q0,{S})将VN中的每一个非终结符号视为状态符号,并增加一个初始状态符号q0,q0VN考试不考
7、状态函数δ由以下规则定义产生式转换函数A→aδ(q0,a)=AA1→Aa,A2→Aa,…,Ak→Aaδ(A,a)={A1,A2,…,Ak}考试不考DFAM=(S,,δ,S0,F)GR=(,S,S0,P)若有δ(A,a)=B,则:(a)当BF时,令A→aB(b)当B∈F时,令A→aB
8、a2.将有穷自动机转换成等价的正规文法FA－>RG例3.4p52不难发现L(M)=0(10)*1)FA－>GRGR:A→0
9、0BA→1DB→0DB→1CC→0
10、0BC→1DD→0D
11、1DACBD0100110,1D
12、是多余状态2)GR－>FA更正:B应为非终态GR:A→0
13、0B
14、1DB→0D
15、1CC→0
16、0B
17、1DD→0D
18、1DAfCBD001010010,1ACBD0100110,1AfCBD001010010,1GR:A→0
19、0B
20、1DB→0D
21、1CC→0
22、0B
23、1DD→0D
24、1D一个正规文法可以对应多个有穷自动机
