在野牛，我怎麼能保留一個非終端的結合？

我有以下的野牛語法片段：在野牛，我怎麼能保留一個非終端的結合？

binary_op:   BINARY_OP 
        { 
         ... 
        } 
        | '|' %prec BINARY_OP 
        { 
         ... 
        } 
; 

non_keyword_expr: non_keyword_expr binary_op non_keyword_expr %prec BINARY_SEND_PREC %dprec 2 
        { 
         ... 
        } 
;

|在我的語法已經超載的意思，所以我不能只是從我的詞法分析器返回它的令牌BINARY_OP。這可能是取決於上下文的不同標記。

如果我用這個作爲我的輸入：

4 OR 5 OR 6

我可以成功地解析它（或識別爲詞法分析器BINARY_OP令牌）。

但是，如果我的輸入是這樣的：

4 | 5 | 6

我得到一個模棱兩可的語法錯誤。（該|沒有被確認爲左結合）

我怎樣才能得到binary_op是內non_keyword_expr左結合的？關於binary_op的第二條規則的%prec聲明似乎沒有效果。

編輯：這是一個GLR分析器

來源

2014-05-16 nielsbot

答案很簡單：你不能。優先級（和關聯性）僅適用於製作（左側）和終端（右側）。它們不適用於非終端。

這不是一個任意的決定;這是野牛處理轉換/減少衝突的方式所固有的。在每一個解析步驟中，先行令牌（終端）必須最終被移位，但是有可能在終端被移位之前有可能減少產量。如果不立即執行減少，它將不會執行。 LR（1）語法允許解析器基於當前解析堆棧和先行令牌來決定是應該執行縮減還是應當立即移位先行令牌。如果兩種行爲都是可能的，那麼這個語法就被說成有一個轉換/減少的衝突，並且嚴格來說不是LR（1）。

優先和關聯規則用於解決移位/減少衝突。製作可能有一個隱含或顯式的優先級：明確的優先級由%prec聲明提供;否則使用生產中最後一個終端的優先級。在發生轉換/減少衝突的情況下，可以減少的生產的優先級與可能被轉移的先行終端的優先級進行比較，並且優先級更高的優先級獲勝。而已。優先權不被保留或繼承。事實上，說比較優先級是不準確的，因爲這在解析過程中不會發生;解析器具有一個動作或轉換表，它定義了在特定堆棧配置（「狀態」）和先行令牌的情況下要執行的操作，並且在解析器生成時使用優先級信息來填充動作表中的條目否則將會模棱兩可。

在生產

binary_op: '|' %prec BINARY_OP

的%prec聲明是沒用的，因爲binary_op必須立即減少的情況;它不能參與轉移/減少衝突。轉換/減少衝突來自non_keyword_expression生產，該生產標記有（不同的）%prec聲明，並且該聲明將用於該生產。

non_keyword_expression的生產沒有終端，所以它也沒有隱式優先。這通常不是你想要的，以及使用作品的喜歡：

binary_op: '|' | "OR" ;

是不使用優先級的真正兼容解決解析衝突。

注1：如果您要求使用GLR解析器，這並不完全正確。 GLR解析器可以執行shift和reduce操作，因爲它（有效地）同時維護許多解析器狀態。最終，除了這些國家之外的所有國家都必須被淘汰。否則，解析是不明確的。 GLR語法分析程序的使用優先級（和%prec聲明）與非GLR語法分析程序的使用方式完全相同;優先級消除的解析器動作實際上被消除並且不會導致並行狀態。但是，GLR解析器也可以處理減少/減少衝突，其中有兩種可能的減少（可能對同一個非終端）。這些衝突可以使用%dprec（「動態優先權」）聲明來解決。

來源

2014-05-16 20:23:09 rici

感謝您的答案。你在說'|'嗎？在我的語法中不是終端？混淆爲什麼它可以正常工作「OR」（令牌BINARY_OP）而不是'|' （隱含的令牌'|'）BINARY_OP的關聯性似乎成功連接到非終端binary_op ... – nielsbot

@nielsbot：對不起，我不是很清楚。我會編輯我的答案。但有一個問題：你使用GLR解析器嗎？（如果是這樣，你應該在你的問題中提及它，因爲它既不明顯也不共同。） – rici

是的，它是GLR。我的意思是補充，但忘了... – nielsbot

如果您可以指定終端'OR'和'|'等的關聯性並將它們的優先級設置爲相同，那麼存在這種問題的解決方法。與一對夫婦改變綴計算器例子可以解析這樣的輸入：

2 PLUS -3 TIMES 4^2 + 3

-43

的主要變化是這樣的：

%token PLUS 
%token TAKE 
%left '-' '+' PLUS TAKE 

... 

add:  '+' | PLUS; 
exp:  NUM       { $$ = $1;   } 
     | exp add exp  %prec '+' { $$ = $1 + $3; }

非終端的優先權將是對野牛恕我直言的一個有用的擴展。當非終端的前綴可以被移位時，它將允許用戶通過有利於減少來解決s/r衝突（並且當它可以被移動到具有優先級的非終端時可以有只有-可能有其他有效的理由轉移）。事實上，我發現這個問題，試圖實現一個Haskell風格的功能應用的語法即

x y z -> ((x y) z)

後卻因爲單獨一個終端也是有效這裏，減少了X/Y/Z到非終端是有效的。因此野牛會達到non-term_x non-term_y | z（|是堆棧/超前邊界）並且不知道是否減少到non-term_x_y或移位z。（類似的技巧幸運地在這裏工作）

我在野牛源中挖了一點，但我看不到一個簡單的方法來允許在非終端％prec。當s/r conficts被解決時，只有裁減規則是已知的，並且衝突的令牌要移位，其優先級被比較。你需要知道所有有效的移位原因，並且有辦法訪問衝突的移位規則，所以也許..您需要將可切換令牌分成與最終減少的規則相對應的組，然後比較規則的優先級。 Somethin我會看看有一天...

來源

2014-08-23 11:21:08 user3125280

在野牛，我怎麼能保留一個非終端的結合？

回答

相關問題