Boost 라이브러리에서 파서 제너레이터인 스피릿(Sprit)에 대한 매뉴얼을 번역한 것입니다. * 원본 : [http://spirit.sourceforge.net/distrib/spirit_1_8_3/libs/spirit/index.html] * 라이센스 : [http://www.boost.org/LICENSE_1_0.txt] * 번역 : [김상균] ---- [[TableOfContents]] == 소개 == 스피릿은 object-oriented recursive-descent parser generator framework으로 template meta-programming 기술을 이용해서 구현되었다. Expression template을 통해서 C++에서 EBNF(Extended Backus-Normal Form) 문법을 나타낼 수 있었다. 스피릿은 C++로 원하는 그래마를 쓸수 있다. C++ 템플리트의 표현력에 의해서 Inline EBNF 그래마는 자유롭게 C++ 코드와 섞어서 쓸 수 있으며 즉시 수행된다. 반면 일반적인 파서 생성기는 EBNF 코드를 C++이나 C 코드로 변환하는 추가 작업이 있었다. 간단한 EBNF 예제:{{{ group ::= '(' expression ')' factor ::= integer | group term ::= factor (('*' factor) | ('/' factor))* expression ::= term (('+' term) | ('-' term))* }}} 위의 것을 스피릿에서 표현한 것:{{{ group = '(' >> expression >> ')'; factor = integer | group; term = factor >> *(('*' >> factor) | ('/' >> factor)); expression = term >> *(('+' >> term) | ('-' >> term)); }}} Expression template의 능력으로 인해서 위의 코드는 C++에서 컴파된다. 프로덕션 룰 ''expression''은 우리가 선언한 그래마를 파싱하는 멤버 함수를 갖는 객체이다. ''expression'은 계산기이다. 간단히 하기 위해서 ''factor''에 있는 ''integer''에 대한 룰은 생략했다. 우리가 정의한 그래마의 프로덕션 룰 ''expression''은 (보통 start symbol로 불린다.) 아래와 같은 입력을 인식할 수 있다. {{{ 12345 -12345 +12345 1 + 2 1 * 2 1/2 + 3/4 1 + 2 + 3 + 4 1 * 2 * 3 * 4 (1 + 2) * (3 + 4) (-1 + 2) * (3 + -4) 1 + ((6 * 200) - 20) / 6 (1 + (2 + (3 + (4 + 5)))) }}} 우리는 원래의 EBNF에서 몇가지에 대해서 변경을 했다. 이것은 C++문법에 맞추기 위해서이다. 가장 주목할 것은 shift 연산자(>>)이다. C++에는 'empty' 연산자가 없기 때문에 다음과 같이 쓰는 것이 불가능하다. {{{ a b }}} 이것은 수학에서 곱셈?표시하는 것과 같은 방식인데 EBNF에서는 순서를 나타낸다.(b가 반드시 a뒤에 있어야 한다.) 스피릿에서는 같은 목적을 위해서 shift 연산자 '>>'를 사용한다. 'is followed by'를 나타내기 위해서 오른쪽으로 가는 shift 연산자 '>>'를 선택했다. 그래서 이렇게 된다. {{{ a >> b }}} 선택 연산자인 '|'과 괄호인 '(' ')'는 그대로 사용한다. 대입 연산자 '='가 EBNF의 ':='를 대체한다. 그리고 별표 연산자 '*'는 EBNF에서 postfix연산자이나 스피릿에서는 C++에서 '*'연산자가 prefix인 관계로 prefix로 사용한다. 즉 {{{ a* //... in EBNF syntax, }}} 가 {{{ *a //... in Spirit. }}} 이 된다. 마지막으로 각각의 룰마다 세미콜론 ';'을 사용해서 끝낸다. == Quick Start == === 왜 Spirit를 사용해야 하나? === 스피릿은 실용적인 파싱 툴로서 설계되었다. EBNF형식을 완벽하게 파싱하는 능력을 C++코드 내에서 작성할 수 있도록 하여 개발 시간을 단축시킨다. C나 Pascal과 같은 새로운 랭귀지를 개발하고자 한다면, YACC나 ANTLR과 같은 큰 stand-alone 파서를 사용하는것도 실용적이다. 하지만 아주 작은 파서를 만들고자 한다면 YACC나 ANTLR을 사용하는 것은 너무 무겁다. 프로그래머가 해야할 파싱 작업의 스펙트럼중 한쪽 끝은 scanf를 사용해서 직관적으로 수행하는 것이다. 정규식 처리를 위한 라이브러리(예 : boost의 regex)나 스캐너(예 : boost의 tokenizer)가 존재하지만, 정교한 파서를 만드는데는 부족하다. 이런 툴을 사용해서 복잡한 파서를 만들면 이해하거나 관리하기 힘든 코드를 작성할 수 밖에 없다. === 예제 1 === 부동소수점 숫자를 파싱하기 위한 파서를 생성하자 {{{ real_p }}} 위의 코드는 스피릿의 ''real_parser''(built-in parser)라는 부동소수점 파서를 이용해서 만들어졌다. 파서의 끝이 ''_p''라는 스피릿 컨벤션(convention)에 따른다는데 주의하자. 스피릿은 많은 pre-defined 파서가 존재하고 일정한 네이밍 컨벤션에 의해서 당신이 사용하는데 편하게 되어있다. === 예제 2 === 부동소수점 숫자 2개를 받아들이는 파서를 생성하자 {{{ real_p >> real_p }}} 친숙한 부동소수점 파서인 ''real_p''가 2번 사용된 것을 볼 수 있다. 여기서 '>>'' 연산자가 무슨 역할을 하는 것일까? 숫자들은 뭔가에 의해서 분리되어 있어야 하는데, 그것이 연속 연산자로 선택되었다. 위의 프로그램은 2개의 단순한 파서부터 하나의 하나의 파서를 생성하는데, 2개의 파서를 붙이는 역할은 연속 연산자가 한다. 결과는 2개의 작은 파서를 결합한 하나의 파서이다. 숫자 사이에 있는 공백은 어떻게 파서가 불리느냐에 따라서 자동적으로 제거된다.(아래를 보라) 주의: 파서를 결합할때 반드시 더큰 파서로 끝난다. 파서는 결합을 시킴에 따라 점점더 커진다. 그렇지만 언제나 두개의 파서를 결합하면 하나의 큰 파서로 끝난다. 이것은 중요한 개념이다. === 예제 3 === 임의의 개수의 부동소수점 숫자를 받아들이는 파서를 생성하자. {{{ *real_p }}} 이것은 '*'를 사용한 정규식 표현과 비슷하지만 C++ 프로그래머가 '*' 연산자를 오버로드 했다고 해도 약간은 이상하다. 이상하게 보이는 것은 '*'가 영향을 주는 ''real_p'의 앞쪽에 위치해 있기 때문이다. 이건 C++ 문법에 맞게 동작하게 하려고 했기 때문이다. 파서를 만들어 내는 표현의 대부분은 '*'를 사용할 것이다. C++의 연산자 우선순위에 따라서 괄호안에 '*'를 넣어야 할지도 모른다. '*'는 Kleene Start, Keene Closure 등으로 알려져 있지만 앞으로는 그냥 별(star)이라고 한다. === 예제 4 === 이 예제에서 쉼표로 분리된 숫자 리스트를 vector에 넣는 파서를 만들 것이다. ==== Step 1. 파서의 생성 ==== {{{ real_p >> *(ch_p(',') >> real_p) }}} ''ch_p(',')''에 주목하라. 이건 쉽표 ','를 인식하기 위한 literal character 파서이다. 여기서는 별이 더 복잡한 아래의 식에 의해서 만들어지는 파서에 영향을 준다. {{{ (ch_p(',') >> real_p) }}} 이번 것에는 괄호가 필요하다는데 주의하라. ==== Step 2. 파서의 사용 ==== 이제 파서가 만들어 졌는데 이것을 어떻게 사용할까? C++ 임시 객체와 마찬가지로 변수에 대입할 수도 있고 직접 콜할 수도 있다. C++의 세부사항은 대충 넘어가겠다. ''r''을 룰이라고 한다면 다음과 같이 파서를 하나의 룰로 정의할 수 있다. (룰이 정확히 무었인지에 대해서 걱정하지마라. 이건 다음에 다시 논의하겠다. 간단히 얘기해서 룰은 하나의 파서를 가진 변수이다.) {{{ r = real_p >> *(ch_p(',') >> real_p); }}} 시시하게도 당신이 수년 동안 해왔던 C++의 대입 구문(expression)과 비슷하다. 파서를 룰에 저장하는 것에 관한 멋진 점은 룰은 파서이며 ''이름''(여기서는 ''r'')로 참조될 수 있다는 것이다. 이것이 전체 대입 구문이라는데 주목하자.(그래서 ';'로 끝났다.) 그렇다. 우리는 파서를 정의하는 것을 완료했다. 다음 과정은 파서를 우리가 원하는 일을 하도록 호출하는 것이다. 여기에는 몇가지 방법이 있다. 여기서는 ''const char *''를 받는 ''parse''함수를 사용할 것이다. 이 함수의 인자는 다음과 같다. * NULL terminated ''const char *'' (input) * 파서 객체 * ''skip parser''라고 불리는 다른 파서 이 예제에서 space와 tab는 스킵하려고 한다. ''space_p''라는 스피릿에서 predefined된 파서를 다른 파서 즉 ''skip parser''로 사용된다. 이 파서는 공백문자를 인식하는 매우 단순한 파서이다. Skip parser는 real_p와 ch_p라는 파서 사이에서 스킵해야할 문자들을 책임진다. 그럼 파싱해보자. {{{ r = real_p >> *(ch_p(',') >> real_p); parse(str, r, space_p) // Not a full statement yet, patience... }}} parse함수는 ''parse_info''라 불리는 하나의 객체를 리턴한다. 이 예제에서 우리는 다음과 같은것을 알고자 한다. * 파서가 str을 성공적으로 인식했는가? * 파서가 완전히 파싱해서 str의 끝까지 다 소모했는가? 위의 것을 모두 나타내기위해서 하나의 함수로 만들겠다. {{{ bool parse_numbers(char const* str) { return parse(str, real_p >> *(',' >> real_p), space_p).full; } }}} 여기서는 룰을 이름으로 선언하지 않고 inline을 통해서 바로 사용했다. parse_number함수가 콜될때, 구문이 계산되고, unnammed 파서가 만들어져서 parse함수로 전달된다. 함수안에서 사용된 파서는 사용이 끝난후 소멸된다. {{{ '''char과 w_char''' 주의깊은 독자는 앞의 예제와는 다르게 ','이 ch_p(',') 대신에 사용된 것을 알았을 것이다. 이것은 C++ 문법에 의해서 허용된다. >> 연산자들 중에 char이나 w_char을 왼쪽이나 오른쪽중 한곳에 받아들이도록 overload한 것이 존재한다.(양쪽 모두는 안된다.) 하나이상의 인자가 사용자 정의 type일 경우 연산자 overloading이 일어난다. 이 경우에는 real_p가 >>연산자의 2번째 인자이고 연산자 >>가 사용되었으므로 ','가 ch_p(',')로 변환된다. ch_p를 콜하는 것을 생략하는데서 문제가 생길 수 있다. 'a' >> 'b' 의 경우인데, 이 경우는 스피릿 파서가 생성되지 않는다. 이 경우는 단순한 숫자 계산 식이며 a의 ASCII값을 b의 ASCII값 만큼 오른쪽으로 shift한다. 하지만 ch_p('a') >> 'b'나 'a' >> ch_p('b')는 스피릿 파서이다. }}} ''parse''함수의 리턴 객체에서 ''full''이라는 멤버를 불렀다. full은 위의 두 요건을 모두 만족 시킬때 true가 된다. (즉 파서는 완전히 입력된 스트링을 인식했다.) ==== Step 3. Semantic Actions ==== 위에서 만든 우리의 파서는 단순히 인식만 한다. 단순히 "입력이 우리의 그래마에 일치하는가?"에 대한 대답만 할 뿐, 어떤 데이터를 기억하지 못하고 사이드 이펙트도 없다. 우리는 읽어들인 자료를 vector에 넣고자 한다는 것을 명심하자. 이것은 특정 파서에 연결된 ''action''에 의해서 이루어진다. 예를 들어서, 우리가 자연수를 파싱할 때마다 파싱된 숫자를 저장하고 싶다고 하자. 우리는 파서로부터 정보를 얻어오고 싶다. Semantic action이 그런 일을 한다. Semantic action은 그래마의 어디에라도 붙을 수 있다. 이런 action은 C++ 함수이거나 함수객체(functor: function object)이며, 파서가 일정분량의 입력을 정확히 인식할 때 마다 불린다. 파서 '''P''', C++ 함수 '''F'''가 있을 때, 파서가 입력이 인식할 때마다 '''F'''를 콜하도록 '''F'''를 다음과 같이 붙일 수 있다. {{{ P[&F] }}} F가 함수객체라면 다음과 같이 한다. {{{ P[F] }}} 함수/함수객체의 형태는 붙여진 파서에 의해서 결정된다. ''real_p''의 경우 단지 하나의 인자 즉 파싱된 숫자 만들 전달한다. 결국 우리가 real_p에 '''F'''를 붙이고자 한다면 우리는 '''F'''를 다음과 같이 정의해야 한다. {{{ void F(double n); }}} 우리의 예제에서 미리 정의된 함수객체와 함수객체 생성기(functor generator)를 사용할 것이다. 스피릿은 ''push_back_a(c)''라는 함수객체 생성기를 가지고 있다. 간단히 말해서 이 함수는 콜되었을 때 container c에 파싱된 값을 추가하게된다. 완성된 파서 코드이다. {{{ bool parse_numbers(char const* str, vector& v) { return parse(str, // Begin grammar ( real_p[push_back_a(v)] >> *(',' >> real_p[push_back_a(v)]) ) , // End grammar space_p).full; } }}} 위에서 설명한 파서와 같은 파서를 사용한다. 여기서는 semantic action을 붙여서 숫자가 파싱될 때마다 그것을 vector v에 저장하도록 했다. parse_numbers함수는 성공했을 때 true를 리턴한다. 전체 소스코드는 [http://spirit.sourceforge.net/distrib/spirit_1_8_3/libs/spirit/example/fundamental/number_list.cpp 여기서] 볼수 있다. == 기본 개념 == 잘 이해해야 할 네 가지 개념이 있다. 1) 파서(Parser), 2) 매치(Match), 3) 스캐너, 4) Semantic Action 이런 기본 개념은 다른 것과 연관되어 있고, 각각의 기능은 프레임워크 전체에 하나의 일관성을 가지고 섞여있다. http://spirit.sourceforge.net/distrib/spirit_1_8_3/libs/spirit/doc/theme/intro1.png === 파서 === 프레임워크의 중심은 파서이다. 파서는 스캐너에 의해서 처음부터 끝까지 순차적으로 읽어진 선형적인 입력 스트림을 인식하는 작업을 수행한다. 파서는 잘 정의된 사양 즉 그래마 룰에 입력을 매치 시키려고 시도한다. 성공하게 되면 파서는 정의된 semantic action을 수행한다. 그리고 semantic action은 파서에서 넘어온 데이터와 연결된 파서의 계층 컨텍스트(context)에 따라서 구조화된 정보를 뽑아낸다. 스피릿 프레임워크는 간단한 것부터 복잡한 것까지 다양한 것을 파싱할 수 있는 pre-define된 파서들의 집합으로 구성된다. 개념으로서 파서는 공개된 개념적인 인터페이스 약정을 갖는다. 약정에 따라서 누구라도 프레임워크의 pre-define 구성요소와 같이 잘 동작할 수 있는 파서를 작성할 수 있다. 파서의 개념적 인터페이스의 상세한 정의는 나중에 설하겠다. 프레임워크의 사용자들은 일반적으로 그들이 파서를 직접 코딩할 필요가 없다. 스피릿은 대부분의 문법과 의미 분석을 할 수 있는 pre-define 파서들을 대규모로 가지고 있다. 다음 장에서 이런 파서들을 검토할 것이다. 정의된 기능이 없는 매우 드문 경우라 해도 새롭게 사용자가 파서를 작성하는 것도 아주 쉽다. 파서를 작성하는 것이 쉬운 것은 스피릿의 확장가능한 구조(extensibility)에 기인한다. === 기본(Primitive) 파서와 조합(Composite) 파서 === 스피릿 파서들은 두 가지 카테고리인 기본파서와 조합파서로 나눌 수 있다. 이런 두 가지 카테고리들은 파싱 용어에서 terminal과 non-terminal과 비슷하다. 기본파서는 더 이상 분해할 수 없는 단위이다. 반면에 조합파서는 기본파서나 다른 파서들이 합쳐진 파서이다. 다음 스피릿 구문을 살펴보자. {{{ real_p >> *(',' >> real_p) }}} real_p는 자연수를 파싱할 수 있는 기본파서이다. 구문 안에 있는 ','는 ch_p(',')과 같은 것으로 하나의 캐릭터를 인식할 수 있는 기본 파서이다. 위의 구문은 다음과 같은 파스트리와 대응된다. http://spirit.sourceforge.net/distrib/spirit_1_8_3/libs/spirit/doc/theme/intro7.png 아래의 구문을 보자. {{{ ',' >> real_p }}} 이 구문은 새로운 연속 파서(sequence parser)를 구성한다. 위의 ''sequence'' 파서는 왼쪽 편(lhs: left hand side)의 ''ch_p(',')''와 오른쪽 편(rhs: right hand side)의 ''real_p''라는 두 개의 파서를 포함하는 조합 파서이다. 이 조합 파서가 불리면, 순서대로 lhs를 콜하고 rhs를 콜한다. 그리고 두 가지 콜 모두 성공해야만 성공된 매치라는 것을 보고한다. http://spirit.sourceforge.net/distrib/spirit_1_8_3/libs/spirit/doc/theme/intro2.png 연속 파서는 바이너리 조합파서로서 2개의 파서로 조합된다. 단일 조합(unary composite) 또한 존재한다. 단일 조합은 하나의 주제를 유지한다. 바이너리 조합과 같이 단일 조합도 포함된 주제에 따라서 행동이 바뀐다. 하나의 예가 바로 별(Kleen star)이다. 파서에 의해서 별이 불리면 별에 포함된 주제를 0회이상 부른다. 0회 이상이라는 것 때문에 별은 항상 성공적인 매치를 리턴하며 NULL 스트링도 매치할 수 있다. 다음 구문을 살펴보자. {{{ *(',' >> real_p) }}} 위 구문은 연속 파??''kleene_star''로 감싼 것이다. http://spirit.sourceforge.net/distrib/spirit_1_8_3/libs/spirit/doc/theme/intro3.png 전체 구문은 ''real_p'' 기본 파서와 ''sequence'' 파서를 감싼 ''kleene_star'' 파서로 구성된다. http://spirit.sourceforge.net/distrib/spirit_1_8_3/libs/spirit/doc/theme/intro4.png 계층적으로 조합되고 구조화된 몇 개의 간단한 클래스 들이 매우 강력한 객체지향적 리커시브-디센던트 파서 엔진을 만들어 낸다. 이런 클래스들은 더 복잡한 파서를 만드는데 필요한 인프라를 제공한다. 최종적인 파서 조합은 무한 look-ahead를 갖는 non-deterministic recursive-descent parser이다. Top-down descent는 계층을 순방한다. 외각의 ''sequence''는 제일 왼쪽은 ''real_p'' 파서를 콜한다. 만약 성공하면 ''kleene_star''이 다음으로 콜된다. ''kleene_star''는 안쪽의 ''sequence''를 매치에 실패하거나 입력이 다 소모될 때까지 반복적으로 콜한다. 내부에서는 ''ch_p(',')''와 ''real_p''가 순서대로 콜된다. 파스칼 문법 다이어그램을 연상시키는 아래의 다이어그램은 어떤 일이 일어나는지를 나타낸다. http://spirit.sourceforge.net/distrib/spirit_1_8_3/libs/spirit/doc/theme/intro5.png 객체 포함과 리커전으로 연결된 조합의 유연함은 파싱에 대한 단일 접근법을 제시한다. 서브클래스들은 연관을 형성하는 것과 복잡한 알고리즘들로부터 자유롭다. 복잡한 파서는 몇 개의 기본 파서 클래스들로부터 조합되어 생성될 수 있다. 프레임워크는 확장할 수 있는 구조로 설계되었다. 새로운 기본 파서나 조합 파서가, 단순한 것부터 복잡한 것까지 언제나 추가될 수 있다. 조합되는 것은 컴파일 타임에 정적으로 일어난다. 이것은 C++ expression template와 template 메타 프로그래밍의 유연성 때문에 가능하다. 결과는 기본 파서와 작은 조합들이 조합된 조합 파서이다. 이런 포함 전략은 완벽한 EBNF구문을 모델링 할 수 있는 계층 구조를 만들 수 있는 능력을 준다. 나중에 더 많은 기본 파서와 조합 파서 제작용 블록들을 보여주겠다. === 스캐너 === 파서와 같이 스캐너는 추상적은 개념이다. 스캐너의 작업은 파서에게 제공되는 순차적인 입력 스트림을 제공하는 것이다. 스캐너는 first와 last라는 2개의 STL forward iterator로 구성된다. 여기서 first는 레퍼런스이고 last를 값이다. First iterator는 파서에 의해서 위치를 변화시킬 수 있는 레퍼런스를 가지고 있다. 정책의 집합에 의해서 스캐너의 행동이 통제된다. 파서는 스캐너로부터 데이터를 추출해와서 스캐너의 맴버함수에 의해서 iterator를 위치시킨다. 스캐너 정책들의 복잡함은 대부분의 경우 몰라도 된다. 하지만 스캐너의 기본 API에 대한 지식은 완전한 스피릿 파서를 작성하는데 필요하다. 스캐너 API는 다른 섹션에서 개략적으로 보여줄 것이다. 추가적으로 파워 유저를 위해서 스캐너 정책을 설명할 것이다. 스캐너 정책은 스피릿을 매우 유연하고 확장 가능한 구조로 만든다. 예를 들어 어떤 정책들은 데이터를 필터링 할 수 있다. 실제로 사용되는 스캐너 정책의 예는 대소문자 구별 없는 입력을 위해서 대소문자를 구별하지 않도록 하는 것이다. 다른 스캐너 정책 예는 입력으로부터 공백을 제거하는 것이다. === 매치 === 파서는 스캐너로부터 얻어오는 멤버 함수와 매치되는 객체를 리턴하는 멤버함수를 갖는다. 매치 객체를 위한 기본 함수는 파싱의 성공을 파서의 콜러에게 보고하기 위한 것이다. 즉 파싱 함수가 성공하면 true를, 그렇지 않으면 false를 계산해낸다. 만약 파싱이 성공하면 매치 객체로부터 매치되는 캐릭터의 길이를 알아낼 수 있다. (match.length()를 사용한다.) 길이는 매치가 성공한다면 음이 아닌 값을 갖는고 실패할 경우는 일반적으로 -1을 갖는다. 길이가 0일 경우도 정확한 입력이며 성공적인 매치를 표현한다. 파서는 대응되는 속성 데이터를 갖는다. 예를 들어 real_p 파서는 대응되는 숫자 데이터를 갖는다. 이 속성은 파싱된 숫자이다. 속성은 리턴된 매치 객체로 전달된다. 매치 객체로부터 속성을 얻어올 수 있다. 이 데이터는 매치가 성공했을 때만 유요하다. === Semantic Action === 조합 파서는 계층을 형성한다. 파싱은 가장 위쪽의 부모 파서로부터 시작한다. 그 파서는 파싱 임무를 자신의 자식 파서에게 위임하고 배분한다. 이런 과정을 기본 파서에 도달할 때까지 리커시브하게 반복한다. Semantic action을 이런 계층의 다양한 위치에 붙이는 것을 통해 단조로운 입력을 구조화된 표현으로 변환할 수 있다. 이것이 파서가 하는 일의 핵심이다. 위에서 사용한 예를 다시 한번 살펴보자. {{{ real_p >> *(',' >> real_p) }}} ''real_p'' 파서를 위한 함수(또는 함수객체)를 걸어놓는 것을 통해서 우리는 입력으로부터 숫자를 뽑아올 수 있다. {{{ real_p[&f] >> *(',' >> real_p[&f]) }}} http://spirit.sourceforge.net/distrib/spirit_1_8_3/libs/spirit/doc/theme/intro6.png 여기서 ''f''는 하나의 인자를 갖는 함수이다. {{{[&f]}}}는 ''real_p''가 유효한 숫자를 인식했을 때 ''f''가 콜되게 한다. 어떤 작업을 수행할 지는 함수에 달려 있다. 예를 들어서 백터에 들어갈 숫자가 될 수 있다. 만약 그래마에서 ','을 '+'로 변경해서 우리는 합계를 계산하는 단순 계산기로 정의한다면, 함수 ''f''는 입력된 숫자를 더하는 기능으로 만들어야 한다. == 구조 == 프레임워크는 잘 모듈화 되어있고 레이어들로 구성되어 있다. ||iterator||actor|| ||debug|| ||attribute||dynamic||error_handling||symbols||tree||utility|| ||meta|| ||||||||core|| ||scanner||primitives||composite||non_terminal|| 스피릿은 4개의 레이어에 독립적인 최상위 레이어가 추가된 형태를 갖는다. '''actor'''과 '''iterator'''을 갖는 독립 레이어는 다른 계층에 종속되지 않는다. 프레임워크의 구조는 완전히 orthogoanl하다. 레이어간의 관계는 순환종속이 없다. 하위 레이어들은 상위 레이어에 종속되지 않는다. 같은 레이어에 있는 모듈들도 서로서로에 종속되지 않는다. 사용자는 컴파일 타임이나 런타임 부하를 초래하지 않고 원하는 모듈들을 사용할 수 있다. 최소한의 경우는 '''core'''만 사용하는 것이다. '''core'''는 매우 유용하다. '''core'''는 매우 작은 규모의 파싱 작업에 이용하기 적합하다. '''iterator''' 모듈은 스피릿과는 독립적이며 스피릿이 아닌 어플리캐이션에도 사용할 수 있다. 이 모듈은 standalone iterator 들과 스피릿과 호환을 위한 iterator wrapper로 구성되어 있다. 이 iterator들은 스피릿의 파싱 과정에서 유용하게 사용되는 것을 알 수 있다. '''actor''' 모듈 역시 스피릿과는 독립적인 모듈로서 일반적인 semantic 작업 처리를 위해서 사용하는 predefined semantic action들로 이루어져 있다. '''debug''' 모듈은 파서 디버깅을 위한 라이브러리이다. 이 모듈은 필요할 경우 '''core'''에 투명하게 관여한다. '''attribute''' 모듈은 발전된 semantic action을 제공한다. 이 모듈은 파서 계층 구조 사이에서 상속되거나 조합된 속성들을 위 아래로 전달하고 추출하는 것을 도와준다. 속성은 파싱을 제어하는데도 사용될 수 있다. Parametric 파서는 수행 중 속성이나 데이터 값에 따라서 자신의 행동을 변경하는 다이나믹 파서의 형태를 갖는다. '''dynamic''' 모듈은 런타임에 행동이 변경될 수 있는 파서에 사용된다. '''error_handling'''. 프레임워크는 에러 핸들링 없이는 완전하지 않다. C++의 예외 핸들링 구조는 스피릿의 높은 수준의 리커시브 함수에 적합하다. C++ Exception이 이 모듈에서 확장되어서 에러 처리를 위해서 사용된다. '''symbol''' 모듈은 심볼 테이블의 관리를 위해서 사용된다. 이 모듈은 지금은 아주 기초적인 수준이다. 목표는 C++ 형태의 다중 스코프 방식을 수용할 수 있는 서브 프레임워크(sub-framework)를 만드는 것이다. C++은 스코프에서는 어떤 다른 랭귀지에서도 필적할 수 없는 복잡도를 갖는 훌륭한 모델이다. 클래스들과 상속, private, protected, public와 같은 접근 제한, friend, namespace, declaration의 사용, directive의 사용 등이 C++ 스코프에 해당한다. 현재 심볼 테이블의 기능은 C++ 스코프를 모델링하기 위한 완전한 기능의 기초부분이 될 것이다. 파스 트리와 AST(Abstract Syntax Tree)를 만드는 것은 '''tree''' 모듈에 의해서 처리된다. 파스 트리나 AST는 semantic action에 비해서 다음과 같은 장점들이 있다. 입력을 다시 파싱하지 않고도 여러 번의 데이터 전달을 할 수 있다. 트리에서 변환을 시도할 수도 있다. 속성을 통해서는 처음부터 끝으로 처리해야 하지만, 트리를 이용하면 원하는 순서대로 어떤 값을 계산할 수 있다. 애매모호한 그래마에서 나타날 수 있는 백트래킹이나 사이드 이펙트에 대해서 신경쓸 필요가 없다. '''utility''' 모듈은 일반적으로 유용한 파서들과 리스트 작업이나 주석, confix expression등의 작업의 처리에 유용한 지원 클래스들의 모음이다. '''meta''' 모듈은 고급 스피릿 프로그래머를 위한 메타프로그래밍 기능을 제공한다. 이 모듈은 스피릿 파서의 컴파일타임이나 런타임 자가 점검을 용의하게 한다. == Core == === Primitives === 프레임워크는 predefine된 기본 파서들을 갖고 있다. 이것들은 사용자가 복잡한 파서를 만들기 위해서 사용되는 가장 기초적인 제작 단위이다. 기본 파서들은 매우 유연하게 만들어진 템플리트 클래스들이다. 기본 파서들은 직접이나 헬퍼 함수들을 통해서 인스탄스화 된다. 일반적으로 헬퍼 함수들이 사용하기 더 쉽다. 지금까지는 ''ch_p''를 문자 파싱 함수로 알아왔으나 사실 파서 생성 함수이다. 클래스 ''chlit''가 문자 파싱 함수의 뒤쪽에 있는 실제 템플릿 클래스이다. ''chilt''객체를 인스턴스화 하려면 템플리트 인자로서 캐릭터의 타입을 결정하기 위한 ''CharT''를 제공해 줘야 한다. 보통 이 타입은 입력의 타입과 대응되며, 일반적으로 ''char''이나 ''wchar_t''가 사용된다. 다음의 구문은 하나의 글자 'X'를 인식하는 임시 파서 객체를 만든다. {{{ chlit('X'); }}} ''chilt''의 생성 함수인 ''ch_p''를 사용하는 것은 ''chilt<>'' 클래스의 사용을 단순화한다. (이 내용은 대부분의 파서 클래스에도 적용된다. 그 이유는 대부분의 스피릿 파서 클래스들이 대응되는 생성 함수를 가지고 있기 때문이다.) 컴파일러가 인자 추론을 통해서 템플리트 타입을 추론하기 때문에 함수를 콜하는 것이 편리하다. 위의 예제를 ''ch_p'' 헬퍼 함수를 통해서 표현할 수 있다. {{{ ch_p('X') // equivalent to chlit('X') object }}} {{{ 파서 생성기 파서 생성 함수를 콜하는 것은 파서 자체를 사용하는 것과 동일하다. 왜냐하면 ch_p 문자 파서를 콜 할 때 마다 파서를 생성하기 때문이다. }}} 다음의 인용된 그래마는 이런 것이 어떻게 동작하는지를 보여준다. {{{ // a rule can "store" a parser object. They're covered // later, but for now just consider a rule as an opaque type rule<> r1, r2, r3; chlit x('X'); // declare a parser named x r1 = chlit('X'); // explicit declaration r2 = x; // using x r3 = ch_p('X') // using the generator }}} ==== chlit와 ch_p ==== 하나의 문자를 매치한다. ''chilt''는 하나의 타입 인자를 갖는 템플리트로 기본 인자로서 ''char''를 갖는다. (즉 ''chilt<>''는 ''chilt''와 동일하다.) 이 타입 인자는 파싱할 때 인식할 인자의 타입이다. 생성 함수에서는 함수의 인자를 통해서 템플리트의 타입 인자를 추론한다. ''chilt'' 클래스 생성자는 하나의 인자를 받는다. 생성자 인자는 입력에 매치될 문자이다. 예: {{{ r1 = chlit<>('X'); r2 = chlit(L'X'); r3 = ch_p('X'); }}} 원래의 예로 돌아가 보자. {{{ group = '(' >> expr >> ')'; expr1 = integer | group; expr2 = expr1 >> *(('*' >> expr1) | ('/' >> expr1)); expr = expr2 >> *(('+' >> expr2) | ('-' >> expr2)); }}} 여기서 그래마 안의 문자 '(', ')', '+', '-', '*', '/'는 implicit하게 ''chilt'' 객체를 선언한다. {{{ char 오퍼랜드(operand) 위의 예제는 (char, ParserT)나 (ParserT, char)를 받는 >> 연산자의 오버로드를 만든다. 이 함수들은 char를 chilt객체로 바꾼다. }}} 다음과 같이 명확하게 선언해서 사용할 수도 있다. {{{ chlit<> plus('+'); chlit<> minus('-'); chlit<> times('*'); chlit<> divide('/'); chlit<> oppar('('); chlit<> clpar(')'); }}} ==== range와 range_p ==== 문자의 ''range''는 낮고 높은 문자의 쌍으로부터 생성된다. ''range''파서는 양끝을 포함한 범위에 있는 하나의 캐릭터만을 매치한다. ''chilt''와 마찬가지로 ''char''를 기본 값으로 하는 하나의 템플리트 타입 인자를 갖는다. ''range''클래스의 생성자는 2개의 인자를 갖는다. 2개의 인자는 시작과 끝의 문자 범위를 나타내며 나중에 입력에 매치가 된다. 생성 함수는 ''range_p''이다. 예: {{{ range<>('A','Z') // matches 'A'..'Z' range_p('a','z') // matches 'a'..'z' }}} 내부 문자 인코딩에서 첫번째 문자는 두번째 문자보다 작은 것이어야 한다는데 주의하자. ''range''는 ''chilt''와 마찬가지로 single character 파서이다. {{{ 문자 매핑 문자 매핑은 플랫폼에 종속적이다. 예에서 사용한 'A' < 'Z'가 보장되는 것은 아니다. 하지만 대부분의 경우 ASCII, ISO-8859-1, Unicode등을 사용한다. 다른 플랫폼에서 사용할 때는 주의하자. }}} ==== strlit와 str_p ==== 이 파서는 하나의 스트링을 매치한다. ''strlit''는 iterator 타입의 템플리트 타입 인자 한 개를 갖는다. 내부적으로 ''strlit''는 스트링을 가리키는 begin/end iterator 쌍을 유지한다. ''strlit''는 현재 입력 스트림과 이 문자열과의 매치를 시도한다. 기본 템플리트 타입 인자는 ''char const *''이다. ''strlt''는 2가지 생성자를 갖는다. 첫번째는 null-terminated character pointer이다. 이 생성자는 ''strlit''를 ""로 만들어진 문자열에서 만들 때 사용한다. 두번째 생성자는 first/last iterator 쌍을 받는다. 생성 함수는 ''str_p''이다. 예: {{{ strlit<>("Hello World") str_p("Hello World") std::string msg("Hello World"); strlit(msg.begin(), msg.end()); }}} {{{ 문자 단위와 구문 단위 파싱 일반적인 파서는 문자(하나의 단어를 이루는 기호)와 문장(문장을 이루는 단어들)의 처리를 별도의 영역으로 취급한다. 예약어나 연산자, 스트링, 숫자 상수 등과 같은 그래마의 terminal로 사용되는 요소들은 보통 lexical analysis 단계에서 먼저 추출되는 것이 일반적이다. 우리가 지금까지 살펴본 예에서 알 수 있듯이, 일반적인 파서와는 다르게 스피릿 프레임워크는 문자 단위나 구문 단위나 같이 처리한다. 스피릿 프레임워크에서는 lexical analyzer가 완벽하게 통합되어 있다. 스피릿 파서 라이브러리에서는 분리된 lexical analyzer가 불필요하지만, 반드시 사용하지 않을 필요는 없다. 필요에 따라서는 여러 개의 파싱 단계를 사용할 수 있다. Preprocessor, lexical analyzer, 파서를 생성하고 같은 프레임워크에서 모두를 사용할 수 있다. }}} ==== chseq와 chseq_p ==== 문자를 순서대로 받아들인다. ''chseq''는 ''strlit''와 같은 템플리트 타입 인자를 사용한다. 생성 함수는 ''chseq_p''이다. 예: {{{ chseq<>("ABCDEFG") chseq_p("ABCDEFG") }}} ''strlit''는 문자 단위로 동작한다. 반면에 ''chseq''는 문자 단위와 구문 단위의 양쪽 모두로 동작한다. 단순히 얘기하면 스트링에 존재하는 공백을 무시할 수 있다는 것이다. 예: {{{ chseq<>("ABCDEFG") }}} 이것은 아래의 문자열들을 파싱할 수 있다. {{{ ABCDEFG A B C D E F G AB CD EFG }}} ==== 기타 문자 파서들 ==== 스피릿에서는 모든 single character 파서들을 정의하고 있다. ||||Single character 파서들|| ||anychar_p|| Matches any single character (including the null terminator: '\0') || ||alnum_p|| Matches alpha-numeric characters || ||alpha_p|| Matches alphabetic characters || ||blank_p|| Matches spaces or tabs || ||cntrl_p|| Matches control characters || ||digit_p|| Matches numeric digits || ||graph_p|| Matches non-space printing characters || ||lower_p|| Matches lower case letters || ||print_p|| Matches printable characters || ||punct_p|| Matches punctuation symbols || ||space_p|| Matches spaces, tabs, returns, and newlines || ||upper_p|| Matches upper case letters || ||xdigit_p|| Matches hexadecimal digits || ==== negation ~ ==== ''chlit'', ''range'', ''anychar_p'', ''alnum_p''들과 같은 single character 파서는 부정(negate)될 수 있다. 예: {{{ ~ch_p('x') }}} 위의 예는 'x'를 제외한 모든 캐릭터를 매치한다. 파서의 이중 부정은 취소된다. ~~alpha_p는 alpha_p와 같다. ==== eol_p ==== 라인의 마지막과 매치된다. (CR/LF와 매치된다.) ==== nothing_p ==== 아무것과도 매치되지 않는다. 항상 실패한다. ==== end_p ==== 입력의 끝과 매치된다. (입력이 모두 소진되었을 때 성공적으로 매치된다.) === Operators === 연산자는 객체의 조합과 포함의 수단으로 사용된다. 단순한 파서는 오퍼레이터 오버로딩을 통해서 조합 파서를 만들기 위해서 조합된다. 이것은 EBNF(Extended Backus-Normal Form) 문법을 만들어 내기 위해서 사용된다. 다음과 같은 구문을 보면 {{{ a | b }}} a와 b라는 것을 조합하는 새로운 파서 타입을 만들어 낸다. 이 예제를 더 살펴보면, a와 b가 chilt<>타입이라고 한다면, 결과는 다음과 같은 조합 타입이 된다. {{{ alternative, chlit<> > }}} 일반적으로 어떤 바이너리 연산자든 parser1과 parser2라는 두 개의 인자를 받아서 새로운 조합 파서를 만든다. {{{ op }}} 여기서 parser1과 parser2는 어떤 복합 파서라도 가능하다. (이 가능성은 컴파일러의 한계에만 제약된다.) ==== 집합 연산자 ==== ||||Set operators || ||a | b ||Union Match a or b. Also referred to as alternative || ||a & b ||Intersection Match a and b || ||a - b ||Difference Match a but not b. If both match and b's matched text is shorter than a's matched text, a successful match is made || ||a ^ b ||XOR Match a or b, but not both || ===== 단절(short-circuiting) ===== 선택은 왼쪽에 있는 인자부터 순서대로 하나씩 시도한다. 성공적으로 매치되는 것이 발견되면 파서는 결과를 결정짓지만 다른 결과가 존재할 가능성은 단절된다. 이런 단절은 가장 왼쪽에 있는 것에 가장 높은 운선순위가 있다. 단절은 C나 C++의 로직 연산과 비슷하다. 즉 만약 {{{if(x<3 || y<2)}}}에서 만약 x가 3보다 작다고 계산되었다면 {{{y<2}}}는 테스트가 되지 않는다. 이런 단절은 수행시간을 향상시킨다. 선택의 순서는 논리적으로 관계없기 때문에 최대의 효율을 위해서 가장 일반적인 선택을 앞에 놓도록 해야 한다. ==== 연속 연산자들(Sequencing Operators) ==== ||||Sequencing operators || ||a >> b ||Sequence Match a and b in sequence || ||a && b ||Sequential-and Sequential-and. Same as above, match a and b in sequence || ||a | | b ||Sequential-or Match a or b in sequence || 연속 연산자 >>는 연속-and 연산자로 간주할 수 있다. a && b 는 ‘match a and b in sequence’로 읽는다. 계속해서 연속-or 는 ‘match a or b in sequence’로 읽는다. 이것은 만약 a와 b가 모두 매치된다면 순서대로 있어야 한다는 것으로 {{{a >> !b | b}}} 와 동일하다. ==== 옵션과 루프(Optional and Loops) ==== ||||||Optional and Loops || ||*a ||Kleene star ||Match a zero (0) or more times || ||+a ||Positive ||Match a one (1) or more times || ||!a ||Optional ||Match a zero (0) or one (1) time || ||a % b ||List ||Match a list of one or more repetitions of a separated by occurrences of b. This is the same as a >> *(b >> a). Note that a must not also match b || 자세히 살펴보면 옵션 연산자인 !a가 루프와 같은 카테고리에 있는 것에 주의하게 된다. 이것은 옵션이 매치하는 것을 고려할 때 그것이 0번이나 1번 반복된다는 것을 의미하기 때문이다. ---- CategoryManual