0

我正在为 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语法的代码版本。主代码中注释的部分已消除歧义（意味着消除了歧义！），并在第二部分（数学规则）中消除了左递归。

谁能指出这哪里出错了，为什么我没有得到想要的输出？

提前致谢！

4

1 回答 1

1

除了 中的操作之外program，您的每个println调用都出现在语法中的标记引用之前。很明显，这意味着它们将按照令牌在文件中出现的顺序执行。

预期输出和实际输出之间的第一个不匹配是行16和的反转27。+仅当输入中的标记出现在输入中的标记之前时，您的预期输出才会出现2，但显然您可以看到情况并非如此。出于同样的原因发生第二个不匹配；具体来说，这是因为预期的输出假设*令牌在您的语法中出现的时间比3令牌更早。

我注意到您最初编写了一个左递归expr规则并在其中包含嵌入式操作。以下信息与解决您的特定问题无关，但如果您决定取消注释该代码并使用expr.

考虑以下左递归规则，以允许简单地添加标识符，并添加两个嵌入式操作。

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

正如您可能发现的那样，此语法不会与 ANTLR 一起编译。我们发现{b();}在我在这里展示它的位置评估表达式会对生成的代码产生巨大的（负面）性能影响，因此我们选择不允许它。输出将是表达式的波兰语前缀形式，而解析器实际上正在尝试使用中缀表示法对输入进行操作。解决方案是改为发出中缀符号：

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

通过收集对aand的调用结果b，您可以在编写结果之前将结果转换为您喜欢的任何符号。另一种选择是将嵌入的操作移动到解析完成后执行的访问者，在那里以您喜欢的任何顺序执行它们是微不足道的。

进一步阅读：中缀、后缀和前缀

于 2014-10-30T12:41:58.870 回答