用antlr解析酷語，不能打印所需的輸出

Question

我是一名COOL（課堂面嚮對象語言）的編寫解析器/詞法分析器。 ü可以看到下面的鏈接語法：（本手冊的最後一頁）

http://theory.stanford.edu/~aiken/software/cool/cool-manual.pdf

我使用ANTLR寫這個計劃，並與下面的輸入，我希望下面的輸出：

輸入：

class Main inherits IO { 
    main(): Object {{ 
    x <- 2 + 3 *4; 
    }}; 
}; 

輸出：

1 
2 
3 
11 
6 
16 
27 
18 
27 
27 

，但我得到的輸出是：

1 
2 
3 
11 
6 
27 
16 
27 
18 
27 

，這裏是我的語法/詞法分析器代碼：

// parser 
grammar CA2; 

program : {System.out.println("1");} (classdef';')+ ; 
classdef : {System.out.println("2");} CLASS ID (INHERITS ID)? '{' (feature';')* '}' ; 
feature : {System.out.println("3");} ID OPENP (formal (','formal)*)? CLOSEP ':' ID '{' expr '}' 
     | {System.out.println("4");} ID ':' ID (POINTTOLEFT expr)? ; 
formal : {System.out.println("5");} ID ':' ID ; 
expr : {System.out.println("6");} ID POINTTOLEFT expr exprprime 
    | {System.out.println("8");} ID OPENP (expr (','expr)*)? CLOSEP exprprime 
    | {System.out.println("9");} IF expr THEN expr ELSE expr FI exprprime 
    | {System.out.println("10");} WHILE expr LOOP expr POOL exprprime 
    | {System.out.println("11");} '{' (expr';')+ '}' exprprime 
    | {System.out.println("12");} LET ID ':' ID (POINTTOLEFT expr)? (','ID ':' ID (POINTTOLEFT expr)?)* IN expr exprprime 
    | {System.out.println("13");} CASE expr OF (ID POINTTORIGHT expr ';')+ ESAC exprprime 
    | {System.out.println("14");} NEW ID exprprime 
    | {System.out.println("15");} ISVOID expr exprprime 
    /*| {System.out.println("16");} expr ADD expr 
    | {System.out.println("17");} expr SUB expr 
    | {System.out.println("18");} expr MULTIPLY expr 
    | {System.out.println("19");} expr DIV expr 
    | {System.out.println("20");} TILDA expr 
    | {System.out.println("21");} expr LARGERTHAN expr 
    | {System.out.println("22");} expr LARGEREQ expr 
    | {System.out.println("23");} expr EQUALS expr 
    | {System.out.println("24");} NOT expr 
    | {System.out.println("25");} OPENP expr CLOSEP 
    | {System.out.println("26");} ID 
    | {System.out.println("27");} INTEGER*/ 
    | {System.out.println("28");} STRING exprprime | mathex exprprime ; 
    /*| {System.out.println("29");} TRUE 
    | {System.out.println("30");} FALSE ;*/ 
exprprime : {System.out.println("7");} (('@'ID)?)'.'ID OPENP (expr (','expr)*)? CLOSEP exprprime | ; 
mathex : b ; 
b : {System.out.println("24");} NOT b | c ; 
cprime : {System.out.println("21");} LARGERTHAN d cprime 
     | {System.out.println("22");} LARGEREQ d cprime 
     | {System.out.println("23");} EQUALS d cprime | ; 
c : d cprime ; 
dprime : {System.out.println("16");} ADD e dprime 
     | {System.out.println("17");} SUB e dprime | ; 
d : e dprime ; 
eprime : {System.out.println("18");} MULTIPLY f eprime 
     | {System.out.println("19");} DIV f eprime | ; 
e : f eprime ; 
f : {System.out.println("20");} TILDA f | g ; 
g : {System.out.println("25");} OPENP mathex CLOSEP 
    | {System.out.println("26");} ID 
    | {System.out.println("27");} INTEGER 
    | {System.out.println("29");} TRUE 
    | {System.out.println("30");} FALSE ; 

//lexer 
TRUE : 'true' ; 
FALSE : 'false' ; 
INHERITS : 'inherits' ; 
CLASS : 'class' ; 
IF : 'if' ; 
THEN : 'then' ; 
ELSE : 'else' ; 
FI : 'fi' ; 
WHILE : 'while' ; 
LOOP : 'loop' ; 
POOL : 'pool' ; 
LET : 'let' ; 
IN : 'in' ; 
CASE : 'case' ; 
OF : 'of' ; 
ESAC : 'esac' ; 
NEW : 'new' ; 
ISVOID : 'isvoid' ; 
NOT : 'not' ; 
TILDA : '~' ; 
WHITESPACE : [ ' '|'\r'|'\n'|'\t']+ ->skip ; 
INTEGER : [0-9]+ ; 
ID : ['_'a-zA-Z][a-zA-Z0-9'_']* ; 
ADD : '+' ; 
MULTIPLY : '*' ; 
SUB : '-' ; 
DIV : '/' ; 
OPENP : '(' ; 
CLOSEP : ')' ; 
EQUALS : '=' ; 
LARGERTHAN : '<' ; 
LARGEREQ : '<=' ; 
POINTTOLEFT : '<-' ; 
POINTTORIGHT : '=>' ; 
STRING : '"'(~[\r\n])*'"' ; 

這是ANTLR的COOL語法的代碼版本。在主代碼中被註釋的部分被消除了（手段被模糊不清！）並且在第二部分（mathex規則）中被左遞歸釋放。

任何人都可以指出這是哪裏出錯，爲什麼我沒有得到所需的輸出？

在此先感謝！

Answer 1

除program中的操作外，您的每個println調用都會​​立即出現在語法中的令牌引用之前。很明顯，這意味着它們將按照令牌出現在文件中的順序執行。

您的預期輸出與實際輸出之間的第一次不匹配是線條16和27的反轉。只有當輸入中的+令牌出現在輸入中的2令牌之前時，纔會出現您的預期輸出，但顯然您可以看到情況並非如此。第二種不匹配是出於同樣的原因;具體而言，這是由於預期的輸出假定*令牌將在文法中比3令牌早出現。

---

我注意到您最初寫了左遞歸expr規則，包括在其內嵌入行動。以下信息與解決您的具體問題無關，但如果您決定取消註釋該代碼並使用expr的左遞歸表單，則需要了解以下信息。

考慮以下左遞歸規則，允許簡單添加標識符，並添加兩個嵌入式操作。

expr 
    : {a();} ID 
    | {b();} expr '+' ID 
    ; 

正如您可能已經發現的，該語法不會與ANTLR一起編譯。我們發現評估表達式{b();}在我在這裏展示的位置會對生成的代碼產生巨大（負面）的性能影響，所以我們選擇不允許它。輸出應該是表達式的Polish prefix form，而解析器實際上是試圖使用infix notation對輸入進行操作。解決的辦法是不是發出綴表示法：

expr 
    : {a();} ID 
    | expr {b();} '+' ID 
    ; 

通過收集調用a和b的結果，你可以轉換的結果，你喜歡的任何符號寫的結果之前。另一種選擇是將嵌入式操作移動到在解析完成後執行的訪問者，它在處不起作用以您喜歡的任何順序執行它們。

延伸閱讀：Infix, Postfix, and Prefix