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

我正在尝试编写一个上下文无关语法来执行一些非常简单的操作 - 将一个字符串解析为（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。

是否可以说“消耗空间，除非它们恰好在换行符之前”而不会丢失语法的上下文无关特性？

来源

2014-09-13 drhagen

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

作为参考，这里是正则表达式（正式规则，不能用一些“正则表达式”包识别）。我们假设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，所以我将放弃这一点。

来源

2014-09-13 18:41:30 rici

对我来说，理解的关键是'EVERYTHING_ELSE = {xωy| x，y∈NOTSPACE∧ω∈NOTEOL *}'，并认识到我必须要求'raw_section'中的最后一个字符是非空白字符。 – drhagen 2014-09-13 22:35:26

@drhagen：很酷。修复了'EOL_WHITESPACE'定义中的错误。实际上，在这个规则中，ω可以简单地称为“SPACE *”，但除非你关心模糊性，否则没有区别。还修复了“Other”中的错误（我没有留下它只是一个非空白字符的可能性）。所有这些都证明了实际测试语法的重要性，在这种情况下我仍然没有这样做：（ – rici 2014-09-14 03:47:40

这是罗杰斯国际商品指数的伟大答案翻译成我在我的问题中使用的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的定义，要求它与一个非白人字符结束。这个简单的语法不会匹配以空格结尾的空字符串或字符串，但很容易修复。

来源

2014-09-13 23:52:25 drhagen

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

回答

相关问题