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

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

解题方法

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

$左线性文法 G = (V_{N}, V_{T}, P, Z) (1) G 中形如 U : : = B a, 则可化成： 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 : : = U 0 ∣ V 1 U : : = Z 1 ∣ 1 V : : = Z 0 ∣ 0$

解：

$由 Z : : = U 0 ∣ V 1, 得 U - (0) - > Z, V - (1) - > Z 由 U : : = Z 1 ∣ 1, 得 Z - (1) - > U, S - (1) - > U 由 V : : = Z 0 ∣ 0, 得 Z - (0) - > V, S - (0) - > V$

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

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

$右线性文法 G = (V_{N}, V_{T}, P, S) (1) G 中形如 U : : = a B, 则可化成： 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 : : = b A A : : = b B A : : = a A A : : = b B : : = a$

解：

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

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

$等价关系右线性文法的产生式左线性文法的产生式 S - > a S - > a S - > a_{1} A_{1} A_{1} - > a_{1} A_{1} - > a_{2} A_{2} A_{2} - > A_{1} a_{2} A_{2} - > a_{3} S - > A_{2} a_{3}$