语法分析---文法转换

朱雀 2022-03-16 01:44 252阅读 0赞

### 文章目录 ###

*  需要文法转换的原因
 *   *  问题1
     *  问题2
 *  消除直接左递归
 *  消除直接左递归的一般形式
 *  消除间接左递归
 *  提取左公因子

# 需要文法转换的原因 #

## 问题1 ##

例如：

**文法G：**

S → a A d ∣ a B e S \\rightarrow\{aAd | aBe\} S→aAd∣aBe

A → c A \\rightarrow\{c\} A→c

B → b B \\rightarrow\{b\} B→b

**输入**：

a b c

**当同一非终结符的多个候选式存在共同前缀，将导致回溯现象。**

--------------------

## 问题2 ##

例如：

文法G：  
 E → E + T ∣ E − T ∣ T E \\rightarrow\{E+T | E-T | T\} E→E\+T∣E−T∣T

T → T ∗ F ∣ T / F ∣ F T \\rightarrow\{T \* F | T/F | F\} T→T∗F∣T/F∣F

F → ( E ) ∣ i d F \\rightarrow\{(E) | id\} F→(E)∣id

**输入：**

i d + i d ∗ i d id + id \* id id\+id∗id

**推导过程：**

E ⇒ E + T ⇒ E + T + T ⇒ E + T + T + T ⇒ . . . E \\Rightarrow\{E + T \\Rightarrow\{E + T + T \\Rightarrow\{E + T + T + T \\Rightarrow\{...\}\}\}\} E⇒E\+T⇒E\+T\+T⇒E\+T\+T\+T⇒...

因为文法开始符号的候选式没有以 i d id id开头的，所以选择第一个候选式。而因为输入的符号并没有被匹配，所以在相同的条件下依然还是要选择第一个候选式。由此导致了死循环。

注：

1.  含有 A → A α A \\rightarrow\{A\\alpha\} A→Aα形式产生式的文法称为是直接左递归(immediate left recursive)的（一步推导）。
2.  如果一个文法中有一个非终结符A使得对某个串 α \\alpha α存在一个推导 A ⇒ + A α A \\Rightarrow ^+\{A\\alpha\} A⇒\+Aα，那么这个文法就是左递归的。
3.  经过两步或两步以上推导产生的左递归称为是间接左递归。
4.  左递归文法会使递归下降分析器陷入无限循环。

# 消除直接左递归 #

例如：

A → A α ∣ β A \\rightarrow\{A \\alpha | \\beta\} A→Aα∣β( a ≠ ϵ a \\ne \\epsilon a̸=ϵ， β \\beta β不以A开头)

**推导：**

A ⇒ A α ⇒ A α α ⇒ . . . ⇒ A α α α . . . α ⇒ β α α α . . . α A \\Rightarrow\{A\\alpha \\Rightarrow\{A\\alpha\\alpha \\Rightarrow\{... \\Rightarrow\{A\\alpha\\alpha\\alpha...\\alpha \\Rightarrow\{\\beta\\alpha\\alpha\\alpha...\\alpha\}\}\}\}\} A⇒Aα⇒Aαα⇒...⇒Aααα...α⇒βααα...α

所以写成正则表达式就是 r = β α ∗ r=\\beta\\alpha^\* r=βα∗

那么原来的文法即可转换成 A → β A ′ A \\rightarrow\{\\beta A&\#x27;\} A→βA′和 A ′ → α A ′ ∣ ϵ A&\#x27; \\rightarrow\{\\alpha A&\#x27; | \\epsilon\} A′→αA′∣ϵ.

**而**， A ′ ⇒ α A ′ ⇒ α α A ′ ⇒ . . . ⇒ α . . . α α α A ′ ⇒ α . . . α α α A&\#x27; \\Rightarrow\{\\alpha A&\#x27; \\Rightarrow\{\\alpha\\alpha A&\#x27; \\Rightarrow\{...\\Rightarrow\{\\alpha...\\alpha\\alpha\\alpha A&\#x27; \\Rightarrow\{\\alpha...\\alpha\\alpha\\alpha\}\}\}\}\} A′⇒αA′⇒ααA′⇒...⇒α...αααA′⇒α...ααα，即 A ′ → α ∗ A&\#x27; \\rightarrow\{\\alpha ^\*\} A′→α∗。

事实上，这种转换把左递归转换成了右递归。

**例子：**

E → E + T ∣ T E \\rightarrow\{E + T | T\} E→E\+T∣T

可把 \+ T +T \+T看做 β \\beta β，把 T T T看做 β \\beta β。直接套用上面的公式，即

E → T E ′ E \\rightarrow\{T E&\#x27;\} E→TE′

E ′ → + T E ′ ∣ ϵ E&\#x27; \\rightarrow\{+TE&\#x27; | \\epsilon\} E′→\+TE′∣ϵ

# 消除直接左递归的一般形式 #

A → A α 1 ∣ . . . ∣ A α 2 ∣ A α n ∣ β 1 ∣ β 2 ∣ . . . ∣ β n A \\rightarrow\{A \\alpha\_1 | ... | A\\alpha\_2 | A\\alpha\_n | \\beta\_1 | \\beta\_2 | ... | \\beta\_n\} A→Aα1∣...∣Aα2∣Aαn∣β1∣β2∣...∣βn  
( a j ≠ ϵ a\_j \\ne \\epsilon aj̸=ϵ， β j \\beta\_j βj不以A开头)

那么可以转换为

A → β 1 A ′ ∣ β 2 A ′ ∣ . . . ∣ β n A ′ A \\rightarrow\{\\beta\_1A&\#x27; | \\beta\_2A&\#x27; | ... | \\beta\_nA&\#x27;\} A→β1A′∣β2A′∣...∣βnA′

A ′ → α 1 A ′ ∣ α 2 A ′ ∣ . . . ∣ α n A ′ ∣ ϵ A&\#x27; \\rightarrow\{\\alpha\_1A&\#x27; | \\alpha\_2A&\#x27; | ... | \\alpha\_nA&\#x27; | \\epsilon\} A′→α1A′∣α2A′∣...∣αnA′∣ϵ

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

# 消除间接左递归 #

例：

S → A α ∣ b S \\rightarrow\{A \\alpha | b\} S→Aα∣b

A → A c ∣ S d ∣ ϵ A \\rightarrow\{Ac | Sd | \\epsilon\} A→Ac∣Sd∣ϵ

将S的定义带入A-产生式，得：

A → A c ∣ A a d ∣ b d ∣ ϵ A \\rightarrow\{Ac | Aad | bd | \\epsilon\} A→Ac∣Aad∣bd∣ϵ

再消除A-产生式得直接左递归，得：

A → b d A ′ ∣ A ′ A \\rightarrow\{bdA&\#x27; | A&\#x27;\} A→bdA′∣A′

A ′ → c A ′ ∣ a d A ′ ∣ ϵ A&\#x27; \\rightarrow\{cA&\#x27; | adA&\#x27; | \\epsilon\} A′→cA′∣adA′∣ϵ

# 提取左公因子 #

**例：**