我正在為 Yacc 中的一種玩具語言（與 Go 打包的語言）編寫語法，并且由于以下偽問題，我有一個預期的 shift-reduce 沖突。我必須將問題語法提煉成以下內(nèi)容。start: stmt_listexpr: INT | IDENT | lambda | '(' expr ')' { $$ = $2 }lambda: '(' params ')' '{' stmt_list '}'params: expr | params ',' exprstmt: /* empty */ | exprstmt_list: stmt | stmt_list ';' stmt一個 lambda 函數(shù)看起來像這樣：map((v) { v * 2 }, collection)我的解析器發(fā)出：沖突：1班次/減少給定輸入：(a)expr它按'(' expr ')'規(guī)則正確解析。但是，如果輸入：(a) { a }（這將是標識函數(shù)的 lambda，返回其輸入）。我得到：語法錯誤：意外的“{”這是因為當(a)被讀取時，解析器選擇將其歸約為'(' expr ')'，而不是將其視為'(' params ')'。鑒于這種沖突是一個減少而不是減少的沖突，我假設這是可以解決的。我只是不知道如何構(gòu)建語法來支持這種語法。編輯 | 這很難看，但我正在考慮定義一個標記，以便詞法分析器可以識別 ')' '{' 序列并將其作為單個標記發(fā)送以解決此問題。編輯 2 | 實際上，更好的是，我會讓 lambdas 需要語法->(a, b) { a * b}中的語法，但是讓詞法分析器發(fā)出->而不是在實際的源代碼中。
2 回答
慕勒3428872
TA貢獻1848條經(jīng)驗 獲得超6個贊
你的分析確實是正確的；盡管語法沒有歧義，但解析器不可能在輸入縮減為( <expr>和前瞻的情況下)決定是否應在移動 the 之前將其expr縮減為，或者是否應將其作為 a 的一部分進行移動。如果下一個標記可見，則可以做出決定，因此語法 LR(2) 超出了 go/yacc 的權(quán)限。params))lambda
如果您使用的是 bison，您可以通過請求 GLR 解析器輕松解決此問題，但我不相信 go/yacc 提供該功能。
該語言有一個 LR(1) 語法（對于 的任何值，總是有一個 LR(1) 語法對應于任何 LR(k) 語法k），但是手寫相當煩人。LR(k) 到 LR(1) 轉(zhuǎn)換的基本思想是通過將 k-1 個上下文標記累積到每個產(chǎn)生式中來將減少決策 k-1 個標記向前移動。因此，在k2 的情況下，每個產(chǎn)生式 P:N → α將被替換為 each in和 each in 的產(chǎn)生式。[見注 1] 這會導致任何非平凡語法中的非終結(jié)符出現(xiàn)相當大的爆炸。TNU → Tα UTFIRST(α)UFOLLOW(N)
與其追求這個想法，讓我提出兩個更簡單的解決方案，您似乎都非常接近這兩個解決方案。
首先，在您提出的語法中，問題實際上只是當兩個標記為){. 這可以很容易地在詞法分析器中檢測到，并導致一個仍然是 hacky 但更簡單的 hack 的解決方案：){作為單個令牌返回。您需要處理中間的空格等，但它不需要在詞法分析器中保留任何上下文。這有額外的好處，您不需要將其定義params為exprs 列表；它們可以只是一個列表IDENT（如果相關的話；評論表明它不是）。
我認為更簡潔的替代方法是擴展您似乎已經(jīng)提出的解決方案：接受太多并拒絕語義操作中的錯誤。在這種情況下，您可能會執(zhí)行以下操作：
start:
stmt_list
expr:
INT
| IDENT
| lambda
| '(' expr_list ')'
{ // If $2 has more than one expr, report error
$$ = $2
}
lambda:
'(' expr_list ')' '{' stmt_list '}'
{ // If anything in expr_list is not a valid param, report error
$$ = make_lambda($2, $4)
}
expr_list:
expr | expr_list ',' expr
stmt:
/* empty */ | expr
stmt_list:
stmt | stmt_list ';' stmt
筆記
這只是一個大綱；完整的算法包括恢復原始解析樹的機制。如果k大于 2 則TandU是字符串 the and集合。FIRSTk-1FOLLOWk-1
夢里花落0921
TA貢獻1772條經(jīng)驗 獲得超6個贊
如果確實是 shift-reduce 沖突，并且您只需要 shift 行為，那么您的解析器生成器可能會為您提供一種更喜歡 shift 與 reduce 的方法。當 if 語句也可以是語句時，這是經(jīng)典地解決“if-then-stmt”和“if-then-stmt-else-stmt”的語法規(guī)則沖突的方法。
見http://www.gnu.org/software/bison/manual/html_node/Shift_002fReduce.html
您可以通過兩種方式獲得這種效果： a) 依靠解析引擎的意外行為。如果 LALR 解析器首先處理移位，然后在沒有移位的情況下進行歸約，那么您將免費獲得這個“首選移位”。解析器生成器所要做的就是構(gòu)建解析表，即使檢測到?jīng)_突也是如此。b) 強制執(zhí)行意外行為。設計（或獲?。┙馕銎魃善饕越邮堋案矚g在令牌 T 上移位”。然后可以抑制歧義。仍然必須像 a) 那樣實現(xiàn)解析引擎，但這很容易。
我認為這比濫用詞法分析器制作奇怪的標記更容易/更干凈（而且這并不總是有效）。
顯然，您可以偏愛減少以將其轉(zhuǎn)向其他方式。通過一些額外的黑客攻擊，您可以使 shift-vs-reduce 特定于發(fā)生沖突的狀態(tài)；您甚至可以使其特定于一對沖突的規(guī)則，但現(xiàn)在解析引擎需要保留非終結(jié)符的偏好數(shù)據(jù)。那仍然不難。最后，您可以為每個非終結(jié)符添加一個謂詞，當即將發(fā)生移位減少沖突時調(diào)用該謂詞，并讓它提供一個決定。
關鍵是您不必接受“純” LALR 解析；如果您愿意稍微修改解析器生成器/引擎，您可以通過多種方式輕松彎曲它。這為了解這些工具的工作原理提供了一個很好的理由；那么你就可以濫用它們來謀取利益。
- 2 回答
- 0 關注
- 187 瀏覽
添加回答
舉報
0/150
提交
取消