计算机课件第三章词法分析习题讲解(编译原理).ppt

自动机、正则文法、正则表达式的相互转化 如何为正则文法构造状态转换图？ Q-a 或Q-Ba 步骤如下： 以S为开始状态作结点； 把文法中的每一个非终结符号作为状态结点； 对于形如Q-a的每个规则，引一条开始状态S到状态Q的弧，弧上标记为a；对于形如Q-Ba的规则引一条从状态B到Q的弧，弧上标记为a。 以识别符号为终止状态。 构造状态转换图举例 例如：对于正则文法G[Z]： Z-Za|Aa|Bb A-Ba|a B-Ab|b 从状态转换图构造有穷状态自动机 例如：从下面状态图构造DFA DFA D=（{S，Z，A，B}，{a，b}，M，S，{Z}） 其中M定义为： M（S，a）=A M（S，b）=B M（A，a）=Z M（A，b）=B M（B，a）=A M（B，b）=Z M（Z，a）=Z 有穷自动机?正规文法 已知DFA为M =(S,?,δ,S0,F),求相应的正规文法(右线性) G=(?,S,S0,P)的方法: 1. 终结符号: VT=字母表? 2. 开始符号：S=初始状态S0 3. 非终结符号：VN = S 4. 产生式： 对任何a∈?，A,B∈S,若有：δ(A,a)=B，则： 当B?F, 令A→aB； 当 B∈F， A→a|aB; 若S0∈F，增加S0 → ? 例:有穷自动机为： 正规式?NFA方法 示例 NFA M到正规式R 我们把状态转换图的概念拓广，令每条弧可用一个正规式作标记。 第一步，在M的状态转换图上加进两个结，一个为x结点，一个为y结点，从x结点用ε弧连接到M的所有初态结点，从M的所有终态结点用ε连接到y结点。形成一个与M等价的M`，M`只有一个初态x和一个终态y。 第二步，逐步消去M`中的所有结点，直至只剩下x和y结点。在消结过程中，逐步用正规式来标记弧。其消结的规则如下： 正规文法转换成正规式 将每条产生式改写为正规式 用代入法解正规式方程组，最后只剩下一个开始符号定义的正规式,其中不含非终结符 正规文法到正规式的转换规则: 例：将文法G[S]转换成正规式 G：S→a A|a A→dA|d 先由产生式得: S=aA|a A=d*d 将A代入S中得: S=ad*d|a 利用正规式变换得 S=a(d*d|ε)=ad* 说明:d*d|ε =(ε|d|dd|…)d|ε =d|dd|…|ε= d* 所求正规式为ad* 正规式转换成正规文法 例: 将R=a(a|d)*转换成相应的正则文法 令转换成文法G=(VN,VT,P,S) 其中VT={a,d}， 文法开始符为S 首先形成S→a(a|d)*,然后变换 S→aA A→(a|d)* 例: L(M)如右图： 求正规式R，使L(R)=L(M). 书本例题讲解 例2.5 例2.7 例2.15 例2.16 例2.17 习题 2.1，2.5 2.6 2.8 2.9 2.10 2.13 5: 将R=a(a|b)*转换成相应的正则文法 令转换成文法G=(VN,VT,P,S) 其中VT={a,b}， 文法开始符为S 首先形成S→a(a|b)*,然后变换 S→aA A→(a|b)* 6：将文法G[S]转换成正规式 G：S→a A|a A→bA|b 先由产生式得: S=aA|a A=b*b 将A代入S中得: S=ab*b|a 利用正规式变换得 S=a(b*b|ε)=ab* 说明:d*d|ε =(ε|b|bb|…)b|ε =b|bb|…|ε= b* 所求正规式为ab* * * 正则文法 NFA 正则式 1 2 3 4 5 6 DFA 最小化 复习 1 S A B a b S A B a Z Z a S A B a b Z b a a b a a a b a (1) (2) (3) a b S A B a b Z b a a 2 X Y α α α|β 1 2 α β 1 2 3 3 α ε ε 1 αβ 3 2 α β 1 2 2 1 α* 1 2 3.3 有穷自动机 a(a|b)* X Y a(a|b)* X Y a 1 (a|b)* X Y a 1 (a|b) 2 X Y a 1 a 2 b ε ε ε ε 4 NFA M a,b b a a a b b a b 0 1 3 4 2 a,b a,b a a b b a,b ε ε ε x 0 3 1 4 2 y R1|R