在 antlr4 语法中消除一元和二元减号的歧义

Question

我正在为一种比较简单的语言创建 antlr4 语法。我正在努力让语法区分一元和二进制减号。我已经阅读了我可以在 Whosebug 上找到的关于这个主题的所有其他帖子，但我发现这些答案要么以我无法弄清楚如何在 antlr4 中表达的方式适用于 antlr3，要么我似乎不擅长翻译这些答案对我自己情况的建议。如果我尝试其他替代方案，我经常会遇到 antlr 无法明确解决规则的问题。

下面是完整的antlr文件。此版本中的歧义发生在制作过程中：

binop_expr
        : SUMOP product
        | product ( SUMOP product )*
        ;

（我最初使用 UNARY_ABELIAN_OP 而不是第二个 SUMOP，但这导致了另一种歧义——该工具显然无法识别它需要在两个不同的上下文。我提到这个是因为这里的一篇帖子建议为一元运算符使用不同的名称。）

grammar Kant;

program
        : type_declaration_list main
        ;

type_declaration_list
        : type_declaration
        | type_declaration_list type_declaration
        | /* null */
        ;

type_declaration
        : 'context' JAVA_ID '{' context_body '}'
        | 'class'   JAVA_ID '{' class_body   '}'
        | 'class'   JAVA_ID 'extends' JAVA_ID '{' class_body   '}'
        ;

context_body
        : context_body context_body_element
        | context_body_element
        | /* null */
        ;

context_body_element
        : method_decl
        | object_decl
        | role_decl
        | stageprop_decl
        ;

role_decl
        : 'role' JAVA_ID '{' role_body '}'
        | 'role' JAVA_ID '{' role_body '}' REQUIRES '{' self_methods '}'
        | access_qualifier 'role' JAVA_ID '{' role_body '}'
        | access_qualifier 'role' JAVA_ID '{' role_body '}' REQUIRES '{' self_methods '}'
        ;

role_body
        : method_decl
        | role_body method_decl
        | object_decl               // illegal
        | role_body object_decl     // illegal — for better error messages only
        ;

self_methods
        : self_methods ';' method_signature
        | method_signature
        | self_methods /* null */ ';'
        ;

stageprop_decl
        : 'stageprop' JAVA_ID '{' stageprop_body '}'
        | 'stageprop' JAVA_ID '{' stageprop_body '}' REQUIRES '{' self_methods '}'
        | access_qualifier 'stageprop' JAVA_ID '{' stageprop_body '}'
        | access_qualifier 'stageprop' JAVA_ID '{' stageprop_body '}' REQUIRES '{' self_methods '}'
        ;

stageprop_body
        : method_decl
        | stageprop_body method_decl
        ;

class_body
        : class_body class_body_element
        | class_body_element
        | /* null */
        ;

class_body_element
        : method_decl
        | object_decl
        ;

method_decl
        : method_decl_hook '{' expr_and_decl_list '}'
        ;

method_decl_hook
        : method_signature
        | method_signature CONST
        ;

method_signature
        : access_qualifier return_type method_name '(' param_list ')'
        | access_qualifier return_type method_name 
        | access_qualifier method_name '(' param_list ')'
        ;

expr_and_decl_list
        : object_decl
        | expr ';' object_decl
        | expr_and_decl_list object_decl
        | expr_and_decl_list expr
        | expr_and_decl_list /*null-expr */ ';'
        | /* null */
        ;

return_type
        : type_name
        | /* null */
        ;

method_name
        : JAVA_ID
        ;

access_qualifier
        : 'public' | 'private' | /* null */
        ;

object_decl
        : access_qualifier compound_type_name identifier_list ';'
        | access_qualifier compound_type_name identifier_list
        | compound_type_name identifier_list /* null expr */ ';'
        | compound_type_name identifier_list
        ;

compound_type_name
        : type_name '[' ']'
        | type_name
        ;

type_name
        : JAVA_ID
        | 'int'
        | 'double'
        | 'char'
        | 'String'
        ;

identifier_list
        : JAVA_ID
        | identifier_list ',' JAVA_ID
        | JAVA_ID ASSIGN expr
        | identifier_list ',' JAVA_ID ASSIGN expr
        ;

param_list
        : param_decl
        | param_list ',' param_decl
        | /* null */
        ;

param_decl
        : type_name JAVA_ID
        ;

main
        : expr
        ;

expr
        : block
        | expr '.' message
        | expr '.' CLONE
        | expr '.' JAVA_ID
        | ABELIAN_INCREMENT_OP expr '.' JAVA_ID
        | expr '.' JAVA_ID ABELIAN_INCREMENT_OP
        | /* this. */ message
        | JAVA_ID
        | constant
        | if_expr
        | for_expr
        | while_expr
        | do_while_expr
        | switch_expr
        | BREAK
        | CONTINUE
        | boolean_expr
        | binop_expr
        | '(' expr ')'
        | <assoc=right> expr ASSIGN expr
        | NEW message
        | NEW type_name '[' expr ']'
        | RETURN expr
        | RETURN
        ;

relop_expr
        : sexpr RELATIONAL_OPERATOR sexpr
        ;


// This is just a duplication of expr. We separate it out
// because a top-down antlr4 parser can't handle the
// left associative ambiguity. It is used only
// for abelian types.
sexpr
        : block 
        | sexpr '.' message
        | sexpr '.' CLONE
        | sexpr '.' JAVA_ID
        | ABELIAN_INCREMENT_OP sexpr '.' JAVA_ID
        | sexpr '.' JAVA_ID ABELIAN_INCREMENT_OP
        | /* this. */ message
        | JAVA_ID
        | constant
        | if_expr
        | for_expr
        | while_expr
        | do_while_expr
        | switch_expr
        | BREAK
        | CONTINUE
        | '(' sexpr ')'
        | <assoc=right> sexpr ASSIGN sexpr
        | NEW message
        | NEW type_name '[' expr ']'
        | RETURN expr
        | RETURN
        ;

block
        : '{' expr_and_decl_list '}'
        | '{' '}'
        ;

expr_or_null
        : expr
        | /* null */
        ;

if_expr
        : 'if' '(' boolean_expr ')' expr
        | 'if' '(' boolean_expr ')' expr 'else' expr
        ;

for_expr
        : 'for' '(' object_decl boolean_expr ';' expr ')' expr  // O.K. — expr can be a block
        | 'for' '(' JAVA_ID ':' expr ')' expr
        ;

while_expr
        : 'while' '(' boolean_expr ')' expr
        ;

do_while_expr
        : 'do' expr 'while' '(' boolean_expr ')'
        ;

switch_expr
        : SWITCH '(' expr ')' '{'  ( switch_body )* '}'
        ;

switch_body
        : ( CASE constant | DEFAULT ) ':' expr_and_decl_list
        ;

binop_expr
        : SUMOP product
        | product ( SUMOP product )*
        ;

product
        : atom  ( MULOP atom )*
        ;

atom
        : null_expr
        | JAVA_ID
        | JAVA_ID ABELIAN_INCREMENT_OP
        | ABELIAN_INCREMENT_OP JAVA_ID
        | constant
        | '(' expr ')'
        | array_expr '[' sexpr ']'
        | array_expr '[' sexpr ']' ABELIAN_INCREMENT_OP
        | ABELIAN_INCREMENT_OP array_expr '[' sexpr ']'
        ;

null_expr
        : NULL
        ;

array_expr
        : sexpr
        ;

boolean_expr
        : boolean_product ( BOOLEAN_SUMOP boolean_product )*
        ;

boolean_product
        : boolean_atom  ( BOOLEAN_MULOP boolean_atom )*
        ;

boolean_atom
        : BOOLEAN
        | JAVA_ID
        | '(' boolean_expr ')'
        | LOGICAL_NOT boolean_expr
        | relop_expr
        ;

constant
        : STRING
        | INTEGER
        | FLOAT
        | BOOLEAN
        ;

message
        : <assoc=right> JAVA_ID '(' argument_list ')'
        ;

argument_list
        : expr
        | argument_list ',' expr
        | /* null */
        ;

// Lexer rules

STRING : '"' ( ~'"' | '\' '"' )* '"' ;

INTEGER : ('1' .. '9')+ ('0' .. '9')* | '0';

FLOAT : (('1' .. '9')* | '0') '.' ('0' .. '9')* ;

BOOLEAN : 'true' | 'false' ;

SWITCH : 'switch' ;

CASE : 'case' ;

DEFAULT : 'default' ;

BREAK : 'break' ;

CONTINUE : 'continue' ;

RETURN : 'return' ;

REQUIRES : 'requires' ;

NEW : 'new' ;

CLONE : 'clone' ;

NULL : 'null' ;

CONST : 'const' ;

RELATIONAL_OPERATOR : '!=' | '==' | '>' | '<' | '>=' | '<=';

LOGICAL_NOT : '!' ;

BOOLEAN_MULOP : '&&'  ;

BOOLEAN_SUMOP : '||' | '^' ;

SUMOP : '+' | '-' ;

MULOP : '*' | '/' ;

ABELIAN_INCREMENT_OP : '++' | '--' ;

JAVA_ID: (('a' .. 'z') | ('A' .. 'Z')) (('a' .. 'z') | ('A' .. 'Z') | ('0' .. '9') | '_')* ;

INLINE_COMMENT: '//' ~[\r\n]* -> channel(HIDDEN) ;

C_COMMENT: '/*' .*? '*/' -> channel(HIDDEN) ;

WHITESPACE : ( '\t' | ' ' | '\r' | '\n'| '\u000C' )+ -> channel(HIDDEN) ;

ASSIGN : '=' ;

典型的问题是解析器无法识别此表达式中的一元减号（它根本不接受构造）：

Base b1 = new Base(-threetwoone);

Answer 1

尝试从 binop_expr 中删除一元表达式，并将其添加到 expr 规则中：

expr
 : ...
 | unary_expr
 | binop_expr
 | ...
 ;

unary_expr
 : SUMOP binop_expr
 ;

binop_expr
 : product ( SUMOP product )*
 ;

Answer 2

问题似乎是由于语法中有两种表达式需要更好地相互组合而不是像它们一样混合。总体意图是创建一种语言，其中一切都是表达式，包括，例如，循环和条件。（你可以发挥你的想象力来推断它们产生的值；但是，这是一个语义问题，而不是句法问题）。

这些表达式中的一组具有良好的交换性质（它们的行为类似于具有良好操作的普通算术类型）。该语言指定了较低级别的产品如何通过为它们提供上下文的操作联系在一起：因此两个标识符 "a" 和 "b" 可以通过运算符“+”关联为 "a + b"。这是一种高度语境化的语法。

这些表达式中的另一组包含句法内聚度低得多的产生式。可以按任意顺序组合 "if" 表达式、"for" 表达式和声明。正如我们在 object_body、class_body 和 expr_and_decl_list.

的作品中所发现的那样，将它们联系起来的唯一语言属性是串联

基本问题是这两种语法在 antlr 规范中交织在一起。结合像“+”这样的运算符是上下文敏感的，并且上下文可以从级联或更上下文化的阿贝尔替代中产生的事实，解析器有两种解析某些表达式的替代方法。我设法解决了大部分歧义，但它被推到了一元前缀运算符的领域。所以如果 "a" 是一个表达式（它是），并且 "b" 是一个表达式，那么字符串 "a + b" 是有歧义的。它可以表示 product ( SUMOP product )*，也可以表示 expr_and_decl_list expr，其中 expr_and_decl_list 早先是从 expr "a" 缩减而来的。 expr_and_decl_list expr中的expr可以从"+b"减少。

我重新编写了语法，受到我在网上找到的其他示例的启发。（其中一个更有影响力的是 Bart Kiers 向我指出的：If/else statements in ANTLR using listeners）您可以在下面找到新语法。与阿贝尔表达式的文法属于一起但用于简化为 expr 目标的内容，如 NEW expr 和 expr '.' JAVA_ID，现在已被分离出来以简化为 [=23] =] 目标。所有减少到 abelian_expr 的产生式现在或多或少都是语法中 abelian_expr 节点的直接后代；这有助于 antlr 智能地处理否则会出现的歧义。一元“+”表达式不再可以直接归约为 expr，但只能通过 abelian_expr 找到通往 expr 的途径，因此它永远不会被视为可以简单地串联为的产生式一个很大程度上没有上下文的表达。

我无法证明那是正在发生的事情，但迹象表明了那个方向。如果其他人有更正式或演绎的分析（特别是如果它指向另一个结论），我很想听听你的推理。

这里的教训似乎是，语言设计中一个高级的、基本的缺陷设法表现为一个孤立的、在某种意义上是小的错误：无法消除一元之间的歧义和运算符的二进制使用。

grammar Kant;

program
        : type_declaration_list main
        | type_declaration_list     // missing main
        ;

main
        : expr
        ;

type_declaration_list
        : type_declaration
        | type_declaration_list type_declaration
        | /* null */
        ;

type_declaration
        : 'context' JAVA_ID '{' context_body '}'
        | 'class'   JAVA_ID '{' class_body   '}'
        | 'class'   JAVA_ID 'extends' JAVA_ID '{' class_body   '}'
        ;

context_body
        : context_body context_body_element
        | context_body_element
        | /* null */
        ;

context_body_element
        : method_decl
        | object_decl
        | role_decl
        | stageprop_decl
        ;

role_decl
        : 'role' JAVA_ID '{' role_body '}'
        | 'role' JAVA_ID '{' role_body '}' REQUIRES '{' self_methods '}'
        | access_qualifier 'role' JAVA_ID '{' role_body '}'
        | access_qualifier 'role' JAVA_ID '{' role_body '}' REQUIRES '{' self_methods '}'
        ;

role_body
        : method_decl
        | role_body method_decl
        | object_decl               // illegal
        | role_body object_decl     // illegal — for better error messages only
        ;

self_methods
        : self_methods ';' method_signature
        | method_signature
        | self_methods /* null */ ';'
        ;

stageprop_decl
        : 'stageprop' JAVA_ID '{' stageprop_body '}'
        | 'stageprop' JAVA_ID '{' stageprop_body '}' REQUIRES '{' self_methods '}'
        | access_qualifier 'stageprop' JAVA_ID '{' stageprop_body '}'
        | access_qualifier 'stageprop' JAVA_ID '{' stageprop_body '}' REQUIRES '{' self_methods '}'
        ;

stageprop_body
        : method_decl
        | stageprop_body method_decl
        | object_decl               // illegal
        | stageprop_body object_decl        // illegal — for better error messages only
        ;

class_body
        : class_body class_body_element
        | class_body_element
        | /* null */
        ;

class_body_element
        : method_decl
        | object_decl
        ;

method_decl
        : method_decl_hook '{' expr_and_decl_list '}'
        ;

method_decl_hook
        : method_signature
        ;

method_signature
        : access_qualifier return_type method_name '(' param_list ')' CONST*
        | access_qualifier return_type method_name CONST*
        | access_qualifier method_name '(' param_list ')' CONST*
        ;

expr_and_decl_list
        : object_decl
        | expr ';' object_decl
        | expr_and_decl_list object_decl
        | expr_and_decl_list expr
        | expr_and_decl_list /*null-expr */ ';'
        | /* null */
        ;

return_type
        : type_name
        | /* null */
        ;

method_name
        : JAVA_ID
        ;

access_qualifier
        : 'public' | 'private' | /* null */
        ;

object_decl
        : access_qualifier compound_type_name identifier_list ';'
        | access_qualifier compound_type_name identifier_list
        | compound_type_name identifier_list /* null expr */ ';'
        | compound_type_name identifier_list
        ;

compound_type_name
        : type_name '[' ']'
        | type_name
        ;

type_name
        : JAVA_ID
        | 'int'
        | 'double'
        | 'char'
        | 'String'
        ;

identifier_list
        : JAVA_ID
        | identifier_list ',' JAVA_ID
        | JAVA_ID ASSIGN expr
        | identifier_list ',' JAVA_ID ASSIGN expr
        ;

param_list
        : param_decl
        | param_list ',' param_decl
        | /* null */
        ;

param_decl
        : type_name JAVA_ID
        ;

expr
        : abelian_expr
        | boolean_expr
        | block
        | if_expr
        | for_expr
        | while_expr
        | do_while_expr
        | switch_expr
        | BREAK
        | CONTINUE
        | RETURN expr
        | RETURN
        ;

abelian_expr
        : <assoc=right>abelian_expr POW abelian_expr           
        | ABELIAN_SUMOP expr                           
        | LOGICAL_NEGATION expr
        | NEW message
        | NEW type_name '[' expr ']'                            
        | abelian_expr ABELIAN_MULOP abelian_expr       
        | abelian_expr ABELIAN_SUMOP abelian_expr             
        | abelian_expr ABELIAN_RELOP abelian_expr                    
        | null_expr
        | /* this. */ message
        | JAVA_ID
        | JAVA_ID ABELIAN_INCREMENT_OP
        | ABELIAN_INCREMENT_OP JAVA_ID
        | constant
        | '(' abelian_expr ')'
        | abelian_expr '[' expr ']'
        | abelian_expr '[' expr ']' ABELIAN_INCREMENT_OP
        | ABELIAN_INCREMENT_OP expr '[' expr ']'
        | ABELIAN_INCREMENT_OP expr '.' JAVA_ID
        | abelian_expr '.' JAVA_ID ABELIAN_INCREMENT_OP
        | abelian_expr '.' message
        | abelian_expr '.' CLONE
        | abelian_expr '.' CLONE '(' ')'
        | abelian_expr '.' JAVA_ID
        | <assoc=right> abelian_expr ASSIGN expr
        ;

message
        : <assoc=right> JAVA_ID '(' argument_list ')'
        ;

boolean_expr
        : boolean_expr BOOLEAN_MULOP expr                       
        | boolean_expr BOOLEAN_SUMOP expr
        | constant      // 'true' / 'false'
        | abelian_expr
        ;

block
        : '{' expr_and_decl_list '}'
        | '{' '}'
        ;

expr_or_null
        : expr
        | /* null */
        ;

if_expr
        : 'if' '(' expr ')' expr
        | 'if' '(' expr ')' expr 'else' expr
        ;

for_expr
        : 'for' '(' object_decl expr ';' expr ')' expr  // O.K. — expr can be a block
        | 'for' '(' JAVA_ID ':' expr ')' expr
        ;

while_expr
        : 'while' '(' expr ')' expr
        ;

do_while_expr
        : 'do' expr 'while' '(' expr ')'
        ;

switch_expr
        : SWITCH '(' expr ')' '{'  ( switch_body )* '}'
        ;

switch_body
        : ( CASE constant | DEFAULT ) ':' expr_and_decl_list
        ;

null_expr
        : NULL
        ;

constant
        : STRING
        | INTEGER
        | FLOAT
        | BOOLEAN
        ;

argument_list
        : expr
        | argument_list ',' expr
        | /* null */
        ;


// Lexer rules

STRING : '"' ( ~'"' | '\' '"' )* '"' ;

INTEGER : ('1' .. '9')+ ('0' .. '9')* | '0';

FLOAT : (('1' .. '9')* | '0') '.' ('0' .. '9')* ;

BOOLEAN : 'true' | 'false' ;

SWITCH : 'switch' ;

CASE : 'case' ;

DEFAULT : 'default' ;

BREAK : 'break' ;

CONTINUE : 'continue' ;

RETURN : 'return' ;

REQUIRES : 'requires' ;

NEW : 'new' ;

CLONE : 'clone' ;

NULL : 'null' ;

CONST : 'const' ;

ABELIAN_RELOP : '!=' | '==' | '>' | '<' | '>=' | '<=';

LOGICAL_NOT : '!' ;

POW : '**' ;

BOOLEAN_SUMOP : '||' | '^' ;

BOOLEAN_MULOP : '&&'  ;

ABELIAN_SUMOP : '+' | '-' ;

ABELIAN_MULOP : '*' | '/' | '%' ;

MINUS : '-' ;

PLUS : '+' ;

LOGICAL_NEGATION : '!' ;

ABELIAN_INCREMENT_OP : '++' | '--' ;

JAVA_ID: (('a' .. 'z') | ('A' .. 'Z')) (('a' .. 'z') | ('A' .. 'Z') | ('0' .. '9') | '_')* ;

INLINE_COMMENT: '//' ~[\r\n]* -> channel(HIDDEN) ;

C_COMMENT: '/*' .*? '*/' -> channel(HIDDEN) ;

WHITESPACE : ( '\t' | ' ' | '\r' | '\n'| '\u000C' )+ -> channel(HIDDEN) ;

ASSIGN : '=' ;

在 antlr4 语法中消除一元和二元减号的歧义

Disambiguating unary and binary minus in antlr4 grammar

antlr4