有沒有辦法讓這個語法LALR（1）？

Question

我有規則的語法像這樣

A -> pq 
B -> pr 

Block -> { Astar Bstar } 

Astar -> Astar A 
     | epsilon 

Bstar -> Bstar B 
     | epsilon 

有什麼辦法把這個語法到LALR（1）？從我可以弄明白的，如果解析器在塊內看到p，就會出現轉換/消除衝突。

Answer 1

您的語言是正常的，相當於正則表達式\{(pq)*(pr)*\}。問題是，任何簡單的轉換到語法將需要兩個字符的前瞻，看看是否有該p

現在，經過一個q或r你有這個標記都yacc和parsing所以它不清楚你是否在尋找一個實際的答案是「你如何用yacc處理這個問題」或者一個理論答案「是否有這種語言的LALR（1）語法。」

爲實際的答案，解決的辦法是，你撐船 - 你移動的認可A和B到您識別字符序列pq和pr爲令牌A和B詞法分析器。由於lex/flex使用DFA並且回溯到最長的匹配標記，所以它們在這裏沒有任意的前瞻性問題。

對於理論上的答案，您需要轉換語法以消除對前瞻的需求。有問題的構建體是(pq)*(pr)*（括號是不相關的），其等效於p(qp)*(rp)*r | p(qp)*q | epsilon這表明一個語法，如：

Block -> { p Astar Bstar r } 
     | { p Astar q } 
     | { } 
A -> q p 
B -> r p 
Astar -> Astar A | epsilon 
Bstar -> Bstar B | epsilon 

另一種方法是unfactoring的star規則，使它們不匹配空字符串：

Block -> { Aplus Bplus } 
     | { Aplus } 
     | { Bplus } 
     | { } 
A -> p q 
B -> p r 
Aplus -> Aplus A | A 
Bplus -> Bplus B | B 

爲您提供了兩種截然不同的LALR（1）語法。

Answer 2

讓我們先看看爲什麼你會遇到LALR（1）衝突，然後看看我們是否可以重寫語法來使其成爲LALR（1）。

明白爲什麼語法不是LALR（1），讓我們開始通過計算LR（1）構式集語法：

(1) 
S'  -> .Block [$] 
Block -> .{ Astar Bstar } [$] 

(2) 
S'  -> Block. [$] 

(3) 
Block -> { . Astar Bstar } [$] 
Astar -> .Astar A [ }p ] 
Astar -> .epsilon [ }p ] 

(4) 
Block -> { Astar . Bstar } [$] 
Astar -> Astar .A [ }p] 
A  -> .pq [}p] 
Bstar -> .epsilon [ }p ] 
Bstar -> . Bstar B [ }p ] 

在這一點上，我們可以停下來，因爲我們有一個在符號p上的狀態（4）上移動/減少信念：你是否將p移到A -> .pq [ {p ]，或者你是否減少BStar -> .epsilon [ }p ]？由於在LR（1）語法中存在移位/減少衝突，所以語法根本不是LR（1），這意味着它不可能是LALR（1）（因爲每個LALR（1）語法也是LR （1）語法）。

從根本上說，這個問題是，當解析器看到一個p，它不能告訴它無論是在看一個A開始（這意味着它需要轉移的話），或者如果沒有更多A的左並且它正在查看B（意味着它需要減少Bstar -> epsilon）的開頭。

要解決這個問題，讓我們看看如果我們做一個小小的調整會發生什麼。我們遇到的問題是，解析器需要在看到p時立即確定是否轉移或減少。如果我們通過查看p以及後續字符給予時間推遲做出決定怎麼辦？要做到這一點，讓我們稍微改變你的語法重寫

Bstar -> epsilon 
Bstar -> Bstar B 

爲

Bstar -> epsilon 
Bstar -> B Bstar 

現在，解析器得到看更多的令牌決定做什麼之前。如果它看着pq，它知道它沒有看到任何與B有關的東西。如果它看到pr，它知道它正在查看B，因此可以開始製作第二類作品。讓我們看看會發生什麼我們的LR（1）規定，如果我們做到這一點：

(1) 
S'  -> .Block [$] 
Block -> .{ Astar Bstar } [$] 

(2) 
S'  -> Block. [$] 

(3) 
Block -> { . Astar Bstar } [$] 
Astar -> .Astar A [ }p ] 
Astar -> .epsilon [ }p ] 

(4) 
Block -> { Astar . Bstar } [$] 
Astar -> Astar .A [ }p] 
A  -> .pq [}p] 
Bstar -> .epsilon [ } ] 
Bstar -> . B Bstar [ } ] 
B  -> .pr [}] 

(5) 
Block -> { Astar Bstar . } [$] 

(6) 
Block -> { Astar Bstar } . [$] 

(7) 
A  -> p.q [}p] 
B  -> p.r [}] 

(8) 
A  -> .pq [}p] 

(9) 
B  -> pr. [}] 

(10) 
Bstar -> B . Bstar [ } ] 
Bstar -> . B Bstar [ } ] 
B  -> .pr [}] 

(11) 
B  -> p.r [}] 

請注意，我們原來的轉變/減少衝突已經消失，而這種新的語法不再有任何轉變/減少衝突的。而且，由於沒有任何一對具有相同核心的狀態，上述狀態集合也是我們在LALR（1）表中所具有的狀態集合。因此，上面的語法確實是LALR（1），我們根本沒有改變語法的含義。

希望這會有所幫助！