换行敏感语言中 if 语句的语法
Grammar for if statements in newline sensitive language
我正在研究一种读起来很像英语的语言，但 if 语句的语法存在问题。如果您好奇，该语言的灵感来自 HyperTalk, so I'm trying to make sure I match all the valid constructs in that language. The sample input I'm using that demonstrates all the possible if constructs can be viewed here。有很多，所以我不想内联代码。
我已经从语法中删除了大多数其他结构以使其更易于阅读，但基本上语句如下所示：
start
: statementList
;
statementList
: '\n'
| statement '\n'
| statementList '\n'
| statementList statement '\n'
;
statement
: ID
| ifStatement
;
我看到的 shift/reduce 冲突在 ifStatement 规则中：
ifStatement
: ifCondition THEN statement
| ifCondition THEN statement ELSE statement
| ifCondition THEN statement ELSE '\n' statementList END IF
| ifCondition THEN '\n' statementList END IF
| ifCondition THEN '\n' END IF
| ifCondition THEN '\n' ELSE statement
| ifCondition THEN '\n' ELSE '\n' statementList END IF
| ifCondition THEN '\n' statementList ELSE statement
| ifCondition THEN '\n' statementList ELSE '\n' statementList END IF
// The following rules cause issues, but should be legal:
| ifCondition THEN statement newlines ELSE statement
| ifCondition THEN statement newlines ELSE '\n' statementList END IF
;
ifCondition
: IF expression
| IF expression '\n'
;
expression
: TRUE
| FALSE
;
newlines
: '\n'
| newlines '\n'
;
问题是我需要支持这个结构：
if true then statement # <- Any number of newlines
else statement
问题（据我所知）是没有足够的上下文来正确确定是移动 else，还是只减少 if true then statement 部分而不知道后面会发生什么（语句列表的末尾，或另一个语句）。这甚至可以解析吗？
我有要点 parser, scanner, and sample input 可以尝试。
要做到这一点出奇地困难，所以我尝试对这些步骤进行注释。有很多烦人的细节。
从本质上讲，这只是悬而未决的 else 歧义的一种表现，其解决方案是众所周知的（强制解析器始终移动 else）。下面的解决方案解决了语法本身的歧义，没有歧义。
我在这里使用的基本原则是几十年前在 Principles of Compiler Design by Alfred Aho and Jeffrey Ullman (the so-called "Dragon book", which I mention since its authors were recently granted the Turing award 中概述的原则，正是针对该原则和他们的其他有影响力的作品）。特别是，我使用术语“匹配”和“不匹配”（而不是“开放”和“封闭”，它们也很流行），因为这是我学习它的方式。
也可以使用优先声明来解决这个语法问题；事实上，这通常要简单得多。但在这种特殊情况下，使用运算符优先级并不容易，因为相关标记 (else) 之前可以有任意数量的换行标记。我很确定您仍然可以构建基于优先级的解决方案，但是使用明确的语法有很多优点，包括易于移植到不使用相同优先级算法的解析器生成器，以及它是可以进行机械分析。
解决方案的基本轮廓是将所有语句分为两类：
- “匹配”（或“封闭”）语句，在不可能用
else 子句扩展语句的意义上是完整的。 （换句话说，每个 if…then 都对应一个 else。）这些
- “不匹配”（或“开放”）语句，可以使用
else 子句进行扩展。 （换句话说，至少有一个 if…then 子句与 else 不匹配。）由于不匹配的语句是一个完整的语句，因此不能紧跟 else 标记；如果出现 else 标记，它会用于扩展声明。
一旦我们设法为这两类语句构造语法，只需要弄清楚else在歧义语法中的哪些用法中可以跟随statement。在所有这些上下文中，非终结符 statement 必须替换为非终结符 matched-statement，因为只有匹配的语句可以跟在 else 之后而不与之交互。在其他情况下，else 不能是下一个标记，任何一类陈述都是有效的。
所以基本语法风格是（取自龙书）：
stmt → matched_stmt
| unmatched_stmt
matched_stmt → "if" expr "then" matched_stmt "else" matched_stmt
| other_stmt
unmatched_stmt → "if" expr "then" matched_stmt "else" unmatched_stmt
| "if" expr "then" stmt
other_stmt 不是条件语句。或者，更准确地说，不是以 stmt.
结尾的复合语句
据我所知，在 Hypertalk 中，if 语句是唯一可以以语句结尾的复合语句。其他复合语句以 end X 精确终止，这有效地关闭了语句。但是在其他语言中，比如C，有各种各样的复合语句，其中大部分需要根据它们的终止子语句是（递归地）匹配还是不匹配来分为“匹配”和“不匹配”。
这里我要注意的一件事是 if 语句的 if…then…else 部分在语法上类似于括号中的前缀运算符。即matched_stmt和unmatched_stmt都类似于一元负的右递归规则：
unary → '-' unary
| atom
这又可以用扩展的 BNF 方言编写，它允许 Kleene stars 作为
unary → ('-')* atom
如果我们对 Aho&Ullman 的语法进行这种转换，我们最终会得到：
if_then_else → "if" expr "then" matched_stmt "else"
matched_stmt → (if_then_else)* other_stmt
unmatched_stmt → (if_then_else)* "if" expr "then" stmt
这使得如何使用自上而下的递归下降解析器实现此语法变得相当清楚。 （需要一些左因式分解，但它最终仍然类似于一元负语法。）我不打算在这个答案中进一步发展这个想法，但我认为 EBNF 转换有助于指导直觉这个语法实际上是如何解开 else 的。
它对弄清楚如何处理换行也很有帮助。关键的见解（对我而言）是语句必须以换行符结尾。一个例外是 if 命令的精简单行版本。但是该异常仅发生在 else 标记之前（并且仅当它在同一行中匹配的 then 时）。在这个语法中，这种情况是用 inner-matched 非终结符实现的，这得益于单行语句（如 do-statement）缺少终止换行符这一事实。在 matched (single-statement NL) 的递归基本情况中添加了终止单行语句的换行符；这是唯一需要处理的地方。多行复合语句都用终止换行符定义（例如，参见 repeat-statement）。
其余的大部分并发症都与句法形式的多样性有关。唯一真正有趣的是在行尾的 then 标记之后处理块。该块可以通过两种方式终止：
- 有
end if 行，没有 else 子句。这被视为“匹配”案例，因为它显然不能用 else 子句扩展。
- 带有
else 子句（可以是单行 else 或块 else，其中 else 标记位于行尾） .但这里可能存在歧义；如果块中的最后一个语句是不匹配的 if，那么 else 行应该扩展该语句，而不是终止块。这与 matched/unmatched 逻辑的其余部分并没有什么不同；为了实现它，我创建了两个不同的 block 非终结符，一个以匹配的语句结尾，另一个以不匹配的语句结尾。然后，像往常一样，只能在 else. 之前使用匹配的块
(我发现 bison 3.7.6 中的新反例生成器在这里非常有用；我最初的尝试只是使用 block 因为我没有注意到歧义。但这是一个真正的歧义，而且它导致 shift-reduce 冲突，其起源似乎很神秘。一旦我看到反例生成器生成的反例——它显示冲突发生在 block 之后的 if-then ——问题变得很多更明显。）
matched-block和unmatched-block之间的交替是语法产生式和状态机之间对应关系的一个简单例子。两个非终结符表示一个非常简单的状态机中的两个状态，其状态记录一个位：最后一条语句是否匹配。非终结符必须是右递归的才能工作，这与构建 LALR(1) 语法的通常的“首选左递归”启发式有所不同。
好的，由于前言太长，下面是语法。为了紧凑化，我将表达式简化为变量和布尔常量，只包含一个简单的语句（do expr）并且只包含一个其他复合语句 (repeat until expr / block / end repeat). （最后一个作为占位符。）
program : block
block : %empty
| matched-block
| unmatched-block
NL : '\n'
| NL '\n'
matched-block
: block matched
unmatched-block
: block unmatched
simple-statement
: "do" expression
repeat-statement
: "repeat" "until" expression NL block "end" "repeat" NL
matched : if-then matched else-matched
| if-then inner-matched else-matched
| if-then NL matched-block else-matched
| if-then NL else-matched
| if-then NL block "end" "if" NL
| repeat-statement
| simple-statement NL
inner-matched
: %empty
| simple-statement
| if-then inner-matched "else" inner-matched
unmatched
: if-then matched
| if-then unmatched
| if-then inner-matched "else" unmatched
| if-then matched "else" unmatched
if-then : "if" expression NL "then"
| "if" expression "then"
else-matched
: "else" NL block "end" "if" NL
| "else" matched
expression
: ID
| "true"
| "false"
上一个答案（原问题，仅在 edit history 中可见）
之间有明显的歧义
ifCondition THEN statement EOL ELSE statement
和
ifCondition THEN EOL statementList ELSE statement
回想一下
statement: %empty
statementList: statement
结果statement和statementList都可以推导出空序列。所以以上两个对ifStatement的产生式都可以推导出：
ifCondition THEN EOL ELSE statement
解析器无法知道 EOL 之前是空的 statement 还是后面是空的 statementList。 （您可能不关心选择了哪一个，但解析器对这种决定很着迷。）
可空产品通常有问题。尽可能避免使用它们。不要让 statement 派生为空，而是通过添加省略可选语句的规则来明确指示空语句的位置。并考虑重写 statementList，使其必须以 EOL 结尾，我认为这无论如何都是你的意图（但也许我错了）。
我正在研究一种读起来很像英语的语言，但 if 语句的语法存在问题。如果您好奇，该语言的灵感来自 HyperTalk, so I'm trying to make sure I match all the valid constructs in that language. The sample input I'm using that demonstrates all the possible if constructs can be viewed here。有很多，所以我不想内联代码。
我已经从语法中删除了大多数其他结构以使其更易于阅读，但基本上语句如下所示：
start
: statementList
;
statementList
: '\n'
| statement '\n'
| statementList '\n'
| statementList statement '\n'
;
statement
: ID
| ifStatement
;
我看到的 shift/reduce 冲突在 ifStatement 规则中：
ifStatement
: ifCondition THEN statement
| ifCondition THEN statement ELSE statement
| ifCondition THEN statement ELSE '\n' statementList END IF
| ifCondition THEN '\n' statementList END IF
| ifCondition THEN '\n' END IF
| ifCondition THEN '\n' ELSE statement
| ifCondition THEN '\n' ELSE '\n' statementList END IF
| ifCondition THEN '\n' statementList ELSE statement
| ifCondition THEN '\n' statementList ELSE '\n' statementList END IF
// The following rules cause issues, but should be legal:
| ifCondition THEN statement newlines ELSE statement
| ifCondition THEN statement newlines ELSE '\n' statementList END IF
;
ifCondition
: IF expression
| IF expression '\n'
;
expression
: TRUE
| FALSE
;
newlines
: '\n'
| newlines '\n'
;
问题是我需要支持这个结构：
if true then statement # <- Any number of newlines
else statement
问题（据我所知）是没有足够的上下文来正确确定是移动 else，还是只减少 if true then statement 部分而不知道后面会发生什么（语句列表的末尾，或另一个语句）。这甚至可以解析吗？
我有要点 parser, scanner, and sample input 可以尝试。
要做到这一点出奇地困难，所以我尝试对这些步骤进行注释。有很多烦人的细节。
从本质上讲，这只是悬而未决的 else 歧义的一种表现，其解决方案是众所周知的（强制解析器始终移动 else）。下面的解决方案解决了语法本身的歧义，没有歧义。
我在这里使用的基本原则是几十年前在 Principles of Compiler Design by Alfred Aho and Jeffrey Ullman (the so-called "Dragon book", which I mention since its authors were recently granted the Turing award 中概述的原则，正是针对该原则和他们的其他有影响力的作品）。特别是，我使用术语“匹配”和“不匹配”（而不是“开放”和“封闭”，它们也很流行），因为这是我学习它的方式。
也可以使用优先声明来解决这个语法问题；事实上，这通常要简单得多。但在这种特殊情况下，使用运算符优先级并不容易，因为相关标记 (else) 之前可以有任意数量的换行标记。我很确定您仍然可以构建基于优先级的解决方案，但是使用明确的语法有很多优点，包括易于移植到不使用相同优先级算法的解析器生成器，以及它是可以进行机械分析。
解决方案的基本轮廓是将所有语句分为两类：
- “匹配”（或“封闭”）语句，在不可能用
else子句扩展语句的意义上是完整的。 （换句话说，每个if…then都对应一个else。）这些 - “不匹配”（或“开放”）语句，可以使用
else子句进行扩展。 （换句话说，至少有一个if…then子句与else不匹配。）由于不匹配的语句是一个完整的语句，因此不能紧跟else标记；如果出现else标记，它会用于扩展声明。
一旦我们设法为这两类语句构造语法，只需要弄清楚else在歧义语法中的哪些用法中可以跟随statement。在所有这些上下文中，非终结符 statement 必须替换为非终结符 matched-statement，因为只有匹配的语句可以跟在 else 之后而不与之交互。在其他情况下，else 不能是下一个标记，任何一类陈述都是有效的。
所以基本语法风格是（取自龙书）：
stmt → matched_stmt
| unmatched_stmt
matched_stmt → "if" expr "then" matched_stmt "else" matched_stmt
| other_stmt
unmatched_stmt → "if" expr "then" matched_stmt "else" unmatched_stmt
| "if" expr "then" stmt
other_stmt 不是条件语句。或者，更准确地说，不是以 stmt.
据我所知，在 Hypertalk 中，if 语句是唯一可以以语句结尾的复合语句。其他复合语句以 end X 精确终止，这有效地关闭了语句。但是在其他语言中，比如C，有各种各样的复合语句，其中大部分需要根据它们的终止子语句是（递归地）匹配还是不匹配来分为“匹配”和“不匹配”。
这里我要注意的一件事是 if 语句的 if…then…else 部分在语法上类似于括号中的前缀运算符。即matched_stmt和unmatched_stmt都类似于一元负的右递归规则：
unary → '-' unary
| atom
这又可以用扩展的 BNF 方言编写，它允许 Kleene stars 作为
unary → ('-')* atom
如果我们对 Aho&Ullman 的语法进行这种转换，我们最终会得到：
if_then_else → "if" expr "then" matched_stmt "else"
matched_stmt → (if_then_else)* other_stmt
unmatched_stmt → (if_then_else)* "if" expr "then" stmt
这使得如何使用自上而下的递归下降解析器实现此语法变得相当清楚。 （需要一些左因式分解，但它最终仍然类似于一元负语法。）我不打算在这个答案中进一步发展这个想法，但我认为 EBNF 转换有助于指导直觉这个语法实际上是如何解开 else 的。
它对弄清楚如何处理换行也很有帮助。关键的见解（对我而言）是语句必须以换行符结尾。一个例外是 if 命令的精简单行版本。但是该异常仅发生在 else 标记之前（并且仅当它在同一行中匹配的 then 时）。在这个语法中，这种情况是用 inner-matched 非终结符实现的，这得益于单行语句（如 do-statement）缺少终止换行符这一事实。在 matched (single-statement NL) 的递归基本情况中添加了终止单行语句的换行符；这是唯一需要处理的地方。多行复合语句都用终止换行符定义（例如，参见 repeat-statement）。
其余的大部分并发症都与句法形式的多样性有关。唯一真正有趣的是在行尾的 then 标记之后处理块。该块可以通过两种方式终止：
- 有
end if行，没有else子句。这被视为“匹配”案例，因为它显然不能用else子句扩展。 - 带有
else子句（可以是单行else或块else，其中else标记位于行尾） .但这里可能存在歧义；如果块中的最后一个语句是不匹配的if，那么else行应该扩展该语句，而不是终止块。这与 matched/unmatched 逻辑的其余部分并没有什么不同；为了实现它，我创建了两个不同的block非终结符，一个以匹配的语句结尾，另一个以不匹配的语句结尾。然后，像往常一样，只能在else. 之前使用匹配的块
(我发现 bison 3.7.6 中的新反例生成器在这里非常有用；我最初的尝试只是使用 block 因为我没有注意到歧义。但这是一个真正的歧义，而且它导致 shift-reduce 冲突，其起源似乎很神秘。一旦我看到反例生成器生成的反例——它显示冲突发生在 block 之后的 if-then ——问题变得很多更明显。）
matched-block和unmatched-block之间的交替是语法产生式和状态机之间对应关系的一个简单例子。两个非终结符表示一个非常简单的状态机中的两个状态，其状态记录一个位：最后一条语句是否匹配。非终结符必须是右递归的才能工作，这与构建 LALR(1) 语法的通常的“首选左递归”启发式有所不同。
好的，由于前言太长，下面是语法。为了紧凑化，我将表达式简化为变量和布尔常量，只包含一个简单的语句（do expr）并且只包含一个其他复合语句 (repeat until expr / block / end repeat). （最后一个作为占位符。）
program : block
block : %empty
| matched-block
| unmatched-block
NL : '\n'
| NL '\n'
matched-block
: block matched
unmatched-block
: block unmatched
simple-statement
: "do" expression
repeat-statement
: "repeat" "until" expression NL block "end" "repeat" NL
matched : if-then matched else-matched
| if-then inner-matched else-matched
| if-then NL matched-block else-matched
| if-then NL else-matched
| if-then NL block "end" "if" NL
| repeat-statement
| simple-statement NL
inner-matched
: %empty
| simple-statement
| if-then inner-matched "else" inner-matched
unmatched
: if-then matched
| if-then unmatched
| if-then inner-matched "else" unmatched
| if-then matched "else" unmatched
if-then : "if" expression NL "then"
| "if" expression "then"
else-matched
: "else" NL block "end" "if" NL
| "else" matched
expression
: ID
| "true"
| "false"
上一个答案（原问题，仅在 edit history 中可见）
之间有明显的歧义ifCondition THEN statement EOL ELSE statement
和
ifCondition THEN EOL statementList ELSE statement
回想一下
statement: %empty
statementList: statement
结果statement和statementList都可以推导出空序列。所以以上两个对ifStatement的产生式都可以推导出：
ifCondition THEN EOL ELSE statement
解析器无法知道 EOL 之前是空的 statement 还是后面是空的 statementList。 （您可能不关心选择了哪一个，但解析器对这种决定很着迷。）
可空产品通常有问题。尽可能避免使用它们。不要让 statement 派生为空，而是通过添加省略可选语句的规则来明确指示空语句的位置。并考虑重写 statementList，使其必须以 EOL 结尾，我认为这无论如何都是你的意图（但也许我错了）。