编译原理:文法转换

文法转换

1. 例

$$\begin{gathered} \text{文法}G \\ S\to aAd\mathrm{\mid }aBe \\ A\to c \\ B\to b \\ \text{输入}abc \end{gathered}$$

文法G\ S \rarr aAd | aBe \ A \rarr c \ B \rarr b \ 输入 a b c文法GS→aAd∣aBeA→cB→b输入abc

:::warning 同一非终结符的多个候选式存在共同前缀,将导致回溯现象 :::

2. 例

$$文法G\ E \rarr E+T | E - T | T \ T \rarr T*F | T/F | F \ F \rarr ( E ) | id \ 输入 id + id * id\$$

E \Rightarrow E + T \ E \Rightarrow E + T + T \ ...\文法GE→E+T∣E−T∣TT→T∗F∣T/F∣FF→(E)∣id输入id+id∗idE⇒E+TE⇒E+T+T...

:::danger

左递归文法会使递归下降分析器陷入无限循环

:::

概念

:::tip

含有$A \rarr Aa$形式产生式的文法称为是直接左递归

---

如果一个文法中有一个非终结符A使得对某个串a存在一个推导$A \Rightarrow {}^{+}Aa$,那么这个文法就是左递归的

---

经过两步或两步以上推到产生的左递归成为是间接左递归的

:::

消除直接左递归

$$A \rarr A\alpha | \beta (a \not= \varepsilon,\beta不以A开头)\ \Downarrow \ A \rarr \beta A^{'{'}'{'}'} \ A^{'{'}'{'}'} \rarr \alpha A^{'{'}'{'}'} |\varepsilon$$

:::info

事实上,这种消除过程,就是把左递归转换成了右递归

:::

更一般地

$$A \rarr A \alpha_1 | A \alpha_2 | ... | A \alpha_n | \beta_1 | \beta_2 | ... | \beta_m \ (\alpha_i \not= \varepsilon, \beta_j不以A开头 )\ \Downarrow \ A \rarr \beta_1 A^{'{'}'{'}'} | \beta_2 A^{'{'}'{'}'}|...|\beta_m A^{'{'}'{'}'} \ A^{'{'}'{'}'} \rarr \alpha_1 A^{'{'}'{'}'} | \alpha_2 A^{'{'}'{'}'}| ... | a_n A^{'{'}'{'}'} | \varepsilon$$

:::warning

消除左递归是要付出代价的---引进了一些非终结符和$\varepsilon$_产生式

:::

消除间接左递归

例

$$S \rarr A \alpha | b \ A \rarr Ac | Sd | \varepsilon \ >>将S的定义带入A-产生式,得:\ A-Ac | Aad | bd | \varepsilon \ >> 消除A-产生式的直接左递归,得: \ A \rarr bdA^{'{'}'{'}'} | A \ A^{'{'}'{'}'} \rarr cA^{'{'}'{'}'} | adA^{'{'}'{'}'} | \varepsilon$$

提取左公因子

例

文法G

$$S \rarr aAd | aBe \ A \rarr c \ B \rarr b \ \Downarrow \$$

S→aAd∣aBeA→cB→b⇓

文法$G^{'}$

$$S \rarr aS^{'{'}'{'}'} \ S^{'{'}'{'}'} \rarr Ad |Be \ A \rarr c \ B \rarr b \$$

:::info

通过改写产生式来推迟决定,等读入了足够多的输入,获得足够信息后再做出正确的选择

:::