衝突在分析一組表達式

的，我想分析一組表達式：R[3]C，R[2]C，R[3]C-R[2]C ...有衝突，我不能解決... ...衝突在分析一組表達式

這裏是lexer.mll部分：

rule token = parse 
    | 'R'   { R } 
    | 'C'   { C } 
    | "RC"   { RC } 
    | ['0'-'9']+ as lxm { INTEGER (int_of_string lxm) } 
    | '+'   { PLUS } 
    | '-'   { MINUS } 
    | '['   { LBRACKET } 
    | ']'   { RBRACKET } 
    | eof   { EOF } 
    ...

的parser.mly的一部分：

main: 
    e_expression EOF    { $1 }; 

e_expression: 
| ec = e_cell { EE_rc (Rc.Cell ec) } 
| e_expression MINUS e_expression { EE_string_EEL ("MINUS", [$1; $3]) } 

e_cell: 
| R LBRACKET r = index RBRACKET C c = index { (Rc.I_relative r, Rc.I_absolute c) } 
| R LBRACKET r = index RBRACKET C { (Rc.I_relative r, Rc.I_relative 0) } 

index: 
| INTEGER { $1 } 
| MINUS INTEGER { Printf.printf "%n\n" 8; 0 - $2 }

此代碼好奇地不與合作，這裏是parser.conflicts，我真的不明白。

如果我評論在e_cell行線| R LBRACKET r = index RBRACKET C c = index ...，代碼可以解析R[3]C-R[2]C，其中3和2是index，`R[3]C和R[2]C是e_cell和R[3]C-R[2]C是e_expression。

任何人都可以幫忙嗎？

來源

2013-07-23 SoftTimur

所以這個問題似乎是，當它看到a後面的「 - 」標記時，解析器不確定它是在創建索引，還是在分離兩個表達式。

即當語法分析器到達R [3] C-時，它不確定是否需要等待INTEGER完成e_cell並減少或立即減少並開始在另一個e_expression上工作。

解決此問題的最佳方法可能是將負整數代碼移入詞法分析器。我沒有一個ocamllex安裝方便，但我想改變

['0'-'9']+

到

'-'? ['0'-'9']+

會的工作，然後從指數的負整數情況下（這顯然會導致與問題printf語句，但是你可以使內部邏輯更復雜來解決這個問題。

來源

2013-07-23 22:11:35 MWB

謝謝，這工作......但我認爲解析器足夠智能** **期待**，得知'等待INTEGER完成e_cell'在我們的例子中是不可能的，並且'現在減少開始在另一個e_expression上工作是它應該做的... – SoftTimur

我會說它可能是LALR（1）而不是LALR（*），在這種情況下它可能無法向前看得遠遠不足以消除歧義因爲它需要兩個令牌來確定它（MINUS和下面的INTEGER或R） – MWB

你的語法不是LALR(1)。事實上，它甚至不是LR(1)。

考慮以下兩個有效e_expression S：

R[1]C-R[2]C 
R[1]C-1-R[2]C

在第一種情況下，我們已經轉移了C後，我們會得出如下：

R [ index ] C -R[2]C

，我們會再希望它減少：

e_cell -R[2]C

並再次減少到

e_expression -R[2]C

然後

e_expression - e_expression

在第二種情況下，我們會得到：

R [ index ] C -1-R[2]C

然後

R [ index ] C - 1-R[2]C 
R [ index ] C index -R[2]C 
e_cell -R[2]C

（在這一點上，我們」我已經達到了與第一個輸入類似的位置，所以我會留下下一個st EPS）。

所以，當我們轉移C，超前爲-，我們需要：

減少R [ index ] C到e_cell，或
移-，使R [ index ] C -

我們不能分辨沒有一個廁所頭部：以下標記必須爲R（案例1）或INTEGER（案例2）。

所以我們可以說語法是LALR（2），除了有關負號的另一個移位 - 減少衝突使得語法模糊不清，因此對任何k都不是LALR（k）。這可能是因爲你已經處理了這個一個使用運算符優先級的聲明，但以防萬一：

假設你已經達到：

e_expression - e_expression

和超前是-。現在，它可以減少e_expression - e_expression到e_expression，然後轉移-，導致：

e_expression -

或者，它可能只是轉移了-：

e_expression - e_expression -

無論我們多麼向前背景下閱讀，這是不可能的在這兩者之間做出決定，因爲它們都導致有效的分析。第一個解析將使-左結合，第二個結合右結合。

如果你不與優先級聲明解決這個問題，你可以選擇完全下列操作之一，而不是e_expression: e_expression MINUS e_expression：

e_expression: e_cell MINUS e_expression 
e_expression: e_expression MINUS e_cell

現在，如何解決原有問題:)

的最簡單的解決方案，如果在-1可以被認爲是一個負整數的一部分，是讓詞法分析器處理它。然後解析器將不會在R[-1]C-1中看到MINUS，因此它不會嘗試減少R[-1]C。

另一種解決方案是使用GLR解析器（顯然有一個用於OCaml，但我對此一無所知）。

最後，有可能機械地創建一個LR（2）語法，給定一個LR（2）語法，以及一個提取原始語法分析樹的機制。由此產生的語法通常會臃腫並且很難手寫，但翻譯可以自動完成。不幸的是，我不知道任何這樣做的OCaml工具。基本思想是將每個非終端分成一組成對的新終端。您可以輕鬆地將所有現有規則擴展到新的非終結點集合中。現在，由於每個非終結符有效地包含一個前瞻符號，所以一個單一符號前瞻等價於原始語言中的雙個符號前瞻。

來源

2013-07-24 06:29:34 rici

衝突在分析一組表達式

回答

相關問題