用于识别行尾空格的上下文无关语法

Question

我正在尝试编写一个上下文无关语法来执行一些非常简单的操作\xe2\x80\x94，将字符串解析为（1）行尾空格和（2）其他所有内容的交替部分的列表。例如：

\n\n

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

\n\n

（为了可读性显示" "为"."和换行符"\\n"）被解析为

\n\n

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

\n\n

我写了这个语法：

\n\n

string = raw_start | newline_start\nraw_start = raw_section [newline_start]\nnewline_start = newline_section [raw_start]\nraw_section = {any_character_except_newline}\nnewline_section = {whitespace_except_newline} new_line {any_whitespace_character}\n

\n\n

但这是不正确的，因为{any_character_except_newline}当我希望将那些包含在new_line_section.

\n\n

是否可以说“使用空格，除非它们位于换行符之前”而不丢失语法的上下文无关属性？

\n

Answer 1

当然，上下文无关不是问题。“行尾空白”和“其他所有内容”都是常规语言。

作为参考，这里是正则表达式（正式的正则表达式，而不是“可通过某些‘正则表达式’包识别”）。我们假设这A是字母表，并定义：

NOTSPACE = { ∀x | x ∈ A ∧ x ≠ NL ∧ x ≠ SPACE }
NOTEOL   = { ∀x | x ∈ A ∧ x ≠ NL }
EVERYTHING_ELSE = { xωy | x,y ∈ NOTSPACE ∧ ω ∈ NOTEOL* } ⋃ NOTSPACE
EOL_WHITESPACE = { ωNLγ | ω,γ ∈ {SPACE, NL}* }

可以轻松将其转换为 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，所以我将其保留。