일반적으로 유용한 RPython 모듈 ============================== .. contents:: 이 페이지는 :source:`rpython/rlib`\ 의 일부 모듈을 나열하며, 각 모듈을 어떤 용도로 사용할 수 있는지에 대한 힌트도 함께 제공합니다. 여기의 모듈들은 RPython 프로그램에 유용한 일반적인 라이브러리를 구성합니다(표준 라이브러리 모듈 대부분이 RPython이 아니기 때문입니다). 이 모듈들 대부분은 아직 다소 미완성 상태이며, 언젠가 변경될 가능성이 있습니다. 보통 모듈을 어떻게 사용하는지 감을 잡으려면 :source:`rpython/rlib/test`\ 의 테스트를 살펴보는 것이 유용합니다. listsort -------- timsort 정렬 알고리즘의 구현은 :source:`rpython/rlib/listsort.py` 모듈에 들어 있습니다(리스트의 sort 메서드는 RPython이 아닙니다). 이를 사용하려면 ``MySort = listsort.make_timsort_class(lt=my_comparison_func)``\ 를 호출하여 (전역적으로) 하나의 클래스를 만드십시오. 다른 선택적 인자도 있지만, 보통은 ``lt=...``\ 로 리스트에 있는 두 객체를 비교하는 함수를 전달합니다. 리스트의 "타입"과 비교 함수마다 하나의 클래스가 필요합니다. ``MySort``\ 의 생성자는 인자로 리스트를 받으며, 이 리스트는 ``MySort`` 인스턴스의 ``sort`` 메서드가 호출될 때 제자리에서 정렬됩니다. nonconst -------- 주로 테스트에서 유용하게 쓰이는 모듈이 :source:`rpython/rlib/nonconst.py`\ 입니다. 상당한 상수 폴딩(constant folding)을 수행하는 것이 :ref:`flow graph builder`\ 와 :ref:`annotator `\ 인데, 이는 테스트에서 때때로 바람직하지 않습니다. 특정 값에 대한 상수 폴딩(constant folding)을 방지하려면 ``NonConst`` 클래스를 사용하십시오. ``NonConst``\ 의 생성자는 임의의 값을 받습니다. 어노테이션 중에는 ``NonConst``\ 의 인스턴스가 그 값처럼 동작하지만, 상수 접기는 일어나지 않습니다. objectmodel ----------- 다양한 기능이 뒤섞인 잡동사니 모듈이 바로 :source:`rpython/rlib/objectmodel.py`\ 입니다. 그중에서 더 유용한 것들은 다음과 같습니다: ``ComputedIntSymbolic``: 어노테이터는 ``ComputedIntSymbolic``\ 의 인스턴스를 값을 알 수 없는 정수처럼 취급합니다. 값은 인자가 없는 함수(클래스의 생성자에 전달되어야 함)에 의해 결정됩니다. 백엔드가 코드를 생성할 때, 값을 결정하기 위해 그 함수가 호출됩니다. ``CDefinedIntSymbolic``\ : ``CDefinedIntSymbolic``\ 의 인스턴스도 애노테이터(annotator)에 의해 값을 알 수 없는 정수처럼 취급됩니다. C 코드가 생성될 때 이들은 심볼릭(symbolic)의 속성 ``expr``\ 로 표현되며, 이는 생성자의 첫 번째 인자이기도 합니다. ``r_dict``: RPython의 dict와 유사한 객체입니다. r_dict의 생성자는 딕셔너리의 항목을 비교하고 해싱하는 데 사용되는 두 함수 ``key_eq``\ 와 ``key_hash``\ 를 받습니다. ``instantiate(cls)``: ``__init__``\ 을 호출하지 않고 클래스 ``cls``\ 를 인스턴스화합니다. ``we_are_translated()``: 이 함수는 CPython 위에서 실행될 때 ``False``\ 를 반환하지만, 애너테이터(annotator)는 그 반환값을 ``True``\ 로 여깁니다. 따라서 이는 번역(translation) 이후와는 다르게 CPython 위에서 다른 동작을 하도록 사용할 수 있습니다. 이는 매우 드물게 사용해야 합니다(주로 최적화나 디버그 코드에서). ``cast_object_to_weakaddress(obj)``: obj에 대한 일종의 "약한 참조(weak reference)"를 반환하지만, 어떠한 편의성도 제공하지 않습니다. 반환되는 약한 주소는 객체가 소멸되어도 무효화되지 않으므로, 객체가 언제 소멸되는지는 직접 파악해야 합니다. 극히 주의해서 사용하십시오. ``cast_weakadress_to_object(obj)``\ : 이전 함수의 역함수입니다. 객체가 소멸했다면 세그폴트가 발생합니다. ``UnboxedValue``: 이것은 정확히 하나의 정수 필드를 가지는 클래스의 기반 클래스로 사용해야 하는 클래스입니다. 이 클래스는 정확히 하나의 항목이 정의된 ``__slots__``\ 을 가져야 합니다. 번역(translation) 이후에는 이 클래스의 인스턴스가 할당되지 않고, 최하위 비트가 설정된 포인터, 즉 *태그된 포인터**\ 로 표현됩니다. rarithmetic ----------- 일반 Python 코드와 RPython 코드에서 산술 코드의 동작에 나타나는 작은 차이를 처리하는 기능은 :source:`rpython/rlib/rarithmetic.py` 모듈에 들어 있습니다. 그중 대부분은 이미 :doc:`RPython description `\ 에서 설명되어 있습니다. rbigint ------- 모듈 :source:`rpython/rlib/rbigint.py`\ 는 Python ``long`` 타입(RPython 자체에서는 지원되지 않음)의 완전한 RPython 구현을 담고 있습니다. ``rbigint`` 클래스가 그 구현을 담고 있습니다. ``rbigint`` 인스턴스를 생성하려면 정적 메서드 ``fromint``, ``frombool``, ``fromfloat``, ``fromdecimalstr``\ 를 사용하십시오. 다른 타입으로 다시 변환하려면 메서드 ``toint``, ``tobool``, ``touint``, ``tofloat``\ 를 사용하십시오. RPython은 연산자 오버로딩을 지원하지 않으므로, 일반적으로 앞뒤에 "__"가 붙는 ``rbigint``\ 의 모든 특수 메서드는 가독성을 높이기 위해 이 밑줄이 생략되어 있습니다(따라서 두 rbigint 인스턴스를 더할 때 ``a.add(b)``\ 를 사용할 수 있습니다). rrandom ------- 메르센 트위스터(mersenne twister) 난수 생성기의 구현은 :source:`rpython/rlib/rrandom.py` 모듈에 포함되어 있습니다. 이 모듈은 ``Random``\ 이라는 하나의 클래스를 포함하고 있으며, 이 클래스에는 무엇보다도 0.0과 1.0 사이의 의사 난수 부동소수점 수를 반환하는 ``random`` 메서드가 있습니다. rsocket ------- 소켓 표준 라이브러리의 기능을 약간 다른 인터페이스로 구현한 RPython 코드가 :source:`rpython/rlib/rsocket.py` 모듈에 들어 있습니다. Python 소켓 API의 어려움은 주소가 "타입이 명확한(well-typed)" 객체가 아니라는 점입니다: 주소 체계(address family)에 따라 튜플이거나 문자열이거나 그 밖의 형태일 수 있는데, 이는 RPython에 적합하지 않습니다. 대신 ``rsocket``\ 은 전형적인 정적 객체지향 프로그래밍 스타일로 Address 클래스들의 계층 구조를 담고 있습니다. rstrategies ----------- RPython VM들에서 저장소 전략(storage strategy)을 구현하기 위한 라이브러리는 :source:`rpython/rlib/rstrategies` 모듈에 들어 있습니다. 이 라이브러리는 언어 독립적이며 확장 가능합니다. 더 자세한 내용과 예제는 :doc:`rstrategies documentation `\ 에서 확인할 수 있습니다. streamio -------- RPython 스트림 I/O 구현은 :source:`rpython/rlib/streamio.py`\ 에 들어 있으며, 이는 Guido van Rossum이 Python 3000에서 예정된 새로운 파일 구현의 프로토타입으로서 CPython 샌드박스에 `sio.py`_\ 로 작성을 시작한 것입니다. .. _sio.py: http://svn.python.org/view/sandbox/trunk/sio/sio.py 언롤(unroll) ------------ 무엇보다도, :source:`rpython/rlib/unroll.py` 모듈은 반복자(iterator)를 감싸는 함수 ``unrolling_iterable``\ 을 포함합니다. RPython 코드에서 반복자에 대해 루프를 도는 것은 결과로 만들어지는 흐름 그래프(flow graph)에 루프를 만들어내지 않고, 대신 그 루프를 펼칩니다. rsre ---- PyPy에서 사용하는 정규 표현식의 구현입니다. 다른 언어에서 재사용하기 어렵다는 점에 유의하십시오: Python에서 정규 표현식은 먼저 표준 라이브러리의 순수 Python 코드에 의해 바이트코드 형식으로 컴파일됩니다. 이 저수준 모듈은 이 바이트코드 형식만 이해합니다. 완전한 Python 인터프리터 없이는 정규식 구문을 바이트코드 형식으로 변환할 수 없습니다. (정적 정규식만 있는 제한된 사용 사례를 위한 편법이 있습니다: 이런 경우 번역(translation) 중에 미리 컴파일할 수 있습니다. 또는 런타임에 정규식을 변환하기 위해서만 Python 하위 프로세스를 실행하는 방법을 상상해 볼 수도 있습니다...) 파싱 ---- RPython에서 토크나이저와 파서를 생성하기 위한 :source:`rpython/rlib/parsing/` 모듈은 아직 개발 중인 모듈입니다. 이 모듈은 여전히 매우 실험적이며, 약간 비표준적인 방식이기는 하지만 실제로는 `Prolog interpreter`_\ 에서만 사용되고 있습니다. 토크나이저/문법을 지정하는 가장 쉬운 방법은 정규 표현식과 간단한 EBNF 형식을 사용하여 작성하는 것입니다. 정규 표현식은 유한 오토마톤을 사용하여 구현됩니다. 파싱 엔진은 `packrat parsing`_\ 을 사용하는데, 이는 O(n) 파싱 시간을 가지면서도 LL(n) 및 LR(n) 문법보다 더 강력합니다. .. _packrat parsing: http://pdos.csail.mit.edu/~baford/packrat/ 정규 표현식 ----------- 정규 표현식 문법은 대부분 `re`_ 모듈 문법의 부분집합입니다. *참고: 이는 rlib.rsre와 다릅니다.* 기본적으로 특수 문자가 아닌 문자는 자기 자신과 일치합니다. 정규 표현식을 연결하면, 그 결과는 각각의 정규 표현식이 일치시키는 문자열들의 연결과 일치합니다. ``|`` ``R|S``\ 는 R과 매치되거나 S와 매치되는 *어느* 문자열이든 매치합니다. ``*`` ``R*``\ 는 R의 0회 이상 반복과 일치합니다. ``+`` ``R+``\ 는 R의 1회 이상 반복과 일치합니다. ``?`` ``R?``\ 는 R의 0회 또는 1회 반복과 일치합니다. ``(...)`` 괄호는 정규 표현식을 그룹화하는 데 사용할 수 있습니다(단, Python의 re 모듈과 달리 이 그룹의 내용을 나중에 다시 매칭할 수는 없다는 점에 유의하십시오). ``{m}`` ``R{m}``\ 은 R을 정확히 m번 반복한 것과 일치합니다. ``{m, n}`` ``R{m, n}``\ 은 R이 m회에서 n회까지(m과 n을 포함) 반복되는 것과 일치합니다. ``[]`` 문자 집합과 일치합니다. 일치시킬 문자들을 순서대로 나열할 수 있습니다. ``-``\ 를 사용하여 문자 범위를 지정할 수 있습니다. 예를 들어 ``[ac-eg]``\ 는 문자 a, c, d, e, g와 일치합니다. ``^``\ 로 시작하면 전체 집합을 반전시킬 수 있습니다. 따라서 [^a]는 a를 제외한 모든 문자와 일치합니다. 정규 표현식을 파싱하고 이에 대한 매처를 얻으려면, ``rpython.rlib.parsing.regexparse`` 모듈의 ``make_runner(s)`` 함수를 사용할 수 있습니다. 이 함수는 ``input``\ 이 문자열과 일치하는지 여부에 따라 True 또는 False를 반환하는 ``recognize(input)`` 메서드를 가진 객체를 반환합니다. .. _re: http://docs.python.org/library/re.html EBNF ---- 토크나이저와 문법을 기술하기 위해 ``rpython.rlib.parsing.ebnfparse``\ 는 이를 위한 구문을 정의합니다. 문법 파일은 규칙들의 시퀀스를 포함합니다. 각 규칙은 정규 표현식 또는 문법 규칙을 기술합니다. 정규 표현식 규칙은 다음과 같은 형식을 가집니다:: NAME: "regex"; NAME은 정규 표현식이 생성하는 토큰의 이름이며(대문자로만 이루어져야 합니다), ``regex``\ 는 위에서 설명한 구문을 따르는 정규 표현식입니다. 토큰 이름 중 하나는 특별하게 처리됩니다: ``IGNORE``\ 라는 토큰은 파서로 전달되기 전에 토큰 스트림에서 걸러지므로, 주석이나 의미 없는 공백을 매칭하는 데 사용할 수 있습니다. 문법 규칙은 다음과 같은 형태를 가집니다:: name: expansion_1 | expansion_2 | ... | expansion_n; 여기서 ``expansion_i``\ 는 비단말(nonterminal) 또는 토큰 이름의 시퀀스입니다:: symbol_1 symbol_2 symbol_3 ... symbol_n 이는 소문자로 이루어져야 하는 비단말 기호 ``name``\ 가 확장 중 어느 하나로 확장될 수 있음을 의미합니다. 확장은 토큰 이름, 비단말 이름 또는 리터럴(따옴표로 둘러싸인, 글자 그대로 일치하는 문자열)의 시퀀스로 구성될 수 있습니다. 이를 더 명확하게 하는 예시:: IGNORE: " "; DECIMAL: "0|[1-9][0-9]*"; additive: multitive "+" additive | multitive; multitive: primary "*" multitive | primary; primary: "(" additive ")" | DECIMAL; 이 문법은 덧셈과 곱셈을 포함하는 산술 표현식의 구문을 설명합니다. 토크나이저는 DECIMAL 토큰이나 리터럴 "+", "*", "(", ")" 중 하나와 일치하는 토큰의 스트림을 생성합니다. 공백은 모두 무시됩니다. 이 문법은 연산자의 우선순위를 따르는 구문 트리를 생성합니다. 예를 들어 ``12 + 4 * 5`` 표현식은 다음과 같은 트리로 파싱됩니다: .. graphviz:: digraph G{ "-1213931828" [label="additive"]; "-1213931828" -> "-1213951956"; "-1213951956" [label="multitive"]; "-1213951956" -> "-1213949172"; "-1213949172" [label="primary"]; "-1213949172" -> "-1213949812"; "-1213949812" [shape=box,label="DECIMAL\l'12'"]; "-1213931828" -> "-1213935220"; "-1213935220" [shape=box,label="__0_+\l'+'"]; "-1213931828" -> "-1213951316"; "-1213951316" [label="additive"]; "-1213951316" -> "-1213948180"; "-1213948180" [label="multitive"]; "-1213948180" -> "-1213951380"; "-1213951380" [label="primary"]; "-1213951380" -> "-1213951508"; "-1213951508" [shape=box,label="DECIMAL\l'4'"]; "-1213948180" -> "-1213948788"; "-1213948788" [shape=box,label="__1_*\l'*'"]; "-1213948180" -> "-1213951060"; "-1213951060" [label="multitive"]; "-1213951060" -> "-1213948980"; "-1213948980" [label="primary"]; "-1213948980" -> "-1213950420"; "-1213950420" [shape=box,label="DECIMAL\l'5'"]; } 파스 트리 --------- 파싱 과정은 ``Symbol``\ 과 ``Nonterminal``\ 의 인스턴스로 구성된 트리를 구축하며, 전자는 토큰에 해당하고 후자는 비단말 기호에 해당합니다. 두 클래스는 모두 :source:`rpython/rlib/parsing/tree.py` 모듈에 있습니다. 파스 트리(parse tree)의 pygame 뷰를 얻기 위해 ``Nonterminal`` 인스턴스의 ``view()`` 메서드를 사용할 수 있습니다. ``Symbol`` 인스턴스는 다음 속성을 가집니다: 토큰의 이름인 ``symbol``\ 과, 일치한 소스인 ``additional_info``\ 입니다. ``Nonterminal`` 인스턴스는 다음과 같은 속성을 가집니다: ``symbol``\ 은 비단말(nonterminal)의 이름이고, ``children``\ 은 자식 속성들의 목록입니다. 방문자(Visitors) ~~~~~~~~~~~~~~~~ RPython으로 작성된 파스 트리를 위한 트리 방문자(visitor)를 작성하려면, :source:`rpython/rlib/parsing/tree.py`\ 에 사용할 수 있는 특수 베이스클래스 ``RPythonVisitor``\ 가 있습니다. 클래스가 이를 사용하면, ``node`` 인자에 따라 적절한 ``visit_`` 메서드를 호출하는 ``dispatch(node)`` 메서드가 생겨납니다. 여기서 은 방문된 노드의 ``symbol`` 속성으로 대체됩니다. 방문자(visitor)가 RPython이 되려면, 모든 visit 메서드의 반환값이 같은 타입이어야 합니다. 트리 변환 --------- 위의 산술 예제 트리에서 보듯이, 기본적으로 파스 트리에는 실제로 유용한 정보를 전달하지 않는 노드가 많이 포함되어 있습니다. 이 중 일부를 제거하기 위해, 문법 형식에는 추가 노드를 제거하도록 트리를 변환하는 방문자(visitor)를 자동으로 생성하는 지원 기능이 있습니다. 이러한 변환 중 가장 단순한 것은 그냥 노드를 제거하는 것이지만, 더 복잡한 것들도 있습니다. 이러한 변형(transformation)의 구문은 비단말(nonterminal) 확장 내의 기호를 [...], <...> 또는 >...<로 둘러싸는 것입니다. [symbol_1 symbol_2 ... symbol_n] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 이렇게 하면 트리에서 둘러싸인 기호를 완전히 제거하는 트랜스포머가 생성됩니다. 예제:: IGNORE: " "; n: "A" [","] n | "A"; 문자열 "A, A, A"를 파싱하면 다음과 같은 트리를 얻습니다: .. graphviz:: digraph G{ "-1213678004" [label="n"]; "-1213678004" -> "-1213681108"; "-1213681108" [shape=box,label="__0_A\n'A'"]; "-1213678004" -> "-1213681332"; "-1213681332" [shape=box,label="__1_,\n','"]; "-1213678004" -> "-1213837780"; "-1213837780" [label="n"]; "-1213837780" -> "-1213837716"; "-1213837716" [shape=box,label="__0_A\n'A'"]; "-1213837780" -> "-1213839476"; "-1213839476" [shape=box,label="__1_,\n','"]; "-1213837780" -> "-1213839956"; "-1213839956" [label="n"]; "-1213839956" -> "-1213840948"; "-1213840948" [shape=box,label="__0_A\n'A'"]; } 변환 후 트리에서는 "," 노드가 제거됩니다: .. graphviz:: digraph G{ "-1219325716" [label="n"]; "-1219325716" -> "-1219325844"; "-1219325844" [shape=box,label="__0_A\n'A'"]; "-1219325716" -> "-1219324372"; "-1219324372" [label="n"]; "-1219324372" -> "-1219325524"; "-1219325524" [shape=box,label="__0_A\n'A'"]; "-1219324372" -> "-1219324308"; "-1219324308" [label="n"]; "-1219324308" -> "-1219325492"; "-1219325492" [shape=box,label="__0_A\n'A'"]; } ~~~~~~~~ 이는 부모를 기호로 치환합니다. 당연히 부모는 한 번만 치환될 수 있으므로, 모든 확장(expansion)은 <...>로 둘러싸인 기호를 최대 하나만 포함할 수 있습니다. 예시:: IGNORE: " "; n: "a" "b" "c" m; m: "(" ")" | "d"; 문자열 "a b c (a b c d)"를 파싱하면 다음과 같은 트리가 나옵니다: .. graphviz:: digraph G{ "-1214029460" [label="n"]; "-1214029460" -> "-1214026452"; "-1214026452" [shape=box,label="__0_a\n'a'"]; "-1214029460" -> "-1214028276"; "-1214028276" [shape=box,label="__1_b\n'b'"]; "-1214029460" -> "-1214027316"; "-1214027316" [shape=box,label="__2_c\n'c'"]; "-1214029460" -> "-1214026868"; "-1214026868" [label="m"]; "-1214026868" -> "-1214140436"; "-1214140436" [shape=box,label="__3_(\n'('"]; "-1214026868" -> "-1214143508"; "-1214143508" [label="n"]; "-1214143508" -> "-1214141364"; "-1214141364" [shape=box,label="__0_a\n'a'"]; "-1214143508" -> "-1214141748"; "-1214141748" [shape=box,label="__1_b\n'b'"]; "-1214143508" -> "-1214140756"; "-1214140756" [shape=box,label="__2_c\n'c'"]; "-1214143508" -> "-1214144468"; "-1214144468" [label="m"]; "-1214144468" -> "-1214414868"; "-1214414868" [shape=box,label="__5_d\n'd'"]; "-1214026868" -> "-1214141492"; "-1214141492" [shape=box,label="__4_)\n')'"]; } 변환 후 트리는 다음과 같은 모습입니다: .. graphviz:: digraph G{ "-1219949908" [label="n"]; "-1219949908" -> "-1214026452"; "-1214026452" [shape=box,label="__0_a\n'a'"]; "-1219949908" -> "-1214028276"; "-1214028276" [shape=box,label="__1_b\n'b'"]; "-1219949908" -> "-1214027316"; "-1214027316" [shape=box,label="__2_c\n'c'"]; "-1219949908" -> "-1219949876"; "-1219949876" [label="n"]; "-1219949876" -> "-1214141364"; "-1214141364" [shape=box,label="__0_a\n'a'"]; "-1219949876" -> "-1214141748"; "-1214141748" [shape=box,label="__1_b\n'b'"]; "-1219949876" -> "-1214140756"; "-1214140756" [shape=box,label="__2_c\n'c'"]; "-1219949876" -> "-1219949748"; "-1219949748" [label="m"]; "-1219949748" -> "-1214414868"; "-1214414868" [shape=box,label="__5_d\n'd'"]; } >nonterminal_1 nonterminal_2 ... nonterminal_n< ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 이는 nonterminal_1부터 nonterminal_n까지의 노드를 해당 자식 노드로 대체합니다. 예제:: IGNORE: " "; DECIMAL: "0|[1-9][0-9]*"; list: DECIMAL >list< | DECIMAL; 문자열 "1 2"를 파싱하면 다음과 같은 트리가 나옵니다: .. graphviz:: digraph G{ "-1213518708" [label="list"]; "-1213518708" -> "-1213518196"; "-1213518196" [shape=box,label="DECIMAL\n'1'"]; "-1213518708" -> "-1213518260"; "-1213518260" [label="list"]; "-1213518260" -> "-1213520308"; "-1213520308" [shape=box,label="DECIMAL\n'2'"]; } 변환 후 트리는 다음과 같은 모습입니다: .. graphviz:: digraph G{ "-1219505652" [label="list"]; "-1219505652" -> "-1213518196"; "-1213518196" [shape=box,label="DECIMAL\n'1'"]; "-1219505652" -> "-1213520308"; "-1213520308" [shape=box,label="DECIMAL\n'2'"]; } 이 변환\ 은 재귀적으로 동작한다는 점에 유의하십시오. 이는 다음도 동작한다는 것을 의미합니다: 문자열 "1 2 3 4 5"가 파싱되면 트리는 처음에 다음과 같은 모습입니다: .. graphviz:: digraph G{ "-1213611892" [label="list"]; "-1213611892" -> "-1213608980"; "-1213608980" [shape=box,label="DECIMAL\n'1'"]; "-1213611892" -> "-1213623476"; "-1213623476" [label="list"]; "-1213623476" -> "-1213623380"; "-1213623380" [shape=box,label="DECIMAL\n'2'"]; "-1213623476" -> "-1213442868"; "-1213442868" [label="list"]; "-1213442868" -> "-1213441652"; "-1213441652" [shape=box,label="DECIMAL\n'3'"]; "-1213442868" -> "-1213441332"; "-1213441332" [label="list"]; "-1213441332" -> "-1213441620"; "-1213441620" [shape=box,label="DECIMAL\n'4'"]; "-1213441332" -> "-1213443060"; "-1213443060" [label="list"]; "-1213443060" -> "-1213442100"; "-1213442100" [shape=box,label="DECIMAL\n'5'"]; } 하지만 변환 후에는 전체 구조가 자식이 많은 하나의 노드로 축소됩니다: .. graphviz:: digraph G{ "-1219430228" [label="list"]; "-1219430228" -> "-1213608980"; "-1213608980" [shape=box,label="DECIMAL\n'1'"]; "-1219430228" -> "-1213623380"; "-1213623380" [shape=box,label="DECIMAL\n'2'"]; "-1219430228" -> "-1213441652"; "-1213441652" [shape=box,label="DECIMAL\n'3'"]; "-1219430228" -> "-1213441620"; "-1213441620" [shape=box,label="DECIMAL\n'4'"]; "-1219430228" -> "-1213442100"; "-1213442100" [shape=box,label="DECIMAL\n'5'"]; } EBNF 문법 형식의 확장 --------------------- EBNF 문법 형식에는 실제로는 문법 설탕(syntactic sugar)에 불과하지만 문법을 작성하는 수고를 덜어주는 몇 가지 확장이 있습니다. 이는 다음과 같습니다: ``symbol?``: symbol의 0회 또는 1회 반복과 일치합니다 ``symbol*``: symbol의 0회 이상 반복과 일치합니다. 트리 변환 후, 이러한 모든 반복은 현재 symbol의 자식이 됩니다. ``symbol+``: symbol의 1회 이상 반복과 일치합니다. 트리 변환 후에는 이러한 반복이 모두 현재 symbol의 자식이 됩니다. 이러한 것들은 문법에 올바른 방식으로 규칙을 몇 가지 더 추가하여 구현됩니다. 예시: 문법:: s: a b? c; 다음과 같은 모습으로 변환됩니다:: s: a >_maybe_symbol_0_< c | a c; _maybe_symbol_0_: b; 문법:: s: a b* c; 다음과 같은 모습으로 변환됩니다:: s: a >_star_symbol_0< c | a c; _star_symbol_0: b >_symbol_star_0< | b; 문법:: s: a b+ c; 다음과 같은 형태로 변환됩니다:: s: a >_plus_symbol_0< c; _plus_symbol_0: b >_plus_symbol_0< | b; 전체 예제 --------- `json format`_\ 을 위한 반쯤 완성된 파서:: STRING: "\\"[^\\\\"]*\\""; NUMBER: "\-?(0|[1-9][0-9]*)(\.[0-9]+)?([eE][\+\-]?[0-9]+)?"; IGNORE: " |\n"; value: | | | | <"null"> | <"true"> | <"false">; object: ["{"] (entry [","])* entry ["}"]; array: ["["] (value [","])* value ["]"]; entry: STRING [":"] value; 문자열을 파싱한 결과 트리는:: {"a": "5", "b": [1, null, 3, true, {"f": "g", "h": 6}]} 다음과 같습니다: .. graphviz:: digraph G{ "-1220061652" [label="object"]; "-1220061652" -> "-1220127636"; "-1220127636" [label="entry"]; "-1220127636" -> "-1213915636"; "-1213915636" [shape=box,label="STRING\n'a'"]; "-1220127636" -> "-1214251156"; "-1214251156" [shape=box,label="STRING\n'5'"]; "-1220061652" -> "-1220063188"; "-1220063188" [label="entry"]; "-1220063188" -> "-1214253076"; "-1214253076" [shape=box,label="STRING\n'b'"]; "-1220063188" -> "-1220059444"; "-1220059444" [label="array"]; "-1220059444" -> "-1214253364"; "-1214253364" [shape=box,label="NUMBER\n'1'"]; "-1220059444" -> "-1214254292"; "-1214254292" [shape=box,label="__0_null\n'null'"]; "-1220059444" -> "-1214253268"; "-1214253268" [shape=box,label="NUMBER\n'3'"]; "-1220059444" -> "-1214252596"; "-1214252596" [shape=box,label="__1_true\n'true'"]; "-1220059444" -> "-1220062260"; "-1220062260" [label="object"]; "-1220062260" -> "-1220060116"; "-1220060116" [label="entry"]; "-1220060116" -> "-1214211860"; "-1214211860" [shape=box,label="STRING\n'f'"]; "-1220060116" -> "-1214210132"; "-1214210132" [shape=box,label="STRING\n'g'"]; "-1220062260" -> "-1220062868"; "-1220062868" [label="entry"]; "-1220062868" -> "-1214211956"; "-1214211956" [shape=box,label="STRING\n'h'"]; "-1220062868" -> "-1214212308"; "-1214212308" [shape=box,label="NUMBER\n'6'"]; } .. _Prolog interpreter: https://bitbucket.org/cfbolz/pyrolog/ .. _json format: http://www.json.org