PEP 617 – CPython을 위한 새로운 PEG 파서

Author:: Guido van Rossum <guido at python.org>, Pablo Galindo Salgado <pablogsal at python.org>, Lysandros Nikolaou <lisandrosnik at gmail.com>
Discussions-To:: Python-Dev list
Status:: Final
Type:: Standards Track
Created:: 24-Mar-2020
Python-Version:: 3.9
Post-History:: 02-Apr-2020

Table of Contents

번역·라이선스 안내

이 비공식 한국어 번역은 원문 Copyright 절의 Public Domain 조건에 따라 제공합니다. 원저자와 공식 원문은 그대로 표시합니다. 수정되지 않은 기준 원문 · 공식 최신판

Important

This PEP is a historical document. The up-to-date, canonical documentation can now be found at Full Grammar specification.

See PEP 1 for how to propose changes.

개요

이 PEP는 CPython의 현재 LL(1) 기반 파서를 새로운 PEG 기반 파서로 교체할 것을 제안합니다. 새로운 파서를 도입하면 LL(1) 제약을 우회하려고 현재 문법에 넣어 둔 여러 “꼼수(hack)”를 없앨 수 있습니다. 또한 문법, 파서, AST 생성처럼 컴파일 파이프라인과 관련된 일부 영역의 유지 보수 비용을 크게 줄일 수 있습니다. 새로운 PEG 파서는 현재 Python 문법에 걸려 있는 LL(1) 제약도 없앨 것입니다.

LL(1) 파서에 대한 배경

현재 Python 문법은 LL(1) 기반 문법입니다. LL(1) 파서로 파싱할 수 있는 문법을 LL(1) 문법이라고 할 수 있습니다. 여기서 LL(1) 파서는 입력을 왼쪽에서 오른쪽으로 읽으며 문장의 최좌단 유도(leftmost derivation)를 수행하고, 토큰을 단 하나만 미리 보는(lookahead) 하향식(top-down) 파서로 정의됩니다. LL(1) 파서를 구성하거나 생성하는 전통적인 방법은 파서가 가질 수 있는 모든 상태 사이의 가능한 전이를 인코딩한 파싱 테이블을 만드는 것입니다. 이러한 테이블은 보통 문법의 first 집합과 follow 집합으로부터 구성됩니다:

규칙이 주어졌을 때, first 집합은 그 규칙의 완전한 유도에서 맨 처음에 나타날 수 있는 모든 종단 기호(terminal)의 모음입니다. 직관적으로 설명하면, 이 집합은 파서가 규칙 안의 여러 대안 가운데 하나를 고르는 데 도움을 줍니다. 예를 들어, 다음 규칙이 주어졌을 때:
```
rule: A | B
```
A만 종단 기호 a로 시작할 수 있고 B만 종단 기호 b로 시작할 수 있다면, 파서는 이 규칙을 파싱하다가 토큰 b를 만났을 때 비종단 기호 B를 따라가야 한다는 것을 압니다.
규칙이 빈 문자열로 확장될 수 있는 경우에는 이 단순한 아이디어를 확장해야 합니다. 규칙이 주어졌을 때, follow 집합은 부분 유도에서 그 규칙의 바로 오른쪽에 나타날 수 있는 종단 기호의 모음입니다. 직관적으로 설명하면, 이 집합은 빈 대안의 문제를 해결합니다. 예를 들어, 다음 규칙이 주어졌을 때:
```
rule: A 'b'
```
파서가 토큰 b를 가지고 있고 비종단 기호 A가 토큰 a로만 시작할 수 있다면, 파서는 이것이 유효하지 않은 프로그램이라고 판단할 수 있습니다. 그러나 A가 빈 문자열로 확장될 수 있다면(이를 ε-생성 규칙이라고 합니다), 다음 토큰 b가 A의 follow 집합에 속하므로 파서는 이를 유효한 빈 A로 인식합니다.

현재 Python 문법에는 ε-생성 규칙이 없으므로, 파싱 테이블을 만들 때 follow 집합이 필요하지 않습니다. 현재 CPython에서는 파서 제너레이터 프로그램이 문법을 읽어, C 프로그램인 파서에 포함될 수 있는 결정적 유한 오토마타(DFA) 집합을 나타내는 파싱 테이블을 생성합니다. 파서는 이 데이터를 사용하여 때로는 곧바로 “파스 트리”라고도 불리는 구체 문법 트리(Concrete Syntax Tree, CST)를 생성하는 푸시다운 오토마톤입니다. 이 과정에서 first 집합은 DFA를 생성할 때 간접적으로 사용됩니다.

LL(1) 파서와 문법은 대개 효율적이며, 구현하고 생성하기도 간단합니다. 하지만 LL(1) 제약 아래에서는 흔히 쓰이는 일부 구문을 언어 설계자와 독자에게 자연스러운 방식으로 표현할 수 없습니다. Python 언어의 일부 구문도 여기에 포함됩니다.

LL(1) 파서는 가능성을 구분할 때 토큰을 하나만 미리 볼 수 있으므로, 문법의 일부 규칙은 모호해질 수 있습니다. 예를 들어, 다음 규칙은:

rule: A | B

A와 B 양쪽의 첫 집합(first set)에 공통 원소가 있으면 모호합니다. 파서가 입력 프로그램에서 A와 B가 모두 시작할 수 있는 토큰을 만나면, 모호성을 해소하기 위해 프로그램의 토큰을 더 살펴볼 수 없으므로 어느 선택지를 확장해야 할지 추론할 수 없습니다. 이 규칙을 동등한 LL(1) 규칙으로 변환할 수는 있지만, 그렇게 하면 사람이 읽을 때 그 의미를 파악하기가 더 어려워질 수 있습니다. 이 문서 뒷부분의 예시들은 현재의 LL(1) 기반 문법이 이러한 상황 때문에 많은 어려움을 겪고 있음을 보여 줍니다.

LL(1)이 배제하는 또 다른 광범위한 규칙 부류는 좌재귀(left-recursive) 규칙입니다. 어떤 규칙이 자기 자신을 가장 왼쪽 기호로 갖는 문장 형식(sentential form)으로 유도될 수 있으면 그 규칙은 좌재귀적입니다. 예를 들어 다음 규칙은:

rule: rule 'a'

자기 자신으로 시작하는 표현식으로 확장될 수 있으므로 좌재귀적입니다. 뒤에서 설명하겠지만, 좌재귀는 원하는 특정 언어 속성을 문법에 직접 표현하는 자연스러운 방법입니다.

PEG 파서에 대한 배경

PEG(Parsing Expression Grammar) 문법은 작성 방식이 파서가 그 문법을 파싱할 때 동작하는 방식을 더 밀접하게 반영한다는 점에서 (현재 문법과 같은) 문맥 자유 문법과 다릅니다. 근본적인 기술적 차이는 선택 연산자에 순서가 있다는 점입니다. 이는 다음과 같이 작성할 때:

rule: A | B | C

(LL(1) 파서와 같은) 문맥 자유 문법 파서는 입력 문자열이 주어졌을 때 어느 대안(A, B 또는 C)을 확장해야 하는지 추론하는 구조를 생성하는 반면, PEG 파서는 첫 번째 대안이 성공하는지 확인하고 그것이 실패한 경우에만 작성된 순서대로 두 번째나 세 번째 대안으로 넘어간다는 뜻입니다. 이 때문에 선택 연산자는 교환 법칙이 성립하지 않습니다.

LL(1) 파서와 달리 PEG 기반 파서는 모호할 수 없습니다. 어떤 문자열이 파싱된다면, 그 문자열에는 유효한 파스 트리가 정확히 하나 존재합니다. 이는 PEG 기반 파서가 앞 절에서 설명한 모호성 문제를 겪을 수 없다는 뜻입니다.

PEG 파서는 보통 재귀 하향 파서로 구성되며, 이때 문법의 모든 규칙은 파서를 구현하는 프로그램의 함수 하나에 대응하고, 파싱 표현식(규칙의 “확장” 또는 “정의”)은 해당 함수의 “코드”를 나타냅니다. 각 파싱 함수는 개념적으로 입력 문자열을 인자로 받아 다음 결과 중 하나를 산출합니다.

“성공” 결과입니다. 이 결과는 해당 표현식이 그 규칙으로 파싱될 수 있음을 나타내며, 함수는 선택적으로 앞으로 나아가거나 전달받은 입력 문자열의 문자를 하나 이상 소비할 수 있습니다.
“실패” 결과이며, 이 경우 입력은 소비되지 않습니다.

“실패” 결과가 프로그램이 잘못되었거나 파싱에 실패했다는 뜻은 아니라는 점에 유의하십시오. 선택 연산자에 순서가 있으므로 “실패” 결과는 단지 “다음 선택지 시도”를 의미할 뿐입니다. PEG 파서는 무한 전방 탐색(lookahead)을 하므로(즉, 규칙을 결정하기 전에 임의 개수의 토큰을 고려할 수 있으므로), PEG 파서를 재귀 하향 파서로 직접 구현하면 LL(1) 파서에 비해 최악의 경우 지수 시간 성능을 보이게 됩니다. 보통 PEG 파서는 “packrat 파싱” [1]이라는 기법으로 이러한 지수 시간 복잡도를 피합니다. 이 기법은 파싱하기 전에 프로그램 전체를 메모리에 적재할 뿐만 아니라 파서가 임의로 역추적(backtrack)할 수 있게 해 줍니다. 이는 각 위치에서 이미 매칭된 규칙을 메모이제이션함으로써 효율적으로 이루어집니다. 메모이제이션 캐시의 대가로, 파서는 보통 테이블 기반인 단순한 LL(1) 파서보다 당연히 더 많은 메모리를 사용하게 됩니다. 이 비용을 왜 감수할 만하다고 보는지는 이 문서 뒷부분에서 설명하겠습니다.

근거

이 절에서는 CPython의 현재 파서 구조에 존재하며 새로운 파서가 필요한 이유가 되는 문제들을 나열합니다.

일부 규칙은 실제로는 LL(1)이 아닙니다

파이썬 문법은 LL(1) 파서로 파싱되므로 엄밀히 말하면 LL(1) 문법입니다. 그러나 여러 규칙이 LL(1)이 아니며, 이를 처리하기 위해 문법과 CPython의 다른 부분에 여러 우회책이 구현되어 있습니다. 예를 들어, 대입 표현식에 대한 다음 규칙을 살펴보십시오.:

namedexpr_test: [NAME ':='] test

이 단순한 규칙은 Python 문법과 호환되지 않는데, NAME이 규칙 test의 first 집합 원소에 속하기 때문입니다. 이 제약을 우회하기 위해 현재 문법에 실제로 들어 있는 규칙은 다음과 같습니다.:

namedexpr_test: test [':=' test]

이 규칙은 이전 규칙보다 훨씬 넓어서 [x for x in y] := [1,2,3]과 같은 구문까지 허용합니다. 규칙을 원하는 형태로 제한하는 방법은 파스 트리를 추상 문법 트리로 변환할 때 이러한 원치 않는 구성을 허용하지 않는 것입니다. 이 방식은 우아하지 않을 뿐만 아니라 유지보수 부담도 상당합니다. 원래 파서만 맡아야 할 일인데도, 유효한 프로그램과 유효하지 않은 프로그램을 구별하는 일을 AST 생성 루틴과 컴파일러가 떠맡게 되기 때문입니다. 이로 인해 실제 문법 파일이 실제 문법(즉, 유효한 모든 Python 프로그램의 집합)을 정확히 반영하지 못하는 결과로도 이어집니다.

현재 문법의 다른 여러 규칙에도 비슷한 우회책이 있습니다. 때로는 이 문제를 해결할 수 없습니다. 예를 들어, bpo-12782: Multiple context expressions do not support parentheses for continuation across lines는 다음과 같은 작성 방식을 지원하는 LL(1) 규칙을 만드는 것이:

with (
    open("a_really_long_foo") as foo,
    open("a_really_long_baz") as baz,
    open("a_really_long_bar") as bar
):
  ...

불가능하다는 것을 보여 줍니다. 컨텍스트 관리자로 나타날 수 있는 문법 항목들의 first 집합에 여는 괄호가 포함되어 있어 규칙이 모호해지기 때문입니다. 이 규칙은 언어의 다른 부분(여러 항목을 임포트하는 규칙 등)과 일관될 뿐만 아니라 자동 포매팅 도구에도 매우 유용합니다. 괄호로 묶인 그룹은 보통 함께 포매팅할 요소들을 묶는 데 사용되기 때문입니다(도구가 리스트, 집합 등의 내용을 다루는 방식과 같습니다).

복잡한 AST 파싱

현재 파서의 또 다른 문제는 AST 생성 루틴이 생성된 파스 트리의 특정 형태에 지나치게 강하게 결합되어 있다는 점입니다. 이 때문에 많은 동작과 선택이 암묵적으로 이루어져 AST를 생성하는 코드가 특히 복잡합니다. 예를 들어, AST 생성 코드는 주어진 파스 노드에 있는 자식 노드의 개수를 보고 특정 규칙의 어떤 대안이 생성되었는지 판단합니다. 이 속성은 문법 파일과 직접적인 관련이 없고 구현 세부 사항의 영향을 받으므로 코드를 따라가기 어렵습니다. 그 결과, AST 생성 코드의 상당 부분이 전달받은 파스 트리의 특정 형태를 검사하고 추론하는 데 쓰입니다.

좌재귀의 부재

앞서 설명했듯이, LL(1) 문법에는 좌재귀를 허용할 수 없다는 한계가 있습니다. 이 때문에 일부 규칙은 매우 부자연스럽게 작성할 수밖에 없고, 프로그래머가 평소에 프로그램을 생각하는 방식과도 동떨어지게 됩니다. 예를 들어 다음 구문(현재 문법에 있는 여러 규칙을 단순화한 변형)은:

expr: expr '+' term | term

LL(1) 파서로 파싱할 수 없습니다. 전통적인 해결책은 문제를 피해 가도록 문법을 다시 작성하는 것입니다.:

expr: term ('+' term)*

이 형태의 문제는 파스 트리가 매우 부자연스러운 형태가 될 수밖에 없다는 점입니다. 이 규칙을 사용하면 입력 프로그램 a + b + c의 파스 트리가 평탄화되며(['a', '+', 'b', '+', 'c']), 좌재귀 파스 트리([['a', '+', 'b'], '+', 'c'])를 구성하려면 후처리를 거쳐야 하기 때문입니다. 두 번째 규칙처럼 작성할 수밖에 없으면 파스 트리가 원하는 결합 방향을 올바르게 반영하지 못할 뿐만 아니라, 이후 컴파일 단계에서 이러한 경우를 찾아내 후처리해야 하므로 부담도 더 커집니다.

중간 파스 트리

현재 파서에 존재하는 마지막 문제는 파스 트리, 즉 구체 문법 트리를 중간 단계로 생성한 뒤 나중에 이를 추상 문법 트리로 변환한다는 점입니다. CST를 구성하는 일은 파서 및 컴파일러 파이프라인에서 매우 흔하지만, CPython에서는 이 중간 CST를 다른 어느 곳에서도 사용하지 않습니다(parser 모듈을 통해 간접적으로만 노출되며, CST 생성 코드 가운데 이 모듈에서 재사용되는 부분은 놀라울 정도로 적습니다). 더 나쁜 점은 트리 전체가 메모리에 유지되며, 자식이 하나뿐인 노드들의 사슬로 이루어진 브랜치가 많이 남아 있다는 것입니다. 이 때문에 메모리가 상당히 많이 소비된다는 사실이 확인되었습니다(예: bpo-26415: Excessive peak memory consumption by the Python parser).

문법과 AST 사이에 중간 결과를 만들어야 한다는 것은 바람직하지 않을 뿐만 아니라, AST 생성 단계를 훨씬 더 복잡하게 만들어 유지 보수 부담을 상당히 늘립니다.

새로 제안하는 PEG 파서

새로 제안하는 PEG 파서는 다음과 같은 부분으로 구성됩니다.

문법 파일을 읽어 해당 문법을 파싱할 수 있는 PEG 파서를 Python 또는 C로 생성하는 파서 제너레이터.
파서 제너레이터 자체에 사용되는 Python 파서를 자동으로 생성하는 PEG 메타 문법(즉, 수작업으로 작성한 파서는 없습니다).
C 및 Python AST 객체를 직접 생성할 수 있는, (파서 제너레이터로) 생성된 파서.

좌재귀

PEG 파서는 일반적으로 좌재귀를 지원하지 않지만, 저희는 Medeiros 등 [2]이 설명한 것과 유사하되 정적 변수 대신 메모이제이션 캐시를 사용하는 기법을 구현했습니다. 이 접근 방식은 Warth 등 [3]이 설명한 방식에 더 가깝습니다. 이를 통해 단순한 좌재귀 규칙뿐만 아니라 다음과 같이 간접 좌재귀를 포함하는 더 복잡한 규칙도 작성할 수 있습니다.:

rule1: rule2 | 'a'
rule2: rule3 | 'b'
rule3: rule1 | 'c'

또한 다음과 같은 “숨은 좌재귀”도 작성할 수 있습니다.:

rule: 'optional'? rule '@' some_other_rule

문법

문법은 다음 형식의 규칙들이 나열된 것으로 구성됩니다.:

rule_name: expression

선택적으로 규칙 이름 바로 뒤에 타입을 포함할 수 있으며, 이 타입은 해당 규칙에 대응하는 C 또는 Python 함수의 반환 타입을 지정합니다.:

rule_name[return_type]: expression

반환 타입을 생략하면 C에서는 void *가, Python에서는 Any가 반환됩니다.

문법 표현식

`# comment`

Python 스타일 주석입니다.

`e1 e2`

e1을 매칭한 다음 e2를 매칭합니다.

rule_name: first_rule second_rule

`e1 | e2`

e1 또는 e2를 매칭합니다.

서식을 위해 첫 번째 대안을 규칙 이름 다음 줄에 둘 수도 있습니다. 이 경우 다음과 같이 첫 번째 대안 앞에 |를 사용해야 합니다.

rule_name[return_type]:
    | first_alt
    | second_alt

`( e )`

e를 매칭합니다.

rule_name: (e)

조금 더 복잡하면서 유용한 예로는 그룹화 연산자를 반복 연산자와 함께 사용하는 경우가 있습니다.

rule_name: (e1 e2)*

`[ e ] or e?`

e에 선택적으로 매치합니다.

rule_name: [e]

더 유용한 예로, 후행 쉼표를 선택 사항으로 정의하는 경우가 있습니다:

rule_name: e (',' e)* [',']

`e*`

e가 0번 이상 나타나는 것에 매치합니다.

rule_name: (e1 e2)*

`e+`

e가 1번 이상 나타나는 것에 매치합니다.

rule_name: (e1 e2)+

`s.e+`

s로 구분되어 e가 1번 이상 나타나는 것에 매치합니다. 생성된 파스 트리에는 구분자가 포함되지 않습니다. 그 점을 제외하면 (e (s e)*)와 동일합니다.

rule_name: ','.e+

`&e`

입력을 소비하지 않고, e를 파싱할 수 있으면 성공합니다.

`!e`

입력을 소비하지 않고, e를 파싱할 수 있으면 실패합니다.

제안된 Python 문법에서 가져온 다음 예는 primary가 뒤에 ., (, [ 중 어느 것도 오지 않는 atom으로 구성된다고 지정합니다:

primary: atom !'.' !'(' !'['

`~`

파싱에 실패하더라도 현재 대안에 커밋합니다.

rule_name: '(' ~ some_rule ')' | some_alt

이 예에서 왼쪽 괄호가 파싱되면, some_rule이나 ‘)’의 파싱에 실패하더라도 다른 대안은 고려되지 않습니다.

문법 내의 변수

하위 표현식 앞에 식별자와 = 기호를 붙여 이름을 지정할 수 있습니다. 그러면 이 이름을 다음과 같이 액션(아래 참조)에서 사용할 수 있습니다:

rule_name[return_type]: '(' a=some_other_rule ')' { a }

문법 액션

문법과 AST 생성 사이의 관계를 흐리게 만드는 중간 단계를 피하기 위해, 제안된 PEG 파서는 문법 액션을 통해 규칙에 대한 AST 노드를 직접 생성할 수 있도록 합니다. 문법 액션은 문법 규칙이 성공적으로 파싱되었을 때 평가되는 언어별 표현식입니다. 이 표현식은 파서 제너레이터에서 원하는 출력에 따라 Python이나 C로 작성할 수 있습니다. 즉, 파서를 Python으로 하나, C로 또 하나 생성하려면 두 개의 문법 파일을 작성해야 하며, 각 파일은 서로 다른 액션 집합을 가지되 해당 액션을 제외한 나머지는 두 파일에서 모두 동일하게 유지해야 합니다. Python 액션을 사용하는 문법의 예로, 파서 제너레이터에서 문법 파일을 파싱하는 부분은 파싱 결과로 문법 트리를 생성하는 Python 액션이 담긴 메타 문법 파일로부터 부트스트랩됩니다.

새로 제안된 Python용 PEG 문법의 경우, 액션이 있으면 AST가 어떻게 구성되는지를 문법 자체에서 직접 기술할 수 있으므로 문법이 더 명확해지고 유지 보수하기 쉬워집니다. 이 AST 생성 과정은 공통적인 AST 객체 조작과 문법과 직접 관련되지 않은 기타 필요한 작업을 분리해 둔 몇 가지 헬퍼 함수를 사용하여 지원됩니다.

이러한 액션을 나타내기 위해 각 대안 뒤에 중괄호로 감싼 액션 코드를 붙일 수 있으며, 이 코드는 해당 대안의 반환값을 지정합니다:

rule_name[return_type]:
    | first_alt1 first_alt2 { first_alt1 }
    | second_alt1 second_alt2 { second_alt1 }

액션이 생략되고 C 코드를 생성하는 경우에는 두 가지 가능성이 있습니다:

대안에 이름이 하나만 있으면 그것이 반환됩니다.
그렇지 않으면 더미 이름 객체가 반환됩니다(이 경우는 피해야 합니다).

액션이 생략되고 Python 코드를 생성하는 경우에는 파싱된 모든 표현식을 담은 리스트가 반환됩니다(이는 디버깅용입니다).

PEG 제너레이터가 지원하는 문법에 대한 전체 메타 문법은 다음과 같습니다:

start[Grammar]: grammar ENDMARKER { grammar }

grammar[Grammar]:
    | metas rules { Grammar(rules, metas) }
    | rules { Grammar(rules, []) }

metas[MetaList]:
    | meta metas { [meta] + metas }
    | meta { [meta] }

meta[MetaTuple]:
    | "@" NAME NEWLINE { (name.string, None) }
    | "@" a=NAME b=NAME NEWLINE { (a.string, b.string) }
    | "@" NAME STRING NEWLINE { (name.string, literal_eval(string.string)) }

rules[RuleList]:
    | rule rules { [rule] + rules }
    | rule { [rule] }

rule[Rule]:
    | rulename ":" alts NEWLINE INDENT more_alts DEDENT {
          Rule(rulename[0], rulename[1], Rhs(alts.alts + more_alts.alts)) }
    | rulename ":" NEWLINE INDENT more_alts DEDENT { Rule(rulename[0], rulename[1], more_alts) }
    | rulename ":" alts NEWLINE { Rule(rulename[0], rulename[1], alts) }

rulename[RuleName]:
    | NAME '[' type=NAME '*' ']' {(name.string, type.string+"*")}
    | NAME '[' type=NAME ']' {(name.string, type.string)}
    | NAME {(name.string, None)}

alts[Rhs]:
    | alt "|" alts { Rhs([alt] + alts.alts)}
    | alt { Rhs([alt]) }

more_alts[Rhs]:
    | "|" alts NEWLINE more_alts { Rhs(alts.alts + more_alts.alts) }
    | "|" alts NEWLINE { Rhs(alts.alts) }

alt[Alt]:
    | items '$' action { Alt(items + [NamedItem(None, NameLeaf('ENDMARKER'))], action=action) }
    | items '$' { Alt(items + [NamedItem(None, NameLeaf('ENDMARKER'))], action=None) }
    | items action { Alt(items, action=action) }
    | items { Alt(items, action=None) }

items[NamedItemList]:
    | named_item items { [named_item] + items }
    | named_item { [named_item] }

named_item[NamedItem]:
    | NAME '=' ~ item {NamedItem(name.string, item)}
    | item {NamedItem(None, item)}
    | it=lookahead {NamedItem(None, it)}

lookahead[LookaheadOrCut]:
    | '&' ~ atom {PositiveLookahead(atom)}
    | '!' ~ atom {NegativeLookahead(atom)}
    | '~' {Cut()}

item[Item]:
    | '[' ~ alts ']' {Opt(alts)}
    |  atom '?' {Opt(atom)}
    |  atom '*' {Repeat0(atom)}
    |  atom '+' {Repeat1(atom)}
    |  sep=atom '.' node=atom '+' {Gather(sep, node)}
    |  atom {atom}

atom[Plain]:
    | '(' ~ alts ')' {Group(alts)}
    | NAME {NameLeaf(name.string) }
    | STRING {StringLeaf(string.string)}

# Mini-grammar for the actions

action[str]: "{" ~ target_atoms "}" { target_atoms }

target_atoms[str]:
    | target_atom target_atoms { target_atom + " " + target_atoms }
    | target_atom { target_atom }

target_atom[str]:
    | "{" ~ target_atoms "}" { "{" + target_atoms + "}" }
    | NAME { name.string }
    | NUMBER { number.string }
    | STRING { string.string }
    | "?" { "?" }
    | ":" { ":" }

예를 들어, 다음의 간단한 문법 파일로 간단한 산술 표현식을 파싱하고 유효한 C 기반 Python AST를 반환하는 완전한 파서를 바로 생성할 수 있습니다:

start[mod_ty]: a=expr_stmt* $ { Module(a, NULL, p->arena) }
expr_stmt[stmt_ty]: a=expr NEWLINE { _Py_Expr(a, EXTRA) }
expr[expr_ty]:
    | l=expr '+' r=term { _Py_BinOp(l, Add, r, EXTRA) }
    | l=expr '-' r=term { _Py_BinOp(l, Sub, r, EXTRA) }
    | t=term { t }

term[expr_ty]:
    | l=term '*' r=factor { _Py_BinOp(l, Mult, r, EXTRA) }
    | l=term '/' r=factor { _Py_BinOp(l, Div, r, EXTRA) }
    | f=factor { f }

factor[expr_ty]:
    | '(' e=expr ')' { e }
    | a=atom { a }

atom[expr_ty]:
    | n=NAME { n }
    | n=NUMBER { n }
    | s=STRING { s }

여기서 EXTRA는 start_lineno, start_col_offset, end_lineno, end_col_offset, p->arena로 확장되는 매크로이며, 이들은 파서가 자동으로 주입하는 변수입니다. p는 파서의 모든 상태를 보관하는 객체를 가리킵니다.

Python AST 객체를 대상으로 작성한 비슷한 문법은 다음과 같습니다:

start: expr NEWLINE? ENDMARKER { ast.Expression(expr) }
expr:
    | expr '+' term { ast.BinOp(expr, ast.Add(), term) }
    | expr '-' term { ast.BinOp(expr, ast.Sub(), term) }
    | term { term }

term:
    | l=term '*' r=factor { ast.BinOp(l, ast.Mult(), r) }
    | term '/' factor { ast.BinOp(term, ast.Div(), factor) }
    | factor { factor }

factor:
    | '(' expr ')' { expr }
    | atom { atom }

atom:
    | NAME { ast.Name(id=name.string, ctx=ast.Load()) }
    | NUMBER { ast.Constant(value=ast.literal_eval(number.string)) }

마이그레이션 계획

이 절에서는 이 PEP가 승인될 경우 새로운 PEG 기반 파서로 이전하기 위한 마이그레이션 계획을 설명합니다. 마이그레이션은 필요한 경우 초기에는 이전 파서로 대체할 수 있도록 하는 일련의 단계로 진행됩니다:

Python 3.9 알파 6부터, 새 파서와 이전 파서를 전환할 수 있는 명령줄 플래그 및 환경 변수와 함께, 새 파서와 이전 파서를 각각 독립적으로 호출할 수 있는 명시적인 API를 포함하여 새로운 PEG 기반 파서 장치를 CPython에 포함합니다. 이 단계에서 ast.parse와 compile 같은 모든 Python API는 플래그나 환경 변수로 설정된 파서를 사용하며, 기본 파서는 새로운 PEG 기반 파서가 됩니다.
Python 3.9와 Python 3.10 사이에는 새로운 Python 릴리스(Python 3.10)가 나올 때까지 이전 파서와 관련 코드(“parser” 모듈 등)를 유지합니다. 그동안, 그리고 이전 파서가 제거될 때까지는 PEG 파서가 필요한 새로운 Python 문법은 추가하지 않습니다. 즉, 이전 파서가 제거될 때까지 문법은 LL(1)로 유지됩니다.
Python 3.10에서는 이전 파서, 명령줄 플래그, 환경 변수, “parser” 모듈과 관련 코드를 제거합니다.

성능과 검증

저희는 새 파서의 시간 측정과 검증을 폭넓게 수행했으며, 그 결과 새 파서의 품질이 현재 파서를 대체하기에 충분히 높다고 확신합니다.

검증

먼저 검증에 관해 말씀드리면, 저희는 Python 3.8 표준 라이브러리 전체를 정기적으로 컴파일하고, 그 결과로 나온 AST를 표준 컴파일러가 생성한 AST와 모든 측면에서 비교합니다. (이 과정에서 표준 파서가 줄 번호와 열 번호를 처리하는 방식의 버그를 몇 개 발견했으며, 이 버그들은 여러 이슈와 PR을 통해 업스트림에서 모두 수정했습니다.)

또한 가끔은 훨씬 더 큰 코드베이스(PyPI에서 가장 인기 있는 패키지 약 3800개)도 컴파일했으며, 이를 통해 새 파서의 추가 버그를 (아주) 몇 개 찾을 수 있었습니다.

(저희가 아직 충분히 살펴보지 못한 영역 하나는 잘못된 프로그램을 모두 거부하는지입니다. 명시적인 거부 사례 일부를 확인하는 단위 테스트는 있지만, 예를 들어 기존 코드에 미묘한 버그를 무작위로 끼워 넣는 퍼저를 사용하는 등 더 많은 작업을 할 수 있습니다. 이 영역에서의 도움은 언제든 환영합니다.)

성능

저희는 새 파서의 성능을 조정하여 속도와 메모리 사용량 모두에서 현재 파서와 10% 이내의 차이를 보이도록 만들었습니다. PEG/packrat 파싱 알고리즘은 본질적으로 현재의 LL(1) 파서보다 메모리를 더 많이 사용하지만, 저희는 중간 CST를 만들지 않기 때문에 이 점에서 유리합니다.

다음은 몇 가지 벤치마크 결과입니다. 이 벤치마크는 소스 코드를 바이트코드로 컴파일하는 작업에 초점을 맞추었습니다. 이것이 가장 현실적인 상황이기 때문입니다. Python 코드에 AST를 반환하는 작업은 대표성이 떨어집니다. 내부 AST(C 코드에서만 접근 가능)를 외부 AST(ast.AST의 인스턴스)로 변환하는 과정이 파서 자체보다 시간이 더 오래 걸리기 때문입니다.

여기에 제시한 모든 측정은 최신 MacBook Pro에서 세 번 실행한 결과의 중앙값입니다. 같은 컴퓨터에서 실행 중인 다른 애플리케이션을 중지하는 데 특별히 신경 쓰지는 않았습니다.

첫 번째 시간 측정은 저희의 표준 테스트 파일로 수행했습니다. 이 파일은 100,000줄로 이루어져 있으며, 다음 세 줄이 끝없이 반복됩니다:

1 + 2 + 4 + 5 + 6 + 7 + 8 + 9 + 10 + ((((((11 * 12 * 13 * 14 * 15 + 16 * 17 + 18 * 19 * 20))))))
2*3 + 4*5*6
12 + (2 * 3 * 4 * 5 + 6 + 7 * 8)

파싱만 하고 내부 AST를 버리는 데는 1.16초가 걸리며, 최대 RSS는 681 MiB입니다.
파싱 후 ast.AST로 변환하는 데는 6.34초가 걸리며, 최대 RSS는 1029 MiB입니다.
파싱 후 바이트코드로 컴파일하는 데는 1.28초가 걸리며, 최대 RSS는 681 MiB입니다.
현재 파서로는 파싱과 컴파일에 1.44초가 걸리며, 최대 RSS는 836 MiB입니다.

이 테스트 파일에서는 새 파서가 현재 파서보다 빠르고 메모리도 적게 사용합니다(마지막 두 항목을 비교하십시오).

더 현실적인 입력인 Python 3.8 표준 라이브러리 전체로도 시간을 측정했습니다. 이 입력은 파일 1,641개, 749,570줄, 27,622,497바이트로 이루어져 있습니다. (다만 그중 11개 파일은 인코딩 문제 때문에 어떤 Python 3 파서로도 컴파일할 수 없으며, 이 중에는 의도된 경우도 있습니다.)

내부 AST까지 컴파일한 후 버리는 데 2.141초가 걸렸습니다. 이는 초당 350,040줄, 또는 초당 12,899,367바이트에 해당합니다. 최대 RSS는 74 MiB였습니다(표준 라이브러리에서 가장 큰 파일도 저희의 기준 테스트 파일보다 훨씬 작습니다).
바이트코드로 컴파일하는 데 3.290초가 걸렸습니다. 이는 초당 227,861줄, 또는 초당 8,396,942바이트에 해당합니다. 최대 RSS는 77 MiB였습니다.
현재 파서로 바이트코드까지 컴파일하는 데 3.367초가 걸렸습니다. 이는 초당 222,620줄, 또는 초당 8,203,780바이트에 해당합니다. 최대 RSS는 70 MiB였습니다.

마지막 두 항목을 비교하면 새 파서가 약간 더 빠르지만 메모리를 약간(약 10%) 더 사용한다는 것을 알 수 있습니다. 저희는 이 정도면 수용할 만하다고 생각합니다. (또한 메모리 사용량을 줄이기 위해 할 수 있는 조정이 아마 더 있을 것입니다.)

기각된 대안

새 파서를 구현하는 다른 방법을 진지하게 검토하지는 않았지만, 여기서 LALR(1)에 대해 간단히 논의합니다.

30년 전 첫 번째 저자는 당시 업계 표준이던 LALR(1)(예: Bison과 Yacc)을 사용하는 대신 Python 파서를 자신만의 방식으로 만들기로 했습니다. 그 이유는 주로 감정적인 것(직감, 직관)이었으며, 다른 프로젝트에서 Yacc을 사용했던 과거 경험에 근거한 것이었습니다. 당시 문법을 개발하는 데 예상보다 더 많은 노력이 들었습니다(부분적으로는 shift-reduce 충돌 때문이었습니다). Bison과 Yacc에 대해 지금도 유효한 구체적인 비판 하나는, 이들의 메타 문법(문법을 파서 제너레이터에 입력하는 데 쓰는 표기법)이 [optional_clause]나 (repeated_clause)* 같은 EBNF 편의 기능을 지원하지 않는다는 점입니다. 자체 파서 제너레이터를 사용하면 문법 구조와 일치하는 구문 트리를 자동으로 생성할 수 있었고, EBNF를 사용하면 그 트리가 문법의 “사람 친화적인” 구조와 일치하도록 만들 수 있었습니다.

LR의 다른 변형들은 검토하지 않았으며, LL(예: ANTLR)도 마찬가지였습니다. PEG를 선택한 이유는 재귀 하향 파싱을 기본적으로 이해하고 있으면 쉽게 이해할 수 있었기 때문입니다.

참고 문헌

[4] PEG 파싱에 관한 Guido의 연재 글 https://medium.com/@gvanrossum_83706/peg-parsing-series-de5d41b2ed60

Copyright

This document has been placed in the public domain.