我正在決議一種沒有像;. 運算式被定義為最長的標記序列，因此5-5必須被決議為減法，而不是兩個陳述句（文字5后跟一元否定-5）。
我使用LALRPOP作為決議器生成器（盡管名稱是 LR(1) 而不是 LALR，afaik）。LALRPOP 沒有優先屬性，并且默認情況下不像 yacc 那樣更喜歡 shift 而不是 reduce。我想我了解如何通過構建規則“鏈”在 LR 語法中編碼常規運算子優先級，但我不知道如何將其應用于此問題。
預期的決議將是（括號中的單個陳述句）：
"5 - 5" → 5-5 instead of 5, -5
"5 (- 5)" → 5, -5
"- 5" → -5
"5 5" → 5, 5
如何更改語法以使其始終更喜歡更長的決議？
瀏覽谷歌結果的前幾頁以及堆疊溢位并沒有針對這個特定問題產生任何結果。大多數相關問題需要更多的前瞻性，否則結果是不允許沒有終止符的連續陳述句。
我創建了一個重現移位/減少沖突的最小示例語法（此語法中的陳述句只是一個運算式，在完整語法中還會有“if”、“while”等以及更多級別的運算子優先級，但是為簡潔起見，我省略了它們）。除了一元減號之外，原始語法中還存在其他沖突，例如print(5)，可以將其決議為識別符號print和帶括號的數字(5)或函式呼叫。可能會有更多這樣的沖突，但它們都有相同的潛在問題，即應該首選較長的序列，但兩者目前都是有效的，盡管只有第一個應該是。
為方便起見，我創建了一個repo（結帳和cargo run）。語法是：
use std::str::FromStr;
grammar;
match {
" ",
"-",
"(",
")",
r"[0-9] ",
// Skip whitespace
r"\s*" => { },
}
Expr: i32 = {
<l:Expr> " " <r:Unary> => l r,
<l:Expr> "-" <r:Unary> => l - r,
Unary,
};
Unary: i32 = {
"-" <r:Unary> => -r,
Term,
}
Term: i32 = {
Num,
"(" <Expr> ")",
};
Num: i32 = {
r"[0-9] " => i32::from_str(<>).unwrap(),
};
Stmt: i32 = {
Expr
};
pub Stmts: Vec<i32> = {
Stmt*
};
部分錯誤（完整錯誤資訊）：
/lalrpop-shift-repro/src/test.lalrpop:37:5: 37:8: Local ambiguity detected
The problem arises after having observed the following symbols in the input:
Stmt Expr
At that point, if the next token is a `"-"`, then the parser can proceed in two different ways.
First, the parser could execute the production at
/lalrpop-shift-repro/src/test.lalrpop:37:5: 37:8, which would consume
the top 1 token(s) from the stack and produce a `Stmt`. This might then yield a parse tree like
Expr ? Stmt
├─Stmt──┤ │
├─Stmt ─┘ │
└─Stmt ──────┘
Alternatively, the parser could shift the `"-"` token and later use it to construct a `Expr`. This might
then yield a parse tree like
Stmt Expr "-" Unary
│ ├─Expr───────┤
│ └─Stmt───────┤
└─Stmt ────────────┘
See the LALRPOP manual for advice on making your grammar LR(1).
uj5u.com熱心網友回復：
您將不得不面對的問題是如何處理函式呼叫。根據您的問題，我真的不能給您任何具體建議，因為您提供的語法沒有任何關于函式呼叫的預期語法的指示，但是print(5)作為有效陳述句的提示清楚地表明存在兩種不同的情況，即需要分開處理。
考慮：
5 - 5 One statement 5 ( - 5 ) Two statements
print(-5) One statement print - 5 Two statements (presumably)
a - 5 ???
如果編譯器知道a是函式還是變數，則可以解決第三個運算式的歧義（如果我們假設函式不是一等值，則print宣告無效）。但是決議器知道這一點的方法并不多，而且似乎都不太可能：
- 可能沒有任何用戶定義的函式。然后可以構建詞法分析器以識別類似識別符號的標記，這些標記恰好是內置函式（如
print），然后a(-5)將是非法的，因為a它不是內置函式。 - 函式和識別符號的名稱可能在詞法分析器可以檢測到的某些方面有所不同。例如，該語言可能要求函式以大寫字母開頭。我認為情況并非如此，因為您撰寫了
print而不是Print但可能存在其他一些簡單的區別，例如要求識別符號是單個字符。 - 函式必須在第一次使用函式之前宣告，并且決議器與詞法分析器共享符號表。 （我沒有為您正在使用的生成器搜索相當不充分的檔案來查看詞匯反饋是否實用。）
- 如果有一個可選的陳述句分隔符（例如 Lua），那么您可以簡單地要求以括號開頭的陳述句（通常是非常罕見的情況）明確分隔，除非它們是塊中的第一個陳述句。或者可能有一個可選的關鍵字，例如
compute可以用作明確的陳述句啟動器，并且以括號開頭的陳述句需要使用它。我認為這兩種情況都不是，因為你可以用它來強制5 - 5被識別為兩個陳述句（5; -5或5 compute - 5。） - 再次基于
print(5)示例，另一個不太可能的可能性是函式呼叫使用與運算式分組不同的括號。在這種情況下，a[5]（例如）將是一個函式呼叫，a(5)并且明確地是兩個陳述句。
由于我不知道這里的確切要求，我將展示一個語法（在 yacc/bison 語法中，盡管它應該很容易翻譯），它試圖說明一個有代表性的示例。return除了運算式陳述句之外，它還實作了一個陳述句 ( )，運算式包括乘法、減法、否定和單引數函式呼叫。為了強制“貪婪”運算式，它禁止某些陳述句序列：
- 以一元運算子開頭的陳述句
- 如果前一個陳述句以識別符號結尾，則陳述句以左括號開頭。（這實際上要求在呼叫運算式中應用的函式是一個簡單的識別符號。沒有這個限制，幾乎不可能將兩個連續的括號運算式與單個函式呼叫運算式區分開來，然后您需要一些其他方法來消除歧義.)
這些規則很容易陳述，但實際的實作令人討厭地重復，因為它需要各種不同型別的運算式，這取決于運算式中的第一個和最后一個標記是什么，并且可能還有不同型別的陳述句，如果你有可能結束的陳述句帶著表情。( return x，例如。) ECMAScript 使用的形式在這里會很有用，但我懷疑你的決議器生成器沒有實作它——盡管它的宏工具可能會被用來達到那種效果，如果它帶有一些東西的話類似于檔案。沒有它，就會有很多重復。
在生成語法的模糊嘗試中，我使用了以下后綴：
_un/_pr/_oth：與一元/括號開始/其他令牌_id/_nid: 結束 / 不以 id 結尾
沒有后綴用于不同可能性的聯合。可能有比必要更多的單位生產。它還沒有經過徹底除錯，但它在一些測驗用例上作業（見下文）：
program : block
block_id : stmt_id
| block_id stmt_oth_id
| block_nid stmt_pr_id
| block_nid stmt_oth_id
block_nid : stmt_nid
| block_id stmt_oth_nid
| block_nid stmt_pr_nid
| block_nid stmt_oth_nid
block : %empty
| block_id | block_nid
stmt_un_id : expr_un_id
stmt_un_nid : expr_un_nid
stmt_pr_id : expr_pr_id
stmt_pr_nid : expr_pr_nid
stmt_oth_id : expr_oth_id
| return_id
stmt_oth_nid : expr_oth_nid
| return_nid
stmt_id : stmt_un_id | stmt_pr_id | stmt_oth_id
stmt_nid : stmt_un_nid | stmt_pr_nid | stmt_oth_nid
return_id : "return" expr_id
return_nid : "return" expr_nid
expr_un_id : sum_un_id
expr_un_nid : sum_un_nid
expr_pr_id : sum_pr_id
expr_pr_nid : sum_pr_nid
expr_oth_id : sum_oth_id
expr_oth_nid : sum_oth_nid
expr_id : expr_un_id | expr_pr_id | expr_oth_id
expr_nid : expr_un_nid | expr_pr_nid | expr_oth_nid
expr : expr_id | expr_nid
sum_un_id : mul_un_id
| sum_un '-' mul_id
sum_un_nid : mul_un_nid
| sum_un '-' mul_nid
sum_un : sum_un_id | sum_un_nid
sum_pr_id : mul_pr_id
| sum_pr '-' mul_id
sum_pr_nid : mul_pr_nid
| sum_pr '-' mul_nid
sum_pr : sum_pr_id | sum_pr_nid
sum_oth_id : mul_oth_id
| sum_oth '-' mul_id
sum_oth_nid : mul_oth_nid
| sum_oth '-' mul_nid
sum_oth : sum_oth_id | sum_oth_nid
mul_un_id : unary_un_id
| mul_un '*' unary_id
mul_un_nid : unary_un_nid
| mul_un '*' unary_nid
mul_un : mul_un_id | mul_un_nid
mul_pr_id : mul_pr '*' unary_id
mul_pr_nid : unary_pr_nid
| mul_pr '*' unary_nid
mul_pr : mul_pr_id | mul_pr_nid
mul_oth_id : unary_oth_id
| mul_oth '*' unary_id
mul_oth_nid : unary_oth_nid
| mul_oth '*' unary_nid
mul_oth : mul_oth_id | mul_oth_nid
mul_id : mul_un_id | mul_pr_id | mul_oth_id
mul_nid : mul_un_nid | mul_pr_nid | mul_oth_nid
unary_un_id : '-' unary_id
unary_un_nid : '-' unary_nid
unary_pr_nid : term_pr_nid
unary_oth_id : term_oth_id
unary_oth_nid: term_oth_nid
unary_id : unary_un_id | unary_oth_id
unary_nid : unary_un_nid | unary_pr_nid | unary_oth_nid
term_oth_id : IDENT
term_oth_nid : NUMBER
| IDENT '(' expr ')'
term_pr_nid : '(' expr ')'
這是一個小測驗：
> 5-5
{ [- 5 5] }
> 5(-5)
{ 5; [~ -- 5] }
> a-5
{ [- a 5] }
> a(5)
{ [CALL a 5] }
> -7*a
{ [* [~ -- 7] a] }
> a*-7
{ [* a [~ -- 7]] }
> a-b*c
{ [- a [* b c]] }
> a*b-c
{ [- [* a b] c] }
> a*b(3)-c
{ [- [* a [CALL b 3]] c] }
> a*b-c(3)
{ [- [* a b] [CALL c 3]] }
> a*b-7(3)
{ [- [* a b] 7]; 3 }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/407373.html
標籤：