파서 콤비네이터

Parser combinator

컴퓨터 프로그래밍에서 파서 콤비네이터는 여러 파서를 입력으로 받아들이고 새로운 파서를 출력물로 반환하는 고차 함수다.이 맥락에서 파서는 문자열을 입력으로 받아들이고 일부 구조를 출력(일반적으로 파싱이 성공적으로 중지된 문자열의 위치를 나타내는 파스 트리 또는 인덱스 집합)으로 반환하는 함수다.파서 콤비네이터는 모듈식 조각 구조와 시험을 용이하게 하는 재귀적 강하 파싱 전략을 가능하게 한다.이 파싱 기법은 콤비네이션 파싱이라고 불린다.

콤비네이터를 사용하는 파서들은 복잡하고 다양한 의미 작용이 구문 처리와 밀접하게 통합되는 데이터베이스에 대한 자연 언어 인터페이스와 같은 도메인 고유 언어에 대한 컴파일러와 프로세서의 시제품 제작에 광범위하게 사용되어 왔다.1989년 리처드 프로스트와 존 런치버리는 파서 콤비네이터를 사용하여 자연어 통역사를 건설하는 것을[1] 시연했다.Graham Hutton은 또한 1992년에 기본 구문 분석에서 고차원의 기능을 사용했다.[2]S. D. Swierstra는 또한 2001년에 파서 콤비네이터의 실용적인 면들을 전시했다.[3]2008년 프로스트, 하피즈, 캘러헌은[4] 하스켈의 파서 콤비네이터 세트를 설명했는데, 이 세트는 왼쪽 재귀 수용이라는 오랜 문제를 해결하고, 다항식 시공간에서 완전한 하향식 파싱 도구로 일한다.

기본 아이디어

퍼스트 클래스 기능이 있는 모든 프로그래밍 언어에서 파서 콤비네이터를 사용하여 기본 파서들을 조합하여 더 복잡한 규칙을 위한 파서들을 구성할 수 있다.예를 들어, 문맥 없는 문법(CFG)의 생산 규칙은 하나 이상의 대안이 있을 수 있으며 각 대안은 비단말 및/또는 단자의 순서로 구성되거나, 대안은 단일 비단말 또는 단자 또는 빈 문자열로 구성될 수 있다.각 대안에 대해 간단한 파서를 사용할 수 있는 경우 파서 결합기를 사용하여 이들 파서 각각을 결합할 수 있으며, 대안의 일부 또는 전부를 인식할 수 있는 새로운 파서를 반환할 수 있다.

연산자 과부하를 지원하는 언어에서 파서 콤비네이터는 다른 파서들을 접착시켜 완전한 규칙을 형성하는 데 사용되는 인픽스 연산자의 형태를 취할 수 있다.따라서 파서 결합자는 정형 문법의 규칙과 구조가 유사한 코드, 내장된 스타일로 파서를 정의할 수 있다.이와 같이, 구현은 모든 관련 장점을 가진 실행 가능한 규격으로 생각할 수 있다.(알 수 없음: 가독성)

콤비네이터

논의를 비교적 간단하게 하기 위해, 인식자 측면에서만 파서 결합자를 논한다.입력 문자열의 길이인 경우#input그리고 그 구성원은 색인을 통해 접속된다.j인식자는 파서가 성공적으로 위치에서 시작된 토큰의 시퀀스 인식을 완료한 위치를 나타내는 일련의 지수를 출력물로 반환하는 파서다.j. 빈 결과 집합은 인식자가 인덱스에서 시작하는 시퀀스를 인식하지 못했음을 나타낸다.j. 비어 있지 않은 결과 집합은 인식자가 다른 위치에서 성공적으로 종료됨을 나타낸다.

  • 그empty인식기는 빈 문자열을 인식한다.이 파서는 항상 성공하며 현재 위치가 포함된 싱글톤 세트를 반환한다.
  • 인식자term x단말기를 인식하다x. 토큰이 제자리에 있는 경우j입력 문자열에는x, 이 파서는 다음을 포함하는 싱글톤 세트를 반환한다.j + 1; 그렇지 않으면 빈 세트를 반환한다.

동일한 색인에서 마치는 동안 문자열을 구문 분석하는 여러 가지 뚜렷한 방법이 있을 수 있다는 점에 유의하십시오. 이것은 문법이 모호함을 나타낸다.단순 인식자는 이러한 모호성을 인정하지 않는다. 각 가능한 마감 지수는 결과 집합에 한 번만 나열된다.더 완전한 결과 집합을 위해서는 파스 트리와 같은 더 복잡한 물체를 반환해야 한다.

두 개의 기본 인식자의 정의에 따름p그리고q대체 및 시퀀싱에 대한 두 가지 주요 분석기 결합기를 정의할 수 있다.

  • '대체' 구문 분석기 콤비네이터 ⊕은 동일한 입력 위치에 두 인식자를 모두 적용한다.j그리고 두 인식자가 모두 반환한 결과를 요약하고, 최종 결과는 최종적으로 반환된다.사이사이에 인픽스 연산자로 사용된다.p그리고q아래와 같이
  • 인식자의 시퀀싱은 ⊛ 파서 콤비네이터로 한다.⊕과 마찬가지로 사이사이에 인픽스 연산자로 사용된다.p그리고q그러나 첫 번째 인식자를 적용한다.p입력 위치까지j, 그리고 이 어플리케이션의 성공적인 결과가 있다면, 두 번째 인식자는q첫 번째 인식자가 반환한 결과 집합의 모든 요소에 적용된다.⊛ 궁극적으로 q의 이러한 적용의 결합을 반환한다.

예

매우 모호한 문맥이 없는 문법을 고려해보자.s ::= ‘x’ s s ε. 앞에서 정의한 결합기를 사용하여, 우리는 이 문법의 실행 가능한 표기들을 현대 기능 언어(예: Haskell)로 모듈로 정의할 수 있다.s = term ‘x’ <*> s <*> s <+> empty. 인식자일 때s입력 시퀀스에 적용됨xxxxx제자리에1, 위의 정의에 따라 결과 집합을 반환함{5,4,3,2}.

단점과 해결책

파서 콤비네이터는 모든 재귀적 강하 파서와 마찬가지로 컨텍스트 없는 그래머에 국한되지 않으므로 Firstk 및 Followk 세트를 구문 분석하는 LL(k)에서 모호성을 전역적으로 검색하지 않는다.따라서 모호성은 입력에 의해 촉발될 경우 런타임까지 알 수 없다.이러한 경우, 재귀적 강하 분석기는 가능한 모호한 경로 중 하나로 디폴트(아마도 문법 설계자에게 알려지지 않은)할 수 있으며, 언어 사용에서 의미적 혼란(별칭)을 초래할 수 있다.이는 컴파일 시간에 보고되지 않고 인간의 실수가 아니라 문법적으로 도입되는 애매한 프로그래밍 언어 사용자들에 의해 버그로 이어진다.이런 벌레들을 없애는 유일한 해결책은 모호함을 제거하고 문맥이 없는 문법을 사용하는 것이다.

파서 콤비네이터의 간단한 구현에는 몇 가지 단점이 있는데, 이는 하향식 파싱에서 흔히 볼 수 있다.모호한 문맥이 없는 문법을 구문 분석할 때는 기하급수적인 시간과 공간이 필요하다.1996년 프로스트와 시들로우스키는 시간 복잡성을 다항식으로 줄이기 위해 파서 콤비네이터와 함께 메모화가 어떻게 사용될 수 있는지를 시연했다.[5]후기 프로스트는 계산 내내 메모 테이블의 체계적이고 정확한 스레딩을 위해 결합기를 구성하기 위해 모노드를 사용했다.[6]

다른 하향식 재귀적 하강 파싱과 마찬가지로 기존의 파서 결합기(위에서 설명한 결합기)는 왼쪽-재귀적 문법(예:)을 처리하는 동안 종료되지 않는다.s ::= s <*> term ‘x’ empty). 왼쪽-복구 규칙의 모호한 문법을 수용하는 인식 알고리즘은 2006년 프로스트와 하피즈가 설명한다.[7]그 알고리즘은 깊이 제한을 가함으로써 그 외의 계속 증가하는 좌회귀 파스를 커트한다.이 알고리즘은 2007년 프로스트, 하피즈, 캘러헌이 만든 매우 모호한 문법에 대해 간접적인 것은 물론 직접적인 좌뇌 리큐르를 수용하고 잠재적으로 기하급수적으로 많은 수의 파스 트리를 수식할 수 있도록 완전한 파싱 알고리즘으로 확장되었다.[8]이 확장 알고리즘은 '계산된 컨텍스트'와 '현재 컨텍스트'를 비교하여 간접적인 좌측 재귀성을 수용한다.같은 저자들은 또한 같은 알고리즘에 기초하여 하스켈 프로그래밍 언어로 쓰여진 일련의 파서 콤비네이터의 구현에 대해서도 설명했다.[4][9]

메모들

  1. ^ 프로스트 & 런치베리 1989.
  2. ^ 허튼 1992.
  3. ^ 스위어스트라 2001.
  4. ^ a b 프로스트, 하피즈 & 캘러헌 2008.
  5. ^ 프로스트 & 시드로우스키 1996.
  6. ^ 프로스트 2003.
  7. ^ 프로스트 & 하피즈 2006.
  8. ^ 프로스트, 하피즈 & 캘러헌 2007.
  9. ^ cf. X-SAIGA — 그래머의 실행 가능한 사양

참조

  • Burge, William H. (1975). Recursive Programming Techniques. The Systems programming series. Addison-Wesley. ISBN 978-0201144505.
  • Frost, Richard; Launchbury, John (1989). "Constructing natural language interpreters in a lazy functional language" (PDF). The Computer Journal. Special edition on Lazy Functional Programming. 32 (2): 108–121. doi:10.1093/comjnl/32.2.108. Archived from the original on 2013-06-06.{{cite journal}}: CS1 maint : bot : 원본 URL 상태 미상(링크)
  • Frost, Richard A.; Szydlowski, Barbara (1996). "Memoizing Purely Functional Top-Down Backtracking Language Processors" (PDF). Sci. Comput. Program. 27 (3): 263–288. doi:10.1016/0167-6423(96)00014-7.
  • Frost, Richard A. (2003). Monadic Memoization towards Correctness-Preserving Reduction of Search (PDF). Proceedings of the 16th Canadian Society for Computational Studies of Intelligence Conference on Advances in Artificial Intelligence (AI'03). pp. 66–80. ISBN 978-3-540-40300-5.
  • Frost, Richard A.; Hafiz, Rahmatullah (2006). "A New Top-Down Parsing Algorithm to Accommodate Ambiguity and Left Recursion in Polynomial Time" (PDF). ACM SIGPLAN Notices. 41 (5): 46–54. doi:10.1145/1149982.1149988. S2CID 8006549.
  • Frost, Richard A.; Hafiz, Rahmatullah; Callaghan, Paul (2007). "Modular and Efficient Top-Down Parsing for Ambiguous Left-Recursive Grammars". Proceedings of the 10th International Workshop on Parsing Technologies (IWPT), ACL-SIGPARSE: 109–120. CiteSeerX 10.1.1.97.8915.
  • Frost, Richard A.; Hafiz, Rahmatullah; Callaghan, Paul (2008). Parser Combinators for Ambiguous Left-Recursive Grammars. Proceedings of the 10th International Symposium on Practical Aspects of Declarative Languages (PADL). ACM-SIGPLAN. Vol. 4902. pp. 167–181. CiteSeerX 10.1.1.89.2132. doi:10.1007/978-3-540-77442-6_12. ISBN 978-3-540-77441-9.
  • Hutton, Graham (1992). "Higher-order functions for parsing". Journal of Functional Programming. 2 (3): 323–343. CiteSeerX 10.1.1.34.1287. doi:10.1017/s0956796800000411.
  • Okasaki, Chris (1998). "Even higher-order functions for parsing or Why would anyone ever want to use a sixth-order function?". Journal of Functional Programming. 8 (2): 195–199. doi:10.1017/S0956796898003001.
  • Swierstra, S. Doaitse (2001). "Combinator parsers: From toys to tools" (PDF). Electronic Notes in Theoretical Computer Science. 41: 38–59. doi:10.1016/S1571-0661(05)80545-6.
  • Wadler, Philip (1985). How to replace failure by a list of successes — A method for exception handling, backtracking, and pattern matching in lazy functional languages. Proceedings of a Conference on Functional Programming Languages and Computer Architecture. Lecture Notes in Computer Science. Vol. 201. pp. 113–128. doi:10.1007/3-540-15975-4_33. ISBN 978-0-387-15975-1.

외부 링크