解釋有關活前綴

在厄爾曼的著作編譯器，在換擋減少解析，下面的活前綴的定義給出：解釋有關活前綴

「集，它可以在在堆棧上出現的右句型的前綴移降低解析器被稱爲可行前綴，一個可行前綴的等價定義是它是一個正確的句子形式的前綴，它不會繼續超越該句子形式最右邊句柄的右端，通過這個定義，總是可以添加終端符號添加到可行前綴的末尾以獲得正確的句子形式，因此，只要輸入到給定點的輸入部分可以縮減爲可行的前綴，顯然就不會出現錯誤。「

我無法理解這個定義。有人能用一個例子解釋可行前綴的含義嗎？
特別是，請解釋
的意思是「一個活前綴的等效定義是，它是對句型的前綴不會繼續過去那種句型的最右手柄的右端」

來源

2010-11-17 Happy Mittal

這只是顯示專家（書籍作者）如何使學習體驗如此複雜。他們似乎認爲簡潔的語言是可以理解的語言。 – Domi 2014-02-26 18:07:14

編輯（或實際上重寫）：您要求澄清的句子是一個主要的毛球！我需要對語言和自動機進行一點複習，以便自己挑選那個毛球。我發現these lecture notes在這方面非常有用。

它也不會讓它變得更容易，這些術語是以自頂向下擴展的形式定義的，而最右邊的派生通常用於自下而上的解析！

我將使用下面的表達式文法來說明：

 
    expr -> expr + term | term 
    term -> term * factor | factor 
    factor -> NUMBER | (expr)

甲右句型是句型其可以通過最右推導到達，這是描述重複的另一種方式自上而下只擴展最右端的非終結符號。這是一個最右推導，並在它的所有形式，因此右句型：一個句型的

 
    expr -> expr + term 
     -> expr + term * factor 
     -> expr + term * NUMBER 
     -> expr + factor * NUMBER 
     -> expr + NUMBER * NUMBER 
     -> expr + term + NUMBER * NUMBER 
     -> expr + NUMBER + NUMBER * NUMBER 
     -> term + NUMBER + NUMBER * NUMBER 
     -> NUMBER + NUMBER + NUMBER * NUMBER

甲前綴（無論是右或以其它方式）被輸入的序列將符號縮減爲零或更多的該句子形式的前導符號。空序列是每個句子形式的前綴，構成句式的符號的完整序列也是它的前綴。
A 簡單的短語是一個單一的非終結符號的擴展，它在句子形式中佔有一席之地。例如，term * factor是一個簡單的短語，因爲它是term的擴展，並且term本身發生在三個作品中。
句子形式的句柄是該形式中最左邊的簡單短語。（我承認，我覺得'句柄'這個詞在這裏有點混淆。）在最右邊的推導中，句柄很容易識別 - 這是由最近擴展的非終結符引起的符號序列。如果您正在使用shift-reduce解析器的方式進行自下而上的操作，那麼句柄就是這個簡單的短語，需要減少下一個。（從下往上，看着這些符號均減少，閱讀推導表格上面看到我的意思。）
一個活前綴右句型的是不超出一個前綴表單的句柄 - 換句話說，前綴是有效的，並且不包含可縮減的簡單短語，如果所述前綴延伸到句柄的末尾，則可能除了句柄本身。

從一個移位歸約解析器的角度來看，只要你有在堆棧上可行的前綴，你還沒有被迫要麼減少對堆棧的頂部（可能不完全）簡單的短語到一個新的非終結符，或者如果它不能被減少，就無法解析。如果移動下一個符號會導致除可行前綴之外的其他內容，那麼您必須在此時減少或失敗。

如果你解析上下文無關語言，還有一個比較方便的特性，隨着表驅動移位歸約解析器建設幫助：設定一個上下文無關語言的所有可行的前綴是本身是一種常用語言！因此，您可以構建一個識別可行前綴的常規語言的有限自動機，並使用它來確定何時移位以及何時減少。堆棧和有限狀態機的組合本質上是一個下推自動機，它正是需要識別上下文無關語言的自動機類。

來源

2010-11-17 07:09:56

檢查[this]（http://web.eecs.utk.edu/~bvz/cs461/notes/parsing.html）。點之前的項目部分表示可行的前綴。可行的前綴是一串語法符號，可以包含生產右側的第一部分。例如：a，aX，aXY和aXYb是生產A - > aXYb的可行前綴。 – Shashwat 2013-01-15 12:45:07

@Shashwat我相信這是解釋同樣事情的另一種方式：'aXYb'是一個簡單的短語，因爲它構成了製作的右側，而鏈接的筆記中的'點'實際上是一個表示進度點的光標通過潛在投入。我認爲討論單個生產的可行前綴是有意義的（並且在構造shift-reduce語法分析器的有限狀態機時有用），但是完成的shift-reduce分析器通常主要關注完整句法形式的可行前綴。 – 2013-01-15 23:19:48

考慮本書給出的語法（我在這裏重申它）

E -> E+T | T 
T -> T*F | F 
F -> (E) | id

是通過將E」增強 - 在它>電子

現在，在這個推導看看，

E' -> E 
    -> E+T 
    -> E+T*F

權利要求E + T *是一個可行的前綴

參數：這個派生是一個正確的句子形式& E + T *是它的前綴。手柄目前是T * F（如降低T * F至難道我們能達到開始符號&因此，一個成功的解析）

，因此，E + T *是一個可行的前綴，因爲它是一個前綴右句子形式&不會超過這個句子形式的最右邊的句柄。定義它:)

另一種方式是：

The prefixes of right sentential forms that can appear on the stack of a shiftreduce 
parser are called viable prefixes.

來源

2013-02-18 19:23:55 ak2

我認爲應該提供可行前綴的正式定義，以防萬一，如果有人發現它更容易理解（就像我）。

給定一個語法，我們說是一個活前綴如果存在一個最右推導

這樣。

Source。

來源

2014-12-25 22:35:05 newbie

解釋有關活前綴

回答

相關問題