SLR 문법

SLR grammar

SLR 그래머는 단순 LR 파서(Simple LR 파서)가 수용하는 공식 그래머 등급이다.SLR 그래머는 모든 LR(0) 그래머와 모든 LALR(1) 및 LR(1) 그래머의 하위 집합이다.

SLR 파서에 의해 처리될 때, SLR 문법은 LR(0) 파서 상태와 예상되는 룩어헤드 기호의 조합에 대해 시프트/감소 또는 감소/감소되지 않는 파스 테이블로 변환된다.문법이 SLR이 아닌 경우, 파스 테이블은 일부 상태와 일부 룩어헤드 기호에 대해 충돌을 줄이거나 줄이며, 결과적으로 거부된 파서는 더 이상 결정론적이지 않다.파서는 다음 번에는 교대 여부를 결정할 수도 없고, 두 후보 감축 사이에서 결정할 수도 없다.SLR 구문 분석기는 완료된 모든 비터미널에 대해 예상할 룩어헤드 기호를 선택하기 위해 추적(A) 계산을 사용한다.

LALR 파서들은 동일한 파서 상태에 대해 더 작고 더 촘촘한 룩어헤드 세트를 제공하는 다른 계산을 사용한다.이러한 소규모 집합은 주의 교대조 조치와 중복되는 것을 제거할 수 있으며, 동일한 상태의 다른 감축을 위한 경계선과 중복된다.SLR 파서가 보고한 중복 충돌은 Follow(A)를 사용한 대략적인 계산의 결과인 거짓이다.

모호한 문법은 SLR을 포함한 모든 LR 분석 방법에 대해 불가피하게 교대/축소하거나 충돌을 감소/축소할 수 있다.컴퓨터 언어 문법이 모호해지는 일반적인 방법은 일부 비단어가 좌뇌와 우뇌 모두인 경우:

Expr → Expr * Val
Expr → Val + Expr
엑스퍼 → 발

정의들

SLR(1) 자동화의 상태 내 B → y • 형식의 규칙은 완전히 확장되었고 어떤 변속 전환을 수행할 수 없기 때문에 되돌릴 수 없거나 감소된 상태라고 한다.이 상태의 규칙은 RHS(우측 측면)의 맨 오른쪽 끝에 점( • , 현재 자동 검색 위치)이 위치한다.

규칙.

문법은 SLR(1) 자동화의 각 및 모든 상태에 대해 다음 조건 중 어느 것도 위반되지 않는 경우에만 SLR(1)이라고 한다.

  1. 모든 축소 가능한 규칙 A → a • Xb in state s(X가 일부 단자인 경우)에 대해, 다음 B 집합이 단자 X를 포함하는 것과 같은 상태에 어떤 수정 불가능한 규칙 B → a •가 존재하지 않아야 한다.좀 더 형식적인 용어로, 단자 X를 포함하는 집합과 B의 추종 집합의 교차점은 비어 있어야 한다.이 규칙의 위반은 시프트-리듀스 갈등이다.
  2. A → a • b → b • s 단위의 경우 Follow(A)와 Follow(B)가 분리된다(교차는 빈 세트임).이 규칙의 위반은 '절감-절감 갈등'이다.

파싱 알고리즘

다음의 간단한 LR 파서 알고리즘이 애매하지 않은 결과를 가져오면 문법은 SLR(1)이라고 한다.

  1. state s가 형식 A → a • Xb의 어떤 항목을 포함하고 있는 경우, 여기서 X는 단자이고 X는 입력 문자열의 다음 토큰인 경우, 현재의 입력 토큰을 스택으로 옮기는 것이 동작이며, 스택에서 푸시되는 새로운 상태는 항목 A → aX • b가 포함된 상태다.
  2. state s가 전체 항목 A → y • 를 포함하고 입력 문자열의 다음 토큰이 Follow(A)에 있는 경우, 그 동작은 규칙 A → y에 의해 감소한다. 여기서 s가 시작 상태인 규칙 S' → S에 의한 감소는 수락과 동등하다. 이는 다음 입력 토큰이 $인 경우에만 발생한다.다른 모든 경우에 있어서, 새로운 상태는 다음과 같이 계산된다.구문 분석 스택에서 문자열 y와 해당하는 모든 상태를 제거하십시오.그에 따라, y의 건설이 시작된 상태로 DFA에 백업한다.건설에 의해, 이 상태는 형식 B → a • Ab의 항목을 포함해야 한다.A를 스택에 밀어넣고, B → A • b 항목이 포함된 상태를 밀어 넣는다.
  3. 다음 입력 토큰이 위의 두 가지 사례 중 어느 것도 적용되지 않을 경우 오류가 선언된다.

참고 항목

참조

  • 케네스 C의 "컴파일러 건설: 원칙과 실천"루든.