消除左递归ANTL4规则的歧义

Question

让我们考虑一下这个简单的ANTL4语言语法。

Lexer:

lexer grammar BiaLexer;
Lt                      : '<' ;
Gt                      : '>' ;
Identifier              : [a-zA-Z] ([a-zA-Z1-9] | ':')* ;
LeftParen               : '(' ;
RightParen              : ')' ;
Comma                   : ',' ;
Whitespace              : (' ' | 'n') -> skip ;

分析器：

parser grammar BiaParser;
options { tokenVocab = BiaLexer; }
typeExpression
: referredName=Identifier # typeReference ;
expression
: callee=expression callTypeVariableList LeftParen callArgumentList RightParen # callExpression
| left=expression operator=Lt right=expression # binaryOperation
| left=expression operator=Gt right=expression # binaryOperation
| referredName=Identifier # reference
| LeftParen expression RightParen # parenExpression ;
callTypeVariableList: Lt typeExpression (Comma typeExpression)* Gt ;
callArgumentList: (expression (Comma expression)*)? ;

所以，基本上，这种语言只有：

• 普通参考，例如a

• 类型引用，例如A

• 比较，例如a < b或c > d

• 括号中的表达式，例如(a)

• 最后，一般函数调用：例如f<A, B>(a, b)或f<A>(a)(类似于Kotlin(

这个语法不明确。像f<A>(a)这样的简单表达式可以解释为…

一个通用调用：Call(calle = ref:f, typeArgs = TypeArgs(typeRef:A), args = Args(ref:a))

或一个引用、另一个引用和带括号的表达式之间的比较链：Binary(op = >, left = Binary(op = <, left = ref:f, right = ref:A), right = Paren(ref:a))

ANTLR生成的实际解析器执行第二个，即比较链。如果我注释掉二进制运算规则。。。

//    | left=expression operator=Lt right=expression # binaryOperation
//    | left=expression operator=Gt right=expression # binaryOperation

然后，正如我所期望的那样，结果就是泛型调用。

请注意，我特意将#callExpression大小写放在expression规则的顶部，目的是声明它的优先级高于下面的比较大小写。我相信这就是在ANTLR中声明案例优先级的方式，但显然在这种情况下不起作用。

问题：

• 为什么ANTLR将f<A>(a)解释为一系列比较
• 我如何解决这个问题，即使泛型调用优先于比较链

如果这很重要，我可以提供我用来将AST转储到一个漂亮字符串的代码，但这只是一个简单的ANTLR访问者发出的字符串。为了可读性，我跳过了它。

Answer 1

我看了Swift和Rust的ANTLR语法。它们都只允许某种标识符在泛型类型规范之前(即，它们不允许任何表达式用作被调用者(。

使用这种方法，类似这样的东西可以很好地解析您的输入：

grammar Bia
;
typeExpression: referredName = Identifier # typeReference;
expression
: callee=Identifier callTypeVariableList LeftParen callArgumentList RightParen # callExpr
| left = expression operator = (Lt | Gt) right = expression             # binaryExpression
| Identifier                                                            # reference
| LeftParen expression RightParen                                       # parenExpression
;
callTypeVariableList
: Lt typeExpression (Comma typeExpression)* Gt
;
callArgumentList: (expression (Comma expression)*)?;
Lt:         '<';
Gt:         '>';
Identifier: [a-zA-Z] ([a-zA-Z1-9] | ':')*;
LeftParen:  '(';
RightParen: ')';
Comma:      ',';
Whitespace: (' ' | 'n') -> skip;

你可能会发现，你想要一个规则，它对你想要允许的callee标识符的类型更灵活一点，而不只是任何类型的表达式(可能有一个很好的论点，<或>表达式的布尔结果无论如何都不能真正用作callee(。

以下允许更大的灵活性，并且仍然正确匹配您的表达式：

grammar Bia
;
typeExpression: referredName = Identifier # typeReference;
expression
: callExpression                                            # callExpr
| left = expression operator = (Lt | Gt) right = expression # binaryExpression
| Identifier                                                # reference
| LeftParen expression RightParen                           # parenExpression
;
callExpression
: callee = calleeIdentifier (callTypeVariableList)? LeftParen callArgumentList RightParen # idCall
| callee = callExpression (callTypeVariableList)? LeftParen callArgumentList RightParen # exprCall
;
callTypeVariableList
: Lt typeExpression (Comma typeExpression)* Gt
;
calleeIdentifier: Identifier ('.' Identifier)*;
callArgumentList: (expression (Comma expression)*)?;
Lt:         '<';
Gt:         '>';
Identifier: [a-zA-Z] ([a-zA-Z1-9] | ':')*;
LeftParen:  '(';
RightParen: ')';
Comma:      ',';
Whitespace: (' ' | 'n') -> skip;

注意：我也试过kaby76的建议，它确实能处理你的情况。不过，您可能会发现生成的上下文类有点尴尬(因为将有一个与LT表达式的调用相匹配的规则替代项(。

Answer 2

要回答第一个(我自己的(子问题，我仍然不知道为什么第一个#callExpression替代方案不"被选中"；由ANTLR在原始语法中。kaby76的这一评论提出了一个有根据的猜测，听起来很合理。

Mike Cargal的回答很好地解决了问题中描述的问题。在此基础上，我调整了语法，使其也能处理带括号表达式(如(a)<A>(b)或(a + b)<A>(c)(上的函数调用。

该方法的细微区别在于，在我的情况下，我对"；可调用表达式"；(一个可以调用的表达式(，而不是用于调用表达式本身。尽管如此，正如你所能"呼叫呼叫"；在这个调整后的语法中，调用表达式是该规则中的一个可选表达式。

修改后的语法分析器如下所示：

parser grammar BiaParser;
options { tokenVocab = BiaLexer; }
typeExpression
: referredName=Identifier # typeReference ;
expression
: callableExpression # callableExpression_
| left=expression operator=Lt right=expression # binaryOperation
| left=expression operator=Gt right=expression # binaryOperation ;
callableExpression
: LeftParen expression RightParen # parenExpression
| callee=callableExpression callTypeVariableList? LeftParen callArgumentList RightParen # callExpression
| referredName=Identifier # reference ;
callTypeVariableList: Lt typeExpression (Comma typeExpression)* Gt ;
callArgumentList: (expression (Comma expression)*)? ;

它允许以下类型的通用调用：

• 调用标识符，例如f<A>(a)
• 调用任何带括号的表达式
• 随叫随到，例如f<A>(a, b)<B, C>(c, d, e)

我已经通过测试验证了上述所有案例都按预期进行了解析。

需要注意的一件有趣的事情是，就我所见，与原始语法相比，这种调整后的语法并没有以任何方式真正限制程序员。很难解释直接调用</>表达式意味着什么，因为即使是原始语法(通过意图和排序(也认为a < b<B>(c)是引用a和b<B>(c)泛型调用的lt比较(这可能是大多数程序员所期望的(。这(可能(推广到所有类型的二进制运算符(例如+、-(，以及可能出现在通用语言中的更多类型的表达式。