GLR 파서

GLR parser

GLR 파서(GLR은 "일반화된 LR"을 의미하며, 여기서 L은 "좌우"를 의미하고 R은 "가장 오른쪽(분열)"을 의미하며, LR 파서 알고리즘을 확장하여 결정적이지 않고 모호한 문법을 처리한다.[1]이론적 기초는 (GLL과 같은 다른 일반 컨텍스트 프리 파서들과 함께) 베르나르 랭이 1974년에 발표한[2] 논문에서 제공되었다.그러한 알고리즘을 만드는 체계적인 방법을 설명하고, 정확성 입증에 관한 통일된 결과, 문법 수업에 관한 복잡성, 최적화 기법을 제공한다.GLR의 첫 번째 실제 구현은 토미타 마사루(Tomita)가 1984년 논문에서 기술한 것으로, 「병렬 파서(parallel parser)」라고도 한다.토미타는 본작에서 5단계를 제시했지만, 실제로는 GLR 파서로 인정받는 두 번째 단계다.[3]

알고리즘은 원래 형태부터 진화했지만 원리는 그대로 유지됐다.이전 출판물에서 보듯이,[4] 랭은 주로 확장 가능한 프로그래밍 언어에 더 쉽게 사용되고 더 유연한 파서들에 관심이 있었다.토미타의 목표는 자연어 텍스트를 철저하고 효율적으로 파싱하는 것이었다.표준 LR 파서들은 자연 언어의 비결정적이고 모호한 성질을 수용할 수 없으며, GLR 알고리즘은 이를 수용할 수 있다.

알고리즘.

간단히 말해서, GLR 알고리즘은 LR 파서 알고리즘과 유사한 방식으로 작동한다. 단, 특정 문법을 주어진 GLR 파서는 넓은 첫 번째 검색에서 주어진 입력의 모든 가능한 해석을 처리한다.전면에서 GLR 파서 생성기는 입력 문법을 파서 테이블로 변환하며, LR 생성기와 유사한 방식으로 변환한다.그러나 LR 구문 분석 테이블이 하나의 상태 전환만 허용하는 경우(상태 및 입력 토큰이 주어진 경우), GLR 구문 분석 테이블은 다중 전환을 허용한다.사실상 GLR은 교대/축소를 허용하고 충돌을 감소/축소한다.

상충되는 전환이 발생하면 파스 스택을 두 개 이상의 병렬 파스 스택으로 포칭하며, 가능한 전환 각각에 해당하는 상태가 맨 위에 있다.그런 다음, 다음 입력 토큰을 읽고 각 "상위" 상태에 대한 다음 전환을 결정하는 데 사용되며, 추가 포킹이 발생할 수 있다.지정된 상위 상태 및 입력 토큰이 적어도 하나의 전환을 초래하지 않는 경우 구문 분석 테이블을 통과하는 "경로"는 유효하지 않으며 폐기될 수 있다.

GSS(Graph-structured stack)로 알려진 중요한 최적화는 이러한 스택의 공통 접두사 및 접미사를 공유할 수 있게 하여 입력 텍스트를 구문 분석하는 데 필요한 전체 검색 공간과 메모리 사용을 제한한다.이러한 개선으로 인해 발생하는 복잡한 구조는 검색 그래프를 트리가 아닌 방향의 아세클릭 그래프(다양한 노드의 "깊이"에 대한 추가 제한 포함)로 만든다.

이점

GLR 알고리즘을 사용한 인식은 CYK 알고리즘과 Earley 알고리즘: O(n3)와 동일한 최악의 시간 복잡성을 가진다.[citation needed]그러나 GLR에는 다음과 같은 두 가지 추가 장점이 있다.

  • 알고리즘을 실행하는 데 필요한 시간은 문법에서 비결정론적 수준에 비례한다: 결정론적 문법에서 GLR 알고리즘은 O(n) 시간에 실행된다(이는 Earley와[citation needed] CYK 알고리즘에는 해당되지 않지만, 원래 Earley 알고리즘은 이를 보장하기 위해 수정할 수 있다).
  • GLR 알고리즘은 "온라인"이다. 즉, 입력 토큰을 특정 순서로 소비하고 각 토큰을 소비한 후 가능한 많은 작업을 수행한다(Earley에게도 해당).

실제로 대부분의 프로그래밍 언어의 문법은 결정론적 또는 "거의 결정론적"이며, 이는 비결정론은 대개 적은 수의 토큰[citation needed](한계되지 않을 수도 있지만) 내에서 해결된다는 것을 의미한다.Earley 또는 CYK와 같은 맥락 없는 그래머의 전체 클래스(예: Earley 또는 CYK)를 처리할 수 있는 다른 알고리즘에 비해 GLR 알고리즘은 대부분의 파싱 과정 동안 단 하나의 스택만이 활성화되기 때문에 이러한 "거의 결정론적" 그래머에서 더 나은 성능을 제공한다.

GLR은 하이브리드 파서로 LALR(1) 알고리즘과 결합하여 더 높은 성능을 제공할 수 있다.[5]

참고 항목

참조

  1. ^ Masaru Tomita (6 December 2012). Generalized LR Parsing. Springer Science & Business Media. ISBN 978-1-4615-4034-2.
  2. ^ Lang, Bernard (1974). Loeckx, J. (ed.). "Deterministic techniques for efficient non-deterministic parsers". Automata, Languages and Programming, 2nd Colloquium. Lecture Notes in Computer Science. Saarbrücken: Springer. 14: 255–269. doi:10.1007/3-540-06841-4_65. ISBN 978-3-540-06841-9. ISSN 0302-9743.
  3. ^ 토미타 마사루.자연어를 위한 효율적인 구문 분석.1986년 보스턴 클루워 학술 출판사
  4. ^ Lang, Bernard (December 1971). "Parallel non-deterministic bottom-up parsing". ACM SIGPLAN Notices. Proceedings of the international symposium on Extensible languages. 6 (12): 56–57. doi:10.1145/942582.807982.
  5. ^ "Elkhound, Elsa and Cqual++: Open-Source Static Analysis for C++". Archived from the original on 2021-12-21.

추가 읽기

  • Grune, Dick; Jacobs, Ceriel J.H. (2008). Parsing Techniques. Springer Science+Business Media. ISBN 978-0-387-20248-8.
  • Tomita, Masaru (1984). "LR parsers for natural languages". COLING. 10th International Conference on Computational Linguistics. pp. 354–357.
  • Tomita, Masaru (1985). "An efficient context-free parsing algorithm for natural languages". IJCAI. International Joint Conference on Artificial Intelligence. pp. 756–764.