스캐너리스 해석

Scannerless parsing

컴퓨터 과학에서 스캐너리스 파싱(렉서리스 파싱이라고도 함)은 토큰화(문자의 스트림을 단어로 분할)와 파싱(단어를 구로 배열)을 동시에 실행하는 렉서 파이프라인으로 분할하는 것이 아니라 단일 단계로 수행합니다.언어 문법은 언어의 어휘(단어 수준)와 구문 수준 구조를 모두 표현하기 위해 단일 형식주의를 사용하는 경우 스캐너 없이 사용할 수 있습니다.

처리를 렉서 다음에 파서로 분할하는 것은 모듈러형입니다.스캐너리스 파싱은 주로 렉서-파서의 명확한 구분이 불필요하거나 불필요한 경우에 사용됩니다.적절한 예로는 TeX, 대부분의 Wiki 문법, makefile, 단순한 응용 프로그램 고유의 스크립트 언어, Raku 등이 있습니다.

이점

  • 하나의 메타 언어만 필요합니다.
  • 불규칙한 어휘 구조를 쉽게 다룰 수 있습니다.
  • "token classification(토큰 분류)"은 불필요하며, "texer hack(렉서 해킹)" 및 언어 예약 단어(C의 "while(while)"와 같은 설계 수용이 필요하지 않습니다.
  • 문법은 구성될 수 있습니다(인간의 개입 없이 병합할 수 있습니다.

단점들

  • 어휘 검색과 구문 파싱이 결합되어 있기 때문에 결과 파서는 더 복잡해지고, 따라서 이해와 디버깅이 더 어려워지는 경향이 있습니다.파서를 생성하기 위해 문법이 사용되는 경우 관련 문법에 대해서도 동일한 내용이 적용됩니다.
  • 결과적으로 발생하는 파서는 시간과 [1]메모리 모두에서 렉서-파서 파이프라인보다 훨씬 덜 효율적입니다.

실장

  • SGLR은 모듈러 구문 정의 형식주의 SDF의 파서이며 ASF+SDF Meta-Environment 및 Stratego/XT 프로그램 변환 시스템의 일부입니다.
  • JSGLR은 SDF를 기반으로 한 순수 Java 구현입니다.
  • TXL은 문자 수준의 해석을 지원합니다.
  • dparser는 스캐너리스 GLR 파서의 ANSI C 코드를 생성합니다.
  • Spirit는 스캐너리스와 스캐너 기반의 해석을 모두 가능하게 합니다.
  • SBP는 Java로 작성된 부울 문법(문맥이 없는 문법의 상위 집합)용 스캐너리스 파서입니다.
  • Laja는 Java로 작성된 오브젝트에 문법 규칙을 매핑하는 것을 지원하는 2단계 스캐너 없는 파서 생성기입니다.
  • 범용 프로그래밍 언어 Raku의 Raku Grammars 특징.
  • PyParsing은 순수 Python으로 작성된 스캐너리스 파서입니다.
  • META II 토큰 파서 기능이 내장되어 있습니다.
  • TREE-META Like META II도 렉서 기능이 내장된 스캐너리스입니다.
  • CWIC 컴파일러를 통한 컴파일러 기술 및 구현.언어의 일부로 토큰 규칙이 있습니다.CWIC의 규칙은 성공 또는 실패를 반환하는 부울 함수로 컴파일되었습니다.

메모들

  • a 이는 일반 언어의 문자열 시퀀스의 문맥이 없는 언어와 달리 파서에 의해 인식되는 언어를 문자에 정의된 단일 문맥이 없는 언어로 만들기 때문입니다.일부 렉서리스 파서는 문맥이 없는 언어의 전체 클래스를 처리하며, 구도로 닫혀 있습니다.

레퍼런스

  1. ^ Economopoulos, Giorgios; Klint, Paul; Vinju, Jurgen (2009). "Faster Scannerless GLR Parsing" (PDF). Compiler Construction. 5501: 126–141. doi:10.1007/978-3-642-00722-4_10.

추가 정보