JParser (6) 승인 조건

앞선 포스팅에서 확장 심볼과 승인 조건(accept condition)에 대한 논의는 뒤로 미뤄두었다. 즉, 앞에서 소개한 알고리즘들로는 평이한 CDG들만 파싱할 수 있다. 이 포스팅에서 승인 조건에 대해 자세히 이야기해보자.

어떤 노드에 붙어있는 승인 조건이 거부되면 해당 노드는 파싱 결과에서 배제된다. 즉, 만약 어떤 파싱 조건이 노드에 붙어있었는데 결과적으로 승인 조건이 해당 노드를 인정하지 않으면 해당 노드는 처음부터 존재하지 않았던 것처럼 취급되고 파싱 결과에서 완전히 배제된다. 승인 조건에는 네가지 종류가 있다. NotExists, Exists, Unless, OnlyIf. 그리고 실제 구현에서는 이 승인 조건들 여러개를 이어 붙이기 위해서, Always, Never, And, Or라는 네가지 조건이 추가된다.

네가지 승인 조건은 모두 한 개의 심볼과 generation을 나타내는 정수 두 개를 받는다. 이 심볼을 A, generation을 나타내는 두 개의 정수를 s와 e라고 부르자.

NotExists

만약 X라는 노드에 NotExists(s, e, A)가 붙어있으면 설령 X가 종료된 뒤에라도 0 이상의 정수 k에 대해 source[s:e+k] 중 A가 매칭될 수 있는 k가 존재하면 X는 존재하지 않았던 것처럼 처리된다.

source는 입력 스트링을 의미하고, [s:e+k]는 파이썬 식으로 substring을 나타내기 위해 사용했다. 파싱 컨텍스트에 ((A•, s..e), ∅)라는 노드가 있으면 source[s:e]가 심볼 A에 매치될 수 있음을 의미한다. 만약 (A•, s..e) 커널을 갖되 승인 조건이 비어있지 않은 노드가 있으면, 그 조건이 만족되는 경우에만 source[s:e]가 심볼 A에 매치될 수 있다는 것을 의미한다.

NotExists 승인 조건은 Longest 심볼과 Lookahead except 심볼을 처리하기 위해 사용된다. 예를 들어,((•<A>, 3..3), ∅)라는 노드를 생각해 보자. 이 노드에 대한 Derive 태스크가 실행되면 ((•A, 3..3), ∅) 노드와 두 노드 사이에 엣지가 추가된다. 만약 generation 5에서 이 노드에 대한 Progress 태스크가 수행됐다고 생각해보자. ((A•, 3..5), ∅)라는 노드가 추가될 것이고, 연쇄적으로 ((•<A>, 3..5), ∅) 노드에 대한 Progress 태스크가 수행될 것이다.

이 때, 이미 우리는 source[3:5]가 A에 매치될 수 있음을 알고 있는 상태이다. 하지만 <A>라는 심볼은 만약 source[3:6]이 A에 매치될 수 있으면, 혹은 source[3:100]이 A에 매치될 수 있으면, 즉 source[3:5]보다 시작점은 같고 길이는 더 긴 서브스트링에 A가 매치될 수 있으면 <A>는 source[3:5]에 대해서는 매치되어서는 안 된다.

NotExists 승인 조건은 이런 경우를 의미하며, 그래서 progressTask(ParsingTasks.scala)에는 다음과 같은 코드가 있다.

val newCondition = grammar.symbolOf(node.kernel.symbolId) match {
  case NLongest(_, _, longest) =>
    NotExists(node.kernel.beginGen, nextGen + 1, longest)
  case NExcept(_, _, _, except) =>
    Unless(node.kernel.beginGen, nextGen, except)
  case NJoin(_, _, _, join) =>
    OnlyIf(node.kernel.beginGen, nextGen, join)
  case NLookaheadIs(_, _, _, lookahead) =>
    Exists(nextGen, nextGen, lookahead)
  case NLookaheadExcept(_, _, _, lookahead) =>
    NotExists(nextGen, nextGen, lookahead)
  case _ => Always
}

그래서 <A> 심볼의 노드에 Derive 태스크를 실행하면 A 심볼의 노드를 추가하고, <A> 심볼의 노드에 Progress 태스크가 실행되면 새로운 노드에는 NotExists 조건이 추가된다.

LookaheadExcept 심볼도 비슷한 원리로 동작한다. LookaheadExcept 심볼은 derive 시에는 빈 시퀀스를 추가하고, Progress 시에는 NotExists 조건을 추가한다.

3..5에서 심볼 A가 매치되었을 때, 현재 generation이 5인 상태에서는 3..6이나 3..100에서 A가 매치될 지 어떨지 알 수 없다. 그래서 마치 A가 앞으로 매치되지 않을 것처럼 가정하고 일단 파싱을 계속 진행하되, 만약 미래에 더 긴 A의 매치 스트링이 발견되면 과거의 3..5에서 매치된 A가 3에서 시작된 가장 긴 A라고 가정하고 진행하며 파생된 내용을 모두 무효화할 수 있게 하는 것이다. 즉, 승인 조건의 핵심은 “원하지 않던 일이 결국 일어났을 때 일을 되돌릴 수 있도록, 일을 되돌릴 때 제거해야 할 노드들에 표시 해 두는 것”이라고 할 수 있다.

Exists

Exists(s, e, A)는 0 이상의 정수 k에 대해 source[s:e+k]가 A에 매치되는 k가 존재하는 경우에만 이 조건이 붙은 노드가 인정된다. 말로 적으면 좀 헷갈리지만, NotExists와 반대 의미라고 보면 된다. 그래서 LookaheadIs 심볼의 노드를 progress할 때는 Exists 조건이 추가된다. (LookaheadIs 심볼을 derive할 때는 LookaheadExcept와 마찬가지로 빈 시퀀스 노드가 추가된다)

Unless

Unless(s, e, A)가 붙은 노드는 source[s:e]가 심볼 A에 대해서 매칭될 수 없는 경우에만 인정된다. 만약 source[s:e]가 A로 매칭될 수 있다면 그 노드는 처음부터 존재하지 않았던 것과 마찬가지로 취급된다.

NotExists와 비슷해 보일 수도 있지만, NotExists는 입력 스트링에서 s에서 시작해서 e 이후에 끝나는 서브스트링 중 단 하나라도 심볼 A에 매칭되면 해당 노드를 무효화시키는 반면 Unless는 source[s:e]가 A로 매칭되는지 않는지만 확인한다. source[s:e+1]이나 source[s:e+2]는 신경쓰지 않는다는 것이다.

이 조건은 Except 심볼에서 사용된다. A-B라는 심볼의 노드 ((•A-B, s..s), ∅)는 Derive시 ((•A, s..s), ∅)(와 두 노드 사이의 엣지)를 추가하고, ((•A-B, s..s), ∅) 노드가 Progress될 때 새로 추가되는 (A-B•, s..e) 커널을 갖는 노드에는 Unless(B, s, e) 조건이 추가된다. 그래서 만약 source[s:e]에서 B가 매치될 수 있으면 해당 노드를 무효화한다.

이 때, ((•A-B, s..s), ∅)를 Derive하면 ((•A, s..s), ∅)와 ((•B, s..s), ∅) 노드가 모두 추가되는데, 엣지는 ((•A, s..s), ∅)로 가는 것 하나만 추가된다. 이는 ((•B, s..s), ∅)가 승인 조건의 evaluation을 위해 필요하긴 하지만, source[s:e]에서 A가 매치되지 않으면 ((•B, s..s), ∅)는 아무 의미가 없기 때문이다. ((•B, s..s), ∅)와 같은 노드들은 엣지만 고려하면 시작 노드에서 도달이 불가능할 수도 있지만, 그래프 트리밍시 승인 조건의 확인을 위해 살려두어야 한다.

OnlyIf

OnlyIf(s, e, A)는 Unless와 반대 의미를 갖는다. 즉, OnlyIf(s, e, A) 조건이 붙은 노드는 source[s:e]가 심볼 A에 대해 매치되는 경우에만 살아남는다. Join 심볼을 처리하기 위해 사용한다. Except에서와 마찬가지로 ((•A&B, s..s), ∅)를 Derive하면 ((•A, s..s), ∅)와 ((•B, s..s), ∅) 두 개의 노드가 추가되지만 엣지는 ((•A&B, s..s), ∅)에서 ((•A, s..s), ∅)로 가는 엣지만 추가된다.

이 네가지 조건은 코드로 다음과 같이 정의되어 있다. (AcceptCondition.scala)

sealed trait AcceptCondition extends Equals {
  ...
}

case class NotExists(beginGen: Int, endGen: Int, symbolId: Int)
    extends AcceptCondition with SymbolCondition {
  ...
}
case class Exists(beginGen: Int, endGen: Int, symbolId: Int)
    extends AcceptCondition with SymbolCondition {
  ...
}
case class Unless(beginGen: Int, endGen: Int, symbolId: Int)
    extends AcceptCondition with SymbolCondition {
  ...
}
case class OnlyIf(beginGen: Int, endGen: Int, symbolId: Int)
    extends AcceptCondition with SymbolCondition {
  ...
}

SymbolCondition이란 trait은 뒤에 나오는 nodes라는 멤버를 대신 계산해주는 trait으로, 뒤에서 다시 다루기로 하자.

승인 조건의 evaluation

실용성을 완전히 무시하고 이야기한다면, 파싱 컨텍스트의 노드가 위에서 말한 네가지 승인 조건들의 집합을 갖고, 그냥 계속해서 조건을 누적해가는 형태로 동작한다고 생각해도 된다. 하지만 실제 구현에서는, 승인 조건 중 절대 인정될 수 없는 조건이나 혹은 더이상 존재할 필요가 없는 조건이 나오면 최대한 빨리 제거해주어야 파싱을 원활히 할 수 있다.

그래서 실제 jparser 구현에서, 각 노드에 붙은 승인 조건은 파싱이 진행되면서 새로 얻어지는 정보를 반영하여 계속해서 업데이트된다. 그런데 새로 얻어지는 정보를 반영하려다 보면 어떤 승인 조건의 부정형(negation)을 얻어야 하는 경우가 있었고, 단순한 승인 조건들의 집합으로는 이런 부정형의 승인 조건을 나타내기가 어려웠다. 그래서 위의 네가지 승인 조건들을 묶기 위한 네가지의 조건을 추가로 만들었다. Always, Never, And, 그리고 Or이다.

Always는 노드에 아무 조건이 걸리지 않았음을 의미하고, 빈 승인 조건이라고 생각해도 좋다. 평이한 CDG를 파싱하면 등장하는 모든 노드에는 Always 조건이 붙을 것이다. Never는 반대로 이 조건은 절대로 만족될 수 없으며, 따라서 해당 노드가 완전히 무효화되었으므로 더이상 고려할 필요가 없음을 나타낸다. 만약 파싱을 진행하다 어떤 노드에 Never 조건이 붙으면 그 노드는 더이상 추적할 필요가 없으니 파싱 컨텍스트에서 제거해도 좋다. And는 여러개의 승인 조건들을 모두 만족해야 함을 나타내고, Or는 여러 개의 승인 조건 중 하나만이라도 만족되면 해당 노드가 인정됨을 나타낸다.

case object Always extends AcceptCondition {
  ...
}
case object Never extends AcceptCondition {
  ...
}
case class And(conditions: Set[AcceptCondition]) extends AcceptCondition {
  ...
}
case class Or(conditions: Set[AcceptCondition]) extends AcceptCondition {
  ...
}

Always와 Never는 인자를 받지 않기 때문에 object로 정의했다. 이제 소개한 총 8개의 승인 조건 클래스들의 내용을 살펴보자.

sealed trait AcceptCondition extends Equals {
  def nodes: Set[Node]
  def evaluate(gen: Int, graph: Graph): AcceptCondition
  def acceptable(gen: Int, graph: Graph): Boolean
  def neg: AcceptCondition
}

일단 AcceptCondition trait에는 4개의 메소드가 정의되어 있다.

이제 각 조건의 내용을 살펴보자. 간단한 Always와 Never부터 살펴보자.

case object Always extends AcceptCondition {
  val nodes: Set[Node] = Set()
  def evaluate(gen: Int, graph: Graph): AcceptCondition = this
  def acceptable(gen: Int, graph: Graph) = true
  def neg: AcceptCondition = Never
}

case object Never extends AcceptCondition {
  val nodes: Set[Node] = Set()
  def evaluate(gen: Int, graph: Graph): AcceptCondition = this
  def acceptable(gen: Int, graph: Graph) = false
  def neg: AcceptCondition = Always
}

Always는 관련된 노드가 없으므로 nodes는 빈 집합을 반환하고, 파싱 컨텍스트가 아무리 바뀌어도 Always는 계속 Always이므로 evaluate는 Always를 반환한다. Always의 정의에 따라 acceptable은 항상 true를 반환하고, neg는 Never를 반환한다. Never의 내용도 직관적으로 이해할 수 있다.

case class And(conditions: Set[AcceptCondition]) extends AcceptCondition {
  def nodes: Set[Node] = conditions flatMap { _.nodes }
  def evaluate(gen: Int, graph: Graph): AcceptCondition =
    conditions.foldLeft[AcceptCondition](Always) { (cc, condition) =>
      conjunct(condition.evaluate(gen, graph), cc)
    }
  def acceptable(gen: Int, graph: Graph): Boolean =
    conditions forall { _.acceptable(gen, graph) }
  def neg: AcceptCondition = disjunct((conditions map { _.neg }).toSeq: _*)
}

case class Or(conditions: Set[AcceptCondition]) extends AcceptCondition {
  def nodes: Set[Node] = conditions flatMap { _.nodes }
  def evaluate(gen: Int, graph: Graph): AcceptCondition =
    conditions.foldLeft[AcceptCondition](Never) { (cc, condition) =>
      disjunct(condition.evaluate(gen, graph), cc)
    }
  def acceptable(gen: Int, graph: Graph): Boolean =
    conditions exists { _.acceptable(gen, graph) }
  def neg: AcceptCondition = conjunct((conditions map { _.neg }).toSeq: _*)
}

And와 Or 모두 nodes는 연관된 AcceptCondition 모두의 nodes를 모두 합쳐서 반환한다. acceptable은 각 조건의 의미대로 And는 연관된 모든 승인 조건이 acceptable에 true를 반환하는 경우에 true를 반환하고, Or는 연관된 승인 조건 중 acceptable이 true를 반환하는 것이 하나라도 있으면 true를 반환한다.

그런데 evaluate와 neg에서 conjunct와 disjunct라는 함수가 나온다. 쉽게 말해 conjunct는 여러 개의 AcceptCondition 객체들을 주면 그것들을 and로 묶은 것을 반환하고, disjunct는 or로 묶은 것을 반환하는 함수이다. 그냥 And 클래스나 Or 클래스 객체를 만들어도 의미상은 똑같겠지만, conditions가 하나뿐인 And나 Or를 만들고싶지 않아서 별도의 함수에서 처리하도록 했다. 이들 함수는 다음과 같다.

// conjunct는 condition들을 and로 연결
def conjunct(conditions: AcceptCondition*): AcceptCondition =
  if (conditions contains Never) Never
  else {
    val conds1 = conditions flatMap {
      case And(set) => set
      case item => Set(item)
    }
    val conds2 = conds1.toSet filter { _ != Always }
    if (conds2.isEmpty) Always
    else if (conds2.size == 1) conds2.head
    else {
      // 상충되는 두 조건(e.g. Exist(a, b, c)와 NotExists(a, b, c))이 함께 들어 있으면 Never 반환
      if (containsConflictingConditions(conds2)) Never else And(conds2)
    }
  }

// disjunct는 condition들을 or로 연결
def disjunct(conditions: AcceptCondition*): AcceptCondition = {
  if (conditions contains Always) Always
  else {
    val conds1 = conditions flatMap {
      case Or(set) => set
      case item => Set(item)
    }
    val conds2 = conds1.toSet filter { _ != Never }
    if (conds2.isEmpty) Never
    else if (conds2.size == 1) conds2.head
    else {
      // 상충되는 두 조건(e.g. Exist(a, b, c)와 NotExists(a, b, c))이 함께 들어 있으면 Always 반환
      if (containsConflictingConditions(conds2)) Always else Or(conds2)
    }
  }
}

private def containsConflictingConditions(conditions: Set[AcceptCondition]): Boolean = conditions exists {
  case NotExists(beginGen, endGen, symbolId) => conditions contains Exists(beginGen, endGen, symbolId)
  case Exists(beginGen, endGen, symbolId) => conditions contains NotExists(beginGen, endGen, symbolId)
  case Unless(beginGen, endGen, symbolId) => conditions contains OnlyIf(beginGen, endGen, symbolId)
  case OnlyIf(beginGen, endGen, symbolId) => conditions contains Unless(beginGen, endGen, symbolId)
  case _ => false
}

특별한 내용은 없기 때문에 자세히 설명하지는 않아도 될 것 같다.

이제 나머지 네 개의 승인 조건 중 비교적 단순한 OnlyIf부터 살펴보자.

case class OnlyIf(beginGen: Int, endGen: Int, symbolId: Int)
    extends AcceptCondition with SymbolCondition {
  def evaluate(gen: Int, graph: Graph): AcceptCondition = {
    assert(gen >= endGen)
    if (gen > endGen) {
      Never
    } else {
      val conditions = graph.conditionsOf(kernel1(gen))
      disjunct(conditions.toSeq: _*).evaluate(gen, graph)
    }
  }
  def acceptable(gen: Int, graph: Graph): Boolean = {
    assert(gen >= endGen)
    if (gen != endGen) false else {
      graph.conditionsOf(kernel1(gen)) exists { _.acceptable(gen, graph) }
    }
  }
  def neg: AcceptCondition = Unless(beginGen, endGen, symbolId)
}

우선 NotExists, Exists, Unless, OnlyIf 네 개의 AcceptCondition들은 SymbolCondition이란 trait도 상속받고 있는데, 이 SymbolCondition이 nodes를 대신 계산해준다. 이 네 가지 승인 조건들은 모두 심볼(symbolId), 시작 지점(beginGen)과 종료 지점(endGen)을 인자로 받는데, 이 승인 조건이 파싱 컨텍스트에 남아있을 수 있는 상황은 포인터가 0인 해당 심볼의 노드가 파싱 컨텍스트에 있는 경우 뿐이다. 그리고 포인터가 0인 커널을 가진 노드는 태생적으로 승인 조건이 무조건 Always이기 때문에, symbolId와 beginGen만 알면 (endGen은 beginGen과 동일할 것이기 때문에) nodes를 계산할 수 있다.

sealed trait SymbolCondition extends AcceptCondition {
  val symbolId: Int
  val beginGen: Int

  lazy val node0: Node = Node(Kernel(symbolId, 0, beginGen, beginGen), Always)
  def kernel1(endGen: Int): Kernel = Kernel(symbolId, 1, beginGen, endGen)
  lazy val nodes: Set[Node] = Set(node0)
}

가장 단순한 neg부터 보면, 정의상 OnlyIf의 반대 의미를 갖는 조건은 Unless이기 때문에 neg는 Unless 클래스를 반환한다. evaluate와 acceptable 함수에서는 graph.conditionsOf라는 함수를 사용하고 있는데, 이 함수는 커널을 하나 받아서 graph에 존재하는 노드들 중 해당 커널을 가진 노드들의 승인 조건을 모아서 반환한다.

OnlyIf는 생성될 때 항상 endGen이 현재 생성중인 파싱 컨텍스트의 generation 숫자(코드상에서 주로 nextGen라는 이름으로 쓰였던)로 설정된다. 그래서 파싱이 진행되면서 acceptable이나 evaluate 함수에서 받게 될 generation 숫자인 gen은 endGen보다 크거나 같아야 한다. 그리고 의미상 endGen을 지난 시점에는 Unless 조건이 발동될 수 없기 때문에 acceptable 함수는 gen != endGen인 경우(실은 gen > endGen도 같은 의미) 무조건 true를 반환한다. 만약 gen == endGen인 경우엔 먼저 graph.conditionsOf 함수에 (symbol, 1, beginGen..endGen) 커널을 줘서(kernel1함수가 이런 커널을 생성해준다) beginGen과 endGen 사이에서 symbol이 매치된 경우가 있는지 찾고, 있다면 그들의 승인 조건을 수집한다. 이렇게 수집된 승인 조건이 두 개 이상인 경우, 그 중 하나라도 acceptable하면 해당 커널은 해당 범위에서 매치될 수 있다는 의미이다.

evaluate함수에서는, gen > endGen인 경우 대상이 되는 generation을 지나쳤다는 의미로 OnlyIf 조건이 더이상 인정될 가능성이 없어졌기 때문에 Never로 치환된다. 만약 gen == endGen인 경우엔 acceptable과 비슷하게 동작한다. 주의할 점은 OnlyIf 자체는 endGen 시점을 지나면 휘발성으로 사라지지만, OnlyIf의 evaluate가 반환한 조건은 계속 살아남을 수 있다는 점이다. 뒤의 &Token 섹션에서 이런 경우의 실제 사례를 살펴볼 것이다.

case class Unless(beginGen: Int, endGen: Int, symbolId: Int)
    extends AcceptCondition with SymbolCondition {
  def evaluate(gen: Int, graph: Graph): AcceptCondition = {
    assert(gen >= endGen)
    if (gen > endGen) {
      Always
    } else {
      val conditions = graph.conditionsOf(kernel1(gen))
      disjunct(conditions.toSeq: _*).neg.evaluate(gen, graph)
    }
  }
  def acceptable(gen: Int, graph: Graph): Boolean = {
    assert(gen >= endGen)
    if (gen != endGen) true else {
      graph.conditionsOf(kernel1(gen)) forall { _.acceptable(gen, graph) == false }
    }
  }
  def neg: AcceptCondition = OnlyIf(beginGen, endGen, symbolId)
}

Unless는 OnlyIf의 대칭점에 있는 승인 조건이다. 내용은 OnlyIf와 거의 동일한데, 한가지 차이점은 evaluate에서 neg 메소드를 사용한다는 점이다.

case class Exists(beginGen: Int, endGen: Int, symbolId: Int)
    extends AcceptCondition with SymbolCondition {
  def evaluate(gen: Int, graph: Graph): AcceptCondition = {
    if (gen < endGen) this else {
      val conditions0 = graph.conditionsOf(kernel1(gen)) map { _.evaluate(gen, graph) }
      val conditions = conditions0 ++ (if (graph.nodes contains node0) Set(this) else Set())
      disjunct(conditions.toSeq: _*)
    }
  }
  def acceptable(gen: Int, graph: Graph): Boolean = {
    if (gen < endGen) false else {
      graph.conditionsOf(kernel1(gen)) exists { _.acceptable(gen, graph) }
    }
  }
  def neg: AcceptCondition = NotExists(beginGen, endGen, symbolId)
}

Exists 조건은 beginGen부터 시작해서 endGen 이후로 어느 시점에든 대상 심볼이 매치되는 것이 발견되는 경우에만 노드가 인정되는 승인 조건이다. acceptable은 먼저 gen < endGen인지 확인해서 그렇다면 false를 반환한다. Exists 조건의 정의가 endGen “이후로” 심볼의 매치가 발견되는 경우만 포함하기 때문이다. else절에서 gen >= endGen인 경우, graph.conditionsOf로 (symbol, 1, beginGen..endGen) 커널을 갖는 노드가 존재하는지 찾고, 존재한다면 그 노드들의 승인 조건을 모아서 반환 받는다. 이들 승인 조건 중 하나라도 만족되면 해당 노드는 살아남게 되고, beginGen..endGen 사이에서 심볼이 매치된 것이 된다.

evaluate는 앞서 살펴본 OnlyIf랑 비슷한데, 한가지 다른 점은, graph에 (symbol, 0, beginGen..beginGen) 커널의 노드(with SymbolCondition에 정의된 node0)가 존재하면 이 조건을 존속시킨다는 점이다. 이게 의미하는 것이 무엇인가 하면, Exists 조건은 그 의미상 endGen을 지난 어떤 시점에라도 대상 심볼에 대한 매치가 발견되면 노드가 인정되고, 그 이후 어떤 시점에도 매치가 발견되지 않으면 최종적으로 노드는 인정되지 않는다. node0가 현재 파싱 컨텍스트에 살아남아 있다는 것은, beginGen에서 시작해서 gen 이후에 끝나는 서브 스트링에 대해 심볼이 매치될 수 있는 가능성이 아직 남아있다는 의미이다. 그래서 그런 경우엔 이 Exists 조건을 유지시켜야 하는 것이다.

neg는 의미상 NotExists를 반환한다.

case class NotExists(beginGen: Int, endGen: Int, symbolId: Int)
    extends AcceptCondition with SymbolCondition {
  def evaluate(gen: Int, graph: Graph): AcceptCondition = {
    if (gen < endGen) this else {
      val conditions0 = graph.conditionsOf(kernel1(gen)) map { _.neg.evaluate(gen, graph) }
      val conditions = conditions0 ++ (if (graph.nodes contains node0) Set(this) else Set())
      conjunct(conditions.toSeq: _*)
    }
  }
  def acceptable(gen: Int, graph: Graph): Boolean = {
    if (gen < endGen) true else {
      graph.conditionsOf(kernel1(gen)) forall { _.acceptable(gen, graph) == false }
    }
  }
  def neg: AcceptCondition = Exists(beginGen, endGen, symbolId)
}

NotExists는 Exists의 거울상과도 같은 존재이다. 앞서 OnlyIf와 Unless의 관계와 비슷하고, evaluate 함수에서 neg 메소드가 사용된다.

파싱 예제

다음 문법을 보자.

Tokens = Token*
Token = Identifier | Keyword | Punctuation
Identifier = Word-Keyword
Keyword = ("if" | "else")&Word
Word = <'a-z'+>
Punctuation = ','

Identifier, Keyword, Punctuation 세 종류의 토큰의 어레이를 파싱하는 문법이다. 다음은 이 문법의 초기 컨텍스트이다.

그래프

여기에 x라는 입력이 들어왔다고 해보자. x라는 입력은 그 자체로 Word가 되고, Keyword는 아니기 때문에 Identifier이며, 따라서 Token이기도 하다. 그래서 x라는 입력을 처리한 뒤의 파싱 컨텍스트는 다음과 같은 형태가 된다.

그래프

그래프가 너무 커서 보기가 어려우니 필요한 부분만 떼어서 보자.

그래프

((•['a-z'+],0..0),∅) 노드(프록시 심볼 노드)에 대한 Progress까지는 새로울 것이 없고, 그렇게 해서 생성된 ((['a-z'+]•,0..1),∅) 노드의 승인 조건도 여전히 비어있는 상태다. 그런데 연쇄적으로 실행되는 다음 Progress가 longest 심볼 노드에 대한 것이고, 여기에 longest 심볼을 위한 조건이 추가된다. 그래서 (<['a-z'+]>•, 0..1) 커널과 함께 조건 NotExists 0 2 ['a-z'+]이 조합된 노드가 생겼다. 이제 이 노드로부터 파생되는 모든 노드는 0에서 시작해서 2 이후에 'a-z'+ 심볼에 매치될 수 있는 서브 스트링이 발견되면, 즉 0 이상의 정수 k에 대해 source[0:2+k]에서 'a-z'+ 심볼에 매치되는 경우 없던것처럼 취급당한다는 뜻이다. 그래서 ((•Word,0..0),∅) 노드에 대한 Progress 태스크로 인해 생겨난 노드에도 동일하게 NotExists 0 2 ['a-z'+] 조건이 설정되어 있다.

그리고 연쇄적으로 이어서 실행되는 ((•Word-Keyword,0..0),∅) 노드에서는 except 심볼에 의해 새로운 조건이 하나 더 추가된다(∧ 기호는 and라는 의미로 쓰였다). 바로 Unless 0 1 Keyword 조건이다. Word-Keyword 라는 심볼의 의미 그대로, 0..1 에서 Word가 매치된 것은 알았으나, 0..1이라는 영역이 Keyword 심볼로는 매치될 수 없는 경우에만 0..1이 Word-Keyword에 매치되어야 하기 때문에 이런 조건이 추가된 것이다. 그리고 이 조건은 그 이후로 연쇄적으로 실행되는 Identifier, Token, Token* Token, Token*, 그리고 마지막에 Tokens 심볼의 노드에까지 전달되어 (Tokens•,0..1) 커널의 노드에는 NotExists 0 2 ['a-z'+]와 Unless 0 1 Keyword 조건이 추가되어 있다.

그러면 이제 이 조건들에 대해 생각해보자. Unless 0 1 Keyword라는 조건을 먼저 살펴보면, 0..1 사이에서 Kernel 심볼이 매치되었으려면 (Kernel•,0..1) 커널의 노드가 파싱 컨텍스트에 있었어야 했는데 존재하지 않는다. 따라서 Unless 0 1 Keyword가 붙어 있는 노드들은 gen=1에서 이 조건때문에 탈락할 가능성은 없고, 그 이후의 generation에서도 이 조건은 의미가 없다.

NotExists 0 2 ['a-z'+] 조건의 경우, 아직 generation 1을 처리하고 있기 때문에 현재로썬 이 조건이 승인될지 탈락될 지 알 수가 없다. 그래서 다음 generation에서도 이 조건은 그대로 존속시켜야 하고, 만약 파싱이 gen=1에서 종료된다면 최종적으로 이 조건이 붙은 노드들은 승인되어야 한다.

그래서 그래프 트리밍과 승인 조건 evaluate를 거쳐서 완성된 gen=1 파싱 컨텍스트는 다음과 같다.

그래프

중요한 부분만 확대해서 보자.

그래프

테두리가 점선으로 표시된 ((Token*•Token,0..1),NotExists 0 2 ['a-z'+])와 ((Token*•Token,0..0),∅) 두 개의 노드만 잘 이해하면 된다. 첫번째 노드는 0..1에서 매치된 “x”가 그대로 토큰으로 인정되는 경우를 가정하고 파싱을 진행하는 노드이고, 두번째 노드는 0..1에서 매치된 “x”가 0에서 시작하는 더 긴 노드(예를 들면 “xyz”같은)의 일부였을 가능성을 추적하는 노드이다. 첫번째 노드에 NotExists 승인 조건이 붙어있는 이유는 0에서 시작하는 0..1보다 더 긴 토큰이 발견되지 않는 경우에만 0..1을 하나의 토큰으로 인정할 수 있기 때문이다.

이 문법에 i, if, ifx 같은 1. 키워드의 일부일 수 있는 입력, 2. 실제로 키워드인 입력, 3. 키워드 뒤에 뭐가 더 붙은 입력 등을 넣어서 파서가 어떻게 동작하는지 확인해보는 것도 재미있다. 관심 있는 사람은 jparser에서 실험해보아도 좋겠다. 하지만 그 과정을 모두 설명하려면 포스팅이 너무 길어지니까 이쯤에서 줄이고 i가 입력된 파싱 컨텍스트와 if가 입력된 파싱 컨텍스트를 첨부하고 포스팅을 마무리하기로 하자.

그래프

그래프

전체 목차:

이제 파싱 알고리즘은 모두 살펴봤다. 이제 파싱 결과로부터 파스 트리를 만드는 방법을 알아보자.

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