---
title: 编译原理:文法转换
abbrlink: 20304
date: "2025-03-26 14:35:14"
updated: "2025-07-04 18:44:32"
desc: 同一非终结符的多个候选式存在共同前缀,将导致回溯现象
categories:
    - 学校学习
tags:
    - 学习
    - 记录
    - 编译原理
---

文法转换

1. 例

$$


文法G\\
S \rarr aAd | aBe \\
A \rarr c \\
B \rarr b \\
输入 a b c
$$

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

<!--more-->

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 \\
...\\
$$

:::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 \\


$$

文法$G^{'}$

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

:::info

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

:::


---

**作者：**xingwangzhe

**本文链接：**[https://xingwangzhe.fun/posts/20304/](https://xingwangzhe.fun/posts/20304/)

本文采用[知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议](https://creativecommons.org/licenses/by-nc-sa/4.0/)进行许可。