解析maxscript-换行符问题

Question

我正在尝试使用其官方语言grammar description为MAXScript语言创建解析器。我使用flex和bison创建词法分析器和解析器。

但是，我遇到了以下问题。在传统语言（例如C）中，语句由特殊标记（C中的;）分隔。但是在复合表达式内部的MAXScript表达式中，可以用;或newline分隔。还有其他一些在解析器中使用空格字符的语言，例如Python。但是Python对于newline的放置更加严格，并且Python中的以下程序无效：

# compile error
def 
foo(x):
  print(x)

# compile error
def bar
(x):
  foo(x)

但是在MAXScript中，以下程序有效：

fn
foo x =
(              // parenthesis start the compound expression
   a = 3 + 2;  // the semicolon is optional
   print x
)

fn bar
x =
   foo x

您甚至可以这样写：

for
x
in
#(1,2,3,4)
do
format "%," x

将评估结果良好，然后将1,2,3,4,打印到输出中。因此newline可以插入许多地方而没有特殊含义。

但是，如果您在程序中再插入一个newline：

for
x
in
#(1,2,3,4)
do
format "%,"
x

您将收到运行时错误，因为format函数期望传递多个参数。

这里是我拥有的野牛输入文件的一部分：

expr:
    simple_expr
|   if_expr
|   while_loop
|   do_loop
|   for_loop
|   expr_seq

expr_seq:
    "(" expr_semicolon_list ")"

expr_semicolon_list:
    expr
|   expr TK_SEMICOLON expr_semicolon_list
|   expr TK_EOL expr_semicolon_list

if_expr:
    "if" expr "then" expr "else" expr
|   "if" expr "then" expr
|   "if" expr "do" expr

// etc.

这将仅解析仅使用newline作为表达式分隔符并且不会期望newline分散在程序其他位置的程序。

我的问题是：有什么方法可以告诉野牛将一个标记视为可选标记？对于野牛来说，这意味着：

• [如果找到newline令牌并且可以随其移动或减少，那么就这样做。
• 否则，请丢弃newline令牌并继续解析。

因为如果没有办法，我想到的唯一的解决方案是修改野牛语法文件，以便它期望到处都是newline。并改变规则的优先级，其中newline用作表达式分隔符。像这样：

%precedence EXPR_SEPARATOR   // high precedence

%%

// w = sequence of whitespace tokens
w:  %empty    // either nothing
|   TK_EOL w  // or newline followed by other whitespace tokens

expr:
    w simple_expr w
|   w if_expr w
|   w while_loop w
|   w do_loop w
|   w for_loop w
|   w expr_seq w

expr_seq:
    w "(" w expr_semicolon_list w ")" w

expr_semicolon_list:
    expr
|   expr w TK_SEMICOLON w expr_semicolon_list
|   expr TK_EOL w expr_semicolon_list           %prec EXPR_SEPARATOR

if_expr:
    w "if" w expr w "then" w expr w "else" w expr w
|   w "if" w expr w "then" w expr w
|   w "if" w expr w "do" w expr w

// etc.

但是这看起来很丑陋且容易出错，如果可能，我想避免这种解决方法。

Answer 1

我的问题是：有什么方法可以告诉野牛将一个标记视为可选标记？

不，没有。 （有关图表的详细说明，请参见下文。）

不过，解决方法虽然没有问题，但并不像您想象的那样丑陋。

为了简化操作，我假设可以说服词法分析器仅产生一个'\n'令牌，而不管程序文本中出现了多少连续的换行符，包括注释之间散布的情况空白行。可以使用复杂的正则表达式来实现，但是更简单的方法是使用开始条件来抑制\n令牌，直到遇到常规令牌为止。词法分析器的初始开始条件应该是抑制换行符的条件，以便程序文本开头的空白行不会造成任何混淆。

现在，关键的见解是我们不必在整个语法中插入“也许是换行符”标记，因为每条换行符都必须紧跟在某些真实标记之后。这意味着我们可以为每个终端添加一个非终端：

tok_id: ID | ID '\n'
tok_if: "if" | "if" '\n'
tok_then: "then" | "then" '\n'
tok_else: "else" | "else" '\n'
tok_do: "do" | "do" '\n'
tok_semi: ';' | ';' '\n'
tok_dot: '.' | '.' '\n'
tok_plus: '+' | '+' '\n'
tok_dash: '-' | '-' '\n'
tok_star: '*' | '*' '\n'
tok_slash: '/' | '/' '\n'
tok_caret: '^' | '^' '\n'
tok_open: '(' | '(' '\n'
tok_close: ')' | ')' '\n'
tok_openb: '[' | '[' '\n'
tok_closeb: ']' | ']' '\n'
/* Etc. */

现在，这只是将终端的使用替换为上面定义的相应非终端的问题。 （不需要w非终结符。）一旦这样做，bison就会报告刚才添加的非终结符定义中的许多shift-reduce冲突；它们仅在非终结点定义中有效。可能出现在表达式末尾的任何终端都将引发冲突，因为换行可能被终端的非终端包装或expr_semicolon_list产生吸收。我们希望换行成为expr_semicolon_list的一部分，因此我们需要添加以换行开头的优先级声明，以便其优先级低于任何其他标记。

这很可能适用于您的语法，但不是100％确定。基于优先级的解决方案的问题在于它们可能具有隐藏真正的减少班次-减少冲突问题的效果。因此，我建议在语法上运行bison并在添加优先级声明之前验证所有的shift-reduce冲突都出现在预期的位置（在包装产品中）。

---

为什么令牌后备并不像看起来那么简单

理论上，可以实现与您建议的功能相似的功能。 [注1]

但是这并非不平凡，因为LALR解析器构造算法组合状态的方式。结果是，解析器可能无法“知道”先行标记只有经过一次或多次缩减后才能移位。因此，当它确定先行令牌无效时，它已经执行了缩减操作，必须继续执行这些缩减操作才能继续解析，而无需先行令牌。

大多数解析器生成器通过删除与先行令牌相对应的错误操作（如果该令牌状态中的默认操作是减少操作，则使问题更加复杂）。效果再次是将错误的检测延迟到一次或多次无效的减少之后，但是这样做的好处是可以大大减少转换表的大小（因为不需要显式存储默认条目）。由于将在消耗更多输入之前检测到延迟错误，因此通常认为延迟是可以接受的。 （不过，Bison可以选择阻止这种优化。）

作为实际说明，这是一个非常简单的表达语法，仅包含两个运算符：

prog: expr '\n' | prog expr '\n'
expr: prod      | expr '+' prod
prod: term      | prod '*' term
term: ID        | '(' expr ')'

导致此状态图[注2]：

假设我们想用Python忽略换行符，允许输入

( 
  a + b
)

这意味着解析器必须忽略b之后的换行符，因为输入可能是

(
  a + b
  * c
)

（（如果我正确理解的话，在Python中可以使用Python，但没问题））

当然，如果输入未加括号，则换行符将被视为语句分隔符：

a + b
[查看状态图，我们可以看到解析器将在读取b之后以状态15结束，而不管表达式是否带有括号。在那种状态下，换行被标记为归约动作的有效提前行，因此将执行归约动作，大概为总和创建一个AST节点。只有在这种减少之后，解析器才会注意到对换行没有任何操作。如果现在丢弃换行符，则为时已晚。现在没有办法减小b * c使其成为和的操作数。

Bison确实允许您请求不合并状态的Canonical LR解析器。结果，状态机要大得多。如此之多，以至于Canonical-LR对于非玩具语法仍然不切实际。在上面的简单的由两个运算符组成的表达式语法中，要求Canonical LR解析器仅将状态计数从16增加到26，如下所示：

在Canonical LR解析器中，归约term: term '+' prod有两种不同的状态。状态16在顶层应用，因此，前行包括换行符，但不包含)括号内的解析器将改为到达状态26，其中)是有效的前行而换行符不是。因此，至少在某些语法中，使用Canonical LR解析器可以使预测更加精确。但是依赖于使用庞大的解析自动机的功能并不是特别实用。

一种替代方法是使解析器通过首先模拟归约操作以查看转换是否最终成功来对换行作出反应。如果您请求前瞻校正（%define parse.lac full），野牛将插入代码以精确地做到这一点。这段代码会产生大量开销，但是无论如何，许多人还是要求这样做，因为它会使详细的错误消息更加准确。因此，据我所知，当然有可能重新调整此代码的用途以进行令牌回退处理，但实际上没有人这样做。

注意：

1. 时不时出现类似的问题：如果不可能转移令牌，是否可以告诉野牛将令牌重新分类为后备令牌。 （这对于解析具有很多非保留关键字的SQL之类的语言很有用。）

[我使用Bison的-g选项生成了状态图：

bison -o ex.tab.c --report=all -g ex.y
dot -Tpng -oex.png ex.dot
为了生成标准LR，我将lr.type定义为canonical-lr：

bison -o ex_canon.c --report=all -g -Dlr.type=canonical-lr ex.y
dot -Tpng -oex_canon.png ex_canon.dot