얼리 파서

Earley parser
얼리 파서
학급문맥이 없는 구문 분석
data 구조스트링
최악의 경우 성능
베스트 케이스 성능
평균 성능

컴퓨터 과학에서 얼리 파서는 주어진 문맥이 없는 언어에 속하는 문자열을 해석하는 알고리즘이지만 (변종에 따라) 특정 null 가능한 [1]문법에 문제가 있을 수 있습니다.개발자인 Jay Earley의 이름을 딴 이 알고리즘은 동적 프로그래밍을 사용하는 차트 파서입니다. 주로 컴퓨터 언어학에서 파싱에 사용됩니다.그것은 1968년 그의[2] 논문에 처음 소개되었다(나중에 더 읽기 쉽게 축약된 형태로 저널에[3] 실렸다).

Earley 파서는 컴파일러에서 일반적으로 사용되지만 제한된 클래스의 언어만 처리할 수 있는 LR 파서 및 LL 파서와 달리 모든 컨텍스트가 없는 언어를 구문 분석할 수 있기 때문에 매력적입니다.얼리 파서는 일반적인 O 3의경우 입방시간으로 됩니다.여기서 n은 분석된 문자열의 길이, 애매하지 않은 O경우 2차시간, 그리고 모든 결정론적 컨텍스트프리 문법의 선형시간입니다[4]규칙이 왼쪽 반복으로 작성될 때 특히 잘 작동합니다.

얼리 인식자

다음 알고리즘은 Earley 인식기를 설명합니다.인식자는 인식 시 해석 트리를 생성하도록 수정될 수 있으며, 이러한 방식으로 파서로 전환될 수 있습니다.

알고리즘

다음 설명에서 α, β 및 β는 단자/비단말 문자열(빈 문자열 포함), X 및 Y는 단일 비단말기, a는 단자 기호를 나타냅니다.

얼리의 알고리즘은 하향식 동적 프로그래밍 알고리즘입니다.아래에서는 얼리의 도트 표기법을 사용한다: X → αβ가 생성될 때 X → α • β는 α가 이미 해석되고 β가 예상되는 상태를 나타낸다.

입력 위치 0은 입력 전 위치입니다.입력 위치 n은 n번째 토큰을 받아들인 후의 위치입니다.(공식적으로 입력 위치는 토큰 경계에서의 위치라고 생각할 수 있습니다.)파서는 모든 입력 위치에 대해 상태 집합을 생성합니다.각 상태는 다음과 같이 구성된 태플(X → α • β, i)이다.

  • 현재 일치하고 있는 생산량(X → α β
  • 그 생산의 현재 위치(점으로 나타남)
  • 이 생산의 매칭이 시작된 입력의 위치 i: 원점 위치

(Earley의 원래 알고리즘에는 이 상태의 예측이 포함되어 있었습니다.나중의 조사에서는, 이것이 파싱 효율에 실질적으로 거의 영향을 주지 않는 것이 판명되어, 그 후 대부분의 실장으로부터 제외되었습니다).

입력 위치 k에서 설정된 상태를 S(k)라고 합니다.파서는 최상위 규칙만으로 구성된 S(0)로 시드됩니다.그런 다음 파서는 예측, 스캔 및 완료의 세 가지 작업을 반복합니다.

  • 예측:형태(X → α • Y β, j)(여기서 j는 위와 같은 원점 위치)의 S(k)의 모든 상태에 대해 Y가 왼쪽에 있는 문법의 모든 생성에 대해 S(k)에 (Y → • β, k)를 더한다.
  • 스캔: a가 입력 스트림의 다음 기호인 경우, (X → α • a β, j) 형태의 S(k) 내의 모든 상태에 대해 S(k+1)에 (X → α a • β, j)를 더한다.
  • 완료:형태의 S(k)에 있는 모든 상태에 대해(Y → α • Y β, i) 형태의 S(j)에 있는 모든 상태를 찾고 S(k)에 (X → α Y • β, i)를 더한다.

중복된 상태는 상태 세트에 추가되지 않고 새 상태만 추가됩니다.세트에 새로운 상태를 추가할 수 없을 때까지 이 세 가지 조작이 반복됩니다.이 세트는 일반적으로 처리하는 상태 큐로 구현되며, 어떤 상태인지에 따라 동작이 수행됩니다.

알고리즘은 (X → • •, 0)이 S(n)로 끝나는 경우 수락합니다. 여기서 (X → ))는 최상위 규칙이고 n 입력 길이입니다. 그렇지 않으면 거부됩니다.

유사 코드

Daniel Jurafsky와 James H. Martin에 의해 음성 및 언어 처리에서[5] 개작된

선언하다 어레이 S;  기능. 초기화(단어)     S ← CREATE_ARREY(길이(단어) + 1)     위해서 k ← 부터 0 로. 길이(단어) 하다         S[k] ← 빈_주문필_세트  기능. 얼리_파스(단어, 문법.)     초기화(단어)     ADD_TO_SET((γ → •S, 0), S[0])     위해서 k ← 부터 0 로. 길이(단어) 하다         위해서 각각 주 에 S[k] 하다  // 이 루프 중에 S[k]를 확장할 수 있습니다.             한다면 것은 아니다. 끝났습니다(주) 그리고나서                 한다면 다음_Element_OF(주) 이 a 단말기가 아니다 그리고나서                     예측 변수(주, k, 문법.)         // 터미널 이외                 또 다른 하다                     스캐너(주, k, 단어)             // 단말기             또 다른 하다                 완료하다(주, k)         끝.     끝.     돌아가다 도표  절차. 예측 변수((A → α•Bβ, j), k, 문법.)     위해서 각각 (B → γ) 에 문법_규칙_포(B, 문법.) 하다         ADD_TO_SET((B → •외부여, k), S[k])     끝.  절차. 스캐너((A → α•aβ, j), k, 단어)     한다면 a ⊂ 부품_OF_Speech(단어[k]) 그리고나서         ADD_TO_SET((A → αa•β, j), S[k+1])     끝.  절차. 완료하다((B → §, x), k)     위해서 각각 (A → α•Bβ, j) 에서 S[x] 니         ADD_TO_SET((A → αB•β, j), S[k])     끝.

예

:산수 표현에 대해 다음과 같은 간단한 문법을 고려해 보세요.

<>P>.::=<>S>.#의 시작 규칙<>.S>.::=<>S>,"+"<>M>,<>M>,<>M>.::=<>M>,"*"<>T><>T><>T>::)"2""3""4""1".

그 입력:

2 + 3 * 4

상태 집합의 이 시퀀스:.

(상태 번호) 생산. (기원) 댓글
S(0):• 2+3*4
1 P→ • S 0 규칙을 시작하
2 S→ • S+M 0 (1)부터 예측하다
3 S → • M 0 (1)부터 예측하다
4 M → • M * T 0 (3)부터 예측하다
5 M → • T 0 (3)부터 예측하다
6 T → • 수 0 (5)부터 예측하다
S(1): 2 • + 3 * 4
1 T → 번호 • 0 S(0)(6)에서 스캔
2 M → T • 0 (1) 및 S(0)(5)부터 완료
3 M → M • * T 0 (2) 및 S(0)(4)부터 완료
4 S → M • 0 (2) 및 S(0)(3)부터 완료
5 S → S • + M 0 (4) 및 S(0)(2)부터 완료
6 P → S • 0 (4) 및 S(0)(1)부터 완료
S(2): 2 + • 3 * 4
1 S → S + • M 0 S(1)(5)로부터의 스캔
2 M → • M * T 2 (1)부터 예측하다
3 M → • T 2 (1)부터 예측하다
4 T → • 수 2 (3)부터 예측하다
S(3): 2 + 3 • * 4
1 T → 번호 • 2 S(2)(4)에서 스캔
2 M → T • 2 (1) 및 S(2)(3)부터 완료
3 M → M • * T 2 (2) 및 S(2)(2)부터 완료
4 S → S + M • 0 (2) 및 S(2)(1)부터 완료
5 S → S • + M 0 (4) 및 S(0)(2)부터 완료
6 P → S • 0 (4) 및 S(0)(1)부터 완료
S(4): 2 + 3 * • 4
1 M → M * • T 2 S(3)(3)에서 스캔
2 T → • 수 4 (1)부터 예측하다
S(5): 2 + 3 * 4 •
1 T → 번호 • 4 S(4)(2)로부터의 스캔
2 M → M * T • 2 (1) 및 S(4)(1)부터 완료
3 M → M • * T 2 (2) 및 S(2)(2)부터 완료
4 S → S + M • 0 (2) 및 S(2)(1)부터 완료
5 S → S • + M 0 (4) 및 S(0)(2)부터 완료
6 P → S • 0 (4) 및 S(0)(1)부터 완료

상태(P → S •, 0)는 완료된 해석을 나타냅니다.이 상태는 완전한 문장인 S(3)와 S(1)에도 나타난다.

구문 분석 포레스트 구성

Earley의[6] 논문은 Earley 항목의 각 비단말기에서 포인터 세트를 다시 인식하게 한 항목에 추가하여 해석 트리를 구성하는 알고리즘을 간략하게 설명합니다.그러나 Tomita는[7] 이것이 기호 간의 관계를 고려하지 않는다는 것을 알아차렸다. 따라서 문법 S → SS b와 문자열 bbb를 고려할 때, 각 S가 하나 또는 두 개의 bb와 일치할 수 있다는 것을 알 수 있으며, 따라서 bb와 bbb에 대한 두 개의 올바른 파생이 생성된다.

또 하나의 방법은[8] 진행하면서 해석 포레스트를 구축하는 것입니다.각 Earley 항목에 3중(s, i, j) 라벨이 붙은 공유 패킹 해석 포레스트(SPPF) 노드에 대한 포인터를 추가하는 것입니다.여기서 s는 기호 또는 LR(0) 항목(도트가 있는 생산 규칙)이며 i와 j는 이 노드에서 파생된 입력 문자열의 섹션을 제공합니다.노드의 내용은 단일 파생물을 제공하는 한 쌍의 하위 포인터 또는 각각 한 쌍의 포인터를 포함하고 하나의 파생물을 나타내는 "패킹된" 노드의 목록입니다.SPPF 노드는 고유하지만(특정 라벨이 있는 노드는 하나뿐이지만), 모호한 파스에 대한 파생 노드가 두 개 이상 포함될 수 있습니다.따라서 작업이 Earley 항목을 추가하지 않더라도(이미 존재하기 때문에), 여전히 항목의 구문 분석 포리스트에 파생 항목을 추가할 수 있습니다.

  • 예측 항목에 null SPPF 포인터가 있습니다.
  • 스캐너는 스캔 중인 터미널이 아닌 SPPF 노드를 생성합니다.
  • 그런 다음 스캐너 또는 Completer가 항목을 전진시킬 때 점이 전진된 항목에서 노드가 자식인 파생 프로그램과 전진된 새 기호(비단말 또는 완료 항목)를 추가합니다.

SPPF 노드는 완성된 LR(0) 항목으로 라벨링되지 않습니다. 대신, 생산되는 기호로 라벨링되어 어떤 대체 생산에서 파생되는지에 관계없이 모든 파생물이 하나의 노드 아래에 결합됩니다.

최적화

Philippe McL.Nigel Horspool은 논문 "A Faster Earley Parser"에서 Earley 파싱과 LR 파싱을 결합하여 규모순으로 개선했습니다.

「 」를 참조해 주세요.

인용문

  1. ^ Kegler, Jeffrey. "What is the Marpa algorithm?". Retrieved 20 August 2013.
  2. ^ Earley, Jay (1968). An Efficient Context-Free Parsing Algorithm (PDF). Carnegie-Mellon Dissertation.
  3. ^ Earley, Jay (1970), "An efficient context-free parsing algorithm" (PDF), Communications of the ACM, 13 (2): 94–102, doi:10.1145/362007.362035, S2CID 47032707, archived from the original (PDF) on 2004-07-08
  4. ^ John E. Hopcroft and Jeffrey D. Ullman (1979). Introduction to Automata Theory, Languages, and Computation. Reading/MA: Addison-Wesley. ISBN 978-0-201-02988-8. 페이지 표시
  5. ^ Jurafsky, D. (2009). Speech and Language Processing: An Introduction to Natural Language Processing, Computational Linguistics, and Speech Recognition. Pearson Prentice Hall. ISBN 9780131873216.
  6. ^ Earley, Jay (1968). An Efficient Context-Free Parsing Algorithm (PDF). Carnegie-Mellon Dissertation. p. 106.
  7. ^ Tomita, Masaru (April 17, 2013). Efficient Parsing for Natural Language: A Fast Algorithm for Practical Systems. Springer Science and Business Media. p. 74. ISBN 978-1475718850. Retrieved 16 September 2015.
  8. ^ Scott, Elizabeth (April 1, 2008). "SPPF-Style Parsing From Earley Recognizers". Electronic Notes in Theoretical Computer Science. 203 (2): 53–67. doi:10.1016/j.entcs.2008.03.044.

기타 참고 자료

실장

C, C++

하스켈

자바

  • [1] – 얼리 알고리즘의 Java 구현
  • PEN – 얼리 알고리즘을 구현하는 Java 라이브러리
  • Pep – Earley 알고리즘을 구현하여 차트 및 해석 트리를 해석 아티팩트로 제공하는 Java 라이브러리
  • digitalheir/java-probabilic-early-parser - 확률론적 얼리 알고리즘을 구현하는 Java 라이브러리. 애매한 문장에서 가장 가능성이 높은 해석 트리를 결정하는 데 유용하다.

C#

  • coonsta/earley - C#의 얼리 파서
  • patrickhuber/pliant - Marpa가 채택한 개선사항을 통합하여 엘리자베스 스콧의 트리 구축 알고리즘을 보여주는 얼리 파서입니다.
  • elisonch/CFGLib - C#용 확률론적 컨텍스트 자유 문법(PCFG) 라이브러리(Earley + SPPF, CYK)

자바스크립트

OCaml

  • Simple Earley - 간단한 Earley 유사 구문 분석 알고리즘 구현(문서 포함).

펄

  • Marpa::R2:Perl 모듈Marpa는 Joop Leo와 Aycock과 Horspool이 개선한 Earley 알고리즘입니다.
  • 해석:: Earley – Jay Earley의 원래 알고리즘을 구현하는 Perl 모듈

파이썬

  • Lark – SPPF를 출력하는 Earley 파서의 객체 지향적 절차적 구현입니다.
  • NLTK – Earley 파서를 갖춘 Python 툴킷
  • Spark – Earley 파서를 구현하는 Python용 객체 지향 작은 언어 프레임워크
  • spark_parser – Python 3 및 Python 2에서 실행되는 위의 Spark 파서의 업데이트 및 패키지 버전
  • 얼리3py – 150줄 미만의 코드로 알고리즘의 독립형 구현(파싱 및 샘플 생성 포함)
  • tjr_python_earley_parser - Python의 최소 얼리 파서
  • Earley Parsing - Python의 Earley 파서 튜토리얼에 엡실론 핸들링과 오른쪽 재귀에 대한 Leo 최적화 기능이 포함되어 있습니다.

녹

  • Santiago – 얼리 파서를 구현하는 Rust용 렉싱 및 해석 툴킷.

일반적인 리스프

  • CL-Earley-parser – Earley 파서를 구현하는 공통 리스프 라이브러리

스킴, 라켓

울프람

자원.