解析 maxscript - 换行符问题
parsing maxscript - problem with newlines
我正在尝试使用官方 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 函数需要传递多个参数。
这是我拥有的 bison 输入文件的一部分：
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 分散在程序的其他位置。
我的问题是：有什么方法可以告诉 bison 将令牌视为可选令牌吗？对于野牛来说，这意味着：
- 如果您找到
newline 个令牌并且您可以用它移动或减少，那么就这样做。
- 否则只需丢弃
newline 标记并继续解析。
因为如果没有办法做到这一点，我能想到的唯一其他解决方案是修改 bison 语法文件，以便它期望那些 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.
然而，这看起来非常丑陋且容易出错，我想尽可能避免这种解决方案。
My question is: Is there some way to tell bison to treat a token as an optional token?
不，没有。 （有关图表的详细说明，请参见下文。）
不过，解决方法并不像您想象的那么难看，尽管它并非没有问题。
为了简化事情，我将假设可以说服词法分析器只生成一个 '\n' 标记，而不管程序文本中出现了多少个连续的换行符，包括以下情况空白行中散布着注释。这可以通过复杂的正则表达式来实现，但更简单的方法是使用开始条件来抑制 \n 标记，直到遇到常规标记。词法分析器的初始启动条件应该是抑制换行符的条件，这样程序文本开头的空行就不会混淆任何内容。
现在，关键的见解是我们不必在整个语法中插入 "maybe a newline" 标记，因为每个换行符都必须紧跟在某个真正的标记之后。这意味着我们可以为每个终端添加一个非终端：
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 解析器构造算法结合状态的方式。结果是解析器可能不会 "know" 在完成一次或多次归约之前不能移动先行标记。因此，当它发现先行标记无效时，它已经执行了缩减，必须撤消这些缩减才能在没有先行标记的情况下继续解析。
大多数解析器生成器通过删除与先行标记对应的错误操作来使问题复杂化，如果该标记的状态中的默认操作是减少的话。结果再次延迟错误检测，直到在一次或多次无用的减少之后，但它具有显着减少转换大小的好处 table （因为不需要显式存储默认条目）。由于延迟错误将在更多输入被消耗之前被检测到，因此延迟通常被认为是 acceptable。 （但是，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 中很好，但如果我理解正确的话，在 MAXScript 中则不行。）
当然，如果输入没有括号，换行符将被识别为语句分隔符：
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 解析器可以使预测更加精确。但是依赖于使用庞大的解析自动机的功能并不是特别实用。
一种替代方法是让解析器通过首先模拟缩减操作来查看换行是否最终会成功来对换行符做出反应。如果您请求 Lookahead Correction (%define parse.lac full)，bison 将插入代码来执行此操作。这段代码会产生很大的开销，但是很多人无论如何都会请求它，因为它可以使详细的错误消息更加准确。因此，当然可以重新利用此代码来进行令牌回退处理，但据我所知，实际上还没有人这样做过。
备注：
一个不时出现的类似问题是，如果没有可能转移令牌，您是否可以告诉 bison 将令牌重新分类为后备令牌。 （这对于解析像 SQL 这样有很多非保留关键字的语言很有用。）
我使用 Bison 的 -g 选项生成了状态图：
bison -o ex.tab.c --report=all -g ex.y
dot -Tpng -oex.png ex.dot
为了生成 Canonical 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
我正在尝试使用官方 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 函数需要传递多个参数。
这是我拥有的 bison 输入文件的一部分：
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 分散在程序的其他位置。
我的问题是：有什么方法可以告诉 bison 将令牌视为可选令牌吗？对于野牛来说，这意味着：
- 如果您找到
newline个令牌并且您可以用它移动或减少，那么就这样做。 - 否则只需丢弃
newline标记并继续解析。
因为如果没有办法做到这一点，我能想到的唯一其他解决方案是修改 bison 语法文件，以便它期望那些 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.
然而，这看起来非常丑陋且容易出错，我想尽可能避免这种解决方案。
My question is: Is there some way to tell bison to treat a token as an optional token?
不，没有。 （有关图表的详细说明，请参见下文。）
不过，解决方法并不像您想象的那么难看，尽管它并非没有问题。
为了简化事情，我将假设可以说服词法分析器只生成一个 '\n' 标记，而不管程序文本中出现了多少个连续的换行符，包括以下情况空白行中散布着注释。这可以通过复杂的正则表达式来实现，但更简单的方法是使用开始条件来抑制 \n 标记，直到遇到常规标记。词法分析器的初始启动条件应该是抑制换行符的条件，这样程序文本开头的空行就不会混淆任何内容。
现在，关键的见解是我们不必在整个语法中插入 "maybe a newline" 标记，因为每个换行符都必须紧跟在某个真正的标记之后。这意味着我们可以为每个终端添加一个非终端：
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 解析器构造算法结合状态的方式。结果是解析器可能不会 "know" 在完成一次或多次归约之前不能移动先行标记。因此，当它发现先行标记无效时，它已经执行了缩减，必须撤消这些缩减才能在没有先行标记的情况下继续解析。
大多数解析器生成器通过删除与先行标记对应的错误操作来使问题复杂化，如果该标记的状态中的默认操作是减少的话。结果再次延迟错误检测，直到在一次或多次无用的减少之后，但它具有显着减少转换大小的好处 table （因为不需要显式存储默认条目）。由于延迟错误将在更多输入被消耗之前被检测到，因此延迟通常被认为是 acceptable。 （但是，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 中很好，但如果我理解正确的话，在 MAXScript 中则不行。）
当然，如果输入没有括号，换行符将被识别为语句分隔符：
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 解析器可以使预测更加精确。但是依赖于使用庞大的解析自动机的功能并不是特别实用。
一种替代方法是让解析器通过首先模拟缩减操作来查看换行是否最终会成功来对换行符做出反应。如果您请求 Lookahead Correction (%define parse.lac full)，bison 将插入代码来执行此操作。这段代码会产生很大的开销，但是很多人无论如何都会请求它，因为它可以使详细的错误消息更加准确。因此，当然可以重新利用此代码来进行令牌回退处理，但据我所知，实际上还没有人这样做过。
备注：
一个不时出现的类似问题是，如果没有可能转移令牌，您是否可以告诉 bison 将令牌重新分类为后备令牌。 （这对于解析像 SQL 这样有很多非保留关键字的语言很有用。）
我使用 Bison 的
-g选项生成了状态图：bison -o ex.tab.c --report=all -g ex.y dot -Tpng -oex.png ex.dot为了生成 Canonical 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