什麼是左遞迴以及如何消除它？

一個文法 G (V, T, P, S) 如果它具有以下形式的產生式，則為左遞迴。

A → A α |β。

上述文法是左遞迴的，因為產生式的左側出現在產生式右側的第一個位置。可以透過用以下一對產生式替換它來消除左遞迴

A → βA′

A → αA′|ϵ

左遞迴的消除

可以透過引入新的非終結符 A 來消除左遞迴，使得。

這種型別的遞迴也稱為**直接左遞迴**。

在左遞迴文法中，A 的展開將在每一步生成 Aα、Aαα、Aααα，導致它進入無限迴圈。

左遞迴的一般形式為

A → Aα₁|Aα₂| … . |Aα_m|β₁|β₂| … . . β_n

可以替換為

A → β₁A′|β₂A′| … . . | … . . |β_nA′

A → α₁A′|α₂A′| … . . |α_mA′|ε

**示例 1** − 考慮來自文法的左遞迴。

E → E + T|T

T → T * F|F

F → (E)|id

從文法中消除直接左遞迴。

解決方案

將 E → E + T|T 與 A → A α |β 進行比較

∴ A = E，α = +T，β = T

∴ A → A α |β 更改為 A → βA′ 和 A′ → α A′|ε

∴ A → βA′ 表示 E → TE′

A′ → α A′|ε 表示 E′ → +TE′|ε

將 T → T ∗ F|F 與 A → Aα|β 進行比較

∴ A = T，α =∗ F，β = F

∴ A → β A′ 表示 T → FT′

A → α A′|ε 表示 T′ →* FT′|ε

產生式 F → (E)|id 沒有左遞迴

∴ 組合產生式 1、2、3、4、5，我們得到

E → TE′
E′ → +TE′| ε
T → FT′
T →* FT′|ε
F → (E)| id

**示例 2** − 消除以下文法的左遞迴。

S → a|^|(T)

T → T, S|S

解決方案

在 T-產生式中存在直接左遞迴。

將 T → T, S|S 與 A → A α | β 進行比較，其中 A = T，α =, S，β = S

∴ 完整的文法將是

S→ a|^(T)
T→ ST′
T′ →,ST′| ε

**示例 3** − 從文法中消除左遞迴

E → E + T|T

T → T * F|F

F → (E)|id

解決方案

去除左遞迴後的產生式將是

E → TE′

E′ → +TE′| ∈

T → FT′

T′ →∗ FT′| ∈

F → (E)|id

**示例 4** − 從文法中去除左遞迴

E → E(T)|T

T → T(F)|F

F → id

解決方案

消除所有 Aα 產生式中的直接左遞迴，我們得到

E → TE′

E → (T)E′|ε

T → FT′

T′ → (F)T′|ε

F → id

Ginni

更新於: 2021-10-30

117K+ 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

開始學習