構建字串 aabbabba 的推導樹。

問題

針對給定的上下文無關文法 (CFG)，推匯出字串 aabbabba 的推導樹。

S->aB|bA
A->a|aS|bAA
B->b|bS|aBB

解決方案

推導是一系列產生式規則，用於獲取輸入字串。

推導樹

它是給定 CFG 的給定產生式規則推導的圖形表示。它也稱為語法樹。

屬性

推導樹包含一些屬性，如下所示：

  • 根節點始終是表示起始符號的節點。
  • 推導是從左到右讀取的。
  • 葉節點始終是終結符節點。
  • 內部節點始終是非終結符節點。

給定的 CFG 如下：

S->aB|bA
A->a|aS|bAA
B->b|bS|aBB

要繪製語法樹，首先嚐試獲取字串 aabbabba 的推導。

讓我們以如下所示的最左推導為例：

S-> aB
 ->aaBB
 ->aabSB
 ->aabbAB
 ->aabbaB
 ->aabbabS
 ->aabbabbA
 ->aabbabba which is our final string

現在，為給定的語法構建推導樹。

如果語法生成多種型別的樹，則稱給定的語法為二義性語法。

更新於： 2021年6月12日

12K+ 瀏覽量

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告