用於識別行尾空白的上下文無關語法

我正在嘗試編寫一個上下文無關語法來執行一些非常簡單的操作 - 將一個字符串解析爲（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

用於識別行尾空白的上下文無關語法

回答

相關問題