如何解決這個模糊的語法？

我寫了這個語法：如何解決這個模糊的語法？

expr  : multExpr (('+' | '-') multExpr)*; 
multExpr : atom (('*' | '/') atom)*; 
atom : INT | FLOAT | ID | '(' expr ')'; 
condition : cond ('or' cond)*; 
cond : c1 ('and' c1)*; 
c1  : ('not')? c2; 
c2  : '(' condition ')' | boolean; 
boolean : expr (relop expr | ²) | 'true' | 'false'; 
relop : '<' | '<=' | '>' | '>=' | '==' | '!=';

我已經省略了INT，FLOAT，ID的詞法規則，因爲它是顯而易見的。

問題是C2規則，它是模糊的，因爲「（」，我找不到解決方案，你可以給我一個解決方案嗎？

來源

2012-02-15 nafiseh

什麼是超級腳本'2'在'boolean'做什麼？ – 2012-02-15 20:21:44

爲什麼不能簡單地做：

expr  : orExpr; 
orExpr : andExpr ('or' andExpr)*; 
andExpr : relExpr ('and' relExpr)*; 
relExpr : addExpr (relop addExpr)?; 
relop  : '<' | '<=' | '>' | '>=' | '==' | '!='; 
addExpr : multExpr (('+' | '-') multExpr)*; 
multExpr : unaryExpr (('*' | '/') unaryExpr)*; 
unaryExpr : 'not'? atom; 
atom  : INT | FLOAT | ID | 'true' | 'false' | '(' expr ')';

單數not通常比您現在要做的要高。

這將允許使用像42 > true這樣的表達式，但在走AST /樹時檢查這樣的語義會出現。

編輯

輸入"not(a+b >= 2 * foo/3.14159) == false"現在將解析像這樣（忽略空格）：

enter image description here

如果你設置輸出到AST和一些樹改寫運營商混合（ ^和!）：

options { 
    output=AST; 
} 

// ... 

expr  : orExpr; 
orExpr : andExpr ('or'^ andExpr)*; 
andExpr : relExpr ('and'^ relExpr)*; 
relExpr : addExpr (relop^ addExpr)?; 
relop  : '<' | '<=' | '>' | '>=' | '==' | '!='; 
addExpr : multExpr (('+' | '-')^ multExpr)*; 
multExpr : unaryExpr (('*' | '/')^ unaryExpr)*; 
unaryExpr : 'not'^ atom | atom; 
atom  : INT | FLOAT | ID | 'true' | 'false' | '('! expr ')'!;

你會得到：

enter image description here

來源

2012-02-15 20:27:24

這適用於條件表達式，但我使用expr（在你的語法中：addExpr）作爲數學的東西，那麼我應該定義一個單獨的expr，我認爲這個。另一件事，你已經定義了unaryExpr，但沒有使用它。 – nafiseh 2012-02-15 20:36:45

，謝謝你的解決方案是正確的，我認爲，但我在想，使用句法謂詞是這樣明智的：c2：（'（'atom''''atom）*（（'+'|' - '）atom （'*'atom）*）*'）'）=> boolean | '（'condition'）' – nafiseh 2012-02-15 21:09:59

@nafiseh，我的觀點是：如果可以，儘可能避免謂詞。我知道，有時候你需要它們，但我更傾向於更寬鬆地構造AST，然後在稍後階段驗證AST的語義結構：它使語法對眼睛更加友好！ :) – 2012-02-15 21:13:08

無法定義C1作爲以下？

要解決這個問題

('not')? (('(' condition ')') | boolean)

來源

2012-02-15 19:58:14

這對於'atom'規則來說還是不明確嗎？ – Bill 2012-02-15 20:00:34

不，問題依然存在，如果布爾變爲expr，則expr轉到multExpr，然後是atom，然後是'（'expr'）'。 – nafiseh 2012-02-15 20:07:53

一種方法是將它拆分成兩套詞法規則和順序將其應用到輸入（一個用於數學的東西，其他的布爾）

來源

2012-02-15 19:58:58 Bill

所以你的意思是我不應該從布爾再去expr？ – nafiseh 2012-02-15 20:10:27

取決於您試圖實現的目標。你可以將它們分開並創建一個booleanexpr，而不是重用expr。如果你能列出一些有效的輸入樣本，這將是有幫助的。例如，「true和（4 + 3）/ 4」是否是一個有效的表達式？ – Bill 2012-02-15 20:26:56

是的，那麼它就像Bart所說的那樣，我需要定義兩種類型的表達式。實際上我對整個語言都有語法，我也有數學表達式。 – nafiseh 2012-02-15 20:40:14

您的問題從一個事實，即「（」可無論是c2第一選擇或最後的選擇開始莖。舉例來說，給定像((x+y) > (a+b))這樣的輸入，第一個開放參數是c2的開始，但第二個是的開始。 [編輯：而解析器沒有指示要走哪個路，直到稍後的任意點 - 例如，它不知道第一個開放paren是c2的開始，直到它遇到>。例如，如果這是一個*代替，那麼無論是開括號將是開始的時候也。]

一種可能的方式來處理這將是統一的算術和布爾表達式的規則，所以你只有一個規則爲'(' expression ')，而expression可能是算術或布爾值。然而，這經常會產生相當鬆散的輸入的副作用，算術和布爾表達式之間相對自由的轉換（至少在解析器級別 - 然後您可以在語義中儘可能嚴格地執行類型）。

編輯：帕斯卡，例如，規則運行像這樣（簡化一點點）：

expression: simple_expression (rel_op simple_expression)* 

simple_expression: ('+' | '-')? term (('+' | '-' | 'or') term)* 

term: factor (('/' | '*' | 'div' | 'mod' | 'and') factor)* 

factor: constant | variable | function_call | '(' expression ')' | 'not' factor

來源

2012-02-15 20:28:54

是的，我認爲我必須這樣做，並且有一個問題，一些知名的語言如java，pascal等如何解決這個問題？他們的語法是否像這樣行事？還是他們使用不同的方法，如回溯和這樣的東西？ – nafiseh 2012-02-15 20:51:03

取決於語言。 Fortran使用寬鬆的規則和回溯。 Pascal使用了我上面概述的內容 - 所有表達式的一組規則，布爾或其他。大多數人都喜歡帕斯卡。請參閱編輯答案 - 我已經添加了來自Pascal的規則。 – 2012-02-15 21:04:41

如何解決這個模糊的語法？

回答

相關問題