JParser (5) Naive 파싱 알고리즘 동작 예제

이번 포스팅에서는 앞서 소개한 예제 문법을 갖고 Naive 파싱 알고리즘의 동작 과정을 살펴볼 것이다.

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

이는 평이한 CDG이고, 파싱과 관련된 주제에 가장 흔히 등장하는 수식 문법으로, 1+2나 3*4, 1+2*3+4 같은 수식을 파싱할 수 있다. Factor를 한자리 이상의 숫자를 지원하도록 고치거나, '(' WS Expr WS ')'나 Identifier같은 것들을 추가해서 여러가지로 확장해볼 수도 있겠지만, 그러면 파싱 컨텍스트의 크기가 너무 커지기 때문에 되도록이면 단순한 문법으로 Naive 파싱 알고리즘의 동작 과정을 따라가보자. 이 문법만으로도 파싱 컨텍스트를 그려놓으면 크기가 만만치 않다.

이 문법의 초기 파싱 컨텍스트는 다음과 같다. Naive 파싱 알고리즘에서 입력 스트링을 처리하기 전에 초기 파싱 컨텍스트는 인풋 스트링과 관계 없이 문법에 의해서만 결정된다. 여기에 어떤 인풋이 들어오느냐에 따라 파싱 컨텍스트가 변형되는 양상이 달라질 것이다.

그래프

그래프 1: 초기 상태의 파싱 컨텍스트.

앞선 포스팅의 그래프와 마찬가지로, 보다 간결하게 표현하기 위해 그래프에는 커널의 포인터가 커널의 심볼 사이에 점으로 표시되어 있고, 시작 위치와 종료 위치가 ..으로 연결되어 표시되어 있다. 즉, (Expr, 0, 0, 0)은 (•Expr, 0..0)으로 표시된다. 승인 조건은 모두 Always로, 비어있다는 뜻으로 ∅라고 적었다. 앞선 포스팅에 나온 그래프와의 차이점은 Start 심볼의 유무인데, Start심볼은 문법을 알고 있는 경우에는 의미가 없기 때문에 생략하기로 한다.

노드의 테두리가 둥근 것과 각진 것이 있는데, 테두리가 각진 것은 시퀀스 노드이고 둥근 것은 atomic 심볼 노드이다. 가장 아래 왼쪽에 (•'0-9', 0..0), ∅ 라고 써 있는 노드가 두 개가 있고 두 노드가 엣지로 연결되어 있는데, 그 중 윗쪽의 노드는 '0-9'라는 심볼 하나만 갖는 시퀀스 심볼의 노드이고, 그 아래는 '0-9'라는 실제 터미널 심볼의 노드이다. CDG에서 데이터 구조로 바꾸는 과정에서 길이가 1인 시퀀스는 그냥 atomic 심볼로 변환하도록 코딩하면 그래프가 조금 더 보기 좋아지겠지만.. 지금 그 코드를 건드릴 엄두가 나지 않으니 그냥 이렇게 진행해보기로 하자. 텍스트에서 조금 더 쉽게 구분하기 위해 시퀀스 노드는 커널을 감싸는 괄호를 대괄호로 표시하기로 하자. 즉 이 파싱 컨텍스트에는 [•'0-9', 0..0], ∅ 노드에서 (•'0-9', 0..0), ∅ 노드로 가는 엣지가 있는 것이다.

첫번쩨 예제

1이라는 단순한 입력이 들어온 경우를 보자. 기대되는 파싱 결과는 1이라는 글자는 Factor가 되고, Factor는 Term이, Term은 Expr이 돼서 파싱에 성공해야 한다.

초기 컨텍스트에는 2개의 터미널 심볼 노드 ((•'0-9', 0..0), ∅)과 ((•'(', 0..0), ∅) 가 있다. 1이라는 글자는 '0-9' 터미널에는 해당되지만 '('에는 해당되지 않는다. 그러므로 초기 컨텍스트에 Progress(((•'0-9', 0..0), ∅), ∅)를 적용하게 된다. 이 때 nextGen은 1이 될 것이다.

그렇게 해서 나온 그래프는 다음과 같다.

그래프

초기 파싱 컨텍스트에서 Progress(((•'0-9', 0..0), ∅), ∅)가 실행되면 (('0-9'•, 0..1), ∅)노드가 추가되고, ((•'0-9', 0..0), ∅) 노드로 들어오는 엣지들의 시작점에서 새로운 노드로 가는 엣지도 함께 추가된다. ([•'0-9', 0..0], ∅)에서 ((•'0-9', 0..0), ∅)로 가는 엣지가 있으므로 ([•'0-9', 0..0], ∅)에서 새로운 노드로 가는 엣지도 추가되었다.

새로 추가된 (('0-9'•, 0..1), ∅) 노드를 보면 포인터가 가장 뒤에 가 있다. 즉 종료된 커널의 노드이다. 따라서 이 노드에 대한 Finish 태스크가 수행된다. 그러면 ([•'0-9', 0..0], ∅)에 대한 Progress 태스크가 수행된다. 그래서 (['0-9'•, 0..1], ∅) 노드가 추가되었고, ((•Factor, 0..0), ∅) 노드에서 새로운 노드로 가는 엣지도 추가되었다. 새로 추가된 노드 역시 포인터가 시퀀스의 가장 뒤에 가 있어서 종료된 노드이므로 Finish 태스크가 실행된다. 그러면 함께 추가된 엣지에 의해 ((•Factor, 0..0), ∅) 노드에 대한 Progress 태스크가 실행되고, 그래서 ((Factor•, 0..1), ∅) 노드가 추가되고, 엣지도 함께 추가되었다. 새로 추가된 ((Factor•, 0..1), ∅) 노드 역시 종료된 노드이므로 이 노드에 대한 Finish 태스크가 실행된다.

((Factor•, 0..1), ∅) 노드에 대한 Finish 태스크때문에 ([•Factor, 0..0], ∅) 노드에 대한 Progress 태스크가 수행되고, 이 과정이 반복돼서 결과적으로 ((•Expr, 0..0), ∅)이 Progress돼서 ((Expr•, 0..1), ∅) 노드까지 추가된다.

그런데 ((Factor•, 0..1), ∅) 노드로 들어오는 엣지가 하나 더 있다. ((•Factor WS '*' WS Term, 0..0), ∅)이다. 이 노드에 대해서도 Progress 태스크가 수행되어야 한다. 그 결과 ((Factor•WS '*' WS Term, 0..1), ∅) 노드가 새로 추가되고, 이 노드는 종료되지 않았기 때문에 Finish 태스크가 아니라 Derive 태스크가 수행된다. 그래서 이 노드에서 나가는 엣지로 연결되는 ((•WS, 1..1), ∅) 노드가 추가된다. 이 노드 역시 종료되지 않았기 때문에 Derive 태스크가 수행된다.

((•WS, 1..1), ∅) 노드에 대한 Derive를 수행하면 ([•' '*, 1..1], ∅) 노드가 생기고 이어서 연쇄적으로 ((•' '*, 1..1), ∅) 노드가 생기는데, 이 노드에 대한 Dervie의 결과로 ([•, 1..1], ∅) 노드, 즉 빈 시퀀스에 대한 노드가 추가된다. 빈 시퀀스는 생성되는 순간 종료된 상태이기 때문에 Finish 태스크를 수행하게 되고, 그 결과, Derive 과정의 역순으로 Progress가 진행되게 된다. 그러면 결과적으로 ((•WS, 1..1), ∅) 노드에 대한 Progress가 실행되고, ((WS•, 1..1), ∅) 노드가 생성되고, 그래서 ((Factor•WS '*' WS Term, 0..1), ∅) 노드에 대한 Progress 태스크까지 실행되어 ((Factor WS•'*' WS Term, 0..1), ∅) 노드가 추가된다. 그 결과 1이라는 입력을 받은 뒤에는 *라는 글자를 받을 수 있는 근거가 생기게 된다. nullable 심볼들이 어떻게 처리되는지 볼 수 있었다.

파싱 태스크는 노드를 삭제하거나 변경하지 않기 때문에 초기 파싱 컨텍스트에 있는 노드들이 그대로 남아 있다. 하지만 그 중 일부는 더이상 필요 없기 때문에 앞선 포스팅에서 설명한 그래프 트리밍 과정에서 제거된다. 회색 노드는 그래프 트리밍 과정에서 제거된 노드를 나타낸다.

그래프

((Expr•, 0..1), ∅) 라는 노드가 이미 만들어짐으로써 1이라는 인풋만으로 Expr이라는 넌터미널을 만들고 파싱이 종료될 수 있다는 것을 알 수 있었다. 하지만 ((•Expr, 0..0), ∅) 노드도 아직 남아있는 것은, Expr이 1에서 끝날 수도 있지만 뒤에 뭔가 더 와서 더 긴 Expr을 완성할 수도 있음을 의미한다.

두번째 예제

1에 이어서 1+2이라는 스트링을 파싱해보자. 첫번째 글자인 1을 받은 상태의 파싱 컨텍스트는 위에서 본 것과 동일하다. 거기에 +가 들어가면 어떻게 될까?

그래프

이번에도 역시 +를 받을 수 있는 터미널 심볼의 노드인 ((•'+', 1..1), ∅) 노드에 대한 Progress 태스크에서 시작한다. (('+'•, 1..2), ∅)노드가 생성되고, 이 노드에 대한 Finish 태스크가 실행된다. 이 노드로 들어오는 ([Term WS•'+' WS Expr, 0..1], ∅) 노드에 Progress 태스크가 수행되어 ([Term WS '+'•WS Expr, 0..2], ∅) 노드가 추가된다. 이 노드는 종료되지 않았으므로 Derive 태스크가 추가되고, 새로 추가된 ((•WS, 2..2), ∅) 노드의 Derive를 수행하다 보면 WS 심볼이 nullable이라서 결과적으로 ((WS•, 2..2), ∅) 노드가 추가되고, ([Term WS '+'•WS Expr, 0..2], ∅) 노드에 대한 Progress 태스크가 수행되어서 ([Term WS '+' WS•Expr, 0..2], ∅) 노드가 추가되고.. 하는 과정이 앞에서 본것과 동일하게 반복된다.

1+라는 인풋은 Expr 심볼로 매칭될 수 없기 때문에 (Expr•, 0..2)와 같은 커널이 보이지 않는다. 만약 입력이 여기서 끝난다면 종료된 시작 심볼의 노드가 없기 때문에 파스 에러를 반환하게 된다.

여기서 그래프 트리밍을 거치면 그래프는 다음과 같아진다.

그래프

마지막 글자인 2를 받은 상태의 파싱 컨텍스트는 다음과 같아진다.

그래프

기대한대로 ((Expr•, 0..2), ∅)라는 노드가 포함되어 1+2가 우리의 문법에 부합하는 입력임을 알 수 있다.

사이클

파싱 컨텍스트는 얼핏 보기엔 DAG(Directed acyclic graph)같아 보이지만 사실 내부적으로 싸이클이 생기는 경우가 있다. Left recursive 문법이 입력으로 들어오는 경우이다. 다음의 문법을 보자.

As = As A | A
A = 'a'

이 문법의 초기 파싱 컨텍스트는 다음과 같다.

그래프

보다시피 ((•As,0..0),∅)와 ((•As A,0..0),∅) 노드 사이에 사이클이 발생했다. ((•As,0..0),∅)에 대한 Derive 태스크를 수행하면 RHS에 있는 ((•As A,0..0),∅) 노드로 가는 엣지가 생기고, ((•As A,0..0),∅)에 대해 Derive를 수행하면 포인터 뒤의 심볼이 As 이기 때문에 ((•As,0..0),∅) 노드로 가는 엣지가 추가되기 때문이다.

CDG에서 반복 심볼을 사용할 때 이런 현상이 흔히 발생한다. A+라는 심볼은 A+ A와 A라는 두 개의 RHS를 갖는 A+라는 이름의 넌터미널과 동일하게 동작하기 때문이다. (A*도 마찬가지로 A* A와 빈 시퀀스 두 개의 RHS를 갖는 A*라는 이름의 넌터미널과 동일하게 동작한다.) 위에서 다룬 문법에서도 WS의 RHS에 있는 ' '* 등의 심볼이 나오면 같은 이유로 사이클이 발생한다.

전체 목차:

다음 포스팅에서는 승인 조건에 대한 이야기를 해보자.

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