문맥 자유 문법

Context-free grammar
C 프로그래밍 언어의 형식[1] 문법의 간략화 발췌(왼쪽)와 비단말기 기호 Stmt \ \ \ { \ 에서 C 코드(오른쪽)를 추출한 것입니다.비단말기 기호와 단말 기호는 각각 파란색과 빨간색으로 표시됩니다.

형식 언어 이론에서, 문맥 자유 문법(CFG)은 생산 규칙이 형식인 형식 문법이다.

A는 단일 비단말기 이고α는 {\ 단자 및/또는 비단말 입니다({\ 비워 둘 수 있음).형식 문법은 비단말기의 문맥에 관계없이 생산 규칙을 적용할 수 있는 경우 "문맥 자유"입니다.어떤 기호가 둘러져 있든 좌측에 있는 단일 비단자는 항상 우측으로 대체할 수 있습니다.이것이 문맥 의존 문법과 구별되는 점이다.

형식 문법은 기본적으로 주어진 형식 언어로 가능한 모든 문자열을 설명하는 일련의 생산 규칙입니다.생산 규칙은 단순한 대체 수단입니다.예를 들어, 사진의 첫 번째 규칙은

(\{Stmt""" rangle)로 바꿉니다. ;특정 비단말기 기호에는 여러 개의 치환 규칙이 있을 수 있습니다.문법에 의해 생성되는 언어는 반복되는 규칙 적용에 의해 특정 비단말기호("시작 기호")에서 파생될 수 있는 터미널 기호의 모든 문자열 집합입니다.비말단 기호는 파생 프로세스 중에 사용되지만 최종 결과 문자열에는 표시되지 않습니다.

문맥 자유 문법에 의해 생성된 언어는 문맥 자유 언어(CFL)라고 불립니다.문맥이 없는 다른 문법은 동일한 문맥이 없는 언어를 생성할 수 있습니다.언어의 속성(내적 속성)과 특정 문법의 속성(외적 속성)을 구별하는 것이 중요합니다.언어 평등 문제(문맥이 없는 두 개의 문법이 같은 언어를 생성합니까?)는 결정할 수 없습니다.

문맥이 없는 문법은 언어학에서 발생하는데, 언어학자인 노암 촘스키에 의해 자연어로 문장이나 단어의 구조를 기술하는데 사용된다.대조적으로, 컴퓨터 과학에서는, 재귀적으로 정의된 개념의 사용이 증가함에 따라, 그것들은 점점 더 많이 사용되었다.초기 어플리케이션에서는 프로그래밍 언어의 구조를 기술하기 위해 문법이 사용됩니다.최신 응용 프로그램에서는 문서 유형 [2]정의라고 하는 XML(Extensible Markup Language)의 필수 부분에서 사용됩니다.

언어학에서, 몇몇 저자들은 문맥이 없는 문법을 언급하기 위해 구 구조 문법이라는 용어를 사용합니다. 여기서 구 구조 문법은 의존 문법과 구별됩니다.컴퓨터 과학에서 문맥 자유 문법의 일반적인 표기법은 백커스-나우르 형식 또는 BNF입니다.

배경

적어도 파니니 시대 이후 언어학자들은 언어의 문법을 블록 구조의 관점에서 기술하고, 문장이 어떻게 작은 구절에서 재귀적으로 형성되고, 결국 개별 단어 또는 단어 요소에서 만들어지는지를 기술해 왔다.이러한 블록 구조의 본질적인 특성은 논리 유닛이 절대 겹치지 않는다는 것입니다.예를 들어 다음과 같은 문장이 있습니다.

차고에 파란 차가 있던 존은 식료품점으로 걸어갔다.

는 다음과 같이 논리적으로 괄호로 묶을 수 있습니다(논리 메타심볼[ ] ) 。

[[[누구[파란 ]][[차고지]], [[[식당]까지 걸어갔다]]

문맥이 없는 문법은 문장의 "블록 구조"를 자연스러운 방법으로 포착하면서, 일부 자연 언어의 구문이 더 작은 블록으로부터 어떻게 만들어지는지를 기술하기 위한 간단하고 수학적으로 정확한 메커니즘을 제공한다.그 단순성은 형식주의를 엄격한 수학 연구에 따르게 한다.일치와 참조와 같은 자연어 구문의 중요한 특징은 문맥이 없는 문법의 일부가 아니지만 문장의 기본적인 재귀적 구조, 절이 다른 절에 내포되는 방식, 형용사와 부사의 목록이 명사와 동사에 의해 삼켜지는 방식이 정확하게 기술되어 있다.

문맥이 없는 문법은 Semi-Thu 시스템의 특수한 형태로 Axel Thue의 작품으로 거슬러 올라갑니다.

문맥 자유 문법의 형식주의는 1950년대 중반에 노암 [3]촘스키에 의해 개발되었고, 또한 그가 구 구조 문법이라고 [4]불렀던 특별한 형태형식 문법으로 분류되었다.그러나 일부 작가들은 촘스키 계층 구조에서 문맥에 민감한 문법이나 문맥이 없는 문법이라는 더 제한적인 문법에 대한 용어를 유보하고 있다.더 넓은 의미에서, 구문 구조 문법은 선거구 문법으로도 알려져 있다.따라서 구 구조 문법의 정의 특성은 의존 문법의 의존 관계와는 반대로 구성 관계에 대한 고수이다.촘스키의 생성 문법 체계에서 자연어의 구문은 변환 [5]규칙과 결합된 문맥 없는 규칙에 의해 설명되었다.

블록 구조는 알골 프로젝트(1957–1960)에 의해 컴퓨터 프로그래밍 언어에 도입되었고, 결과적으로 알골 구문을 설명하는 문맥 없는 문법을 특징으로 했다.이것은 컴퓨터 언어의 표준적인 특징이 되었고, 컴퓨터 언어의 구체적인 설명에 사용되는 문법의 표기법은 알골어 [3]디자인 위원회의 두 명의 멤버의 이름을 따서 백커스-나우르 형태로 알려지게 되었다.문맥이 없는 문법이 포착하는 "블록 구조" 측면은 문법에 매우 기초적이어서 구문과 문법은 문맥이 없는 문법 규칙, 특히 컴퓨터 과학에서 종종 식별된다.문법에 의해 포착되지 않은 형식적 제약은 언어의 "의미학"의 일부로 간주됩니다.

문맥이 없는 문법은 주어진 문자열에 대해 문법에 의해 생성될 수 있는지 여부와 방법을 결정하는 효율적인 구문 분석 알고리즘을 구성할 수 있을 정도로 단순합니다.얼리 파서는 이러한 알고리즘의 한 예입니다만, 널리 사용되는 LR 파서와 LL 파서는 문맥이 없는 문법의 보다 제한적인 서브셋만을 취급하는 단순한 알고리즘입니다.

정식 정의

문맥이 없는 문법 G는 G ( , , ,) { G = ( , \ , R , )} 로 정의됩니다[6].

  1. V는 유한 집합입니다.각 vV {\ v V 비말단 문자 또는 변수라고 불립니다.각 변수는 문장에서 다른 유형의 구 또는 절을 나타냅니다.변수는 구문 범주라고도 합니다.각 변수는 G에 의해 정의된 언어의 하위 언어를 정의합니다.
  2. δ는 V에서 분리유한한 단자 집합으로, 문장의 실제 내용을 구성합니다.터미널 세트는 문법 G에 의해 정의된 언어의 알파벳입니다.
  3. R은 V× ( ) \ V \ ( \ \ * }에서의 유한관계입니다.여기서 아스타리스크는 클린별 연산을 나타냅니다.R의 구성원은 (다시 쓰기) 규칙 또는 문법의 산물이라고 불립니다.(또한 일반적으로 P로 표시됨)
  4. S는 전체 문장(또는 프로그램)을 나타내기 위해 사용되는 시작 변수(또는 시작 기호)입니다.V의 요소여야 합니다.

생산규칙 표기법

R생성규칙은 수학적으로,)R {\alpha ,\ )\ R서 α V style \alpha \V 비단말기, ( ) ) ) \sigma ) *( \ ) ^{ ) 。생산 규칙은 일반적으로 α 왼쪽, β에 둔 화살표 연산자를 사용하여 작성됩니다.

β는 빈 문자열로 할 수 있으며, 이 경우 β로 나타내는 것이 관례입니다.α ε ( \ \ \varepsilon [7]γ-production이라고 합니다.

일반적으로 (파이프 기호)를 사용하여 동일한 좌측에 대한 모든 우측을 같은 선에 나열하여 구분합니다. 규칙 1(\ 2 (\ 쓸 수 있다. 이 경우 1 β 2 1 β β 2 δ 2 δ 2 β 2 2 β 1 β 2 β 1 β β 2 β 2 β β β β β β β _ 각각 제1의 대안과 제2의 대안으로 불린다.

규칙 적용

u, ( ( ) {\ { \ \ ( \ \ Sigma *}, directly 、 \ \ ( \ )로 직접 v를 출력합니다. 2 ({ v, =alpha v 2 ({ v, u {1}\2 규칙 결과입니다

반복 규칙 적용

임의의 u , ( ( V ) , {\( \Sigma 대해, u산출량은, k 의 정의 k ( σσ σ ), {ldots { {1}, {}, u}, u}, u} 의 이든 상관없습니다. u 화살표오른쪽 \오른쪽 }=이 관계는 일부 교재에서는 v{\ {\ 또는 u v \u\v로 되어 있습니다.k2 { \ k \ 2일 경우 u+ { \ u { \ { + } { \ 가 유지됩니다. ( { ( \ { * } { \ )및 ( +) ( \ { + } { \ )는문자열을 스스로 양보할 수 있는)의 재귀적 전이폐(최소한1단계 이상 필요입니다.화려하게

문맥이 없는 언어

G ( , , ,) { G = ( , \ , S 언어는 집합입니다.

시작 기호에서 파생할 수 있는 모든 종단 문자열의 경우.

L 언어는 L = () \ L , , L ( )과 CFG G가 존재하는 경우 Context-Free Language(CFL; 컨텍스트 프리 언어)라고 합니다.

비결정론적 푸시다운 오토마타는 문맥이 없는 언어를 정확하게 인식합니다.

단어와 그 역어가 연결되어 있다.

G ({ , { , , ,) { G = ( \ { \ , \ { , \ , , ) 、product product 。

SaSa,
SbSb,
S → 、

는 컨텍스트가 없습니다.--프로덕션이 포함되어 있기 때문에 적절하지 않습니다.이 문법의 대표적인 파생어는 다음과 같습니다.

SaSaaaSaaabSbaaaabbaa.

이를 통해 L( ) { : { , b { L ( G ) = \ { { : w \ \ { , \ }^{ *}} } l this this 。그 언어는 문맥이 없지만 규칙적이지 않다는 것을 증명할 수 있다.

프로덕션이

Sa,
Sb,

알파벳 {a, b} 위의 모든 회문 집합에 대한 문맥 없는 문법을 얻을 수 있습니다.[8]

올바른 형식의 괄호

문맥이 없는 문법의 표준적인 예는 괄호 매칭입니다.이것은 일반적인 경우를 대표하는 것입니다.2개의 단자 기호(""와 "")와 1개의 비단자 기호 S가 있습니다.제작 규칙은

SSS,
S → (S),
S → ()

첫 번째 규칙에서는 S 기호를 곱할 수 있습니다.두 번째 규칙에서는 일치하는 괄호로 S 기호를 묶을 수 있습니다.세 번째 규칙에서는 [9]재귀가 종료됩니다.

올바른 형식의 네스트 괄호 및 대괄호

두 번째 표준 예는 두 가지 종류의 일치하는 중첩 괄호입니다.이러한 괄호는 프로덕션에서 설명합니다.

SSS
S → ()
S → (S)
S → [ ]
S → [S]

단자 기호 [ ] ( )와 비단말기 S를 사용합니다.

이 문법으로 다음 시퀀스를 도출할 수 있습니다.

([ [ [ ()() [ ][ ] ] ]([ ]) ])

짝짓기 쌍

문맥이 없는 문법은 괄호처럼 문자를 조합할 수 있습니다.가장 간단한 예:

S → aSb
S → ab

이 문법은 { n : n 1 { \ { b 1 언어를 생성합니다(일반 언어의 펌핑 보조법에 따라).

특수문자 stands는 빈 문자열을 나타냅니다.위의 문법을 로 바꿈으로써

S → aSb
S → ε

대신 언어{ n : 0 { \ { b 0 생성하는 문법을 구한다.이것은 빈 문자열이 포함되어 있지만 원래 문법은 포함되어 있지 않다는 점에서만 다릅니다.

a와 b의 고유 수

a와 b의 수가 같지 않은 {a, b} 이상의 모든 문자열로 구성된 언어에 대한 컨텍스트 없는 문법:

S → T U
T → VaT VaV TaV
U → VbU VbV UbV
V → aVbV bVaV †

여기서 비단말기 T는 b보다 많은 모든 문자열을 생성할 수 있으며, 비단말기 U는 a보다 많은 b를 가진 모든 문자열을 생성하고, 비단말기 V는 같은 수의 a와 b를 가진 모든 문자열을 생성할 수 있다.T와 U의 규칙에서 세 번째 대안을 생략하는 것은 문법의 언어를 제한하지 않는다.

두 배 크기의 두 번째 b 블록

비정규 언어의 또 다른로는 { n : 0 , 0 0 {\\{b} {a} {\0, 0이 있습니다.문법은 문법에 의존하지 않습니다.

SbSbb A
AaA »

1차 논리식

형식 논리의 용어와 공식에 대한 형성 규칙은 문맥 자유 문법의 정의에 부합하지만, 기호 집합은 무한할 수 있고 시작 기호가 두 개 이상 있을 수 있습니다.

문맥이 없는 언어의 예

앞서 설명한 네스트된 괄호 및 각 괄호와는 달리 두 가지 다른 유형의 괄호 시퀀스를 모두 생성하기 위한 컨텍스트프리 문법은 없습니다.각각 다른 유형의 괄호는 각각 다른 유형의 괄호를 무시한 채 개별적으로 균형 있게 생성됩니다.예를 들어 두 유형이 서로 중첩할 필요가 없습니다.

[ ( ] )

또는

[ [ [ [(((( ] ] ] ]))))(([ ))(([ ))([ )( ])( ])( ])

이 언어가 문맥이 자유롭지 않다는 사실은 문맥이 없는 언어에 대한 펌프 보조어를 사용하여 증명할 수 있으며 모순에 의한 증명은 ([ )n \ { ( )^{n}{[ }^{를 관찰할 수 있다. {{n} {]} n}}은(는) 언어에 속해야 합니다. 언어는 보다 일반적인 클래스에 속하며 접속문법으로 기술할 수 있습니다.접속문법에는 n n n \ \ text { }^{ } { \ { }{ n} { \ { }^{n 단어의 언어 등 문맥이 없는 다른 언어도 포함됩니다.

정규 문법

모든 정규 문법은 문맥이 없지만 문맥이 없는 모든 문법이 [10]정규인 것은 아닙니다.예를 들어 다음과 같은 문맥이 없는 문법도 규칙적입니다.

Sa
SaS
SbS

여기의 단말기는 ab인데 비단말기는 S뿐입니다.설명되는 언어는 모두 빈 이 아닌\ b입니다.

이 문법은 규칙입니다.어떤 규칙도 오른쪽 끝에 여러 개의 비터미널을 가지고 있지 않으며 이들 비터미널 각각은 오른쪽 끝에 있습니다.

모든 정규 문법은 비결정론적 유한 오토마톤에 직접 대응하기 때문에 우리는 이것이 정규 언어라는 것을 알고 있습니다.

파이프 기호를 사용하면 위의 문법을 다음과 같이 보다 간결하게 설명할 수 있습니다.

SaS bS

파생 및 구문 트리

문법에 대한 문자열 파생은 시작 기호를 문자열로 변환하는 일련의 문법 규칙 응용 프로그램입니다.파생은 문자열이 문법의 언어에 속함을 증명합니다.

도출은 각 단계에 대해 다음과 같이 완전히 결정됩니다.

  • 그 단계에서 적용되는 규칙
  • 그것이 적용되는 왼쪽의 발생

알기 쉽게 하기 위해 보통 중간 문자열도 제공됩니다.

예를 들어 다음과 같은 문법을 사용합니다.

  1. SS + S
  2. S → 1
  3. Sa

현악기

1 + 1 + a

출발 기호 S에서 다음과 같은 파생 결과를 얻을 수 있습니다.

S
S + S(규칙 1. S에 따름)
S + S + S (규칙 1. 두 번째 S)
1 + S + S (규칙 2. 첫 번째 S)
→ 1 + 1 + S(규칙 2. 두 번째 S)
→ 1 + 1 + a (3번째 S 규칙)

대부분의 경우 다음 비단말기를 결정적으로 선택하여 다시 쓰는 전략을 따릅니다.

  • 최좌측 유도에서는 항상 최좌측 비단말기이다.
  • 오른쪽 끝 유도에서는 항상 오른쪽 끝 비말단입니다.

그러한 전략이 주어지면, 파생은 적용되는 규칙의 순서에 따라 완전히 결정된다.예를 들어, 동일한 문자열의 왼쪽 끝 파생은 다음과 같습니다.

S
S + S(맨 왼쪽 S의 규칙 1에 따름)
1 + S(맨 왼쪽 S의 규칙 2에 따름)
1 + S + S (맨 왼쪽 S의 규칙 1)
→ 1 + 1 + S(왼쪽 S의 규칙 2)
→ 1 + 1 + a (맨 왼쪽 S의 규칙 3에 따라),

라고 요약할 수 있다.

규칙 1
규칙 2
규칙 1
규칙 2
규칙 3.

가장 오른쪽에 있는 파생 요소는 다음과 같습니다.

S
S + S(가장 오른쪽 S의 규칙 1에 따름)
S + S + S (최우측 S의 규칙 1에 따라)
S + S + a (최우측 S의 규칙 3에 따라)
S + 1 + a (최우측 S의 규칙 2에 따라)
→ 1 + 1 + a (최우측 S의 규칙 2에 따라),

라고 요약할 수 있다.

규칙 1
규칙 1
규칙 3
규칙 2
규칙 2

대부분의 파서에서 입력의 변환은 규칙이 적용될 때마다 실행되는 모든 문법 규칙에 대해 하나의 코드를 부여함으로써 정의되기 때문에 왼쪽 파생과 오른쪽 파생의 구별이 중요합니다.따라서 파서가 코드 조각이 실행되는 순서를 결정하므로 파서가 가장 왼쪽 또는 가장 오른쪽 중 어느 쪽을 결정하는지 아는 것이 중요합니다.LL 파서 및 LR 파서에 대해서는, 을 참조해 주세요.

파생은 어떤 의미에서 파생된 문자열에 계층 구조를 부과하기도 합니다.예를 들어 문자열 "1 + 1 + a"가 위에서 설명한 가장 왼쪽의 파생에 따라 파생되는 경우 문자열의 구조는 다음과 같습니다.

{{S1} + {1} +S {a}}SSS

여기서 {...}은 S에 속하는 것으로 인식된 서브스트링을 나타냅니다.S이 계층은 트리로도 볼 수 있습니다.

Rightmost derivation of 1 + 1 + a

트리는 추상 구문 트리와 대조적으로 문자열의 구문 분석 트리 또는 "구체 구문 트리"라고 합니다.이 경우 표시된 왼쪽 끝과 오른쪽 끝 파생은 동일한 해석 트리를 정의합니다.단, 같은 문자열의 오른쪽 끝 파생이 또 있습니다.

S
S + S(가장 오른쪽 S의 규칙 1에 따름)
S + a(가장 오른쪽 S의 규칙 3에 따름)
S + S + a (최우측 S의 규칙 1에 따라)
S + 1 + a (최우측 S의 규칙 2에 따라)
→ 1 + 1 + a (최우측 S의 규칙 2에 따라),

다른 구조를 가진 문자열을 정의합니다.

{{1} +S {1}}SS + {a}SS

및 다른 해석 트리:

Leftmost derivation of 1 + 1 + a

단, 해석 트리는 최좌측과 최우측 모두 도출에 의해 취득할 수 있습니다.예를 들어, 마지막 트리는 다음과 같이 가장 왼쪽의 파생 정보로 얻을 수 있습니다.

S
S + S(맨 왼쪽 S의 규칙 1에 따름)
S + S + S (맨 왼쪽 S의 규칙 1에 따라)
1 + S + S (맨 왼쪽 S의 규칙 2)
→ 1 + 1 + S(왼쪽 S의 규칙 2)
→ 1 + 1 + a (맨 왼쪽 S의 규칙 3에 따라),

문법 언어의 문자열에 두 개 이상의 구문 분석 트리가 있는 경우 문법은 애매한 문법이라고 합니다.파서가 적용할 문법 규칙을 항상 결정할 수는 없기 때문에 이러한 문법은 일반적으로 해석하기가 어렵습니다.일반적으로 모호성은 언어가 아닌 문법의 특징이며, 문맥이 없는 동일한 언어를 생성하는 모호하지 않은 문법을 찾을 수 있습니다.하지만, 모호한 문법에 의해서만 생성될 수 있는 특정한 언어들이 있습니다; 그러한 언어들은 본질적으로 모호한 언어라고 불립니다.

예:대수식

변수 x, y 및 z의 구문적으로 올바른 infix 대수식을 위한 문맥 없는 문법을 다음에 나타냅니다.

  1. Sx
  2. Sy
  3. Sz
  4. SS + S
  5. SSS
  6. SS * S
  7. SS / S
  8. S → (S)

예를 들어 이 문법은 문자열을 생성할 수 있습니다.

(x + y) * xz * y / (x + x)

다음과 같습니다.

S
SS (규칙 5에 따라)
S * S – S (규칙 6에 따라 가장 왼쪽 S에 적용)
S * S S / S (규칙 7에 따라 가장 오른쪽 S에 적용)
(S) * S S / S (규칙 8에 따라 가장 왼쪽 S에 적용)
(S) * SS / (S) (규칙 8에 따라 가장 오른쪽 S에 적용)
(S + S) * S – S / (S) (규칙 4에 따라 가장 왼쪽 S에 적용)
(S + S) * S – S * S / (S) (규칙 6에 따라 네 번째 S에 적용)
(S + S) * S – S * S / (S + S) (규칙 4에 따라 가장 오른쪽 S에 적용됨)
(x + S) * S S * S / (S + S) (등)
→ (x + y) * SS * S / (S + S)
→ (x + y) * xS * S / (S + S)
→ (x + y) * x – z * S / (S + S)
→ (x + y) * x – z * y / (S + S)
→ (x + y) * xz * y / (x + S)
→ (x + y) * xz * y / (x + x)

다음에 어떤 개서를 실행할지에 대해 많은 선택이 진행 중이었음을 유의하십시오.이 선택들은 상당히 자의적으로 보입니다.실제로 최종적으로 생성된 문자열은 항상 동일하다는 점에서 동일합니다.예를 들어, 두 번째와 세 번째가 다시 씁니다.

S * S – S (규칙 6에 따라 가장 왼쪽 S에 적용)
S * S S / S (규칙 7에 따라 가장 오른쪽 S에 적용)

반대 순서로 실행할 수 있습니다.

S S / S (규칙 7에 따라 가장 오른쪽 S에 적용)
S * S S / S (규칙 6에 따라 가장 왼쪽 S에 적용)

또한 선택된 각 S에 어떤 규칙을 적용할 것인지 많은 선택이 이루어졌다.선택한 순서뿐만 아니라 선택한 항목을 변경하면 일반적으로 마지막에 나오는 단말기 문자열에 영향을 미칩니다.

이것을 좀 더 자세히 살펴봅시다.이 파생물의 해석 트리를 검토합니다.

An example parse tree

위에서 시작하여 트리의 S가 단계별로 확장되어 확장되지 않은 Ses(비종단)가 더 이상 남아 있지 않을 때까지 확장됩니다.다른 확장 순서를 선택하면 다른 파생이 생성되지만 동일한 해석 트리가 생성됩니다.해석 트리는 트리의 특정 위치에 적용할 다른 규칙을 선택한 경우에만 변경됩니다.

그러나 다른 해석 트리에서 동일한 터미널 문자열(이 경우 (x + y) * x z * y / (x + x))을 생성할 수 있습니까?네, 이 문법은 가능합니다.이 성질을 가진 문법은 애매하다고 불립니다.

예를 들어 x + y * z다음 두 가지 해석 트리로 생성할 수 있습니다.

Two different parse trees from the same input

그러나 이 문법에 의해 기술된 언어는 본질적으로 모호하지 않습니다. 예를 들어 다음과 같이 언어에 대해 대체적이고 모호하지 않은 문법을 제공할 수 있습니다.

Tx
Ty
Tz
SS + T
SST
SS * T
SS/T
T → (S)
ST,

다시 한 번 S를 시작 기호로 선택합니다.이 대체 문법은 위의 왼쪽 문법과 유사한 해석 트리를 사용하여 x + y * z생성합니다. 즉, 표준 연산 순서를 따르지 않는 연관(x + y) * z를 암묵적으로 가정합니다.원하는 모든 연산자 우선 순위 및 연관성 규칙을 따르는 해석 트리를 생성하는 보다 정교하고 모호하지 않으며 컨텍스트가 없는 문법을 구성할 수 있습니다.

표준형식

문맥이 없는 문법은 모두 촘스키 노멀 형식의 문법과 그리바흐 노멀 형식의 문법이 동일합니다.여기서 "동등"은 두 문법이 같은 언어를 생성한다는 것을 의미합니다.

촘스키 정규형 문법에서 특히 단순한 형태의 생산 규칙은 이론적인 의미와 실제적인 의미를 모두 가지고 있다.예를 들어, 문맥이 없는 문법이 주어진다면, 촘스키 정규 형식을 사용하여 주어진 문자열이 해당 문법이 나타내는 언어(CYK 알고리즘)에 있는지 여부를 결정하는 다항식 시간 알고리즘을 구성할 수 있습니다.

닫힘 속성

문맥이 없는 언어는 다양한 조작으로 닫힙니다., 언어 K와 L이 문맥이 없는 경우 다음 조작의 결과도 마찬가지입니다.

이들은 일반 교차로에서는 닫히지 않으며(따라서 상호 보완에서는 닫히지 않음) 차이를 [15]설정한다.

결정 가능한 문제

다음은 문맥이 없는 문법에 대한 몇 가지 결정 가능한 문제입니다.

해석

특정 단어가 문맥이 없는 문법에 의해 주어진 언어에 속하는지 여부를 확인하는 해석 문제는 범용 해석 알고리즘 중 하나를 사용하여 판단할 수 있습니다.

촘스키 정규 형식 문법에 대한 문맥 없는 해석은 Leslie G. Valiant에 의해 부울 행렬 곱셈으로 환원될 수 있다는 것을 보여주었고, 따라서 복잡도 상한인 O(n2.3728639)[16][17][note 1]를 상속받았다.반대로, Lillian Lee는 O3−ε(n) 부울 행렬 곱셈이 O3−3ε(n) CFG 해석으로 환원될 수 있음을 보여주었고,[18] 따라서 후자에 대한 일종의 하한을 확립했습니다.

도달 가능성, 생산성, 무효화

문법 예:
SBb Cc Ee
BBb b
CC
DBd CD d
E → Ee

비단말기 X(\ X 일부 w w 파생 X X {\ 있는 경우 생산적 또는 생성이라고 합니다. X 일부 ,β(\, nonterminal의 \displaystyle \ \) 및 terminal 심볼의 시작에서 된 Sdisplaystyle S 있는 경우도달 가능합니다. X 도달할 수 없거나 생산적이지 않으면 무용지물이라고 합니다.X})는 파생 X X}}}\가 있는 경우 nullable이라고 .규칙 X{X\varepsilon ε anction라고 불립니다. Xδ + {\ X {\ {\ 순환이라고 합니다.

알고리즘은 생성된 언어를 변경하지 않고 주어진 문법을 제거하는 것으로 알려져 있다.

특히 불필요한 비말단 심볼을 포함한 대안을 규칙의 오른쪽에서 삭제할 수 있다.그런 규칙과 대안을 [25]쓸모없는 것이라고 한다.

예시 문법에서 비말단 D는 도달할 수 없고 E는 비생산적인 반면 C → C는 사이클을 일으킨다.따라서 마지막 세 가지 규칙을 생략해도 문법에 의해 생성된 언어가 변경되지 않으며 S 규칙의 오른쪽에서 대체 "Cc Ee"가 누락되지 않습니다.

문맥이 없는 문법은 쓸모없는 기호나 --생성, [26]순환이 없다면 적절하다고 한다.상기 알고리즘을 조합하면 θ를 생성하지 않는 모든 문맥 없는 문법을 약등가 고유 문법으로 변환할 수 있다.

규칙성 및 LL(k) 체크

주어진 문법이 정규 [27]문법인지 아닌지는 물론 주어진 k00에 [28]: 233 대한 LL(k) 문법인지도 판단할 수 있다.k를 지정하지 않으면 후자의 문제는 판별할 [28]: 252 수 없습니다.

문맥이 없는 언어가 주어졌을 때,[29] 그것이 정규 언어인지도,[28]: 254 주어진 k에 대한 LL(k) 언어인지도 판단할 수 없습니다.

공허함과 결말성

주어진 문맥이 없는 언어의 언어가 비어 있는지 여부 및 [30]유한한지를 결정하는 알고리즘이 있습니다.

결정할 수 없는 문제

더 넓은 클래스의 문법에 대해 결정할 수 없는 일부 질문은 문맥이 없는 문법에 대해 결정할 수 있습니다. 예를 들어, 공허함 문제(문법이 끝 문자열을 생성하는지 여부)는 문맥에 민감한 문법에 대해서는 결정할 수 없지만 문맥이 없는 문법에 대해서는 결정할 수 없습니다.

그러나 문맥이 없는 문법에도 많은 문제가 해결되지 않습니다.예를 들면 다음과 같습니다.

유니버설리티

CFG를 지정하면 [31][32]규칙에 사용되는 단말기 기호 알파벳에 대해 모든 문자열의 언어를 생성합니까?

튜링 기계가 특정 입력(정지 문제)을 받아들일지 여부를 결정하는 잘 알려진 결정 불가능한 문제에서 이 문제에 대한 감소가 입증될 수 있다.축소는 튜링 기계의 전체 계산을 설명하는 문자열인 계산 이력의 개념을 사용합니다.CFG는 특정 입력에 대해 특정 튜링 머신의 계산 이력을 받아들이지 않는 모든 문자열을 생성하는 것으로 구성될 수 있으며, 따라서 기계가 해당 입력을 받아들이지 않을 경우에만 모든 문자열을 받아들인다.

언어의 평등

2개의 CFG를 지정하면 같은 [32][33]언어를 생성합니까?

이 문제의 판별 불능은 앞의 문제의 직접적인 결과입니다.CFG가 모든 스트링의 언어를 정의하는 사소한 CFG와 동등한지 여부를 판단할 수도 없습니다.

언어 포함

2개의 CFG를 지정하면 첫 번째 CFG는 두 번째 CFG가 [32][33]생성할 수 있는 모든 문자열을 생성할 수 있습니까?

이 문제가 결정 가능한 경우 언어의 평등도 결정할 수 있습니다.L(G1)이 L(G2)의 서브셋이고 L(G2)이 L(G1)의 서브셋인 경우, 2개의 CFG G1과 G2가 같은 언어를 생성합니다.

촘스키 계층의 하위 또는 상위 레벨에 있는 것

Greibach의 정리를 사용하면 다음 두 가지 문제를 결정할 수 없다는 것을 알 수 있습니다.

  • 문맥에 민감한 문법을 지정하면 문맥이 없는 언어를 설명합니까?
  • 문맥이 없는 문법이 주어졌을 때, 그것[32][33]정규 언어를 묘사하는가?

문법의 모호성

CFG를 지정하면 애매한가요?

이 문제의 결정 불가능성은 모호성을 결정하는 알고리즘이 존재하면 결정 불가능하다고 알려진 사후 대응 문제가 결정될 수 있다는 사실에서 비롯됩니다.

언어의 불연속성

2개의 CFG를 지정하면 양쪽 문법에서 파생할 수 있는 문자열이 있습니까?

이 문제를 해결할 수 있는 경우에는 할 수 없는 Post 대응 문제도 결정할 수 있습니다., 1, N \ \N \{,\ \ N}, \style \ \style G 규칙으로 구성됩니다.

1 e N r b { S \ _ {S \ _ { { { \ \_ { } \ { N ;

\ \_ { }^}는 반전 i\ \_ { }이며, b\ b}는i \ _ { 사이에 발생하지 않습니다.{ 로 구성됩니다.

} \b

다음으로 1, N 1, N _에 의해 주어지는 Post 문제에는L 1 displaystyle 에만 해결 방법이 있습니다.

내선번호

문맥 없는 문법 형식주의를 확장하는 분명한 방법은 비말단어가 인수를 갖도록 허용하는 것입니다. 이 인수의 값은 규칙 내에서 전달됩니다.이를 통해 일치 참조와 같은 자연스러운 언어 특징과 식별자의 올바른 사용 및 정의와 같은 프로그래밍 언어 유사점을 자연스러운 방식으로 표현할 수 있습니다.예를 들어, 우리는 이제 영어 문장에서 주어와 동사의 수가 일치해야 한다는 것을 쉽게 표현할 수 있다.컴퓨터 과학에서 이 접근법의 로는 접사 문법, 속성 문법, 색인 문법, 반 빈가르덴 2단계 문법이 있습니다.언어학에도 비슷한 확장이 존재한다.

문맥 자유 확장 문법(또는 정규 오른쪽 부분 문법)은 생성 규칙의 오른쪽이 문법의 종단 및 비말단 위에 정규 표현식이 되도록 허용된 문법입니다.문맥이 없는 확장된 문법은 문맥이 없는 [34]언어를 정확하게 기술합니다.

또 다른 확장 기능은 추가 터미널 기호가 규칙의 왼쪽에 나타나도록 허용하여 적용을 제한하는 것입니다.이것은 문맥에 민감한 문법의 형식주의를 낳는다.

서브클래스

문맥이 없는 문법의 중요한 서브클래스는 다음과 같습니다.

  • LR(k) 문법(결정론적 문맥 자유 문법이라고도 함)은 결정론적 푸시다운 오토마타(PDA)를 사용한 구문 분석(문자열 인식)을 허용하지만, 결정론적 문맥 자유 언어만 기술할 수 있습니다.
  • 단순 LR, Look-Ahead LR 문법은 파싱을 더욱 단순화할 수 있는 하위 클래스입니다.SLR 및 LALR은 LR과 동일한 PDA를 사용하여 인식되지만 대부분의 경우 단순한 표로 인식됩니다.
  • LL(k) 및 LL(*) 문법은 위에서 설명한 바와 같이 왼쪽 끝의 파생물을 직접 구문 분석할 수 있으며 더 적은 수의 언어를 기술할 수 있습니다.
  • 단순문법은 단순문법의 언어평등성은 결정가능하지만 언어포함성은 결정가능하지 않다는 이론적 특성 때문에 LL(1)문법의 하위분류이다.
  • 괄호로 묶인 문법은 종단 기호가 규칙 내에서 항상 일치하는 왼쪽 및 오른쪽 괄호 쌍으로 분할되는 특성이 있습니다.
  • 선형 문법은 오른쪽에 여러 개의 비말단이 있는 규칙이 없습니다.
  • 정규 문법은 선형 문법의 하위 클래스이며 정규 언어, 즉 유한 오토마타정규 표현에 대응합니다.

LR 파싱은 LL 파싱을 확장하여 보다 광범위한 문법을 지원합니다.그 결과 일반화된 LR 파싱은 LR 파싱을 확장하여 임의의 컨텍스트가 필요 없는 문법을 지원합니다.LL 문법 및 LR 문법에서는 기본적으로 각각 LL 구문 분석 및 LR 구문 분석을 수행하지만 비결정론적 문법에서는 기대한 만큼 효율적입니다.GLR 파싱은 1980년대에 개발되었지만 많은 새로운 언어 정의와 파서 생성기는 오늘날까지 LL, LALR 또는 LR 파싱에 기반하고 있습니다.

언어 응용 프로그램

촘스키는 처음에 변환 [4]규칙을 추가함으로써 문맥이 없는 문법의 한계를 극복하기를 희망했다.

이러한 규칙은 전통적인 언어학에서 또 다른 표준 장치입니다. 예를 들어 영어의 수동화입니다.생성문법의 많은 부분은 문법과 변환규칙의 서술적 메커니즘을 정교하게 하는 방법을 찾는데 전념하여 자연어가 실제로 허용하는 종류의 것들을 정확하게 표현할 수 있도록 한다.임의의 변환을 허용하는 것은 그 목표를 달성하지 못한다: 그것들은 매우 강력하며, 중대한 제한이 추가되지 않는 한 튜링이 완전하다(예를 들어 문맥 없는 방식으로 기호를 도입하고 다시 쓰는 변환 없음).

자연어의 문맥이 없는 문법에 대한 촘스키의 일반적인 입장은 그 [35]이후로 유지되었지만, 문맥이 없는 문법의 약한 생성 능력의 부족에 대한 그의 구체적인 예는 나중에 반증되었다.[36]Gerald Gazdar와 Geoffrey Pullum은 자연어로 문맥이 없는 몇 가지 구성(스위스[35] 독일어에서의 교차직렬 의존관계 밤바라어[37] 복제 등)에도 불구하고 자연어로 된 대부분의 형태는 문맥이 없다고 [36]주장했습니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ Brian W. Kernighan and Dennis M. Ritchie (Apr 1988). The C Programming Language. Prentice Hall Software Series (2nd ed.). Englewood Cliffs/NJ: Prentice Hall. ISBN 0131103628. 여기: 앱.a
  2. ^ 오토마타 이론, 언어, 계산 소개, John E.홉크로프트, 라지예프 모트와니, 제프리 D.울먼, 애디슨 웨슬리, 2001, 페이지 191
  3. ^ a b 홉크로프트 & 울먼(1979), 페이지 106.
  4. ^ a b Chomsky, Noam (Sep 1956), "Three models for the description of language", IEEE Transactions on Information Theory, 2 (3): 113–124, doi:10.1109/TIT.1956.1056813
  5. ^ https://web.stanford.edu/~slpafsky/slp3/12.pdf[베어 URL PDF]
  6. ^ 여기서의 표기법은 Sipser(1997), 페이지 94의 표기법입니다.Hopcroft & Ullman(1979) (p.79)에서는 문맥이 없는 문법을 같은 방법으로 4튜플이라고 정의하지만 변수명은 다릅니다.
  7. ^ 홉크로프트 & 울먼(1979), 90~92페이지.
  8. ^ 홉크로프트 & 울먼(1979), 연습 4.1a, 페이지 103.
  9. ^ 홉크로프트 & 울먼(1979), 연습 4.1b, 페이지 103.
  10. ^ Aho, Alfred Vaino; Lam, Monica S.; Sethi, Ravi; Ullman, Jeffrey David (2007). "4.2.7 Context-Free Grammars Versus Regular Expressions" (print). Compilers: Principles, Techniques, & Tools (2nd ed.). Boston, MA USA: Pearson Addison-Wesley. pp. 205–206. ISBN 9780321486813. Every construct that can be described by a regular expression can be described by a [context-free] grammar, but not vice-versa.
  11. ^ 홉크로프트 & 울먼(1979), 페이지 131, 정리 6.1
  12. ^ 홉크로프트 & 울먼(1979), 131~132, 정리 6.2
  13. ^ 홉크로프트 & 울먼(1979), 132-134쪽, 정리 6.3
  14. ^ 홉크로프트 & 울먼(1979), 135~136, 정리 6.5
  15. ^ 홉크로프트 & 울먼(1979), 134-135페이지, 정리 6.4
  16. ^ Leslie Valiant (Jan 1974). General context-free recognition in less than cubic time (Technical report). Carnegie Mellon University. p. 11.
  17. ^ Leslie G. Valiant (1975). "General context-free recognition in less than cubic time". Journal of Computer and System Sciences. 10 (2): 308–315. doi:10.1016/s0022-0000(75)80046-8.
  18. ^ Lillian Lee (2002). "Fast Context-Free Grammar Parsing Requires Fast Boolean Matrix Multiplication" (PDF). J ACM. 49 (1): 1–15. arXiv:cs/0112018. doi:10.1145/505241.505242. S2CID 1243491.
  19. ^ Hopcroft & Ullman(1979), Lemma 4.1, 페이지 88.
  20. ^ Aiken, A.; Murphy, B. (1991). "Implementing Regular Tree Expressions". ACM Conference on Functional Programming Languages and Computer Architecture. pp. 427–447. CiteSeerX 10.1.1.39.3766.;여기서: 제4장
  21. ^ 홉크로프트 & 울먼(1979), 레마 4.2, 89페이지.
  22. ^ Hopcroft, Motwani & Ullman (2003) 오류:: CITREFHopcroft Ullman 2003 ( 정리 7.2, 제7.1장, 페이지 255ff
  23. ^ (PDF) https://www.springer.com/cda/content/document/cda_downloaddocument/9780387202488-c1.pdf?SGWID=0-0-45-466216-p52091986. {{cite web}}:누락 또는 비어 있음 title=(도움말)
  24. ^ 홉크로프트 & 울먼(1979), 정리 4.3, 페이지 90.
  25. ^ John E. Hopcroft; Rajeev Motwani; Jeffrey D. Ullman (2003). Introduction to Automata Theory, Languages, and Computation. Addison Wesley.;여기서: 제7.1.1장, 페이지 256
  26. ^ 를 클릭합니다Nijholt, Anton (1980), Context-free grammars: covers, normal forms, and parsing, Lecture Notes in Computer Science, vol. 93, Springer, p. 8, ISBN 978-3-540-10245-8, MR 0590047.
  27. ^ 이것은 문법의 정의를 보면 쉽게 알 수 있다.
  28. ^ a b c D.J. Rosenkrantz and R.E. Stearns (1970). "Properties of Deterministic Top Down Grammars". Information and Control. 17 (3): 226–256. doi:10.1016/S0019-9958(70)90446-8.
  29. ^ Hopcroft & Ullman(1979), 연습 8.10a, 페이지 214.이 문제는 언어가 "선형" 문맥이 없는 문법(즉, 각 규칙의 오른쪽에 최대 1개의 비말단이 있는 cf)에 의해 생성되어도 결정되지 않는 상태로 남아 있습니다.연습 4.20, 페이지 105).
  30. ^ 홉크로프트 & 울먼(1979), 137-138페이지, 정리 6.6
  31. ^ Sipser(1997), 정리 5.10, 페이지 181.
  32. ^ a b c d 홉크로프트 & 울먼(1979), 페이지 281.
  33. ^ a b c 를 클릭합니다Hazewinkel, Michiel (1994), Encyclopaedia of mathematics: an updated and annotated translation of the Soviet "Mathematical Encyclopaedia", Springer, Vol. IV, p. 56, ISBN 978-1-55608-003-6.
  34. ^ Norvell, Theodore. "A Short Introduction to Regular Expressions and Context-Free Grammars" (PDF). p. 4. Retrieved August 24, 2012.
  35. ^ a b 를 클릭합니다Shieber, Stuart (1985), "Evidence against the context-freeness of natural language" (PDF), Linguistics and Philosophy, 8 (3): 333–343, doi:10.1007/BF00630917, S2CID 222277837.
  36. ^ a b 를 클릭합니다Pullum, Geoffrey K.; Gerald Gazdar (1982), "Natural languages and context-free languages", Linguistics and Philosophy, 4 (4): 471–504, doi:10.1007/BF00360802, S2CID 189881482.
  37. ^ 를 클릭합니다Culy, Christopher (1985), "The Complexity of the Vocabulary of Bambara", Linguistics and Philosophy, 8 (3): 345–351, doi:10.1007/BF00630918, S2CID 189881984.

메모들

  1. ^ Valiant의 논문에는 당시 가장 잘 알려진 상한인 O2.81(n)가 제시되어 있다.그 후의 대폭적인 향상에 대해서는, 매트릭스 곱셈 #계산 복잡도를 참조해 주세요.
  2. ^ 규칙적인 나무 문법의 경우, Aiken과 Murphy는 비생산적인 [20]비종단을 탐지하기 위한 고정점 알고리즘을 제공합니다.
  3. ^ 문법이 을 생성할 수 있는 경우 S S 피할 수 없습니다.
  4. ^ 이것은 Hopcroft & Ullman(1979), 페이지 91, 정리 4.4의 단위 생산 제거 정리의 결과이다.

추가 정보

  • Hopcroft, John E.; Ullman, Jeffrey D. (1979), Introduction to Automata Theory, Languages, and Computation, Addison-Wesley. 4장: 문맥 자유 문법, 77–106페이지; 6장: 문맥 자유 언어의 특성, 125–137페이지.
  • Sipser, Michael (1997), Introduction to the Theory of Computation, PWS Publishing, ISBN 978-0-534-94728-6. 2장: 문맥 자유 문법, 91–122페이지; 섹션 4.1.2: 문맥 자유 언어에 관한 결정 가능한 문제, 페이지 156–159; 섹션 5.1.1: 연산 이력을 통한 감소: 페이지 176–183.
  • J. Berstel, L. Boasson (1990). Jan van Leeuwen (ed.). Context-Free Languages. Handbook of Theoretical Computer Science. Vol. B. Elsevier. pp. 59–102.

외부 링크

  • 컴퓨터 프로그래머는 스택 교환 답변이 유용하다고 생각할 수 있습니다.
  • 2014년 Stanford University에서 Christopher Wong이 CFG Developer를 만들고 2015년 Kevin Gibbons에 의해 수정.