파싱 표현 문법

컴퓨터 과학에서 파싱 표현 문법(parsing expression grammar, PEG)은 분석적 형식 문법의 일종으로, 언어 내의 문자열을 인식하기 위한 규칙 집합으로 형식 언어를 설명한다. 이 형식론은 브라이언 포드(Bryan Ford)가 2004년에 도입했으며 1970년대 초에 도입된 하향식 파싱 언어 계열과 밀접한 관련이 있다.
구문적으로 PEG는 문맥 자유 문법(CFG)과도 유사하지만 해석이 다르다. PEG에서는 선택 연산자가 첫 번째 일치 항목을 선택하는 반면, CFG에서는 모호할 수 있다. 이는 재귀 하향 파서와 같이 문자열 인식이 실제에서 수행되는 방식에 더 가깝다.

CFG와 달리 PEG는 모호할 수 없다. 문자열은 정확히 하나의 유효한 파스 트리를 갖거나 아예 갖지 않는다. PEG로 인식할 수 없는 문맥 자유 언어가 존재한다고 추측되지만, 아직 입증되지 않았다. PEG는 여러 해석 대안을 로컬에서 모호하지 않게 할 수 있는 컴퓨터 언어(및 로지반과 같은 인공 인간 언어)를 구문 분석하는 데 적합하지만, 모호성 해소가 전역적이어야 하는 자연어를 구문 분석하는 데는 덜 유용할 수 있다.

 정의 
파싱 표현식은 각 문자열이 일치하거나 일치하지 않을 수 있는 일종의 패턴이다. 일치하는 경우, 파싱 표현식에 의해 소비된 문자열의 고유한 접두사(전체 문자열, 빈 문자열 또는 그 사이의 일부일 수 있음)가 있다. 이 접두사는 일반적으로 표현식과 일치하는 것으로 간주된다. 그러나 문자열이 파싱 표현식과 일치하는지 여부는 (선행 조건자 때문에) 소비된 부분 다음에 오는 부분에 따라 달라질 수 있다. 파싱 표현식 언어는 특정 파싱 표현식과 일치하는 모든 문자열의 집합이다.

파싱 표현식 문법은 명명된 파싱 표현식들의 모음으로, 서로를 참조할 수 있다. 파싱 표현식에서 그러한 참조의 효과는 마치 참조된 전체 파싱 표현식이 참조 위치에 주어진 것과 같다. 파싱 표현식 문법은 또한 지정된 시작 표현식을 가진다. 문자열이 시작 표현식과 일치하면 문법과 일치한다.

일치하는 문자열의 요소는 말단 기호 또는 줄여서 단말이라고 한다. 마찬가지로 파싱 표현식에 할당된 이름은 비말단 기호 또는 줄여서 비단말이라고 한다. 이러한 용어는 생성 문법에 설명적이지만, 파싱 표현식 문법의 경우 단순히 파싱 알고리즘에 대한 논의에서 거의 보편적으로 사용되기 때문에 유지되는 용어일 뿐이다.

 구문 
파싱 표현식의 추상 구문과 구체 구문 모두 문헌과 이 문서에서 사용된다. 추상 구문은 본질적으로 수식이며 주로 이론적인 맥락에서 사용되는 반면, 구체 구문 파싱 표현식은 구문 분석기를 직접 제어하는 데 사용될 수 있다. 주된 구체 구문은 포드(Ford)가 정의한 것이지만, 많은 도구들이 자체 방언을 가지고 있다. 다른 도구들은 추상 구문 파싱 표현식의 프로그래밍 언어 기본 인코딩을 구체 구문으로 사용하는 데 더 가깝다.

 원자 파싱 표현식 
다른 파싱 표현식을 포함하지 않는 두 가지 주요 파싱 표현식은 개별 단말 기호와 비단말 기호이다. 구체 구문에서 단말은 따옴표(홑따옴표 또는 겹따옴표) 안에 배치되는 반면, 따옴표가 없는 식별자는 비단말을 나타낸다:
 "terminal" Nonterminal 'another terminal'
추상 구문에서는 형식화된 구분이 없으며, 대신 각 기호가 단말 또는 비단말 중 하나로 정의되어 있다고 가정하지만, 비단말에는 대문자를 사용하고 단말에는 소문자를 사용하는 것이 일반적인 관례이다.

구체 구문에는 단말 클래스에 대한 여러 형식도 있다:
 . (마침표)는 어떤 단일 단말과도 일치하는 파싱 표현식이다.
 문자 목록 [abcde]를 둘러싼 대괄호는 나열된 문자 중 하나와 일치하는 파싱 표현식을 형성한다. 정규 표현식에서와 같이 이러한 클래스에는 하이픈으로 범위의 시작과 끝을 쓰는 범위 [0-9A-Za-z]도 포함될 수 있다. (정규 표현식의 경우와 달리 대괄호 문자 클래스에는 부정을 위한 ^가 없다. 그 목적은 대신 not-predicates를 통해 달성할 수 있다.)
 일부 방언은 문자, 숫자, 구두점 또는 공백과 같은 미리 정의된 문자 클래스에 대한 추가 표기법을 가지고 있다. 이는 정규 표현식의 상황과 유사하다.
추상 구문에서 이러한 형식은 보통 간결성을 위해 정확한 정의가 생략된 비단말로 형식화된다. 유니코드에는 수만 개의 문자(글자)가 있다. 반대로 이론적 논의에서는 복합 파싱 표현식을 사용하여 표현할 수 있는 개념에 대한 원자적 추상 구문을 도입하기도 한다. 이에는 다음이 포함된다:
 빈 문자열 ε (파싱 표현식으로서 모든 문자열과 일치하며 문자를 소비하지 않음),
 입력 끝 E (구체 구문 동등물은 !.), 그리고
 실패 (아무것도 일치하지 않음).

구체 구문에서 따옴표로 묶인 단말과 괄호로 묶인 단말은 백슬래시 이스케이프를 사용하므로, "줄 바꿈 또는 캐리지 리턴"은 [\n\r]로 작성될 수 있다. 길이가 1보다 큰 따옴표로 묶인 단말의 추상 구문 대응물은 해당 단말들의 시퀀스이다. "bar"는 "b" "a" "r"와 동일하다. 주된 구체 구문은 단말이 홑따옴표를 사용하는지 겹따옴표를 사용하는지에 따라 별개의 의미를 부여하지 않지만, 일부 방언은 하나를 대소문자 구분으로 처리하고 다른 하나는 대소문자 비구분으로 처리한다.

 복합 파싱 표현식 
기존의 파싱 표현식 e, e1, e2가 주어지면 다음 연산자를 사용하여 새로운 파싱 표현식을 구성할 수 있다:
 시퀀스: e1 e2
 순서 선택: e1 / e2
 0개 이상: e*
 1개 이상: e+
 선택적: e?
 And-predicate: &e
 Not-predicate: !e
 그룹: (e)
연산자 우선순위는의 표 1에 따라 다음과 같다:
 

 문법 
구체 구문에서 파싱 표현식 문법은 단순히 비단말 정의의 시퀀스이며, 각 정의는 다음 형식을 가진다:
 Identifier LEFTARROW Expression
Identifier는 정의되는 비단말이고, Expression은 이 비단말이 참조하도록 정의된 파싱 표현식이다. LEFTARROW는 방언에 따라 조금씩 다르지만, 일반적으로 <-, ←, :=, =와 같은 왼쪽 화살표 또는 할당 기호이다. 이를 이해하는 한 가지 방법은 비단말에 대한 할당 또는 정의를 만드는 것으로 정확히 이해하는 것이다. 다른 방법은 문맥 자유 문법의 규칙에서 사용되는 오른쪽 화살표 →와의 대비로 이해하는 것이다. 파싱 표현식에서는 정보의 흐름이 표현식에서 비단말로 가는 것이지, 비단말에서 표현식으로 가는 것이 아니다.

수학적 객체로서 파싱 표현식 문법은 튜플이며, 여기서 은 비단말 기호 집합, 는 단말 기호 집합, 는 에서 에 대한 파싱 표현식 집합으로의 함수, 그리고 는 시작 파싱 표현식이다. 일부 구체 구문 방언은 시작 표현식을 명시적으로 지정하지만, 주된 구체 구문은 대신 첫 번째로 정의된 비단말이 시작 표현식이라는 암묵적인 규칙을 가진다.

구체 구문 파싱 표현식 문법의 주된 방언에는 명시적인 정의 종결자나 정의 간의 구분자가 없다는 점에 주목할 필요가 있다. 새 정의를 새 줄에서 시작하는 것이 관례이지만, Expression 내의 비단말 뒤에 LEFTARROW가 오면 안 된다는 제약 조건을 추가하면 다음 정의의 LEFTARROW만으로 경계를 찾는 것으로 충분하다. 그러나 일부 방언은 명시적인 종결자를 허용하거나 명시적으로 요구할 수 있다.

 예시 
이것은 음이 아닌 정수에 다섯 가지 기본 연산을 적용하는 수학 공식을 인식하는 PEG이다.
Expr ← Sum
Sum ← Product (('+' / '-') Product)*
Product ← Power (('*' / '/') Power)*
Power ← Value ('^' Power)?
Value ← [0-9]+ / '(' Expr ')'
위 예에서 단말 기호는 '('와 ')'와 같이 홑따옴표 안의 문자로 표현된 텍스트 문자이다. 범위 [0-9]는 '0'부터 '9'까지의 10개 문자에 대한 약어이다. (이 범위 구문은 정규 표현식에서 사용되는 구문과 동일하다.) 비단말 기호는 다른 규칙으로 확장되는 것들이다: Value, Power, Product, Sum, Expr. Sum 및 Product 규칙은 이러한 연산에 대해 원하는 왼쪽 결합성을 제공하지 않으며(결합성을 전혀 처리하지 않으며, 구문 분석 후 후처리 단계에서 처리해야 함), Power 규칙(자신을 오른쪽에서 참조함으로써)은 원하는 지수 오른쪽 결합성을 제공한다. 또한, 와 같은 규칙(왼쪽 결합성을 달성하기 위한 의도)은 무한 재귀를 유발하므로 문법에서 표현할 수 있더라도 실제로는 사용할 수 없음에 유의하라.

 의미론 

문맥 자유 문법과 파싱 표현식 문법의 근본적인 차이점은 PEG의 선택 연산자가 순서화되어 있다는 것이다. 첫 번째 대안이 성공하면 두 번째 대안은 무시된다. 따라서 순서화된 선택은 문맥 자유 문법과 같은 비순서 선택과는 달리 교환적이지 않다. 순서화된 선택은 일부 논리형 프로그래밍 언어에서 사용 가능한 소프트 컷 연산자와 유사하다.

결과적으로 CFG가 PEG로 직접 변환되면, 이전의 모호성은 가능한 구문 분석 중 하나를 결정적으로 선택하여 해결된다. 문법 대안이 지정되는 순서를 신중하게 선택함으로써 프로그래머는 어떤 구문 분석 트리가 선택되는지에 대해 상당한 제어권을 가질 수 있다.

파싱 표현식 문법은 또한 and- 및 not- 구문 예측을 추가한다. 입력 문자열을 실제로 소비하지 않고 임의로 복잡한 하위 표현식을 사용하여 "미리보기"를 할 수 있기 때문에, 특히 대안을 재정렬하는 것으로는 원하는 정확한 구문 분석 트리를 지정할 수 없을 때 강력한 구문 미리보기 및 모호성 해소 기능을 제공한다.

 파싱 표현식의 운영적 해석 
파싱 표현식 문법의 각 비단말은 본질적으로 재귀 하향 파서의 파싱 함수를 나타내며, 해당 파싱 표현식은 함수를 구성하는 "코드"를 나타낸다. 각 파싱 함수는 개념적으로 입력 문자열을 인수로 받아 다음 결과 중 하나를 반환한다:
 성공: 함수가 선택적으로 앞으로 이동하거나 제공된 입력 문자열의 하나 이상의 문자를 소비할 수 있다. 또는
 실패: 이 경우 입력이 소비되지 않는다.

단일 단말(즉, 리터럴)로 구성된 원자 파싱 표현식은 입력 문자열의 첫 번째 문자가 해당 단말과 일치하는 경우 성공하며, 이 경우 입력 문자를 소비한다. 그렇지 않으면 표현식은 실패 결과를 반환한다. 빈 문자열로 구성된 원자 파싱 표현식은 항상 어떤 입력도 소비하지 않고 사소하게 성공한다.

비단말 A로 구성된 원자 파싱 표현식은 비단말 함수 A에 대한 재귀 호출을 나타낸다. 비단말은 실제로 어떤 입력도 소비하지 않고 성공할 수 있으며, 이는 실패와는 다른 결과로 간주된다.

시퀀스 연산자 e1 e2는 먼저 e1을 호출하고, e1이 성공하면 e1이 소비하지 않고 남은 입력 문자열의 나머지 부분에 대해 e2를 호출하고 결과를 반환한다. e1 또는 e2 중 하나라도 실패하면 시퀀스 표현식 e1 e2는 실패한다(입력을 소비하지 않음).

선택 연산자 e1 / e2는 먼저 e1을 호출하고, e1이 성공하면 즉시 결과를 반환한다. 그렇지 않고 e1이 실패하면 선택 연산자는 e1을 호출했던 원래 입력 위치로 퇴각검색하지만, 대신 e2를 호출하여 e2의 결과를 반환한다.

0개 이상, 1개 이상, 선택적 연산자는 각각 하위 표현식 e의 0개 이상, 1개 이상, 0개 또는 1개의 연속된 반복을 소비한다. 그러나 문맥 자유 문법 및 정규 표현식과는 달리, 이 연산자들은 항상 탐욕적으로 작동하여 가능한 한 많은 입력을 소비하며 절대 퇴각검색하지 않는다. (정규 표현식 매처는 탐욕적으로 일치시키려 시도하지만, 일치에 실패하면 퇴각검색하여 더 짧은 일치를 시도할 수 있다.) 예를 들어, 표현식 a*는 입력 문자열에서 연속적으로 사용 가능한 가능한 한 많은 a를 항상 소비하며, 표현식 (a* a)는 첫 번째 부분(a*)이 두 번째 부분이 일치할 a를 전혀 남기지 않기 때문에 항상 실패한다.

and-predicate 표현식 &e는 하위 표현식 e를 호출하고, e가 성공하면 성공하고 e가 실패하면 실패하지만, 어떤 경우에도 입력을 소비하지 않는다.

not-predicate 표현식 !e는 e가 실패하면 성공하고 e가 성공하면 실패하며, 어떤 경우에도 입력을 소비하지 않는다.

 더 많은 예시 
다음 재귀 규칙은 선택적 "else" 절이 항상 가장 안쪽의 "if"에 바인딩되도록 표준 C 스타일 if/then/else 문을 일치시킨다. 이는 '/' 연산자의 암시적 우선순위 때문이다. (문맥 자유 문법에서 이 구문은 고전적인 매달린 else 모호성을 발생시킨다.)
S ← 'if' C 'then' S 'else' S / 'if' C 'then' S

다음 재귀 규칙은 파스칼 스타일의 중첩 주석 구문인 와 일치한다. 가 임의의 단일 문자와 일치한다는 것을 기억하라.
C ← Begin N* End
Begin ← '(*'
End ← '*)'
N ← C / (!Begin !End .)

파싱 표현식 는 "foo" 텍스트와 일치하고 소비하지만, 그 뒤에 "bar" 텍스트가 오는 경우에만 그렇다. 파싱 표현식 는 "foo" 텍스트와 일치하지만, 그 뒤에 "bar" 텍스트가 오지 않는 경우에만 그렇다. 표현식 는 단일 "a"와 일치하지만, 임의로 긴 a 시퀀스 뒤에 b가 오는 시퀀스의 일부가 아닌 경우에만 그렇다.

파싱 표현식 는 임의 길이의 a와 b 시퀀스와 일치하고 소비한다. 생성 규칙 는 간단한 문맥 자유 "매칭 언어" 를 설명한다.
다음 파싱 표현식 문법은 고전적인 비문맥 자유 언어 를 설명한다:
S ← &(A 'c') 'a'+ B !.
A ← 'a' A? 'b'
B ← 'b' B? 'c'

 파싱 표현식 문법으로 파서 구현하기 
모든 파싱 표현식 문법은 직접적으로 재귀 하향 파서로 변환될 수 있다. 그러나 문법 형식론이 제공하는 무제한 미리보기 기능 때문에 결과 파서는 최악의 경우 지수 시간 성능을 보일 수 있다.

어떤 파싱 표현식 문법이라도 팩랫 파서로 변환하여 더 나은 성능을 얻을 수 있다. 팩랫 파서는 항상 선형 시간으로 실행되지만, 훨씬 더 많은 저장 공간을 필요로 한다. 팩랫 파서는 구조적으로 재귀 하향 파서와 유사한 파서의 한 형태이다. 단, 파싱 과정에서 메모이제이션을 통해 모든 상호 재귀 파싱 함수의 중간 결과를 메모이제이션하여 각 파싱 함수가 주어진 입력 위치에서 최대 한 번만 호출되도록 한다. 이러한 메모이제이션 덕분에 팩랫 파서는 많은 문맥 자유 문법과 모든 파싱 표현식 문법(문맥 자유 언어를 나타내지 않는 일부 문법 포함)을 선형 시간에 파싱할 수 있다. 메모이제이션된 재귀 하향 파서의 예는 적어도 1993년부터 알려져 있다.
팩랫 파서의 성능 분석은 모든 메모이제이션된 결과를 저장할 충분한 메모리가 있다고 가정한다. 실제로는 메모리가 부족하면 일부 파싱 함수가 동일한 입력 위치에서 두 번 이상 호출될 수 있으며, 결과적으로 파서가 선형 시간보다 더 많은 시간을 소요할 수 있다.

LL 파서 및 LR 파서도 파싱 표현식 문법에서 구축할 수 있으며, 메모이제이션 없는 재귀 하향 파서보다 최악의 경우 성능이 더 좋다. 그러나 문법 형식론의 무제한 미리보기 기능은 이때 손실된다. 따라서 파싱 표현식 문법을 사용하여 표현할 수 있는 모든 언어가 LL 또는 LR 파서로 파싱될 수 있는 것은 아니다.

 상향식 PEG 파싱 

피카 파서(pika parser)는 동적 계획법을 사용하여 PEG 규칙을 상향식 및 오른쪽에서 왼쪽으로 적용한다. 이는 일반적인 재귀 하향식 및 왼쪽에서 오른쪽 파싱 순서의 역이다. 역순으로 파싱하면 좌측 재귀 문제를 해결하여 좌측 재귀 규칙을 문법에 직접 사용할 수 있도록 하며, 구문 분석기에 최적의 오류 복구 기능을 부여한다. 이는 역사적으로 재귀 하향 파서에게 달성하기 어려웠던 것이다.

 장점 
 컴파일 불필요 
많은 구문 분석 알고리즘은 문법이 먼저 불투명한 실행 가능한 형태로, 종종 어떤 종류의 자동자로 컴파일되는 전처리 단계를 필요로 한다. 파싱 표현식은 직접 실행될 수 있다(이 문서에 표시된 인간이 읽을 수 있는 PEG를 평가하기 전에 S-표현식과 같은 더 기본 형식으로 변환하는 것이 일반적으로 여전히 권장되더라도).

 정규 표현식과의 비교 
순수한 정규 표현식(즉, 유한 자동자를 사용하여 인식할 수 있는 언어를 설명하는 것)과 비교할 때 PEG는 훨씬 더 강력하다. 특히 PEG는 무제한 재귀를 처리할 수 있으므로 임의의 중첩 깊이까지 괄호를 일치시킨다. 정규 표현식은 기껏해야 고정된 깊이까지의 중첩을 추적할 수 있는데, 이는 유한 자동자(유한한 내부 상태 집합을 가짐)가 유한한 수의 다른 중첩 깊이만을 구별할 수 있기 때문이다. 더 이론적인 용어로, (0개 이상의 다음에 동일한 수의 가 오는 모든 문자열의 언어)는 정규 언어가 아니지만, 다음 문법으로 쉽게 파싱 표현식 언어임을 알 수 있다.

start ← AB !.
AB ← ('a' AB 'b')?

여기서 AB !.는 시작 표현식이다. !. 부분은 "다음 문자가 없다"고 말함으로써 AB 다음에 입력이 끝남을 강제한다. 이를 위한 마법 제약 조건인 $ 또는 \Z가 있는 정규 표현식과 달리 파싱 표현식은 기본 원시 자료형만을 사용하여 입력의 끝을 표현할 수 있다.

파싱 표현식의 *, +, ?는 정규 표현식의 그것들과 유사하지만, 차이점은 이들이 엄격히 탐욕 모드로 작동한다는 것이다. 이는 궁극적으로 /가 순서 선택이기 때문이다. 결과적으로 정규 표현식으로는 일치하지만 파싱 표현식으로는 일치하지 않는 것이 있을 수 있다:
 [ab]?[bc][cd]
는 유효한 정규 표현식이자 유효한 파싱 표현식이다. 정규 표현식으로서는 bc와 일치하지만, 파싱 표현식으로서는 일치하지 않는다. 왜냐하면 [ab]?가 b와 일치하고, 그 다음 [bc]가 c와 일치하여 [cd]에 아무것도 남기지 않아, 그 지점에서 시퀀스 일치가 실패하기 때문이다. [ab]?가 빈 문자열과 일치하도록 "다시 시도"하는 것은 파싱 표현식의 의미론에 명시적으로 위배된다. 이것은 특정 일치 알고리즘의 예외적인 경우가 아니라, 추구하는 동작이다.

비결정론에 의존하는 정규 표현식조차도 해당 DFA의 모든 상태에 대해 별도의 비단말을 가지고 해당 전이 함수를 비단말의 정의로 인코딩함으로써 파싱 표현식 문법으로 컴파일될 수 있다.
A ← 'x' B / 'y' C
는 사실상 "상태 A에서 다음 문자가 x이면 상태 B로 전이하고, 다음 문자가 y이면 상태 C로 전이한다"고 말하는 것이다. 그러나 이것은 비결정론이 정규 언어의 영역 내에서 제거될 수 있기 때문에 작동한다. 이는 반복 연산의 파싱 표현식 변형을 사용하지 않을 것이다.

 문맥 자유 문법과의 비교 

PEG는 문자를 사용하여 편안하게 표현할 수 있지만, 문맥 자유 문법(CFG)은 보통 토큰을 사용하여 표현하므로 적절한 파싱 앞에 추가적인 토큰화 단계가 필요하다. 별도의 토큰화기가 없는 장점은 언어의 다른 부분(예: 내장된 미니 언어)이 쉽게 다른 토큰화 규칙을 가질 수 있다는 것이다.

엄격한 형식적 의미에서 PEG는 CFG와 비교할 수 없을 가능성이 높지만, 실제로는 순수 CFG가 할 수 없는 많은 것들을 PEG가 할 수 있는 반면, 그 반대의 예시를 찾기는 어렵다. 특히 PEG는 C, C++, Java의 "dangling else" 문제와 같은 모호성을 자연스럽게 해결하도록 만들 수 있는 반면, CFG 기반 파싱은 종종 문법 외부의 규칙을 사용하여 이를 해결해야 한다. 또한 어떤 PEG든 위에 설명된 팩랫 파서를 사용하면 선형 시간으로 파싱할 수 있는 반면, 일반 CFG에 따른 파싱은 이진 행렬 곱셈과 점근적으로 동일하다는 것이 입증되었다(따라서 이차 또는 삼차 시간 사이일 가능성이 높다).

명백히 문맥 자유가 아닌 형식 언어의 고전적인 예시 중 하나는 언어이다. 즉, 임의의 수의 다음에 동일한 수의 가 오고, 그 다음에 동일한 수의 가 오는 언어이다. 이것 또한 다음 문법으로 일치되는 파싱 표현식 언어이다.

start ← AB 'c'*
AB ← 'a' AB 'b' / &(BC !.)
BC ← ('b' BC 'c')?

AB가 일치하려면, 첫 번째 의 연속 부분 뒤에 동일한 수의 가 와야 하며, 추가로 가 로 바뀌는 곳에서 BC가 일치해야 한다. 이는 해당 들 뒤에 동일한 수의 가 온다는 것을 의미한다.

 단점 

 메모리 소비 
PEG 파싱은 일반적으로 팩랫 파싱을 통해 수행되며, 이는 중복 파싱 단계를 제거하기 위해 메모이제이션을 사용한다. 팩랫 파싱은 LR 파서와 같이 파스 트리의 깊이에 비례하는 대신 전체 입력 크기에 비례하는 내부 스토리지를 필요로 한다. 이것이 중요한 차이인지 여부는 상황에 따라 달라진다. 파싱이 함수로 제공되는 서비스인 경우, 파서는 반환하기 전까지 전체 파스 트리를 저장했을 것이고, 이미 그 파스 트리는 일반적으로 전체 입력 크기에 비례하는 크기를 가질 것이다. 파싱이 대신 제너레이터로 제공되는 경우 파스 트리의 일부만 메모리에 유지할 수 있지만, 이것의 타당성은 문법에 따라 달라진다. 파싱 표현식 문법은 전체 입력을 소비한 후에야 파서가 시작 부분으로 퇴각검색해야 함을 발견하도록 설계될 수 있으며, 이는 다시 전체 입력 크기에 비례하는 스토리지를 필요로 할 수 있다.

재귀 문법과 일부 입력의 경우, 파스 트리의 깊이가 입력 크기에 비례할 수 있으므로, LR 파서와 팩랫 파서 모두 동일한 최악의 경우 점근적 성능을 가지는 것으로 보인다. 그러나 많은 도메인, 예를 들어 수기로 작성된 소스 코드에서는 표현식 중첩 깊이가 프로그램 길이에 관계없이 효과적으로 일정한 한계를 가지는데, 특정 깊이 이상으로 중첩된 표현식은 리팩터링되는 경향이 있기 때문이다. 전체 파스 트리를 유지할 필요가 없을 때, 더 정확한 분석은 입력 크기와 별도로 파스 트리의 깊이를 고려할 것이다.

 계산 모델 
선형적 전체 복잡성을 달성하기 위해서는 메모이제이션에 사용되는 저장 공간이 개별 메모이제이션된 데이터 항목에 대한 분할 상환 상수 시간 접근을 제공해야 한다. 실제로는 문제가 되지 않는다. 예를 들어 동적으로 크기가 조정되는 해시 테이블이 이를 달성한다. 하지만 이는 포인터 산술을 사용하므로, 랜덤 접근 기계를 전제한다. 데이터 구조와 알고리즘에 대한 이론적 논의는 더 제한적인 모델(아마도 람다 대수 또는 스킴의 모델)을 전제하는 경향이 있는데, 여기서 희소 테이블은 트리로 구축되어야 하며 데이터 항목 접근은 상수 시간이 아니다. LL 파서와 같은 전통적인 파싱 알고리즘은 이에 영향을 받지 않지만, 팩랫 파서의 평판에 불이익이 된다: 팩랫 파서는 겉보기에 평판이 좋지 않은 연산에 의존한다.

반대로 보면, 이는 팩랫 파서가 실제 시스템에서 쉽게 사용할 수 있는 계산 능력을 활용하며, 오래된 파싱 알고리즘은 이를 활용하는 방법을 알지 못했다는 것을 의미한다.

 간접 좌측 재귀 

PEG는 좌측 재귀 규칙, 즉 비단말이 동일한 비단말이 가장 왼쪽에 있는 기호로 나타나는 표현식으로 확장될 수 있는 규칙을 포함하지 않으면 잘 형성되었다고 한다. 좌측에서 우측으로의 하향식 파서의 경우, 이러한 규칙은 무한 회귀를 야기한다. 즉, 파싱은 문자열에서 앞으로 나아가지 않고 동일한 비단말을 계속 확장할 것이다. 따라서 팩랫 파싱을 허용하려면 좌측 재귀를 제거해야 한다.

 실제적 중요성 
좌측 또는 우측이든 직접 재귀는 문맥 자유 문법에서 중요하다. 왜냐하면 재귀가 반복을 설명하는 유일한 방법이기 때문이다.
Sum → Term | Sum '+' Term | Sum '-' Term
Args → Arg | Arg ',' Args
문맥 자유 문법 사용에 익숙한 사람들은 종종 동일한 관용구를 사용하기 위해 PEG를 기대하지만, 파싱 표현식은 재귀 없이 반복을 수행할 수 있다.
Sum ← Term ( '+' Term / '-' Term )*
Args ← Arg ( ',' Arg )*
차이점은 생성되는 추상 구문 트리에 있다. 재귀를 사용하면 각 Sum 또는 Args가 최대 두 개의 자식을 가질 수 있지만, 반복을 사용하면 임의의 많은 자식을 가질 수 있다. 예를 들어 마이크로프로세서의 덧셈 명령어는 일반적으로 두 개의 피연산자만 허용하므로, 후속 처리 단계에서 이러한 자식 목록을 유한 차수를 가진 트리로 재구성해야 하는 경우, 좌측 결합성과 같은 속성은 PEG 지향 파싱 단계 이후에 부여될 것이다.

따라서 좌측 재귀는 문맥 자유 관용구를 고집하지 않는 한 LL(k) 문맥 자유 파서보다 PEG 팩랫 파서에 문제를 일으킬 가능성이 실제로는 적다. 그러나 모든 재귀의 경우가 반복에 관한 것은 아니다.

 비반복 좌측 재귀 

예를 들어, 위 산술 문법에서 연산자 우선순위를 순서 선택으로 표현하려는 유혹이 있을 수 있다. — Sum / Product / Value는 먼저 Sum으로 보려고 시도하고(하향식으로 파싱하므로), 두 번째로 Product로 보려고 시도하고, 세 번째로 Value로 보려고 시도한다는 의미이다. — 이는 정의의 중첩을 통하는 것보다 더 간단하다. 이 (잘못 형성된) 문법은 우선순위 순서를 한 줄에만 유지하려고 한다.

Value ← [0-9.]+ / '(' Expr ')'
Product ← Expr (('*' / '/') Expr)+
Sum ← Expr (('+' / '-') Expr)+
Expr ← Sum / Product / Value

불행히도 Expr을 일치시키려면 Sum이 일치하는지 테스트해야 하고, Sum을 일치시키려면 Expr이 일치하는지 테스트해야 한다. 이 항이 가장 왼쪽에 나타나기 때문에 이러한 규칙들은 해결할 수 없는 순환 정의를 이룬다. (원래 첫 번째 예시의 공식화처럼 해결될 수 있는 순환 정의도 존재하지만, 그러한 정의는 병리적 재귀를 보이지 않아야 한다.) 그러나 좌측 재귀 규칙은 항상 좌측 재귀를 제거하도록 다시 작성될 수 있다. 예를 들어, 다음 좌측 재귀 CFG 규칙:
string-of-a ← string-of-a 'a' | 'a'

는 플러스 연산자를 사용하여 PEG로 다시 작성될 수 있다.
string-of-a ← 'a'+

간접 좌측 재귀 규칙을 다시 작성하는 과정은 일부 팩랫 파서에서 복잡하며, 특히 의미론적 동작이 관련될 때 더욱 그렇다.

일부 수정으로 전통적인 팩랫 파싱은 직접 좌측 재귀를 지원할 수 있지만, 그렇게 하면 선형 시간 파싱 속성이 손실된다. 이는 원래 PEG 및 팩랫 파싱을 사용하는 정당성이다. 오직 OMeta 파싱 알고리즘만이 추가 복잡성 없이 완전한 직접 및 간접 좌측 재귀를 지원하며(다시 말하지만, 선형 시간 복잡성은 손실된다), 모든 GLR 파서들은 좌측 재귀를 지원한다.

 예상치 못한 동작 
PEG에 대한 흔한 첫인상은 정규 표현식과 같은 반복 연산자 *+?와 미리보기 조건자 &!와 같은 특정 편의 기능과 모호성 해결을 위한 순서 선택을 가진 CFG처럼 보인다는 것이다. 이러한 이해는 언어 파서를 만들려는 목표를 가질 때 충분할 수 있지만, 파싱 표현식의 계산 능력에 대한 더 이론적인 논의에는 충분하지 않다. 특히 문맥 자유 문법의 비순서 선택 |에 내재된 비결정론은 결정론적 순서 선택 /와 매우 다르다.

 중간 지점 문제 

PEG 팩랫 파서는 다음과 같은 모호하지 않은 비결정적 CFG 규칙을 인식할 수 없다.
S ← 'x' S 'x' | 'x'
LL(k) 및 LR(k) 파싱 알고리즘 모두 이 예시를 인식할 수 없다. 그러나 이 문법은 CYK 알고리즘과 같은 일반 CFG 파서에서 사용될 수 있다. 그럼에도 불구하고, 이 문제의 언어는 실제로 정규 언어(홀수 개의 x 문자열)이므로 이러한 모든 종류의 파서에서 인식될 수 있다.

PEG 파서가 xxxxxq 문자열에 대해
S ← 'x' S 'x' / 'x'
를 일치시키려고 시도할 때 정확히 어떤 일이 발생하는지 살펴보는 것은 유익하다. 예상대로, q에 대한 일치에 실패할 때까지 문자열의 증가하는 위치에서 비단말 S를 재귀적으로 일치시키려고 시도하며, 그 후 퇴각검색을 시작한다. 과정은 다음과 같다:
 위치: 123456
 문자열: xxxxxq
 결과: ↑ 위치 6: S의 어떤 분기도 일치하지 않음
 ↑ 위치 5: S의 첫 번째 분기 실패, 두 번째 분기 성공, 길이 1 일치 결과.
 ↑ 위치 4: S의 첫 번째 분기 실패, 두 번째 분기 성공, 길이 1 일치 결과.
 ↑ 위치 3: S의 첫 번째 분기 성공, 길이 3 일치 결과.
 ↑ 위치 2: S의 첫 번째 분기 실패, 3에서의 S 일치 후 q가 오기 때문.
 두 번째 분기 성공, 길이 1 일치 결과.
 ↑ 위치 1: S의 첫 번째 분기 성공, 길이 3 일치 결과.
파싱 표현식에 대한 일치는 탐욕적이다. 즉, 발견된 첫 번째 성공만이 고려된다. 비록 지역적으로 선택이 가장 긴 것을 먼저 하도록 순서가 지정되어 있더라도, 이 탐욕적인 일치가 전역적으로 가장 긴 일치를 찾을 것이라는 보장은 없다.

 모호성 감지 및 규칙 순서가 일치하는 언어에 미치는 영향 
LL(k) 및 LR(k) 파서 생성기는 입력 문법이 모호하면 완료되지 않는다. 이는 문법이 모호하지 않아야 하지만 결함이 있는 일반적인 경우에 유용한 기능이다. PEG 파서 생성기는 의도하지 않은 모호성을 가장 먼저 일치하는 것으로 해결하며, 이는 임의적일 수 있고 예상치 못한 구문 분석으로 이어질 수 있다.

PEG 문법에서 생성의 순서는 모호성 해결뿐만 아니라 일치하는 언어에도 영향을 미친다. 예를 들어, 포드(Ford)의 논문에 있는 첫 번째 PEG 예시(pegjs.org/online 표기법으로 다시 작성하고 및 로 레이블링함)를 고려하라:

 :  
 :  

포드는 후자의 PEG 규칙에서 두 번째 대안은 입력 문자열이 'a'로 시작하면 첫 번째 선택이 항상 이루어지기 때문에 결코 성공하지 못한다고 언급한다.
구체적으로, (즉, 과 일치하는 언어)는 입력 "ab"를 포함하지만, 는 포함하지 않는다.
따라서 PEG 문법에 새로운 옵션을 추가하면 일치하는 언어에서 문자열을 제거할 수 있다. 예를 들어, 는 에 의해 일치되지 않는 문자열을 포함하는 단일 생성 문법 에 규칙을 추가한 것이다.
더욱이 PEG 문법 과 로부터 와 일치하는 문법을 구성하는 것은 항상 사소한 작업이 아니다.
이는 새로운 생성이 문자열을 제거할 수 없는 CFG와는 극명한 대조를 이룬다(모호성 형태로 문제를 도입할 수는 있지만),
그리고 에 대한 (잠재적으로 모호한) 문법은 다음과 같이 구성될 수 있다.
S → start(G1) | start(G2)

 파싱 표현식 문법 이론 
파싱 표현식 문법으로 인식할 수 없는 문맥 자유 언어의 구체적인 예시를 제시하는 것은 미해결 문제이다. 특히, 파싱 표현식 문법이 회문 언어를 인식할 수 있는지 여부는 미해결이다.

파싱 표현식 언어 클래스는 집합 교차 및 여집합에 대해 닫혀 있으며, 따라서 집합 합집합에 대해서도 닫혀 있다.

 공백성 결정 불가능 
문맥 자유 문법의 경우와는 극명한 대조를 이루게도, 파싱 표현식 문법으로부터 파싱 표현식 언어의 요소를 생성하는 것은 불가능하다. 실제로, 파싱 표현식 문법에 의해 인식되는 언어가 비어있는지 여부를 알고리즘적으로 결정하는 것은 불가능하다! 이에 대한 한 가지 이유는 포스트 대응 문제의 모든 인스턴스가 파싱 표현식 언어가 비어있는지 결정하는 문제의 인스턴스로 환원되기 때문이다.

포스트 대응 문제의 인스턴스는 문자열(단말 기호) 쌍의 목록 으로 구성된다는 것을 상기하라. 문제는 범위의 인덱스 시퀀스 가 존재하여 을 만족하는지 결정하는 것이다. 이것을 파싱 표현식 문법으로 환원하려면, 을 임의의 서로 다른 동일한 길이의 단말 기호 문자열로 두고(이미 2개의 다른 기호가 단말 기호 알파벳에 있으면, 길이가 충분하다) 다음 파싱 표현식 문법을 고려하라.

비단말 에 의해 일치되는 모든 문자열은 일부 인덱스 에 대해 형식을 가진다. 마찬가지로 비단말 에 의해 일치되는 모든 문자열은 형식을 가진다. 따라서 에 의해 일치되는 모든 문자열은 인 형식을 가질 것이다.

 실제 사용 
 파이썬 참조 구현인 C파이썬은 2020년 3.9 버전부터 PEG 파서를 도입했고, 3.10 버전부터는 PEG만 사용한다.

 jq 프로그래밍 언어는 PEG와 밀접한 관련이 있는 형식론을 사용한다.

 루아 개발자들은 정규 표현식 대신 PEG를 사용하는 패턴 일치 라이브러리 LPeg를 만들었으며, LPeg 라이브러리를 활용하여 정규 표현식과 유사한 구문을 구현하는 re 모듈도 만들었다.

 같이 보기 
 불린 문맥 자유 문법
 컴파일러 서술 언어 (CDL)
 형식 문법
 정규 표현식
 하향식 구문 분석 언어
 파서 생성기 비교
 파서 조합기

 각주 

 외부 링크 
 문자열 표현식을 표현식 파서로 람다 표현식으로 변환하기
 팩랫 파싱 및 파싱 표현식 문법 페이지
 인공어 로지반은 로지반 텍스트의 모호하지 않은 파싱을 허용하는 상당히 큰 PEG 문법을 가지고 있다.
 Guile Scheme에서 PEG의 예시적 구현

분류:형식 언어