적응 문법

Adaptive grammar

적응형 문법은 형식주의 내에서 그 자체의 생산 규칙을 조작할 수 있도록 명시적으로 메커니즘을 제공하는 형식 문법이다.

개요

John N. Shutt는 적응 문법을 규칙 집합(일명 생산 규칙 집합)을 문법 내에서 명시적으로 조작할 수 있는 문법적 형식주의로 정의한다.조작 유형에는 규칙 추가, 삭제 및 [1]수정이 포함됩니다.

초기 역사

문헌에서 문법 적응성에 대한 최초의 설명은 일반적으로 1963년에 [5]발표된 Alfonso Caracciolo di Forino의 논문에서 인용된다[2][3][4].다음으로 일반적으로 받아들여진 적응형 형식주의(확장 가능한 문맥 자유 문법)에 대한 언급은 1970년 확장[6] 가능한 프로그래밍 언어의 연구에서 Wegbreit에서 왔고,[7] 1973년 핸포드와 존스의 동적 구문이 뒤따랐다.

공동 작업

꽤 최근까지 적응 문법의 형식적 특성에 대한 연구의 대부분은 연구자들 간에 조율되지 않았으며, 1990년[2] 보리스 버쉬테인의 [8]ACM SIGPLAN Notice에 실린 논문에 대한 반응으로 Henning Christiansen에 의해 처음으로 요약되었다.상파울루 대학의 공학부에는 적응형 언어 및 기술 연구소가 있으며, 특히 적응형 기술과 이론의 연구와 실천에 초점을 맞추고 있습니다.LTA는 또한 [9]해당 분야의 페이지 이름 지정 연구원을 유지합니다.

용어와 분류법

초기의 노력이 동적[7] 구문과 확장,[6] 수정,[10] 동적 [11]및 적응[2][12] 가능한 문법을 참조했지만, 보다 최근의 사용은 적응형([3]또는 문헌의 출판 언어에 따라 적응형)[13][14]이라는 용어를 사용하는 경향이 있다.이와이는 그녀의 형식주의를 적응 문법이라고 [13]부르지만, 이러한 단순 적응 문법의 구체적인 사용은 현재 문학에서 이름 조건 없이 일반적으로 사용되지 않는다.또한 여러 연구자 간에 표준화 또는 분류 작업이 수행되지 않았지만, 일부 연구자는 이러한 [3][4]방향으로 노력을 기울였다.

Shutt 분류(및 확장)

Shutt는 적응형 문법 모델을 두 가지 주요 [3][15]범주로 분류합니다.

  • 명령적 적응 문법은 언어의 생성에 따라 변화하는 글로벌 상태에 따라 규칙을 변화시킵니다.
  • 선언적 적응 문법은 언어 생성 공간(즉, 생성된 문자열의 구문 트리에서 위치)에 걸쳐만 규칙을 변화시킵니다.

Jackson은 Shutt의 분류법을 수정하여 시간 경과에 따른 변화를 전역으로, 공간 경과에 따른 변화를 로컬로 언급하고 하이브리드 시공간 [4]범주를 추가합니다.

  • 시공간 적응 문법(하이브리드)은 언어 생성의 시간 또는 공간(또는 둘 다)에 따라 규칙이 달라집니다(그리고 로컬 및 글로벌 연산은 이러한 변경에 대한 표기법에 따라 명시적으로 구분됩니다).

문헌의 적응적 형식주의

적응형 형식주의는 두 가지 주요 범주로 나눌 수 있다: 완전한 문법 형식주의와 적응형 기계로, 일부 문법 형식주의가 기초가 되었다.

적응문법형식

다음은 위의 Shutt의 정의에 의해 적응 문법으로 간주되거나 그들 자신의 발명가들에 의해 분류된 문법 형식들의 목록입니다.그것들은 문헌에 처음 언급된 역사적 순서로 나열되어 있다.

확장 가능한 컨텍스트 프리 문법(Wegbreit)

1970년 [6]Wegbreit의 박사학위 논문에 기술된 확장 가능한 문맥 자유 문법은 맨 왼쪽 유도 중 단자 접두사를 읽을 때 유한 상태 변환기에 의해 출력되는 명령에 따라 규칙 집합을 수정하는 문맥 자유 문법으로 구성됩니다.따라서 생성된 문자열의 위치에 따라 규칙 집합이 달라지지만 구문 트리의 계층 구조는 무시됩니다.확장 가능한 문맥 자유 문법은 Shutt에 의해 필수 [3]문법으로 분류되었다.

Christiansen 문법(Christiansen)

1985년에 생성 문법(Generative[16] Grammars)으로 처음 소개되었고 나중에 [17]더 자세히 설명되는 Christiansen grammars는 속성 문법의 적응적인 확장이다.Christiansen 문법들은 Shutt에 의해 [3]선언적인 것으로 분류되었다.

언어 L { a }({ L=\{{ a letter는 다음과 [17]같이 표시됩니다.

<프로그램↓>G> → <dcl↓G↑w> <body↓{w-rule}>
여기서 w-rule = <body↓G'> → w
<dcl↓G↑ch•w> → <char↓G↑ch> <dcl↓G↑w> <dcl↓G↑ <> → <car↓G↑a> → a

상향식 수정 가능 문법, 하향식 수정 가능 문법 및 USSA(Burshteyn)

1990년 5월에[8] 처음 도입되어 1990년 [10]12월에 확대된 수정 가능한 문법은 구문 분석 중에 규칙을 추가하고 삭제하는 메커니즘을 명시적으로 제공합니다.ACM SIGPLAN Notice의 응답에 대응하여 Burshteyn은 나중에 형식주의를 수정하고 1992년에 [18]적응형 Universal Syntax and Symantics Analyzer(USSA)를 도입했습니다.이러한 형식주의는 Shutt에 의해 [3]필수사항으로 분류되었다.

재귀적응문법(Shutt)

1993년에 도입된 재귀적응문법(RAGs)은 문맥이 없는 [3]문법의 우아함을 많이 유지하는 튜링의 강력한 형식주의를 도입하려는 시도였다.Shutt는 RAG를 선언적 형식주의로 자기 분류합니다.

동적 문법(Boullier)

1994년에 [11]도입된 Boullier의 동적 문법은 문법 형식주의 [4]표기법의 일부로서 해석의 시간 연속체 개념을 엄격하게 도입한 최초의 적응 문법 계열로 보인다.동적 문법은 문법의 연속이며, 각 문법i G는 시간이 지남에 따라 수열의 다른 문법과 어떤 면에서 다르다.Boullier의 동적 문법에 대한 주요 논문은 또한 이러한 문법에 대한 파싱을 하는 기계인 동적 파서를 정의하며, 그의 형식주의가 어떻게 형식 검사, 확장 가능한 언어, 다형성 및 프로그래밍 언어 번역의 의미 영역에 있는 것으로 여겨지는 다른 구성들과 같은 것들을 처리할 수 있는 예를 보여준다.동작.

적응 문법(이와이)

2000년[13] 이와이의 작업은 상황에 맞는 문법에 적응형 오토마타를 적용함으로써 Neto의[19] 적응형 오토마타를 더욱 발전시켰다.Iwai의 적응형 문법(이름으로 한정자 표시)은 해석 시 ?쿼리(통사적 술어와 유사하지만 수정이 선택되는 규칙 검사와 관련됨), + 추가 및 - 삭제(이전 적응형 오토마타와 공유됨)의 3가지 연산을 허용합니다.

γ-calculus (잭슨)

2000년에[20] 도입되어 [4]2006년에 가장 상세하게 논의된 "-Calculus"(여기에서는 메타에스로 발음됨)는 구문 술어를 제공할 뿐만 아니라 문법 내에서 생산의 명시적 추가, 삭제 및 수정을 가능하게 합니다.이 형식주의는 창조자에 의해 명령과 적응, 또는 더 구체적으로 시공간 적응 문법 형식주의로 자기 분류되고, 다른 사람들에 의해 분석적 형식주의로 [14][21]더욱 분류되었다.

L { + { L = \ { \ { a , b \}^{ + }\ } 의 이중 는 다음과 같습니다.

문법 ww { S : : = #phi ( A . X < - - )R ; R : : : = $C ( ' [ ab ] ) #phi ( A . X < - A . X C ) #phi ( N < = A )X) NR; };

(표기에 관한 주의:위의 예에서는#phi(...)문장은 문법을 명시적으로 수정하는 프로덕션 R의 포인트를 식별합니다. #phi(A.X<-A.X C)(시간 경과에 따른) 글로벌한 변경을 나타내고 있습니다.#phi(N<=A.X)statement는 로컬 변경(공간 초과)을 나타냅니다.그#phi(A.X<-"")S 프로덕션의 스테이트먼트는 빈 문자열을 R에 의해 참조되기 전에 해당 프로덕션으로 배치함으로써 A.X라는 글로벌 프로덕션을 효과적으로 선언합니다).

적응형 디바이스(Neto 및 Pistori)

2001년 [22]Neto에 의해 처음 기술된 적응형 장치는 나중에 [23]Pistori에 의해 2003년에 강화되고 확장되었습니다.

어댑터(Carmi

2002년에 [24]Adam Carmi는 Adapser로 알려진 LALR (1) 기반의 적응 문법 형식을 도입했습니다.형식주의의 구체적인 내용은 공개되지 않은 것으로 보인다.

어피아런스 체크 기능이 있는 적응형 CFG(Bravo)

2004년에 [14]César Bravo는 외관 검사[25] 개념을 이와이의 적응 문법의 제한된 [13]형태인 적응 문맥 없는 문법과 결합하는 개념을 도입하여 외관 검사 기능이 있는 적응 CFG라고 불리는 이러한 새로운 문법을 보여 주었다.

적응형 기계 형식

아래에 열거된 형식주의는 문법적 형식주의는 아니지만 완전한 문법적 형식주의의 기초가 되거나 본질적으로 적응성이 있기 때문에 여기에 포함된다.그것들은 문헌에 처음 언급된 역사적 순서로 나열되어 있다.

자기변경 유한상태 오토마타(Shutt & Rubinstein)
Shutt와 Rubinstein에 [26]의해 1994년에 소개된 자기수정 유한상태 오토마타(SMFA)는 제한된 형태로 튜링 파워가 있는 것으로 나타났다.
적응형 오토마타(Neto)
1994년 [19]Neto는 이와이,[13] 피스토리,[23] 브라보[14] 등이 추구하는 적응형 오토마타 이론의 핵심인 구조화 푸쉬다운 오토마톤이라고 불리는 기계를 선보였다.이 형식주의는 검사(이와이의 적응 문법과 관련하여 위에서 언급한 구문 술어와 유사), 규칙 추가 및 삭제를 허용합니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ Shutt, John N. "What is an Adaptive Grammar?". Retrieved 6 February 2019.
  2. ^ a b c Christiansen, Henning, "적용 가능한 문법의 조사", ACM SIGPLAN Notices, Vol.25 No. 11, p. 35-44, 1990년 11월.
  3. ^ a b c d e f g h Shutt, John N., Worcester Polytechnical Institute, Recursive Adaptive Grammars, 석사논문, 1993. (2003년 12월 16일 개정)
  4. ^ a b c d e Jackson, Quinn Tyler, Adapting to Babel: Adaptivity and Context-Sensitivity in Parsing, Ibis Publis, 매사추세츠 플리머스, 2006년 3월
  5. ^ Caracciolo di Forino, Alfonso, "심볼 프로그래밍 언어의 구문에 관한 몇 가지 발언", ACM의 통신, Vol.6, No.8, 페이지 456-460, 1963년 8월.
  6. ^ a b c Wegbreit, Ben, 확장 가능한 프로그래밍[dead link] 언어 연구, ESD-TR-70-297, 하버드 대학교, 매사추세츠주 캠브리지, 1970년 5월책 형태로, 1980년, 뉴욕, 갈랜드 출판사.
  7. ^ a b Hanford, K.V. & Jones, C.B, "A Concept for the Definition of Programming Language", Automatic Programming 7, Pergamon Press, Oxford, 페이지 115-142, 1973.
  8. ^ a b 버쉬테인, 보리스ACM SIGPLAN 통지, 제25권 제5호, 페이지 117-123, 1990년 5월.
  9. ^ http://www.pcs.usp.br/~lta/union/index.cp=4&cpia=28[데드링크]
  10. ^ a b Burshteyn, Boris, "수정 가능한 문법에 의한 형식 언어의 생성과 인식", ACM SIGPLAN 통지, Vol.25 No. 12, 페이지 45-53, 1990년 12월.
  11. ^ a b Boullier, Pierre, "Dynamic Grammars and Semantic Analysis," INRIA 연구 보고서 No. 2322, 1994년 8월.
  12. ^ John Shutt는 원래 Recursive Adaptive Grammars라는 이름으로 그의 Recursive Adaptive Grammars라고 불렀고, 다음 URL에서 적응에 대한 그의 변화를 주목했습니다: John Shutt의 MS 논문.
  13. ^ a b c d e 이와이, Margarete Keiko, Um formalismo gramativo para languageagens de contexto, 브라질 상파울루 대학 공학부 박사 논문, 2000년 1월.
  14. ^ a b c d Bravo, César, Grammaticas Livres de Contexto Adaptativas com verificassao de aparencia, 박사 논문, 상파울루 대학교 전기공학부, 2004년 1월
  15. ^ Shutt, John N. 2001년 3월 28일자 "Imperative Adaptive Grammars" 웹 페이지 http://web.cs.wpi.edu/ ~jshutt/adapt/Imperative.http:/http://web.cs.wpi.edu/
  16. ^ Christiansen, Henning, "강력한 추상화 메커니즘을 가진 프로그래밍 언어를 위한 구문, 의미론 및 구현 전략", 제18회 하와이 국제 시스템 과학 컨퍼런스 제2권, 57-66, 1985년.
  17. ^ a b Christiansen, Henning, "확장 가능한 언어의 구문과 의미론", Datalogiske Scriftter 14, Roskilde University, 1988.
  18. ^ Burshteyn, Boris, "USSA – Universal Syntax and Symantics Analyzer", ACM SIGPLAN Notice, Vol. 27 No. 1, 페이지 42-60, 1992년 1월.
  19. ^ a b Neto, Joang Jose, "문맥에 맞는 언어를 위한 적응형 오토마타", ACM SIGPLAN 통지, 제29권 제9호, 페이지 115-124, 1994년 9월.
  20. ^ 잭슨, 퀸 타일러, "자연어 해석에서의 적응적 술어", 완벽, 제1권 제4호, 2000년 4월.
  21. ^ Okhotin, Alexander, Boolean Grammars: Expressive Power and Algorithms, 박사학위 논문, 퀸스 대학교, 온타리오 킹스턴, 2004년 8월
  22. ^ Neto, Joang Jose, "어댑티브 규칙 기반 디바이스: 일반적인 처방과 도입 사례[permanent dead link]" B. W. W. Watson, D.Wood (Eds) : 제6회 Automata 국제회의, CIAA 2001, 컴퓨터 사이언스 강의 노트, Vol. 2494, 프리토리아, 남아프리카공화국, 스프링거-벨락, 페이지 234-250, 2001년 7월 23-25.
  23. ^ a b Pistori, Hemerson, Tecnologia Adaptativa em Engenharia de Computassao: Estado da Arte e Aplicaeses, 상파울루 대학교 전기공학부 박사논문, 2003.
  24. ^ Carmi, Adam, "Adapser: An LALR (1) Adapser[permanent dead link]", 프로그래밍 언어 및 개발 환경에 관한 이스라엘 워크숍, 이스라엘 하이파, 2002년 7월 1일.
  25. ^ Salomaa, Arto, Formal Languages, Academic Press, 1973.
  26. ^ Shutt, John & Rubinstein, Roy, "Self-Modifying Finite Automata", B.퍼슨과 나.Simon, 편집자, 테크놀로지 및 재단: 정보처리 '94 Vol. I: 암스테르담에서 열린 제13회 IFIP 세계 컴퓨터 콩그레스(World Computer Congress)의 진행:노스홀랜드, 493-498페이지, 1994.(표준)