hotchpotch/wikipedia-multilingual-ir-pairs huggingface dataset:
LR 파서 개요
축소는 가장 최근에 파싱된 것들을 미리 보기 심볼 바로 왼쪽에 재구성한다. 따라서 이미 파싱된 항목 목록은 스택처럼 작동한다. 이 파스 스택은 오른쪽으로 커진다. 스택의 베이스 또는 바닥은 왼쪽에 있으며 가장 왼쪽의 가장 오래된 파싱 조각을 보유한다. 모든 축소 단계는 가장 오른쪽의 가장 최신 파싱 조각에만 작동한다. (이 누적 파스 스택은 하향식 파서가 사용하는 예측적이고 왼쪽으로 성장하는 파스 스택과는 매우 다르다.)
6단계에서는 여러 부분을 가진 문법 규칙을 적용한다.
Products → Products * Value
LR 파서 개요
이것은 파싱된 구문 "... Products * Value"를 담고 있는 스택 상단과 일치한다. 축소 단계는 이 규칙의 오른쪽 부분인 "Products * Value"의 인스턴스를 규칙의 왼쪽 부분 심볼, 여기서는 더 큰 Products로 대체한다. 파서가 완전한 파스 트리를 구축하면 내부 Products, *, Value에 대한 세 개의 트리가 Products에 대한 새로운 트리 루트에 의해 결합된다. 그렇지 않으면 내부 Products와 Value의 의미론적 세부 정보가 이후 컴파일러 단계로 출력되거나, 새로운 Products 심볼에 결합되어 저장된다.
LR 파서 개요
LR 파서에서 시프트 및 리듀스 결정은 단순히 단일 최상위 스택 심볼뿐만 아니라 이전에 파싱된 모든 것의 전체 스택을 기반으로 할 수 있다. 만약 영리하지 못한 방식으로 이루어진다면, 이는 더 긴 입력에 대해 점점 더 느려지는 매우 느린 파서를 초래할 수 있다. LR 파서는 모든 관련 왼쪽 컨텍스트 정보를 LR(0) 파서 상태라는 단일 숫자로 요약하여 일정한 속도로 이를 수행한다. 각 문법 및 LR 분석 방법에 대해 고정된(유한한) 수의 이러한 상태가 있다. 이미 파싱된 심볼을 저장하는 것 외에도 파스 스택은 해당 지점까지 도달한 상태 번호를 기억한다.
LR 파서 개요
모든 파싱 단계에서 전체 입력 텍스트는 이전에 파싱된 구문 스택, 현재 미리 보기 심볼, 그리고 나머지 스캔되지 않은 텍스트로 나뉜다. 파서의 다음 동작은 현재 LR(0) 상태 번호(스택의 가장 오른쪽)와 미리 보기 심볼에 의해 결정된다. 아래 단계에서 모든 검은색 세부 정보는 다른 비-LR 시프트-리듀스 파서와 정확히 동일하다. LR 파서 스택은 스택의 왼쪽에 있는 검은색 구문과 다음에 예상되는 구문 가능성을 요약하는 보라색 상태 정보를 추가한다. LR 파서 사용자는 일반적으로 상태 정보를 무시할 수 있다. 이 상태들은 나중에 설명한다.
초기 0단계에서 입력 스트림 "A * 2 + 1"은 다음과 같이 나뉜다.
파스 스택은 초기 상태 0만 포함한 채 시작한다. 상태 0이 미리 보기 id를 보면, 해당 id를 스택에 시프트하고 다음 입력 심볼 *를 스캔하여 상태 9로 진행해야 함을 안다.
4단계에서 총 입력 스트림 "A * 2 + 1"은 현재 다음과 같이 나뉜다.
LR 파서 개요
스택된 구문에 해당하는 상태는 0, 4, 5이다. 스택의 현재 가장 오른쪽 상태는 상태 5이다. 상태 5가 미리 보기 int를 보면, 해당 int를 스택에 자체 구문으로 시프트하고 다음 입력 심볼 +를 스캔하여 상태 8로 진행해야 함을 안다.
12단계에서 입력 스트림 전체가 사용되었지만 부분적으로만 정리되었다. 현재 상태는 3이다. 상태 3이 미리 보기 eof를 보면, 완료된 문법 규칙을 적용해야 함을 안다.
Sums → Sums + Products
스택의 가장 오른쪽 세 구문(Sums, +, Products)을 하나로 결합한다. 상태 3 자체는 다음 상태가 무엇이어야 하는지 모른다. 이는 축소되는 구문의 바로 왼쪽에 있는 상태 0으로 돌아가서 찾는다. 상태 0이 이 새로운 Sums의 완료된 인스턴스를 보면, 상태 1로 (다시) 진행한다. 오래된 상태를 참조하는 것이 바로 스택에 현재 상태만 유지하는 대신 모든 상태를 유지하는 이유이다.
LR 파서 개요
LR 파서는 입력 언어의 구문을 패턴 집합으로 공식적으로 정의하는 문법으로부터 구성된다. 문법은 숫자의 크기 또는 전체 프로그램의 컨텍스트에서 이름과 그 정의의 일관된 사용과 같은 모든 언어 규칙을 다루지 않는다. LR 파서는 심볼의 로컬 패턴만을 다루는 문맥 자유 문법을 사용한다.
여기서 사용된 예제 문법은 자바 또는 C 언어의 작은 부분 집합이다.
r0: Goal → Sums eof
r1: Sums → Sums + Products
r2: Sums → Products
r3: Products → Products * Value
r4: Products → Value
r5: Value → int
r6: Value → id
문법의 종결자는 어휘 스캐너에 의해 입력 스트림에서 발견되는 다중 문자 심볼 또는 '토큰'이다. 여기에는 임의의 정수 상수에 대한 + * 및 int, 임의의 식별자 이름에 대한 id, 입력 파일의 끝에 대한 eof가 포함된다. 문법은 int 값이나 id 스펠링이 무엇인지, 공백이나 줄 바꿈에 대해서는 신경 쓰지 않는다. 문법은 이러한 종결자를 사용하지만 정의하지는 않는다. 이들은 항상 파스 트리의 리프 노드(하단 덤불 끝)이다.
LR 파서 개요
Sums와 같이 대문자로 시작하는 용어는 비종결자이다. 이는 언어의 개념 또는 패턴에 대한 이름이다. 이들은 문법에 정의되어 있으며 입력 스트림 자체에서는 결코 발생하지 않는다. 이들은 항상 파스 트리의 내부 노드(하단 위)이다. 이들은 파서가 어떤 문법 규칙을 적용한 결과로만 발생한다. 일부 비종결자는 두 개 이상의 규칙으로 정의된다. 이들은 대체 패턴이다. 규칙은 자신을 참조할 수 있으며, 이를 재귀라고 한다. 이 문법은 재귀 규칙을 사용하여 반복되는 수학 연산자를 처리한다. 완전한 언어의 문법은 재귀 규칙을 사용하여 목록, 괄호 표현식 및 중첩된 문장을 처리한다.
어떤 주어진 컴퓨터 언어도 여러 다른 문법으로 기술될 수 있다. LR(1) 파서는 많은 일반적인 문법을 처리할 수 있지만 전부는 아니다. 일반적으로 LR(1) 파싱 및 생성기 도구의 제한에 맞게 문법을 수동으로 수정하는 것이 가능하다.
LR 파서 개요
LR 파서의 문법은 그 자체로 모호하지 않거나 또는 우선순위 규칙에 의해 보강되어야 한다. 이는 언어의 주어진 유효한 예시에 문법을 적용하는 유일하게 올바른 방법이 단 하나의 의미를 가진 고유한 파스 트리를 생성하고 해당 예시에 대한 고유한 시프트/리듀스 동작 순서를 생성한다는 의미이다. LR 파싱은 단어의 상호작용에 의존하는 모호한 문법을 가진 인간 언어에는 유용한 기술이 아니다. 인간 언어는 일반화된 LR 파서, 얼리 파서 또는 CYK 알고리즘과 같이 한 번에 가능한 모든 파스 트리를 동시에 계산할 수 있는 파서에 의해 더 잘 처리된다.
대부분의 LR 파서는 테이블 기반이다. 파서의 프로그램 코드는 모든 문법과 언어에 대해 동일한 간단한 일반 루프이다. 문법과 그 구문적 함의에 대한 지식은 파스 테이블(또는 파싱 테이블)이라고 불리는 불변 데이터 테이블에 인코딩된다. 테이블의 항목은 파서 상태와 미리보기 심볼의 모든 유효한 조합에 대해 시프트할지 또는 리듀스할지(그리고 어떤 문법 규칙에 의해)를 보여준다. 파스 테이블은 또한 현재 상태와 다음 심볼이 주어졌을 때 다음 상태를 계산하는 방법도 알려준다.
LR 파서 개요
파스 테이블은 문법보다 훨씬 크다. LR 테이블은 큰 문법에 대해 손으로 정확하게 계산하기 어렵다. 그래서 비손과 같은 파서 생성기 도구에 의해 문법에서 기계적으로 파생된다.
상태 및 파싱 테이블이 생성되는 방법에 따라 결과 파서는 SLR(Simple LR) 파서, LALR(Look-Ahead LR) 파서 또는 정규 LR 파서라고 불린다. LALR 파서는 SLR 파서보다 더 많은 문법을 처리한다. 정규 LR 파서는 훨씬 더 많은 문법을 처리하지만, 더 많은 상태와 훨씬 더 큰 테이블을 사용한다. 예제 문법은 SLR이다.
LR 파스 테이블은 2차원이다. 각 현재 LR(0) 파서 상태는 자체 행을 가진다. 각 가능한 다음 심볼은 자체 열을 가진다. 상태와 다음 심볼의 일부 조합은 유효한 입력 스트림에 대해 불가능하다. 이러한 빈 셀은 구문 오류 메시지를 유발한다.
테이블의 액션 왼쪽 절반은 미리보기 종결자 열을 가진다. 이 셀들은 다음 파서 액션이 시프트(상태 n으로)인지 또는 리듀스(문법 규칙 rn에 의해)인지 결정한다.
LR 파서 개요
테이블의 고투 오른쪽 절반은 비종결자 열을 가진다. 이 셀들은 어떤 리덕션의 좌변이 해당 심볼의 예상되는 새 인스턴스를 생성한 후 어떤 상태로 진행할지를 보여준다. 이는 시프트 액션과 비슷하지만 비종결자를 위한 것이다. 미리보기 종결자 심볼은 변경되지 않는다.
"현재 규칙"이라는 테이블 열은 파서 생성기에 의해 도출된 각 상태에 대한 의미와 구문 가능성을 문서화한다. 파싱 시 실제로 사용되는 테이블에는 포함되지 않는다. •(핑크 점) 마커는 파서가 현재 부분적으로 인식된 문법 규칙 내에서 어디에 있는지 보여준다. • 왼쪽에 있는 항목들은 파싱되었으며, 오른쪽에 있는 항목들은 곧 예상된다. 파서가 가능성을 단일 규칙으로 좁히지 않은 경우 상태는 여러 개의 현재 규칙을 가질 수 있다.
위의 상태 2에서 파서는 문법 규칙의 +를 방금 찾아서 시프트했다.
r1: Sums → Sums + • Products
LR 파서 개요
다음 예상 구문은 Products이다. Products는 종결자 int 또는 id로 시작한다. 미리 보기가 이 둘 중 하나인 경우 파서는 이들을 시프트하고 각각 상태 8 또는 9로 진행한다. Products가 발견되면 파서는 합산 항목의 전체 목록을 축적하고 규칙 r0의 끝을 찾기 위해 상태 3으로 진행한다. Products는 비종결자 Value로도 시작할 수 있다. 다른 미리 보기 또는 비종결자의 경우 파서는 구문 오류를 알린다.
상태 3에서 파서는 방금 Products 구문을 찾았는데, 이는 두 가지 가능한 문법 규칙에서 비롯될 수 있다.
r1: Sums → Sums + Products •
r3: Products → Products • * Value
r1과 r3 사이의 선택은 이전 구문을 뒤로만 살펴서는 결정할 수 없다. 파서는 무엇을 해야 할지 알아내기 위해 미리보기 심볼을 확인해야 한다. 미리보기가 *이면 규칙 3에 있으므로 파서는 *를 시프트하고 상태 5로 진행한다. 미리보기가 eof이면 규칙 1과 규칙 0의 끝에 있으므로 파서는 완료된다.
위의 상태 9에서 비어있지 않고 오류가 아닌 모든 셀은 동일한 축소 r6에 대한 것이다. 일부 파서는 이러한 간단한 경우에 미리보기 심볼을 확인하지 않아 시간과 테이블 공간을 절약한다. 구문 오류는 약간 나중에, 일부 무해한 축소 후에 감지되지만, 다음 시프트 동작 또는 파서 결정 전에는 여전히 감지된다.
개별 테이블 셀에는 여러 대안 동작이 있어서는 안 된다. 그렇지 않으면 파서는 추측 및 백트래킹으로 비결정적이 될 수 있다. 문법이 LR(1)이 아닌 경우, 일부 셀에는 가능한 시프트 동작과 축소 동작 간의 시프트/축소 충돌 또는 여러 문법 규칙 간의 축소/축소 충돌이 발생한다. LR(k) 파서는 첫 번째를 넘어 추가 미리보기 심볼을 확인하여 이러한 충돌을 (가능한 경우) 해결한다.
LR 파서는 시작 상태 0만 포함하는 거의 비어있는 파스 스택으로 시작하며, 미리보기는 입력 스트림의 첫 번째 스캔된 심볼을 담고 있다. 그런 다음 파서는 완료되거나 구문 오류에 갇힐 때까지 다음 루프 단계를 반복한다.
파스 스택의 최상위 상태는 특정 상태 s이고, 현재 미리보기는 특정 종결자 t이다. 미리보기 액션 테이블의 s행 t열에서 다음 파서 액션을 찾는다. 해당 액션은 시프트, 리듀스, 수락 또는 오류 중 하나이다.
일치하는 종결자 t를 파스 스택에 시프트하고 다음 입력 심볼을 미리보기 버퍼로 스캔한다.
새로운 현재 상태로 다음 상태 n을 파스 스택에 푸시한다.
일치하는 최상위 L개 심볼(및 파스 트리 및 관련 상태 번호)을 파스 스택에서 제거한다.
이는 Lhs 심볼의 인스턴스를 예상하던 이전 상태 p를 노출한다.
L개의 파스 트리를 Lhs라는 새 루트 심볼을 가진 하나의 파스 트리로 결합한다.
LHS 고투 테이블의 p행 Lhs 열에서 다음 상태 n을 찾는다.
Lhs 심볼과 트리를 파스 스택에 푸시한다.
새로운 현재 상태로 다음 상태 n을 파스 스택에 푸시한다.
미리보기와 입력 스트림은 변경되지 않는다.
LR 파서 스택은 일반적으로 LR(0) 오토마톤 상태만 저장한다. 왜냐하면 문법 심볼은 이들로부터 파생될 수 있기 때문이다(오토마톤에서 어떤 상태로의 모든 입력 전이는 동일한 심볼로 표시되며, 이는 이 상태와 연관된 심볼이다). 게다가 파싱 결정을 내릴 때 상태가 가장 중요하므로 이러한 심볼은 거의 필요하지 않다.
LR 파서 LR 생성기 분석
이 문서의 이 섹션은 LR 파서 생성기 사용자 대부분은 건너뛸 수 있다.
예제 파스 테이블의 상태 2는 부분적으로 파싱된 규칙을 위한 것이다.
r1: Sums → Sums + • Products
이는 파서가 더 큰 Sums를 찾으면서 Sums를 본 다음 +를 보면서 여기에 어떻게 도달했는지 보여준다. • 마커는 규칙의 시작을 지나 전진했다. 또한 파서가 완전한 Products를 다음에 찾아 궁극적으로 규칙을 완료할 것으로 예상하는 방법도 보여준다. 그러나 해당 Products의 모든 부분을 파싱하는 방법에 대한 더 자세한 정보가 필요하다.
상태에 대한 부분적으로 파싱된 규칙을 "코어 LR(0) 항목"이라고 한다. 파서 생성기는 예상되는 Products를 구축하는 데 필요한 모든 가능한 다음 단계에 대한 추가 규칙 또는 항목을 추가한다.
r3: Products → • Products * Value
r4: Products → • Value
r5: Value → • int
r6: Value → • id
LR 파서 LR 생성기 분석
• 마커는 이러한 추가된 각 규칙의 시작 부분에 있다. 파서는 아직 이들 중 어떤 부분도 확인하고 파싱하지 않았다. 이러한 추가 항목을 코어 항목의 "폐쇄"라고 한다. • 바로 뒤에 오는 각 비종결자 심볼에 대해 생성기는 해당 심볼을 정의하는 규칙을 추가한다. 이는 더 많은 • 마커와 경우에 따라 다른 후행 심볼을 추가한다. 이 폐쇄 과정은 모든 후행 심볼이 확장될 때까지 계속된다. 상태 2의 후행 비종결자는 Products로 시작한다. Value는 폐쇄에 의해 추가된다. 후행 종결자는 int와 id이다.
커널 및 폐쇄 항목은 함께 현재 상태에서 미래 상태로 진행하고 구문을 완료하는 모든 가능한 합법적인 방법을 보여준다. 만약 후행 심볼이 단 하나의 항목에만 나타난다면, • 마커가 전진된 단 하나의 핵심 항목을 포함하는 다음 상태로 이어진다. 따라서 int는 핵심을 가진 다음 상태 8로 이어진다.
r5: Value → int •
LR 파서 LR 생성기 분석
만약 동일한 후행 심볼이 여러 항목에 나타난다면, 파서는 어떤 규칙이 여기에 적용되는지 아직 알 수 없다. 따라서 해당 심볼은 • 마커가 전진된 상태에서 모든 나머지 가능성을 보여주는 다음 상태로 이어진다. Products는 r1과 r3 모두에 나타난다. 따라서 Products는 핵심을 가진 다음 상태 3으로 이어진다.
r1: Sums → Sums + Products •
r3: Products → Products • * Value
쉽게 말하면, 파서가 단일 Products를 보았다면 작업이 완료되었거나, 곱해야 할 항목이 더 많을 수 있다는 의미이다. 모든 핵심 항목은 • 마커 앞에 동일한 심볼을 가진다. 이 상태로의 모든 전이는 항상 동일한 심볼로 이루어진다.
일부 전이는 이미 열거된 코어 및 상태로 이어진다. 다른 전이는 새로운 상태로 이어진다. 생성기는 문법의 목표 규칙으로 시작한다. 거기서부터 모든 필요한 상태가 발견될 때까지 알려진 상태와 전이를 계속 탐색한다.
LR 파서 LR 생성기 분석
이러한 상태들은 k=0, 즉 미리보기가 없음을 사용하기 때문에 "LR(0)" 상태라고 불린다. 입력 심볼의 확인은 심볼이 시프트될 때만 발생한다. 축소에 대한 미리보기 확인은 파스 테이블에 의해 별도로 수행되며, 열거된 상태 자체에 의해 수행되지 않는다.
파스 테이블은 가능한 모든 LR(0) 상태와 그 전이를 기술한다. 이들은 유한 상태 기계 (FSM)를 형성한다. FSM은 스택을 사용하지 않고 간단한 중첩되지 않은 언어를 파싱하기 위한 간단한 엔진이다. 이 LR 애플리케이션에서 FSM의 수정된 "입력 언어"는 종결자와 비종결자 심볼을 모두 가지며, 전체 LR 파스의 부분적으로 파싱된 스택 스냅샷을 포함한다.
파스 단계 예시의 5단계를 다시 살펴보자.
LR 파서 LR 생성기 분석
구문 분석 스택은 시작 상태 0에서 상태 4로, 그리고 5를 거쳐 현재 상태 8로 이어지는 일련의 상태 전환을 보여준다. 구문 분석 스택의 심볼은 이러한 전환에 대한 시프트 또는 고투 심볼이다. 이를 다른 방식으로 보면, 유한 상태 기계는 스트림 "Products * int + 1"을 (또 다른 스택을 사용하지 않고) 스캔하고 다음에 축소되어야 할 가장 왼쪽의 완전한 구문을 찾을 수 있다. 그리고 그것이 바로 그 역할이다!
원래의 파싱되지 않은 언어가 중첩과 재귀를 포함하고 분석기에 스택이 분명히 필요한데, 단순한 FSM이 어떻게 이를 수행할 수 있을까? 핵심은 스택 상단의 왼쪽에 있는 모든 것이 이미 완전히 축소되었다는 점이다. 이는 해당 구문에서 모든 루프와 중첩을 제거한다. FSM은 구문의 모든 오래된 시작 부분을 무시하고, 다음에 완료될 수 있는 가장 새로운 구문만 추적할 수 있다. LR 이론에서 이를 설명하는 모호한 이름은 "유효 접두사"이다.
상태와 전이는 파스 테이블의 시프트 동작과 고투 동작에 필요한 모든 정보를 제공한다. 생성기는 또한 각 리듀스 동작에 대한 예상 미리보기 집합을 계산해야 한다.
LR 파서 LR 생성기 분석
SLR 파서에서는 이러한 미리보기 집합이 개별 상태와 전이를 고려하지 않고 문법에서 직접 결정된다. 각 비종결자 S에 대해 SLR 생성기는 S의 어떤 발생 직후에 올 수 있는 모든 종결자 집합인 Follows(S)를 계산한다. 파스 테이블에서 S로의 각 축소는 Follow(S)를 해당 LR(1) 미리보기 집합으로 사용한다. 이러한 팔로우 집합은 LL 하향식 파서의 생성기에서도 사용된다. 팔로우 집합을 사용할 때 시프트/리듀스 또는 리듀스/리듀스 충돌이 없는 문법을 SLR 문법이라고 한다.
LR 파서 LR 생성기 분석
LALR 파서는 SLR 파서와 동일한 상태를 가지지만, 각 개별 상태에 대해 최소한으로 필요한 축소 미리보기를 계산하는 더 복잡하고 정확한 방법을 사용한다. 문법의 세부 사항에 따라 이는 SLR 파서 생성기가 계산한 팔로우 집합과 동일하거나 SLR 미리보기의 부분 집합이 될 수 있다. 일부 문법은 LALR 파서 생성기에는 적합하지만 SLR 파서 생성기에는 적합하지 않다. 이는 팔로우 집합을 사용할 때 문법에 가짜 시프트/리듀스 또는 리듀스/리듀스 충돌이 있지만 LALR 생성기가 계산한 정확한 집합을 사용할 때는 충돌이 없을 때 발생한다. 이때 해당 문법은 LALR(1)이지만 SLR은 아니다.
LR 파서 LR 생성기 분석
SLR 또는 LALR 파서는 중복 상태를 피한다. 그러나 이러한 최소화는 필수가 아니며, 때로는 불필요한 미리보기 충돌을 일으킬 수 있다. 정규 LR 파서는 중복된(또는 "분할된") 상태를 사용하여 비종결자 사용의 왼쪽 및 오른쪽 컨텍스트를 더 잘 기억한다. 문법에서 심볼 S의 각 발생은 자체 미리보기 집합으로 독립적으로 처리되어 축소 충돌을 해결하는 데 도움이 된다. 이는 몇몇 문법을 더 많이 처리한다. 불행히도, 문법의 모든 부분에 대해 수행되면 파스 테이블의 크기가 크게 확대된다. 이러한 상태 분할은 비종결자의 두 개 이상의 명명된 복사본을 만들어서 어떤 SLR 또는 LALR 파서에서도 수동으로, 그리고 선택적으로 수행할 수 있다. 정규 LR 생성기에는 충돌이 없지만 LALR 생성기에는 충돌이 있는 문법을 LR(1)이라고 하지만 LALR(1)도 SLR도 아니다.
LR 파서 LR 생성기 분석
SLR, LALR, 정규 LR 파서는 입력 스트림이 올바른 언어일 때 정확히 동일한 시프트 및 리듀스 결정을 내린다. 입력에 구문 오류가 있을 때 LALR 파서는 정규 LR 파서보다 오류를 감지하기 전에 몇 가지 추가 (무해한) 리듀스를 수행할 수 있다. 그리고 SLR 파서는 더 많은 리듀스를 수행할 수도 있다. 이는 SLR 및 LALR 파서가 해당 특정 상태에 대한 실제 최소 미리보기 심볼에 대한 관대한 상위 집합 근사를 사용하기 때문에 발생한다.
LR 파서는 프로그램의 첫 번째 구문 오류에 대해 다소 도움이 되는 오류 메시지를 생성할 수 있다. 예상치 못한 잘못된 미리보기 심볼 대신 다음에 나타날 수 있었던 모든 종결자 심볼을 단순히 열거함으로써 말이다. 그러나 이는 파서가 나머지 입력 프로그램을 파싱하여 추가적인 독립적인 오류를 찾는 데 도움이 되지 않는다. 파서가 첫 번째 오류에서 잘못 복구하면 다른 모든 것을 잘못 파싱하여 쓸모없는 잘못된 오류 메시지의 연쇄를 생성할 가능성이 매우 높다.
LR 파서 LR 생성기 분석
yacc 및 Bison 파서 생성기에서 파서는 현재 문장을 포기하고 오류 주변의 파싱된 구문과 미리보기 토큰을 버리고 세미콜론이나 중괄호와 같은 신뢰할 수 있는 문장 수준 구분 기호에서 파싱을 재동기화하는 임시 메커니즘을 가지고 있다. 이는 파서와 컴파일러가 프로그램의 나머지 부분을 검토하는 데 종종 잘 작동한다.
많은 구문 코딩 오류는 간단한 오타 또는 사소한 심볼의 생략이다. 일부 LR 파서는 이러한 일반적인 경우를 감지하고 자동으로 복구하려고 시도한다. 파서는 오류 지점에서 가능한 모든 단일 심볼 삽입, 삭제 또는 대체를 열거한다. 컴파일러는 각 변경 사항으로 시험 파싱을 수행하여 제대로 작동하는지 확인한다. (이는 파서에서 일반적으로 필요 없는 파스 스택 및 입력 스트림의 스냅샷으로의 백트래킹을 필요로 한다.) 최상의 복구가 선택된다. 이는 매우 유용한 오류 메시지를 제공하고 파싱을 잘 재동기화한다. 그러나 이 복구는 입력 파일을 영구적으로 수정할 만큼 신뢰할 수 없다. 구문 오류 복구는 파스 테이블과 명시적 데이터 스택을 가진 파서(예: LR)에서 일관되게 수행하기 가장 쉽다.
LR 파서 LR 생성기 분석
LR 파서 생성기는 파서 상태와 미리보기 심볼의 각 조합에 대해 무엇이 발생해야 하는지 결정한다. 이러한 결정은 일반적으로 읽기 전용 데이터 테이블로 변환되어 문법 및 상태에 독립적인 일반 파서 루프를 구동한다. 그러나 이러한 결정을 활성 파서로 전환하는 다른 방법도 있다.
일부 LR 파서 생성기는 파스 테이블 대신 각 상태에 대해 별도로 맞춤형 프로그램 코드를 생성한다. 이 파서들은 테이블 기반 파서의 일반 파서 루프보다 몇 배 더 빠르게 실행될 수 있다. 가장 빠른 파서는 생성된 어셈블러 코드를 사용한다.
재귀 상승 파서 변형에서는 명시적 파스 스택 구조가 서브루틴 호출에 의해 사용되는 암시적 스택으로 대체된다. 리덕션은 여러 수준의 서브루틴 호출을 종료시키는데, 이는 대부분의 언어에서는 서투른 일이다. 따라서 재귀 상승 파서는 일반적으로 재귀 하향 파서보다 느리고 덜 명확하며 수동으로 수정하기 어렵다.
또 다른 변형은 파스 테이블을 프롤로그와 같은 비절차적 언어의 패턴 매칭 규칙으로 대체한다.
GLR 일반화된 LR 파서는 LR 상향식 기술을 사용하여 입력 텍스트의 가능한 모든 파싱을 찾으며, 단 하나의 올바른 파싱만을 찾지 않는다. 이는 인간 언어에 사용되는 것과 같은 모호한 문법에 필수적이다. 여러 유효한 파스 트리는 백트래킹 없이 동시에 계산된다. GLR은 충돌 없는 LALR(1) 문법으로 쉽게 기술할 수 없는 컴퓨터 언어에 유용할 때가 있다.
LC 좌상향 파서는 LR 상향식 기술을 사용하여 대체 문법 규칙의 왼쪽 끝을 인식한다. 대안이 단일 가능한 규칙으로 좁혀지면 파서는 해당 규칙의 나머지를 파싱하기 위해 하향식 LL(1) 기술로 전환한다. LC 파서는 LALR 파서보다 파스 테이블이 작고 오류 진단이 더 좋다. 결정론적 LC 파서에 대한 널리 사용되는 생성기는 없다. 다중 파싱 LC 파서는 매우 큰 문법을 가진 인간 언어에 유용하다.
LR 파서는 도널드 커누스가 1965년에 우선순위 파서의 효율적인 일반화로 발명했다. 커누스는 LR 파서가 최악의 경우에도 효율적일 수 있는 가장 일반적인 목적의 파서임을 증명했다.
"LR(k) 문법은 문자열의 길이에 비례하는 실행 시간으로 효율적으로 파싱될 수 있다."
모든 k ≥ 1에 대해, "언어가 LR(k) 문법에 의해 생성될 수 있는 경우는 결정론적 [문맥 자유]인 경우에 한하며, 이는 LR(1) 문법에 의해 생성될 수 있는 경우와 동일하다."
다른 말로 하면, 효율적인 단일 패스 파서가 가능할 만큼 합리적인 언어라면 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의 알파벳의 심볼이 아니다.
LR 파서 추가 예제 1 + 1
이 LR 파싱 예시는 목표 심볼 E를 가진 다음 작은 문법을 사용한다.
(1)   E → E * B
(2)   E → E + B
(3)   E → B
(4)   B → 0
(5)   B → 1
다음 입력을 파싱한다.
1 + 1
이 문법에 대한 두 LR(0) 파싱 테이블은 다음과 같다.
액션 테이블은 파서의 상태와 종결자(입력 스트림의 끝을 나타내는 특수 종결자 $ 포함)로 색인화되며 세 가지 유형의 액션을 포함한다.
고투 테이블은 파서의 상태와 비종결자로 인덱싱되며 특정 비종결자를 인식한 경우 파서의 다음 상태가 무엇인지를 단순히 나타낸다. 이 테이블은 모든 축소 후에 다음 상태를 알아내는 데 중요하다. 축소 후에는 스택의 맨 위(즉, 현재 상태)와 축소된 규칙의 LHS(즉, 비종결자)에 대한 고투 테이블 항목을 찾아 다음 상태를 찾는다.
아래 표는 과정의 각 단계를 보여준다. 여기서 상태는 스택의 맨 위(가장 오른쪽 요소) 요소를 나타내며, 다음 액션은 위 액션 테이블을 참조하여 결정된다. 입력 스트림의 끝을 나타내기 위해 입력 문자열에 $가 추가된다.
LR 파서 추가 예제 1 + 1
파서는 초기 상태('0')만 포함된 스택으로 시작한다.
[0]
파서가 입력 문자열에서 처음 보는 심볼은 '1'이다. 다음 액션(시프트, 리듀스, 수락 또는 오류)을 찾기 위해 액션 테이블은 현재 상태(스택 맨 위에 있는 것)인 0과 현재 입력 심볼인 '1'로 인덱싱된다. 액션 테이블은 상태 2로 시프트하도록 지정하므로 상태 2가 스택에 푸시된다(다시 말하지만, 모든 상태 정보는 스택에 있으므로 "상태 2로 시프트"하는 것은 2를 스택에 푸시하는 것과 동일하다). 결과 스택은 다음과 같다.
[0 '1' 2]
스택의 맨 위는 2이다. 심볼(예: '1', B)을 설명하기 위해 다음 상태로의 전환을 유발한 원인이 표시되지만, 엄밀히 말하면 스택의 일부는 아니다.
LR 파서 추가 예제 1 + 1
상태 2에서 액션 테이블은 문법 규칙 5를 사용하여 축소하라고 한다(파서가 입력 스트림에서 어떤 터미널을 보든지 상관없이). 이는 파서가 규칙 5의 오른쪽 부분을 방금 인식했음을 의미한다. 이 경우 파서는 출력 스트림에 5를 쓰고, 스택에서 한 상태를 팝하고(규칙의 오른쪽 부분에 심볼 하나가 있기 때문), 상태 0과 B에 대한 고투 테이블의 셀에서 새 상태, 즉 상태 4를 푸시한다. 결과 스택은 다음과 같다.
[0 B 4]
하지만 상태 4에서 액션 테이블은 파서가 이제 규칙 3으로 축소해야 한다고 말한다. 그래서 출력 스트림에 3을 쓰고, 스택에서 상태 하나를 팝하고, 상태 0과 E에 대한 고투 테이블에서 새 상태인 상태 3을 찾는다. 결과 스택은 다음과 같다.
[0 E 3]
파서가 다음에 보는 종결자는 '+'이고, 액션 테이블에 따르면 상태 6으로 시프트해야 한다.
[0 E 3 '+' 6]
결과 스택은 비종결자 E 뒤에 종결자 '+'를 읽은 유한 상태 기계의 기록으로 해석될 수 있다. 이 오토마톤의 전이 테이블은 액션 테이블의 시프트 액션과 고투 테이블의 고투 액션으로 정의된다.
LR 파서 추가 예제 1 + 1
다음 종결자는 '1'이며, 이는 파서가 시프트를 수행하여 상태 2로 이동함을 의미한다.
[0 E 3 '+' 6 '1' 2]
이전의 '1'과 마찬가지로 이 '1'도 B로 축소되어 다음 스택을 제공한다.
[0 E 3 '+' 6 B 8]
스택은 비종결자 E를 읽은 후 '+'와 비종결자 B를 읽은 유한 오토마톤의 상태 목록에 해당한다. 상태 8에서 파서는 항상 규칙 2로 축소를 수행한다. 스택의 최상위 3개 상태는 규칙 2의 오른쪽에 있는 3개 심볼에 해당한다. 이번에는 스택에서 3개 요소를 팝하고(규칙의 오른쪽에 3개 심볼이 있기 때문) E와 0에 대한 고투 상태를 찾아 상태 3을 다시 스택에 푸시한다.
[0 E 3]
마지막으로, 파서는 입력 스트림에서 '$'(입력 끝 심볼)를 읽는데, 이는 액션 테이블(현재 상태는 3)에 따르면 파서가 입력 문자열을 수락한다는 것을 의미한다. 그 때 출력 스트림에 기록된 규칙 번호는 [5, 3, 5, 2]가 되며, 이는 "1 + 1" 문자열의 역 가장 오른쪽 파생이다.
LR 파서 LR(0) 파싱 테이블 구축
이러한 파싱 테이블의 구성은 LR(0) 아이템(여기서는 간단히 아이템이라고 함) 개념을 기반으로 한다. 이는 오른쪽 부분에 특수 점이 추가된 문법 규칙이다. 예를 들어, E → E + B 규칙에는 다음과 같은 4가지 해당 아이템이 있다.
E → • E + B
E → E • + B
E → E + • B
E → E + B •
A → ε 형태의 규칙은 단일 아이템 A → •만을 가진다. 예를 들어, 아이템 E → E • + B는 파서가 입력 스트림에서 E에 해당하는 문자열을 인식했으며 이제 '+' 뒤에 B에 해당하는 다른 문자열을 읽을 것으로 예상함을 나타낸다.
파서의 상태를 단일 항목으로 특징짓는 것은 일반적으로 불가능하다. 왜냐하면 파서가 축소를 위해 어떤 규칙을 사용할지 미리 알지 못할 수 있기 때문이다. 예를 들어, E → E * B 규칙도 있다면, E에 해당하는 문자열이 읽힌 후에는 E → E • + B와 E → E • * B 항목이 모두 적용된다. 따라서 이 경우 { E → E • + B, E → E • * B }와 같은 항목 집합으로 파서의 상태를 특징짓는 것이 편리하다.
LR 파서 LR(0) 파싱 테이블 구축
E → E + • B와 같이 비종결자 앞에 점이 있는 항목은 파서가 다음에 비종결자 B를 파싱할 것으로 예상함을 나타낸다. 항목 집합이 파서가 파싱 중일 수 있는 모든 가능한 규칙을 포함하도록 하려면, B 자체를 어떻게 파싱할지를 설명하는 모든 항목을 포함해야 한다. 이는 B → 1 및 B → 0과 같은 규칙이 있는 경우 항목 집합에 B → • 1 및 B → • 0 항목도 포함되어야 함을 의미한다. 일반적으로 다음과 같이 공식화할 수 있다.
항목 집합에 A → v • Bw 형태의 항목이 있고 문법에 B → w' 형태의 규칙이 있다면, B → • w' 항목도 항목 집합에 포함되어야 한다.
따라서 점 앞에 있는 모든 비종결자가 고려될 때까지 모든 적절한 항목을 재귀적으로 추가하여 모든 항목 집합을 확장할 수 있다. 최소 확장을 항목 집합의 폐쇄라고 하며 I가 항목 집합일 때 clos(I)로 쓴다. 실제로 시작 상태에서 도달할 수 있는 항목 집합만 테이블에 포함되지만, 이 폐쇄된 항목 집합이 파서의 상태로 간주된다.
LR 파서 LR(0) 파싱 테이블 구축
다른 상태 간의 전이가 결정되기 전에 문법은 추가 규칙으로 확장된다.
(0) S → E eof
여기서 S는 새로운 시작 심볼이고 E는 이전 시작 심볼이다. 파서는 입력 문자열 전체를 수락했을 때 정확히 이 규칙을 축소에 사용할 것이다.
이 예제에서는 위와 동일한 문법이 다음과 같이 확장된다.
(0) S → E eof
(1) E → E * B
(2) E → E + B
(3) E → B
(4) B → 0
(5) B → 1
이 확장된 문법에 대해 항목 집합과 그들 사이의 전이가 결정될 것이다.
LR 파서 테이블 구축
테이블을 구축하는 첫 번째 단계는 폐쇄된 항목 집합들 간의 전이를 결정하는 것이다. 이 전이들은 우리가 종결자와 비종결자를 모두 읽을 수 있는 유한 오토마톤을 고려하는 것처럼 결정될 것이다. 이 오토마톤의 시작 상태는 항상 추가된 규칙의 첫 번째 항목의 폐쇄이다. S → • E eof:
항목 집합 0
S → • E eof
+ E → • E * B
+ E → • E + B
+ E → • B
+ B → • 0
+ B → • 1
항목 앞의 굵은 "+"는 폐쇄를 위해 추가된 항목을 나타낸다(수학적 '+' 연산자, 즉 종결자와 혼동하지 말 것). "+"가 없는 원래 항목을 항목 집합의 커널이라고 한다.
시작 상태(S0)에서 시작하여 이 상태에서 도달할 수 있는 모든 상태가 이제 결정된다. 항목 집합의 가능한 전이는 점 뒤에 오는 심볼(종결자와 비종결자)을 확인함으로써 찾을 수 있다. 항목 집합 0의 경우 해당 심볼은 종결자 '0'과 '1' 그리고 비종결자 E와 B이다. 각 심볼 가 이끄는 항목 집합을 찾기 위해 각 심볼에 대해 다음 절차를 따른다.
종결자 '0'(즉, x = '0'인 경우)에 대해 결과는 다음과 같다.
LR 파서 테이블 구축
항목 집합 1
B → 0 •
그리고 종결자 '1'(즉, x = '1'인 경우)에 대해 결과는 다음과 같다.
항목 집합 2
B → 1 •
그리고 비종결자 E(즉, x = E인 경우)에 대해 결과는 다음과 같다.
항목 집합 3
S → E • eof
E → E • * B
E → E • + B
그리고 비종결자 B(즉, x = B인 경우)에 대해 결과는 다음과 같다.
항목 집합 4
E → B •
클로저가 항상 새로운 항목을 추가하는 것은 아니다. 예를 들어 위의 새로운 집합들에는 점 뒤에 비종결자가 없다.
위의 절차는 더 이상 새로운 항목 집합이 발견되지 않을 때까지 계속된다. 항목 집합 1, 2, 4에는 점이 어떤 심볼 앞에도 없으므로 전이가 없을 것이다. 하지만 항목 집합 3에는 종결자 '*'와 '+' 앞에 점이 있다. 심볼 에 대해 전이는 다음과 같다.
항목 집합 5
E → E * • B
+ B → • 0
+ B → • 1
그리고 에 대해 전이는 다음과 같다.
항목 집합 6
E → E + • B
+ B → • 0
+ B → • 1
이제 세 번째 반복이 시작된다.
LR 파서 테이블 구축
항목 집합 5의 경우 종결자 '0'과 '1', 그리고 비종결자 B를 고려해야 하지만, 종결자에 대해 생성되는 폐쇄된 항목 집합은 이미 발견된 항목 집합 1과 2와 각각 동일하다. 비종결자 B의 경우 전이는 다음과 같다.
항목 집합 7
E → E * B •
항목 집합 6의 경우 종결자 '0'과 '1', 비종결자 B를 고려해야 하지만, 이전과 마찬가지로 종결자에 대해 생성되는 항목 집합은 이미 발견된 항목 집합 1과 2와 동일하다. 비종결자 B의 경우 전이는 다음과 같다.
항목 집합 8
E → E + B •
이 최종 항목 집합 7과 8에는 점 너머의 심볼이 없으므로 더 이상 새로운 항목 집합이 추가되지 않아 항목 생성 절차가 완료된다. 항목 집합을 상태로 하는 유한 오토마톤은 아래에 나와 있다.
이제 오토마톤의 전이 테이블은 다음과 같다.
이 테이블과 발견된 항목 집합으로부터 액션 및 고투 테이블은 다음과 같이 구축된다.
독자는 이러한 단계들이 이전에 제시된 액션 및 고투 테이블을 생성하는지 확인할 수 있다.
LR 파서 테이블 구축
위 절차의 4단계만 리듀스 액션을 생성하므로, 모든 리듀스 액션은 전체 테이블 행을 차지해야 하며, 입력 스트림의 다음 심볼에 관계없이 축소가 발생하게 한다. 이것이 바로 이들이 LR(0) 파스 테이블인 이유이다. 즉, 어떤 축소를 수행할지 결정하기 전에 미리보기를 전혀 하지 않는다(즉, 0개의 심볼을 미리 본다). 축소의 모호성을 해소하기 위해 미리보기가 필요한 문법은 다른 열에 다른 축소 액션을 포함하는 파스 테이블 행을 필요로 하며, 위 절차는 그러한 행을 생성할 수 없다.
LR(0) 테이블 구축 절차의 개선 사항(예: SLR 및 LALR)은 전체 행을 차지하지 않는 리듀스 액션을 구축할 수 있다. 따라서 이들은 LR(0) 파서보다 더 많은 문법을 파싱할 수 있다.
오토마톤은 결정론적임을 보장하는 방식으로 구축된다. 그러나 액션 테이블에 축소 액션이 추가될 때, 동일한 셀이 축소 액션과 시프트 액션(시프트-축소 충돌) 또는 두 개의 다른 축소 액션(축소-축소 충돌)으로 채워지는 경우가 발생할 수 있다. 그러나 이 경우 문법이 LR(0) 문법이 아님을 보여줄 수 있다. 시프트-축소 충돌의 고전적인 실제 예는 매달린 else 문제이다.
LR 파서 테이블 구축
시프트-리듀스 충돌이 있는 비-LR(0) 문법의 작은 예시는 다음과 같다.
(1) E → 1 E
(2) E → 1
발견된 항목 집합 중 하나는 다음과 같다.
항목 집합 1
E → 1 • E
E → 1 •
+ E → • 1 E
+ E → • 1
이 항목 집합에는 시프트-리듀스 충돌이 있다. 위 규칙에 따라 액션 테이블을 구축할 때 [항목 집합 1, 종결자 '1'] 셀에는 s1(상태 1로 시프트)과 r2(문법 규칙 2로 축소)가 모두 포함된다.
축소-축소 충돌이 있는 비-LR(0) 문법의 작은 예시는 다음과 같다.
(1) E → A 1
(2) E → B 2
(3) A → 1
(4) B → 1
이 경우 다음 항목 집합이 얻어진다.
항목 집합 1
A → 1 •
B → 1 •
이 항목 집합에는 축소-축소 충돌이 있다. 이 항목 집합의 액션 테이블 셀에 규칙 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는 여러 해석 대안을 로컬에서 모호하지 않게 할 수 있는 컴퓨터 언어(및 로지반과 같은 인공 인간 언어)를 구문 분석하는 데 적합하지만, 모호성 해소가 전역적이어야 하는 자연어를 구문 분석하는 데는 덜 유용할 수 있다.
파싱 표현 문법 정의
파싱 표현식은 각 문자열이 일치하거나 일치하지 않을 수 있는 일종의 패턴이다. 일치하는 경우, 파싱 표현식에 의해 소비된 문자열의 고유한 접두사(전체 문자열, 빈 문자열 또는 그 사이의 일부일 수 있음)가 있다. 이 접두사는 일반적으로 표현식과 일치하는 것으로 간주된다. 그러나 문자열이 파싱 표현식과 일치하는지 여부는 (선행 조건자 때문에) 소비된 부분 다음에 오는 부분에 따라 달라질 수 있다. 파싱 표현식 언어는 특정 파싱 표현식과 일치하는 모든 문자열의 집합이다.:Sec.3.4
파싱 표현식 문법은 명명된 파싱 표현식들의 모음으로, 서로를 참조할 수 있다. 파싱 표현식에서 그러한 참조의 효과는 마치 참조된 전체 파싱 표현식이 참조 위치에 주어진 것과 같다. 파싱 표현식 문법은 또한 지정된 시작 표현식을 가진다. 문자열이 시작 표현식과 일치하면 문법과 일치한다.
파싱 표현 문법 정의
일치하는 문자열의 요소는 말단 기호 또는 줄여서 단말이라고 한다. 마찬가지로 파싱 표현식에 할당된 이름은 비말단 기호 또는 줄여서 비단말이라고 한다. 이러한 용어는 생성 문법에 설명적이지만, 파싱 표현식 문법의 경우 단순히 파싱 알고리즘에 대한 논의에서 거의 보편적으로 사용되기 때문에 유지되는 용어일 뿐이다.
파싱 표현식의 추상 구문과 구체 구문 모두 문헌과 이 문서에서 사용된다. 추상 구문은 본질적으로 수식이며 주로 이론적인 맥락에서 사용되는 반면, 구체 구문 파싱 표현식은 구문 분석기를 직접 제어하는 데 사용될 수 있다. 주된 구체 구문은 포드(Ford)가 정의한 것이지만,:Fig.1 많은 도구들이 자체 방언을 가지고 있다. 다른 도구들은 추상 구문 파싱 표현식의 프로그래밍 언어 기본 인코딩을 구체 구문으로 사용하는 데 더 가깝다.
다른 파싱 표현식을 포함하지 않는 두 가지 주요 파싱 표현식은 개별 단말 기호와 비단말 기호이다. 구체 구문에서 단말은 따옴표(홑따옴표 또는 겹따옴표) 안에 배치되는 반면, 따옴표가 없는 식별자는 비단말을 나타낸다:
파싱 표현 문법 정의
추상 구문에서는 형식화된 구분이 없으며, 대신 각 기호가 단말 또는 비단말 중 하나로 정의되어 있다고 가정하지만, 비단말에는 대문자를 사용하고 단말에는 소문자를 사용하는 것이 일반적인 관례이다.
구체 구문에는 단말 클래스에 대한 여러 형식도 있다:
문자 목록 [abcde]를 둘러싼 대괄호는 나열된 문자 중 하나와 일치하는 파싱 표현식을 형성한다. 정규 표현식에서와 같이 이러한 클래스에는 하이픈으로 범위의 시작과 끝을 쓰는 범위 [0-9A-Za-z]도 포함될 수 있다. (정규 표현식의 경우와 달리 대괄호 문자 클래스에는 부정을 위한 ^가 없다. 그 목적은 대신 not-predicates를 통해 달성할 수 있다.)
추상 구문에서 이러한 형식은 보통 간결성을 위해 정확한 정의가 생략된 비단말로 형식화된다. 유니코드에는 수만 개의 문자(글자)가 있다. 반대로 이론적 논의에서는 복합 파싱 표현식을 사용하여 표현할 수 있는 개념에 대한 원자적 추상 구문을 도입하기도 한다. 이에는 다음이 포함된다:
파싱 표현 문법 정의
구체 구문에서 따옴표로 묶인 단말과 괄호로 묶인 단말은 백슬래시 이스케이프를 사용하므로, "줄 바꿈 또는 캐리지 리턴"은 [\n\r]로 작성될 수 있다. 길이가 1보다 큰 따옴표로 묶인 단말의 추상 구문 대응물은 해당 단말들의 시퀀스이다. "bar"는 "b" "a" "r"와 동일하다. 주된 구체 구문은 단말이 홑따옴표를 사용하는지 겹따옴표를 사용하는지에 따라 별개의 의미를 부여하지 않지만, 일부 방언은 하나를 대소문자 구분으로 처리하고 다른 하나는 대소문자 비구분으로 처리한다.
기존의 파싱 표현식 e, e1, e2가 주어지면 다음 연산자를 사용하여 새로운 파싱 표현식을 구성할 수 있다:
연산자 우선순위는의 표 1에 따라 다음과 같다:
구체 구문에서 파싱 표현식 문법은 단순히 비단말 정의의 시퀀스이며, 각 정의는 다음 형식을 가진다:
파싱 표현 문법 정의
Identifier는 정의되는 비단말이고, Expression은 이 비단말이 참조하도록 정의된 파싱 표현식이다. LEFTARROW는 방언에 따라 조금씩 다르지만, 일반적으로 <-, ←, :=, =와 같은 왼쪽 화살표 또는 할당 기호이다. 이를 이해하는 한 가지 방법은 비단말에 대한 할당 또는 정의를 만드는 것으로 정확히 이해하는 것이다. 다른 방법은 문맥 자유 문법의 규칙에서 사용되는 오른쪽 화살표 →와의 대비로 이해하는 것이다. 파싱 표현식에서는 정보의 흐름이 표현식에서 비단말로 가는 것이지, 비단말에서 표현식으로 가는 것이 아니다.
수학적 객체로서 파싱 표현식 문법은  튜플이며, 여기서 은 비단말 기호 집합, 는 단말 기호 집합, 는 에서 에 대한 파싱 표현식 집합으로의 함수, 그리고 는 시작 파싱 표현식이다. 일부 구체 구문 방언은 시작 표현식을 명시적으로 지정하지만, 주된 구체 구문은 대신 첫 번째로 정의된 비단말이 시작 표현식이라는 암묵적인 규칙을 가진다.
파싱 표현 문법 정의
구체 구문 파싱 표현식 문법의 주된 방언에는 명시적인 정의 종결자나 정의 간의 구분자가 없다는 점에 주목할 필요가 있다. 새 정의를 새 줄에서 시작하는 것이 관례이지만, Expression 내의 비단말 뒤에 LEFTARROW가 오면 안 된다는 제약 조건을 추가하면 다음 정의의 LEFTARROW만으로 경계를 찾는 것으로 충분하다. 그러나 일부 방언은 명시적인 종결자를 허용하거나 명시적으로 요구할 수 있다.
이것은 음이 아닌 정수에 다섯 가지 기본 연산을 적용하는 수학 공식을 인식하는 PEG이다.
파싱 표현 문법 정의
위 예에서 단말 기호는 '('와 ')'와 같이 홑따옴표 안의 문자로 표현된 텍스트 문자이다. 범위 [0-9]는 '0'부터 '9'까지의 10개 문자에 대한 약어이다. (이 범위 구문은 정규 표현식에서 사용되는 구문과 동일하다.) 비단말 기호는 다른 규칙으로 확장되는 것들이다: Value, Power, Product, Sum, Expr. Sum 및 Product 규칙은 이러한 연산에 대해 원하는 왼쪽 결합성을 제공하지 않으며(결합성을 전혀 처리하지 않으며, 구문 분석 후 후처리 단계에서 처리해야 함), Power 규칙(자신을 오른쪽에서 참조함으로써)은 원하는 지수 오른쪽 결합성을 제공한다. 또한, Sum ← Sum (('+' / '-') Product)?와 같은 규칙(왼쪽 결합성을 달성하기 위한 의도)은 무한 재귀를 유발하므로 문법에서 표현할 수 있더라도 실제로는 사용할 수 없음에 유의하라.
파싱 표현 문법 정의
문맥 자유 문법과 파싱 표현식 문법의 근본적인 차이점은 PEG의 선택 연산자가 순서화되어 있다는 것이다. 첫 번째 대안이 성공하면 두 번째 대안은 무시된다. 따라서 순서화된 선택은 문맥 자유 문법과 같은 비순서 선택과는 달리 교환적이지 않다. 순서화된 선택은 일부 논리형 프로그래밍 언어에서 사용 가능한 소프트 컷 연산자와 유사하다.
결과적으로 CFG가 PEG로 직접 변환되면, 이전의 모호성은 가능한 구문 분석 중 하나를 결정적으로 선택하여 해결된다. 문법 대안이 지정되는 순서를 신중하게 선택함으로써 프로그래머는 어떤 구문 분석 트리가 선택되는지에 대해 상당한 제어권을 가질 수 있다.
파싱 표현식 문법은 또한 and- 및 not- 구문 예측을 추가한다. 입력 문자열을 실제로 소비하지 않고 임의로 복잡한 하위 표현식을 사용하여 "미리보기"를 할 수 있기 때문에, 특히 대안을 재정렬하는 것으로는 원하는 정확한 구문 분석 트리를 지정할 수 없을 때 강력한 구문 미리보기 및 모호성 해소 기능을 제공한다.