JParser (2) Conditional Derivation Grammar

앞선 포스팅에서 RE와 CFG로 문법을 정의하는 방식의 한계점에 대해 이야기했고 이 문제를 해결하기 위해 내가 Conditional Derivation Grammar라는 것을 고안했다고 했다. 이 포스팅에서는 이 Conditional Derivation Grammar, 나는 줄여서 CDG라고 부르는 것에 대해 이야기해보자.

처음 내가 파서를 만들려고 했던 것은 자바스크립트 프로그램 분석기를 만들기 위해서였다. 인터프리터든, 컴파일러든, 프로그램 분석기든 가장 먼저 필요한 것이 파서이기 때문이다. 실은 자바스크립트 파서는 시중에 엄청나게 많고, 그 중 아무거나 하나 갖다 써도 될 일이었다. 그때는 자바스크립트 문법이 변경될 가능성이 높다는 실질적 문제가 있기는 했지만, 아마 문법이 변경되더라도 내가 만든 파서보다 남이 만든 파서가 변경된 문법에 더 잘 대응해주었을 가능성이 높다. 그래서 사실 진짜 파서 제너레이터를 만들기로 한 것은 자바스크립트 분석기 프로젝트 자체가 재미로 하는 나의 사이드 프로젝트였기 때문에 기왕 사이드 프로젝트를 하는 김에 파서부터 만들어보자, 기왕 파서를 만들거면 파서 제너레이터부터 만들어보자 라는 이상한 논리 전개의 결과였다.

그런데 문제는 파서 제너레이터를 만들겠다고 덤볐을 때에는, 이전 포스팅에서 설명한 lex와 yacc의 차이를 인지하지 못하고 있었고, 기왕 파서를 만드는 김에 스캐닝 과정 없이 한번에 파싱하도록 만들어보자는 생각을 했던 것이다. 그때는 그냥 단순하게 regular grammar는 CFG의 하위 개념이니까 CFG 파서 제너레이터를 만들면 RG는 당연히 될 거라고 생각했다. lex와 yacc이 분리된 이유는 그냥 개발 편의성 정도라고만 생각했었다.

그래서 중간중간 짬을 내서 몇 주에 걸쳐 CFG 파서 제너레이터를 만들고 자바스크립트 문법을 입력한 다음 테스트를 해보는데 (이때도 파싱 알고리즘들을 잘 몰라서 공부도 하고 여러 시행착오를 겪었는데 오래 전 일이라 잘 기억이 안 난다) 원하는 결과가 나오질 않았다. var i = 1; 같은 단순한 문장도 해석을 못했는데, 그 이유를 자세히 살펴보니 v도 va도 var도 모두 Identifier로 인식하는게 문제였다. 한참을 고민한 끝에 CFG만으로는 자바스크립트의 문법을 정확히 표기할 수 없다는걸 깨달았다.

CFG에 어떤 기능을 새로 추가해야 하는지, 추가한다면 어떤식으로 추가해야 하는지를 처음엔 정확히 알 수 없어서 그것도 한참을 더 고민했다. lex에서 하는 것처럼 넌터미널의 derive 순서를 정하게 할까? 한 규칙을 시도해보고 실패하면 다른 규칙을 시도하도록 해야 할까? longest match를 기본 정책으로 할까? 나중에 알고 보니 Packrat 파서나 yacc같은 다른 파서나 파서 제너레이터에서 이런 유사한 방식을 실제로 사용하기도 했다.

많은 고민과 시행착오 끝에 나는 CFG에 5가지의 새로운 기능을 추가하면 기존의 방식처럼 스캐너와 파서를 분리하지 않고도 꽤 많은 일을 할 수 있겠다는 결론에 도달했다. 만들어진 것이 5가지의 새로운 기능을 추가한 Conditional Derivation Grammar, 줄여서 CDG였다. 추가된 5가지의 새로운 기능은 이렇다: longest, join, except, lookahead, lookahead except.

이 새로운 종류의 심볼들은 “확장 심볼”이라고 부르고, 다른 심볼 한 개 혹은 두 개를 argument로 받는 함수처럼 표현된다.

말로 들어서는 어려울 수 있다. 실제 사례를 보면서 이야기해보자.

longest 심볼

longest 심볼은 앞선 포스팅에서 살펴본 Identifier 매칭과 같은 경우에 유용하다.

Identifier = 'a-zA-Z_' Rest
Rest = ε
     | 'a-zA-Z0-9_' Rest

'a-zA-Z0-9_'는 a부터 z 사이의 글자, A부터 Z 사이의 글자, 0에서 9 사이의 글자와 _ 문자 중 하나에 매치되는 터미널 심볼이다. .라고 쓰면 모든 문자에 매치되는 심볼을 나타낸다.

실제 lex가 파싱해주는 문법은 다음과 같은 규칙을 추가한, 그리고 시작 심볼은 Tokens인 문법이라고 볼 수 있다.

Tokens = Token*
Token = Identifier

*는 그 앞의 심볼이 0번 이상 반복되는 것을 의미한다. +는 그 앞의 심볼이 1번 이상 반복됨을 의미하고, ?는 그 앞의 심볼이 한번 나타나거나 나타나지 않을 수도 있음을 의미한다.

위의 문법에 abc라는 입력이 들어오면 네가지 방식으로 해석될 수 있다. 1. a/b/c라는 세개의 토큰으로 해석되거나, 2. a/bc, 3. ab/c로 해석되거나, 4. abc라는 한 토큰으로 해석될 수 있다. 이렇게 한 입력에 대해 파싱 결과가 여러개인 경우를 모호하다(ambiguous)고 한다. 위의 Tokens 문법은 모호한 문법이다.

longest 심볼을 사용하면 이 문제를 해결할 수 있다. Identifier 심볼의 longest 심볼을 만들려면 Identifier를 <>로 감싸준다.

Tokens = Token*
Token = <Identifier>
Identifier = 'a-zA-Z_' Rest
Rest = ε
     | 'a-zA-Z0-9_' Rest

그러면 Identifier 심볼은 a에 매칭될 수 없다. a보다 긴 ab라는 매칭이 있기 때문이다. 같은 원리로 abc라는 매칭이 있기 때문에 ab에도 매칭될 수 없다. 그래서 longest 심볼을 사용하면 lex의 longest match 정책의 동작을 흉내낼 수 있다. longest의 내부에는 시퀀스가 들어갈 수도 있다. 즉 심볼이 여러개 들어갈 수도 있다. 그래서 위 문법을 아래와 같이 쓸 수도 있다.

Tokens = Token*
Token = Identifier
Identifier = <'a-zA-Z_' Rest>
Rest = ε
     | 'a-zA-Z0-9_' Rest

여기에 *를 사용하면 Rest 넌터미널 없이 Identifier의 규칙을 다음과 같이 간소화할 수도 있다.

Identifier = <'a-zA-Z_' 'a-zA-Z0-9_'*>

except 심볼

except 심볼은 앞서 살펴본 Identifier에서 if와 같은 키워드를 제외해야하는 경우에 유용하다. Identifier 외에 if나 for와 같은 키워드들도 토큰으로 처리하려기 위해 문법을 아래와 같이 수정해보자.

Tokens = Token*
Tokens = Identifier | Keyword
Identifier = <'a-zA-Z_' 'a-zA-Z0-9_'*>
Keyword = "if" | "for"

이 문법에 for라는 입력이 들어왔다고 해보자. 그럼 for는 Identifier의 규칙에도 부합하고 Keyword의 규칙에도 부합하기 때문에 두가지 모두로 해석이 가능하다. 즉 문법이 모호해진다. 이런 모호성을 해결하기 위해 대부분의 언어는 Keyword를 Identifier로 사용할 수 없도록 한다. 이럴때 except 심볼을 사용할 수 있다.

Tokens = Token*
Token = Identifier | Keyword
Identifier = <'a-zA-Z_' 'a-zA-Z0-9_'*>-Keyword
Keyword = "if" | "for"

이렇게 쓰면 for나 if라는 이름은 <'a-zA-Z_' 'a-zA-Z0-9_'*>라는 심볼에도 매칭될 수 있지만 -Keyword라는 조건이 붙어있어서 Identifier로 매칭되지 않고 Keyword로만 매칭된다.

join 심볼

앞서 except 심볼을 설명하면서 본 문법에는 사실 문제가 있다. ifx와 같은 입력이 들어오면 해석이 모호해지는 것이다. ifx라는 입력에 대해 우리가 원하는 결과는 ifx라는 하나의 Identifier일텐데, 위의 문법에서는 ifx라는 하나의 Identifier로 해석도 가능하지만, if라는 Keyword와 바로 따라 이어지는 x라는 Identifier의 두 개의 토큰으로도 해석이 가능해지기 때문이다.

이런 문제는 문법을 다음과 같이 join 심볼을 사용해서 해결할 수 있다.

Tokens = Token*
Token = Identifier | Keyword
Identifier = Word-Keyword
Keyword = ("if" | "for")&Word
Word = <'a-zA-Z_' 'a-zA-Z0-9_'*>

기존 Identifer 넌터미널의 RHS에서 실제 이름 규칙을 나타내는 일부를 Word이라는 별도의 넌터미널로 분리했고, Keyword 넌터미널의 RHS에 &Word라는 조건을 추가했다. 이렇게 수정하면 ifx라는 입력에 대해서 if부분이 Keyword의 "if"라는 조건에 부합되기는 하지만 if가 Word에 매칭되지는 않기 때문에(if보다 더 긴 ifx라는 매칭이 존재하기 때문) if를 Keyword로 해석하지 않는다. 그래서 ifx라는 입력은 하나의 토큰으로 인식되고 모호성이 제거된다.

이 join 심볼은 의미적으로 except 심볼의 반대 의미에 해당한다고 볼 수도 있겠다.

위와 같은 패턴은 CDG를 이용해 실제 문법을 정의할 때 매우 흔히 사용된다. 자세한 사용례는 뒤에서 좀더 자세히 이야기해보자.

lookahead와 lookahead except 심볼

join과 except가 서로 반대의 의미를 갖는 것처럼, lookahead와 lookahead except 심볼도 정 반대의 의미를 갖는다. lookahead 심볼은 ^를 앞에 붙이고 lookahead except 심볼은 !를 앞에 붙인다. 이 기호들은 매우 임의로 정한 것이라 특별한 의미가 있지는 않다. (심볼의 이름도 썩 마음에 들지는 않는데 딱히 다른 대안이 있지도 않아서 그냥 쓰고 있다)

lookahead 심볼은 현재 위치에서부터 해당 심볼이 매칭되는 경우에만 전체적으로 매칭해주는 심볼이고, lookahead except 심볼은 그 반대의 기능을 하는 심볼이다. lookahead except 심볼을 사용하는 예를 들어보자.

Tokens = Token*
Token = Identifier | Keyword
Identifier = !Keyword Word
Keyword = ("if" | "for")&Word
Word = <'a-zA-Z_' 'a-zA-Z0-9_'*>

위에서 join 심볼을 설명하면서 보았던 문법에서 Identifier의 RHS를 Word-Keyword에서 !Keyword Word으로 바꾸었다. 이렇게 되면 if라는 입력이 들어왔을 때 이 입력은 Word에 매칭될 수 있긴 하지만, !Keyword라는 조건때문에 Identifier가 될 수는 없게 된다.

그 앞의 문법과 비교해보면, ifx라는 입력이 들어왔을 때 except 심볼을 사용하는 위의 문법의 경우, ifx는 "if" | "for"에 매칭될 수 없기 때문에 if를 지나 x까지 포함하는 ifx는 Identifier가 될 수 있지만, 이 문법에서는 한 번 !Keyword 조건이 만족되면 그 이후로 뭐가 나와도 Identifier 심볼로 매칭될 수는 없게 되어 ifx는 이 문법으로는 해석할 수 없는 입력이 된다는 차이점이 있다.

이 기능은 자바스크립트 문법 정의에 “lookahead except”라는 조건이 붙은 부분이 있어서 넣었던 것이었다. (최신 문법 정의에도 $lookahead \notin$ 와 같은 식으로 자주 등장한다) 그리고 lookahead except를 넣으려니 그 반대에 해당하는 lookahead도 있어야할 것 같아서 추가했다. 하지만 그간의 경험상으론 실제로 사용할 일이 그렇게 많지는 않았다. 다만 lookahead except는 end of file(줄여서 EOF), 즉 입력의 마지막을 !.같은 식으로 나타낼 수 있어서 유용하게 사용된다. 다음 포스팅에서는 이런 기능을 포함해 CDG로 문법을 정의할 때 흔히 사용되는 팁을 몇가지 살펴보자.

잘못된 문법

그런데 CDG가 태생적으로 처리할 수 없는 종류의 문법이 있다. 다음의 문법을 보자.

S = !S 'ab' | 'a'

b라는 입력이 들어왔다고 생각해보자. 'ab' 라는 터미널 심볼이 b라는 입력을 받을 수 있지만 거기에는 !S라는 조건이 앞에 붙어 있다. b라는 입력이 !S라는 조건을 만족하는지 확인하려면 b라는 입력이 S라는 심볼에 매치될 수 있는지 알아야 한다. 그리고 b라는 입력이 S라는 심볼에 매치될 수 있는지 알려면 b라는 입력이 !S라는 조건을 만족하는지 확인해야 한다. 그리고 b라는 입력이 !S라는 조건을 만족하는지 확인하려면 b라는 입력이 S라는 심볼에 매치될 수 있는지 알아야 한다. …

이런식으로 확장 심볼에 의해 추가되는 조건을 확인하기 위해서는 해당 심볼의 결과를 알아야 하고, 그래서 무한 루프에 빠지는 현상이 생기는 문법을 illegal 문법이라고 부른다. jparser 구현체에 이런 문법을 주면 실제로 무한루프에 빠진다. 고치려면 고칠 수 있을 것 같지만 이런 문제는 일부러 만들려고 하는 경우가 아니면 생각보다 잘 생기지 않기 때문에 고치지 않고 있다..

전체 목차:

다음 포스팅에서는 CDG를 사용할때 흔히 사용되는 패턴들을 소개한다.

이 페이지에서 오류나 문제점을 발견하시면 이메일로 알려주시면 감사하겠습니다.
뒤로