JParser (1) 파싱

오늘부터 내 필생의 역작..일지도 모를 JParser에 대해 소개 겸 자랑하는 포스팅 시리즈를 시작하려고 한다.

이 프로젝트를 이해하려면 우선 파싱이 무엇인지, 그리고 기존의 파싱 방법에 어떤 문제점이 있는지 이해해야 한다.

원래 parse라는 단어는 “문장을 문법적으로 분석하다”라는 뜻을 갖고 있다. 일반적으로 쓰이는 단어의 의미지만 컴퓨터에서도 동일한 의미로 쓰인다. 다만 컴퓨터에서는 문장, 문법, 분석과 같은 단어들을 좀더 엄밀하게 수학적으로 정의할 필요가 있다. 컴퓨터는 언제나 정확하게 정의된 동작만 수행할 수 있기 때문이다.

컴퓨터로 문법을 정의하기 위해서는 형식 문법(formal grammar)이라고 하는 것을 사용하게 된다. 형식 문법은 문법의 구성 요소를 터미널(terminal)과 넌터미널(nonterminal)로 나누고, 문장을 구성하는 규칙을 정의한다. 말로 들으면 되게 어려운데 이미 우리는 성문 종합 영어 따위의 영어 교습서를 배우면서 비슷한 내용을 살펴본 바 있다.

요새의 영어 교육에서는 그렇게 하지 않을 것 같지만, 과거 “영어의 정석”으로 통했던 성문 종합 영어나 맨투맨 종합 영어같은 책에서는 영어 문장은 5가지 형태로 나뉘어진다는 따위의 내용들을 가르쳤다. 주어 Subject를 나타내는 S, 동사 Verb를 나타내는 V, 목적어 Object를 나타내는 O, 보어 Complement를 나타내는 C 등의 기호를 사용해서 문장 1형식은 S+V(예를 들면 He left), 2형식은 S+V+C(예를 들면 She is Korean), 3형식은 S+V+O(예를 들면 They had lunch) 라고 가르치는 식이다.

여기서 S, V, O, C 따위가 넌터미널에 해당된다. 각 단어들은 터미널에 해당된다고 볼 수 있다. 그렇다면 (성문 종합 영어의 문장 구성 1, 2, 3 형식에 따르면) 문장 Sentence는 다음과 같이 정의할 수 있다

Sentence = S V | S V C | S V O

여기서 등장한 Sentence도 새로운 넌터미널이다. Sentence라는 넌터미널을 S, V로 치환하거나, S, V, C로 치환하거나, S, V, O로 치환할 수 있다는 뜻으로 |는 = 왼쪽 부분의 넌터미널을 여러가지 중 하나로 치환할 수 있음을 나타낸다. 이렇게 = 왼쪽에 나타난 패턴을 찾아 오른쪽에 나타난 패턴으로 변경하는 과정을 derive 혹은 produce라고 부른다.

하지만 위의 규칙만으로는 문장을 만들 수 없다. 왜냐하면 완성된 문장에는 넌터미널이 나와서는 안되기 때문이다. 위에서 예로 든 문장을 만들 수 있으려면 규칙을 더 추가해야 한다.

Sentence = S V | S V C | S V O
S = he | she | they
V = left | is | had
C = korean
O = lunch

이 규칙으로 위에서 예로 들었던 “He left”, “She is Korean”, “They had lunch”같은 문장을 만들어낼 수 있다. 예를 들면,

Sentence => S V => He V => He left

와 같은 순서로 변환할 수 있는 것이다. 하지만 여기엔 함정이 있다. 이 규칙들로는 다음과 같은 문장도 만들 수 있다는 것이다.

Sentence => S V O => They V O => They is O => They is lunch

“그들은 점심”이라는 말의 의미 자체가 넌센스라는 점은 차치하고서라도, 문법적으로 They라는 단어 뒤에 나오는 be동사는 is가 아니라 are여야 하므로 위의 규칙으로 만들어진 문장은 제대로된 영어 문장이 아니다. 즉, 위의 규칙은 정확한 영어 문법을 나타내지 못한다. 이런 복잡한 문제들을 해결하기가 어렵기 때문에 사실 한국어나 영어같은 자연어는 형식 문법으로 적기가 매우 어렵다.

하지만 우리가 흔히 사용하는 프로그래밍 언어는 대부분 위에서 설명한 것과 같은 구조로 정의할 수 있고, 그래서 대부분의 프로그래밍 언어는 위에서 본 것과 같은 형식 문법으로 문법을 정의한다(물론 일반 목적의 프로그래밍 언어 문법을 정의하는 것은 쉬운 일이 아니다). 이들은 수학적으로 엄밀히 정의할 수 있기 때문에 컴퓨터에서 정확하게 처리하는 것이 가능하기 때문이다.

형식 문법

형식 문법을 정의할 때는 네가지 요소를 정의해야 한다. 1. 넌터미널의 집합, 2. 터미널의 집합, 3. 시작 심볼(심볼은 터미널과 넌터미널을 통칭한다), 4. 그리고 규칙들의 집합이다. 위에서 만들어본 성문 종합 영어 1, 2, 3형식 문법의 경우, {Sentence, S, V, C, O}라는 넌터미널들이 사용되었고, {he, she, they, left, is, had, korean, lunch}라는 터미널들이 사용되었다. 시작 넌터미널은 Sentence였으며 규칙은 위에 적은 것과 같다.

우리가 위에서 적은 규칙에서는 ‘=’의 왼쪽, 즉 left-hand-side(LHS)에 넌터미널 하나만 적혀 있지만, 일반적인 formal grammar에서는 그런 제약이 없다. LHS에 심볼(넌터미널 및 터미널)이 하나만 올 필요도 업고, 넌터미널만 올 필요도 없다. 그렇게 규칙에 아무 제약이 없는 formal grammar를 우리는 chomsky hierarchy의 type 0 문법이라고 부른다.

만약 우리가 위에서 성문 종합 영어 문법을 만들때 했던 것처럼 LHS에 반드시 넌터미널 1개만 오는 문법을 우리는 Context-free grammar(CFG)라고 한다. 다른 말로는 Chomsky hierarchy type 2 문법이라고도 한다.

CFG처럼 LHS에는 넌터미널 1개만 오고, right-hand-side(RHS)에도 조건이 붙으면 Regular Grammar(RG) 혹은 Regular Expression(RE)라고 한다. RG에서는 RHS가 비어있거나, 터미널 심볼만 하나 오거나, 혹은 터미널 뒤에 넌터미널이 오는 길이 2의 시퀀스여야 한다. (이를 좌선형 문법이라고 한다. RHS가 비어있거나, 터미널 심볼만 하나 오거나, 넌터미널 뒤에 터미널이 오는 길이 2의 시퀀스인 문법들은 우선형 문법이라고 하며, 이것도 RG의 일종이다) Chomsky hierarchy type 3 문법이라고도 한다.

프로그래밍을 해보았다면 Regular Expression이란 이름은 꽤 익숙할 것이다. 스트링에서 RE로 정의된 특정 패턴을 만족하는 부분을 찾아낼 때 유용하게 사용된다. 방금 설명한 RE가 그 RE가 맞다. 물론 우리가 일반적으로 사용하는 regular expression은 a+처럼 간단하게 적지 위에서 본 것처럼 복잡하게 적지는 않지만 표현법이 근본적으로는 같은 것이다. 하지만 엄밀히 말하면 정확히 같은 것은 아닌데(?), 이 부분은 나중에 다시 이야기하기로 하자.

파싱

앞서 성문 종합 영어 문법에서 우리는 Sentence라는 시작 넌터미널에서부터 문장을 만드는 과정을 보았다. Sentence => S V => He V => He left. 파싱은 “He left”라는 최종 문장이 주어졌을 때, 시작 심볼에서 어떤 과정을 거치면 이 문장을 만들 수 있는지 역으로 알아내는 것을 말한다. 즉, 우리가 만들고자 하는 파서란 위에서 정의한 성문 종합 영어 문법과 “He left”라는 문장을 입력으로 주면 Sentence => S V => He V => He left를 출력으로 내는 프로그램인 것이다.

이제는 좀더 현실감있는 설명을 위해 성문 종합 영어 문법 대신 간단한 수식을 표현하기 위한 문법을 하나 정의해보자.

Expr = Term '+' Expr    ------ (1)
     | Term             ------ (2)
Term = Factor '*' Term  ------ (3)
     | Factor           ------ (4)
Factor = '0-9'          ------ (5)

앞으로는 별도로 설명이 없으면 가장 첫번째 규칙의 LHS가 시작 심볼이다. 이 문법은 덧셈과 곱셈으로 이루어진 수식을 나타낸다. 1+2*3과 같은 수식을 나타낼 수 있다.

Expr
(1) => Term + Expr
(4) => Factor + Expr
(5) => 1 + Expr
(2) => 1 + Term
(3) => 1 + Factor * Term
(5) => 1 + 2 * Term
(4) => 1 + 2 * Factor
(5) => 1 + 2 * 3

파서는 위의 문법과 1+2*3이라는 수식을 주면 위와 같은 derivation 과정을 찾아낸다. 흔히 파서 제너레이터라는 표현도 쓰는데, 파서 제너레이터는 문법을 주면 해당 문법으로 된 문장을 해석하는 파서를 생성하는 프로그램을 말한다. 즉 파서 제너레이터는 파서를 만드는 프로그램, 즉 프로그램을 만드는 프로그램인 것이다. JParser는 그 자체로 파서이기도 하고, 파서 제너레이터 기능도 갖고 있으므로 뒤에서 모두 다루게 될 것이다.

그런데 위에서처럼 derivation 과정을 나열하면 그 문장(1+2*3)의 구조를 제대로 파악하기가 어렵다. 그래서 흔히 다음과 같이 트리의 구조를 사용해서 나타낸다.

이런 트리를 파스 트리라고 부른다. 이 트리를 위아래를 뒤집고 각 노드가 입력 스트링에서 차지하는 영역을 표시하도록 그려보면 다음과 같이 나타낼 수 있다.

  1     +    2   *    3
                  [Factor]
         [Factor] [ Term ]
         [Factor *  Term ]
[Factor] [      Term     ]
[ Term ] [      Expr     ]
[ Term  +       Expr     ]
[          Expr          ]

표현은 조금 다르지만 위의 표현 방식들은 결국 모두 같은 의미이다. 앞으로는 주로 가장 마지막에 소개된 트리의 형태로 파싱 결과를 나타내게 될 것이다.

위의 derivation 과정에서는 현재 가장 왼쪽에 있는 넌터미널을 치환하면서 문장을 만들었다. 이런 방식을 left-most derivation이라고 한다. 반대로 right-most derivation도 가능하다. 하지만 파스 트리의 형태로 결과를 나타내면 derivation 순서는 사실 의미가 없다.

CFG와 RE

위에서 CFG의 한가지 예를 살펴보았는데, 실제로 프로그래밍 언어 문법을 정의할 때는 흔히 CFG와 RE를 함께 사용해 정의한다. 일반적으로 파서는 프로그램 소스코드가 입력으로 들어오면 1차적으로 RE를 이용해 소스코드를 토큰의 어레이로 바꾸고, 토큰의 어레이를 파스 트리로 바꾸는 두 단계로 파싱을 한다. 소스코드를 토큰 어레이로 바꾸는 1차 과정을 scanning, tokenizing, lexical analysis, lexing 등의 여러 이름으로 부르고 2차 과정은 파싱이라고 부른다. 1차 과정과 2차 과정을 합친 것도 파싱이라고 부르기 때문에 이름이 다소 헷갈릴 수 있는데, 일반적으로는 이 전체 과정을 파싱이라고 부르는 경우가 더 많다. 앞으로 구분이 필요한 경우 명시하겠다.

파서 제너레이터로 가장 유명한 lex와 yacc은 보통 결합해서 많이 사용되는데, lex는 토크나이저를 생성해주는 프로그램이고 yacc은 토큰 어레이를 파스 트리로 바꾸는 파서를 생성해주는 프로그램이다. lex는 RE의 형태로 된 문법 정의를 입력으로 받고, yacc은 CFG를 입력으로 받는다. 그래서 이 프로그램들을 사용하는 입장에서는 소스코드를 lex가 생성한 코드로 보내서 토큰 어레이로 바꾸고, 그렇게 나온 토큰 어레이를 yacc으로 보내서 파스 트리를 만드는 것으로 파싱을 수행한다. lex와 yacc와 거의 유사한 GNU 소프트웨어로 flex와 bison이 있다.

그런데 이런 구조에는 한계가 있다. 가장 먼저 지적해야 할 부분은 lex가 입력으로 RE를 받기 때문에 진짜 RE로 된 형식 문법을 따라 파싱하는 것으로 생각하기 쉽지만 실제로 그렇지 않다는 점이다. lex는 가장 긴 매칭을 가정한다는 점과 토큰 사이에 우선순위가 있다는 점이다. 조금 더 자세히 알아보자.

C에서부터 유래된 규칙으로, 많은 언어들에서 영어 알파벳이나 언더스코어(_)로 시작해서 영어 알파벳, 숫자, 언더스코어가 따라오는 이름을 변수나 함수의 이름으로 사용할 수 있다. 이런 규칙을 lex식 RE로 적으면 다음과 같이 적을 수 있다.

{a-zA-Z_}{a-zA-Z0-9_}*

이 규칙을 진짜 Regular grammar로 적으면 아래와 같은 형태가 될 것이다.

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

엡실론(ε)은 RHS가 빈 시퀀스임을 나타내는 기호이다. Regular grammar는 모든 규칙의 RHS가 빈 시퀀스이거나, 터미널 심볼만 하나 오거나, 혹은 넌터미널 뒤에 터미널이 오는 길이 2의 시퀀스여야 한다고 했는데, 위의 문법은 이 규칙을 모두 만족하기 때문에 RG이다. 우리는 lex가 이와 같은 규칙에 맞추어 입력 스트링을 토큰 어레이로 바꾼다고 생각하기 쉽다.

abc라는 입력이 들어왔다고 해보자. abc라는 스트링 전체는 물론 Identifier에 매칭될 수 있다. 하지만 문제는 a라는 한 글자도 Identifier가 될 수 있다는 점이다. abc라는 입력을 a라는 Identifier 뒤에 bc라는 Identifier가 따라오는 것으로 보아서 두 개의 Identifier 토큰으로 해석할 수도 있다. 그래서 위의 RG로 abc라는 입력을 해석할 수 있는 경우의 수는 4가지가 된다(a/b/c, a/bc, ab/c, abc), 입력 스트링이 길어질수록 기하 급수적으로 늘어난다.

이런 모호성을 제거하기 위해 lex는 longest match 정책을 사용한다. 즉, Identifier라는 토큰으로 매칭될 수 있는게 여러개 있을 경우 그 중 가장 긴 것을 사용한다는 의미이다. 위의 abc라는 입력에서 ab라는 Identifier가 a보다 길기 때문에 a로는 매칭되지 않는다고 판단하는 것이고, ab보다도 더 긴 abc라는 Identifier가 있기 때문에 ab는 인정하지 않는다는 것이다.

이 뿐만이 아니라 키워드를 구분하는 문제도 있다. if라는 단어는 거의 모든 언어에서 공통적으로 키워드로 사용하고 있고, 그래서 Identifier로는 사용할 수 없도록 막혀있는 것이 일반적이다. 하지만 위의 규칙에 따르면 if라는 단어는 Identifier의 규칙에 완벽하게 부합하는 단어이다. 그래서 이런 경우를 해결하기 위해 lex에서는 토큰간의 우선순위를 지정하도록 되어 있다.

다음은 위키피디아의 flex(GNU 버전 lex)에 대한 설명에서 발췌한 flex를 위한 RE 문법 정의의 일부이다.

digit [0-9]
letter [a-zA-Z]

%%
...
"if" { return IFSYM; }
...
{letter}({letter}|{digit})* {
                       yylval.id = strdup(yytext);
                       return IDENT;      }
...
%%
...

“if”에 대한 정의가 Identifier를 의미하는 IDENT에 대한 정의보다 앞에 있다. 이런 경우 lex는 두 개 이상의 토큰에 매칭되는 문자열에 대해서 앞서 정의된 토큰으로 판정한다.

이런 특징들 때문에 사실상 lex에서 사용하는 Regular grammar는 일반적으로 Chomsky hierarchy에서 말하는 Regular grammar와는 다르다. 사실 lex에서 지원하는 문법은 RG가 아니라 CFG로도 온전히 정의할 수 없다. 그래서 yacc은 CFG를 지원하기 때문에 RG를 지원하는 lex의 기능을 모두 포함할 것 같지만 실제로는 기능이 구분되어 있고 두 툴이 분리되어 있는 것이다. 앞서 우리가 일반적으로 사용하는 regular expression은 형식 문법에서의 regular grammar와 다르다는 것이 이런 의미였다.

이로 인해 lex와 yacc으로 구성된 파서에는 기능적으로 몇가지 한계가 있다.

오래된 C++ 컴파일러에서는 vector의 vector 타입을 쓸 때 vector<vector<int>>같은 식으로 쓰면 파스 에러가 나서 vector<vector<int> >같은 식으로 닫는 꺽쇠 괄호 두 개 사이에 공백을 주어야 했다. 이 문제는 lex의 longest match 정책때문에 생기는 현상이었다. 사용자가 >>라고 쓴 것은 template 타입을 지정하는 꺽쇠 괄호 두개가 연달아 닫히는 것을 나타내고자 했던 것이지만, C++ 파서의 렉서는 그 부분을 shift right 연산자로 인식했다. shift right 연산자 >>가 닫는 꺽쇠 >보다 길기 때문에 >>라는 스트링을 닫는 꺽쇠 두 개가 아니라 shift right 연산자로 인식했던 것이다. 토큰 어레이를 받아서 파싱하는 입장에서는 닫는 꺽쇠가 나와야될 곳에 shift right 연산자가 나오니 파싱 오류가 발생했던 것이다.

점점 많은 프로그래밍 언어들이 스트링 인터폴레이션 혹은 스트링 템플릿이라고 불리는 기능을 지원하고 있다. name + ": " + score라고 스트링을 + 연산자를 통해 이어붙이는 대신 "$name: $score"와 같이 쓸 수 있게 해주는 기능이다. 이런 기능은 기존의 렉서+파서의 구조로는 지원하기가 어렵다. 보통 렉서에서는 "로 시작해서 "로 끝나는 가장 긴 부분을 찾아서 스트링으로 삼도록 되어 있고, 여기에 이스케이프 문자에 대한 처리가 추가된다.

단순한 이스케이프 문자는 렉서에서도 간단하게 처리가 가능하지만 스트링 안에 수식을 포함해야 하는 경우라면 이야기가 다르다. (매우 이상한 예제이긴 하지만) "${"Hello"} world!"와 같은 문법도 지원할 수 있어야 하는데, 스트링 안의 수식 안에 "와 같은 문자가 들어있어서 일반적인 렉서로는 처리하기가 매우 어렵다.

전체 목차:

이런 문제들을 해결하기 위해 longest match나 심볼간의 우선순위 등을 나타낼 수 있는 문법 정의 방법을 고안해 낸 것이 Conditional Derivation Grammar이다. 여기에 대해서는 이어지는 포스팅에서 살펴보기로 하자.

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