줄 끝 공백을 인식하는 문맥없는 문법

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}은 줄 바꿈까지 이어지는 공백을 사용합니다.에 포함 된 공백을 원하면

문법의 문맥 자유 속성을 잃지 않고 "개행 전에 개행하지 않으면 공백을 소비"라고 말할 수 있습니까?

Answer 1

물론 컨텍스트 프리는 문제가되지 않습니다. "end-of-line 공백"과 "그 외 모든 것"은 일반 언어입니다.

다음은 정규 표현식입니다 (형식적으로 정규식이며 일부 '정규식'패키지에서는 인식 할 수 없음). 우리는 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는 요구하지 않기 때문에 그 자리에 남겨 둘 것입니다.

Answer 2

이것은 내가 내 질문에 사용되는 EBNF 형식으로 RICI의 큰 대답의 번역은 다음과 같습니다

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의 정의를 변경했다. 이 간단한 문법은 빈 문자열이나 공백으로 끝나는 문자열과 일치하지 않지만 수정하기 쉽습니다.