左分解因子和左遞歸之間的區別

Question

Left Factoring和Left Recursion有什麼區別？我知道Left factoring是一種預測性的自頂向下解析技術。但是當我聽到這兩個詞時，我感到困惑。

Answer 1

這是我見過用這兩個詞的方式：

1. 左遞歸：當一個或多個作品可以從自己達到無消耗在中間的標記。
2. 左分解：轉換過程，將語法從左遞歸形式轉換爲等價的非左遞歸形式。

Answer 2

left recursion：=當左手非終端與右手非終端相同時。 示例： A-> A & | B其中&是阿爾法。 我們可以使用重寫這個生產來刪除左邊的ricursion。

A-> BA」 A ' - > & A' |€

左因素意味着productn不應該不確定性。 。 例如： A-> & A | & B | & C

Answer 3

左分解是一種語法轉換技術。它包括「分解」兩個或更多產品共有的前綴。

例如，從去：

A - >αβ| αγ

到：

A - >αA '

A' - >β| γ

---

左遞歸是一個屬性語法具有每當你可以從一個給定的可變（非終端）導出RHS具有相同變量開始，在一個或多個步驟。

例如：

A - > Aα

或

A - >乙α

乙 - >甲γ

有一種稱爲的語法轉換技術，消除了左遞歸，它提供了一種方法，用於在給定左遞歸語法的情況下生成另一個等價且不剩下遞歸的語法。

---

的關係/這兩個詞之間的混淆可能是由事實上，這兩個轉換技術可能需要能夠得到的預測自上而下解析器之前被應用到語法派生的。

Answer 4

左保留因子是消除在同一個非終端的兩個生產中出現的常見左邊因素。這樣做是爲了避免解析器回溯。假設解析器有預見性，請考慮此示例 -

A - > qB | qC
其中A，B，C是非終端並且q是句子。 在這種情況下，解析器會對兩種產品中的哪一種產品感到困惑，並且可能需要回溯。左理後，語法轉換TO-

A - > qD的

d - >乙| C

在這種情況下，帶前視的解析器將始終選擇正確的生產。

左遞歸是一種情況，當非終端生產中最左側的非終端本身是非終端本身（直接左遞歸）或通過一些其他非終端定義時，重寫爲非終端本身，終端再次（間接左遞歸）。 考慮這些實施例 -

（1）A - > AQ（直接）

（2）A - >貝 乙 - >氬（間接）

左遞歸必須被刪除，如果該分析器進行自上而下的分析

Answer 5

左遞歸： 文法留下，如果它有一個非終結符號A使得有一個推導遞歸A - >Aα| β其中α和β是不以A開頭的末端和非末端序列。

設計自頂向下解析器時，如果語法中存在左遞歸，則解析器會陷入無限循環，這是因爲A正試圖匹配A本身，這是不可能的。 我們可以通過重寫違規生產來消除上述左遞歸。AS-

A - >βA '

A' - >αA」 | epsilon

左分解：左分解需要消除語法的非確定性。假設一個文法，S - > abS | aSb

這裏，S在生產規則（S的兩個替代選擇）中導出相同的終端a，其遵循非確定性。我們可以重寫生產推遲S的決定AS-

的S - >爲 '

S' - > BS |銻

因此，S」可以被替換爲bs或銻

Answer 6

左因素：

讓定的文法： A - > AB1 | ab2 | ab3

1）我們可以看到，對於每一個生產，如果我們在這裏選擇任何生產，都會有一個共同的前綴&，我們不會確定我們不需要回溯。
2）它是非確定性的，因爲我們無法選擇任何生產，並且確信我們將通過製作正確的分析樹來達到我們期望的字符串。 但是如果我們以確定性的方式重寫語法，並且讓我們足夠靈活以使它可能沒有回溯的任何字符串....它將是：

A→aA' ， A' - > b1 | B2 | b3 現在，如果我們被要求爲字符串ab2 ......製作解析樹，我們不需要回溯。因爲當我們得到A時，我們總是可以選擇正確的生產，因此我們將生成正確的分析樹。

左遞歸：

A→Aa | b 這裏很明顯，如果我們選擇第一個生產，A的左邊的孩子總是A，這是左邊的遞歸，因爲A一遍又一遍地調用自己。 從這個語法生成的字符串是： 巴* 因爲這不能是一個語法......我們通過書面消除左遞歸：

A - > BA「 A」 - > E | aA' 現在我們不會有遞歸，並且我們也可以生成ba *。