无上下文语法用于识别行末空白符

Question

我正在尝试编写一个无上下文语法，以实现一个非常简单的功能——将字符串解析为交替出现的(1)行末空白和(2)其余所有内容的列表。例如：

This.first.line...\n..and.this....second.line\n.\n..and.final.line

（为了易读性，将空格" "展示为"."，将换行符展示为"\n"）。解析为：

"This.first.line", "...\n..", "and.this....second.line", "\n.\n..", "and.final.line"

我写了这个语法：

string = raw_start | newline_start
raw_start = raw_section [newline_start]
newline_start = newline_section [raw_start]
raw_section = {any_character_except_newline}
newline_section = {whitespace_except_newline} new_line {any_whitespace_character}

但是这并不正确，因为{any_character_except_newline}会消耗掉前导空格，当我希望它们与new_line_section一起被包括进去。

有没有可能说“消耗空格，除非它们紧挨着换行符”而不失去语法的上下文无关性？

- drhagen

Answer 1

当然，无上下文语言不是问题。 "行尾空格"和"其他所有内容"都是正则语言。

以下是正则表达式（正式的正则表达式，而不是“可识别某些‘regex’包”的表达式）。我们假设A是字母表，并定义：

<b>NOTSPACE</b> = { ∀x | x ∈ <b>A</b> ∧ x ≠ <kbd>NL</kbd> ∧ x ≠ <kbd>SPACE</kbd> }
<b>NOTEOL</b>   = { ∀x | x ∈ <b>A</b> ∧ x ≠ <kbd>NL</kbd> }
<b>EVERYTHING_ELSE</b> = { xωy | x,y ∈ <b>NOTSPACE</b> ∧ ω ∈ <b>NOTEOL</b><sup>*</sup> } ⋃ <b>NOTSPACE</b>
<b>EOL_WHITESPACE</b> = { ω<kbd>NL</kbd>γ | ω,γ ∈ {<kbd>SPACE</kbd>, <kbd>NL</kbd>}<sup>*</sup> }

这可以轻松转换成一个CFG。 （文本可能以不包括换行符的空格结束。 以下内容忽略了这种可能性，但很容易添加）：

S → Spaces
S → S Other
S → S EOL_WS
Spaces → ε
Spaces → Spaces [ ]
Other → [^ \n] Line [^ \n]
Other → [^ \n]
Line → ε
Line → Line [^\n]
EOL_WS → Spaces NL_Spaces
NL_Spaces → NL_Space
NL_Spaces → NL_Spaces NL_Space
NL_Space → [/n] Spaces
 

上述代码含糊不清，因为它没有强制要求 Other 和 EOL_WS 最大长度。这很容易修复，但是很繁琐，由于OP只需要CFG而非无歧义或LR(1) CFG，因此我就不做修改了。

- rici

---

对我来说，理解的关键是这一行代码 EVERYTHING_ELSE = { xωy | x,y ∈ NOTSPACE ∧ ω ∈ NOTEOL* }，并且认识到我必须要求 raw_section 中的最后一个字符是非空格字符。 - drhagen

@drhagen：很酷。修复了EOL_WHITESPACE定义中的错误。实际上，在那个规则中，ω可以简单地是SPACE*，但除非你关心歧义，否则没有区别。还修复了Other中的错误（我没有考虑它只是一个单独的非空格字符的可能性）。所有这些都证明了实际测试语法的重要性，在这种情况下我仍然没有做到:( - rici

Answer 2

这是对rici的精彩回答进行翻译，使用了我在问题中使用的EBNF格式：

string = raw_start | newline_start
raw_start = raw_section [newline_start]
newline_start = newline_section [raw_start]
raw_section = any_nonwhite_character [{any_character_except_newline} any_nonwhite_character]
newline_section = {whitespace_except_newline} new_line {any_whitespace_character}

关键是将raw_section的定义更改为要求其以非空白字符结尾。这个简单的语法不会匹配空字符串或以空格结尾的字符串，但这很容易解决。

- drhagen