한정절 문법

Definite clause grammar

한정절 문법(DCG)은 자연어 또는 형식어 중 어느 쪽이든 프롤로그와 같은 논리 프로그래밍 언어로 문법을 표현하는 방법입니다.이것은 Prolog가 원래 개발된 속성 문법/접사 문법의 개념과 밀접하게 관련되어 있습니다.DCG는 보통 Prolog와 관련되어 있지만, Mercury와 같은 유사한 언어에도 DCG가 포함되어 있습니다.그것들은 1차 논리에서의 확정절 집합으로서 문법을 나타내기 때문에 확정절 문법이라고 불립니다.

DCG라는 용어는 프롤로그 및 기타 유사한 언어로 표현되는 특정 유형을 가리킵니다.확정구를 사용하여 문법을 표현하는 모든 방법이 DCG로 간주되는 것은 아닙니다.단, DCG의 모든 기능 또는 속성은 프롤로그와 기본적으로 동일한 방식으로 정의된 절로 표현되는 모든 문법에 대해 동일합니다.

DCG의 확정절들은 한 문장의 타당성, 그리고 그것이 특정한 해석 트리를 가지고 있다는 사실이 이러한 [1]공리에서 따르는 정리로 간주될 수 있는 일련의 공리들의 집합으로 간주될 수 있다.이것은 언어의 표현 인식과 파싱이 논리 프로그래밍 언어의 문장과 같이 문장을 증명하는 일반적인 문제가 되도록 하는 장점이 있습니다.

역사

DCG의 역사는 프롤로그의 역사와 밀접하게 관련되어 있으며, 프롤로그의 역사는 프랑스 마르세유와 스코틀랜드 에든버러에 있는 여러 연구자들을 중심으로 전개되고 있습니다.프롤로그의 초기 개발자인 로버트 코왈스키에 따르면, 최초의 프롤로그 시스템은 1972년 알랭 콜메라우어와 필리프 [2]루셀에 의해 개발되었다.그 언어로 작성된 첫 번째 프로그램은 큰 자연어 처리 시스템이었다.에든버러 대학의 Fernando Pereira와 David Warren도 Prolog의 초기 개발에 참여했습니다.

Colmerauer는 이전에 영어와 [3]프랑스어를 번역하기 위해 사용되는 Q-systems라고 불리는 언어 처리 시스템을 연구한 적이 있다.1978년, 콜메라우어는 마르세유 프롤로그라고 불리는 프롤로그의 초기 버전의 일부였던 변형 문법이라고 불리는 문법을 표현하는 방법에 대한 논문을 썼다.이 논문에서, 그는 변성 문법에 대한 공식적인 설명과 그것들을 사용하는 프로그램의 몇 가지 예를 제시했습니다.

프롤로그의 다른 초기 건축가 페르난도 페레이라와 데이비드 워렌은 "definite clause grammar"라는 용어를 만들고 오늘날 프롤로그에서 사용되는 DCG의 표기법을 만들었다.그들은 그 아이디어를 콜메라우어와 코왈스키에게 인정했고, DCG는 콜메라우어의 변성 문법의 특별한 경우라고 지적했습니다.그들은 "언어 분석을 위한 정의 조항 문법"이라는 기사에서 DCG를 "형식주의"로 묘사하는 아이디어를 소개했다.여기서 문법은 "프로그래밍 언어 프롤로그의 효과적인 프로그램을 구성하는" 1차 술어 논리의 절을 표현한다.[4]

페레이라, 워렌, 그리고 프롤로그의 다른 개척자들은 나중에 DCG의 몇 가지 다른 측면에 대해 썼다.Pereira와 Warren은 "Parsing as Deduation"이라는 기사를 썼고, Earley Deduation 증명 절차가 [5]파싱에 어떻게 사용되는지 등을 설명했다.Pereira는 Stuart M과 함께 작업하기도 했다. 로직 [6]프로그래밍을 사용한 컴퓨터 언어학의 일반적인 입문으로서 의도된 「프롤로그와 자연 언어 분석」이라고 불리는 책에 실렸다.

예

DCG의 기본적인 예는 DCG가 무엇이고 어떻게 생겼는지 설명하는 데 도움이 됩니다. 

 문장. --> 명사_어구, verb_phrase.  명사_어구 --> 멈추다, 명사.  verb_phrase --> 동사., 명사_어구.  멈추다 --> [그].  멈추다 --> [a].  명사 --> [고양이].  명사 --> [박쥐].  동사. --> [먹다].

이는 "고양이가 박쥐를 먹는다", "박쥐가 고양이를 먹는다"와 같은 문장을 만들어낸다.프롤로그 인터프리터에서 이 문법에 의해 생성된 언어로 모든 유효한 표현을 생성할 수 있습니다.sentence(X,[])비슷하게, 다음과 같은 것을 입력함으로써 문장이 언어에서 유효한지 테스트할 수 있다.sentence([the,bat,eats,the,bat],[]).

확정절로의 번역

DCG 표기법은 프롤로그의 정상적인 확정 절에 대한 통사적인 설탕일 뿐이다.예를 들어, 앞의 예는 다음과 같이 변환할 수 있습니다.

 문장.(A,Z) :- 명사_어구(A,B), verb_phrase(B,Z).  명사_어구(A,Z) :- 멈추다(A,B), 명사(B,Z).  verb_phrase(A,Z) :- 동사.(A,B), 명사_어구(B,Z).  멈추다([그 X], X).  멈추다([a X], X).  명사([고양이 X], X).  명사([박쥐 X], X).  동사.([먹다 X], X).

차이점 리스트

각 함수에 대한 인수(예:(A,B)그리고.(B,Z)는 차분 리스트입니다.차이 리스트는 리스트의 프레픽스를 2개의 서픽스(작은 서픽스 포함)의 차이로 나타내는 방법입니다.목록에 대한 Prolog 표기법 사용, 싱글톤 목록 접두사P = [H]사이의 차이로 볼 수 있다[H X]그리고.X, 즉, 쌍으로 표시됩니다.([H X],X),예를 들어.

라고 말하는 것P의 차이입니다.A그리고.B라고 말하는 것과 같다append(P,B,A)보류. 또는 이전 예제의 경우,append([H],X,[H X]).

차분 리스트는 효율성의 이유로 DCG를 사용한 리스트를 나타내기 위해 사용됩니다.리스트의 차이(프리픽스)를 사용할 수 있는 상황에서는, 리스트의 차이(프리픽스)를 접속하는 것이, 보다 효율적입니다.이것은, 리스트의 차이(프리픽스)를 접속하는 것이,(A,B)그리고.(B,Z)그냥(A,Z)를 클릭합니다.[7]

실제로.append(P,B,A), append(Q,Z,B)수반하다append(P,Q,S), append(S,Z,A)이것은 목록 연결이 연관성이 있다고 말하는 것과 같습니다.

A = P + B = P + (Q + Z) = (P + Q) + Z = S + Z = A

문맥이 없는 문법

순수 프롤로그에서는 앞의 예와 같이 함수에 추가 인수가 없는 일반 DCG 규칙은 컨텍스트프리 문법만 표현할 수 있습니다.작성 왼쪽에 인수는 1개뿐입니다.다만, 컨텍스트에 의존한 문법은, 다음의 예와 같이 추가의 인수를 지정하는 것으로써, DCG 를 사용해 표현할 수도 있습니다.

 s --> a(N), b(N), c(N).  a(0) --> [].  a(M) --> [a], a(N), {M 이 N + 1}.  b(0) --> [].  b(M) --> [b], b(N), {M 이 N + 1}.  c(0) --> [].  c(M) --> [c], c(N), {M 이 N + 1}.

이 DCG 규칙 집합은 a n n \ a b c[8] 의 문자열로 구성된 언어를 생성하는 문법을 설명합니다.

 s --> 기호(셈,a), 기호(셈,b), 기호(셈,c).  기호(끝.,_) --> [].  기호(s(셈),S) --> [S], 기호(셈,S).

이 DCG 규칙 집합은 n을 구조적으로 표현함으로써[citation needed] a n \ a c 의 문자열로 구성된 언어를 생성하는 문법을 설명합니다.

특징의 표시

DCG에서는 [9]함수에게 추가 인수를 제공함으로써 다양한 언어적 특징을 상당히 간결하게 나타낼 수 있습니다.예를 들어, 다음의 DCG 규칙 세트를 생각해 보겠습니다.

 문장. --> 대명사(주제), verb_phrase.  verb_phrase --> 동사., 대명사(물건).  대명사(주제) --> [그].  대명사(주제) --> [그녀는.].  대명사(물건) --> [그야.].  대명사(물건) --> [그녀.].  동사. --> [좋아요].

이 문법은 "그는 그녀를 좋아한다", "그는 그를 좋아한다"와 같은 문장은 허용하지만 "그녀는 그를 좋아한다", "그는 그를 좋아한다"는 문장은 허용하지 않습니다.

DCG를 사용한 해석

이 문법의 해석 트리의 예를 나타냅니다.

DCG의 주요 실용적인 용도는 주어진 문법의 문장을 해석하는 것이다. 즉, 해석 트리를 구성하는 것이다.이것은, 다음의 룰과 같이, DCG내의 펑터에 「추가 인수」를 제공하는 것으로 실시할 수 있습니다.

 문장.(s(NP,부사장)) --> 명사_어구(NP), verb_phrase(부사장).  명사_어구(np(D,N)) --> 멈추다(D), 명사(N).  verb_phrase(VP(V,NP)) --> 동사.(V), 명사_어구(NP).  멈추다(d(그)) --> [그].  멈추다(d(a)) --> [a].  명사(n(박쥐)) --> [박쥐].  명사(n(고양이)) --> [고양이].  동사.(v(먹다)) --> [먹다].

이제 인터프리터에 문의하여 주어진 문장의 해석 트리를 생성할 수 있습니다.

   ?- 문장.(해석_트리, [그,박쥐,먹다,a,고양이], []).  해석_트리 = s(np(d(그),n(박쥐)),VP(v(먹다),np(d(a),n(고양이)))) ? ;

기타 용도

DCG는 구문 분석 응용 프로그램 외에도 코드의 특정 매개 변수를 숨기는 편리한 구문 설탕 역할을 할 수 있습니다.선언적으로 순수한 프로그래밍 언어에서 수성 I/O는 다음 쌍으로 표현되어야 합니다.io.state논쟁들.일반적으로 상태 변수 표기법이 [citation needed]선호되지만 DCG 표기법을 사용하면 I/O를 [10]보다 편리하게 사용할 수 있습니다.DCG 표기법은 Prolog에서와 마찬가지로 수성의 해석 및 유사에도 사용됩니다.

내선번호

DCG가 Pereira와 Warren에 의해 도입된 이후, 몇 가지 확장이 제안되었습니다.페레이라 자신은 추정 문법(XGs)[11]이라고 불리는 확장을 제안했다.이 형식주의는 부분적으로 왼쪽 첨부와 같은 특정한 문법적 현상을 더 쉽게 표현하기 위해 의도되었다.페레이라는 "XG 규칙과 DCG 규칙의 차이점은 XG 규칙의 왼쪽이 여러 개의 기호를 포함할 수 있다는 것입니다."라고 말한다.이를 통해 상황에 맞는 문법에 대한 규칙을 쉽게 표현할 수 있습니다.

Peter Van Roy는 DCG를 확장하여 여러 [12][13]축전기를 사용할 수 있도록 했습니다.

또 다른, 보다 최근, NEC Corporation의 연구원들은 1995년에 MM-DCGs라고 불리는 Multi-Modal Recordinate Clause Grammars (Multi-Modal Clause Grammars)확장자는 그림 [14]등 텍스트 이외의 부분을 포함하는 인식 및 구문 분석을 가능하게 하기 위한 것입니다.

DCTGs라고 불리는 또 다른 확장은 1984년 [15]Harvey Abramson에 의해 설명되었다.DCTG 표기법은 DCG 표기법과 매우 유사합니다.주요 차이점은,::=대신-->규칙에 따라.그것은 문법적 속성을 [16]편리하게 다루기 위해 고안되었다.DCTG에서 일반 Prolog 구로의 변환은 DCG와 비슷하지만 2가 아닌 3개의 인수가 추가됩니다.

「 」를 참조해 주세요.

메모들

  1. ^ Johnson, M. (1994). "Two ways of formalizing grammars". Linguistics and Philosophy. 17 (3): 221–240. doi:10.1007/BF00985036. S2CID 62165766.
  2. ^ Kowalski, R. A. "The early years of logic programming" (PDF). {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)
  3. ^ Colmerauer, A. (1978). "Metamorphosis grammars". Natural Language Communication with Computers. Lecture Notes in Computer Science. 63: 133–189. doi:10.1007/BFb0031371. ISBN 3-540-08911-X.
  4. ^ Pereira, F.; D. Warren (1980). "Definite clause grammars for language analysis" (PDF). {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)
  5. ^ Pereira, F. C. N.; D. H. D. Warren (1983). "Parsing as deduction" (PDF). Proceedings of the 21st annual meeting on Association for Computational Linguistics. Association for Computational Linguistics Morristown, NJ, USA. pp. 137–144.
  6. ^ Pereira, F. C. N.; S. M. Shieber (2002). Prolog and natural-language analysis. Microtome Publishing. ISBN 9780971977709.
  7. ^ Fleck, Arthur. "Definite Clause Grammar Translation". Retrieved 2009-04-16.
  8. ^ Fisher, J. R. "Prolog Tutorial -- 7.1". Retrieved 2016-05-17.
  9. ^ "DCGs give us a Natural Notation for Features". Retrieved 2009-04-21.
  10. ^ "Prolog to Mercury Transition Guide: Input/Output". Retrieved 2015-03-26.
  11. ^ Pereira, F. (1981). "Extraposition grammars" (PDF). Computational Linguistics. 7 (4): 243–256.
  12. ^ Van Roy, Peter (1990). "Extended DCG Notation: A Tool for Applicative Programming in Prolog". UCB Technical Report. 90 (583).
  13. ^ 소스 코드는 [1]에서 구할 수 있습니다.
  14. ^ Shimazu, H.; Y. Takashima (1995). "Multimodal definite clause grammar" (PDF). Systems and Computers in Japan. 26 (3): 93–102. doi:10.1002/scj.4690260309. S2CID 8199913.
  15. ^ Abramson, H. (1984). "Definite clause translation grammars". {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)
  16. ^ Sperberg-McQueen, C. M. "A brief introduction to definite clause grammars and definite clause translation grammars". Retrieved 2009-04-21.

외부 링크

Wikibook Prolog에는 다음과 같은 토픽의 페이지가 있습니다.