解釋TOC中推導的概念

推導是一系列產生式規則。它用於獲取輸入字串。在解析過程中，我們必須做出兩個決定，如下所示

  • 我們必須確定要替換的非終結符。
  • 我們必須確定用於替換非終結符的產生式規則。

確定哪個非終結符需要用產生式規則替換有兩個選項，如下所示：

  • 最左推導
  • 最右推導。

讓我們詳細瞭解這兩個選項。

最左推導

在最左推導中，輸入被掃描，然後從左到右用產生式規則替換。因此，我們必須從左到右讀取該輸入字串。

示例

產生式規則

E=E+E rule1
E=E-E rule2
E=a|b rule3

假設輸入為a-b+a

現在，當我們執行最左推導時，結果如下：

E=E+E
E=E-E+E from rule2
E=a-E+E from rule3
E=a-b+E from rule3
E=a-b+a from rule3
Finally, the given string is parsed

最右推導

在最右推導中，輸入被掃描並從右到左用產生式規則替換。因此，我們必須從右到左讀取輸入字串。

示例

產生式規則

E=E+E rule1
E=E-E rule2
E=a|b rule3

假設輸入為a-b+a

現在，當我們執行最右推導時，我們得到以下結果：

E=E-E
E=E-E+E from rule1
E=E-E+a from rule3
E=E-b+a from rule3
E=a-b+a from rule3

更新於： 2021年6月11日

5K+ 瀏覽量

開啟您的職業生涯

透過完成課程獲得認證

開始學習
廣告