Parsing expression grammar

컴퓨터 과학에서 파싱 표현 문법(PEG)는 분석 공식 문법의 유형이다. 이는 형식 언어를 언어의 문자열 인식에 대한 문법의 집합의 관점에서 설명한다. formalism(형식주의)는 2004년 Bryan Ford에 의해 소개되었고, 1970년 초에 소개된 top-down parsing language의 가족과 면밀히 관계되어 있다. 문법적으로 PEG는 CFG와 유사하게 보이는데, 다른 해석을 가지고 있다. 선택 연산자는 PEG에서 처음 일치되는 것을 선택하는거에 반면 CFG에서는 모호하다.이것은 문자열 인식이 recursive descent parser에 의해 실제로 수행되는 경향에 더 가깝다. CFG와 달리 PEG는 모호할 수 없다; 문자열은 정확히 하나의 유효한 파스 트리를 가지거나 아무것도 가지지 않는다. 이것은 PEG에 의해 인식될 수 없는 context-free 문법은 존재한다고 추론된다. 하지만 이것은 증명되지 않았다. PEG는 컴퓨처 언어를 파싱하는데 잘 적용되었지만, PEG 알고리즘의 성능은 Early Algorithm과 같은 일반적인 CFG 알고리즘과 유사한 자연어는 적용되지 못한다.

 

정의

---

Syntax

공식적으로, 파싱 식 문법은 다음으로 구성된다.
 ▶ 논터미널 심볼의 유한 집합 N
 ▶ N과 서로소인 터미널 심볼의 유한 집합 ∑
 ▶ 파싱 규칙의 유한 집합 P
 ▶ 시작 표현이라 불리는 표현 e_s

P의 각 파싱 규칙은 A는 논터미널 심볼이고 e가 파싱 표현인 A ← e 형태를 가진다. 파싱 표현은 다음 방법으로 구성되는 정규 표현과 유사한 계층적 표현이다.
1. atomic 파싱 표현은 다음을 구성한다
 ▶ 모든 터미널 심볼
 ▶ 모든 논터미널 심볼
 ▶ 빈 문자열 epsilon

2. 새로운 파싱 표현인 주어진 존재하는 파싱 표현 e, e1 과 e2는 다음 연산자를 사용하여 구성될 수 있다.
 ▶ Sequence: e1 e2
 ▶ Ordered choice: e1 / e2
 ▶ Zero or more: e*
 ▶ one-or-more e+
 ▶ Optional: e?
 ▶ And-predicate: &e
 ▶ Not-predicate: !e
 ▶ Group: (e)
3. 연산자의 우선순위는 테이블 1을 기반으로 다음과 같다.

Operator	Prority
(e)	5
&e, !e	4
e*,e+,e?	3
e1 e2	2
e1 / e2	1

 

---

Semantic

context-free 문법과 파싱 표현 문법 사이의 기본적인 차이 PEG의 choice 연산자는 순서가 있다는 것이다. 만약 첫 번째 대안이 성공한다면 두 번째 대안은 무시된다. 그렇기에 순서가 있는 선택은 context free grammar에서와 같이 순서가 없는 선택과 달리 commutative하지 않다. 여기서 commutative란 순서에 관계없이 연산의 결과가 동일하다는 속성을 말한다. 순서 있는 선택은 일부 로직 프로그래밍 언어에서 가능한 soft-cut 연산자와 유사하다.
결과는 CFG가 PEG로 직접적으로 바꾸어 쓸수 있다면 이전의 모든 모호함은 가능한 parses로 부터 하나의 파스 트리를 결정적으로 고름으로서 해결할 수 있다. 문법 대안이 지정되는 순서를 신중하게 선택함으로써 프로그래머는 파스 트리가 선택되는 것을 상당히 제어할 수 있다.(By carefully choosing the order in which the grammar alternatives are specified, a programmer has a great deal of control over which parse tree is selected.)

boolean context free 문법과 같이 파싱 표현 문법은 and-와 not-과 같은 syntactic predicates를 더한다. 순서가 있는 선택은 실제 소비없이 입력 문자열을 "lookahead"에 임의의 복잡한 치환 표현을 사용할 수 있기 때문에, 강력한 syntactic lookahead와 모호성 해소 기능을 제공한다. 특히 대안(alternative)을 재정렬할 때 요구되는 정확한 파스 트리를 지정할 수 없는 경우에 매우 유용하다.

---

Operational interpretation of parsing expressions

파싱 표현 문법에 각 논터미널은 필수적으로 recursive descent parser의 파싱 함수를 표현하고, 해당하는 파싱 표현은 함수를 포함하는 "code"를 나타낸다. 각 파싱 함수는 개념적으로 인수로써 입력 문자열을 가지고 다음 결과 중 하나를 생성한다.
- success, 함수는 선택적으로 앞으로 움직이거나 혹은 입력 문자열의 하나 이상의 문자를 소비할 수 있다.
- failure, 이 경우 어떤 입력도 소비되지 않는다.

논티미널 A로 구성된 Atomic 파싱 표현은 논티미널 함수 A에 재귀적 호출을 표현한다. 논터미널 A는 모든 입력의 실제 소비 없이 성공한다. 그리고 이것은 실패로부터 구분되는 결과로 고려된다.

sequence 연산자 e1 e2는 첫 번째 e1을 호출한다. 그리고 e1이 성공한다면 연속적으로 e1에 의해 소비되지 않은 입력 문자열의 왼쪽의 나머지에 있는 e2를 호출한다.그리고 결과를 리턴한다. 만약 e1 이나 e2가 실패한다면 sequence 표현 e1 e2는 실패한다(입력에서 소비 없음)

choice 연산자 e1 / e2는 처음 e1을 호출한다. 그리고 e1이 성공하면 결과를 즉시 리턴한다. 반면 만약 e1이 실패한다면 choice 연산자는 e1을 호출한 본래의 입력 위치로 되돌아가고, 대신 e2를 호출하여 e2의 결과를 리턴한다.

zero-or-more, one-or-more 그리고 optional 연산자는 각각 sub-expression e의 0 이상,하나 이상, 0 이거나 하나의 연속적인 반복을 소비한다. 그러나 context-free 문법과 정규 표현과 달리 이 연산자는 항상 '탐욕스럽게' 행동하며 가능한 많은 입력을 소비하고 절대 백트랙킹을 하지 않는다.(정규 표현 matcher는 탐욕스럽게 매칭함으로써 시작할 수 있지만 매치에서 실패한다면 백트랙킹하여 짧은 일치를 시도한다.) 예를 들어 식 a*는 항상 입력 문자열에서 연속적으로 사용할 수 있는 만큼 많은 a를 소비한다. 그리고 표현 (a* a)는 항상 실패할 것이다. 왜냐하면 첫 번째 부분 (a*)은 두 번째 부분이 일치하도록 a를 절대  남기지 않는다.

and-predicate 표현 &e는 하위 표현인 e를 호출하고 e가 성공한다면 succeed 그리고 e가 실패한다면 fail이다. 하지만 두가지 경우에서는 절대 모든 입력을 소비하지 않는다. 

not-predicate 표현인 !e는 e가 실패하면 succeed 그리고 e가 성공한다면 fail이다. 두 경우 모두 다시 입력을 사용하지 않는다. 

---

Examples

이것은 음수가 아닌 5가지 기본 연산자를 적용한 수학 공식을 인식하는 PEG이다.

---

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

위 예제에서 터미널 심볼은 텍스트의 문자이고 '('과 ')'같은 단일 인용 부호 문자에 의해 나타난다. [0-9] 범위는 열 개의 문자 0부터 9까지의 단축이다. 논터미널은 규칙: Valuem Power, Product, Sum과 Expr과 같은 다른 규칙으로 확장한 것이다. Sum과 Product는 요구되는 이 연산의 left-associativity를 이어지지 못한다. 그리고 Power 규칙(오른쪽에 있는 자신을 참조하여)은 지수의 원하는 right-associativity로 이어진다. 또한 Sum ← Sum (('+' / '-') Product)?(왼쪽 결합을 달성하려는 의도로)과 같은 규칙은 무한 재귀을 유발하여 이는 문법으로 표현될 수 있음에도 불구하고 실제로는 사용될 수 없다.

---

S ← 'if' C 'then' S 'else' S / 'if' C 'then' S

위 재귀 규칙은 선택적 else 절은 '/' 연산자의 암시적 우선순위 때문에, 항상 가장 내부의 if와 묶이는 방식으로 표준 C-style if/then/else statements와 일치한다.(context-free 문법에서 이 구조는 고전적인 댕글링 else 모호성을 생상한다)

---

Begin ← '(*'
End   ← '*)'
C     ← Begin N* End
N     ← C / (!Begin !End Z)
Z     ← any single character

위 재귀 규칙은 파스칼 스타일의 중첩되는 주석 구문 (* which can (* nest *) like this *)과 일치한다.

---

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

1. 파싱 표현 foo &(bar)는 텍스트 "bar"가 뒤에 있는 경우에만 텍스트 "foo"를 일치하고 소비한다. 
2. 파싱 표현 foo !(bar) 는 텍스트 "foo"와 일치하지만 텍스트 "bar"가 뒤에 오지 않을 경우에만 일치한다. 
3. !(a+ b) a 표현은 단일 "a"와 일치하지만 a 다음에 b가 오는 임의의 긴 시퀸스의 일부가 아닌 경우에만 일치한다.

파싱 표현 ('a'/'b')*은 a들과 b들의 임의의 긴 시퀀스를 일치하고 소비한다. 생성 규칙 S ← 'a' ''S''? 'b'는 단순한 context-free "mathching 언어" {a^n b^n : n>= 1}를 설명한다. 다음 파싱 표현 문법은 고전 non-context-free 언어 {a^n n^n c^n: n>=1}을 설명한다.

 

Implementing parsers from parsing expression grammars

모든 파싱 표현 문법은 recursive descent parser를 통해 직접적으로 변활될 수 있다. 그러나 문법 formalism이 제공하는 무한한 lookahead 능력때문에, 결과 파서는 최악의 경우 지수 시간의 성능을 나타낼 수 있다.

recurisve decent parser에서 packrat parser로 변환함으로써 파싱 표현 문법을 더 나은 성능으로 얻는 것이 가능하다. 또한 항상 선형 시간에 실행되는 packrat parser는 상당히 큰 저장 공간을 필요로 한다. packrat 파서는 파싱 프로세스 동안 mutually recursive parsing 함수의 모든 호출의 중간 결과를 기억(Memorize)하여, 각 파싱 함수가 주어진 입력 위치에서 최대 한번만 호출하도록 보장하는 것을 제외하고, 구조에서 recursive descent 파서와 비슷한 파서의 형식이다. 이 memorization 때문에 packrat 파서는 많은 context-free 문법과 파싱 표현 문법를 선형 시간에 파싱할 수 있는 능력을 가진다.  물론 충분한 메모리의 사용이 가능해야하며, 메모리가 부족하다면 선형 시간 이상이 될 수 있다.

memorized recursive descent 파서의 예는 적어도 1993년 부터 알려져 있다.

 

mutually recursive parsing 함수란?

서로가 서로를 호출하여 상호적으로 연결된 구조를 갖는 파싱 함수를 의미한다. 이러한 파싱 함수들은 하나의 함수가 다른 함수를 호출하고, 그 다른 함수가 다시 처음 함수를 호출하는 식으로 서로가 상호작용하며 동작한다. 예를 들어 숫자와 연산자로 이루어진 문법이 있다고 할때, 이를 파싱하기 위해 숫자, 연산자 그리고 괄호를 각각 다른 함수로 구현하여 이 함수들을 상호 재귀적으로 호출하면서 복잡한 수식을 처리하는데 도움을 줄 수 있다.

 

memorized recursive descent 파서란?

참조: https://en.wikipedia.org/wiki/Parsing_expression_grammar