shopkeeper/korean_wiki_content_only_120125 huggingface dataset:
대부분의 LR 파서는 테이블 기반이다. 파서의 프로그램 코드는 모든 문법과 언어에 대해 동일한 간단한 일반 루프이다. 문법과 그 구문적 함의에 대한 지식은 파스 테이블(또는 파싱 테이블)이라고 불리는 불변 데이터 테이블에 인코딩된다. 테이블의 항목은 파서 상태와 미리보기 심볼의 모든 유효한 조합에 대해 시프트할지 또는 리듀스할지(그리고 어떤 문법 규칙에 의해)를 보여준다. 파스 테이블은 또한 현재 상태와 다음 심볼이 주어졌을 때 다음 상태를 계산하는 방법도 알려준다.
파스 테이블은 문법보다 훨씬 크다. LR 테이블은 큰 문법에 대해 손으로 정확하게 계산하기 어렵다. 그래서 비손과 같은 파서 생성기 도구에 의해 문법에서 기계적으로 파생된다.
상태 및 파싱 테이블이 생성되는 방법에 따라 결과 파서는 SLR(Simple LR) 파서, LALR(Look-Ahead LR) 파서 또는 정규 LR 파서라고 불린다. LALR 파서는 SLR 파서보다 더 많은 문법을 처리한다. 정규 LR 파서는 훨씬 더 많은 문법을 처리하지만, 더 많은 상태와 훨씬 더 큰 테이블을 사용한다. 예제 문법은 SLR이다.
LR 파스 테이블은 2차원이다. 각 현재 LR(0) 파서 상태는 자체 행을 가진다. 각 가능한 다음 심볼은 자체 열을 가진다. 상태와 다음 심볼의 일부 조합은 유효한 입력 스트림에 대해 불가능하다. 이러한 빈 셀은 구문 오류 메시지를 유발한다.
테이블의 액션 왼쪽 절반은 미리보기 종결자 열을 가진다. 이 셀들은 다음 파서 액션이 시프트(상태 n으로)인지 또는 리듀스(문법 규칙 rn에 의해)인지 결정한다.
테이블의 고투 오른쪽 절반은 비종결자 열을 가진다. 이 셀들은 어떤 리덕션의 좌변이 해당 심볼의 예상되는 새 인스턴스를 생성한 후 어떤 상태로 진행할지를 보여준다. 이는 시프트 액션과 비슷하지만 비종결자를 위한 것이다. 미리보기 종결자 심볼은 변경되지 않는다.
"현재 규칙"이라는 테이블 열은 파서 생성기에 의해 도출된 각 상태에 대한 의미와 구문 가능성을 문서화한다. 파싱 시 실제로 사용되는 테이블에는 포함되지 않는다. (핑크 점) 마커는 파서가 현재 부분적으로 인식된 문법 규칙 내에서 어디에 있는지 보여준다. 왼쪽에 있는 항목들은 파싱되었으며, 오른쪽에 있는 항목들은 곧 예상된다. 파서가 가능성을 단일 규칙으로 좁히지 않은 경우 상태는 여러 개의 현재 규칙을 가질 수 있다.
위의 상태 2에서 파서는 문법 규칙의 +를 방금 찾아서 시프트했다.
다음 예상 구문은 Products이다. Products는 종결자 int 또는 id로 시작한다. 미리 보기가 이 둘 중 하나인 경우 파서는 이들을 시프트하고 각각 상태 8 또는 9로 진행한다. Products가 발견되면 파서는 합산 항목의 전체 목록을 축적하고 규칙 r0의 끝을 찾기 위해 상태 3으로 진행한다. Products는 비종결자 Value로도 시작할 수 있다. 다른 미리 보기 또는 비종결자의 경우 파서는 구문 오류를 알린다.
상태 3에서 파서는 방금 Products 구문을 찾았는데, 이는 두 가지 가능한 문법 규칙에서 비롯될 수 있다.
r1과 r3 사이의 선택은 이전 구문을 뒤로만 살펴서는 결정할 수 없다. 파서는 무엇을 해야 할지 알아내기 위해 미리보기 심볼을 확인해야 한다. 미리보기가 *이면 규칙 3에 있으므로 파서는 *를 시프트하고 상태 5로 진행한다. 미리보기가 eof이면 규칙 1과 규칙 0의 끝에 있으므로 파서는 완료된다.
위의 상태 9에서 비어있지 않고 오류가 아닌 모든 셀은 동일한 축소 r6에 대한 것이다. 일부 파서는 이러한 간단한 경우에 미리보기 심볼을 확인하지 않아 시간과 테이블 공간을 절약한다. 구문 오류는 약간 나중에, 일부 무해한 축소 후에 감지되지만, 다음 시프트 동작 또는 파서 결정 전에는 여전히 감지된다.
개별 테이블 셀에는 여러 대안 동작이 있어서는 안 된다. 그렇지 않으면 파서는 추측 및 백트래킹으로 비결정적이 될 수 있다. 문법이 LR(1)이 아닌 경우, 일부 셀에는 가능한 시프트 동작과 축소 동작 간의 시프트/축소 충돌 또는 여러 문법 규칙 간의 축소/축소 충돌이 발생한다. LR(k) 파서는 첫 번째를 넘어 추가 미리보기 심볼을 확인하여 이러한 충돌을 (가능한 경우) 해결한다.
LR 파서 루프.
LR 파서는 시작 상태 0만 포함하는 거의 비어있는 파스 스택으로 시작하며, 미리보기는 입력 스트림의 첫 번째 스캔된 심볼을 담고 있다. 그런 다음 파서는 완료되거나 구문 오류에 갇힐 때까지 다음 루프 단계를 반복한다.
파스 스택의 최상위 상태는 특정 상태 s이고, 현재 미리보기는 특정 종결자 t이다. 미리보기 액션 테이블의 s행 t열에서 다음 파서 액션을 찾는다. 해당 액션은 시프트, 리듀스, 수락 또는 오류 중 하나이다.
LR 파서 스택은 일반적으로 LR(0) 오토마톤 상태만 저장한다. 왜냐하면 문법 심볼은 이들로부터 파생될 수 있기 때문이다(오토마톤에서 어떤 상태로의 모든 입력 전이는 동일한 심볼로 표시되며, 이는 이 상태와 연관된 심볼이다). 게다가 파싱 결정을 내릴 때 상태가 가장 중요하므로 이러한 심볼은 거의 필요하지 않다.
LR 생성기 분석.
이 문서의 이 섹션은 LR 파서 생성기 사용자 대부분은 건너뛸 수 있다.
LR 상태.
예제 파스 테이블의 상태 2는 부분적으로 파싱된 규칙을 위한 것이다.
이는 파서가 더 큰 Sums를 찾으면서 Sums를 본 다음 +를 보면서 여기에 어떻게 도달했는지 보여준다. 마커는 규칙의 시작을 지나 전진했다. 또한 파서가 완전한 Products를 다음에 찾아 궁극적으로 규칙을 완료할 것으로 예상하는 방법도 보여준다. 그러나 해당 Products의 모든 부분을 파싱하는 방법에 대한 더 자세한 정보가 필요하다.
상태에 대한 부분적으로 파싱된 규칙을 "코어 LR(0) 항목"이라고 한다. 파서 생성기는 예상되는 Products를 구축하는 데 필요한 모든 가능한 다음 단계에 대한 추가 규칙 또는 항목을 추가한다.
마커는 이러한 추가된 각 규칙의 시작 부분에 있다. 파서는 아직 이들 중 어떤 부분도 확인하고 파싱하지 않았다. 이러한 추가 항목을 코어 항목의 "폐쇄"라고 한다. 바로 뒤에 오는 각 비종결자 심볼에 대해 생성기는 해당 심볼을 정의하는 규칙을 추가한다. 이는 더 많은 마커와 경우에 따라 다른 후행 심볼을 추가한다. 이 폐쇄 과정은 모든 후행 심볼이 확장될 때까지 계속된다. 상태 2의 후행 비종결자는 Products로 시작한다. Value는 폐쇄에 의해 추가된다. 후행 종결자는 int와 id이다.
커널 및 폐쇄 항목은 함께 현재 상태에서 미래 상태로 진행하고 구문을 완료하는 모든 가능한 합법적인 방법을 보여준다. 만약 후행 심볼이 단 하나의 항목에만 나타난다면, 마커가 전진된 단 하나의 핵심 항목을 포함하는 다음 상태로 이어진다. 따라서 int는 핵심을 가진 다음 상태 8로 이어진다.
만약 동일한 후행 심볼이 여러 항목에 나타난다면, 파서는 어떤 규칙이 여기에 적용되는지 아직 알 수 없다. 따라서 해당 심볼은 마커가 전진된 상태에서 모든 나머지 가능성을 보여주는 다음 상태로 이어진다. Products는 r1과 r3 모두에 나타난다. 따라서 Products는 핵심을 가진 다음 상태 3으로 이어진다.
쉽게 말하면, 파서가 단일 Products를 보았다면 작업이 완료되었거나, 곱해야 할 항목이 더 많을 수 있다는 의미이다. 모든 핵심 항목은 마커 앞에 동일한 심볼을 가진다. 이 상태로의 모든 전이는 항상 동일한 심볼로 이루어진다.
일부 전이는 이미 열거된 코어 및 상태로 이어진다. 다른 전이는 새로운 상태로 이어진다. 생성기는 문법의 목표 규칙으로 시작한다. 거기서부터 모든 필요한 상태가 발견될 때까지 알려진 상태와 전이를 계속 탐색한다.
이러한 상태들은 k=0, 즉 미리보기가 없음을 사용하기 때문에 "LR(0)" 상태라고 불린다. 입력 심볼의 확인은 심볼이 시프트될 때만 발생한다. 축소에 대한 미리보기 확인은 파스 테이블에 의해 별도로 수행되며, 열거된 상태 자체에 의해 수행되지 않는다.
파스 테이블은 가능한 모든 LR(0) 상태와 그 전이를 기술한다. 이들은 유한 상태 기계 (FSM)를 형성한다. FSM은 스택을 사용하지 않고 간단한 중첩되지 않은 언어를 파싱하기 위한 간단한 엔진이다. 이 LR 애플리케이션에서 FSM의 수정된 "입력 언어"는 종결자와 비종결자 심볼을 모두 가지며, 전체 LR 파스의 부분적으로 파싱된 스택 스냅샷을 포함한다.
파스 단계 예시의 5단계를 다시 살펴보자.
구문 분석 스택은 시작 상태 0에서 상태 4로, 그리고 5를 거쳐 현재 상태 8로 이어지는 일련의 상태 전환을 보여준다. 구문 분석 스택의 심볼은 이러한 전환에 대한 시프트 또는 고투 심볼이다. 이를 다른 방식으로 보면, 유한 상태 기계는 스트림 "Products * int + 1"을 (또 다른 스택을 사용하지 않고) 스캔하고 다음에 축소되어야 할 가장 왼쪽의 완전한 구문을 찾을 수 있다. 그리고 그것이 바로 그 역할이다!
원래의 파싱되지 않은 언어가 중첩과 재귀를 포함하고 분석기에 스택이 분명히 필요한데, 단순한 FSM이 어떻게 이를 수행할 수 있을까? 핵심은 스택 상단의 왼쪽에 있는 모든 것이 이미 완전히 축소되었다는 점이다. 이는 해당 구문에서 모든 루프와 중첩을 제거한다. FSM은 구문의 모든 오래된 시작 부분을 무시하고, 다음에 완료될 수 있는 가장 새로운 구문만 추적할 수 있다. LR 이론에서 이를 설명하는 모호한 이름은 "유효 접두사"이다.
미리보기 집합.
상태와 전이는 파스 테이블의 시프트 동작과 고투 동작에 필요한 모든 정보를 제공한다. 생성기는 또한 각 리듀스 동작에 대한 예상 미리보기 집합을 계산해야 한다.
SLR 파서에서는 이러한 미리보기 집합이 개별 상태와 전이를 고려하지 않고 문법에서 직접 결정된다. 각 비종결자 S에 대해 SLR 생성기는 S의 어떤 발생 직후에 올 수 있는 모든 종결자 집합인 Follows(S)를 계산한다. 파스 테이블에서 S로의 각 축소는 Follow(S)를 해당 LR(1) 미리보기 집합으로 사용한다. 이러한 팔로우 집합은 LL 하향식 파서의 생성기에서도 사용된다. 팔로우 집합을 사용할 때 시프트/리듀스 또는 리듀스/리듀스 충돌이 없는 문법을 SLR 문법이라고 한다.
LALR 파서는 SLR 파서와 동일한 상태를 가지지만, 각 개별 상태에 대해 최소한으로 필요한 축소 미리보기를 계산하는 더 복잡하고 정확한 방법을 사용한다. 문법의 세부 사항에 따라 이는 SLR 파서 생성기가 계산한 팔로우 집합과 동일하거나 SLR 미리보기의 부분 집합이 될 수 있다. 일부 문법은 LALR 파서 생성기에는 적합하지만 SLR 파서 생성기에는 적합하지 않다. 이는 팔로우 집합을 사용할 때 문법에 가짜 시프트/리듀스 또는 리듀스/리듀스 충돌이 있지만 LALR 생성기가 계산한 정확한 집합을 사용할 때는 충돌이 없을 때 발생한다. 이때 해당 문법은 LALR(1)이지만 SLR은 아니다.
SLR 또는 LALR 파서는 중복 상태를 피한다. 그러나 이러한 최소화는 필수가 아니며, 때로는 불필요한 미리보기 충돌을 일으킬 수 있다. 정규 LR 파서는 중복된(또는 "분할된") 상태를 사용하여 비종결자 사용의 왼쪽 및 오른쪽 컨텍스트를 더 잘 기억한다. 문법에서 심볼 S의 각 발생은 자체 미리보기 집합으로 독립적으로 처리되어 축소 충돌을 해결하는 데 도움이 된다. 이는 몇몇 문법을 더 많이 처리한다. 불행히도, 문법의 모든 부분에 대해 수행되면 파스 테이블의 크기가 크게 확대된다. 이러한 상태 분할은 비종결자의 두 개 이상의 명명된 복사본을 만들어서 어떤 SLR 또는 LALR 파서에서도 수동으로, 그리고 선택적으로 수행할 수 있다. 정규 LR 생성기에는 충돌이 없지만 LALR 생성기에는 충돌이 있는 문법을 LR(1)이라고 하지만 LALR(1)도 SLR도 아니다.
SLR, LALR, 정규 LR 파서는 입력 스트림이 올바른 언어일 때 정확히 동일한 시프트 및 리듀스 결정을 내린다. 입력에 구문 오류가 있을 때 LALR 파서는 정규 LR 파서보다 오류를 감지하기 전에 몇 가지 추가 (무해한) 리듀스를 수행할 수 있다. 그리고 SLR 파서는 더 많은 리듀스를 수행할 수도 있다. 이는 SLR 및 LALR 파서가 해당 특정 상태에 대한 실제 최소 미리보기 심볼에 대한 관대한 상위 집합 근사를 사용하기 때문에 발생한다.
구문 오류 복구.
LR 파서는 프로그램의 첫 번째 구문 오류에 대해 다소 도움이 되는 오류 메시지를 생성할 수 있다. 예상치 못한 잘못된 미리보기 심볼 대신 다음에 나타날 수 있었던 모든 종결자 심볼을 단순히 열거함으로써 말이다. 그러나 이는 파서가 나머지 입력 프로그램을 파싱하여 추가적인 독립적인 오류를 찾는 데 도움이 되지 않는다. 파서가 첫 번째 오류에서 잘못 복구하면 다른 모든 것을 잘못 파싱하여 쓸모없는 잘못된 오류 메시지의 연쇄를 생성할 가능성이 매우 높다.
yacc 및 Bison 파서 생성기에서 파서는 현재 문장을 포기하고 오류 주변의 파싱된 구문과 미리보기 토큰을 버리고 세미콜론이나 중괄호와 같은 신뢰할 수 있는 문장 수준 구분 기호에서 파싱을 재동기화하는 임시 메커니즘을 가지고 있다. 이는 파서와 컴파일러가 프로그램의 나머지 부분을 검토하는 데 종종 잘 작동한다.
많은 구문 코딩 오류는 간단한 오타 또는 사소한 심볼의 생략이다. 일부 LR 파서는 이러한 일반적인 경우를 감지하고 자동으로 복구하려고 시도한다. 파서는 오류 지점에서 가능한 모든 단일 심볼 삽입, 삭제 또는 대체를 열거한다. 컴파일러는 각 변경 사항으로 시험 파싱을 수행하여 제대로 작동하는지 확인한다. (이는 파서에서 일반적으로 필요 없는 파스 스택 및 입력 스트림의 스냅샷으로의 백트래킹을 필요로 한다.) 최상의 복구가 선택된다. 이는 매우 유용한 오류 메시지를 제공하고 파싱을 잘 재동기화한다. 그러나 이 복구는 입력 파일을 영구적으로 수정할 만큼 신뢰할 수 없다. 구문 오류 복구는 파스 테이블과 명시적 데이터 스택을 가진 파서(예: LR)에서 일관되게 수행하기 가장 쉽다.
LR 파서의 변형.
LR 파서 생성기는 파서 상태와 미리보기 심볼의 각 조합에 대해 무엇이 발생해야 하는지 결정한다. 이러한 결정은 일반적으로 읽기 전용 데이터 테이블로 변환되어 문법 및 상태에 독립적인 일반 파서 루프를 구동한다. 그러나 이러한 결정을 활성 파서로 전환하는 다른 방법도 있다.
일부 LR 파서 생성기는 파스 테이블 대신 각 상태에 대해 별도로 맞춤형 프로그램 코드를 생성한다. 이 파서들은 테이블 기반 파서의 일반 파서 루프보다 몇 배 더 빠르게 실행될 수 있다. 가장 빠른 파서는 생성된 어셈블러 코드를 사용한다.
재귀 상승 파서 변형에서는 명시적 파스 스택 구조가 서브루틴 호출에 의해 사용되는 암시적 스택으로 대체된다. 리덕션은 여러 수준의 서브루틴 호출을 종료시키는데, 이는 대부분의 언어에서는 서투른 일이다. 따라서 재귀 상승 파서는 일반적으로 재귀 하향 파서보다 느리고 덜 명확하며 수동으로 수정하기 어렵다.
또 다른 변형은 파스 테이블을 프롤로그와 같은 비절차적 언어의 패턴 매칭 규칙으로 대체한다.
GLR 일반화된 LR 파서는 LR 상향식 기술을 사용하여 입력 텍스트의 가능한 모든 파싱을 찾으며, 단 하나의 올바른 파싱만을 찾지 않는다. 이는 인간 언어에 사용되는 것과 같은 모호한 문법에 필수적이다. 여러 유효한 파스 트리는 백트래킹 없이 동시에 계산된다. GLR은 충돌 없는 LALR(1) 문법으로 쉽게 기술할 수 없는 컴퓨터 언어에 유용할 때가 있다.
LC 좌상향 파서는 LR 상향식 기술을 사용하여 대체 문법 규칙의 왼쪽 끝을 인식한다. 대안이 단일 가능한 규칙으로 좁혀지면 파서는 해당 규칙의 나머지를 파싱하기 위해 하향식 LL(1) 기술로 전환한다. LC 파서는 LALR 파서보다 파스 테이블이 작고 오류 진단이 더 좋다. 결정론적 LC 파서에 대한 널리 사용되는 생성기는 없다. 다중 파싱 LC 파서는 매우 큰 문법을 가진 인간 언어에 유용하다.
LR 파서는 도널드 커누스가 1965년에 우선순위 파서의 효율적인 일반화로 발명했다. 커누스는 LR 파서가 최악의 경우에도 효율적일 수 있는 가장 일반적인 목적의 파서임을 증명했다.
다른 말로 하면, 효율적인 단일 패스 파서가 가능할 만큼 합리적인 언어라면 LR(k) 문법으로 기술할 수 있었다. 그리고 그 문법은 항상 기계적으로 동등한 (그러나 더 큰) LR(1) 문법으로 변환될 수 있었다. 따라서 이론적으로 LR(1) 파싱 방법은 모든 합리적인 언어를 처리할 수 있을 만큼 강력했다. 실제로 많은 프로그래밍 언어의 자연스러운 문법은 LR(1)에 가깝다.
커누스가 기술한 정규 LR 파서는 너무 많은 상태와 방대한 파스 테이블을 가지고 있어 그 시대의 제한된 컴퓨터 메모리로는 비실용적으로 컸다. LR 파싱은 프랭크 디리머가 훨씬 적은 상태를 가진 SLR 및 LALR 파서를 발명하면서 실용적이 되었다.
LR 이론과 LR 파서가 문법에서 어떻게 파생되는지에 대한 자세한 내용은 "Parsing, Translation, and Compiling, Volume 1 (Aho and Ullman)"을 참조하라.
얼리 파서는 LR 파서의 기법과 표기법을 인간 언어와 같은 모호한 문법에 대한 가능한 모든 파싱을 생성하는 작업에 적용한다.
LR(k) 문법은 모든 k≥1에 대해 동일한 생성 능력을 가지지만, LR(0) 문법의 경우는 약간 다르다.
언어 L은 L에 있는 어떤 단어도 L에 있는 다른 단어의 고유 접두사가 아닌 경우 접두사 속성을 가진다고 한다.
언어 L이 LR(0) 문법을 가지는 것은 L이 접두사 속성을 가진 결정적 문맥 자유 언어인 경우에 한한다.
결과적으로 언어 L이 결정적 문맥 자유 언어인 것은 L$이 LR(0) 문법을 가지는 경우에 한하며, 여기서 "$"는 L의 알파벳의 심볼이 아니다.
추가 예제 1 + 1.
이 LR 파싱 예시는 목표 심볼 E를 가진 다음 작은 문법을 사용한다.
다음 입력을 파싱한다.
액션 및 고투 테이블.
이 문법에 대한 두 LR(0) 파싱 테이블은 다음과 같다.
액션 테이블은 파서의 상태와 종결자(입력 스트림의 끝을 나타내는 특수 종결자 $ 포함)로 색인화되며 세 가지 유형의 액션을 포함한다.
고투 테이블은 파서의 상태와 비종결자로 인덱싱되며 특정 비종결자를 인식한 경우 파서의 다음 상태가 무엇인지를 단순히 나타낸다. 이 테이블은 모든 축소 후에 다음 상태를 알아내는 데 중요하다. 축소 후에는 스택의 맨 위(즉, 현재 상태)와 축소된 규칙의 LHS(즉, 비종결자)에 대한 고투 테이블 항목을 찾아 다음 상태를 찾는다.
파싱 단계.
아래 표는 과정의 각 단계를 보여준다. 여기서 상태는 스택의 맨 위(가장 오른쪽 요소) 요소를 나타내며, 다음 액션은 위 액션 테이블을 참조하여 결정된다. 입력 스트림의 끝을 나타내기 위해 입력 문자열에 $가 추가된다.
파서는 초기 상태('0')만 포함된 스택으로 시작한다.
파서가 입력 문자열에서 처음 보는 심볼은 '1'이다. 다음 액션(시프트, 리듀스, 수락 또는 오류)을 찾기 위해 액션 테이블은 현재 상태(스택 맨 위에 있는 것)인 0과 현재 입력 심볼인 '1'로 인덱싱된다. 액션 테이블은 상태 2로 시프트하도록 지정하므로 상태 2가 스택에 푸시된다(다시 말하지만, 모든 상태 정보는 스택에 있으므로 "상태 2로 시프트"하는 것은 2를 스택에 푸시하는 것과 동일하다). 결과 스택은 다음과 같다.
스택의 맨 위는 2이다. 심볼(예: '1', B)을 설명하기 위해 다음 상태로의 전환을 유발한 원인이 표시되지만, 엄밀히 말하면 스택의 일부는 아니다.
상태 2에서 액션 테이블은 문법 규칙 5를 사용하여 축소하라고 한다(파서가 입력 스트림에서 어떤 터미널을 보든지 상관없이). 이는 파서가 규칙 5의 오른쪽 부분을 방금 인식했음을 의미한다. 이 경우 파서는 출력 스트림에 5를 쓰고, 스택에서 한 상태를 팝하고(규칙의 오른쪽 부분에 심볼 하나가 있기 때문), 상태 0과 B에 대한 고투 테이블의 셀에서 새 상태, 즉 상태 4를 푸시한다. 결과 스택은 다음과 같다.
하지만 상태 4에서 액션 테이블은 파서가 이제 규칙 3으로 축소해야 한다고 말한다. 그래서 출력 스트림에 3을 쓰고, 스택에서 상태 하나를 팝하고, 상태 0과 E에 대한 고투 테이블에서 새 상태인 상태 3을 찾는다. 결과 스택은 다음과 같다.
파서가 다음에 보는 종결자는 '+'이고, 액션 테이블에 따르면 상태 6으로 시프트해야 한다.
결과 스택은 비종결자 E 뒤에 종결자 '+'를 읽은 유한 상태 기계의 기록으로 해석될 수 있다. 이 오토마톤의 전이 테이블은 액션 테이블의 시프트 액션과 고투 테이블의 고투 액션으로 정의된다.
다음 종결자는 '1'이며, 이는 파서가 시프트를 수행하여 상태 2로 이동함을 의미한다.
이전의 '1'과 마찬가지로 이 '1'도 B로 축소되어 다음 스택을 제공한다.
스택은 비종결자 E를 읽은 후 '+'와 비종결자 B를 읽은 유한 오토마톤의 상태 목록에 해당한다. 상태 8에서 파서는 항상 규칙 2로 축소를 수행한다. 스택의 최상위 3개 상태는 규칙 2의 오른쪽에 있는 3개 심볼에 해당한다. 이번에는 스택에서 3개 요소를 팝하고(규칙의 오른쪽에 3개 심볼이 있기 때문) E와 0에 대한 고투 상태를 찾아 상태 3을 다시 스택에 푸시한다.
마지막으로, 파서는 입력 스트림에서 '$'(입력 끝 심볼)를 읽는데, 이는 액션 테이블(현재 상태는 3)에 따르면 파서가 입력 문자열을 수락한다는 것을 의미한다. 그 때 출력 스트림에 기록된 규칙 번호는 [5, 3, 5, 2]가 되며, 이는 "1 + 1" 문자열의 역 가장 오른쪽 파생이다.
LR(0) 파싱 테이블 구축.
이러한 파싱 테이블의 구성은 LR(0) 아이템(여기서는 간단히 아이템이라고 함) 개념을 기반으로 한다. 이는 오른쪽 부분에 특수 점이 추가된 문법 규칙이다. 예를 들어, E → E + B 규칙에는 다음과 같은 4가지 해당 아이템이 있다.
A → ε 형태의 규칙은 단일 아이템 A → 만을 가진다. 예를 들어, 아이템 E → E + B는 파서가 입력 스트림에서 E에 해당하는 문자열을 인식했으며 이제 '+' 뒤에 B에 해당하는 다른 문자열을 읽을 것으로 예상함을 나타낸다.
아이템 집합.
파서의 상태를 단일 항목으로 특징짓는 것은 일반적으로 불가능하다. 왜냐하면 파서가 축소를 위해 어떤 규칙을 사용할지 미리 알지 못할 수 있기 때문이다. 예를 들어, E → E * B 규칙도 있다면, E에 해당하는 문자열이 읽힌 후에는 E → E + B와 E → E * B 항목이 모두 적용된다. 따라서 이 경우 { E → E + B, E → E * B }와 같은 항목 집합으로 파서의 상태를 특징짓는 것이 편리하다.
비종결자 확장을 통한 아이템 집합 확장.
E → E + B와 같이 비종결자 앞에 점이 있는 항목은 파서가 다음에 비종결자 B를 파싱할 것으로 예상함을 나타낸다. 항목 집합이 파서가 파싱 중일 수 있는 모든 가능한 규칙을 포함하도록 하려면, B 자체를 어떻게 파싱할지를 설명하는 모든 항목을 포함해야 한다. 이는 B → 1 및 B → 0과 같은 규칙이 있는 경우 항목 집합에 B → 1 및 B → 0 항목도 포함되어야 함을 의미한다. 일반적으로 다음과 같이 공식화할 수 있다.
아이템 집합의 폐쇄.
따라서 점 앞에 있는 모든 비종결자가 고려될 때까지 모든 적절한 항목을 재귀적으로 추가하여 모든 항목 집합을 확장할 수 있다. 최소 확장을 항목 집합의 폐쇄라고 하며 I가 항목 집합일 때 clos(I)로 쓴다. 실제로 시작 상태에서 도달할 수 있는 항목 집합만 테이블에 포함되지만, 이 폐쇄된 항목 집합이 파서의 상태로 간주된다.
확장 문법.
다른 상태 간의 전이가 결정되기 전에 문법은 추가 규칙으로 확장된다.
여기서 S는 새로운 시작 심볼이고 E는 이전 시작 심볼이다. 파서는 입력 문자열 전체를 수락했을 때 정확히 이 규칙을 축소에 사용할 것이다.
이 예제에서는 위와 동일한 문법이 다음과 같이 확장된다.
이 확장된 문법에 대해 항목 집합과 그들 사이의 전이가 결정될 것이다.
테이블 구축.
도달 가능한 항목 집합과 그들 사이의 전이 찾기.
테이블을 구축하는 첫 번째 단계는 폐쇄된 항목 집합들 간의 전이를 결정하는 것이다. 이 전이들은 우리가 종결자와 비종결자를 모두 읽을 수 있는 유한 오토마톤을 고려하는 것처럼 결정될 것이다. 이 오토마톤의 시작 상태는 항상 추가된 규칙의 첫 번째 항목의 폐쇄이다. S → E eof:
항목 앞의 굵은 "+"는 폐쇄를 위해 추가된 항목을 나타낸다(수학적 '+' 연산자, 즉 종결자와 혼동하지 말 것). "+"가 없는 원래 항목을 항목 집합의 커널이라고 한다.
시작 상태(S0)에서 시작하여 이 상태에서 도달할 수 있는 모든 상태가 이제 결정된다. 항목 집합의 가능한 전이는 점 뒤에 오는 심볼(종결자와 비종결자)을 확인함으로써 찾을 수 있다. 항목 집합 0의 경우 해당 심볼은 종결자 '0'과 '1' 그리고 비종결자 E와 B이다. 각 심볼 formula_1가 이끄는 항목 집합을 찾기 위해 각 심볼에 대해 다음 절차를 따른다.
종결자 '0'(즉, x = '0'인 경우)에 대해 결과는 다음과 같다.
그리고 종결자 '1'(즉, x = '1'인 경우)에 대해 결과는 다음과 같다.
그리고 비종결자 E(즉, x = E인 경우)에 대해 결과는 다음과 같다.
그리고 비종결자 B(즉, x = B인 경우)에 대해 결과는 다음과 같다.
클로저가 항상 새로운 항목을 추가하는 것은 아니다. 예를 들어 위의 새로운 집합들에는 점 뒤에 비종결자가 없다.
위의 절차는 더 이상 새로운 항목 집합이 발견되지 않을 때까지 계속된다. 항목 집합 1, 2, 4에는 점이 어떤 심볼 앞에도 없으므로 전이가 없을 것이다. 하지만 항목 집합 3에는 종결자 '*'와 '+' 앞에 점이 있다. 심볼 formula_2에 대해 전이는 다음과 같다.
그리고 formula_3에 대해 전이는 다음과 같다.
이제 세 번째 반복이 시작된다.
항목 집합 5의 경우 종결자 '0'과 '1', 그리고 비종결자 B를 고려해야 하지만, 종결자에 대해 생성되는 폐쇄된 항목 집합은 이미 발견된 항목 집합 1과 2와 각각 동일하다. 비종결자 B의 경우 전이는 다음과 같다.
항목 집합 6의 경우 종결자 '0'과 '1', 비종결자 B를 고려해야 하지만, 이전과 마찬가지로 종결자에 대해 생성되는 항목 집합은 이미 발견된 항목 집합 1과 2와 동일하다. 비종결자 B의 경우 전이는 다음과 같다.
이 최종 항목 집합 7과 8에는 점 너머의 심볼이 없으므로 더 이상 새로운 항목 집합이 추가되지 않아 항목 생성 절차가 완료된다. 항목 집합을 상태로 하는 유한 오토마톤은 아래에 나와 있다.
이제 오토마톤의 전이 테이블은 다음과 같다.
액션 및 고투 테이블 구축.
이 테이블과 발견된 항목 집합으로부터 액션 및 고투 테이블은 다음과 같이 구축된다.
독자는 이러한 단계들이 이전에 제시된 액션 및 고투 테이블을 생성하는지 확인할 수 있다.
LR(0) 대 SLR 및 LALR 파싱에 대한 참고 사항.
위 절차의 4단계만 리듀스 액션을 생성하므로, 모든 리듀스 액션은 전체 테이블 행을 차지해야 하며, 입력 스트림의 다음 심볼에 관계없이 축소가 발생하게 한다. 이것이 바로 이들이 LR(0) 파스 테이블인 이유이다. 즉, 어떤 축소를 수행할지 결정하기 전에 미리보기를 전혀 하지 않는다(즉, 0개의 심볼을 미리 본다). 축소의 모호성을 해소하기 위해 미리보기가 필요한 문법은 다른 열에 다른 축소 액션을 포함하는 파스 테이블 행을 필요로 하며, 위 절차는 그러한 행을 생성할 수 없다.
LR(0) 테이블 구축 절차의 개선 사항(예: SLR 및 LALR)은 전체 행을 차지하지 않는 리듀스 액션을 구축할 수 있다. 따라서 이들은 LR(0) 파서보다 더 많은 문법을 파싱할 수 있다.
구축된 테이블의 충돌.
오토마톤은 결정론적임을 보장하는 방식으로 구축된다. 그러나 액션 테이블에 축소 액션이 추가될 때, 동일한 셀이 축소 액션과 시프트 액션(시프트-축소 충돌) 또는 두 개의 다른 축소 액션(축소-축소 충돌)으로 채워지는 경우가 발생할 수 있다. 그러나 이 경우 문법이 LR(0) 문법이 아님을 보여줄 수 있다. 시프트-축소 충돌의 고전적인 실제 예는 매달린 else 문제이다.
시프트-리듀스 충돌이 있는 비-LR(0) 문법의 작은 예시는 다음과 같다.
발견된 항목 집합 중 하나는 다음과 같다.
이 항목 집합에는 시프트-리듀스 충돌이 있다. 위 규칙에 따라 액션 테이블을 구축할 때 [항목 집합 1, 종결자 '1'] 셀에는 s1(상태 1로 시프트)과 r2(문법 규칙 2로 축소)가 모두 포함된다.
축소-축소 충돌이 있는 비-LR(0) 문법의 작은 예시는 다음과 같다.
이 경우 다음 항목 집합이 얻어진다.
이 항목 집합에는 축소-축소 충돌이 있다. 이 항목 집합의 액션 테이블 셀에 규칙 3에 대한 축소 액션과 규칙 4에 대한 축소 액션이 모두 있기 때문이다.
위의 두 예는 파서가 비종결자 A의 팔로우 집합(LL 파서 참조)을 사용하여 A의 규칙 중 하나를 축소에 사용할지 여부를 결정하게 함으로써 해결할 수 있다. 파서는 입력 스트림의 다음 심볼이 A의 팔로우 집합에 있는 경우에만 A → w 규칙을 축소에 사용할 것이다. 이 솔루션은 소위 단순 LR 파서를 낳는다.
컴퓨터 과학에서 파싱 표현 문법(parsing expression grammar, PEG)은 분석적 형식 문법의 일종으로, 언어 내의 문자열을 인식하기 위한 규칙 집합으로 형식 언어를 설명한다. 이 형식론은 브라이언 포드(Bryan Ford)가 2004년에 도입했으며 1970년대 초에 도입된 하향식 파싱 언어 계열과 밀접한 관련이 있다.
구문적으로 PEG는 문맥 자유 문법(CFG)과도 유사하지만 해석이 다르다. PEG에서는 선택 연산자가 첫 번째 일치 항목을 선택하는 반면, CFG에서는 모호할 수 있다. 이는 재귀 하향 파서와 같이 문자열 인식이 실제에서 수행되는 방식에 더 가깝다.
CFG와 달리 PEG는 모호할 수 없다. 문자열은 정확히 하나의 유효한 파스 트리를 갖거나 아예 갖지 않는다. PEG로 인식할 수 없는 문맥 자유 언어가 존재한다고 추측되지만, 아직 입증되지 않았다. PEG는 여러 해석 대안을 로컬에서 모호하지 않게 할 수 있는 컴퓨터 언어(및 로지반과 같은 인공 인간 언어)를 구문 분석하는 데 적합하지만, 모호성 해소가 전역적이어야 하는 자연어를 구문 분석하는 데는 덜 유용할 수 있다.
파싱 표현식은 각 문자열이 일치하거나 일치하지 않을 수 있는 일종의 패턴이다. 일치하는 경우, 파싱 표현식에 의해 소비된 문자열의 고유한 접두사(전체 문자열, 빈 문자열 또는 그 사이의 일부일 수 있음)가 있다. 이 접두사는 일반적으로 표현식과 일치하는 것으로 간주된다. 그러나 문자열이 파싱 표현식과 일치하는지 여부는 (선행 조건자 때문에) 소비된 부분 다음에 오는 부분에 따라 달라질 수 있다. 파싱 표현식 언어는 특정 파싱 표현식과 일치하는 모든 문자열의 집합이다.
파싱 표현식 문법은 명명된 파싱 표현식들의 모음으로, 서로를 참조할 수 있다. 파싱 표현식에서 그러한 참조의 효과는 마치 참조된 전체 파싱 표현식이 참조 위치에 주어진 것과 같다. 파싱 표현식 문법은 또한 지정된 시작 표현식을 가진다. 문자열이 시작 표현식과 일치하면 문법과 일치한다.
일치하는 문자열의 요소는 말단 기호 또는 줄여서 단말이라고 한다. 마찬가지로 파싱 표현식에 할당된 이름은 비말단 기호 또는 줄여서 비단말이라고 한다. 이러한 용어는 생성 문법에 설명적이지만, 파싱 표현식 문법의 경우 단순히 파싱 알고리즘에 대한 논의에서 거의 보편적으로 사용되기 때문에 유지되는 용어일 뿐이다.
파싱 표현식의 추상 구문과 구체 구문 모두 문헌과 이 문서에서 사용된다. 추상 구문은 본질적으로 수식이며 주로 이론적인 맥락에서 사용되는 반면, 구체 구문 파싱 표현식은 구문 분석기를 직접 제어하는 데 사용될 수 있다. 주된 구체 구문은 포드(Ford)가 정의한 것이지만, 많은 도구들이 자체 방언을 가지고 있다. 다른 도구들은 추상 구문 파싱 표현식의 프로그래밍 언어 기본 인코딩을 구체 구문으로 사용하는 데 더 가깝다.
원자 파싱 표현식.
다른 파싱 표현식을 포함하지 않는 두 가지 주요 파싱 표현식은 개별 단말 기호와 비단말 기호이다. 구체 구문에서 단말은 따옴표(홑따옴표 또는 겹따옴표) 안에 배치되는 반면, 따옴표가 없는 식별자는 비단말을 나타낸다:
"terminal" Nonterminal 'another terminal'
추상 구문에서는 형식화된 구분이 없으며, 대신 각 기호가 단말 또는 비단말 중 하나로 정의되어 있다고 가정하지만, 비단말에는 대문자를 사용하고 단말에는 소문자를 사용하는 것이 일반적인 관례이다.
구체 구문에는 단말 클래스에 대한 여러 형식도 있다:
추상 구문에서 이러한 형식은 보통 간결성을 위해 정확한 정의가 생략된 비단말로 형식화된다. 유니코드에는 수만 개의 문자(글자)가 있다. 반대로 이론적 논의에서는 복합 파싱 표현식을 사용하여 표현할 수 있는 개념에 대한 원자적 추상 구문을 도입하기도 한다. 이에는 다음이 포함된다:
구체 구문에서 따옴표로 묶인 단말과 괄호로 묶인 단말은 백슬래시 이스케이프를 사용하므로, "줄 바꿈 또는 캐리지 리턴"은 codice_6로 작성될 수 있다. 길이가 1보다 큰 따옴표로 묶인 단말의 추상 구문 대응물은 해당 단말들의 시퀀스이다. codice_7는 codice_8와 동일하다. 주된 구체 구문은 단말이 홑따옴표를 사용하는지 겹따옴표를 사용하는지에 따라 별개의 의미를 부여하지 않지만, 일부 방언은 하나를 대소문자 구분으로 처리하고 다른 하나는 대소문자 비구분으로 처리한다.
복합 파싱 표현식.
기존의 파싱 표현식 e, e1, e2가 주어지면 다음 연산자를 사용하여 새로운 파싱 표현식을 구성할 수 있다:
연산자 우선순위는의 표 1에 따라 다음과 같다:
구체 구문에서 파싱 표현식 문법은 단순히 비단말 정의의 시퀀스이며, 각 정의는 다음 형식을 가진다:
Identifier LEFTARROW Expression
codice_9는 정의되는 비단말이고, codice_10은 이 비단말이 참조하도록 정의된 파싱 표현식이다. codice_11는 방언에 따라 조금씩 다르지만, 일반적으로 codice_12, codice_13, codice_14, codice_15와 같은 왼쪽 화살표 또는 할당 기호이다. 이를 이해하는 한 가지 방법은 비단말에 대한 할당 또는 정의를 만드는 것으로 정확히 이해하는 것이다. 다른 방법은 문맥 자유 문법의 규칙에서 사용되는 오른쪽 화살표 →와의 대비로 이해하는 것이다. 파싱 표현식에서는 정보의 흐름이 표현식에서 비단말로 가는 것이지, 비단말에서 표현식으로 가는 것이 아니다.
수학적 객체로서 파싱 표현식 문법은 formula_2 튜플이며, 여기서 formula_3은 비단말 기호 집합, formula_4는 단말 기호 집합, formula_5는 formula_3에서 formula_7에 대한 파싱 표현식 집합으로의 함수, 그리고 formula_8는 시작 파싱 표현식이다. 일부 구체 구문 방언은 시작 표현식을 명시적으로 지정하지만, 주된 구체 구문은 대신 첫 번째로 정의된 비단말이 시작 표현식이라는 암묵적인 규칙을 가진다.
구체 구문 파싱 표현식 문법의 주된 방언에는 명시적인 정의 종결자나 정의 간의 구분자가 없다는 점에 주목할 필요가 있다. 새 정의를 새 줄에서 시작하는 것이 관례이지만, codice_10 내의 비단말 뒤에 codice_11가 오면 안 된다는 제약 조건을 추가하면 다음 정의의 codice_11만으로 경계를 찾는 것으로 충분하다. 그러나 일부 방언은 명시적인 종결자를 허용하거나 명시적으로 요구할 수 있다.
이것은 음이 아닌 정수에 다섯 가지 기본 연산을 적용하는 수학 공식을 인식하는 PEG이다.
Expr ← Sum
Sum ← Product (('+' / '-') Product)*
Power ← Value ('^' Power)?
Value ← [0-9]+ / '(' Expr ')'
위 예에서 단말 기호는 codice_19와 codice_20와 같이 홑따옴표 안의 문자로 표현된 텍스트 문자이다. 범위 codice_21는 codice_22부터 codice_23까지의 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 표현식 &amp;e는 하위 표현식 e를 호출하고, e가 성공하면 성공하고 e가 실패하면 실패하지만, 어떤 경우에도 입력을 소비하지 않는다.
not-predicate 표현식 !e는 e가 실패하면 성공하고 e가 성공하면 실패하며, 어떤 경우에도 입력을 소비하지 않는다.
더 많은 예시.
다음 재귀 규칙은 선택적 "else" 절이 항상 가장 안쪽의 "if"에 바인딩되도록 표준 C 스타일 if/then/else 문을 일치시킨다. 이는 '/' 연산자의 암시적 우선순위 때문이다. (문맥 자유 문법에서 이 구문은 고전적인 매달린 else 모호성을 발생시킨다.)
다음 재귀 규칙은 파스칼 스타일의 중첩 주석 구문인 와 일치한다. 가 임의의 단일 문자와 일치한다는 것을 기억하라.
C ← Begin N* End
End ← '*)'
N ← C / (!Begin !End .)
파싱 표현식 는 "foo" 텍스트와 일치하고 소비하지만, 그 뒤에 "bar" 텍스트가 오는 경우에만 그렇다. 파싱 표현식 는 "foo" 텍스트와 일치하지만, 그 뒤에 "bar" 텍스트가 오지 않는 경우에만 그렇다. 표현식 는 단일 "a"와 일치하지만, 임의로 긴 a 시퀀스 뒤에 b가 오는 시퀀스의 일부가 아닌 경우에만 그렇다.
파싱 표현식 는 임의 길이의 a와 b 시퀀스와 일치하고 소비한다. 생성 규칙 는 간단한 문맥 자유 "매칭 언어" formula_9를 설명한다.
다음 파싱 표현식 문법은 고전적인 비문맥 자유 언어 formula_10를 설명한다:
S ← &amp;(A 'c') 'a'+ B !.
파싱 표현식 문법으로 파서 구현하기.
모든 파싱 표현식 문법은 직접적으로 재귀 하향 파서로 변환될 수 있다. 그러나 문법 형식론이 제공하는 무제한 미리보기 기능 때문에 결과 파서는 최악의 경우 지수 시간 성능을 보일 수 있다.
어떤 파싱 표현식 문법이라도 팩랫 파서로 변환하여 더 나은 성능을 얻을 수 있다. 팩랫 파서는 항상 선형 시간으로 실행되지만, 훨씬 더 많은 저장 공간을 필요로 한다. 팩랫 파서는 구조적으로 재귀 하향 파서와 유사한 파서의 한 형태이다. 단, 파싱 과정에서 메모이제이션을 통해 모든 상호 재귀 파싱 함수의 중간 결과를 메모이제이션하여 각 파싱 함수가 주어진 입력 위치에서 최대 한 번만 호출되도록 한다. 이러한 메모이제이션 덕분에 팩랫 파서는 많은 문맥 자유 문법과 모든 파싱 표현식 문법(문맥 자유 언어를 나타내지 않는 일부 문법 포함)을 선형 시간에 파싱할 수 있다. 메모이제이션된 재귀 하향 파서의 예는 적어도 1993년부터 알려져 있다.
팩랫 파서의 성능 분석은 모든 메모이제이션된 결과를 저장할 충분한 메모리가 있다고 가정한다. 실제로는 메모리가 부족하면 일부 파싱 함수가 동일한 입력 위치에서 두 번 이상 호출될 수 있으며, 결과적으로 파서가 선형 시간보다 더 많은 시간을 소요할 수 있다.
LL 파서 및 LR 파서도 파싱 표현식 문법에서 구축할 수 있으며, 메모이제이션 없는 재귀 하향 파서보다 최악의 경우 성능이 더 좋다. 그러나 문법 형식론의 무제한 미리보기 기능은 이때 손실된다. 따라서 파싱 표현식 문법을 사용하여 표현할 수 있는 모든 언어가 LL 또는 LR 파서로 파싱될 수 있는 것은 아니다.
상향식 PEG 파싱.
피카 파서(pika parser)는 동적 계획법을 사용하여 PEG 규칙을 상향식 및 오른쪽에서 왼쪽으로 적용한다. 이는 일반적인 재귀 하향식 및 왼쪽에서 오른쪽 파싱 순서의 역이다. 역순으로 파싱하면 좌측 재귀 문제를 해결하여 좌측 재귀 규칙을 문법에 직접 사용할 수 있도록 하며, 구문 분석기에 최적의 오류 복구 기능을 부여한다. 이는 역사적으로 재귀 하향 파서에게 달성하기 어려웠던 것이다.
컴파일 불필요.
많은 구문 분석 알고리즘은 문법이 먼저 불투명한 실행 가능한 형태로, 종종 어떤 종류의 자동자로 컴파일되는 전처리 단계를 필요로 한다. 파싱 표현식은 직접 실행될 수 있다(이 문서에 표시된 인간이 읽을 수 있는 PEG를 평가하기 전에 S-표현식과 같은 더 기본 형식으로 변환하는 것이 일반적으로 여전히 권장되더라도).
정규 표현식과의 비교.
순수한 정규 표현식(즉, 유한 자동자를 사용하여 인식할 수 있는 언어를 설명하는 것)과 비교할 때 PEG는 훨씬 더 강력하다. 특히 PEG는 무제한 재귀를 처리할 수 있으므로 임의의 중첩 깊이까지 괄호를 일치시킨다. 정규 표현식은 기껏해야 고정된 깊이까지의 중첩을 추적할 수 있는데, 이는 유한 자동자(유한한 내부 상태 집합을 가짐)가 유한한 수의 다른 중첩 깊이만을 구별할 수 있기 때문이다. 더 이론적인 용어로, formula_11(0개 이상의 formula_12 다음에 동일한 수의 formula_13가 오는 모든 문자열의 언어)는 정규 언어가 아니지만, 다음 문법으로 쉽게 파싱 표현식 언어임을 알 수 있다.
start ← AB !.
AB ← ('a' AB 'b')?
여기서 codice_24는 시작 표현식이다. codice_5 부분은 "다음 문자가 없다"고 말함으로써 codice_26 다음에 입력이 끝남을 강제한다. 이를 위한 마법 제약 조건인 codice_27 또는 codice_28가 있는 정규 표현식과 달리 파싱 표현식은 기본 원시 자료형만을 사용하여 입력의 끝을 표현할 수 있다.
파싱 표현식의 codice_29, codice_30, codice_31는 정규 표현식의 그것들과 유사하지만, 차이점은 이들이 엄격히 탐욕 모드로 작동한다는 것이다. 이는 궁극적으로 codice_32가 순서 선택이기 때문이다. 결과적으로 정규 표현식으로는 일치하지만 파싱 표현식으로는 일치하지 않는 것이 있을 수 있다:
는 유효한 정규 표현식이자 유효한 파싱 표현식이다. 정규 표현식으로서는 codice_34와 일치하지만, 파싱 표현식으로서는 일치하지 않는다. 왜냐하면 codice_35가 codice_36와 일치하고, 그 다음 codice_37가 codice_38와 일치하여 codice_39에 아무것도 남기지 않아, 그 지점에서 시퀀스 일치가 실패하기 때문이다. codice_35가 빈 문자열과 일치하도록 "다시 시도"하는 것은 파싱 표현식의 의미론에 명시적으로 위배된다. 이것은 특정 일치 알고리즘의 예외적인 경우가 아니라, 추구하는 동작이다.
비결정론에 의존하는 정규 표현식조차도 해당 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에 따른 파싱은 이진 행렬 곱셈과 점근적으로 동일하다는 것이 입증되었다(따라서 이차 또는 삼차 시간 사이일 가능성이 높다).
명백히 문맥 자유가 아닌 형식 언어의 고전적인 예시 중 하나는 formula_14 언어이다. 즉, 임의의 수의 formula_12 다음에 동일한 수의 formula_13가 오고, 그 다음에 동일한 수의 formula_17가 오는 언어이다. 이것 또한 다음 문법으로 일치되는 파싱 표현식 언어이다.
start ← AB 'c'*
AB ← 'a' AB 'b' / &amp;(BC !.)
BC ← ('b' BC 'c')?
codice_26가 일치하려면, 첫 번째 formula_12의 연속 부분 뒤에 동일한 수의 formula_13가 와야 하며, 추가로 formula_12가 formula_13로 바뀌는 곳에서 codice_42가 일치해야 한다. 이는 해당 formula_13들 뒤에 동일한 수의 formula_17가 온다는 것을 의미한다.
메모리 소비.
PEG 파싱은 일반적으로 팩랫 파싱을 통해 수행되며, 이는 중복 파싱 단계를 제거하기 위해 메모이제이션을 사용한다. 팩랫 파싱은 LR 파서와 같이 파스 트리의 깊이에 비례하는 대신 전체 입력 크기에 비례하는 내부 스토리지를 필요로 한다. 이것이 중요한 차이인지 여부는 상황에 따라 달라진다. 파싱이 함수로 제공되는 서비스인 경우, 파서는 반환하기 전까지 전체 파스 트리를 저장했을 것이고, 이미 그 파스 트리는 일반적으로 전체 입력 크기에 비례하는 크기를 가질 것이다. 파싱이 대신 제너레이터로 제공되는 경우 파스 트리의 일부만 메모리에 유지할 수 있지만, 이것의 타당성은 문법에 따라 달라진다. 파싱 표현식 문법은 전체 입력을 소비한 후에야 파서가 시작 부분으로 퇴각검색해야 함을 발견하도록 설계될 수 있으며, 이는 다시 전체 입력 크기에 비례하는 스토리지를 필요로 할 수 있다.