如何將此語法轉換爲LR（1）？

我有一個LR（1）衝突的語法，我無法解決;但是，語法應該是明確的。我將首先用五個令牌簡化語法來演示問題：(,),{},,和id。如何將此語法轉換爲LR（1）？

的EBNF是這樣的：

 args = (id ',')* 

expression = id 
      | '(' expression ')' 
      | '(' args ')' '{}'

語法是明確的，需要前瞻的最多兩個令牌。當(移位時，只有五種可能性：

(→重複。
)→減少爲'(' args ')'。
id)不是{}→縮小爲'(' expression ')'。
id){}→降低作爲'(' args ')' '{}'
id,→降低作爲'(' args ')' '{}'（最終）。

一個天真的翻譯產生以下結果（和conflicts）：

formal_arg: Ident 
       {} 

    formal_args: formal_arg Comma formal_args 
      | formal_arg 
      | /* nothing */ 
       {} 

     primary: Ident 
      | LParen formal_args Curly 
      | LParen primary RParen 
       {}

所以，語法要求先行決定的最多三個令牌。我知道一個LR（3）語法爲can be transformed LR（1）語法。

但是，我不太瞭解如何在這種特殊情況下進行轉換。請注意，上面的簡化語法是從larger body of code中提取的;特別是有可能變換primary而不碰expr以及上述所有內容？

來源

2013-06-30 whitequark

我提供了一個解決方案，這裏的問題與此非常相似：Is C#'s lambda expression grammar LALR(1)?。其基本思想是將(id)與其他兩種可能性分開（(expr_not_id)和(list_at_least_2_ids)）。那麼關於如何減少(id)的決定可以推遲到先行令牌可用（在你的情況下，{，假設這是足夠的）。

不幸的是，儘管將expr轉換爲expr_not_id非常簡單且幾乎是機械的，但它肯定會涉及大量的製作。另外，它有點難看。所以它不能解決你在最後一句中提出的問題。我並不認爲有可能在不碰expr的情況下轉換primary，但我之前感到驚訝。

（另一個明顯的解決方案，因爲語法其實明確的，就是用一個GLR分析器生成，但我不相信你所使用的解析器發電機具有該功能。）

來源

2013-06-30 03:40:32 rici

事實上我剛剛得出了和你一樣的結論。然而，我的解析器生成器（menhir）具有更高階的規則，所以我可以讓它爲我做出咕嚕的工作。我可能會自己回答這個問題（如果它適用於我），抱歉不接受！ – whitequark

最有趣的部分是我知道你鏈接到的問題的作者。 – whitequark

我剛剛與你的轉換一起工作，雖然需要一套奇怪的語法轉換。真棒。 – whitequark

如何將此語法轉換爲LR（1）？

回答

相關問題