赋值文法与 λ-演算应用文法冲突

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 使用括号是有原因的 :-)）

赋值文法与 λ-演算应用文法冲突

Assignment grammar conflicting with λ-calculus application grammar

c++

grammar

parsing

antlr

lambda-calculus

第 1 期

第 2 期

可能的解决方案