编译原理:文法转换

文法转换

1. 例

$$\text{文}\text{法}GS\to aAd|aBeA\to cB\to b\text{输}\text{入}abc$$

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

2. 例

$$\text{文}\text{法}GE\to E+T|E-T|TT\to T\ast F|T/F|FF\to (E)|id\text{输}\text{入}id+id\ast idE\Rightarrow E+TE\Rightarrow E+T+T...$$

:::danger

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

:::

概念

:::tip

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

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

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

:::

消除直接左递归

$$A\to A\alpha |\beta (a≠\epsilon ,\beta \text{不}\text{以}A\text{开}\text{头})\Downarrow A\to \beta A^{{}^{\prime }}{A}^{{}^{\prime }}\to \alpha A^{{}^{\prime }}|\epsilon$$

:::info

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

:::

更一般地

$$A\to A{\alpha }_1|A{\alpha }_2|...|A{\alpha }_n|{\beta }_1|{\beta }_2|...|{\beta }_m({\alpha }_i≠\epsilon ,{\beta }_j\text{不}\text{以}A\text{开}\text{头})\Downarrow A\to {\beta }_1{A}^{{}^{\prime }}|{\beta }_2{A}^{{}^{\prime }}|...|{\beta }_m{A}^{{}^{\prime }}{A}^{{}^{\prime }}\to {\alpha }_1{A}^{{}^{\prime }}|{\alpha }_2{A}^{{}^{\prime }}|...|a_n{A}^{{}^{\prime }}|\epsilon$$

:::warning

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

:::

消除间接左递归

例

$$S\to A\alpha |bA\to Ac|Sd|\epsilon >>\text{将}S\text{的}\text{定}\text{义}\text{带}\text{入}A-\text{产}\text{生}\text{式},\text{得}:A-Ac|Aad|bd|\epsilon >>\text{消}\text{除}A-\text{产}\text{生}\text{式}\text{的}\text{直}\text{接}\text{左}\text{递}\text{归},\text{得}:A\to bd{A}^{{}^{\prime }}|A{A}^{{}^{\prime }}\to c{A}^{{}^{\prime }}|ad{A}^{{}^{\prime }}|\epsilon$$

提取左公因子

例

文法G

$$S\to aAd|aBeA\to cB\to b\Downarrow$$

文法$G^{{}^{\prime }}$

$$S\to a{S}^{{}^{\prime }}{S}^{{}^{\prime }}\to Ad|BeA\to cB\to b$$

:::info

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

:::