上下文免費語法分析樹

Question

我有相同的數字x和y的字符串。我的CFG應該以xy，xyxy，xyxyxy，xxxyyy和xxyxyy的形式接受它們。

我想出了這些生產規則：

的S - > SAB |電子

A - > XSY |電子

乙 - > YSX |電子

我正在創建分析樹，但我不完全理解。這是我做了什麼

         S 
           /| \ 
            S A B 
           // | \ \ 
           e x S y e 
            /| \ 
            S A B 
           // | \ \ 
           e x S y e 
             | 
             e 

如果我理解正確以上分析樹代表XYXY ....等等一個，如果我繼續

請問這個代表XXYY？

它如何表示xxyxyy？

這是我不理解......

Answer 1

首先，我不知道什麼是對樹正確的閱讀順序 - 我想這是按順序，因爲它通常是與幾乎所有（比較the Wikipedia article on tree traversals）但是我並不完全確定這是正確的。 （如果這是錯誤的，你會想要不同的樹，但想法應該翻譯。）

在那個閱讀下，你的示例樹代表xxyy。通過進一步替代S-A-S-A ......最下面的ε ......鏈，你會得到一個任意的xx…yy鏈。

爲了表示xy…xy，你會交替擴大A S和B s到xSy或ySx，那就是：S → SAB，然後B → ε和A → xSy;在下一層再次展開S → SAB，但是現在做A → ε和B -> ySx;根據需要繼續。一個例子：

  S 
      /|\ 
     /| \ 
     S A B 
     //|\ \ 
     ε/| \ ε 
     x S y 
      /|\ 
     /| \ 
     S A B 
     // /|\ 
     ε ε/| \ 
      y S x 
       | 
       ε 

這應該與xyxy，並且可以再次在底部被擴展爲更長的序列。

爲了節省空間，我將調用解析樹中「root」的最長路徑。 （對於這裏的簡單例子，所有的「脊柱」路徑都是方便的終端符號，所以這些樹的描述是獨一無二的（足夠的）。通常，「側路徑」更復雜，所以這個定義通常是無用的。 ，它可以很好地工作。）

對於這裏繪製的樹，其「脊柱」將是SASBSε（只是讀中間）。擴展任意嵌套，這將成爲(SASB)*(SA)?Sε。

上面繪製的樹有「spine」SASASε，對於任意長的xxx…yyy序列，您會得到(SA)*Sε。

xxyxyy很容易用同樣的方法描述：它的「脊椎」是SASASBSε。

一般（這個語法），因爲這是「逆鏡像」任意序列（下半年扭轉了上半年與X/Y交換 - 即x|y，xyx|yxy，xxy|xyy，...），可以構造這個「脊柱」只取上半部分，並擴大了x → SA,y → SB並且當你到達中間時加入Sε。 （當然，對於像xxyyyx這樣的更復雜的模式，這種方式會失敗，尋找一種方法來快速爲這些不對稱模式提供一棵樹，作爲讀者的練習;-)）