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) 파서는 입력을 왼쪽에서 오른쪽으로 구문 분석하고, 단 하나의 선행 토큰만 사용하여 문장의 가장 왼쪽 유도를 수행하는 하향식 파서로 정의됩니다. LL(1) 파서를 구성하거나 생성하는 전통적인 방법은 파서의 가능한 모든 상태 사이의 가능한 전이를 인코딩하는 parse table을 생성하는 것입니다. 이러한 테이블은 일반적으로 문법의 first sets와 follow sets로부터 구성됩니다:

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

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

LL(1) 파서와 문법은 일반적으로 효율적이며 구현하고 생성하기도 쉽습니다. 그러나 LL(1) 제한하에서는 언어 설계자와 독자에게 자연스러운 방식으로 특정 일반적인 구문을 표현할 수 없습니다. 여기에는 Python 언어의 일부 구문도 포함됩니다.

LL(1) 파서는 가능성을 구별하기 위해 한 토큰 앞만 살펴볼 수 있으므로, 문법의 일부 규칙은 모호할 수 있습니다. 예를 들어 다음 규칙이 주어졌다고 합시다::

rule: A | B

A와 B의 첫 번째 집합 모두에 일부 공통 원소가 있으면 모호합니다. 파서가 입력 프로그램에서 A와 B 모두로 시작할 수 있는 토큰을 발견하면, 프로그램의 더 이상 어떤 토큰도 검사하여 구분할 수 없으므로 어느 선택지를 확장해야 하는지 추론할 수 없습니다. 이 규칙은 동등한 LL(1) 규칙으로 변환할 수 있지만, 그러면 사람이 그 의미를 파악하기 더 어려워질 수 있습니다. 이 문서의 뒷부분에 나오는 예제는 현재의 LL(1) 기반 문법이 이 상황을 크게 겪는다는 것을 보여 줍니다.

LL(1)에서 배제되는 또 다른 광범위한 규칙 부류는 왼쪽 재귀 규칙입니다. 규칙이 자신을 가장 왼쪽 기호로 갖는 문장형으로 유도될 수 있으면 해당 규칙은 왼쪽 재귀입니다. 예를 들어 다음 규칙은:

rule: rule 'a'

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

PEG 파서의 배경

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

rule: A | B | C

문맥 자유 문법 파서(LL(1) 파서와 같은 파서)는 입력 문자열이 주어지면 어떤 대안(A, B 또는 C)을 확장해야 하는지 추론하는 구문을 생성하는 반면, PEG 파서는 첫 번째 대안이 성공하는지 확인하고, 실패한 경우에만 작성된 순서에 따라 두 번째 대안 또는 세 번째 대안으로 계속 진행합니다. 따라서 선택 연산자는 교환법칙을 따르지 않습니다.

LL(1) 파서와 달리 PEG 기반 파서는 모호할 수 없습니다. 문자열이 파싱되면 유효한 파싱 트리가 정확히 하나만 존재합니다. 이는 PEG 기반 파서가 이전 절에서 설명한 모호성 문제를 겪을 수 없다는 의미입니다.

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

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

선택 연산자에 순서가 있으므로 “실패” 결과는 단순히 “다음 선택지를 시도하십시오”를 나타낼 뿐, 프로그램이 잘못되었거나 파싱에 실패했음을 의미하지 않는다는 점에 유의하십시오. PEG 파서는 무한한 선행 탐색을 수행하기 때문에(즉, 규칙을 결정하기 전에 임의의 수의 토큰을 고려할 수 있기 때문에), PEG 파서를 재귀 하강 파서로 직접 구현하면 최악의 경우 LL(1) 파서와 비교하여 지수 시간 성능을 보입니다. 일반적으로 PEG 파서는 “팩랫 파싱”이라고 하는 기법 [1] 을 사용하여 이러한 지수 시간 복잡도를 피합니다. 이 기법은 파싱하기 전에 전체 프로그램을 메모리에 로드할 뿐만 아니라 파서가 임의로 역추적할 수 있도록 합니다. 이는 각 위치에서 이미 일치한 규칙을 메모이제이션하여 효율적으로 수행됩니다. 메모이제이션 캐시의 비용은 일반적인 단순 LL(1) 파서가 테이블 기반인 것과 달리, 파서가 자연스럽게 더 많은 메모리를 사용한다는 점입니다. 이 문서의 뒷부분에서 이 비용을 수용할 수 있다고 판단하는 이유를 설명하겠습니다.

근거

이 절에서는 새로운 파서의 필요성을 뒷받침하는, 현재 CPython의 파서 체계에 존재하는 여러 문제를 설명합니다.

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

Python 문법은 기술적으로 LL(1) 문법이지만(LL(1) 파서로 구문 분석되기 때문입니다), 여러 규칙이 LL(1)이 아니며 이를 처리하기 위한 여러 우회책이 문법과 CPython의 다른 부분에 구현되어 있습니다. 예를 들어, 대입 표현식에 대한 규칙을 살펴보십시오.:

namedexpr_test: [NAME ':='] test

이 단순한 규칙은 NAME이 test 규칙의 FIRST 집합에 속하는 요소이므로 Python 문법과 호환되지 않습니다. 이 제한을 우회하기 위해 현재 문법에 나타나는 실제 규칙은 다음과 같습니다.:

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 집합에 여는 괄호가 포함되므로, 이 규칙은 모호해지기 때문에 작성할 수 없습니다. 이 규칙은 언어의 다른 부분(예를 들어 여러 import에 대한 규칙)과 일관될 뿐만 아니라 자동 서식 지정 도구에도 매우 유용합니다. 괄호로 묶인 그룹은 일반적으로 함께 서식을 지정할 요소를 그룹화하는 데 사용되기 때문입니다(이러한 도구가 리스트, 집합 등의 내용에 대해 작동하는 방식과 같습니다).

복잡한 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 파서는 다음 구성 요소를 포함합니다.

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

좌재귀

PEG 파서는 일반적으로 좌재귀를 지원하지 않지만, 정적 변수 대신 메모이제이션 캐시를 사용하는 Medeiros et al. [2]에서 설명한 기법과 유사한 기법을 구현했습니다. 이 접근 방식은 Warth et al. [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 !'.' !'(' !'['

`~`

구문 분석에 실패하더라도 현재 대안을 확정합니다.

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 alpha 6부터 새 파서와 이전 파서 사이를 전환할 수 있는 명령줄 플래그 및 환경 변수와, 새 파서와 이전 파서를 독립적으로 호출할 수 있는 명시적 API를 함께 사용하여 새로운 PEG 기반 파서 기능을 CPython에 포함합니다. 이 단계에서 ast.parse와 compile같은 모든 Python API는 플래그 또는 환경 변수가 지정한 파서를 사용하며, 기본 파서는 새로운 PEG 기반 파서가 됩니다.
Python 3.9와 Python 3.10 사이에는 새로운 Python 릴리스(Python 3.10)가 나올 때까지 이전 파서와 관련 코드(예: “parser” 모듈)를 유지합니다. 그동안 그리고 이전 파서가 제거될 때까지는 PEG 파서를 필요로 하는 새로운 Python Grammar 추가 사항을 추가하지 않습니다. 이는 이전 파서가 제거될 때까지 문법이 LL(1)로 유지된다는 의미입니다.
Python 3.10에서는 이전 파서, 명령줄 플래그, 환경 변수, “parser” 모듈 및 관련 코드를 제거합니다.

성능 및 검증

새로운 파서에 대해 광범위한 시간 측정과 검증을 수행했으며, 이를 통해 새로운 파서의 품질이 현재 파서를 대체하기에 충분히 높다는 확신을 얻었습니다.

검증

검증을 시작하기 위해 Python 3.8 표준 라이브러리 전체를 정기적으로 컴파일하고, 그 결과로 생성된 AST의 모든 측면을 표준 컴파일러가 생성한 AST와 비교합니다. (이 과정에서 표준 파서가 행 번호와 열 번호를 처리하는 데 몇 가지 버그가 있음을 발견했으며, 일련의 이슈와 PR을 통해 이를 모두 업스트림에서 수정했습니다.)

또한 때때로 훨씬 더 큰 코드베이스(PyPI에서 가장 인기 있는 약 3,800개의 패키지)를 컴파일했으며, 이를 통해 새로운 파서에서 발생하는 (아주) 소수의 추가 버그를 발견할 수 있었습니다.

(아직 광범위하게 살펴보지 않은 영역 중 하나는 잘못된 프로그램을 모두 거부하는 것입니다. 명시적인 거부를 일정 횟수만큼 확인하는 단위 테스트가 있지만, 예를 들어 기존 코드에 무작위로 미묘한 버그를 삽입하는 퍼저를 사용하는 등 더 많은 작업을 수행할 수 있습니다. 이 영역에 대한 도움을 환영합니다.)

성능

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

아래에 몇 가지 벤치마크가 나와 있습니다. 이는 가장 현실적인 상황인 소스 코드를 바이트코드로 컴파일하는 작업에 초점을 맞춥니다. AST를 Python 코드로 반환하는 것은 대표성이 떨어집니다. 내부 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를 사용했던 과거 경험에 기반한 것이었습니다. 당시 문법 개발에 예상보다 더 많은 노력이 들었고, 그중 일부는 시프트-리듀스 충돌 때문이었습니다. 여전히 유효한 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.