JParser (7) 파스 트리 재구성

먼저 파싱, 문법 등의 단어를 좀 더 정확히 정의해보자. 보통 파싱을 이야기할 때는 언어(language)라는 단어와 문법(grammar)이라는 단어를 구분해서 사용한다. 언어는 “대상이 되는 언어에 속한 모든 문장의 집합”을 의미한다. 영어라는 “언어”에는 “I am a boy”나 “You are a girl” 따위의 문장이 포함될 것이다. 그런데 이런 “언어”들은 무한 집합이기 때문에 다루기가 어렵다. 그래서 이런 “언어”에 속할 수 있는 문장의 조건을 정의하는 것이 “문법”이다. “파싱”이란 입력으로 주어진 문장 $S$가 일반적으로 문법 $G$로 정의된 언어 $L$에 속하는지, 즉 $S \in L$인지를 판정하는 함수로, $parsing(S, G)$는 true나 false값을 반환하는 함수이다. 우리가 앞서 Naive 파싱 알고리즘을 살펴보았고, 이 알고리즘을 이용하면 “파싱”이라는 과업은 이미 달성할 수 있는 것이다.

하지만 실질적인 사용에 있어서는 문법 $G$가 나타내는 언어 $L$에 입력으로 주어진 문장 $S$가 속하는지 아닌지를 아는 것만으로는 별로 쓸모가 없다. $S$의 파스 트리가 어떻게 되는지가 중요하다. 그래야 컴파일이든, 인터프리팅이든, 프로그램 분석이든 해볼 수가 있다. 이번 포스팅에서는 앞서 Naive 파싱 알고리즘을 수행하면서 모인 파싱 컨텍스트들을 가지고 파스 트리를 재구성하는 알고리즘을 살펴보자.

4장에서 파싱 컨텍스트에 등장하는 노드의 의미를 이야기 했었다.

하지만 파싱(recognition)의 과정이 끝난 상황에는 노드의 승인 조건을 모두 evaluate한 다음, 조건에 맞지 않는 노드들은 모두 지우고, 더이상 승인 조건은 필요 없으므로 각 generation의 파싱 컨텍스트들의 커널들만 가지고 파스 트리를 재구성할 수 있다.

파스 결과 자료 구조

문장 $S$가 문법 $G$에서 어떤 식으로 derive될 수 있는지를 나타낼 때 파스 트리를 사용하는 것이 가장 일반적이기는 하지만, 사실 꼭 트리의 형태일 필요는 없다. 그래프일 수도 있고, 집합으로 동일한 내용을 나타낼 수도 있다. 그저 트리가 가장 직관적이고 편리하기 때문에 트리를 사용하는 것이다. (이 개념은 첫번째 포스팅에서 간단히 소개한 바 있다)

JParser를 구현하면서 이 부분을 좀 일반화시키고 싶어서 다음과 같이 인터페이스를 정의하고, 파스 트리 자료구조를 갈아끼울 수 있도록 했다. (ParseResult.scala)

trait ParseResult

trait ParseResultFunc[R <: ParseResult] {
    def terminal(location: Int, input: Inputs.Input): R

    def bind(left: Int, right: Int, symbol: NSymbol, body: R): R

    def join(left: Int, right: Int, symbol: NJoin, body: R, join: R): R

    def cyclicBind(left: Int, right: Int, symbol: NSymbol): R

    def sequence(left: Int, right: Int, symbol: NSequence, pointer: Int): R

    def append(sequence: R, child: R): R

    def merge(base: R, merging: R): R

    def merge(results: Iterable[R]): R =
        results.tail.foldLeft(results.head)(merge) ensuring results.nonEmpty
}

실제 파스 결과를 나타내는 자료구조는 ParseResult trait을 상속받지만 특별히 메소드가 정의되어 있지는 않다.

ParseResultFunc는 ParseResult를 만들기 위해 필요한 기능들의 인터페이스를 정의한다. 실제 파스 결과를 재구성하는 ParseTreeReconstructor(이름이 사실 좀 잘못됐다. ParseResultReconstructor가 되었어야 하지 않을까?)에서는 ParseResultFunc를 인자로 받아서 파스 결과를 만들어낸다.

jparser에는 위의 ParseResult와 ParseResultFunc를 상속받는 클래스가 각 세종류가 있다. ParseResultDerivationsSet, ParseResultGraph, ParseResultForest인데 그 중 가장 많이 사용되는 것은 ParseResultForest이므로 이를 기준으로 설명해보자.

ParseTree가 아니라 ParseForest인 것은 입력 문장을 해석할 수 있는 가능성이 두 개 이상인 경우엔(모호한 경우) 하나의 트리로 표현이 불가능하기 때문이다. 그래서 ParseForest는 ParseResultTree.Node의 리스트를 갖는다. (ParseResultForest.scala)

case class ParseForest(trees: Seq[ParseResultTree.Node]) extends ParseResult

object ParseResultTree {
  import Inputs._

  sealed trait Node {
    val start: Inputs.Location
    val end: Inputs.Location

    def range: (Inputs.Location, Inputs.Location) = (start, end)

    ...
  }

  case class TerminalNode(start: Inputs.Location, input: Input) extends Node {
    val end: Inputs.Location = start + 1
  }

  case class BindNode(symbol: NSymbol, body: Node) extends Node {
    val start: Inputs.Location = body.start
    val end: Inputs.Location = body.end
  }

  case class CyclicBindNode(start: Inputs.Location, end: Inputs.Location, symbol: NSymbol) extends Node

  case class JoinNode(symbol: NJoin, body: Node, join: Node) extends Node {
    val start: Inputs.Location = body.start
    val end: Inputs.Location = body.end
  }

  case class SequenceNode(start: Inputs.Location, end: Inputs.Location, symbol: NSequence, _children: List[Node])
      extends Node {
    // _children은 실제 자식 노드들의 역순 리스트

    def append(child: Node): SequenceNode = {
      SequenceNode(start, child.end, symbol, child +: _children)
    }

    lazy val children = _children.reverse
  }

  case class CyclicSequenceNode(start: Inputs.Location, end: Inputs.Location, symbol: NSequence, pointer: Int, _children: List[Node])
      extends Node {
    def append(child: Node): CyclicSequenceNode = {
      CyclicSequenceNode(start, child.end, symbol, pointer, child +: _children)
    }

    lazy val children = _children.reverse
  }
}

ParseForest를 정의하고 나면 이를 위한 ParseResultFunc의 내용은 어렵지 않다.

object ParseForestFunc extends ParseResultFunc[ParseForest] {
  import ParseResultTree._

  def terminal(location: Int, input: Inputs.Input): ParseForest =
    ParseForest(Seq(TerminalNode(location, input)))

  def bind(left: Int, right: Int, symbol: NSymbol, body: ParseForest): ParseForest =
    ParseForest(body.trees map { b => BindNode(symbol, b) })

  def cyclicBind(left: Int, right: Int, symbol: NSymbol): ParseForest =
    ParseForest(Seq(CyclicBindNode(left, right, symbol)))

  def join(left: Int, right: Int, symbol: NJoin, body: ParseForest, constraint: ParseForest): ParseForest = {
    // body와 join의 tree 각각에 대한 조합을 추가한다
    ParseForest(body.trees flatMap { b => constraint.trees map { c => BindNode(symbol, JoinNode(symbol, b, c)) } })
  }

  def sequence(left: Int, right: Int, symbol: NSequence, pointer: Int): ParseForest =
    if (pointer == 0) {
      ParseForest(Seq(SequenceNode(left, right, symbol, List())))
    } else {
      ParseForest(Seq(CyclicSequenceNode(left, right, symbol, pointer, List())))
    }

  def append(sequence: ParseForest, child: ParseForest): ParseForest = {
    assert(sequence.trees forall { n => n.isInstanceOf[SequenceNode] || n.isInstanceOf[CyclicSequenceNode] })
    // sequence의 tree 각각에 child 각각을 추가한다
    ParseForest(sequence.trees flatMap { sequenceNode =>
      child.trees map { c =>
        sequenceNode match {
          case seq: SequenceNode => seq.append(c)
          case seq: CyclicSequenceNode => seq.append(c)
          case _ => ??? // cannot happen
        }
      }
    })
  }

  def merge(base: ParseForest, merging: ParseForest) =
    ParseForest(base.trees ++ merging.trees)
}

CyclicBindNode와 CyclicSequenceNode

다음과 같은 문법을 생각해 보자.

A = C*
C = ε

이 문법은 완전히 모호한 언어다. 이 문법이 나타낼 수 있는 언어는 빈 문장 딱 하나뿐이지만, 그 빈 문장에 대해서 여러가지 해석이 가능하다. 그냥 여러가지 해석이 가능한 정도가 아니라 무한히 다양한 해석이 가능하다. 위의 문법을 CFG식으로 풀어서 써보자.

A = B
B = C | B C
C = ε

빈 문장에 대해서 이 문법의 가장 간단한 해석은 A => B => C => ε일 것이다. 하지만 A => B => B C => C C => C => ε와 같은 해석도 가능하다. A => B => B C => B B C => C B C => B C => C C => C => ε와 같이 B를 B C 시퀀스로 여러번 치환한 다음 B를 C로, 그리고 C를 빈 시퀀스로 치환할 수도 있다. B를 B C 시퀀스로 치환하는 과정을 무한히 반복할 수도 있다.

CyclicBindNode 클래스와 cyclicBind 함수는 이런 경우를 처리하기 위해 도입되었다. 만약 이런 기능이 없었다면 이 문법에 대해 파스 트리를 재구성하려고 하면 프로그램이 무한 루프에 빠져서 종료되지 않았을 것이다. 이런 경우가 언제 발생하는지, 그래서 cyclicBind는 언제 호출되는지는 다음 섹션에서 살펴보자.

CyclicSequenceNode도 비슷한 문제를 해결하기 위해 도입되었다. 다음의 문법을 보자.

A = C*
C = 'a'*

이 문법도 모호한 언어다. 빈 문장에 대해서도 여러가지(실은 무한히 많은) 해석이 가능하고, a나 aa와 같은 입력에 대해서도 무한히 많은 해석이 가능하다. (TODO 설명 보강 필요)

Parse Tree Reconstruction 코드

위에서도 이야기했다시피, ParseTreeReconstructor보다는 ParseResultReconstructor라는 이름이 더 정확한 이름이었을 것이다.

우선 파스 결과 재구성을 위해서 각 generation의 파싱 컨텍스트를 커널의 집합의 목록으로 변환해야 한다. 즉, 하나의 파싱 컨텍스트를 커널의 집합 하나로 변환하게 된다. 이를 위해 먼저 파싱을 종료한 뒤에 알려진 정보에 의해 각 generation의 파싱 컨텍스트의 노드들이 가진 승인 조건을 확인하고, 최종적으로 인정된 노드들만 남기고 나머지 노드를 모두 제거한다. 그리고 그렇게 남은 노드들에서 승인 조건은 빼고 커널들만 모은다. 여기서는 파싱 컨텍스트의 엣지 정보는 사용하지 않는다. 이 코드는 ParseTreeReconstructor의 컴패니언 오브젝트에 정의되어 있다.

object ParseTreeConstructor2 {

  case class Kernels(kernels: Set[Kernel])

  case class KernelCore(symbolId: Int, pointer: Int)

  def kernelsFrom(history: Seq[Graph], conditionFinal: Map[AcceptCondition, Boolean]): Seq[Kernels] =
    history.map(_.filterNode(node => conditionFinal(node.condition)))
      .map(graph => Kernels(graph.nodes.map(_.kernel)))
}

KernelCore는 뒤에서 CyclicBindNode와 CyclicSequenceNode를 처리하기 위해 사용된다.

ParseTreeReconstructor는 그렇게 승인 조건을 만족하는 노드들의 커널들과, ParseResultFunc, NGrammar로 정의된 문법, 입력 스트링을 입력으로 받고 최종적으로 ParseResultFunc가 만들어내는 ParseResult 클래스를 반환한다. 그래서 ParseTreeReconstructor 클래스는 다음과 같이 생겼다.

class ParseTreeConstructor2[R <: ParseResult](resultFunc: ParseResultFunc[R])(grammar: NGrammar)(input: Seq[Input], history: Seq[Kernels]) {

  def reconstruct(): Option[R] =
    reconstruct(Kernel(grammar.startSymbol, 1, 0, input.length))

  def reconstruct(kernel: Kernel): Option[R] =
    if (kernel.pointer > 0 && history(kernel.endGen).kernels.contains(kernel)) {
      Some(reconstruct(kernel, Set()))
    } else {
      None
    }

  private def reconstruct(kernel: Kernel, traces: Set[KernelCore]): R = {
    ...
  }
}

일반적으로 사용자는 가장 위에 정의된 reconstruct 함수를 사용하게 될 것이다. 이 함수가 호출되면 문법의 시작 심볼의 커널을 하나 만들어서 두번째 정의된 reconstruct 함수를 호출한다. 포인터가 0인 커널의 존재는 사실 파스 결과 재구성시에는 아무 의미가 없다. 그리고 (시작 심볼, 1, 0..len(source))라는 커널이 만들어진 바가 없으면 해당 입력 스트링에 대해서는 파싱이 성공하지 못했음을 의미한다. 그래서 두번째 함수는 이 두가지 조건을 확인해 보고, 만족하면 세번째에 private으로 정의된 reconstruct 함수를 호출하고, 그렇지 않으면 None을 반환한다.

사실 히스토리를 generation별로 관리할 필요 없이 그냥 커널들을 한 집합에 통째로 때려박아서 해도 결과는 같을 것 같다.

이제 private으로 정의된 세번째 reconstruct의 내용을 살펴보자.

  private def reconstruct(kernel: Kernel, traces: Set[KernelCore]): R = {
    val gen = kernel.endGen

    def reconstruct0(child: Kernel): R = {
      val newTraces: Set[KernelCore] = if ((kernel.beginGen, gen) != (child.beginGen, child.endGen)) Set()
      else traces + KernelCore(kernel.symbolId, kernel.pointer)
      reconstruct(child, newTraces)
    }

    grammar.symbolOf(kernel.symbolId) match {
      case symbol: NAtomicSymbol if traces contains KernelCore(kernel.symbolId, kernel.pointer) =>
        resultFunc.cyclicBind(kernel.beginGen, gen, symbol)

      case symbol: NSequence if traces contains KernelCore(kernel.symbolId, kernel.pointer) =>
        resultFunc.sequence(kernel.beginGen, gen, symbol, kernel.pointer)

첫번째 두 가지 경우는 앞서 살펴보았던 CyclicBindNode와 CyclicSequenceNode를 처리하기 위한 곳이다. reconstruct함수는 kernel 외에도 traces라는 인자를 하나 더 받는데, 이 인자는 현재 처리중인 kernel의 바깥쪽에 어떤 커널들이 있었는지를 나타낸다. 만약 같은 심볼, 같은 포인터에 대해 같은 영역에서 파스 결과 재구성이 이루어졌다면 싸이클이 발생했고, 그대로 두면 무한루프가 발생함을 나타낸다. 따라서 이런 경우 bind 대신 cyclicBind를 호출해야 하고, sequence에서 poitner를 0이 아닌 값으로 호출해야 한다.

reconstruct0는 reconstruct에 전달해주어야 하는 traces의 값을 계산해서 reconstruct 함수를 재귀 호출해주는 역할을 한다. 이어지는 다른 case들에서도 reconstruct 함수를 재귀호출할 때 reconstruct 함수를 직접 호출하지 않고 reconstruct0 함수를 호출한다.

이들 싸이클에 대한 처리는 반드시 match 문의 가장 위쪽에 있어야 한다. 만약 아래쪽의 atomic 심볼에 대한 처리나 시퀀스 심볼에 대한 처리보다 밑에 있으면 이 코드가 실행되지 않아서 무한루프가 발생하게 될 것이기 때문이다.

      case symbol: NTerminal =>
        resultFunc.bind(kernel.beginGen, kernel.endGen, symbol,
          resultFunc.terminal(kernel.beginGen, input(kernel.beginGen)))

그 다음 경우는 가장 간단한 터미널 심볼인 경우이다. 간단하게 resultFunc.terminal을 호출하고 그 결과에 대해 resultFunc.bind를 호출하고 있다. 굳이 bind를 추가로 호출지 말고 terminal 함수 하나로 해결할 수는 없었을까? 약간은 잘못된 디자인 같다.

      case symbol: NAtomicSymbol =>
        assert(kernel.pointer == 1)

        def lastKernel(symbolId: Int) =
          Kernel(symbolId, Kernel.lastPointerOf(grammar.symbolOf(symbolId)), kernel.beginGen, gen)

        val bodyKernels: Set[Kernel] = grammar.nsymbols(kernel.symbolId) match {
          case deriver: NSimpleDerive => deriver.produces.map(lastKernel)
          case NGrammar.NExcept(_, _, body, _) => Set(lastKernel(body))
          case NGrammar.NLongest(_, _, body) => Set(lastKernel(body))
          case symbol: NGrammar.NLookaheadSymbol => Set(lastKernel(symbol.emptySeqId))
          case _: NTerminal | _: NJoin => assert(false); ???
        }
        val validKernels = history(gen).kernels intersect bodyKernels
        assert(validKernels.nonEmpty)
        val bodyTrees = validKernels.toSeq.sortBy(_.tuple) map {
          bodyKernel => reconstruct0(bodyKernel)
        }
        assert(bodyTrees.nonEmpty)
        resultFunc.bind(kernel.beginGen, kernel.endGen, symbol, resultFunc.merge(bodyTrees))

그 다음 atomic 심볼에 대한 처리를 보자. 넌터미널 심볼 A에 대한 (A, 1, s..e) 커널이 history[e]에 존재한다는 것의 의미는, source[s:e]가 A로 매치될 수 있다는 뜻이다. 이는 곧 source[s:e] 사이에는 A의 RHS에 해당하는 어떤 심볼이나 시퀀스가 한 개 이상 매치되었다는 것을 의미한다. 즉, A = B | C라는 룰이 있었다면, (A, 1, s..e) 커널이 있으면 (B, 1, s..e)나 (C, 1, s..e) 중 하나는 반드시 history[e]에 함께 존재해야 한다는 것이다. (만약 (B, 1, s..e)와 (C, 1, s..e)가 모두 존재한다면 해석이 모호한 경우이다)

validKernels가 바로 history[e]에서 atomic 심볼의 RHS에 해당되는 심볼들의 커널이며 종료된 커널들을 추린 것이다. 이제 validKernels에 포함된 커널들에 대해 파스 트리를 재구성하고 resultFunc.bind로 해당 영역이 심볼 A에 매치되었음을 명시한다.

      case symbol@NJoin(_, _, body, join) =>
        assert(kernel.pointer == 1)
        val bodyKernel = Kernel(body, 1, kernel.beginGen, kernel.endGen)
        val joinKernel = Kernel(join, 1, kernel.beginGen, kernel.endGen)
        val bodyTree = reconstruct0(bodyKernel)
        val joinTree = reconstruct0(joinKernel)
        resultFunc.join(kernel.beginGen, kernel.endGen, symbol, bodyTree, joinTree)

Join은 양쪽 심볼 모두에 대해 파스 결과를 만든 다음 resultFunc.join을 호출해서 묶어서 반환한다.

      case symbol@NSequence(_, _, sequence) =>
        if (sequence.isEmpty) {
          assert(kernel.pointer == 0 && kernel.beginGen == kernel.endGen && kernel.beginGen == gen)
          resultFunc.bind(kernel.beginGen, gen, symbol, resultFunc.sequence(kernel.beginGen, kernel.endGen, symbol, 0))
        } else if (kernel.pointer == 0) {
          assert(kernel.beginGen == kernel.endGen)
          resultFunc.sequence(kernel.beginGen, kernel.endGen, symbol, 0)
        } else {
          val (symbolId, prevPointer) = (kernel.symbolId, kernel.pointer - 1)
          val prevKernels = history(gen).kernels filter { kern =>
            (kern.symbolId == symbolId) && (kern.pointer == prevPointer) && (kern.beginGen == kernel.beginGen)
          }
          val trees = prevKernels.toSeq.sortBy(_.tuple) flatMap { prevKernel =>
            val childKernel = Kernel(sequence(prevPointer), 1, prevKernel.endGen, gen)
            if (history(gen).kernels contains childKernel) {
              val precedingTree = reconstruct0(Kernel(kernel.symbolId, prevPointer, kernel.beginGen, prevKernel.endGen))
              val childTree = reconstruct0(childKernel)
              // println(s"preceding: $precedingTree")
              // println(s"child: $childTree")
              Some(resultFunc.append(precedingTree, childTree))
            } else None
          }
          val appendedSeq = resultFunc.merge(trees)
          if (kernel.pointer == sequence.length) resultFunc.bind(kernel.beginGen, gen, symbol, appendedSeq) else appendedSeq
        }

이제 가장 복잡해 보이는 시퀀스 심볼 처리를 보자. 만약 시퀀스 심볼이 빈 시퀀스이면 그냥 빈 시퀀스를 만들고 bind를 호출한다.

시퀀스가 빈 시퀀스가 아닌 경우, kernel.pointer를 확인한다. 커널 포인터가 0보다 큰 경우를 먼저 보자. history[kernel.endGen]에 kernel과 같은 심볼, 같은 시작 generation에, pointer만 kernel.pointer보다 1 작은 커널들을 찾는다. 그렇게 찾아진 커널의 endGen부터 현재 커널의 endGen 사이에 sequence[kernel.pointer - 1]의 심볼에 대한 매치가 존재할 것이다. 그 심볼의 파스 결과를 재구성하고, 그 결과를 시퀀스에 append한다.

예를 들어보면 이해가 쉽다. [A B C D E•, 5..20]이란 커널이 있다고 하자. 이 5..20 영역에서 A B C D E 시퀀스의 파스 결과를 재구성하려면 먼저 generation 20에서 A B C D•E이고 시작 시점이 5인 커널, 즉 [A B C D•E, 5..??]의 형태를 갖는 커널을 찾아야 한다. 만약 [A B C D•E, 5..16]이라는 커널이 발견되었다고 하자. 그럼 이것은 16..20 사이에 E라는 심볼이 매치되었음을 의미한다. 그래서 [A B C D•E, 5..16]에 대한 파스 결과를 재구성한 다음, (E•, 16..20) 커널에 대한 파스 결과 재구성해서 append한다.

[A B C D•E, 5..16]에 대한 파스 결과 재구성도 마찬가지로 우선 [A B C•D E, 5..??]의 형태를 갖는 커널을 찾고, [A B C•D E, 5..14]와 같은 커널이 발견되면 14..16 사이에 D가 있음을 알 수 있으니 [A B C•D E, 5..14]에 대한 파스 결과에 (D, 14..16)에 대한 파스 결과를 append하고.. 하는 과정을 반복하게 된다. 그리고 최종적으로는 [•A B C D E, 5..5] 커널에 대한 파스 결과를 요청하게 되고, 그러면 else if (kernel.pointer == 0) 부분으로 진입해서 resultFunc.sequence 함수를 호출해서 빈 시퀀스 결과를 반환하게 되고, 그러면 재귀호출 스택을 되돌아가면서 파스 트리가 재구성되게 된다.

(파싱 컨텍스트 히스토리에는 그래프 트리밍이 되기 전의 그래프가 저장되기 때문에 이 기능이 동작할 수 있다)

전체 목차:

여기까지 해서 CDG 파싱이 가능해지긴 했지만, Naive 파싱 알고리즘은 실제로 사용하기엔 너무 느리다. 입력 스트링의 길이에 대한 시간 복잡도 자체 높지는 않지만, 문법의 크기가 커질수록 파싱 속도가 느려진다. 이 문제를 해결하기 위해 좀더 빠르게 동작하는 마일스톤 파싱 알고리즘이라는 것을 만들었다. 다음 포스팅에선 이 알고리즘에 대해 이야기 해보자.

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