如何定义像Scala/Rust这样混合语句和表达式文法的简单编程语言文法？

Question

我正在学习 Scala/Rust 的语法并尝试给自己定义一个玩具语言语法。我发现他们的语法混合了命令式语言语法和函数式语言语法，换句话说，语句也是表达式，语句有return值。

在Scala语法中，例如：

https://www.scala-lang.org/files/archive/spec/2.13/13-syntax-summary.html

  Expr              ::=  (Bindings | [‘implicit’] id | ‘_’) ‘=>’ Expr
                      |  Expr1
  Expr1             ::=  ‘if’ ‘(’ Expr ‘)’ {nl} Expr [[semi] ‘else’ Expr]
                      |  ‘while’ ‘(’ Expr ‘)’ {nl} Expr
                      |  ‘try’ Expr [‘catch’ Expr] [‘finally’ Expr]
                      |  ‘do’ Expr [semi] ‘while’ ‘(’ Expr ‘)’
                      |  ‘for’ (‘(’ Enumerators ‘)’ | ‘{’ Enumerators ‘}’) {nl} [‘yield’] Expr
                      |  ‘throw’ Expr
                      |  ‘return’ [Expr]
                      |  [SimpleExpr ‘.’] id ‘=’ Expr
                      |  SimpleExpr1 ArgumentExprs ‘=’ Expr
                      |  PostfixExpr
                      |  PostfixExpr Ascription
                      |  PostfixExpr ‘match’ ‘{’ CaseClauses ‘}’
  PostfixExpr       ::=  InfixExpr [id [nl]]
  InfixExpr         ::=  PrefixExpr
                      |  InfixExpr id [nl] InfixExpr
  PrefixExpr        ::=  [‘-’ | ‘+’ | ‘~’ | ‘!’] SimpleExpr
  SimpleExpr        ::=  ‘new’ (ClassTemplate | TemplateBody)
                      |  BlockExpr
                      |  SimpleExpr1 [‘_’]
  SimpleExpr1       ::=  Literal
                      |  Path
                      |  ‘_’
                      |  ‘(’ [Exprs] ‘)’
                      |  SimpleExpr ‘.’ id
                      |  SimpleExpr TypeArgs
                      |  SimpleExpr1 ArgumentExprs
                      |  XmlExpr
  Exprs             ::=  Expr {‘,’ Expr}
  BlockExpr         ::=  ‘{’ CaseClauses ‘}’
                      |  ‘{’ Block ‘}’
  Block             ::=  BlockStat {semi BlockStat} [ResultExpr]
  BlockStat         ::=  Import
                      |  {Annotation} [‘implicit’] [‘lazy’] Def
                      |  {Annotation} {LocalModifier} TmplDef
                      |  Expr1
                      |

在命令式语言中，语句类似于 for、if、while、expression ;，没有 return 值。但是在这里我们可以看到它们都是 Expr1.

在 Rust 语法中，例如：

https://doc.rust-lang.org/reference/expressions/block-expr.html

BlockExpression :
   {
      InnerAttribute*
      Statements?
   }

Statements :
      Statement+
   | Statement+ ExpressionWithoutBlock
   | ExpressionWithoutBlock

Expression :
      ExpressionWithoutBlock
   | ExpressionWithBlock

ExpressionWithoutBlock :
   OuterAttribute*†
   (
         LiteralExpression
      | PathExpression
      | OperatorExpression
      | GroupedExpression
      | ArrayExpression
      | AwaitExpression
      | IndexExpression
      | TupleExpression
      | TupleIndexingExpression
      | StructExpression
      | EnumerationVariantExpression
      | CallExpression
      | MethodCallExpression
      | FieldExpression
      | ClosureExpression
      | ContinueExpression
      | BreakExpression
      | RangeExpression
      | ReturnExpression
      | MacroInvocation
   )

ExpressionWithBlock :
   OuterAttribute*†
   (
         BlockExpression
      | AsyncBlockExpression
      | UnsafeBlockExpression
      | LoopExpression
      | IfExpression
      | IfLetExpression
      | MatchExpression
   )

IfExpression :
   if Expressionexcept struct expression BlockExpression
   (else ( BlockExpression | IfExpression | IfLetExpression ) )?

LoopExpression :
   LoopLabel? (
         InfiniteLoopExpression
      | PredicateLoopExpression
      | PredicatePatternLoopExpression
      | IteratorLoopExpression
   )

IteratorLoopExpression :
   for Pattern in Expressionexcept struct expression BlockExpression

我们可以看到，{ }块中的语句也是表达式。

我想定义一个非常简单的玩具语言语法，如 Scala/Rust，但语句仍然由 ; 分隔，如 C/C++。

我正在使用 yacc/bison 来定义此语法，这是我的示例：


primary_expr: ID
            | TRUE
            | FALSE
            | INTEGER
            | FLOAT
            | '(' expr ')'
            ;

postfix_expr : primary_expr
             | call_expr
             ;

unary_expr : postfix_expr
           | '-' unary_expr
           | '~' unary_expr
           | '!' unary_expr
           ;

binary_expr : unary_expr
            | binary_expr '+' unary_expr
            | binary_expr '-' unary_expr
            | binary_expr '*' unary_expr
            | binary_expr '/' unary_expr
            | binary_expr '%' unary_expr
            | binary_expr '==' unary_expr
            | binary_expr '!=' unary_expr
            | binary_expr '>' unary_expr
            | binary_expr '>=' unary_expr
            | binary_expr '<' unary_expr
            | binary_expr '<=' unary_expr
            ;

conditional_expr : binary_expr
                 | binary_expr '?' expr ':' conditional_expr
                 ;

assignment_expr : conditional_expr
                | unary_expr '=' assignment_expr
                ;

expr : assignment_expr
     | expr1
     ;

stmt : expr ';'
     | def
     ;

def : ...
    ;

expr1 : 'if' '(' expr ')' expr
      | 'if' '(' expr ')' expr 'else' expr
      | 'while' '(' expr ')' expr
      | 'return' expr
      | '{' stmt_list '}'
      | 'break'
      | 'continue'
      ;

stmt_list : stmt
          | stmt stmt_list
          ;

但是这个语法并不像我期望的那样：

{
  if (true)
    return 1
  else 
    return 0;

  while (true) {
    print(1);
  };
}

但我希望它像：

{
  if (true)
    return 1;
  else 
    return 0;

  while (true) {
    print(1);
  }
}

我该如何解决？

Answer 1

解析分号（或任何其他列表分隔符）完全独立于列表的语义。

换句话说，你想让某些分号被省略的愿望与分号分隔（或终止）的东西是什么东西的问题完全没有关系。一个语句是被认为是一种表达式（可能为空值）还是另一种实体是一个语义问题。解析器唯一涉及的是将语句（或表达式）列表划分为单独的组件。

这并不是说语义问题无趣。支持（和反对）Rust 语义有很多话要说。但是您实际上要问的问题似乎是关于语法的。

无论语句是否是表达式，几乎总是表达式是语句，或者更优雅地说，语句列表——例如，命令式函数的主体——包括表达式, 评估它们的副作用（例如变量赋值，在赋值是表达式的语言中，或调用一个函数来做除计算 return 值以外的事情，例如打印其参数。）

通常，该语言至少有一个后缀运算符，即函数调用运算符。在没有表达式定界符的情况下，这必然会产生歧义，因为像

这样的表达式

a ( b )

不是明确的单个表达式。可能是 a 和 ( b ) 这两个表达式。类似地，如果语言包含具有相同拼写的前缀和中缀运算符（- 是最常见的示例，但还有许多其他可能性），那么使用中缀形式的表达式也可以解释为两个连续的表达式，第二个使用前缀运算符。

虽然可以通过各种特殊用途的规则来解决所有这些歧义，但有两种常见的解决方案：（当我在这里说“声明”时，请将其理解为“列表中的句法实体适合用作块”或类似的东西。正如我之前所说，这与语句或表达式无关；它与您如何编写列表有关。）

使所有语句自行终止。一个例子是 C 语言家族，其中不会自行终止的语句在其语法中包含一个分号。是自终止语句的一个例子是一个块，它必须以块打开 ({) 开始并以匹配的块关闭 (}).一个非自终止语句的例子是一个简单的赋值语句。

由于 ; 是赋值语句的句法部分，即使在块的末尾也不能省略。尽管 } 明确表示封闭块的结束，但分号仍必须存在。（初学者经常会遇到需要在 else 标记前使用分号的需要，这会响应相同的逻辑。）

可以使用不太严格的语法，在不需要分号分隔列表元素的上下文中，分号变为可选。通常，只有当源代码包含换行符或在其他一些非常特定的上下文中时，才会提供这种灵活性。但这种灵活性对编译器编写者（以及因此对任何其他为该语言编写工具的人）来说是有代价的，因为它会使语法分析和词法分析变得相当复杂。
列表在连续元素之间放置一个分隔符。当列表是某种聚合文字时，这很常见，但有些语言——比如 Rust——也对块使用这种风格。在这种风格中，分隔符是列表语法的一部分，而不是（某些）列表元素的语法的一部分。因此，即使在前面的列表元素明确终止的上下文中，也需要分隔符。这会导致像
这样的烦恼
```
 {
     { ...
     };   /* Semicolon redundantly separates two list elements */
     { ...
     }    /* Here there is no semicolon because there is no following element. */
 }
```
同样，可以编写一个灵活的语法，其中一些多余的分号成为可选的。同样，这种灵活性是以实现复杂性为代价的。

在许多使用列表分隔符的语言中，列表分隔符可以选择性地附加到列表（或某些列表）的末尾。例如，在 C 中，用于初始化数组（使用 , 作为分隔符）的值列表可以在末尾包含一个额外的逗号，该逗号将被忽略。（这对于自动生成列表特别方便。）这与 Rust 不同，在 Rust 中，语句块（表达式）可以以空表达式结尾：...; }。这个分号不会被忽略；相反，它用于将块的值类型从最后一个表达式的类型更改为空表达式的类型。（并非所有语言都允许空语句。例如，Python 和 Posix shell 都不允许连续出现两个 ;。）

以上是从基本忽略空格（包括换行符），分号作为terminator/separator的语言角度写的。但是还有另一种非常相似的方法，其中 换行符 是 terminator/separator （可能分号是一种替代方法），但是在某些情况下换行符会失去其句法意义。例如，Scala 就是这种情况。上下文分号插入（如在 ECMAScript 中）和换行符删除（如在 Scala 中）之间的区别是微妙的，也许到了不可见的地步。（也就是说，这两个约定可能只是产生相同结果的两种不同方式。）

现在，如何实现这些不同的语法？

我不打算在这里讨论分号 insertion/newline 删除，尽管这是一个有趣的问题。存在各种不同的机制，其中一些以令人惊讶的极端情况告终；实现细节是特定于语言的，通常是手写的，而不是从语法中自动生成的。 SO 上有一些答案讨论了特定语言的实现。（但下面有一种简单的可能性。）

1。分号作为终止符

list : %empty
     | list expression
expression
     : simple_expression ';'
     | ';'
     | block
     | 'while' simple_expression 'do' expression
     | 'if' simple_expression 'then' expression 
     | 'if' simple_expression 'then' expression 'else' expression
     | ...
block: '{' list '}'

2。分号作为分隔符

list : expression
     | list ';' expression
expression
     : simple_expression
     | block 
     | 'while' expression 'do' expression
     | 'if' expression 'then' expression
     | 'if' expression 'then' expression 'else' expression
block: '{' '}'
     | '{' list '}'
     | '{' list ';' '}'    // If you want optional trailing delimiter

上面两个示例之间存在一些细微差别，尽管它们对各自的模型并不重要。它们只是我碰巧编写语法的方式的结果，尽管我的主要目标是最简单的语法。

首先，虽然他们都回应了“一切都是表达式”的想法，但是“分号作为终止符”不允许任意表达式作为while和if语句的控制表达式为了避免在下面的关键字前需要分号 [注 1]。其次，它们在 else:

之前使用 ; 不同

if x < y then min = x; else min = y; /* Grammar 1 */
if x < y then min = x else min = y;  /* Grammar 2 */

2a。变体：分号作为分隔符，但在某些元素之后是可选的

这里的目的是删除（一些）特别烦人的分号，而不会使语法（非常）复杂。可选的分号完全是且仅是 block 中结束 } 之后的分号，因此逻辑根本不考虑以下标记。这或多或少消除了语法 1 中不需要的那些分号的需要，因此它可能更接近您正在寻找的内容。

为了实现它，我们需要区分以 block 结尾的表达式和不以 block 结尾的表达式，这在条件语句和循环语句的情况下会有点尴尬。因为我的目的是避免复杂性，所以我通过将复合语句限制为 block 而不是允许简单表达式来简化该问题。该限制使得可以取消 then 和 do 标记，它们将复合语句中的保护表达式与保护块分开，这是必要的，因为我们不能有两个连续的 expression s 不产生歧义：

list : unterminated_list
     | terminated_list
unterminated_list
     : unterminated_expression
     | terminated_list unterminated_expression
terminated_list
     : terminated_expression
     | list ';'
     | terminated_list terminated_expression
expression
     : unterminated_expression
     | terminated_expression
unterminated_expression
     : simple_expression
/*   | ... /* Perhaps assignment */
terminated_expression
     : block 
     | "while" expression block
     | "if" expression block
     | "if" expression block "else" block
block: '{' '}'
     | '{' list '}'
simple_expression
     : term
     | simple_expression '+' term
term : IDENTIFIER
     | LITERAL
     | '(' expression ')'
     | term '(' ')'
     | term '(' arglist ')'
arglist
     : expression
     | arglist ',' expression

备注

一种确实需要在该位置使用终止符的语言是 Posix shell，您需要在其中编写，例如，
```
 if (( count == 3 )); then break
```
但在大多数语言中，分号会让人觉得很烦人。）

如何定义像Scala/Rust这样混合语句和表达式文法的简单编程语言文法？

How to define simple programming language grammar that mix statements and expressions grammar just like Scala/Rust?

grammar

parsing

antlr4

1。分号作为终止符

2。分号作为分隔符

2a。变体：分号作为分隔符，但在某些元素之后是可选的

备注