이것은 lex의 버그입니까?

Question

규칙 :

%% 
AAAA  print("AAAA  : %s\n",yytext); 
AAA  print("AAA  : %s\n",yytext); 
AA  print("AA  : %s\n",yytext); 

그리고 입력이 AAAAA이며, 출력은 다음과 같습니다

AAAA  : AAAA 
A 

대신 :

AAA  : AAA 
AA  : AAA 

가 렉스의 버그인가?

Answer 1

아니요, 사양을 고수하고 있습니다.

규칙 패턴 매칭 동안 (man 1p lex)

렉스 단일 최장 일치하는 패턴들의 세트를 검색하여야한다. 같은 수의 문자와 일치하는 규칙 중에서 먼저 주어진 규칙이 선택됩니다.

그래서 가장 먼저 AAAA을 먼저 검색합니다. 이 규칙은 여러 언어의 어휘 규칙에서 일반적입니다. 예 : C++는 : 문자 *=가 (가장 긴 경기 인) 할당 - 곱셈 연산자로 해석되기 때문에

void f(void*=0); 

하지 * 다음 =, 구문 분석하는 데 실패합니다.

이 규칙의 이유는 효율적으로 구현할 수 있기 때문입니다. 이 규칙이 적용된 스캐너는 O (1) 공간 (입력, 즉 입력이 메모리에 맞지 않아도 됨)과 O (N) 시간 만 필요합니다. 나머지 입력을 토큰화할 수 있는지 확인하려면 O (N) 공간과 O (N^2) 시간이 필요합니다. 특히 모든 컴파일 작업이 선형 패스로 수행되는 중세 시대에는 메모리 소비가 결정적이었습니다. 그리고 오늘 수십만 라인 소스 파일 (예 : 헤더를 포함한 C 파일)을 파싱 할 때 O (N^2) 실행 시간을 인식하지 않을 것이라고 확신합니다. 둘째, 이렇게 생성 된 스캐너는 매우 빠르며 파싱 할 때 많은 도움을줍니다.

마지막으로, 규칙은 이해하기 쉽습니다. 반대의 예로, ANTLR의 토큰 화 규칙을 고려하십시오. 현재 토큰의 접두어가 토큰이고 입력이 접두어에서 토큰 화 가능하더라도 일치하지 않는 경우가 있습니다. 예 :

TOK1 : 12 
TOK2 : (13)+ 

은 '12131312'와 일치하지 않습니다. lex에서는 이러한 놀람이 발생하지 않습니다. 그래서 저는 그대로 규칙을 지키라고 제안합니다.