DeepintoPharo:Chapter 18

제 18 장 PetitParser: Modular 파서 빌드하기

PetitParser: Modular 파서 빌드하기

작성자:

Jan Kurs (kurs@iam.unibe.ch)

Guillaume Larcheveque (guillaume.larcheveque@gmail.com)

Lukas Renggli (renggli@gmail.com)

데이터를 분석하고 변형하기 위해 파서를 빌드하는 것은 소프트웨어 개발에서 공통적인 작업에 해당한다. 따라서 이번 장에서는 PetitParser라는 강력한 파서 프레임워크를 제시하고자 한다. PetitParser는 다양한 파싱 기술로부터 아이디어를 결합하여 문법과 파서를 객체로서 모델링하여 동적으로 재설정(reconfigured) 할 수 있도록 한다. PetitParser는 Lukas Renggli가 Helvetia 시스템^[1]을 작업하면서 그 일부로 작성하였으나 독립적인 라이브러리로 사용할 수도 있다.

PetitParser를 이용해 파서 작성하기

PetitParser는 다른 유명한 파서 생성기와는 다른 파싱 프레임워크다. PetitParser는 스몰토크 코드를 이용해 파서를 정의하고 문법을 동적으로 재사용, 작성, 변형, 확장하기 수월하게 만든다. 우리는 이를 결과적 문법에 반영하고 상황에 따라 수정할 수 있다. 따라서 PetitParser는 스몰토크의 동적인 특성에 잘 맞는다.

게다가 PetitP는 SmaCC이나 ANTLR과 달리 테이블을 기반으로 하지 않는다. 대신 네 가지의 대안적 파서 방법론을 결합하여 사용하는데, 이는 scannerless parser, parser combinator, parsing expression grammer, packrat parser가 해당한다. 그러한 PetitParser는 무엇을 파싱할 수 있는지에 더 강력한 기능을 보인다. 네 가지 파서 방법론을 간략하게 살펴보자.

Scannerless parser는 두 개의 독립된 툴(스캐너와 파서)이 하는 일을 하나로 결합한다. 따라서 문법을 작성하기 훨씬 간단해지고, 문법을 작성할 때 공통적으로 직면하는 문제를 피하도록 해준다.
Parser Combinator는 구성 가능한 객체의 그래프로서 모델화된 파서에 대한 빌딩 블록이다. 이들은 모듈식으로서 관리가 가능하고(maintainable), 변경, 재구성, 변형, 반영 가능하다.
Parsing expression grammars (PEGs)는 정렬된 선택의 개념을 제공한다. Parser combinator와 달리 PEGs의 정렬된 선택은 항상 첫 번째 매칭 대안책을 따르고 다른 대안들은 무시한다. 유효한 입력의 경우 언제나 정확히 하나의 파스 트리를 야기하고, 파싱의 결과는 결코 모호하지 않다.
Packrat Parsers는 선형의 파싱 시간 보장을 제공하고 PEGs에서의 왼쪽 재귀(left recursion)에 발생하는 공통 문제를 피하도록 해준다.

PetitParser 로딩하기

충분히 설명했으니 본격적으로 시작해보자. PetitParser는 Pharo에서 개발되며, Java와 Dart에 이용 가능한 버전도 있다. 사용할 준비가 된 이미지를 다운로드할 수 있다^[2]. PetitParser를 기존 이미지에 로딩하기 위해서는 아래 Gofer 표현식을 평가하라.

스크립트 18.1: PetitParser 설치하기

Gofer new
    smalltalkhubUser: 'Moose' project: 'PetitParser';
    package: 'ConfigurationOfPetitParser';
    load.
(Smalltalk at: #ConfigurationOfPetitParser) perform: #loadDefault.

PetitParser를 사용하는 방법에 관한 상세한 정보는 Moose book^[3]의 petit parser와 관련된 장에서 찾을 수 있다.

간단한 문법 작성하기

PetitParser으로 문법을 작성하기란 스몰토크 코드를 작성하는 것 만큼이나 간단한 일이다. 가령, 문자로 시작해 그 뒤에 0 또는 더 많은 문자나 숫자가 붙은 식별자를 파싱하는 문법은 아래와 같이 정의되고 사용된다.

스크립트 18.2: 식별자를 파싱하기 위한 첫 번째 파서 생성하기.

|identifier|
identifier := #letter asParser , #word asParser star.
identifier parse: 'a987jlkj' → #($a #($9 $8 $7 $j $l $k $j))

그래픽 표기법

그림 18.1은 식별자 파서의 구문 해석도를 나타낸다. 각 상자마다 하나의 파서를 표시한다. 상자들 간 화살표는 입력이 소모되는 흐름을 나타낸다. 모서리가 둥근 상자는 기본 파서들(terminals)이다. 네모난 상자(그림에 표시되지 않음)는 다른 파서들로 (non-terminal) 구성된 파서들이다.

앞의 스크립트에서 identifier 객체를 살펴보면 이것이 PPSequenceParser의 인스턴스임을 눈치챌 것이다. 해당 객체를 더 깊숙이 살펴보면 여러 파서 객체로 된 아래의 트리를 목격할 것이다.

스크립트 18.3: 식별자 파서에 사용된 파서의 구성.

PPSequenceParser (accepts a sequence of parsers)
    PPPredicateObjectParser (accepts a single letter)
    PPPossessiveRepeatingParser (accepts zero or more instances of another parser)
        PPPredicateObjectParser (accepts a single word character)

루트 파서는 시퀀스 파서인데 그 이유는 ,(콤마) 연산자가 (1) 문자 파서, (2) 0개 또는 그 이상의 워드(word) 문자 파서에 대한 시퀀스를 생성하기 때문이다. 루트 파서 첫 번째 자식은 #letter asParser 표현식으로 생성된 서술(predicate) 객체 파서이다. 해당 파서는 Character>>isLetter 메서드가 정의한 바와 같이 단일 문자를 파싱할 수 있다. 두 번째 자식은 star 호출에 의해 생성된 반복 파서로서 입력 상에서 그 자식 파서를 (또 다른 서술 객체 파서) 가능한 한 많이 사용한다 (예: 욕심이 많은 파서이다). 그 자식 파서는 #word asParser 표현식으로 생성된 서술 객체 파서이다. 해당 파서는 Character>>isDigit과 Character>>isLetter 메서드가 정의한 대로 한 자리 숫자 또는 문자의 파싱이 가능하다.

일부 입력 파싱하기

문자열(또는 스트림)을 실제로 파싱하기 위해 아래와 같이 PPParser>>parse:를 이용한다.

스크립트 18.4: 식별자 파서를 이용해 일부 입력 문자열 파싱하기.

identifier parse: 'yeah'. → #($y #($e $a $h))
identifier parse: 'f123'. → #($f #($1 $2 $3))

문자를 리턴 값으로 한 중첩 배열을 얻는 것이 이상하게 보이겠지만 이는 입력이 파스 트리로 분해되는 기본적인 모습이다. 맞춤설정하는 방식은 머지않아 살펴보겠다.

유효하지 않은 입력을 파싱할 경우 PPFailure의 인스턴스를 응답으로 얻는다.

스크립트 18.5: 무효한 입력을 파싱 시 실패를 야기한다

identifier parse: '123'. → letter expected at 0

이러한 파싱은 실패를 야기하는데, 그 이유는 첫 번째 문자(1)가 글자(letter)가 아니기 때문이다. PPFailure의 인스턴스는 당신이 #isPetitFailure 메시지를 전송할 때 true를 응답하는 시스템 내의 객체에 불과하다. 오류가 발생할 경우 예외를 던지기 위해 PPParser>>parse:onError:를 사용할 수도 있다.

identifier
    parse: '123'
    onError: [ :msg :pos | self error: msg ].

주어진 문자열(또는 스트림)의 매칭 여부에만 관심이 있다면 다음 구조체를 사용해도 좋다.

스크립트 18.6: 일부 입력이 식별자인지 확인하기

identifier matches: 'foo'. → true
identifier matches: '123'. → false
identifier matches: 'foo()'. → true

마지막 결과를 보고 놀랄지도 모른다. 사실 괄호는 #word asParser 표현식에 명시된 바와 같이 숫자도 아니고 글자도 아니다. 사실상 identifier 파서는 "foo"에 매치하고, 이것만으로 PPParser>>matches: 호출이 true를 리턴하기엔 충분하다. 결과는 #($f #($o$o))를 리턴하게 될 parse:를 사용할 때와 유사하다.

전체 입력이 확실히 매칭하길 원한다면 아래처럼 PPParser>>end 메시지를 사용하라.

스크립트 18.7: PPParser>>end를 이용해 전체 입력이 매칭하도록 하기

identifier end matches: 'foo()'. → false

PPParser>>end 메시지는 입력의 끝에 미창하는 새로운 파서를 생성한다. 쉽게 파서를 구성할 수 있으려면 기본 값으로 파서가 입력의 끝에 매칭하지 않도록 하는 것이 중요하다. 이러한 점 때문에 당신은 PPParser>>matchesSkipIn:와 PPParser>>matchesIn: 메시지를 이용해 파서가 매칭할 수 있는 모든 장소를 찾는 데에 흥미를 가질지도 모른다.

스크립트 18.8: 입력에서 모든 매치 찾기

identifier matchesSkipIn: 'foo 123 bar12'.
    → an OrderedCollection(#($f #($o $o)) #($b #($a $r $1 $2)))

identifier matchesIn: 'foo 123 bar12'.
    → an OrderedCollection(#($f #($o $o)) #($o #($o)) #($o #()) #($b #($a $r $1 $2)) #($a #($r $1 $2)) #($r #($1 $2)))

PPParser>>matchesSkipIn: 메서드는 매칭한 내용을 포함하는 배열의 컬렉션을 리턴한다. 해당 함수는 동일한 문자를 두 번 파싱하는 것을 피한다. PPParser>>matchesIn: 도 비슷한 일을 하지만 가능한 하위 파싱된(sub-parsed) 요소를 모두 포함한 컬렉션을 리턴하는데, 가령 identifier matchesIn: 'foo 123 bar12'를 평가하면 6개 요소의 컬렉션을 리턴한다.

이와 유사하게 주어진 입력에서 모든 매칭 범위를 (첫 번째 문자의 색인과 마지막 문자의 색인) 찾기 위해서는 PPParser>>matchingSkipRangesIn: 또는 PPParser>>matchingRangesIn: 를 아래 스크립트와 같이 사용할 수 있다.

스크립트 18.9: 입력에 매칭하는 모든 범위 찾기

identifier matchingSkipRangesIn: 'foo 123 bar12'.
    → an OrderedCollection((1 to: 3) (9 to: 13))

identifier matchingRangesIn: 'foo 123 bar12'.
    → an OrderedCollection((1 to: 3) (2 to: 3) (3 to: 3) (9 to: 13) (10 to: 13) (11 to: 13))

그 외 파서 유형

PetitParser는 복잡한 언어를 소모하거나 임의로 변형하기 위해 구성할 수 있는 즉시 사용 가능한 파서의 거대한 집합을 제공한다. 그 중에서 터미널(terminal) 파서가 가장 간단하다. 이미 몇 가지를 살펴봤고, 몇 가지만 더 프로토콜 Table 18.1에서 정의하겠다.

PPPredicateObjectParser 의 클래스 측은 좀 더 복잡한 terminal 파서를 빌드하는 데에 사용할 수 있는 다른 팩토리(factory) 메서드를 많이 제공한다. 이를 사용하기 위해서는 팩토리 메서드의 이름을 포함한 부호로 PPParser>>asParser 메시지를 전송하라(예: #punctuation asParser).

다음 파서 집합은 다른 파서들을 결합하는 데에 사용되며, 프로토콜 표 18.2 에서 정의된다.

terminal 파서	설명
$a asParser	$a 문자를 파싱한다.
'abc' asParser	'abc ' 문자열을 파싱한다.
#any asParser	어떤 문자든 파싱한다.
#digit asParser	한 자리 숫자(0..9)를 파싱한다.
#letter asParser	하나의 글자를 파싱한다 (a..z 그리고 A..Z).
#word asParser	한 자리 숫자 또는 글자를 파싱한다.
#blank asParser	공백이나 도표(tabulation)를 파싱한다.
#newline asParser	carriage return 또는 행 피드 문자를 파싱한다.
#space asParser	새로운 행을 포함해 어떤 흰 공백 문자든 파싱한다.
#tab asParser	탭 문자를 파싱한다.
#lowercase asParser	소문자로 된 문자를 파싱한다.
#uppercase asParser	대문자로 된 문자를 파싱한다.
nil asParser	아무 것도 파싱하지 않는다.
표 18.1: PetitParser 는 다수의 terminal 파서를 사전 정의한다.

Parser Combinators	설명
p1 , p2	p1을 파싱하고 나서 p2를 파싱한다 (시퀀스).
p1 / p2	p1을 파싱하고, 효과가 없으면 p2를 파싱한다.
p star	0개 또는 그 이상의 p를 파싱한다.
p plus	1개 또는 그 이상의 p를 파싱한다.
p optional	가능하다면 p를 파싱한다.
p and	p를 파싱하되 그 입력은 소모하지 않는다.
p negate	p를 파싱하고, p가 실패하면 성공한다.
p not	p를 파싱하고, p가 실패하면 성공하지만 그 입력은 소모하지 않는다.
p end	p를 파싱하고, 입력 끝에서만 성공한다.
p times: n	p를 정확히 n 횟수만큼 파싱한다.
p min: n max: m	p를 최소 n 배 이상 m 배 이하로 파싱한다.
p starLazy: q	star와 같지만 q가 성공하면 소모를 중단한다.
표 18.2: PetitParser는 다수의 parser combinator를 사전 정의한다

파서 결합(parser combination)의 간단한 예제로 아래 identifier2 파서의 정의가 앞서 소개한 identifier의 정의와 동일함을 보이겠다.

스크립트 18.10: identifier 파서를 표현하는 다른 방법

identifier2 := #letter asParser , (#letter asParser / #digit asParser) star.

파서 액션

파서에서 액션이나 변형을 정의하기 위해서는 프로토콜 Table 18.3에 정의된 PPParser>>==>, PPParser>>flatten, PPParser>>token, PPParser>>trim 중 하나를 사용할 수 있다.

액션 파서	설명
p flatten	p의 결과로부터 문자열을 생성한다.
p token	flatten과 비슷하지만 세부 내용과 함께 PPToken을 리턴한다.
p trim	p 전후에 흰 공백을 제거(trim)한다.
p trim: trimParser	trimParesr가 파싱할 수 있는 것은 무엇이든 제거한다 (예: 주석).
p ==> aBlock	주어진 aBlock 내에서 변형을 실행한다.
표 18.3: PetitParser 는 많은 액션 파서를 사전 정의한다.

매칭한 요소의 배열을 얻는 대신 파싱된 식별자의 문자열을 리턴하려면 그 곳으로 PPParser>>flatten 메시지를 전송하여 파서를 구성하라.

스크립트 18.11: flatten을 이용해 파싱 결과가 문자열이 되도록 하기

|identifier|
identifier := (#letter asParser , (#letter asParser / #digit asParser) star).
identifier parse: 'ajka0' 		→	 #($a #($j $k $a $0))

identifier flatten parse: 'ajka0' 		→ 	'ajka0'

PPParser>>token 메시지는 flatten과 유사하지만 token이 위치한 컬렉션, 컬렉션 내 그것의 위치 등 컨텍스트적 정보를 훨씬 더 많이 제공하는 PPToken을 리턴한다.

PPParser>>trim 메시지를 전송하면 파싱된 결과의 시작과 끝에 있는 흰 공백은 무시하도록 파서를 설정한다. 다음으로, 입력 상에서 첫 번째 파서를 사용할 경우 오류를 야기하는데, 파서가 공백(space)을 허용하지 않기 때문이다. 두 번째 파서를 이용해 공백이 무시되고 결과로부터 제거된다.

스크립트 18.12: PPParser>>trim를 이용해 공백 무시하기

|identifier|
identifier := (#letter asParser , #word asParser star) flatten.
identifier parse: ' ajka ' 	→ 	letter expected at 0

identifier trim parse: ' ajka ' 		→ 	'ajka'

trim 메시지를 전송하는 것은 #space asParser를 매개변수로 하여 PPParser>>trim:를 호출하는 것과 동일하다. 즉, trim:은 입력으로부터 다른 데이터, 즉 소스 코드 주석과 같은 데이터를 무시하는 데에 유용하다.

스크립트 18.13: PPParser>>trim를 이용해 주석 무시하기

| identifier comment ignorable line |
identifier := (#letter asParser , #word asParser star) flatten.
comment := '//' asParser, #newline asParser negate star.
ignorable := comment / #space asParser.
line := identifier trim: ignorable.
line parse: '// This is a comment
oneIdentifier // another comment' 	→ 	'oneIdentifier'

PPParser>>==> 메시지는 파서가 입력에 매칭할 때 실행되어야 할 블록을 명시하도록 해준다. 다음 절에는 이와 관련된 예제가 몇 가지 제시되어 있을 것이다. 문자열 표현으로부터 숫자(number)를 얻는 간단한 방식을 아래 소개하겠다.

스크립트 18.14: 정수 파싱하기

number := #digit asParser plus flatten ==> [ :str | str asNumber ].
number parse: '123' 		→ 	      123

표 18.3는 파서를 빌드 시 기본적인 요소들을 보여준다. PPParser의 operators 프로토콜에는 이보다 더 잘 문서화되고 테스트된 팩토리 메서드들이 몇 가지 더 있다. 이러한 팩토리 메서드에 대해 더 알고 싶다면 이러한 프로토콜을 살펴보라. 그 중에 흥미로운 메서드로 separatedBy: 를 들 수 있는데, 이는 입력을 다른 파서에 의해 명시된 구분(separation)을 바탕으로 하여 한 번 또는 그 이상 파싱하는 새 파서를 응답한다.

조금 더 복잡한 문법 작성하기

이제 간단한 산술 표현식을 평가하기 위해 좀 더 복잡한 문법을 작성한다. 위에서 정의된 숫자에 대한 (사실 정수) 문법을 이용하면, 우선순위 순서대로 덧셈과 곱셈의 production을 정의하는 것이 다음 단계가 된다. production은 서로 재귀적으로 참조하기 때문에 PPDelegateParser로서 인스턴스화함을 주목하라. #setParaser: 메서드는 이러한 재귀를 해결한다. 아래 스크립트는 덧셈, 곱셈, 괄호에 대해 3개의 파서를 정의한다 (이와 연관된 구문 해석도는 그림 18.4를 참고).

스크립트 8.15: 산술 표현식 파싱하기

term := PPDelegateParser new.
prod := PPDelegateParser new.
prim := PPDelegateParser new.

term setParser: (prod , $+ asParser trim , term ==> [ :nodes | nodes first + nodes last ])
        / prod.
prod setParser: (prim , $*asParser trim , prod ==> [ :nodes | nodes first*nodes last ])
        / prim.
prim setParser: ($( asParser trim , term , $) asParser trim ==> [ :nodes | nodes second ])
        / number.

term 파서는 (1) prod 다음에 '+', 그 다음에 다른 term이 따라오도록 정의되거나 (2) prod로서 정의된다. (1)의 경우 액션 블록은 파서에게 첫 번째 노드(prod)와 마지막 노드(term)의 값의 산술 덧셈을 계산해줄 것을 요청한다. Prod 파서는 term 파서와 유사하다. Prim 파서는 term 전후에 왼쪽과 오른쪽 괄호를 허용하는데 이를 단순히 무시하는 액션 블록을 갖고 있다는 점에서 흥미롭다.

productions의 우선순위를 이해하기 위해서는 그림 18.5를 참고한다. 그림의 트리에서 루트는 (term) 먼저 시도된 production이다. Term은 + 이거나 prod에 해당한다. term production이 먼저 오는데, +는 산술에서 우선순위가 가장 낮기 때문이다.

파서가 입력을 모두 소모하도록 확신하기 위해선 end 파서를 이용해 start production으로 래핑(wrap)한다.

start := term end.

이게 모두다. 그러면 파서를 테스트할 수 있다.

스크립트 18.16: 산술 표현식 evaluator 시도하기

start parse: '1 + 2 * 3'. → 7
start parse: '(1 + 2) * 3'. → 9

PetitParser를 이용한 Composite 문법

앞 절에서는 PetitParser의 기본 원리를 살펴보고 입문자를 위한 예제들을 몇 가지 제시하였다. 이번 절에서는 좀 더 복잡한 문법을 정의하는 방법을 소개할 것이다. 산술 표현식 문법을 계속해서 예로 들겠다.

앞에서와 같이 파서를 스크립트로서 작성하는 일은 번거로울 수 있으며, 특히 문법 production이 상호 재귀적이고 서로를 복잡한 방식으로 참조한다면 더 귀찮을 것이다. 게다가 단일 스크립트에 명시된 문법은 문법 중에서 특정 부분들을 재사용하기가 힘들 수밖에 없도록 만든다. 천만 다행으로 이를 위해 PPCompositeParser가 존재한다.

문법 정의하기

마지막 절에서 빌드한 것과 동일한 표현식 문법을 이용해 composite 파서를 생성하되, 이번에는 PPCompositeParser의 서브클래스에 정의해보자.

스크립트 18.17: 산술 표현식 문법을 보유하기 위한 클래스 생성하기

PPCompositeParser subclass: #ExpressionGrammar
    instanceVariableNames: ''
    classVariableNames: ''
    poolDictionaries: ''
    category: 'PetitTutorial'

다시 말하지만 정수 숫자에 대한 문법으로 시작한다. 아래와 같이 number 메서드를 정의하자.

스크립트 18.18: 첫 번째 파서를 메서드로서 구현하기

ExpressionGrammar>>number
    ^ #digit asParser plus flatten trim ==> [ :str | str asNumber ]

ExpressionGrammar 내의 모든 production은 그 파서를 리턴하는 메서드로서 명시된다. 우리도 이와 유사하게 term, prod, mul, prim productions를 정의한다. production들은 동일한 이름으로 된 각각의 인스턴스 변수를 읽음으로써 서로를 참조하고, PetitParser는 당신을 위해 이러한 인스턴스 변수를 자동으로 초기화해준다. 그리고 필요한 인스턴스 변수들을 처음으로 참조하면 Pharo가 자동으로 추가하도록 한다. 아래의 클래스 정의를 얻는다.

스크립트 18.19: 산술 표현식 문법을 보유하는 클래스 생성하기

PPCompositeParser subclass: #ExpressionGrammar
    instanceVariableNames: 'add prod term mul prim parens number'
    classVariableNames: ''
    poolDictionaries: ''
    category: 'PetitTutorial'

스크립트 18.20: 더 많은 표현식 문법 파서 정의하되, 연관된 액션 없이 정의하기

ExpressionGrammar>>term
    ^ add / prod

ExpressionGrammar>>add
    ^ prod , $+ asParser trim , term

ExpressionGrammar>>prod
    ^ mul / prim

ExpressionGrammar>>mul
    ^ prim , $* asParser trim , prod

ExpressionGrammar>>prim
    ^ parens / number

ExpressionGrammar>>parens
    ^ $( asParser trim , term , $) asParser trim

앞의 구현과 반대로 아직 production action를 정의하지 않고 (앞에서는 PParser>>==>를 이용해 정의함), 덧셈(add), 곱셈(mul), 괄호(parens)에 해당하는 부분들을 구분된 production들로 뽑아낸다. 이는 추후 재사용 가능성을 향상시킨다. 예를 들어 서브클래스는 그러한 메서드를 오버라이드하여 약간 다른 production 출력을 생성할 수도 있다. 주로 production 메서드들은 grammar로 명명된 프로토콜에서 (필요 시 가령 grammar-literals와 같이 좀 더 구체적인 프로토콜 이름으로 재정의 가능한) 분류된다.

표현식 문법의 시작점을 마지막으로 정의할 것인데 그 중요성은 앞에서 소개한 것 못지 않다. 이는 ExpressionGrammar 클래스에서 PPCompositeParser>>start 를 오버라이드함으로써 이루어진다.

스크립트 18.21: 표현식 문법 파서의 시작점 정의하기

ExpressionGrammar>>start
    ^ term end

ExpressionGrammar를 인스턴스화하면 기본 추상적-구문 트리를 리턴하는 표현식을 제공한다.

스크립트 18.22: 간단한 산술 표현식에서 파서 테스트하기

parser := ExpressionGrammar new.
parser parse: '1 + 2 * 3'. → #(1 $+ #(2 $ * 3)) 
parser parse: '(1 + 2) * 3'. → #(#($( #(1 $+ 2) $)) $ * 3)

의존 문법(dependent grammars) 작성하기

다른 문법이 정의한 파서도 쉽게 재사용이 가능하다. 예로, 방금 정의한 ExpressionGrammar에 숫자의 정의를 재사용하는 새 문법을 생성한다고 가정해보자. 이를 위해서는 ExpressionGrammar로 의존성을 선언해야 할 것이다.

스크립트 18.23: ExpressionGrammar 문법으로부터 number 파서 재사용하기

PPCompositeParser subclass: #MyNewGrammar
    instanceVariableNames: 'number'
    classVariableNames: ''
    poolDictionaries: ''
    category: 'PetitTutorial'

MyNewGrammar class>>dependencies
    "Answer a collection of PPCompositeParser classes that this parser directly
        dependends on."
    ^ {ExpressionGrammar}

MyNewGrammar>>number
    "Answer the same parser as ExpressionGrammar>>number."
    ^ (self dependencyAt: ExpressionGrammar) number

evaluator 정의하기

이제 문법을 정의했으니 evaluator를 구현하기 위해 해당 정의를 재사용할 수 있다. 이를 위해 ExpressionEvaluator라고 불리는 ExpressionGrammar의 서브클래스를 생성한다.

스크립트 18.24: 서브클래스를 생성함으로써 문법을 계산기로부터 분리하기

ExpressionGrammar subclass: #ExpressionEvaluator
    instanceVariableNames: ''
    classVariableNames: ''
    poolDictionaries: ''
    category: 'PetitTutorial'

우리의 평가 구문을 이용해 add, mul, parens의 구현을 재정의한다. 이는 아래 메서드에서 보이는 바와 같이 super 구현을 호출하고 리턴된 파서를 조정함으로써 가능하다.

스크립트 18.25: 산술 표현식을 평가하기 위해 일부 파서의 정의를 재정의하기

ExpressionEvaluator>>add
    ^ super add ==> [ :nodes | nodes first + nodes last ]

ExpressionEvaluator>>mul
    ^ super mul ==> [ :nodes | nodes first * nodes last ]

ExpressionEvaluator>>parens
    ^ super parens ==> [ :nodes | nodes second ]

이제 evaluator를 테스트할 준비가 되었다.

스크립트 18.26: 간단한 산술 표현식에 자신의 evaluator 테스트하기

parser := ExpressionEvaluator new.
parser parse: '1 + 2 * 3'. 	→ 7
parser parse: '(1 + 2) * 3'. 	→ 9

Pretty-Printer 정의하기

우리는 이제 간단한 pretty printer를 정의하기 위해 문법을 재사용할 수도 있다. 이는 ExpressionGrammar를 다시 서브클래싱하는 것 만큼이나 쉽다!

스크립트 18.27: 서브클래스를 생성함으로써 문법을 pretty printer로부터 분리하기

ExpressionGrammar subclass: #ExpressionPrinter
    instanceVariableNames: ''
    classVariableNames: ''
    poolDictionaries: ''
    category: 'PetitTutorial'

ExpressionPrinter>>add
    ^ super add ==> [:nodes | nodes first , ' + ' , nodes third]

ExpressionPrinter>>mul
    ^ super mul ==> [:nodes | nodes first , ' * ' , nodes third]

ExpressionPrinter>>number
    ^ super number ==> [:num | num printString]

ExpressionPrinter>>parens
    ^ super parens ==> [:node | '(' , node second , ')']

이러한 pretty printer는 아래 표현식에서와 같이 시도할 수 있다.

스크립트 18.28: 간단한 산술 표현식에 자신의 pretty printer 테스트하기

parser := ExpressionPrinter new.
parser parse: '1+2 * 3'. → '1 + 2 * 3'
parser parse: '(1+ 2 ) * 3'. → '(1 + 2) * 3'

PPExpressionParser를 이용한 손쉬운 표현식

PetitParser는 표현식을 생성하는 강력한 툴을 제시하는데, 바로 PPExpressionParser라는 것으로, 이는 전위(prefix), 후위(postfix), 좌측 연관 및 우측 연관 연산자를 이용해 표현식 문법을 편리하게 정의하는 파서이다. 연산자 그룹은 내림차순으로 정의된다.

스크립트 18.29: 앞서 정의한 ExpressionGrammar는 몇 행만으로 구현이 가능하다

| expression parens number |
expression := PPExpressionParser new.
parens := $( asParser token trim , expression , $) asParser token trim
==> [ :nodes | nodes second ].
number := #digit asParser plus flatten trim ==> [ :str | str asNumber ].

expression term: parens / number.

expression
    group: [ :g |
        g left: $ * asParser token trim do: [ :a :op :b | a * b ].
        g left: $/ asParser token trim do: [ :a :op :b | a / b ] ];
    group: [ :g |
        g left: $+ asParser token trim do: [ :a :op :b | a + b ].
        g left: $- asParser token trim do: [ :a :op :b | a - b ] ].

스크립트 18.30: 이제 파서는 뺄셈과 나눗셈도 관리할 수 있다

expression parse: '1-2/3'. → (1/3)

PPCompositeParser의 서브클래스를 생성하거나 PPExpressionParser를 인스턴스화할 때는 어떻게 결정하는가? 작은 업무용으로 작은 파서를 실행하고 싶다면 PPExpressionParser를 인스턴스화해야 한다. 반대로 다수의 파서로 구성된 문법을 갖고 있다면 PPCompositeParser를 서브클래싱해야 한다.

문법 테스트하기

PetitParser 는 당신의 문법을 테스트하기 위한 프레임워크를 포함한다. 문법의 테스트는 아래와 같이 PPCompositeParserTest의 서브클래싱을 통해 이루어진다.

스크립트 18.31: 자신의 산술 표현식 문법의 테스트를 보유하기 위한 클래스 생성하기

PPCompositeParserTest subclass: #ExpressionGrammarTest
    instanceVariableNames: ''
    classVariableNames: ''
    poolDictionaries: ''
    category: 'PetitTutorial'

이제 test case 클래스는 파서 클래스를 참조한다는 사실이 중요한데, 이는 ExpressionGrammarTest에 있는 PPCompositeParserTest>>parserClass 메서드의 오버라이드를 통해 이루어진다.

스크립트 18.32: 자신의 test case 클래스를 자신의 파서로 연결하기

ExpressionGrammarTest>>parserClass
    ^ ExpressionGrammar

테스트 시나리오의 작성은 ExpressionGrammarTest에 새 메서드를 구현함으로써 이루어진다.

스크립트 18.33: 자신의 산술 표현식 구문에 대한 테스트 구현하기

ExpressionGrammarTest>>testNumber
    self parse: '123 ' rule: #number.

ExpressionGrammarTest>>testAdd
    self parse: '123+77' rule: #add.

이러한 테스트들은 ExpressionGrammar 파서가 명시된 production 규칙을 이용해 일부 표현식을 파싱할 수 있도록 보장한다. evaluator와 pretty printer의 테스트도 마찬가지로 쉽다.

스크립트 18.34: evaluator와 pretty printer 테스트하기

ExpressionGrammarTest subclass: #ExpressionEvaluatorTest
    instanceVariableNames: ''
    classVariableNames: ''
    poolDictionaries: ''
    category: 'PetitTutorial'

ExpressionEvaluatorTest>>parserClass
    ^ ExpressionEvaluator

ExpressionEvaluatorTest>>testAdd
    super testAdd.
    self assert: result equals: 200

ExpressionEvaluatorTest>>testNumber
    super testNumber.
    self assert: result equals: 123

ExpressionGrammarTest subclass: #ExpressionPrinterTest
    instanceVariableNames: ''
    classVariableNames: ''
    poolDictionaries: ''
    category: 'PetitTutorial'

ExpressionPrinterTest>>parserClass
    ^ ExpressionPrinter

ExpressionPrinterTest>>testAdd
    super testAdd.
    self assert: result equals: '123 + 77'

ExpressionPrinterTest>>testNumber
    super testNumber.
    self assert: result equals: '123'

사례 연구: JSON 파서

이번 절에서는 JSON 파서의 개발을 통해 PetitParser를 설명하고자 한다. JSON은 http://www.json.org 에 정의된 가벼운 데이터 교환 포맷이다. 우리만의 JSON 파서를 정의하기 위해 해당 웹사이트에 실린 명세를 이용하고자 한다.

JSON은 중첩된 쌍(nested pairs)과 배열을 기반으로 한 간단한 포맷이다. 아래 스크립트는 Wikipedia http://en.wikipedia.org/wiki/JSON 에서 발췌한 예를 제시한다.

스크립트 18.35: JSON의 예제

{ "firstName" : "John",
    "lastName" : "Smith",
    "age" : 25,
    "address" :
        {   "streetAddress" : "21 2nd Street",
            "city" : "New York",
            "state" : "NY",
            "postalCode" : "10021" },
    "phoneNumber":
        [
            {   "type" : "home",
                "number" : "212 555-1234" },
            {   "type" : "fax",
                "number" : "646 555-4567" } ] }

JSON 은 객체 정의(중괄호 "{}" 사이 내용)와 배열(사각 괄호 "[]" 사이 내용)로 구성된다. 객체 정의는 키/값 쌍의 집합인 반면 배열은 값의 리스트이다. 앞의 JSON 예제는 몇 개의 키/값 쌍으로 된 (예: 사람의 이름, 성, 나이) 객체(개인)를 표현한다. 개인의 주소는 다른 객체에 의해 표현되는 반면 휴대전화 번호는 객체의 배열에 의해 표현된다.

먼저 문법을 PPCompositeParser의 서브클래스로서 정의한다. 이를 PPJsonGrammar라고 부르자.

스크립트 18.36: JSON 문법 클래스 정의하기

PPCompositeParser subclass: #PPJsonGrammar
    instanceVariableNames: ''

classVariableNames: 'CharacterTable'
poolDictionaries: ''
category: 'PetitJson-Core'

후에 문자열의 파싱에 사용할 것이기 때문에 CharacterTable 클래스 변수를 정의하도록 한다.

객체와 배열 파싱하기

JSON 객체와 배열에 대한 구문 해석도를 그림 18.6과 그림 18.7에 소개하고 있다. 아래 코드를 이용해 JSON 객체에 대한 PetitParser를 정의할 수 있겠다.

스크립트 18.37: 그림 18.6에 표현된 바와 같이 객체에 대한 JSON 파서 정의하기

PPJsonGrammar>>object
    ^ ${ asParser token trim , members optional , $} asParser token trim

PPJsonGrammar>>members
    ^ pair separatedBy: $, asParser token trim

PPJsonGrammar>>pair
    ^ stringToken , $: asParser token trim , value

여기서 새로운 내용은 PPParser>>separatedBy: 라는 편의 메서드를 호출하는 것인데, 해당 메서드는 수신자(본문에서는 값)를 한 번 또는 그 이상 파싱하는 새 파서를 응답하며 각 파싱은 그 매개변수 파서(본문에서는 콤마)에 의해 구분된다.

배열은 스크립트 18.38에 묘사된 바와 같이 파싱이 훨씬 수월하다.

스크립트 18.38: 그림 18.7에 표현된 바와 같이 배열에 대한 JSON 파서 정의하기

PPJsonGrammar>>array
    ^ $[ asParser token trim ,
        elements optional ,
    $] asParser token trim

PPJsonGrammar>>elements
    ^ value separatedBy: $, asParser token trim

값 파싱하기

JSON에서 값은 문자열, 숫자, 객체, 배열, 부울(true 또는 false), 널(null) 중에 하나에 해당한다. value 파서는 아래와 같이 정의되며 그림 18.8에 제시하였다.

스크립트 18.39: 그림 18.8에 제시된 바와 같이 값이 대한 JSON 파서 정의하기

PPJsonGrammar>>value
    ^ stringToken / numberToken / object / array /
        trueToken / falseToken / nullToken

문자열은 파싱 시 어느 정도 작업이 필요하다. 문자열은 쌍따옴표로 시작하고 끝난다. 쌍따옴표 안의 내용은 문자의 시퀀스다. 그 중 어떤 문자든 escape 문자, 8진 문자, 또는 일반 문자가 가능하다. escape 문자는 백슬래시 바로 다음에 특수 문자가 따라온다(예: '\n'은 문자열에 새 행을 얻는다). 8진 문자는 백슬래시 바로 뒤에 'u' 글자가 따라오고, 그 다음에 4개의 16진 숫자가 따라온다. 마지막으로 일반 문자는 쌍따옴표(문자열을 끝내는 데에 사용되는)와 백슬래시(escape 문자를 소개 시 사용되는)를 제외하고 어떤 문자든 가능하다.

스크립트 18.40: 그림 18.9에 제시된 바와 같이 문자열에 대한 JSON 파서 정의하기

PPJsonGrammar>>stringToken
    ^ string token trim
PPJsonGrammar>>string
    ^ $" asParser , char star , $" asParser
PPJsonGrammar>>char
    ^ charEscape / charOctal / charNormal
PPJsonGrammar>>charEscape
    ^ $\ asParser , (PPPredicateObjectParser anyOf: (String withAll: CharacterTable keys))
PPJsonGrammar>>charOctal
    ^ '\u' asParser , (#hex asParser min: 4 max: 4)
PPJsonGrammar>>charNormal
    ^ PPPredicateObjectParser anyExceptAnyOf: '\"'

슬래시 다음에 특수 문자가 허용되는데 특수 문자의 의미는 initialize 클래스 메서드에서 초기화하는 CharacterTable dictionary에 정의된다. 클래스를 시스템에 로딩하면 클래스 측에서 initialize 메서드가 호출됨을 주목하길 바란다. initialize 메서드를 방금 생성했다면 클래스는 메서드 없이 로딩된다. 이를 실행하려면 워크스페이스에 PPJsonGrammar initialize를 평가해야 한다.

스크립트 18.41: JSON 특수 문자와 그 의미 정의하기

PPJsonGrammar class>>initialize
    CharacterTable := Dictionary new.
    CharacterTable
        at: $\ put: $\;
        at: $/ put: $/;
        at: $" put: $";
        at: $b put: Character backspace;
        at: $f put: Character newPage;
        at: $n put: Character lf;
        at: $r put: Character cr;
        at: $t put: Character tab

숫자를 파싱하는 것은 약간 더 간단한데, 숫자는 음수이거나 양수에 해당하는 동시 정수이거나 십진수(decimal)기 때문이다. 뿐만 아니라 십진수는 부동 소수점 숫자(floating number) 구문을 이용해 표현 가능하다.

스크립트 18.42: 그림 18.10에 제시된 바와 같이 숫자에 대한 JSON 파서 정의하기

PPJsonGrammar>>numberToken
    ^ number token trim
PPJsonGrammar>>number
    ^ $- asParser optional ,
    ($0 asParser / #digit asParser plus) ,
    ($. asParser , #digit asParser plus) optional ,
    (($e asParser / $E asParser) , ($- asParser / $+ asParser) optional , #digit asParser
        plus) optional

주의를 기울여 읽은 독자라면 그림 18.10의 구문 해석도와 스크립트 18.42 코드에 약간의 차이점을 눈치챘을 것이다. JSON에서 숫자는 앞에 0이 올 수가 없기 때문에, 가령 "01"과 같은 문자열은 유효하지 않은 숫자를 표현한다. 구문 해석도는 0 또는 1부터 9까지 숫자를 허용함으로써 이 점을 명시적으로 표현한다. 위의 코드에서는 파서 combinator $/가 정렬된다는 사실에 의존함으로써 규칙을 암묵적으로 만들어 냈으며, $/의 우측에 있는 파서는 왼쪽의 파서가 실패할 경우에만 시도되므로, ($0 asParser / #digit asParser plus)는 0으로 시작되지 않는 숫자의 시퀀스 또는 0으로 숫자를 정의한다.

다른 파서들은 평범한 편이다.

스크립트 18.43: 누락된 JSON 파서 정의하기

PPJsonGrammar>>falseToken
    ^ 'false' asParser token trim
PPJsonGrammar>>nullToken
    ^ 'null' asParser token trim
PPJsonGrammar>>trueToken
    ^ 'true' asParser token trim

유일하게 빠진 부분은 start 파서다.

스크립트 18.44: JSON start 파서를 값(그림 18.8) 외에 어떤 것도 따라오지 않는 것으로 정의하기

PPJsonGrammar>>start
    ^ value end

PetitParser Browser

PetitParser 에는 복잡한 파서를 개발하도록 도와주는 강력한 브라우저가 구비되어 있다. PetitParser Browser는 그래픽 시각성, 디버깅 지원, 재팩토링 지원을 비롯해 본 장에서 소개할 다른 여러 기능들을 제공한다. 이러한 기능들은 자신의 파서를 개발하는 데에 있어 매우 유용함을 확인할 것이다. 시스템에 Glamour를 로딩한 채 진행하도록 한다. Glamour를 로딩하려면 10을 참고한다. 이후 아래 표현식을 평가하여 PetitParser를 열어라.

스크립트 18.45: PetitParser 브라우저 열기

PPBrowser open.

PetitParser Browser 개요

그림 18.11에서 PPBrowser 창이 보일 것이다. 좌측 패널, Parsers는 시스템 내 모든 파서의 리스트를 포함한다. ExpressionGrammar와 그 서브클래스를 비롯해 본 장의 앞에서 정의한 PPJsonGrammar도 보일 것이다. 이 패인에서 파서를 하나 선택하면 브라우저 우측 상단이 활성화된다. 선택된 파서(예: prim)의 각 규칙과 관련해, 규칙에 연관된 5개의 탭이 보일 것이다.

Source 는 규칙에 대한 소스 코드를 표시한다. 코드는 해당 창에서 업데이트 및 저장이 가능하다. 뿐만 아니라 새 메서드의 이름과 body를 정의함으로써 새 규칙을 추가할 수 있다.

Graph 는 규칙의 그래픽 표현을 표시한다. 규칙 소스가 변경되면서 이 또한 업데이트된다. prim의 시각적 표현은 그림 18.12에서 확인할 수 있다.

Example 은 규칙의 정의를 기반으로 자동으로 생성된 예제를 보여준다 (그림 18.3의 prim 규칙에 대한 예제를 참고). 우측 상단 모서리의 reload 버튼은 동일한 규칙에 대한 새로운 예제를 생성한다 (그림 18.14는 prim 규칙에 대해 자동으로 생성되는 또 다른 예제를 보여주는데, 이번에는 괄호로 된 표현식이 이용되었다).

First 는 규칙이 시작된 직후 활성화가 가능한 terminal 파서 집합을 보여준다. 그림 18.15에서 볼 수 있듯이 prim의 첫 번째 집합은 숫자(digit) 또는 여는 괄호 '('가 된다. 즉, prim의 파싱을 시작하는 즉시 입력은 숫자 또는 '('를 계속해야 함을 의미한다.

첫 번째 집합을 이용해 문법이 올바로 명시되었는지 다시 확인할 수 있다. 예를 들어, prim의 첫 번째 집합에 '+'가 보인다면 정의의 어딘가에 문제가 있다는 뜻인데, prim 규칙은 절대 이항 연산 기호로 시작되도록 만들어진 것이 아니기 때문이다.

terminal 파서는 다른 파서로 위임하지 않는 파서이다. 따라서 prim 첫 번째 집합에 parens가 보이지 않을 것인데, parens는 다른 파서-trimming 파서와 시퀀스 파서-로 위임하기 때문이다 (스크립트 18.46 참고). '('가 parens의 첫 번째 집합임을 확인할 수 있을 것이다. number 규칙도 마찬가진데, 이는 action 파서를 생성하고 해당 파서는 trimming 파서로 위임하며, 이 파서는 flattening 파서로 위임하고, 이는 다시 repeating 파서로 위임하며 이는 마지막으로 #digit 파서로 위임한다 (스크립트 18.46 참고). #digit 파서는 terminal 파서이므로 첫 번째 집합에서 '예상되는 숫자'를 확인할 수 있다. 일반적으로 첫 번째 집합의 계산은 복잡할 수 있으므로 PPBrowser는 우리를 위해 이러한 정보를 계산해준다.

스크립트 18.46: ExpressionGrammar에서 prim 규칙

ExpressionGrammar>>prim
    ^ parens / number

ExpressionGrammar>>parens
    ^ $( asParser trim, term, $} asParser trim

ExpressionGrammar>>number
    ^ #digit asParser plus flatten trim ==> [:str | str asNumber ]

Follow 는 규칙이 완료된 직후 활성화가 가능한 terminal 파서의 집합을 보여준다. 그림 18.16에서 볼 수 있듯이 잇따른 prim의 집합은 닫는 괄호 문자 파서 ')', 별표 문자 파서 '*', 플러스 문자 파서 '+' 또는 엡실론 파서(빈 문자열을 나타냄)에 해당한다. 다시 말해, prim 규칙의 파싱을 완료하고 나면, 입력은 ')', '*', '+' 문자 중 하나를 계속해야 하고, 그렇지 않으면 입력이 완전히 소모되어야 한다.

문법이 올바로 명시되었는지 확인하기 위해 추종 기호 집합(follow set)을 사용할 수도 있다. 예를 들어, prim 추종 기호 집합에서 '('가 보이면 자신의 문법 정의에 무언가 잘못된 것이다. prim 규칙 다음에는 이항 연산 기호나 닫는 괄호가 따라와야 하며 여는 기호가 뒤따라선 안 된다.

일반적으로 follow의 계산은 첫 번째 계산보다 더 복잡할 수 있으므로, PPBrowser 가 우리를 대신해 해당 정보를 계산해준다.

브라우저의 우측 하단은 특정 파싱 입력과 연관된다. Sample 탭의 텍스트 영역을 채움으로써 입력 예제를 명시할 수 있다. play ▶ 버튼을 클릭하거나 Cmd-s 또는 Ctrl-s 버튼을 눌러 입력 예제를 파싱할 수도 있다. 이후 우측 하단 패인에 있는 탭을 검사함으로써 파싱 결과에 대한 정보를 얻을 수 있다.

Result 는 Inspect 과 Explore 버튼 중 하나를 클릭하면 검사할 수 있는 입력 예제의 파싱 결과를 보여준다. 그림 18.17은 (1+2)의 파싱 결과를 표시한다.

Debugger 는 파싱 도중에 실행된 단계들의 트리 뷰를 표시한다. 이는 파싱 도중에 정확히 무슨 일이 일어나는지 알지 못할 때 매우 유용하다. 단계를 선택하면 입력의 하위집합이 강조 표시되어 특정 단계에서 파싱된 입력 부분을 확인할 수 있다.

가령, ExpressionGrammar가 작용하는 방식과 어떤 규칙이 어떤 순서로 호출되는지를 확인할 수 있는 것이다. 이것을 그림 18.18에서 설명한다. grey 규칙은 실패한 규칙이다. 이는 주로 choice 파서에 발생하는데, prod 규칙에 대한 예제를 확인할 수 있다 (그 정의가 스크립트 18.47에 제시되어 있다). 파서가 12+3*4 term을 파싱했을 당시에는 파서가 mul 규칙을 prod에서 첫 번째 옵션으로서 파싱을 시도하였다. 하지만 mul은 별표 문자 '*'를 위치 2에 필요로 했는데 해당 위치는 존재하지 않았기 때문에 mul가 실패하였고, 대신 12 값을 가진 prim이 파싱되었다.

스크립트 18.47: ExpressionGrammar 내의 prod 규칙

ExpressionGrammar>>prod
    ^ mul / prim
ExpressionGrammar>>mul
    ^ prim, $ * asParser trim, prod

12+3*4를 12*3*4로 변경할 때 파싱 도중에 어떤 일이 발생하는지 비교해보라. 어떤 규칙이 적용되고, 그 중 어떤 규칙이 실패하는가? 두 번째 디버거 출력을 그림 18.19에서 소개하고 있지만 스스로 시도해보길 바란다.

Tally 는 특정 파서가 파싱 도중에 몇 번이나 호출되었는지를 보여준다. 퍼센트는 총 호출 횟수에 대한 비율이다. 이는 자신의 파서 성능을 최적화할 때 유용할 것이다 (그림 18.20 참고).

Profile 은 입력의 파싱 도중에 특정 파서에서 소요된 시간을 표시한다. 퍼센트는 총 시간에 대한 비율이다. 이는 자신의 파서 성능을 최적화할 때 유용할 것이다 (그림 18.20 참고).

Progress 는 파서가 입력을 어떻게 소모하는지 시각적으로 표시한다. x 축은 입력 예제에서 얼마나 많은 문자가 읽혔는지 0부터 (좌측 margin) 입력의 문자 개수(우측 margin)까지 범위로 나타낸다. y 축은 시간을 나타내는데, 파싱 프로세스의 상단 한계(top margin)부터 하단 한계(bottom margin)까지 범위다. 좌측 상단부터 우측 하단까지 그어진 직선은 (그림 18.22 참고) 파서가 입력 예제의 각 문자를 한 번만 읽어서 작업을 완료하였음을 나타낸다. 이는 최고의 시나리오로, 파싱은 입력 길이를 따라 선형으로 이루어지는 경운데, 다시 말해 n 개 문자의 입력이 n 개 단계에서 파싱됨을 의미한다.

직선이 여러 개가 보이면 파서가 입력 예제에서 이전에 읽힌 문자로 돌아가 다른 규칙을 시도함을 의미한다. 그림 18.23에서 이를 확인할 수 있다. 이 예제에서 파서는 전체 입력 예제를 올바로 파싱하기 위해 여러 번 돌아가야 했는데, 모든 입력이 n에서 파싱되었기 때문이다! 문법에 대한 backward jump가 여러 개 보인다면 choice 파서의 순서를 재고려하거나, 자신의 문법을 재구성하거나, 보관된(memoized) 파서를 사용해야 한다. 추적 문제는 다음 절에서 상세히 살펴볼 것이다.

디버깅 예제

연습으로 스크립트 18.48의 BacktrackingParser를 개선해보겠다. BacktrackingParser는 정규 표현식 'a*b'와 'a*c'에 상응하는 입력을 허용하기 위해 설계되었다. 파서는 올바른 결과를 제공하지만 성능에 문제가 있다. BacktrackingParser가 추적을 너무 많이 실행하기 때문이다.

스크립트 18.48: 너무 많은 추적으로 'a * b'와 'a * c'를 수락하는 파서.

PPCompositeParser subclass: #BacktrackingParser
    instanceVariableNames: 'ab ap c p'
    classVariableNames: ''
    poolDictionaries: ''
    category: 'PetitTutorial'

BacktrackingParser>>ab
    ^ 'b' asParser /
    ('a' asParser, ab)

BacktrackingParser>>c
    ^ 'c' asParser

BacktrackingParser>>p
    ^ ab / ap / c

BacktrackingParser>>start
    ^ p

BacktrackingParser>>ap
    ^ 'a' asParser, p

무엇이 일어나는지 이해를 돕기 위해 개요를 설명하겠다. 제일 먼저 inputb = 'aaaaaaaaab' 과 inputc = 'aaaaaaaaac'. 를 파싱해보라. 그림 18.24에 나타난 경과에서 볼 수 있듯이 inputb는 다소 선형적인 시간으로 파싱되고, 추적이 전혀 없다. 하지만 그림 18.25에 설명된 경과는 상태가 좋아 보이지 않는다. 많은 추적과 함께 파싱되고 시간이 훨씬 더 많이 소요된다. inputb와 inputc 모두 tally 출력을 비교할 수도 있다 (그림 18.26과 그림 18.27 참고). inputb의 경우 파서 b의 총 호출 횟수는 19회, 파서 a의 호출 횟수는 9회다. 이는 inpubc 의 경우 파서 b의 110회 호출, 파서 a의 55회 호출에 비하면 엄청 적다.

inpubc에 문제가 있음을 확인할 수 있다. 문제가 무엇인지 아직도 모르겠다면 디버거 창이 힌트를 제공해줄 것이다. 그림 18.28과 같이 inputb에 대한 디버거 창을 살펴보자. 각 단계에서 하나의 'a'가 소모되고 파서 ab는 'b'로 도달할 때까지 호출됨을 확인할 수 있다. inpubc에 대한 디버거 창은 그림 18.29과 같이 약간 다르다. p->ab->ap->p 루프 내에서 경과가 있지만 파서 ab는 루프의 반복마다 실패한다. 파서 ab는 모든 문자열을 끝까지 읽고 'b' 대신 'c'가 보인 이후 실패하므로, 추적의 원인을 로컬화하였다. 이제 문제를 알았으니 무엇을 할 수 있을까? BacktrackingParser를 업데이트하여 'a*c' 문자열이 'a*b' 문자열과 비슷한 방식으로 파싱되도록 시도할 수 있다. 그러한 수정은 스크립트 18.49에서 확인할 수 있다.

스크립트 18.49: 'a * b'와 'a * c'를 허용하는 더 나은 파서.

PPCompositeParser subclass: #BacktrackingParser
    instanceVariableNames: 'ab ac'
    classVariableNames: ''
    poolDictionaries: ''
    category: 'PetitTutorial'

BacktrackingParser>>ab
    ^ 'b' asParser /
    ('a' asParser, ab)

BacktrackingParser>>ac
    ^ 'b' asParser /
    ('c' asParser, ab)

BacktrackingParser>>start
    ^ ab / ac

그림 18.30과 그림 18.31에서 inputc에 대한 새 측정(metrics)을 확인할 수 있다. 크게 개선된 점이 보인다. inputc의 경우 tally를 통해 파서 a가 20번만 호출되고 파서 a가 9번 호출됨을 확인할 수 있다. 이는 파서 b가 110회 호출되고 파서 a가 55회 호출되던 기존 BacktrackingParser(그림 18.27 참고)에 비하면 엄청나게 향상된 것이다.

여기서 끝날 것이 아니라 이보다 더 개선할 수도 있다. inputc에 여전히 한 번의 추적이 발생한다. 이는 파서 ab가 'a*b' 입력의 인식을 시도하고 실패(그리고 추적)하여 파서 ac가 'a*c' 입력을 인식할 수 있을 때 발생한다. 그렇다면 모든 'a'들을 소모한 후 젤 마지막에 'b'와 'c' 중에서 선택하는 경우는 어떨까? BacktrackingParser의 그러한 수정은 스크립트 18.50에서 확인할 수 있다. 이런 경우 그림 18.32에 묘사된 것처럼 inputc에 대한 추적이 없이도 경과를 확인할 수 있다.

반대로 inputb에 대한 파서 호출 횟수는 18만큼 증가했다 (Table 18.4에 BacktrackingParser의 각 버전마다 총 호출 횟수가 실려 있다). 자신의 요구에 맞는 문법을 결정하는 일은 프로그래머에게 달려 있다. 'a*b'와 'a*c'가 입력에 동일한 가능성으로 발생할 경우 두 번째로 개선된 버전을 사용하는 편이 낫다. 입력에서 더 많은 'a*b' 문자열이 예상된다면 첫 번째 버전이 낫다.

스크립트 18.50: 'a*b'와 'a*c'를 허용하는 더 나은 파서.

PPCompositeParser subclass: #BacktrackingParser
    instanceVariableNames: 'abc'
    classVariableNames: ''
    poolDictionaries: ''
    category: 'PetitTutorial'

BacktrackingParser>>abc
    ^ ('b' asParser / 'c' asParser) /
    ('a' asParser, abc)

BacktrackingParser>>start
    ^ abc

버전	inputb 호출 횟수	inputc 호출 횟수
원본	28	233
첫 번째 개선	28	70
두 번째 개선	46	48
표 18.4: BacktrackingParser의 버전에 따른 inputb와 inputc에 대한 파서 호출 횟수.

Packrat 파서

본 장을 시작할 무렵 네 가지 파서 방법을 언급한 바 있는데, 그 중에 Packrat Parsers가 있었다. packrat 파싱은 선형적 파스 시간을 제공한다고 주장하는 바이다. 하지만 디버깅 예제에서 우리는 BacktrackingParser의 원본 버전이 233개 단계에서 10 길이로 inputc를 파싱하였음을 보았다. 그리고 longinputc = 'aaaaaaaaaaaaaaaaaaaac' (길이 20)의 파싱을 시도할 경우 원본 파서는 969개 단계가 필요함을 확인할 것이다. 사실 경과는 선형적이지 않다.

PetitParser 프레임워크는 기본적으로 packrat 파싱을 사용하지 않는다. packrat 파싱을 활성화하기 위해서는 보관된 메시지를 전송할 필요가 있다. 보관된 파서는 입력과 특정 파서에서 특정 위치에 대한 파싱이 한 번만 실행되고 추후 사용을 위해 결과가 dictionary에 기억되도록 보장한다. 파서가 입력을 두 번째로 파싱하길 원하면 dictionary에서 결과가 검색될 것이다. 이런 방식을 통해 불필요한 파싱을 대다수 피할 수 있다. 단점은 PetitParser가 가능한 모든 위치에서 가능한 모든 파서의 결과를 모두 기억해야 하기 때문에 훨씬 많은 메모리를 필요로 한다는 데에 있다.

packrat 파서의 예제를 제공하기 위해 BacktrackingParser를 다시 살펴보자 (스크립트 18.48). 앞서 분석했듯이 문제는 파서 ab에 있었는데, 이것이 p -> ab -> ap -> p 루프에서 지속적으로 실패했다는 점이다. 이제 트릭을 써서 스크립트 18.51에서와 같이 메서드 ab를 업데이트하여 파서 ab를 보관할 수 있다. 보관(memoization)이 적용되면 그림 18.34에서와 같이 inputc에 대해 총 63회 호출과 longinputc에 대해 129회 호출로 된 경과를 얻을 것이다. BacktrackingParser를 약간만 수정하여 대략적으로 6을 지수(factor)로 하는 선형적 파싱 시간을 (입력의 길이와 연관) 얻었다.

스크립트 18.51: 파서 ab의 보관된 버전.

BacktrackingParser>>ab
    ^ ( 'b' asParser /
        ('a' asParser, ab)
    ) memoized

요약

PetitParser에 대한 지침을 마무리하겠다. 지금까지 아래를 살펴보았다.

파서는 combinator와 결합된 다수의 작은 파서들을 구성 요소로 한다.
문자열을 파싱하기 위해서는 parse: 메서드를 사용한다.
문자열이 문법에 매치하는지 알기 위해서는 matches: 메서드를 사용한다.
flatten 메서드는 파싱 결과로부터 String을 리턴한다.
==>메서드는 매개변수에 주어진 블록에 주어진 변형을 실행한다.
PPCompositeParser를 서브클래싱함으로써 파서를 구성(하고 문법을 생성)한다.
PPCompositeParserTest를 서브클래싱하여 자신의 파서를 테스트한다.

PetitParser와 그 개념, 구현을 광범위하게 살펴보려면 Moose book^[4]과 Lukas Renggli의 PhD^[5]에 그와 관련된 장을 참고하길 바란다.

Notes

[주석18-1-1] ttp://scg.unibe.ch/research/helvetia

[주석18-2-2] ttps://ci.inria.fr/moose/job/petitparser/

[주석18-3-3] ttp://www.themoosebook.org/book/internals/petit-parser

[주석18-4-4] ttp://www.themoosebook.org/book/internals/petit-parser

[주석18-5-5] ttp://scg.unibe.ch/archive/phd/renggli-phd.pdf

[1]

[2]

[3]

[4]

[5]

DeepintoPharo:Chapter 18

Contents

PetitParser: Modular 파서 빌드하기

PetitParser를 이용해 파서 작성하기

PetitParser 로딩하기

간단한 문법 작성하기

그래픽 표기법

일부 입력 파싱하기

그 외 파서 유형

파서 액션

조금 더 복잡한 문법 작성하기

PetitParser를 이용한 Composite 문법

문법 정의하기

의존 문법(dependent grammars) 작성하기

evaluator 정의하기

Pretty-Printer 정의하기

PPExpressionParser를 이용한 손쉬운 표현식

문법 테스트하기

사례 연구: JSON 파서

객체와 배열 파싱하기

값 파싱하기

PetitParser Browser

PetitParser Browser 개요

디버깅 예제

Packrat 파서

요약

Notes

Navigation menu

DeepintoPharo:Chapter 18

PetitParser: Modular 파서 빌드하기

PetitParser를 이용해 파서 작성하기

PetitParser 로딩하기

간단한 문법 작성하기

그래픽 표기법

일부 입력 파싱하기

그 외 파서 유형

파서 액션

조금 더 복잡한 문법 작성하기

PetitParser를 이용한 Composite 문법

문법 정의하기

의존 문법(dependent grammars) 작성하기

evaluator 정의하기

Pretty-Printer 정의하기

PPExpressionParser를 이용한 손쉬운 표현식

문법 테스트하기

사례 연구: JSON 파서

객체와 배열 파싱하기

값 파싱하기

PetitParser Browser

PetitParser Browser 개요

디버깅 예제

Packrat 파서

요약

Notes

Navigation menu

Search