flex/bison 파서는 어떤 순서로든 최대 하나의 토큰을 받아 들일 수 있습니까?

Question

제 언어에서는 특정 시점에서 하나의 토큰 집합에서 하나의 토큰 만 받아 들여야합니다. 예를 들기 위해, 괄호 표현은 임의의 순서 !^&의 최대 한 다음 될 수 있으므로, 다음의 2 행은 동일해야

(foo)!^ 
(foo)^! 

다음 하나는 (a 토큰 회 반복)

불법

(foo)^!^ 

자연스럽게 CFG 규칙을 사용하여 모든 가능성을 다 써 버리지 않는가? 렉시 컬 (flex) 또는 구문 (bison) 레벨 중 하나를 사용합니다.

Answer 1

정규 표현식 또는 모든 가능성을 열거하는 것 이외의 다른 CFG를 사용하여 작업을 수행 할 수는 없습니다. (그룹화하여 실제 크기는 줄일 수 있지만 여전히 지수 적입니다.) 하나의 인스턴스 만 있고 토큰이 3 개만있는 경우 목록이 가장 쉬운 솔루션 일 것입니다.

그러나 다양한 토큰이 있고 앞으로 목록을 확장하려는 경우 모든 토큰 조합을 허용하는 것이 더 쉽지만 토큰 목록에 비트 맵을 연결하면 쉽게 중복을 확인할 수 있습니다 아마도 오류 메시지가 나타납니다.

당신이 언급 한 정확한 사례에 대한 간단한 flex 해결책이 있습니다. (원래는 필자가 많은 코드를 복제했지만 다음과 같이 읽기 쉽다고 생각합니다.) <MODS> 시작 조건은 첫 번째 모양이 [&^!] 일 때 트리거되고 그 나머지 부분을 흡수합니다. 다른 문자가 발견되면 다시 스캔하도록 표시되고 (yyless(0)) 수정 자의 현재 마스크가 반환됩니다.

%{ 
    // The MODS token has %type <ModMask>, and the associated 
    // semantic value will be the union of the enum bits. 
    typedef unsigned int ModMask; 
    enum { MOD_HAT=1, MOD_BANG=2, MOD_AMP=4 }; 
    // This function maps a character to a modmask value. 
    // A real implementation would use a lookup table. I just included 
    // this definition so the snippet is usable. 
    ModMask tokenToMask(unsigned char c) { 
    return c == '^' ? MOD_HAT : 
      c == '!' ? MOD_BANG : 
      c == '&' ? MOD_AMP : 0; 
%} 

%x SC_MODS 

%% 

[&^!]  { yylval.modmask = tokenToMask(yytext[0]; BEGIN(MODS); } 
<MODS>[&^!] { ModMask m = tokenToMask(yytext[0]; 
       if (yylval.modmask & m) { 
       yyerror("Duplicate modifier"); 
       } 
       yylval.modmask |= m; 
      } 
<MODS>.|\n { yyless(0); BEGIN(INITIAL); return MODS; }