re2c

re2c


re2c
원본 작성자피터 품불리스
초기 릴리즈약 1994년; 28년 전 (1998년)[1]
안정적 해제
2.1.1 / 2021년 3월 27일; 12개월 전(2021-03-27)
리포지토리github.com/skvadrik/re2c
유형어휘분석기 발전기
면허증공용 도메인
웹사이트re2c.org

re2c는 C, C++, Go, Rust를 위한 무료 오픈소스 렉서 발전기다.선언적 정규 표현 명세를 결정론적 유한 자동자산에 취합한다.원래 피터 품불리스에 의해 쓰여지고 그의 논문에서 서술된 re2c는 공공영역에 편입되었고 그 이후 자원 봉사자들에 의해 유지되고 있다.[1][2]PHP,[3] SpamAssin,[4] Ninja 빌드 시스템[5] 등 프로젝트에서 채택한 렉서 발전기다.레몬 파서 제너레이터와 함께 re2c가 BRL-CAD에서 사용된다.[6]이 조합은 ISO 10303 표준의 구현인 STEPcode에도 사용된다.[7]

철학

re2c의 주요 목표는 적어도 손으로 코딩한 합리적으로 최적화된 C 렉서만큼 빠른 렉서를 생성하는 것이다.[1]re2c는 전통적인 테이블 주도 접근방식을 사용하는 대신 생성된 유한 상태 기계를 조건부 점프와 비교의 형태로 직접 인코딩한다.결과 프로그램은 테이블 기반 프로그램보다[1] 빠르고 디버깅과 이해가 훨씬 쉽다.더욱이, re2c는 DFA 최소화와 터널 자동화 구축과 같은 다수의 최적화를 적용하기 [1]때문에 이 접근방식은 종종 더 작은 렉서를 낳는다.[8]re2c의 또 다른 독특한 특징은 유연한 인터페이스다. 즉, re2c는 고정된 프로그램 템플릿을 가정하는 대신, 프로그래머가 인터페이스 코드의 대부분을 쓰고 생성된 렉서를 특정 환경에 적응시킬 수 있게 해준다.주된 아이디어는 re2c가 프로그래머에게 제로 코스트 추상화가 되어야 한다는 것이다: re2c를 사용하는 것은 해당 수작업 코드 구현보다 느린 프로그램을 초래해서는 안 된다.

특징들

  • submatch 추출:[9] re2c는 POSIX 호환 캡처 그룹과 독립 실행형 태그(가장 왼쪽 욕심 많은 disabigation과 반복적인 submatch의 선택적 처리 포함)를 모두 지원한다.구현은 룩어헤드-TDFA 알고리즘에 기초한다.[11][12][13]
  • 인코딩 지원:[14] re2c는 ASCII, UTF-8, UTF-16, UTF-32, UCS-2 및 EBCDIC를 지원한다.
  • 유연한 사용자 인터페이스:[15] 생성된 코드는 환경과의 인터페이스(읽기 입력 문자, 다음 입력 위치로 진격 등)를 위해 몇 가지 원시 연산 기능을 사용한다.; 사용자들은 그들이 필요로 하는 어떤 것에도 이러한 원시적 요소들을 재정의할 수 있다.
  • 저장 가능 상태:[16] re2c는 풀 모델 렉서(Lexer가 인터럽트 없이 실행되고 필요에 따라 더 많은 입력을 끌어들이는 경우)와 푸시 모델 렉서(Lexer가 주기적으로 중지되었다가 다시 시작되어 새로운 입력 덩어리를 구문 분석하는 경우)를 모두 지원한다.
  • 시작 조건:[17] re2c는 여러 개의 상호 관련 렉서를 생성할 수 있으며, 여기서 각 렉서는 프로그램의 특정 조건에 의해 트리거된다.
  • 자가 검증:[18] re2c는 사용된 모든 정의 인터페이스 코드를 무시하고 자급식 스켈레톤 프로그램을 생성하는 특수 모드를 가지고 있다.또한 re2c는 정규 문법에서 파생된 입력 문자열과 모든 입력에서 렉서 동작을 검증하는 데 사용되는 압축 일치 결과를 가진 파일 두 개를 생성한다.입력 문자열은 DFA 전환 및 경로를 광범위하게 다루도록 생성된다.데이터 생성은 DFA 구축 직후와 최적화 전에 발생하지만, 렉서 자체가 완전 최적화돼 있어 스켈레톤 프로그램은 최적화 및 코드 생성에 어떤 오류도 밝힐 수 있다.
  • 경고:[19] re2c는 프로그램의 정적 분석을 수행하고 사용자에게 정의되지 않은 제어 흐름, 연결할 수 없는 코드, 잘못된 형식의 탈출 기호 및 인터페이스 원시성의 잠재적인 오용과 같은 가능한 결함 또는 버그에 대해 경고한다.
  • 디버깅.re2c는 사람이 판독할 수 있는 렉서를 생성하는 것 외에도 NFA, DFA의 복수 단계, 결과 프로그램 그래프를 DOT 형식으로 생성하는 등 생성된 렉서의 다양한 중간 표현을 덤프하는 여러 옵션을 가지고 있다.[20]

구문

re2c 프로그램에는 다음이 포함될 수 있다./*!re2c ... */블록들각 블록은 일련의 규칙, 정의, 구성으로 구성된다(혼합될 수 있지만 일반적으로 구성을 먼저, 그 다음에 정의와 규칙을 넣는 것이 좋다).규칙에는 그 형태가 있다.REGEXP { CODE }또는REGEXP := CODE;어디에REGEXP정규 표현이고CODEC 코드의 블록이야언제REGEXP입력 문자열과 일치하며, 제어 흐름이 관련 항목으로 전송됨CODE. 한 가지 특별한 규칙이 있다: 기본 규칙은*대신에REGEXP; 일치하는 다른 규칙이 없을 경우 트리거됨.re2c에는 욕심 많은 일치하는 의미론이 있다. 여러 규칙이 일치하면 더 긴 접두사와 일치하는 규칙이 선호되고, 충돌하는 규칙이 동일한 접두사와 일치하면 이전 규칙의 우선 순위가 있다.정의는 그 형태를 가지고 있다.NAME = REGEXP;(또한)NAME { REGEXP }Flex 호환성 모드).구성에는 형식이 있음re2c:CONFIG = VALUE;어디에CONFIG특정 구성의 이름이며VALUE숫자 또는 문자열.고급 사용 방법은 공식 re2c 매뉴얼을 참조하십시오.[21]

정규식

re2c는 정규식에 다음과 같은 구문을 사용한다.

  • "foo"대소문자 구분 문자열 리터럴
  • 'foo'대소문자 구분 문자열 문자
  • [a-xyz],[^a-xyz]문자 클래스(영문 거부됨)
  • .뉴라인을 제외한 모든 문자
  • R \ S인성계급의 차이
  • R*0개 이상의 발생R
  • R+하나 이상의 발생.R
  • R?선택적R
  • R{n}의 반복.R정확히n시대
  • R{n,}의 반복.R적어도n시대
  • R{n,m}의 반복.R로부터n로m시대
  • (R)정의의R; 우선순위를 무시하거나 POSIX 스타일 하위 검색에 괄호 사용
  • R S연결:R그 뒤를 이어S
  • R S대안:R또는S
  • R / S미리 보기:R그 뒤를 이어S그렇지만S소비되지 않음
  • name로 정의되는 정규식name(Flex 호환성 모드에서는 제외)
  • @stags-태그: 마지막 입력 위치 저장@stag이름의 변수에 있는 일치stag
  • #mtagm-태그: 입력 위치를 모두 저장한다.#mtag이름의 변수에 있는 일치mtag

문자 클래스 및 문자열 리터럴에는 다음과 같은 이스케이프 시퀀스가 포함될 수 있다.\a,\b,\f,\n,\r,\t,\v,\\8각형 탈출\ooo그리고 16진법 탈출.\xhh,\uhhhh그리고\Uhhhhhhhh.

예

여기 re2c(example.re)의 매우 간단한 프로그램이 있다.모든 입력 인수가 16진수인지 확인한다.re2c에 대한 코드는 코멘트로 동봉되어 있다./*!re2c ... */나머지는 모두 C 코드야더 복잡한 예는 공식 re2c 웹 사이트를 참조하십시오.[22] 

#include <stdio.h>  정태의 t로 렉스(경시하다 마를 뜨다 *YY 커서) {     경시하다 마를 뜨다 *와이마커;     /*!re2c re2c:define:YYCTYPE = char; re2c:yfill:enable = 0;  끝 = "\x00"; 16진수 = "0x" [0-9a-fA-F]+;  * { printf("err\n"; return 1; } 16진수 끝 { printf("hex\n"; 반환 0; } */ }  t로 본래의(t로 argc, 마를 뜨다 **아그브) {     을 위해 (t로 i = 1; i < argc; ++i) {         렉스(아그브[i]);     }     돌아오다 0; }

그런 걸 봤을 때.re2c -is -o example.c example.re아래 코드 생성(cdv.c).코멘트의 내용/*!re2c ... */조건부 점프와 비교의 형태로 인코딩된 결정론적 유한 자동화로 대체된다. 프로그램의 나머지 부분은 출력 파일에 그대로 복사된다.몇 가지 코드 생성 옵션이 있으며, 일반적으로 re2c 사용switch문, 그러나 중첩을 사용할 수 있음if(이 예에서와 같이) 진술-s옵션) 또는 비트맵 및 점프 테이블 생성어떤 옵션이 더 나은지는 C 컴파일러에 달려있다; re2c 사용자는 실험을 하도록 권장된다. 

/* re2c 1.2.1에 의해 8월 23일 21:59:00 2019 */ #include <stdio.h>  정태의 t로 렉스(경시하다 마를 뜨다 *YY 커서) {     경시하다 마를 뜨다 *와이마커;      {  마를 뜨다 yych;  yych = *YY 커서;  만일 (yych == '0') 에 가다 yy4;  ++YY 커서; yy3:  { 활자화하다("err\n"); 돌아오다 1; } yy4:  yych = *(와이마커 = ++YY 커서);  만일 (yych != 'x') 에 가다 yy3;  yych = *++YY 커서;  만일 (yych >= 0x01) 에 가다 yy8; yy6:  YY 커서 = 와이마커;  에 가다 yy3; yy7:  yych = *++YY 커서; yy8:  만일 (yych <= '@') {   만일 (yych <= 0x00) 에 가다 yy9;   만일 (yych <= '/') 에 가다 yy6;   만일 (yych <= '9') 에 가다 yy7;   에 가다 yy6;  } 다른 {   만일 (yych <= 'F') 에 가다 yy7;   만일 (yych <= '`') 에 가다 yy6;   만일 (yych <= 'f') 에 가다 yy7;   에 가다 yy6;  } yy9:  ++YY 커서;  { 활자화하다("hex\n"); 돌아오다 0; } }  }  t로 본래의(t로 argc, 마를 뜨다 **아그브) {     을 위해 (t로 i = 1; i < argc; ++i) {         렉스(아그브[i]);     }     돌아오다 0; }

참고 항목

참조

  1. ^ a b c d e Bumbulis, Peter; Donald D., Cowan (March–December 1993). "RE2C: a more versatile scanner generator". ACM Letters on Programming Languages and Systems. 2 (1–4): 70–84. doi:10.1145/176454.176487. S2CID 14814637.
  2. ^ "Authors, re2c documentation".
  3. ^ "Building PHP". PHP Internals Book. Retrieved 2020-07-20.
  4. ^ "SpamAssassin (sa-compile)".
  5. ^ "Ninja: build.ninja". Ninja. Retrieved 2020-07-20.
  6. ^ "BRL-CAD (tools: re2c)".
  7. ^ "Build Process".
  8. ^ Joseph, Grosch (1989). "Efficient Generation of Table-Driven Scanners". Software: Practice and Experience 19: 1089–1103.
  9. ^ "Submatch extraction, re2c documentation".
  10. ^ Ville, Laurikari (2000). "NFAs with tagged transitions, their conversion to deterministic automata and application to regular expressions" (PDF). Seventh International Symposium on String Processing and Information Retrieval, 2000. SPIRE 2000. Proceedings.
  11. ^ Ulya, Trofimovich (2017). "Tagged Deterministic Finite Automata with Lookahead". arXiv:1907.08837 [cs.FL].
  12. ^ Ulya, Trofimovich (2020). "RE2C -- a lexer generator based on lookahead TDFA". Software Impacts. 6: 100027. doi:10.1016/j.simpa.2020.100027.
  13. ^ Ulya, Trofimovich (2021). "Lookahead TDFA in pictures (slides)" (PDF).
  14. ^ "Encodings, re2c documentation".
  15. ^ "Program interface, re2c documentation".
  16. ^ "Storable state, re2c documentation".
  17. ^ "Start conditions, re2c documentation".
  18. ^ "Skeleton, re2c documentation".
  19. ^ "Warnings, re2c documentation".
  20. ^ "Visualization, re2c documentation".
  21. ^ "User manual (C), re2c documentation".
  22. ^ "Official webcite".

외부 링크