하향식 구문 분석 언어

Top-down parsing language

톱다운 파싱 언어(Top-Down Parsing Language, TDPL)는 한정된 형태의 역추적을 지원하는 실용적인 톱다운 파서들의 공통 계층의 행동을 정식으로 연구하기 위해 1970년대 초 알렉산더 버먼이 개발한 분석 형식 문법의 일종이다.버먼은 원래 초기 파서 생성기인 TMG의 이름을 따서 자신의 포멀리즘을 TMG 스키마(TS)라고 이름 지었지만, 후에 고전적인 문집 《파싱·번역·컴파일론》에서 아호와 울먼에 의해 TDPL이라는 이름을 얻게 되었다.

TDPL 문법의 정의

형식적으로 TDPL 문법 G는 다음과 같은 구성 요소로 구성된 튜플이다.

  • 비터미널 기호의 유한 집합 N.
  • N과 분리되는 단자 기호의 유한 집합 σ.
  • 생산 규칙의 유한 집합 P. 여기서 규칙은 다음 형식 중 하나를 갖는다.
    • A ← ε, 여기서 A는 비단어, ε은 빈 끈이다.
    • ← f, 여기서 f는 무조건적인 실패를 나타내는 구별되는 기호다.
    • A ← a, 여기서 a는 모든 단자 기호다.
    • A ← BC/D, 여기서 B, C, D는 비터미널이다.

문법의 해석

TDPL 문법은 각 비터미널이 구문 분석 함수를 개략적으로 나타내는 재귀적 강하 분석기의 극히 미니멀한 형식 표현으로 볼 수 있다.이러한 비단어 기능 각각은 인식해야 할 문자열을 입력 인수로 간주하여 다음 두 가지 결과 중 하나를 산출한다.

  • 성공, 이 경우 함수는 선택적으로 앞으로 이동하거나 하나 이상의 입력 문자열 문자를 사용할 수 있으며, 또는
  • 실패(입력이 소비되지 않는 경우).

비터미널 기능은 실제로 어떤 입력도 소비하지 않고 성공할 수 있으며, 이는 실패와 구별되는 결과로 간주된다는 점에 유의하십시오.

A ← ε 형식의 규칙에 의해 정의된 비단어 A는 제공된 입력 문자열과 관계없이 어떤 입력도 소비하지 않고 항상 성공한다.반대로 A form f 형식의 규칙은 입력에 관계없이 항상 실패한다.형식 A ← a의 규칙은 입력 문자열의 다음 문자가 단자 a인 경우 성공하고, 이 경우 비단자가 성공하여 해당 단자를 소비하고, 다음 입력 문자가 일치하지 않거나(또는 다음 문자가 없는 경우), 비단자어가 실패한다.

A ← BC/D 형식의 규칙에 의해 정의된 비단어 A는 먼저 비단어 B를 재귀적으로 호출하고, B가 성공하면 나머지 입력 문자열에서 C를 호출하여 B에 의해 합치되지 않게 한다.만약 B와 C가 모두 성공한다면, A는 B와 C가 함께 했던 것과 같은 총 입력 문자의 수를 차례로 성공시키고 소비한다.그러나 B 또는 C 중 하나에 고장이 발생하면 A 백트랙이 처음 호출된 입력 문자열의 원래 지점으로 이동한 다음 D를 호출하여 D가 생성하는 모든 결과를 반환한다.

예

다음의 TDPL 문법은 a와 b의 임의 길이 순서로 구성된 정규 언어를 설명한다.

S ← AS/T
T ← BS/E
A ← a
B ← b
E ← ε

다음 문법은 일치하는 가새의 임의 길이 문자열로 구성된 '{}', '{{}{{}}})' 등으로 구성된 문맥 없는 언어 괄호 언어를 설명한다.

S ← OT/E
T ← SU/F
U ← CS/F
O ← {
C ← } }
E ← ε
F ← f

위의 예는 동등하지만 훨씬 간결하게 표현된 문법 표기법을 파싱할 때 다음과 같이 나타낼 수 있다.S ← (a/b)*그리고S ← ({S})*각각,

일반화 TDPL

일반 TDPL 또는 GTDPL로 알려진 TDPL의 약간의 변화는 TDPL의 겉보기 표현성을 크게 증가시키면서 동시에 동일한 미니멀리스트 접근방식을 유지한다(실제로 동일하지만).GTDPL에서는, TDPL의 재귀 규칙 A form BC/D 대신에, A b B[C,D] 형식의 대체 규칙을 사용하며, 이 규칙은 다음과 같이 해석된다.일부 입력 문자열에서 비단어 A가 호출되면 먼저 B를 재귀적으로 호출한다.B가 성공하면 A는 B가 만족하지 않은 나머지 입력에 대해 C를 호출하고 C의 결과를 원래 발신자에게 반환한다.반면 B가 실패하면 A는 원래 입력 문자열에서 D를 호출하고 그 결과를 다시 호출자에게 전달한다.

이 규칙 양식과 TDPL에서 사용되는 A bc BC/D 규칙 양식의 중요한 차이는 C와 D가 A에 대한 동일한 호출에서 모두 호출되지 않는다는 것이다. 즉, GTDPL 규칙은 B를 조건으로/그 다음/else 구성하면 "순수"에 더 가깝다는 것이다.

GTDPL에서는 고전적인 사례 {abcnnn}과 같은 흥미로운 비 컨텍스트 언어를 쉽게 표현할 수 있다.

GTDPL 문법은 과정이 간단하지 않고 필요한 규칙의 수를 크게 증가시킬 수 있지만 동일한 언어를 인식하는 동등한 TDPL 문법으로 줄일 수 있다.[1]또한 TDPL과 GTDPL 모두 매우 제한된 형태의 파싱 표현 그래머로 볼 수 있으며, 모두 동일한 종류의 그래머를 나타낸다.[1]

참고 항목

참조

  1. ^ a b 포드, 브라이언구문 분석 표현 그래머: 인식 기반 통사적 기초

외부 링크