编译原理实验

词法分析

语法分析

语法

$$\left\{ \begin{array}{l} S \to S' \\ S' \to begin \; D_T \; ; \; E_T \; end \\ D_T \to D \mid D_T \; ; \; D \\ D \to V_D \mid F_D \\ V_D \to integer \; V \\ V \to I \\ F_D \to integer \; function \; I (A) \; ; F_B \\ A \to V \\ F_B \to begin \; D_T \; ; \; E_T \; end \\ E_T \to E \mid E_T \; ; \; E \\ E \to E_R \mid E_W \mid E_A \mid E_C \\ E_R \to read(V) \\ E_W \to write(V) \\ E_A \to V \; := \; A_E \\ A_E \to A_E \; - \; I_T \mid I_T \\ I_T \to I_T \; * \; F_A \mid F_A \\ F_A \to V \mid C \mid F_E \\ F_E \to I(V) \\ E_C \to if \; C_E \; then \; E \; else \; E \\ C_E \to A_E \; S_R \; A_E \\ S_R \to < \mid <= \mid > \mid >= \mid = \mid <> \\ \end{array} \right.$$

$S$: 程序 $S'$: 分程序 $D_T$: 说明语句表 $E_T$: 执行语句表 $D$: 说明语句 $V_D$: 变量说明 $F_D$: 函数说明 $V$: 变量 $I$: 标识符 $A$: 参数 $F_B$: 函数体 $E$: 执行语句 $E_R$: 读语句 $E_W$: 写语句 $E_A$: 赋值语句 $E_C$: 条件语句 $A_E$: 算数表达式 $I_T$: 项 $F_A$: 因子 $F_E$: 函数调用 $C_E$: 条件表达式 $S_R$: 关系运算符

左递归消除

有左递归的语句:

$$\left\{ \begin{array}{l} D_T \to D \mid D_T \; ; \; D \\ E_T \to E \mid E_T \; ; \; E \\ I_T \to I_T \; * \; F_A \mid F_A \\ A_E \to A_E \; - \; I_T \mid I_T \\ \end{array} \right.$$

消除左递归:

$$D_T \to D_T \; ; \; D \mid D ==> \left\{ \begin{array}{l} D_T \to D \; D_T' \\ D_T' \to ; D \; D_T' \mid \epsilon \\ \end{array} \right.$$

$$E_T \to E_T \; ; E \mid E ==> \left\{ \begin{array}{l} E_T \to E \; E_T' \\ E_T' \to ; E \; E_T' \mid \epsilon \\ \end{array} \right.$$

$$I \to I \; * \; F_A \mid F_A ==> \left\{ \begin{array}{l} I_T \to F_A \; I_T' \\ I_T' \to * F_A \; I_T' \mid \epsilon \\ \end{array} \right.$$

$$A_E \to A_E \; - \; I_T \mid I_T ==> \left\{ \begin{array}{l} A_E \to I_T \; A_E' \\ A_E' \to - I_T \; A_E' \mid \epsilon \\ \end{array} \right.$$

消除后结果

$$\left\{ \begin{array}{l} S \to S' \\ S' \to begin \; D_T \; ; \; E_T \; end \\ D_T \to D \; D_T' \\ D_T' \to ; D \; D_T' \mid \epsilon \\ D \to V_D \mid F_D \\ V_D \to integer \; V \\ V \to I \\ F_D \to integer \; function \; I (A) \; ; F_B \\ A \to V \\ F_B \to begin \; D_T \; ; \; E_T \; end \\ E_T \to E \; E_T' \\ E_T' \to ; E \; E_T' \mid \epsilon \\ E \to E_R \mid E_W \mid E_A \mid E_C \\ E_R \to read(V) \\ E_W \to write(V) \\ E_A \to V \; := \; A_E \\ A_E \to I_T \; A_E' \\ A_E' \to - I_T \; A_E' \mid \epsilon \\ I_T \to F_A \; I_T' \\ I_T' \to * F_A \; I_T' \mid \epsilon \\ F_A \to V \mid C \mid F_E \\ F_E \to I(A_E) \\ E_C \to if \; C_E \; then \; E \; else \; E \\ C_E \to A_E \; S_R \; A_E \\ S_R \to < \mid <= \mid > \mid >= \mid = \mid <> \\ \end{array} \right.$$