Flex는 A, AB 및 ABC를 어떻게 구별합니까?

Question

Flex에 대해이 실험을 수행하여 ABC를 입력했는지 확인합니다. ABC, ABC 또는 ABC 만 표시되거나 표현식 목록에서 첫 번째 일치 만 표시됩니다.

%{ 
#include <stdio.h> 
%} 

%% 
A puts("got A"); 
AB puts("got AB"); 
ABC puts("got ABC"); 
%% 

int main(int argc, char **argv) 
{ 
    yylex(); 

    return 0; 
} 

내가 컴파일하고 프로그램을 실행 한 후 ABC를 입력, 내가 렉스 방문 텍스트를 추적하고, 첫 번째 일치하는 항목을 발견하지 않는 생각 때문에 정말 나를 놀라게한다 "있어 ABC"로 응답; 하지만 사실, 그것은 가장 긴 일치를 찾는 것으로 보인다.

더 이상 일치하지 않는 경우에만 Flex가 A에 응답하기 위해 어떤 전략을 사용합니까?

Answer 1

(F)는 렉스가 잘 설명되어 있기 때문에 maximal-munch 원리는 거의 놀라운 일이 없어야 사용하는 사실 Flex manual :

생성 된 스캐너가 실행

, 그것은 문자열을 찾고 입력을 분석하는 패턴과 일치해야합니다. 일치하는 항목이 두 개 이상인 경우 & hellip;과 가장 일치하는 항목이 필요합니다. 동일한 길이의 두 개 이상의 일치 항목을 발견하면 플렉스 입력 파일에서 처음 나열된 규칙이 선택됩니다. ("입력이 일치 방법"섹션의 첫 번째 단락)

정확한 알고리즘 대단히 간단 토큰은 DFA를 통해 이동 플렉스 검사 텍스트를 요청할 때마다. 수락 상태에 도달 할 때마다 현재 텍스트 위치를 기록합니다. 전환이 더 이상 가능하지 않으면 마지막으로 기록 된 수용 위치로 돌아가고 토큰의 끝이됩니다.

결과적으로 (F) lex는 각 텍스트에 대해 한 번만 스캔하지만 동일한 텍스트를 여러 번 스캔 할 수 있습니다.

과도한 역 추적이 필요한 어휘 규칙 집합은 어휘 검색 속도를 늦 춥니 다. 이 문제는 플렉스 매뉴얼 섹션 Performance Considerations에서 문제를 피하기위한 몇 가지 전략과 함께 논의됩니다. 그러나 병리학 적 경우를 제외하면 역 추적의 오버 헤드가 눈에 띄지 않습니다.