JParser (8) 마일스톤 파싱 알고리즘 (WIP)

앞서 살펴보았던 naive 파싱 알고리즘의 시간 복잡도는 문법에 따라 달라진다. (뒤에서 더 자세히 이야기할 기회가 있을 것이다) 문법이 특정 조건을 만족시키면 입력 스트링의 길이에 선형으로 비례하는 시간 복잡도를 가질 수도 있다. 하지만 문제는 문법의 복잡성에 따라서도 실행 속도가 달라진다는 점이다. 그래서 복잡한 문법으로 파싱을 시도해보면 naive 파싱 알고리즘은 상당히 느리게 동작한다.

그런데 naive 파싱 알고리즘을 자세히 살펴보면 문법에 대해 미리 처리해두고 실제 파싱시에는 생략할 수 있는 부분이 꽤 많다. 주어진 문법에 대해 사전 처리해 둘 수 있는 부분을 사전 처리해서 실제 파싱시 불필요한(혹은 중복된) 처리를 생략할 수 있도록 한 것이 이번 포스팅에서 소개할 마일스톤 파싱이다.

마일스톤 파싱

앞에서 보았던 문법과 이 문법의 초기 파싱 컨텍스트를 다시 살펴보자.

Expr = Term WS '+' WS Expr
     | Term
Term = Factor WS '*' WS Term
     | Factor
Factor = '0-9'
     | '(' WS Expr WS ')'
WS = ' '*

그래프

그래프 1

그래프에는 생략되긴 했지만 실제 파싱 컨텍스트에는 ((•Start, 0..0), Always) 노드가 포함되고, 이 노드에서 ((•Expr, 0..0), Always) 노드로 가는 엣지가 포함된다. 사실 이 그래프는, 초기 파싱 컨텍스트는 입력 스트링과 관계 없이 문법에 의해서만 결정되기 때문에, 문법만 알고 있으면 ((•Start, 0..0), Always) 노드에 대한 Derive 태스크를 수행함으로서 언제든 재구성 할 수 있다.

이 그래프를 살펴보면, 이 그래프에 속한 노드들은 모두 ((•Start, 0..0), Always) 노드에서 파생된 것이기 때문에 파생된 노드들의 시작 gen과 종료 gen이 모두 0이다. 또한 이 초기 파싱 컨텍스트는 입력 스트링과 관계 없이 문법에 의해 결정되기 때문에, (•Start, 0..0) 심볼에서 파생된 그래프는 '0-9'와 '('라는 터미널 심볼을 받을 수 있다는 점도 알 수 있다.

이 그래프에 1이라는 입력을 주고 그래프 트리밍을 한 상태의 다음 그래프도 보자.

그래프

그래프 2

이 그래프는 첫번째 그래프에서 ((•'0-9', 0..0), Always) 노드가 Progress되어서 얻어진 그래프이다. 이 그래프를 잘 살펴보면, (테두리가 점선으로 표시된) ((Term•WS '+' WS Expr, 0..1), Always), ((Term WS•'+' WS Expr, 0..1), Always), ((Factor•WS '+' WS Term, 0..1), Always), ((Factor WS•'+' WS Term, 0..1), Always) 네 개의 노드를 기준으로 그래프를 두 개로 나눌 수 있다. 이 네 개의 노드를 기준으로 그보다 윗쪽의 노드들은 beginGen과 endGen이 모두 0이고, 그 이후에 등장하는 노드는 모두 beginGen과 endGen이 1이다.

윗쪽의 노드들은 초기 파싱 컨텍스트에서 생성된 노드들이고(즉 Start 심볼 노드에 대한 Derive 태스크로부터 생성된), 아래쪽의 노드들은 이 네 개의 노드들이 Derive되면서 생성된 노드들이이기 때문이다. 즉 이들 노드들이 그래프를 구분하는 마일스톤과 같은 역할을 한다. 또한 그래프 1을 Start 심볼 노드에 대한 Derive 태스크로부터 유추할 수 있었던 것과 마찬가지로, 점선 노드들 이후의 그래프는 각 노드의 Derive 태스크들로부터 유추가 가능하다. 또 Start 심볼과 각 점선 노드 사이의 그래프도 그래프 1에서 각 점선 노드의 initial 노드(같은 심볼에 포인터가 0이고 승인 조건이 비어있는) 사이의 그래프로 계산할 수 있다.

이처럼 그래프를 분리하는 노드들을 마일스톤이라고 부른다. 마일스톤 노드는 ((•Start, 0..0), Always) 노드 및 종료되지 않은 시퀀스 노드 중 beginGen과 endGen이 다른 노드들이다. Start 심볼의 노드는 모든 파싱의 시작점이기 때문에 특별취급을 받는 것이고, 중요한건 “beginGen과 endGen이 다른 종료되지 않은 시퀀스 노드”이다. 이런 마일스톤 노드 사이의 노드들은 커널의 포인터와 관계 없이 beginGen과 endGen이 동일하다.

마일스톤 파싱 알고리즘은 파싱 과정에서 전체 그래프가 아니라 이처럼 그래프를 분리하는 마일스톤들만 추적하는 파싱 알고리즘이다.

마일스톤 파싱 알고리즘에서는 파싱 컨텍스트를 전체 그래프로 나타내지 않고 마일스톤 리스트들의 집합으로 대신 나타낸다. 초기 파싱 컨텍스트는 Derive((•Start, 0..0), Always)에서 만들어진 것이므로 그 그래프는 [((•Start, 0..0), Always)]라는 하나의 마일스톤 리스트로 줄여서 나타낼 수 있다.

두번째 그래프는 다음과 같은 네 개의 마일스톤 리스트로 나타낼 수 있다.

([Term•WS '+' WS Expr, 0..1], Always)가 ((•Start, 0..0), Always) 뒤에 붙어있는 이유는, ((•Start, 0..0), Always)를 Derive해서 나온 그래프에 속해있던 ([•Term WS '+' WS Expr, 0..0], Always) 노드가 Progress되어서 생긴 노드이기 때문이다.

마지막 리스트를 보자. ((•Start, 0..0), Always) 노드와 ([Factor WS•'+' WS Term, 0..1], Always) 노드 사이의 그래프(([•Term WS '+' WS Expr, 0..0], Always), ([•Term, 0..0], Always), ((•Term, 0..0), Always) 세 개의 노드)는 초기 파싱 컨텍스트에서 ((•Start, 0..0), Always) 노드와 ([•Factor WS '+' WS Term, 0..1], Always) 노드 사이의 그래프와 동일하다.

즉, 어떤 마일스톤 리스트가 주어졌을 때 해당 리스트에서 인접한 두 마일스톤 A와 B 사이의 그래프를 얻으려면 다음과 같이 하면 된다는 의미이다.

  1. A 노드를 Derive해서 그래프를 만든다
  2. 1의 결과에는 B 노드의 initial 노드(B 노드에서 커널의 포인터를 0으로 옮기고, endGen을 beginGen과 같게 맞추고, 승인 조건을 비운 노드)가 포함된다.
  3. 1의 결과에서 A노드와 B 노드의 initial 노드 사이의 그래프만 추린다.
  4. 3의 결과에서 B 노드의 initial 노드를 B 노드로 치환한다.

또 마일스톤 리스트의 마지막 마일스톤 A 이후의 그래프는 간단히 A에 대한 Derive를 실행하면 얻을 수 있다.

이는 파싱 컨텍스트를 보다 간단한 마일스톤 리스트들의 집합의 형태로 나타내도 그것이 나타내는 의미가 원본 파싱 컨텍스트와 동일함을 의미한다. 어떤 문법과 어떤 입력 스트링에 대해서든, 파싱 과정에서 발생하는 모든 파싱 컨텍스트에서는 이러한 속성이 만족된다.

그렇다면, 마일스톤 리스트 집합에 대해서 특정 입력이 들어왔을 때, 그 다음 세대의 파싱 컨텍스트와 동치인 마일스톤 리스트 집합을 어떻게 만들어낼 수 있을까? 즉, 만약 마일스톤 리스트 집합 X를 특정 입력 t에 대해 변환해서 그 다음 세대의 마일스톤 리스트 집합 Y를 만들 수 있다면 불필요한 파싱 태스크들을 생략하고 파싱을 수행할 수 있지 않을까? 실제로 이것이 가능하고, 그것이 마일스톤 파싱이다.

승인 조건

실제로는 승인 조건과 generation 숫자가 달라지는 것 때문에 노드를 그대로 마일스톤 데이터로 쓸 수는 없고 약간의 변형이 필요하다. TODO

파서 데이터

마일스톤 파서는 앞서 살펴보았던 naive 파서와 달리 문법에 대한 사전 처리가 필요하다. 사전 처리를 통해 MilestoneParserData라는 클래스를 만들어내고 (MilestoneParserData.scala) 그 데이터를 protocol buffer(스키마)의 형태로 저장한다 (converter).

TODO

승인 조건 처리

TODO tracking

예제

앞에서 살펴본 문법에 1+1이라는 입력을 주면 마일스톤 파서에서 어떻게 처리되는지 살펴보자.

MilestoneParser.scala

=== initial
(1 0 0) Always (None, tracking={})
=== 0 Character(1)
  ** before evaluating accept condition
(1 0 0) (3 1 1) Always (None, tracking={})
(1 0 0) (3 2 1) Always (None, tracking={})
(1 0 0) (5 1 1) Always (None, tracking={})
(1 0 0) (5 2 1) Always (None, tracking={})
  ** after evaluating accept condition
(1 0 0) (3 1 1) Always (None, tracking={})
(1 0 0) (3 2 1) Always (None, tracking={})
(1 0 0) (5 1 1) Always (None, tracking={})
(1 0 0) (5 2 1) Always (None, tracking={})
  ** after removing milestones that are not tracked (tracked={})
(1 0 0) (3 1 1) Always (None, tracking={})
(1 0 0) (3 2 1) Always (None, tracking={})
(1 0 0) (5 1 1) Always (None, tracking={})
(1 0 0) (5 2 1) Always (None, tracking={})
=== 1 Character(+)
  ** before evaluating accept condition
(1 0 0) (3 3 2) Always (None, tracking={})
(1 0 0) (3 4 2) Always (None, tracking={})
  ** after evaluating accept condition
(1 0 0) (3 3 2) Always (None, tracking={})
(1 0 0) (3 4 2) Always (None, tracking={})
  ** after removing milestones that are not tracked (tracked={})
(1 0 0) (3 3 2) Always (None, tracking={})
(1 0 0) (3 4 2) Always (None, tracking={})
=== 2 Character(1)
  ** before evaluating accept condition
(1 0 0) (3 4 2) (3 1 3) Always (None, tracking={})
(1 0 0) (3 4 2) (3 2 3) Always (None, tracking={})
(1 0 0) (3 4 2) (5 1 3) Always (None, tracking={})
(1 0 0) (3 4 2) (5 2 3) Always (None, tracking={})
  ** after evaluating accept condition
(1 0 0) (3 4 2) (3 1 3) Always (None, tracking={})
(1 0 0) (3 4 2) (3 2 3) Always (None, tracking={})
(1 0 0) (3 4 2) (5 1 3) Always (None, tracking={})
(1 0 0) (3 4 2) (5 2 3) Always (None, tracking={})
  ** after removing milestones that are not tracked (tracked={})
(1 0 0) (3 4 2) (3 1 3) Always (None, tracking={})
(1 0 0) (3 4 2) (3 2 3) Always (None, tracking={})
(1 0 0) (3 4 2) (5 1 3) Always (None, tracking={})
(1 0 0) (3 4 2) (5 2 3) Always (None, tracking={})

TODO 마일스톤 그룹 파싱은 여기서 등장하는 4개의 마일스톤, 그리고 그로 인해 4개로 확장되는 마일스톤 경로를 해당 마일스톤 네 개를 병합한 하나의 “마일스톤 그룹”으로 묶어서 처리하도록 하는 것. 기본 원리는 비슷할 것.

TODO 멀티-레벨 마일스톤 그룹 파싱은 마일스톤 그룹 파싱에서 동시에 등장할 수 있는 마일스톤 그룹 경로를 묶어서 처리하는 것. “상태(state)”

그러면 이제 우리는 파싱 컨텍스트에 등장 가능한 마일 스톤을 ((•Start, 0..0), Always), ((Term•WS '+' WS Expr, 0..1), Always), ((Term WS•'+' WS Expr, 0..1), Always), ((Factor•WS '+' WS Term, 0..1), Always), ((Factor•WS '+' WS Term, 0..1), Always) 까지 총 5개 알고 있다. 각 마일스톤에 대해서 Derive 태스크를 미리 해두면, 해당 마일스톤이 어떤 마일스톤 경로의 마지막에 나왔을 때, 어떤 터미널들을 받을 수 있는지 알 수 있고, 터미널이 왔을 때 마일스톤 경로가 어떻게 변경되어야 하는지도 미리 계산해둘 수 있다.

예를 들어 ((Term WS•'+' WS Expr, 0..1), Always)라는 마일스톤을 보자. TODO 여기서 출발한 그래프

이 그래프를 통해 보면 이 마일스톤은 '+'라는 터미널을 받을 수 있다. 그 외의 입력이 들어오면 이 마일스톤은 그 터미널을 처리할 수 없고, 따라서 이 마일스톤이 가장 마지막에 있는 마일스톤 경로는 삭제된다.

파싱 컨텍스트를 마일스톤 경로 집합으로 대체했다. 파싱을 진행하면서 마일스톤 경로가 1개이상 남아 있으면 파싱을 계속 할 수 있다는 의미이다. 마일스톤 경로가 모두 없어지면, 같은 시점에 입력도 종료되면 파싱이 성공했을 수도 있지만(승인 조건을 확인해 봐야 함), 거기서 입력이 더 들어오면 파싱은 실패한다.

TODO 승인 조건 처리. 숫자 1, 2, 3, 4의 의미. ParsingTasks 코드 재사용

여기서 한가지 생각해볼 수 있는 것은, 우리가 여러 개의 경로로 나타내는 것이 실은 DAG의 특성을 갖고, 실제로 jparser의 구현에서도 immutable list를 사용하기 때문에 자연적으로 DAG의 형태로 데이터가 저장되게 된다는 점이다.

이 노드들을 이용해서 milestone list의 list(혹은 milestone의 DAG)로 파싱 컨텍스트를 간략화해서 나타낼 수 있다.

파스 결과 재구성

파스 결과 재구성 코드는 naive 파서에서와 동일한 코드를 사용한다. TODO 그러기 위해서는 마일스톤 파싱 데이터에 각 마일스톤과 마일스톤 액션에 대한 그래프를 포함시켜야 함. 이어서 다룰 AST에 맞춰서 파스 결과 재구성 로직의 성능 개선이 future work

파서 데이터 생성

파서 데이터가 있을 때 파싱이 어떤식으로 이루어지는지는 알았다. 그렇다면 이런 파서 데이터는 어떻게 생성될까? MilestoneParserGen.scala

TODO

a. 처음에는 존재할 수 있는 마일스톤이 Start 심볼 노드밖에 없음. b. 거기서 처리할 수 있는 터미널들을 추리고, 각 터미널에 대해서 Parsing action 계산 c. Parsing action에서 append하는 마일스톤들은 마일스톤 리스트의 가장 마지막에 존재할 수 있는 마일스톤으로 추가. 각각에 대해 b를 실행 d. 각 마일스톤마다 해당 마일스톤 바로 앞에 나올 수 있는 모든 마일스톤의 집합을 관리해야 함. e. 어떤 마일스톤에 대해 ParsingAction에 startNodeProgressConditions가 변경되거나 어떤 마일스톤의 앞에 나올 수 있는 마일스톤이 추가되면 해당 엣지에 대해 ParsingAction 계산

future work - 마일스톤 그룹 파싱

위의 예에서 보면 Start 심볼 노드에서 한 번에 네 개의 마일스톤이 파생되었다. 그리고 다음에 어떤 글자가 입력으로 들어오느냐에 따라 그 중에 어떤 마일스톤이 살아남는지가 결정된다. 그렇다면 굳이 네 개의 마일스톤에 대해 네 개의 리스트를 관리하지 말고 네 개의 마일스톤을 묶어서 “마일스톤 그룹”으로 관리하면 어떨까? 그래서 “마일스톤 리스트”가 아니라 “마일스톤 그룹 리스트”가 되게 하고, 대신 글자 입력을 처리할 때 해당 글자를 처리할 수 있는 마일스톤들을 지운 별도의 마일스톤 그룹으로 치환하면 똑같이 동작하지 않을까? 이런 아이디어에서 시작한 것이 마일스톤 그룹 파싱이다.

future work - 멀티 마일스톤 그룹 파싱

처음 naive 파싱 알고리즘을 만들고 나서 좀더 빠른 알고리즘을 만들 수 있을거라고 생각했을 때 나의 목표는 (지원할 수 있는 언어에 대해서만) 생성되는 파서가 finite state machine처럼 동작하게 하는 것이었다. 그렇다면 파서에서의 “상태(state)”가 무엇인가 고민하다보니, 파서에서의 상태란 여러 마일스톤 경로들의 묶음이어야 한다는 결론을 얻었다.

문제가 너무 복잡해 보여서 조금 더 간단히 하기 위해 “마일스톤”이라는 개념을 도입하고, 마일스톤 파서를 먼저 만들었다. 그리고 중간 단계로 동시에 등장할 수 있는 마일스톤들을 묶은 “마일스톤 그룹”을 이용하는 파싱 알고리즘을 만들고, 더 나가서 처음 생각했던 “상태”에 해당하는 “멀티 마일스톤 그룹”을 이용하는 파싱 알고리즘을 만들어야겠다고 아이디어를 구체화했다.

만약 멀티 마일스톤 그룹 파싱까지 갈 수 있다면, naive 파서에서(그리고 마일스톤 파서에서도) O(n^2)이나 그 이상의 시간 복잡도를 갖게 되는 문법에 대해 O(n)과 같은 더 낮은 시간 복잡도를 갖는 파서를 생성할 수 있게 되지 않을까 싶다 (아직 깊이 생각해본 것은 아니라 확실히는 모르겠다).

하지만 실제 사용할 때는 마일스톤 파서도 생각보다 빠르게 잘 돌아서 현재 멀티 마일스톤 그룹 파서 개발은 매우 후순위로 밀려있는 상태이다.

전체 목차:

이렇게 해서 파싱 자체에 대한 이야기는 얼추 마무리가 되었다. 하지만 현재 파서를 돌려서 나오는 파스 결과는 앞선 포스팅에서 살펴보았던 파스 트리의 형태이다. 이런 형태는 그대로 사용하기가 매우 불편하기 때문에 보통은 Abstract Syntax Tree, 줄여서 보통 AST라고 하는 형태로 가공해서 사용하게 되는데 파스 트리를 AST로 바꾸는 코드를 직접 쓰려면 그 역시 간단한 일이 아니다. 그래서 jparser에는 문법 정의에 파스 트리를 AST로 가공해주기 위해 필요한 정보를 넣으면 파스 트리를 받아서 AST로 변환해주는 코드를 생성하는 기능이 있다. 다음 포스팅에서는 이 기능을 살펴보자.

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