Rob Pike의 Sam에서 비롯된 구조적 정규 표현식 개념을 소개하고, Rust crate `structex`로 이를 일반 목적 엔진과 CLI 도구로 구현하는 방법을 다룬다.
x/fun and.*/ v/profit을 위한 구조적 정규 표현식 엔진 구현기
정규 표현식을 보다 보니 문득 "와, 이거 진짜 유용하긴 한데, 뭔가 더 있었으면 좋겠는데" 라고 생각해 본 적이 있다면, 이 글이 딱 당신을 위한 글이다!
잠깐만 시간을 내 달라. 여기에는 한 번쯤은 들여다 볼 만한 재미있는 내용이 꽤 있다. 아마 "세상에, 왜 이런 걸…" 하는 종류의 흥미일 수도 있지만, 어쨌든 한 번쯤 볼 가치는 있다.
지금부터 구조적(Structural) 정규 표현식의 즐거운 세계로 안내하겠다.
필수 XKCD.
Rob Pike가 Sam 텍스트 에디터에서 처음 도입하고, 1987년 논문에서[1] 더 자세히 다룬 구조적 정규 표현식(structural regular expressions) 은, 우리가 익숙한 정규 표현식을 조합해서 텍스트의 구조(structure) 를 더 쉽게 기술할 수 있게 해 주는 표기법과 의미론을 제공한다.
이 "조합"이라는 아이디어 덕분에, 검색 대상 텍스트를 점점 더 파고드는, 더 작고 이해하기 쉬운 표현식들을 체인으로 엮어 쓸 수 있다. 주된 목표는, 항상 줄(line) 단위로만 루프를 돌도록 강제되는 대신, 텍스트를 우리가 관심 있는 의미 있는 덩어리들로 쪼갤 수 있도록 해 주는 것이다.
구체적인 예를 보는 게 항상 이해에 도움이 된다. 간단한 것부터 시작해 보자. 아래 텍스트를 보고, 각 프로그래머의 이름과 그들이 선호하는 언어를 찾아보라.
textname: Alice occupation: programmer language of choice: Rust name: Bob language of choice: Go occupation: programmer name: Claire occupation: linguist language of choice: French
아마 답을 찾는 데 1–2초도 안 걸렸을 것이다. 그리고 각 레코드의 필드 순서가 제각각이라는 사실은 눈치 못 챘을 수도 있다.
이제, 이 정보들을 위 텍스트에서 추출하는 프로그램을 작성해 달라고 하면 어떨까?
별로 복잡한 프로그램은 아니다. 예를 들어, 아래 파이썬 스크립트 정도면 충분히 일을 해 낸다.
pythonwith open("haystack.txt", "r") as f: haystack = f.read() for chunk in haystack.split("\n\n"): if "programmer" in chunk: for line in chunk.split("\n"): if "name:" in line: name = line.split(": ")[1] elif "lang" in line: lang = line.split(": ")[1] print(f"{name} prefers {lang}") # 출력: # Alice prefers Rust # Bob prefers Go
하지만 이걸 정규 표현식 하나로 해결하려 들면 꽤 까다롭거나, 거의 불가능에 가깝다. Claire는 프로그래머가 아니기 때문에, 이름과 언어만을 직접 찾을 수는 없다. 설사 찾는다 하더라도, 이름과 언어를 쌍으로 뽑아야 하는데, 언어는 직업 줄 앞뒤 어느 쪽에도 올 수 있다. 그러니 하나의 정규식으로 모든 경우를 커버하려 들면 금방 엉망이 된다.
사실 우리가 원하는 건, 위 파이썬 스크립트의 논리(수동 문자열 조작은 빼고)다:
그리고 공교롭게도, 아래 구조적 정규 표현식[1]이 바로 그 일을 한다:
texty/\n\n/ g/programmer/ x/name: (.*)@*lang.*: (.*)/ p/{1} prefers {2}/
textAlice prefers Rust Bob prefers Go
나는 개인적으로 이게 꽤 멋지다고 생각한다.
Rob의 논문은 꼭 한 번 읽어 보기를 권한다. 겨우 6페이지밖에 안 되고, 정규 표현식 기반 도구들이 어떤 식의 문제에 부딪히는지, 그리고 새로운 접근법이 어떻게 도움이 될 수 있는지를 아주 잘 보여 준다.
논문에서는 자신들의 작업이 완성된 해법을 제시한다기보다, 흥미로운 문제들을 드러내고 다른 사람들이 이 아이디어들을 어디에 어떻게 응용할 수 있을지 생각해 보게 하는 것이 목적이라고 분명히 밝힌다.
그러니, 그런 관점에서: 이 아이디어들을 어떻게 더 발전시켜 볼 수 있을지 함께 살펴보자!
Pike가 Sam에서 사용한 문법은 반복(루프) 구조와 조건 필터를, 정규식 매치 결과에 대해 삭제, 치환, 삽입 같은 출력 및 편집 액션들과 결합한 것이었다. 그 뒤로도 몇 가지 구현이 있었는데, 특히 Pike의 또 다른 에디터 acme, vis, 그리고 내 에디터 ad가 있는데, 이들은 모두 조합용 연산자와, 각 매치마다 적용되는 편집 액션을 묶어서 제공하는 같은 접근을 따른다. (Sam 자체에는 에디터의 상태를 다루기 위한 추가 연산자들도 있었지만 여기서는 다루지 않는다.)
위 예제에서 봤듯이, 이 문법은 고전적인 정규 표현식에서 영감을 받아, 꽤나 간결하다. 연산자와 액션은 모두, 동작을 식별하는 단일 문자 하나와, 슬래시(/)로 둘러싼 인자를 받는 공통된 형태를 쓴다.
구조적 정규 표현식을 작성한다는 건, 결국 하나 이상의 연산자로 이루어진 파이프라인을 쓰고, 마지막에 그 파이프라인에서 발견된 매치들에 대해 수행할 액션을 붙이는 것이다. 처리는 전체 문자열(혹은 에디터라면 현재 선택 영역)을 선택된 텍스트로 두고 시작한다. 그 다음, 첫 번째 연산자를 실행해서 찾은 모든 매치를 다음 표현식으로 넘긴다. 이렇게 연산자들은 flat-map / filter 의미론으로 동작하고, 액션은 각 매치를 처리한 뒤 다음 매치로 넘어간다.
연산자의 인자는 언제나 정규 표현식 re[2]다:
x/re/ re의 각 매치마다, 뒤따르는 표현식을 실행한다y/re/ re의 각 매치 사이마다, 뒤따르는 표현식을 실행한다g/re/ re가 매치되면, 뒤따르는 표현식을 실행한다v/re/ re가 매치되지 않을 때 뒤따르는 표현식을 실행한다액션의 인자는 파일에 삽입할 텍스트다.[3]
a/text/ 매치 뒤에 text를 덧붙인다(append)i/text/ 매치 앞에 text를 삽입한다(insert)c/text/ 매치를 text로 교체한다(change)p/text/ text를 출력(print)한다d 매치를 삭제(delete)한다아까 봤던 표현식을 다시 보자:
texty/\n\n/ g/programmer/ x/name: (.*)@*lang.*: (.*)/ p/{1} prefers {2}/
각 줄을 차례로 보면서, 파이프라인이 입력 텍스트를 어떻게 잘게 쪼개서 우리가 원하는 답을 찾아내는지 따라가 보자.
y/\n\n/첫 번째 연산자는 입력 텍스트를 "split"하는 역할을 한다. 즉, 텍스트를 세 개의 블록으로 나눈다.
textname: Alice occupation: programmer language of choice: Rust
textname: Bob language of choice: Go occupation: programmer
textname: Claire occupation: linguist language of choice: French
g/programmer/다음으로, "programmer"라는 표현을 포함하는 블록만 남기도록 필터를 적용한다.
textname: Alice occupation: programmer language of choice: Rust
textname: Bob language of choice: Go occupation: programmer
x/name: (.*)@*lang.*: (.*)/그 다음에는 또 다른 정규 표현식으로 선택 범위를 좁히는데, 이번에는 서브매치(submatch) 를 추출해서 나중에 출력에 사용할 수 있도록 한다.
textname: (Alice) occupation: programmer language of choice: (Rust)
textname: (Bob) language of choice: (Go)
p/{1} prefers {2}/마지막으로, 추출한 서브매치를 사용해서 템플릿 문자열을 채우고 결과를 출력한다.
textAlice prefers Rust Bob prefers Go
멋지다!
하지만, Claire가 linguist라는 사실까지 같이 처리하고 싶다면 어떨까? 다행히도, 이를 도와줄 마지막 문법 요소가 하나 더 있다.
마지막 트릭은 여러 파이프라인을 중괄호로 묶는 것이다. 이렇게 하면, 중괄호 안의 개별 파이프라인을 병렬로 실행하도록 표시하게 된다. 각 파이프라인(브랜치)은 세미콜론으로 끝나며, 기본적으로는 액션으로 끝나는 다른 연산자 체인과 완전히 동일하게 동작한다. 차이점은, 파이프라인 상에서 바로 앞선 연산자가 만들어낸 각각의 매치를, 병렬 그룹의 모든 브랜치에 동시에 흘려보낸다는 것이다.
이제 원래 표현식을 병렬 그룹을 사용하도록 바꿔 보자. 입력을 블록으로 나누는 지점에서 그룹을 시작하고, 이번에는 "linguist"를 포함한 텍스트에 대해 동작하는 대체 파이프라인을 하나 더 추가하자.
texty/\n\n/ { g/programmer/ x/name: (.*)@*lang.*: (.*)/ p/{1} prefers {2}/; + g/linguist/ + x/name: (.*)@*lang.*: (.*)/ + p/{1} has no time for this nonsense, they're busy discussing {2}/; }
이 새로운 표현식을 실행하면, 기존 파이프라인에서 나왔던 출력에 더해, 두 번째 병렬 브랜치의 출력이 추가로 나온다.
textAlice prefers Rust Bob prefers Go Claire has no time for this nonsense, they're busy discussing French
이제 어느 정도는, 이런 시스템이 얼마나 강력한 도구가 될 수 있는지 감이 오기 시작했을 것이다. 텍스트 에디터에 내장하면, 이 표현식들은 꽤 유용한 작업들을 할 수 있는 작은 편집 언어(mini editing language)가 된다.
지금까지 예제에서는 출력만을 사용했다. 이번에는 편집을 해 보자. 새로운, 전혀 논쟁의 여지가 없는 텍스트를 입력으로 삼자.
textYou'll make a lot of people angry if you say that Vim is better than Emacs. (Really, we all know that Emacs is the best).
혹시 누가 기분 나빠하기 전에, 아래 구조적 정규 표현식을 사용하면, (그런 취향이라면) 이 텍스트를 에디터 종교 전쟁의 다른 편에 맞춰서 다시 쓸 수 있다.
text{ x/Emacs/ c/Vim/; x/Vim/ c/Emacs/; }
textYou'll make a lot of people angry if you say that Emacs is better than Vim. (Really, we all know that Vim is the best).
구조적 정규 표현식 안에서 병렬 그룹을 사용했기 때문에, Emacs와 Vim을 동시에 서로 교환할 수 있다. 덕분에 치환이 순차적으로 실행되면서 모든 게 "Emacs"로만 바뀌어 버리는, 너무나도 흔한 사고를 피할 수 있다.
지금까지 본 것들은 모두 원래 Sam 엔진과 그 파생 구현들에서 제공하는 기능이다. 텍스트 에디터에 내장된 편집 언어를 구현하기에는 이걸로도 충분하다. 하지만, 이걸 더 다양한 용도에 맞게 응용할 수 있는 범용 엔진으로 만들려면, 한 가지를 더 해야 한다.
그렇게 하려면, 시스템을 조금 더 쪼개야 한다.
연산자와 액션을 한 시스템 안에 뒤섞어 두는 대신, "관심 있는 구조를 찾아내는(intensify interesting structure)" 문제(연산자 부분)를 처리하는 일반 엔진을 따로 두고, 그 엔진이 찾아낸 구조를 사용하는 처리 로직(당신이 풀고 싶은 문제에 특화된 액션)으로 넘기면 된다. 결과적으로, 텍스트의 서브섹션에 나중에 처리할 수 있도록 태그를 붙이는(tagging) 형태가 된다.
여기서 structex가 등장한다. 최근에 ad 내부 엔진을 전면 개편하면서 함께 작업해 온 Rust 크레이트로, 지금까지 설명한 엔진을 구현하려는 시도다. 핵심 기능 외에도, 간단한 템플릿 엔진, 표현식 컴파일러의 동작을 설정하는 빌더 구조체, 필요하다면 원하는 정규식 엔진을 끼워 넣을 수 있도록 하는 트레이트 세트 등, 커스텀 엔진을 조금 더 쉽게 작성할 수 있게 도와주는 편의 기능들도 제공한다.
이제 structex를 사용해서, 처음에 봤던 grep 비슷한 예제(예쁘게 출력해 주는 것)를 실행할 수 있는 최소한의 CLI 도구를 어떻게 작성할 수 있는지 살펴보자. 로컬에 Rust 툴체인이 깔려 있다면, 새 프로젝트를 만들고 regex와 structex 크레이트를 추가해서 직접 실행해 볼 수 있다.
rustuse std::collections::HashMap; use structex::{Structex, template::Template}; fn main() -> Result<(), Box<dyn std::error::Error>> { // (1) let args: Vec<String> = std::env::args().skip(1).collect(); let se: Structex<regex::Regex> = Structex::new(&args[0])?; let haystack = std::fs::read_to_string(&args[1])?; // (2) let mut templates = HashMap::new(); for action in se.actions() { let arg = action.arg().unwrap(); templates.insert(action.id(), Template::parse(arg)?); } // (3) for caps in se.iter_tagged_captures(haystack.as_str()) { let id = caps.id().unwrap(); println!("{}", templates[&id].render(&caps)?); } Ok(()) }
여기서 무슨 일이 일어나는지 보자.
regex 크레이트를 쓴다. 두 번째 인자는 우리가 검색할 대상 문자열(haystack)로 읽어 들인다.이걸 실행하려면, 예전에 사용하던 표현식을 약간 수정해야 한다. 예제에서 쓰던 @ 메타 문자는 ad 엔진에 있는 기능으로, regex 크레이트에서는 지원하지 않는다. 다행히 (?:.|\n)으로 바꿔 주면 같은 효과를 얻을 수 있다[4]. (물론 문법은 훨씬 추해지지만!)
bash$ cargo run -- ' y/\n\n/ { g/programmer/ x/name: (.*)(?:.|\n)*lang.*: (.*)/ p/{1} prefers {2}/; g/linguist/ x/name: (.*)(?:.|\n)*lang.*: (.*)/ p/{1} has no time for this nonsense, they are busy discussing {2}/; }' haystack.txt Alice prefers Rust Bob prefers Go Claire has no time for this nonsense, they are busy discussing French
좋다!
하지만 두 번째 예제도 실행하고 싶다면 어떨까? Emacs와 Vim을 서로 바꾸던 그 예제 말이다. 거기서 우리가 원하는 의미론은 좀 다르다. sed에 더 가깝게, 기본적으로는 매치되지 않은 텍스트를 그대로 에코하고, 매치된 부분만 출력 스트림에서 수정하는 식이다.
그럴 경우에는 대략 아래와 같은 것이 필요하다.
rustuse std::collections::HashMap; use structex::{Structex, template::Template}; fn main() -> Result<(), Box<dyn std::error::Error>> { let args: Vec<String> = std::env::args().skip(1).collect(); let se: Structex<regex::Regex> = Structex::new(&args[0])?; let haystack = std::fs::read_to_string(&args[1])?; // (1) let mut templates = HashMap::new(); for action in se.actions() { if let Some(arg) = action.arg() { templates.insert(action.id(), Template::parse(arg)?); } } // (2) let mut pos = 0; for caps in se.iter_tagged_captures(haystack.as_str()) { let action = caps.action.as_ref().unwrap(); let id = action.id(); // (3) if caps.from() > pos { print!("{}", &haystack[pos..caps.from()]); } // (4) match action.tag() { 'd' => (), // 매치된 텍스트만 소비 'c' => print!("{}", templates[&id].render(&caps)?), 'i' => print!("{}{}", templates[&id].render(&caps)?, caps.as_slice()), 'a' => print!("{}{}", caps.as_slice(), templates[&id].render(&caps)?), tag => panic!("unknown action {tag}"), } // (5) pos = caps.to(); } // (6) if pos < haystack.len() { print!("{}", &haystack[pos..]); } Ok(()) }
이번에는 해야 할 일이 조금 더 많다.
d 삭제 액션)은 건너뛴다.후… 이제 시험해 보자.
bash$ cargo run -- '{ x/Emacs/ c/Vim/; x/Vim/ c/Emacs/; }' haystack2.txt You'll make a lot of people angry if you say that Emacs is better than Vim. (Really, we all know that Vim is the best).
지금까지는 잘 된다. 다른 액션들에 대한 지원도 추가했으니, 이것들도 테스트해 보자.
bash$ cargo run -- '{ n/a lot of / d; # 첫 번째 "a lot of "만 삭제 x/Emacs/ i/Gnu /; # 각 "Emacs" 앞에 "Gnu " 삽입 x/Vim/ a/ (or Vi)/; # 각 "Vim" 뒤에 " (or Vi)" 추가 }' haystack2.txt You'll make people angry if you say that Vim (or Vi) is better than Gnu Emacs. (Really, we all know that Gnu Emacs is the best).
잘 동작한다!
여기서 n 연산자는 아직 본 적이 없는 것인데, Sam 엔진 의미론에 내가 추가한 것이다. 이 연산자는 주어진 정규 표현식의 첫 번째 매치만을 "좁혀서(narrow)" 선택한다. 효과적으로는 sed의 고전적인 s/regex/replacement/와 비슷하지만, 고정된 치환 텍스트 대신, 추가 연산자를 더 붙이거나 원하는 액션을 사용할 수 있다는 점이 다르다.
지금까지 본 예제들에는 unwrap이 아주 많이 등장하고, 직접 조금만 실험해 봐도 금방 예상치 못한 동작과 크래시를 만나게 될 것이다. 좀 더 견고하게 만들려면, 허용할 표현식 형태를 제어하고, 각 매치에 연결된 액션을 다루는 방식을 더 신중하게 설계해야 한다.
structex 레포에는 여기서 본 두 프로그램의 좀 더 현실적인 버전이 sgrep과 ssed 예제로 포함되어 있다. 이 예제들은 또한 스트림 매칭을 지원하기 위해 ad의 정규식 엔진을 복사해 사용하며, 표준 입력뿐 아니라 지정한 파일들에 대해서도 실행할 수 있다. 이 글에서 소개한 아이디어가 마음에 든다면, 한 번 살펴보고 직접 액션을 추가해 보면서 어떤 도구들을 만들어 낼 수 있을지 실험해 보기를 권한다.
마지막으로, Rob Pike의 글에서 한 장을 더 빌려, 이 아이디어를 앞으로 어디로 가져갈 수 있을지에 대한 열린 문제와 가능성들을 짚어 보며 마무리하자. 우선, 성능을 개선할 수 있는 지점이 분명히 여럿 있다. 현재 설계는, 매칭 엔진과 매치에 대한 액션 적용을 분리하는 아이디어를 검증하고, 유연성을 확보하는 데 초점을 맞추고 있다. 이 표현식을 자동자(automata)로 컴파일해 직접, 효율적으로 실행하는 것도 이론상 충분히 가능해 보인다. 다만 그렇게 되면 더 이상 원하는 정규식 엔진을 가져다 쓸 수는 없을 것이다. 그럴 가치가 있을까? 잘 모르겠다. 하지만 언젠가 시도해 보면 재미있을 것 같다. Pike가 논문에서 제안했듯이, structex 기반 awk를 구현해 보는 것도 재밌을 것이다. 다만 솔직히 말해, 완전한 언어 하나를 구현할 만큼의 시간은 지금으로선 없을 것 같다.
어쨌든 여기까지다. 당신의 도구 상자에 추가할 묘한 새 도구 하나, 혹은, 전염병처럼 피해야 할 괴상한 물건 하나가 더 생긴 셈이다. 그래도 여기까지 읽었다면, 적어도 한 번쯤은 이걸 돌려 보고 싶은 마음은 조금 들었다고 믿고 싶다.
다음에 또 만날 때까지, 즐거운 해킹을!
1 <a id="true-any"></a>
이름과 언어 필드를 뽑는 표현식에서 사용된 @ 문자는 처음에는 조금 이상하게 보일 수 있다. 이것은 ad에서 사용하는 엔진에 추가된 메타 문자로, 일반적인 . ("임의의 문자") 메타 문자와 비슷하지만, 여기에 줄바꿈 문자까지 함께 매치한다. 이름 그대로 "true any"다.
2 <a id="operators"></a>
각 연산자에 사용된 문자는 처음 보면 다소 헷갈릴 수 있다. x는 "extract matches"의 줄임말이고, g는 "guard"이다(여기까지는 괜찮다). 한편 y는 "각 매치에서 split"을 의미하는데, 문자는 단지 x와 가까운 알파벳이라 골랐다. 그래도 v는 "inVerted match"로 외울 수 있다.
3 <a id="templating"></a>
Sam의 print는 템플릿을 지원하지 않았고, 여기서 보여 준 템플릿 문법은 이 글에서 소개하는 엔진에 특화된 최소한의 내장 시스템이다. 하지만, 더 표현력이 강한 템플릿 엔진이 필요하다면, 원하는 엔진으로 갈아끼우는 것은 아주 간단한 변경이다.
4 <a id="non-capturing"></a>
여기 괄호 안의 ?: 접두사는 그룹을 non-capturing으로 표시하기 위한 것이다. 이게 없으면 해당 그룹이 두 번째 캡처 그룹이 되어 버려서, {2} 템플릿 변수가 엉뚱한 값을 출력하게 된다!
5 <a id="no-misquote"></a>
이번 섹션 제목에 쓸 적당한 인용구가 떠오르지 않았다. 이런 식으로 끝내게 되어 미안하다.