색인 문법

색인화된 문법은 문맥이 없는 문법의 일반화로, 비말단에는 플래그 또는 색인 기호 목록이 포함되어 있습니다.색인화된 문법에 의해 만들어진 언어를 색인화된 언어라고 합니다.

정의.

홉크로프트와 울만의 현대적 정의

Hopcroft와 Ullman(1989) 이후의 현대 출판물에서 색인화된 문법은 공식적으로 5 태플 G = "N,T,F,P,S"로 정의된다.

• N은 변수 또는 비말단 기호 집합입니다.
• T는 단자 기호 집합("알파벳")입니다.
• F는 소위 지수 기호 또는 지수 집합이다.
• S n N은 시작 기호입니다.
• P는 유한한 연산 집합이다.

인덱스된 문법의 도출뿐만 아니라 프로덕션에서 인덱스 기호의 문자열("스택") σ^* F는 A[σ]^{[note 1]}로 표시되는 모든 비단말 기호 A n N에 부착됩니다.단자 기호 뒤에 인덱스 스택이 올 수 없습니다.인덱스 스택 δ^* F 및 비단말기 및 단자기호의 문자열 αθ(N ^*δ T)에 대해 α[θ]는 α 내의 모든 비단말기에 [θ]를 부가한 결과를 나타낸다.예를 들어 α가 a,d δ T단자와 B,C,E δ N단말기호를 갖는 BDE와 같다면 α는 α를 나타낸다.이 표기법을 사용하면 P의 각 생산은 다음 형식이어야 합니다.

1. A[di] → α[di],
2. A[filename] → B[filename] 또는
3. A[fθ] → α[ft],

여기서 A, B n N은 비말단 기호, f f F는 인덱스, σ^* F는 인덱스 기호 문자열, α ( (N )^* T)는 비말단 기호 및 종단 기호 문자열입니다.일부 저자는 생산 규칙에서 인덱스 스택에 대해 "index" 대신 ".."로 씁니다. 유형 1, 2, 3의 규칙은 A[..]→α[..], A[..]→B[f..] 및 A[f..]로 읽습니다.→α[..] (각각).

파생어는 각 비말단 심볼에 부가된 색인 스택을 제외하고 문맥이 없는 문법과 유사합니다.예를 들어, 프로덕션과 같은 경우.A[company] → B[company]C[company]를 적용하면 A의 인덱스 스택이 B와 C에 모두 복사됩니다.또한 규칙은 인덱스 기호를 스택에 푸시하거나 "맨 위" 인덱스 기호(예: 맨 왼쪽)를 팝할 수 있습니다.

형식적으로, 관계 θ("직접 파생")는 다음과 같이 "sentential forms"의 집합(N[F^*]tT)^*에 정의된다.

1. A [ β ] → α [ β α ] β A [ β α [ β α ] , , 위의 정의를 사용하여 생성한다.즉, 규칙의 좌측 인덱스 스택 is이 우측의 각 비말단에 복사됩니다.
2. A[l] → B[fl]가 유형 2의 생성물이라면 β A[l] β B[fl] β이다.즉, f를 눌러서 좌측의 스택 θ에서 우측의 인덱스 스택을 얻는다.
3. A[fθ] → α[θ]가 유형 3의 생성물이라면 β A[fθ] β α[θ] β α[θ] δ이다.즉, 첫 번째 인덱스 f는 좌측 스택에서 팝되고, 그 후 우측의 각 비단말기로 분배됩니다.

통상적으로 유도관계 θ는 직접 유도 θ의 반사적 전이폐로 정의된다.L(G) = { w ∈ T^*: S ⇒ w } 언어는 시작 기호에서 파생될 수 있는 모든 종단 기호 문자열 집합입니다.

아호 원정의

역사적으로 색인화된 문법의 개념은 알프레드 아호에 의해 ^[3]다른 형식주의를 사용하여 처음 도입되었다.Aho는 색인화된 문법을 5-태플(N,T,F,P,S)로 정의했다.

1. N은 변수 또는 비말단 기호의 유한 알파벳입니다.
2. T는 종단 기호의 유한 알파벳입니다.
3. F 2^{N × (N ∪ T)*} 2는 이른바 플래그의 유한 집합이다(각 플래그는 그 자체로 이른바 인덱스 생산의 집합이다.
4. P n N × (NF t T)^*는 유한한 연산 집합이다.
5. S n N은 시작 기호입니다.

직접 파생상품은 다음과 같다.

• P로부터의 생산 p = (A → X₁₁ … … X ) )는_kk, 비단말기 A ∈ N 에 이어서, 플래그 문자열 ζ^* F 에 일치합니다.문맥에서 "A"는 p를 경유하여 "X₁₁"…X_kk"로 파생됩니다.여기서 X가 비말단일 경우_i "="이고_ii 그렇지 않을 경우 빈 단어입니다.따라서 A의 오래된 플래그는 p에 의해 생성된 새로운 비단말기에 복사됩니다.이러한 각 생산은 홉크로프트/울먼 형식주의에서 유형 1과 2의 적절한 생산으로 시뮬레이션할 수 있다.
• 인덱스 생성 p=(A→X₁…X_k) f는 Af와 일치하고(발신원 플래그 f는 비단말기 A에 이은 첫 번째 기호와 일치해야 함) 나머지 인덱스 문자열 Af는 새로운 비단말기 각 비단말기에 복사됩니다.여기서 "X"는_i X"…X_kk"의 빈₁₁ 단어입니다_i.이러한 각 생산은 홉크로프트/울먼 형식주의의 유형 3의 생산과 일치한다.

예를 들면, 이 형식주의는 하야시(1973년,^[4] 페이지 65-66년)에 의해서 사용되고 있다.

예

실제로 인덱스 스택은 적용된 규칙과 순서를 계산하고 기억할 수 있습니다.예를 들어 색인화된 문법은 {www : w { {a,b}}^* 단어의 컨텍스트에 맞는 언어를 설명할 수 있습니다.

S[ ]	→	S[f]	T[f]	→	T[T]
S[ ]	→	S[g]	T[g]	→	b T [ ]
S[ ]	→	T[]] T[]] T[]]	T[]	→	ε

abbabb의 유도체는 다음과 같습니다.

S[] s S[g] s S[gg] s S [ fgg ] [ T [ fgg ]T [ fgg ] a 、 T [ fgg ]T [ fgg ] ab 、 AB T [ fg ]abbab T[fg] ... ...abb abb abb.

또 다른 예로, 문법 G = { {S,T,A,B,C}, {a,b,c}, {f,g}, P, S produces는 생산 세트 P가 다음과 같이 구성된 {abcⁿⁿⁿ:n 1 1} 언어를 생성합니다.

S[s] → T[g]	A[f] → A[f]	A[g] → a
T[filename] → T[filename]	B[f] → B[f]	B[g] → b
T[color] → A[color] B[color] C[color]	C[fcl] → C[clos]	C[g] → c

파생 예는 다음과 같습니다.

S [ ] [ T [ fg ]f T [ fg ] a A [ fg ]C [ fg ] a aA [ fg ]C [ fg ]⇒ AB [ g ]C [ fg ]

두 예제 언어 모두 pumping rema에 의해 컨텍스트가 자유롭지 않습니다.

특성.

홉크로프트와 울먼은 색인화된 언어들이 색인화된 문법들 이외의 여러 형식주의들에 의해 생성되었기 때문에 색인화된 언어들을 "자연적인" 클래스로 간주하는 경향이 있다.^[5]

• Aho의 단방향 중첩 스택 오토마타^[6]
• 피셔의 매크로 문법^[7]
• 스택^[8] 스택을 갖춘 Greibach의 오토마타
• 마이바움의 대수적^[9] 특성화

하야시는^[4] 펌핑 보조제를 색인화된 문법으로 일반화했다.반대로^[10][11], Gilman은 색인화된 언어에 대해 "수축 보조"를 부여합니다.

선형 색인 문법

Gerald Gazdar는 두 번째 클래스인 LIG(^[14]Linear Indexed Grammars)를 정의했습니다.이는 각 프로덕션에서 최대 1개의 비터미널을 ^{[note 2]}스택 수신으로 지정하는 반면 일반 인덱스 문법에서는 모든 비터미널이 스택의 복사본을 수신하도록 요구하기 때문입니다.형식적으로 선형 색인 문법은 일반적인 색인 문법과 유사하게 정의되지만, 생산의 양식 요구사항은 다음과 같이 수정된다.

1. A[di] → α[] B[di] β[],
2. A[col] → α[] B[folt] β[,
3. A[fθ] → α[] B[flash]β[],

여기서 A, B, f, α는 위와 같이 사용되며, β δ(N δ T)^*는 ^{[note 3]}α와 같은 비말단 및 종단 기호 문자열이다.또, 직접 유도 관계θ를 위와 같이 정의한다.이 새로운 문법 클래스는 문맥에 민감하게 반응하는 클래스에 속하는 ^[15]언어 클래스를 엄격하게 정의합니다.

{ www : w { { a , b ^*} 언어는 색인화된 문법으로 생성할 수 있지만 선형 색인화된 문법으로 생성할 수 없습니다.또 { ww : w { { a , ^*b } 및 { a cⁿⁿⁿ : n 1 1 }은 모두 선형 색인화된 문법으로 생성할 수 있습니다.

원래 생산 규칙과 수정된 생산 규칙을 모두 허용하면 언어 클래스는 색인화된 ^[16]언어로 유지됩니다.

예

denote가 스택 기호의 임의의 시퀀스를 나타내면, L = {aⁿⁿ bⁿ c n 1 1 ^{[note 4]}} 언어에 대한 문법을 다음과 같이 정의할 수 있습니다.

S[ ]	→	S[f] c
S[ ]	→	T[ ]
T[f]	→	T[]] b
T[]	→	ε

문자열 abc를 도출하는 절차는 다음과 같습니다.

S [ ] s aS [ f ]c a aT [ f ]c a aT [ ]bc 、 abc

마찬가지로:

S[] a aS [ f ]c aa aaS [ff ]cc aa aaT [ff ]cc s aaT [ f ]bbcc a aabbcc

계산 능력

선형 색인화된 언어는 색인화된 언어의 하위 집합이므로 모든 LIG는 IG로 기록될 수 있으며, LIG는 IG보다 훨씬 강력하지 않습니다.LIG에서 IG로의 변환은 비교적 ^[17]간단하다.일반적으로 LIG 규칙은 X${\displaystyle }$[${\displaystyle ]\to }$ ${\displaystyle \alpha }$Y [ ${\displaystyle ]\beta }${$displaystyle$ X [\$sigma$]\$to \alpha$ Y [\$sigma ]\display$ $\}$와 $비슷하며{\displaystyle }$, 개서 규칙의 푸시/팝 부분을 모듈로 합니다.$(\displaystyle \alpha})$ $및$ β(\$displaystyle \beta)$는 단자 기호 및/또는 비단말 기호의 문자열을 나타내며, LIG의 정의에 따라 모든 비단말 기호는 빈 스택을 가져야 합니다.이것은 물론 IG의 정의와는 반대되는 것입니다.IG에서는 스택이 푸시되지 않거나 스택에서 팝되지 않은 비터미널은 고쳐 쓴 비터미널과 완전히 같은 스택이어야 합니다.따라서 α$$$및$ β에 $비터미널$이 있어야 합니다.비어둠은 비어있지 않아도 빈 스택이 있는 것처럼 동작합니다.

${\displaystyle \mathrm{규칙}}$X [ ${\displaystyle ]}$ ${\displaystyle \to Y}$[ ]$Z$ [ ]{ $displaystyle$ X [ \ $sigma ]\to Y$ [ ][ \ $sigma$ f$$]} 를$$ 예로 들 수 있습니다.이를 IG로 변환할 때${\displaystyle }$Y [$]$ \ $display style$ Y [$$][ ${\displaystyle ]}$ \ $display style$ Y^ { \ $prime$} [ \ $sigma$$$]의 대체는$Y{\displaystyle }$${\displaystyle }$[$$] \ $display$$style$ Y [$$]와$$ $동일$하게 동작하는 $일부{\displaystyle {}^{}}$ Y${\displaystyle {}^{}y}$ [ $]$이어야 합니다.이를 실현하기 위해서는 $임의$의 Y ${\displaystyle {}^{}}$ [ $]$ ]{ $displaystyle Y$^{\prime }[\sigma$$$]}(\displaystyle \sigma$})를 사용하여 스택에서 심볼을 팝하는 규칙 쌍이 필요합니다.그 후 스택이 비어 있으면 Y${\displaystyle }$[$]$ \ $displaystyle$ Y [$]$라고 고쳐 쓸 수 있습니다.

$\displaystyle Y^{\prime}[\sigma f]\to Y^{\prime}[\sigma ]}$

$\displaystyle Y^{\prime}[] Y[]$

일반적으로 이것을 적용하여 LIG에서 IG를 도출할 수 있습니다.예를 들어${\displaystyle }${ ${\displaystyle a^{}}$ n ${\displaystyle b^{}}$ n ${\displaystyle c^{}}$ ${\displaystyle {}^{}{}^{}}$ d ${\displaystyle m^{}}$ ${\displaystyle n{}^{}1}$ ${\displaystyle 1}$, ${\displaystyle \mathrm{m}}$1 1$1$ 1$$} { $displaystyle$\ {$a^{n}$ $b^{n}$ c^{$n} d^{m}$n$\geq$1,$m\geq$ 1$\}$ 언어의$$ LIG는 다음과 같습니다.

$\displaystyle S[\sigma]\to T[\sigma]V[]}$

${\displaystyle V[]\to d~~dV[]}$

$\displaystyle T[\sigma]\to aT[\sigma f]c~~U[\sigma]}$

$\displaystyle U[\sigma f]\to bU[\sigma ]}$

$\displaystyle U[]에서 \epsilon으로$

여기서의 센텐셜규칙은 IG규칙은 아니지만 위의 $변환알고리즘$을 사용하면 V의$새로운{\displaystyle {}^{}}$ 규칙을 정의하고 문법을 $다음과 같이$ 변경할 수 있습니다$.$

${\displaystyle S[\sigma]\to T[\sigma]V^{\prime }[\sigma ]}$

$\displaystyle V^{\prime}[\sigma f]\to V^{\prime}[\sigma ]}$

${\displaystyle V^{\prime}[]에서 V[]로$

${\displaystyle V[]\to d~~dV[]}$

$\displaystyle T[\sigma]\to aT[\sigma f]c~~U[\sigma]}$

$\displaystyle U[\sigma f]\to bU[\sigma ]}$

$\displaystyle U[]에서 \epsilon으로$

이제 각 규칙은 IG의 정의에 맞춥니다. IG 정의에서는 다시 쓰기 규칙의 오른쪽에 있는 모든 비터미널이 다시 쓰기된 심볼의 스택 복사본을 받습니다.따라서 색인화된 문법은 선형 색인화된 문법이 기술할 수 있는 모든 언어를 기술할 수 있다.

다른 형식주의와의 관계

Vijay-Shanker와 Weir(1994)^[18]는 선형 색인 문법, 조합 범주 문법, 트리 결합 문법 및 헤드 그래머가 모두 동일한 종류의 문자열 언어를 정의한다는 것을 보여준다.선형 색인화된^[19] 문법에 대한 그들의 공식적인 정의는 ^{[clarification needed]}위와 다르다.

LIGs(및 그 약한 등가물)는 LCFRS, MCTAG, MCFG 및 최소주의 문법(Migmalist Grammars)을 포함한 다른 약등가 형식주의 계열에 의해 생성된 언어보다 표현력이 엄격히 떨어진다(적절한 하위 집합을 생성한다는 의미).후자 패밀리는 다항식 ^[20]시간으로 구문 분석할 수도 있습니다.

분산 인덱스 문법

Staudacher(1993)^[12]에 의해 도입된 색인 문법의 또 다른 형태는 분산 색인 문법(DIGs) 클래스이다.DIGs와 Aho의 Indexed Grammars를 구별하는 것은 인덱스의 전파이다.Aho의 IG와는 달리, 리라이트 조작중에 심볼 스택 전체를 모든 비터미널에 배포합니다.DIG는 스택을 서브스택으로 분할하여 선택된 비터미널에 서브스택을 배포합니다.

DIG의 바이너리 배포 규칙에 대한 일반적인 규칙 스키마는 다음과 같습니다.

X[f₁...ff_ii+1...f_n] → α Y[f₁...f_i]β Z[f_i+1...f_n] †

여기서 α, β 및 β는 임의의 종단 문자열입니다.3진수 분산 문자열의 경우:

X[f₁...ff_ii+1...ff_jj+1...f_n] → α Y[f₁...f_i]β Z[f_i+1...f_j] γ W[f_j+1...f_n] η

개서 규칙 우측에 있는 비종단자 수가 많은 경우에도 마찬가지입니다.일반적으로 리라이트 규칙의 오른쪽에 비터미널이 m개 있는 경우 스택은 m개의 방법으로 분할되어 새로운 비터미널 간에 분산됩니다.파티션이 비어 있는 특수한 경우가 있기 때문에 규칙이 사실상 LIG 규칙이 됩니다.따라서 분산 색인 언어는 선형 색인 언어의 상위 집합입니다.

「 」를 참조해 주세요.

• 촘스키 계층

메모들

레퍼런스

외부 링크

• 색인화된 문법 및 언어에 대한 "NLP in Prolog" 장