c++ - 分配语法与λ微积分应用语法冲突

Question

我正在使用ANTLR4实现扩展的λ演算解释器，它是C++目标。这是语言语法:

grammar lambda;

program: expression|;

expression:
    (Int | Bool)                                # literal
    | Identifier                                # variable
    | expression expression                     # application
    | Lambda Identifier '.' expression          # abstraction
    | Identifier '=' expression                 # assign
    | condition                                 # conditional
    | Operator expression expression            # binaryExpression
    | 'print' expression                        # printInstruction
    | '(' expression ')'                        # brackets;

body: expression;
condition: 'if' expression 'then' body 'else' body
    | '(' expression '->' body '|' body;

Lambda: '\\' | 'λ';
Bool : 'tru' | 'fls' | 'true' | 'false';
Int: [0-9]+;
Identifier: ('a' ..'z') ('a' ..'z' | '0' ..'9')*;
Operator:
    '+'
    | '-'
    | '*'
    | '/'
    | '<'
    | '>'
    | '<='
    | '>='
    | '==';

WS: [ \n\t\r]+ -> skip;

我正在使用访客模型构造AST，该模型将分别进行评估。我在ANTLR解析输入的方式时遇到了问题，我甚至不确定该如何调用。
第1期

// incorrect_association.lambda

y = 1
x = 1

Assignment ( y = ( Application ( Literal ( 1 ) ) ( Assignment ( x = ( Literal ( 1 ) ) ) ) ) )

AST应该是

Assignment ( y = ( Literal ( 1 ) )
Assignment ( x = ( Literal ( 1 ) )

要么

Grouping (
    Assignment ( y = ( Literal ( 1 ) ),
    Assignment ( x = ( Literal ( 1 ) )
)

第2期
我想这可能与第一个问题有关:跨多行的表达式被作为 Application表达式读取。

// incorrect_application.lambda

x = 1
print x

Assignment ( x = ( Application ( Literal ( 1 ) ) ( PrintInstruction ( Identifier ( "x" ) ) ) ) )

AST应该是

Assignment ( x = ( Literal ( 1 ) )
PrintInstruction ( Identifier ( "x" ) )

要么

Grouping (
    Assignment ( x = ( Literal ( 1 ) ),
    PrintInstruction ( Identifier ( "x" ) )
)

我试图拥有类似命令式的常量分配，并具有类似函数的执行方式。最终，程序应该是任何 main = ...(例如Haskell)。是否可以防止 Application规则匹配不同行上的两个表达式，但是继续允许任何其他空格和括号？
可能的解决方案
我正在考虑编写一个预处理器，该预处理器只会在每行结束处抛出分号。无论如何，我可能仍需要这样做，因为我打算添加

imports: 'import' Identifier | '(' imports ')';

作为语法规则，还没有找到使用ANTLR处理导入的理想解决方案。如果我要走这条路线，我该如何在语法中包括 ;行结尾？
PS:我对ANTLR非常陌生，因此任何指导都将非常有帮助。

Answer 1

如果您希望换行很重要，请让它们通过词法扫描器。

WS: [ \t\r]+ -> skip;
NL: [\n];

然后，您可以将程序定义为以换行符结尾的一系列表达式:

program: ( expression NL )*;

如果您希望分号也能正常工作，只需更改NL的定义即可:

NL: [\n;];

您还需要更改 body以接受多个表达式，尽管我尚不清楚您要使用哪种标点符号。有可能

body: expression (NL expression)*;

将为您工作，但可能会产生意外的结果。
您的应用程序语法非常含糊。我不知道Antlr将如何处理它，但我无法解释。如果你有

+ a b c

那必须是以下之一:

(+ a b) (c)
(+ a (b c))
(+ (a b) c)

但是我看不出应该优先选择这三个中的哪个。我认为您需要提出一个具有更精确优先级的语法。
(Lisp和Scheme使用括号是有原因的:-))