구문 분석식 문법

컴퓨터 과학에서, 구문 분석 표현 문법(PEG)은 분석 형식 문법의 일종이다. 즉, 언어의 문자열을 인식하기 위한 규칙 집합의 관점에서 형식 언어를 기술한다.형식주의는 Bryan Ford에 의해 2004년에^[1] 도입되었으며 1970년대 초에 도입된 하향식 구문 분석 언어 패밀리와 밀접한 관련이 있습니다.구문론적으로 PEG는 Context-Free Grammar(CFG; 컨텍스트프리그래머)와 비슷해 보이지만 다른 해석은 선택 연산자가 PEG에서 첫 번째 일치를 선택하는 반면 CFG에서는 애매하다는 것입니다.이것은 예를 들어 재귀 강하 파서에 의해 실제로 문자열 인식이 이루어지는 방식에 가깝다.

CFG와 달리 PEG는 애매할 수 없습니다.문자열이 해석되면 유효한 해석 트리가 1개만 남습니다.PEG에 의해 인식되지 않는 문맥이 없는 언어가 존재할 것으로 추측되지만,^[1] 이는 아직 증명되지 않았다.PEG는 컴퓨터 언어(및 Lojban과 같은 인공 인간 언어)의 해석에는 적합하지만, PEG 알고리즘의 성능이 Earley ^[2]알고리즘과 같은 일반적인 CFG 알고리즘에 필적하는 자연 언어는 아닙니다.

정의.

구문

정식으로 해석식 문법은 다음과 같이 구성됩니다.

비단말기 심볼의 유한 집합 N.
N에서 분리된 단자 심볼의 유한 집합 δ.
해석 규칙의 유한 집합 P.
시작 표현이라고 하는 표현_S.

P의 각 구문 분석 규칙은 A ← e 형식입니다. 여기서 A는 비말단 기호이고 e는 구문 분석 식입니다.해석식은 정규 표현과 유사한 계층 표현으로 다음과 같이 구성됩니다.

원자 해석식은 다음과 같이 구성됩니다.
- 임의의 단자 기호,
- 임의의 비말단 기호 또는
- 빈 문자열 ε.
기존 해석식 e, e₁ 및₂ e를 지정하면 다음 연산자를 사용하여 새로운 해석식을 구성할 수 있습니다.
- 시퀀스: e₁ e₂
- 순서선택: e₁/e₂
- 제로 이상: e*
- 1개 이상: e+
- 옵션: e?
- And-predicate:&e
- 증명되지 않음: !e

의미론

문맥이 없는 문법과 구문 분석 표현 문법의 근본적인 차이점은 PEG의 선택 연산자가 정렬된다는 것입니다.첫 번째 대안이 성공하면 두 번째 대안이 무시됩니다.따라서 순서 선택은 문맥이 없는 문법에서와 같이 순서 없는 선택과는 달리 가환적이지 않다.순서 선택은 일부 로직 프로그래밍 언어에서 사용할 수 있는 소프트 컷 연산자와 유사합니다.

그 결과 CFG가 PEG로 직접 변환되면 가능한 구문 분석에서1개의 해석 트리를 결정적으로 선택함으로써 전자의 모호성이 해결됩니다.프로그래머는 문법대안을 지정하는 순서를 신중하게 선택함으로써 어느 파싱 트리가 선택되는지에 대해 많은 제어를 할 수 있다.

부울 문맥이 없는 문법과 마찬가지로 구문 분석 표현 문법은 구문 술어와 구문 술어를 추가합니다.임의의 복잡한 서브 표현식을 사용하여 입력 문자열을 실제로 소비하지 않고 "앞을 내다볼" 수 있기 때문에 특히 대체 순서를 변경할 때 원하는 정확한 해석 트리를 지정할 수 없는 경우 강력한 구문 검색 및 모호성 제거 기능을 제공합니다.

구문 분석식의 연산 해석

구문해석식 문법의 각 비말단은 기본적으로 재귀적 강하 파서의 구문해석 함수를 나타내고, 대응하는 구문해석식은 해당 함수를 포함하는 "코드"를 나타낸다.각 해석 함수는 개념적으로 입력 문자열을 인수로 사용하여 다음 중 하나의 결과를 생성합니다.

success: 함수가 임의로 앞으로 이동하거나 함수에 제공된 입력 문자열의 하나 이상의 문자를 소비할 수 있습니다.
이 경우 입력이 소비되지 않습니다.

단일 단말(즉 리터럴)로 구성된 원자 해석식은 입력 문자열의 첫 번째 문자가 해당 단말기와 일치하고 이 경우 입력 문자를 소비하면 성공합니다.그렇지 않으면 식이 실패 결과를 낳습니다.빈 문자열로 구성된 원자 구문 분석식은 입력을 소비하지 않고 항상 성공합니다.

비단말기 A로 이루어진 원자 해석식은 비단말기 함수 A에 대한 재귀 호출을 나타낸다.비단말기는 실제로 입력을 소비하지 않고 성공할 수 있으며 이는 장애와는 다른 결과로 간주됩니다.

시퀀스 연산자₁ e는₂ 처음에 e를 호출하고₁ e가 성공하면₁ e에 의해₁ 소비되지 않은 나머지 입력 문자열에 대해 e를₂ 호출하여 결과를 반환합니다.e 또는₂ e 중 하나가₁ 실패하면 시퀀스식₁ e는₂ 실패합니다(입력하지 않습니다).

선택 연산자₁ e/e는₂ 먼저 e를 호출하고₁ e가 성공하면 결과를₁ 즉시 반환합니다.그렇지 않으면 e가 실패하면₁ 선택 연산자는 e를 호출한₁ 원래 입력 위치로 역추적하지만 e를 호출하여₂ e의 결과를 반환합니다₂.

0 이상, 1 이상 및 옵션 연산자는 각각 하위 표현식 e의 0 이상, 1 이상 또는 0 또는1회 연속 반복을 소비합니다.그러나 문맥이 없는 문법이나 정규 표현과는 달리 이러한 연산자는 항상 탐욕스럽게 행동하고 가능한 한 많은 입력을 소비하며 역추적을 하지 않습니다(정규 표현 매칭자는 탐욕스럽게 매칭하는 것으로 시작할 수 있지만 일치하지 않으면 역추적하여 더 짧은 매칭을 시도합니다).예를 들어 식 a*는 항상 입력 문자열에서 연속적으로 사용 가능한 수만큼 a를 소비하며 식 a*a는 항상 실패합니다.이는 첫 번째 부분 a*는 두 번째 부분이 일치하도록 a를 남기지 않기 때문입니다.

and-predicate 식&e는 서브식 e를 호출하고 e가 성공하면 성공하고 e가 실패하면 실패하지만 어느 경우든 입력을 소비하지 않습니다.

not-predicate 표현식 !e는 e가 실패하면 성공하고 e가 성공하면 실패하며 어느 경우에도 입력은 소비되지 않습니다.

예

이것은 음이 아닌 정수에 기본 5개의 연산을 적용하는 수학 공식을 인식하는 PEG입니다.

익스프레르    ← 합 합     ← 제품. (('+' / '-') 제품.)* 제품. ← 힘 (('*' / '/') 힘)* 힘   ← 가치 ('^' 힘)? 가치   ← [0-9]+ / '(' 익스프레르 ')'

위의 예에서 터미널 기호는 텍스트의 문자로, 다음과 같이 작은 따옴표로 표시됩니다.'('그리고.')'범위[0-9]는 숫자 0 ~9 중 하나를 나타내는10 문자의 단축키이기도 합니다(이 범위 구문은 정규 표현에서 사용되는 구문과 동일합니다).nonterminal 기호는 Value, Power, Product, Sum 및 Expr 등의 다른 규칙으로 확장되는 기호입니다.Sum 규칙과 Product 규칙은 이러한 연산의 바람직한 왼쪽 연관성으로 이어지지 않으며(이 규칙은 전혀 관련성을 다루지 않으며 해석 후 처리 단계에서 처리되어야 함), Power 규칙(오른쪽 자체 참조)은 지수의 바람직한 오른쪽 연관성으로 이어집니다.또한 다음과 같은 규칙이 있습니다.Sum ← Sum (('+' / '-') Product)?(좌측 연관성을 달성하려는 의도로) 무한 재귀가 발생하므로 문법적으로 표현할 수 있더라도 실제로는 사용할 수 없습니다.

다음 재귀 규칙은 '/' 연산자의 암묵적 우선 순위 때문에 옵션인 "else" 절이 항상 가장 안쪽의 "if"에 바인딩되도록 표준 C 스타일 if/then/else 문과 일치합니다.(문맥이 없는 문법에서 이 구문은 전형적인 달링, 그렇지 않으면 애매모호함을 만들어 냅니다.

S ← '만약에' C '그럼' S '실패' S / '만약에' C '그럼' S

다음 재귀 규칙은 Pascal 스타일의 중첩 주석 구문과 일치합니다.(* which can (* nest *) like this *)코멘트 기호는 PEG 연산자와 구별하기 위해 작은 따옴표로 둘러싸여 있습니다.

시작한다. ← '(*' 끝.   ← '*)' C     ← 시작한다. N* 끝. N     ← C / (!시작한다. !끝. Z) Z     ← 조금도 싱글 성격

해석식foo &(bar)는 "foo"라는 텍스트와 일치하고 그 뒤에 "bar"라는 텍스트가 이어지는 경우에만 사용합니다.해석식foo !(bar)는 "foo" 텍스트와 일치하지만 뒤에 "bar" 텍스트가 없는 경우에만 일치합니다.표현!(a+ b) a는 단일 "a"와 일치하지만 임의로 긴a의 시퀀스 뒤에 b가 이어지는 경우에 한해 일치합니다.

해석식('a'/'b')*는 a와 b의 임의의 길이의 시퀀스와 일치하여 소비합니다.생산 규칙 S ← 'a' ''S''? 'b'에, 콘텍스트가 필요 없는 심플한 「표준어 $\{a^{n}b^{n}:n\geq 1\}$ $\{a^{n}b^{n}:n\geq 1\}$ $\{a^{n}b^{n}:n\geq 1\}$ $\{a^{n}b^{n}:n\geq 1\}$ : n $\{a^{n}b^{n}:n\geq 1\}$ 1 $}{$ $displaystyle$ \ { $a^{n}b^{n}:n\geq$ 1 $\{a^{n}b^{n}:n\geq 1\}$ 에 대해 설명합니다.다음 구문해석식 문법은 문맥이 없는 고전적인 언어 $\{a^{n}b^{n}c^{n}:n\geq 1\}$ $\{a^{n}b^{n}c^{n}:n\geq 1\}$ $\{a^{n}b^{n}c^{n}:n\geq 1\}$ $\{a^{n}b^{n}c^{n}:n\geq 1\}$ : n $\{a^{n}b^{n}c^{n}:n\geq 1\}$ 1 $\{a^{n}b^{n}c^{n}:n\geq 1\}$ } { $displaystyle$ \ { $a^{n}$ $b^{n}$ c^{ $n}$ : n\ $geq$ 1 $\{a^{n}b^{n}c^{n}:n\geq 1\}$ 에 대해 설명합니다.

S ← &(A 'c') 'a'+ B !. A ← 'a' A? 'b' B ← 'b' B? 'c'

표현식 문법의 구문 분석에서 파서를 구현하는 중

구문 분석식 문법은 재귀 강하 ^[3]파서로 직접 변환할 수 있습니다.그러나 문법 형식주의가 제공하는 무제한 예측 기능으로 인해 최악의 경우 결과 파서가 기하급수적인 시간 성능을 나타낼 수 있습니다.

재귀적 하강 파서를 packrat 파서로 변환하면 구문 분석식 문법에 대해 더 나은 성능을 얻을 수 있습니다. 이 파서는 저장 공간 요구 사항이 상당히 커지지만 항상 선형 시간으로 실행됩니다.packrat 파서는^[3] 구조상 재귀 하강 파서와 유사한 파서의 한 형태입니다.단, 파싱 프로세스 중에 상호 재귀 파싱 함수의 모든 호출의 중간 결과를 메모하여 각 파싱 함수가 주어진 입력 위치에서 최대 한 번만 호출되도록 합니다.이 메모화에 의해 packrat 파서는 많은 컨텍스트프리 문법과 구문해석식 문법(문맥프리 언어를 나타내지 않는 문법도 포함)을 선형시간에 해석할 수 있습니다.메모화된 재귀 강하 파서의 예는 적어도 ^[4]1993년부터 알려져 있다.이 packrat 파서의 퍼포먼스 분석에서는 메모된 결과를 모두 저장할 수 있는 충분한 메모리가 있는 것을 전제로 하고 있습니다.실제로 메모리가 부족하면 동일한 입력 위치에서 일부 파싱 함수를 여러 번 호출해야 하므로 결과적으로 파서가 선형 시간보다 더 오래 걸릴 수 있습니다.

표현식 문법을 해석하여 LL 파서와 LR 파서를 작성할 수도 있으며, 재귀 강하 파서보다 최악의 경우 성능이 우수하지만 문법 형식주의의 무제한 예측 기능은 손실됩니다.따라서 구문 분석식 문법을 사용하여 표현할 수 있는 모든 언어가 LL 또는 LR 파서로 구문 분석할 수 있는 것은 아닙니다.

이점

PEG는 순수 정규 표현(즉, 백 레퍼런스가 없는 경우)에 비해 훨씬 강력하지만 훨씬 더 많은 메모리를 필요로 합니다.예를 들어, 정규 표현식은 본질적으로 일치하는 괄호 쌍의 임의의 수를 찾을 수 없습니다.이는 재귀적인 것이 아니라 PEG에서는 찾을 수 있기 때문입니다.단, PEG는 입력 길이에 비례하는 메모리 양을 필요로 하는 반면 정규 표현 매처는 일정한 양의 메모리만 필요로 합니다.

PEG는 위에서 설명한 바와 같이 packrat 파서를 사용하여 선형 시간 내에 해석할 수 있습니다.

많은 CFG는 모호하지 않은 언어를 기술하는 경우에도 모호함을 포함합니다.C, C++ 및 Java의 "dangling else" 문제가 그 예입니다.이러한 문제들은 종종 문법을 벗어난 규칙을 적용함으로써 해결된다.PEG에서는 우선순위 부여에 의해 이러한 애매모호함이 발생하는 일은 없습니다.

단점들

메모리 소비량

PEG 해석은 보통 packrat 해석을 통해 실행됩니다.메모화는^[5]^[6] 다중 해석 절차를 배제하기 위해 사용됩니다.Packrat 구문 분석에는 LR 구문 분석과 같이 구문 분석 트리의 깊이보다는 총 입력 크기에 비례하는 스토리지가 필요합니다.이것은 많은 도메인에서 중요한 차이입니다.예를 들어 손으로 쓴 소스 코드는 프로그램 길이에 관계없이 효과적으로 일정한 표현 네스트 깊이를 가지며 특정 깊이를 초과하여 중첩된 표현은 리팩터링되는 경향이 있습니다.

일부 문법 및 일부 입력의 경우 구문 분석 트리의 깊이는 입력 ^[7]크기에 비례할 수 있으므로 LR 파서와 packrat 파서는 모두 최악의 점근 성능을 가진 것으로 보입니다.보다 정확한 분석에서는 입력 크기와는 별도로 해석 트리의 깊이가 고려됩니다.이는 그래프 알고리즘에서 발생하는 상황과 유사합니다.Bellman-Ford 알고리즘과 Floyd-Warshall 알고리즘은 정점 수만 고려한다면 동일한 실행 시간 $displaystyle$ O $(V ^{3$ 을 갖는 것으로 보입니다.단, 엣지 수를 별도의 파라미터로 간주하는 보다 정밀한 분석에서는 Bellman-Ford 알고리즘에 O $V$ E $)$ 의 $O(|V|*|E|)$ 을 할당합니다.이것은 E $|E|\in O(|V|)$ ( $|E|\in O(|V|)$ V $|E|\in O(|V|)$ ) \ $displaystyle$ E \ $in$ O $O(|V|*|E|)$ $|E|\in O(|V|)$ $V$ $)$ 의 스파스 그래프에서는 2차입니다 $O(|V|*|E|)$

좌측 간접 재귀

PEG에 왼쪽 재귀 규칙이 없는 경우, 즉 비터미널을 왼쪽 끝 기호와 같은 비터미널이 발생하는 식까지 확장할 수 있는 규칙이 포함되어 있지 않은 경우, PEG는 well-formed라고^[1] 불립니다.왼쪽에서 오른쪽으로의 하향식 파서의 경우 이러한 규칙에 의해 무한 회귀가 발생합니다.파싱은 문자열 내에서 앞으로 이동하지 않고 동일한 비터미널을 계속 확장합니다.

따라서 packrat 해석을 허용하려면 왼쪽 재귀는 삭제해야 합니다.예를 들어, 위의 산술 문법에서는 곱과 합계의 우선순위를 한 줄로 나타낼 수 있도록 몇 가지 규칙을 이동시키는 것이 매력적입니다.

가치   ← [0-9.]+ / '(' 익스프레르 ')' 제품. ← 익스프레르 (('*' / '/') 익스프레르)* 합     ← 익스프레르 (('+' / '-') 익스프레르)* 익스프레르    ← 제품. / 합 / 가치

이 새로운 문법에서, 매칭은Expr테스트 필요Product일치시키는 동안Product테스트 필요Expr일치합니다.이 용어는 맨 왼쪽에 나타나기 때문에 이러한 규칙은 해결할 수 없는 순환적 정의를 구성합니다.(첫 번째 예에서처럼 원래 공식으로 해결할 수 있는 순환적 정의는 존재하지만 이러한 정의는 병리학적 재귀를 나타내지 않기 위해 필요합니다.)단, 왼쪽 재귀 규칙을 항상 다시 작성하여 ^[2]^[8]왼쪽 재귀가 발생하지 않도록 할 수 있습니다.예를 들어 다음과 같은 왼쪽 반복 CFG 규칙입니다.

스트링 오브 어 ← 스트링 오브 어 'a'   'a'

플러스 연산자를 사용하여 PEG로 다시 작성할 수 있습니다.

스트링 오브 어 ← 'a'+

일부 패커트 파서에서는 간접적으로 왼쪽 반복 규칙을 다시 쓰는 프로세스가 복잡합니다.특히 의미적인 액션이 관련되어 있는 경우에는 더욱 그렇습니다.

기존 팩랏 구문 분석에서는 직접 왼쪽 ^[3]^[9]^[10]재귀가 지원되지만 이렇게 하면 일반적으로 PEG 및 팩랏 구문 분석의 근거가 되는 선형 시간 구문^[9] 분석 속성이 손실됩니다.모든 GLR 파서는 왼쪽 재귀를 지원하는 반면, OMeta 구문 [9] 분석 알고리즘은 추가 어텐던트의 복잡성(단, 선형 시간 복잡성 손실) 없이 완전한 왼쪽 재귀를 지원합니다.

표현력

PEG 패커트파서에서는 다음과 ^[2]같은 명확한 비결정적 CFG 규칙을 인식할 수 없습니다.

S ← 'x' S 'x'   'x'

LL(k)과 LR(k)의 해석 알고리즘은 모두 이 예를 인식할 수 없습니다.단, 이 문법은 CYK 알고리즘과 같은 일반적인 CFG 파서로 사용할 수 있습니다.그러나 해당 언어는 실제로는 정규 언어(홀수 x 문자열의 언어)이기 때문에 이러한 모든 유형의 파서에 의해 인식될 수 있습니다.

구문 분석 표현 ^[1]문법으로 인식할 수 없는 문맥 자유 언어의 구체적인 예를 제시하는 것은 미해결 문제이다.특히, 구문 분석 표현 문법이 ^[11]회문의 언어를 인식할 수 있는지 여부는 열려 있다.

일치하는 언어에 대한 규칙 순서의 모호성 검출 및 영향

입력 문법이 애매하면 LL(k) 및 LR(k) 파서 생성기가 완료되지 않습니다.이것은 문법이 모호하지 않지만 결함이 있는 일반적인 경우에 나타나는 특징입니다.PEG 파서 생성기는 의도하지 않은 모호성 early-match-first를 해결합니다.이러한 모호성은 임의이며 예기치 않은 파스가 발생할 수 있습니다.

PEG 문법에서의 제작 순서는 모호성의 해결뿐만 아니라 일치하는 언어에도 영향을 미칩니다.예를 들어 Ford 문서의 첫^[1] 번째 PEG 예(pegjs.org/online 표기로 고쳐 쓰고 $({$ G_ ${1$ $G_{2}$ ({ $display style G_{$ 2}}) $G_{2}$ 로 $G_{1}$ 이 붙어 있습니다).

$(\$ G_ ${1$ A = "a" "b" / "a"
$({$ A = "a" / "a" "b"

Ford는 후자의 PEG 규칙에서 두 번째 대안은 결코 성공하지 못할 것이라고 지적합니다. 왜냐하면 첫 번째 선택은 항상 입력 문자열이 "a"^[1]로 시작되면 선택되기 때문입니다.특히 L ( $L(G_{1})$ G $L(G_{1})$ ) $L(G_{1})$ （ \ $displaystyle L$ ( $G$ _ { $G_{1}$ $1}$ $G_{1}$ ) （ $L(G_{1})$ G 1 $G_{1}$ ） $G_{1}$ by by matched ） 에는 입력 「ab」가 포함되어 있습니다만 $L(G_{2})$ $L(G_{2})$ ( $L(G_{2})$ ) $L(G_{2})$ （ \ $displaystyle$ L ( $G$ _ { $L(G_{2})$ 2} )에는 $L(G_{2})$ 입력이 포함되어 있지 않습니다.따라서 PEG 문법에 새로운 옵션을 추가하면 일치하는 언어에서 문자열을 삭제할 수 있습니다. $G_{2}$ 를 들어 $(\$ 는 $G_{2}$ 단일 생산 문법에 규칙을 추가합니다.A = "a" "b" $또한$ PEG $G_{1}$ $G_{1}$ $G2에서$ L $G1$ L $G_{2}$ G2 $l Cup$ L $(G_$ ${$ 2 $})$ 과 $L(G_{1})\cup L(G_{2})$ $G_{2}$ 하는 문법을 작성합니다.이것은 CFG와는 완전히 대조적입니다.CFG에서는 새로운 프로덕션을 추가해도 문자열을 삭제할 수 없고(단, 애매한 형태로 문제가 발생할 수 있습니다), $L(G_{1})\cup L(G_{2})$ L ( $L(G_{1})\cup L(G_{2})$ 1) $L(G_{1})\cup L(G_{2})$ ) $L(G_{1})\cup L(G_{2})$ ( $L(G_{1})\cup L(G_{2})$ $)\display style$ L ( $G$ _ {1 $}\cup$ L ( $G$ _ {2 $}$ )의 $L(G_{1})\cup L(G_{2})$ $L(G_{1})\cup L(G_{2})$ 이 구축될 수 있습니다.

S → 개시하다(G1)   개시하다(G2)

보텀업 PEG 해석

pika 파서는^[12] 동적 프로그래밍을 사용하여 PEG 규칙을 상향식 및 우측에서 좌측으로 적용합니다.이것은 하향식의 일반 재귀 하강 순서와 반대입니다.역순으로 해석하면 왼쪽 재귀 문제가 해결되어 왼쪽 재귀 규칙을 왼쪽 재귀가 아닌 형식으로 다시 작성하지 않고 문법에 직접 사용할 수 있습니다.또, 파서에 대해서 최적의 에러 리커버리 기능을 전달할 수 있습니다.이것은, 지금까지 재귀적인 하강 파서로 실현하기 어려운 것이 판명되었습니다.

「」를 참조해 주세요.

레퍼런스

^ ^a ^b ^c ^d ^e ^f Ford, Bryan (January 2004). "Parsing Expression Grammars: A Recognition Based Syntactic Foundation" (PDF). Proceedings of the 31st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. ACM. pp. 111–122. doi:10.1145/964001.964011. ISBN 1-58113-729-X.
^ ^a ^b ^c Ford, Bryan (September 2002). "Packrat parsing: simple, powerful, lazy, linear time, functional pearl" (PDF). ACM SIGPLAN Notices. 37 (9). doi:10.1145/583852.581483.
^ ^a ^b ^c Ford, Bryan (September 2002). Packrat Parsing: a Practical Linear-Time Algorithm with Backtracking (Thesis). Massachusetts Institute of Technology. Retrieved 2007-07-27.
^ Merritt, Doug (November 1993). "Transparent Recursive Descent". Usenet group comp.compilers. Retrieved 2009-09-04.
^ Ford, Bryan. "The Packrat Parsing and Parsing Expression Grammars Page". BFord.info. Retrieved 23 Nov 2010.
^ Jelliffe, Rick (10 March 2010). "What is a Packrat Parser? What are Brzozowski Derivatives?". Archived from the original on 28 July 2011.
^ 예를 들어, LISP 식(x(x(x) ..))을 나타냅니다.
^ Aho, A.V.; Sethi, R.; Ullman, J.D. (1986). Compilers: Principles, Techniques, and Tools. Boston, MA, USA: Addison-Wesley Longman. ISBN 0-201-10088-6.
^ ^a ^b ^c Warth, Alessandro; Douglass, James R.; Millstein, Todd (January 2008). "Packrat Parsers Can Support Left Recursion" (PDF). Proceedings of the 2008 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation. PEPM '08. ACM. pp. 103–110. doi:10.1145/1328408.1328424. ISBN 9781595939777. Retrieved 2008-10-02.
^ Steinmann, Ruedi (March 2009). "Handling Left Recursion in Packrat Parsers" (PDF). n.ethz.ch. Archived from the original (PDF) on 2011-07-06.
^ Loff, Bruno; Moreira, Nelma; Reis, Rogério (2020-02-14). "The computational power of parsing expression grammars". arXiv:1902.08272 [cs.FL].
^ Hutchison, Luke A. D. (2020). "Pika parsing: parsing in reverse solves the left recursion and error recovery problems". arXiv:2005.06444 [cs.PL].

외부 링크

식 구문 분석기를 사용하여 문자열 식을 람다 식으로 변환
[ Packrat Parsing and Parsing Expression Grammars ]페이지
생성된 언어인 Lojban은 상당히 큰 PEG 문법을 가지고 있어 Lojban 텍스트를 모호하지 않게 해석할 수 있다.
Guile 스킴에서의 PEG 실시 예

[For04-1] ^ ^a ^b ^c ^d ^e ^f Ford, Bryan (January 2004). "Parsing Expression Grammars: A Recognition Based Syntactic Foundation" (PDF). Proceedings of the 31st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. ACM. pp. 111–122. doi:10.1145/964001.964011. ISBN 1-58113-729-X.

[pegs-2] Ford, Bryan (September 2002). "Packrat parsing: simple, powerful, lazy, linear time, functional pearl" (PDF). ACM SIGPLAN Notices. 37 (9). doi:10.1145/583852.581483.

[ford02-3] Ford, Bryan (September 2002). Packrat Parsing: a Practical Linear-Time Algorithm with Backtracking (Thesis). Massachusetts Institute of Technology. Retrieved 2007-07-27.

[merritt01-4] Merritt, Doug (November 1993). "Transparent Recursive Descent". Usenet group comp.compilers. Retrieved 2009-09-04.

[5] Ford, Bryan. "The Packrat Parsing and Parsing Expression Grammars Page". BFord.info. Retrieved 23 Nov 2010.

[6] Jelliffe, Rick (10 March 2010). "What is a Packrat Parser? What are Brzozowski Derivatives?". Archived from the original on 28 July 2011.

[7] 예를 들어, LISP 식(x(x(x) ..))을 나타냅니다.

[AhoSethiUllman_1986-8] Aho, A.V.; Sethi, R.; Ullman, J.D. (1986). Compilers: Principles, Techniques, and Tools. Boston, MA, USA: Addison-Wesley Longman. ISBN 0-201-10088-6.

[warth08-9] Warth, Alessandro; Douglass, James R.; Millstein, Todd (January 2008). "Packrat Parsers Can Support Left Recursion" (PDF). Proceedings of the 2008 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation. PEPM '08. ACM. pp. 103–110. doi:10.1145/1328408.1328424. ISBN 9781595939777. Retrieved 2008-10-02.

[ruediste09-10] Steinmann, Ruedi (March 2009). "Handling Left Recursion in Packrat Parsers" (PDF). n.ethz.ch. Archived from the original (PDF) on 2011-07-06.

[11] Loff, Bruno; Moreira, Nelma; Reis, Rogério (2020-02-14). "The computational power of parsing expression grammars". arXiv:1902.08272 [cs.FL].

[Hut20-12] Hutchison, Luke A. D. (2020). "Pika parsing: parsing in reverse solves the left recursion and error recovery problems". arXiv:2005.06444 [cs.PL].

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

v t 해석 알고리즘
톱다운	LL 재귀 강하 테일 재귀
상향식	우선 순위 간단하죠. 교환입니다. 쉰팅야드 LR 간단하죠. 미리 보다 표준 일반화 사이키 재귀적 상승 시프트 리듀스
혼합, 기타	콤비네이터 차트 얼리
관련 토픽	PEG 한정절 문법 결정론적 해석 동적 프로그래밍 메모화 파서 발생기 LALR 해석 트리 AST 스캐너리스 해석 컴파일러 구축의 역사 파서 생성기 비교 연산자-우선순위 문법

Search

구문 분석식 문법

네임스페이스

더

목차

정의.

구문

의미론

구문 분석식의 연산 해석

예

표현식 문법의 구문 분석에서 파서를 구현하는 중

이점

단점들

메모리 소비량

좌측 간접 재귀

표현력

일치하는 언어에 대한 규칙 순서의 모호성 검출 및 영향

보텀업 PEG 해석

「」를 참조해 주세요.

레퍼런스

외부 링크

Search

구문 분석식 문법

정의.

구문

의미론

구문 분석식의 연산 해석

예

표현식 문법의 구문 분석에서 파서를 구현하는 중

이점

단점들

메모리 소비량

좌측 간접 재귀

표현력

일치하는 언어에 대한 규칙 순서의 모호성 검출 및 영향

보텀업 PEG 해석

「 」를 참조해 주세요.

레퍼런스

외부 링크

「」를 참조해 주세요.