在我的語法中解決轉換 - 減少衝突的問題

我試圖用Irony編寫一個小解析器。不幸的是，我得到了一個「減少衝突」的衝突。文法不是我的強項，我只需要完成這一件小事。這是產生錯誤的簡化文法：在我的語法中解決轉換 - 減少衝突的問題

ExpressionTerm := "asd" 
LogicalExpression := 
    ExpressionTerm | 
    LogicalExpression "AND" LogicalExpression | 
    LogicalExpression "OR" LogicalExpression

「shift-reduce衝突」是什麼意思，我該如何解決它？我認爲這意味着我的語法是模糊的，但我不能充分扭曲我的邏輯來看看如何。

加：澄清 - 「asd」只是一個字符串「asd」。因此，我想到的是，下面的表達式是由這個語法解析：

asd 
asd AND asd 
asd AND asd OR asd 
asd OR asd AND asd OR asd

新增2：忘了說了，語法的根源是LogicalExpression。

添加了3：啊，我明白了！歧義是因爲喜歡

asd AND asd OR asd

的表達可以有兩種不同的解釋：

(asd AND asd) OR asd 
asd AND (asd OR asd)

但我怎麼能解決這個問題？好的，我可以把AND和OR中的一個比另一個更強大（無論如何我都會這樣做）。但是現在我發現即使只有一個操作員也會出現錯誤。換句話說，這也產生了同樣的錯誤：

LogicalExpression := "asd" | LogicalExpression "OR" LogicalExpression

在這種情況下，我想這一點：

asd OR asd OR asd

被解析到這一點：

(asd OR asd) OR asd

什麼是無曖昧的做法呢？

加了4個： Got it！

LogicalExpression1 := LogicalExpression1 "OR" LogicalExpression2 | LogicalExpression2 
LogicalExpression2 := LogicalExpression2 "AND" LogicalExpression3 | LogicalExpression3 
LogicalExpression3 := "NOT" LogicalExpression4 | LogicalExpression4 
LogicalExpression4 := "asd" | "(" LogicalExpression1 ")"

這將解析所有布爾表達式，運算符優先級爲NOT-> AND-> OR。「asd」可以替換爲用於您的術語的表達式。

來源

2009-05-26 Vilx-

嘿，想起來了，我開始記住這個我在大學期間的模式。：D –

如果只使用單個預測，則語法不明確。爲了說明，什麼是「asd」？它是ExpressionTerm還是更長期的？這是轉變 - 減少衝突。我懷疑這裏也有減少衝突的衝突。

大多數LL（1）/ LALR（1）生成器將通過優先運算符提供一些方法來處理shift-reduce衝突。大多數人也會在出現移位減少衝突時默認最長序列，因此往往這些可以被忽略（經過一些詳細審查後）。（在這種情況下，您可能需要將單個詞移到底部才能正常運行）。

來源

2009-05-26 12:41:07 leppie

「asd」只是一個字符串「asd」。 –

我還是不明白。在這種情況下，AND和OR應該具有相同的優先級。 –

使用1個字符的lookahead，您可以忘記AND和OR。衝突更早:) – leppie

Shift-Reduce衝突意味着您的語法不明確。使用遞歸規則，標記「asd」可能被解釋爲ExpressionTerm或LogicalExpression的一部分，解析器無法確定哪個。需要一個額外的規則來打破平局。

來源

2009-05-26 12:45:25 dwc

當談到解析器時，減少衝突是讓你的大腦難以接受的難題之一。說明衝突的最簡單方法是在這個僞代碼中：

if (a) then 
    if (b) then 
    printf('a + b'); 
    else 
    print('this could be a + !b or !a');

else語句可以綁定到第一個或第二個if。在模糊語法的情況下，您通常會定義一個值來指示語法中預期的移位減少警告的數量。

或者，您可以使用LL（k）或LL（*）解析器。這些類型的解析器沒有移位/減少歧義。根據您的應用程序，它們可能比LALR（1）解析器更容易或更難。

來源

2009-06-04 01:16:17 brianegge

語法是LL(1)或LALR(1)模糊的，因爲ASD令牌可以在ExpressionTerm被取代，也LogicalExpression扁平化語法規則來解決移進/歸約衝突

來源

2013-09-08 13:22:16

在我的語法中解決轉換 - 減少衝突的問題

回答

相關問題