負前瞻分析算法

Question

考慮語法這樣的規則的LR-家庭解析生成器（例如YACC，野牛等）：

Nonterminal : [ lookahead not in {Terminal1, ..., TerminalN} ] Rule ; 

這是一個普通的規則，不同之處在於它有一個限制：用此規則生成的短語不能以Terminal1, ..., TerminalN開頭。 （當然，這個規則可以用一套通常的規則來代替，但它會導致更大的語法）。這對解決衝突很有用。

問題是，LR表構造算法是否存在對這種限制的修改？在我看來，這樣的修改是可能的（如優先關係）。

當然，它可以在運行時進行檢查，但我的意思是編譯時檢查（這是在構建分析表，如%prec進行檢查%left，%right和%nonassoc指令在YACC-compartible發電機。）

Answer 1

我不明白爲什麼這不應該是可能的，但我也沒有看到明顯的原因，爲什麼它會有用。你有沒有一個例子？

最簡單的方法是做圓括號裏提到的語法轉換。這會產生更大的語法，但不會人爲地增加LR狀態的數量。

基本變換，只用位的揮手：

對於任何生產與終端限制：

• 如果生產具有非空的非端開始，更換非終端與終端限制版本。

• 如果生產與終端限制列表中的終端開始，除去生產

• 如果生產與終端不在終端限制列表，無需更改啓動。

如果生產具有可空非終端開始，你必須創建的兩個版本可空非終端，其中一個總是空，而另一個是不可爲空;然後創建兩個版本的製作，一個從每個新的非終端開始。然後應用上述變換，但解釋「開始於」意味着「在任何始終爲空的非終端之後開始」。

實際上您並不需要修改語法，因爲上述轉換可以在底層SLR機器的構建過程中動態完成，至少對於LR（0）和LALR（1）構造而言。