编译原理 | 由正规文法构造状态转换图

词法分析 ：由正规文法构造状态转换图

解题方法

1. 由左线性文法构造状态转换图

$左线性文法G=(V_N,V_T,P,Z)\\ (1) G中形如U::=Ba,则可化成：B—(a)—>U（表示状态B向状态U引一条箭弧线并标记符号a，不方便画图，就直接这样表示了，你们懂就行）\\ (2) G中形如U::=a,则可化成：S—(a)—>U（表示初始状态S向状态U引一条箭弧线并标记符号a）\\ (3) 状态转换图开始状态标记为S，终止状态标记为Z$左线性文法G=(VN​,VT​,P,Z)(1)G中形如U::=Ba,则可化成：B—(a)—>U（表示状态B向状态U引一条箭弧线并标记符号a，不方便画图，就直接这样表示了，你们懂就行）(2)G中形如U::=a,则可化成：S—(a)—>U（表示初始状态S向状态U引一条箭弧线并标记符号a）(3)状态转换图开始状态标记为S，终止状态标记为Z

例题

$设左线性文法G[Z] = (V_N,V_T,P,Z),其中\\ V_N={Z,U,V}\\ V_T={0,1}\\ P: Z::=U0|V1\\ U::=Z1|1\\ V::=Z0|0$设左线性文法G[Z]=(VN​,VT​,P,Z),其中VN​=Z,U,VVT​=0,1P:Z::=U0∣V1U::=Z1∣1V::=Z0∣0

解：

$由Z::=U0|V1,得U-(0)->Z,V-(1)->Z\\ 由U::=Z1|1,得Z-(1)->U,S-(1)->U\\ 由V::=Z0|0,得Z-(0)->V,S-(0)->V$由Z::=U0∣V1,得U−(0)−>Z,V−(1)−>Z由U::=Z1∣1,得Z−(1)−>U,S−(1)−>U由V::=Z0∣0,得Z−(0)−>V,S−(0)−>V

所以，得到状态转换图如下：

2. 由右线性文法构造状态转换图

$右线性文法G=(V_N,V_T,P,S)\\ (1) G中形如U::=aB,则可化成：U—(a)—>B（表示状态U向状态B引一条箭弧线并标记符号a，不方便画图，就直接这样表示了，你们懂就行）\\ (2) G中形如U::=a,则可化成：U—(a)—>Q（表示状态U向终止状态Q引一条箭弧线并标记符号a）\\ (3) 状态转换图开始状态标记为S，终止状态标记为Q$右线性文法G=(VN​,VT​,P,S)(1)G中形如U::=aB,则可化成：U—(a)—>B（表示状态U向状态B引一条箭弧线并标记符号a，不方便画图，就直接这样表示了，你们懂就行）(2)G中形如U::=a,则可化成：U—(a)—>Q（表示状态U向终止状态Q引一条箭弧线并标记符号a）(3)状态转换图开始状态标记为S，终止状态标记为Q

例题

$设右线性文法G = (\{S,A,B\},\{a,b\},S,P),其中\\ P: S::=bA\\ A::=bB\\ A::=aA\\ A::=b\\ B::=a$设右线性文法G=({S,A,B},{a,b},S,P),其中P:S::=bAA::=bBA::=aAA::=bB::=a

解：

过程和左线性差别不大，所以得到状态转换图如下：

3. 左线性文法和右线性文法之间的关系

$等价关系\\ 右线性文法的产生式 \qquad 左线性文法 的产生式\\ S->a \qquad S->a\\ S->a_1A_1 \qquad A_1->a_1\\ A_1->a_2A_2 \qquad A_2->A_1a_2\\ A_2->a_3 \qquad S->A_2a_3$等价关系右线性文法的产生式左线性文法的产生式S−>aS−>aS−>a1​A1​A1​−>a1​A1​−>a2​A2​A2​−>A1​a2​A2​−>a3​S−>A2​a3​