Можно ли установить приоритеты для правил, чтобы избежать «самого раннего» шаблона сопоставления? - PullRequest
Новая
       10

Можно ли установить приоритеты для правил, чтобы избежать «самого раннего» шаблона сопоставления?

14 голосов
/ 05 декабря 2011

Еще один простой вопрос: есть ли способ сказать флексу, чтобы он предпочитал правило, которое соответствует короткой вещи, а не правилу, которое соответствует более длинной вещи? Я не могу найти хорошую документацию по этому поводу.

Вот почему мне это нужно: я анализирую файл для псевдоязыка, который содержит некоторые ключевые слова, соответствующие инструкциям управления. Я бы хотел, чтобы они были абсолютным приоритетом, чтобы они не анализировались как части выражения. Я действительно нуждаюсь в этой приоритетной вещи, потому что мне не нужно писать полную грамматику для моего проекта (в моем случае это было бы совершенно излишним, так как я выполняю структурный анализ анализируемой программы, мне не нужно знать детали). ., поэтому я не могу использовать точную грамматическую настройку, чтобы быть уверенным, что эти блоки не будут проанализированы в выражении.

Любая помощь будет оценена.

Вот пример разбора файла: 

If a > 0 Then read(b); Endif
c := "If I were...";
While d > 5 Do d := d + 1 Endwhile

Я просто хочу собрать информацию о Ifs, Thens, Endifs и т.д ... Остальное не имеет значения для меня. Вот почему я бы хотел, чтобы правила, связанные с Ifs, Thens и т. Д., Были приоритетными без необходимости писать грамматику.

1 Ответ

14 голосов
/ 07 декабря 2011

Из Книги Дракона, 2-е издание, раздел 3.5.3 «Разрешение конфликтов в Lex»: 

We have alluded to the two rules that Lex uses to decide on the proper lexeme
to select, when several prefixes of the input match one or more patterns:
    1. Always prefer a longer prefix to a shorter prefix.
    2. If the longest possible prefix matches two or more patterns, prefer the
       pattern listed first in the Lex program.

Приведенное выше правило также применимо к Flex.Вот что говорится в руководстве Flex (Глава 7: Как сопоставляются входные данные.) 

When the generated scanner is run, it analyzes its input looking for strings 
which match any of its patterns. If it finds more than one match, it takes the 
one matching the most text (for trailing context rules, this includes the length 
of the trailing part, even though it will then be returned to the input). If it 
finds two or more matches of the same length, the rule listed first in the flex 
input file is chosen.

Если я правильно понял, ваш лексер рассматривает такие ключевые слова, как Endif, как идентификатор,поэтому он будет рассматриваться как часть выражения впоследствии.Если это ваша проблема, просто поместите правила ключевых слов поверх вашей спецификации , например, такие: (предположим, что каждое слово в верхнем регистре является предопределенным перечислением, соответствующим токену) 

"If"                      { return IF;         }
"Then"                    { return THEN;       }
"Endif"                   { return ENDIF;      }
"While"                   { return WHILE;      }
"Do"                      { return DO;         }
"EndWhile"                { return ENDWHILE;   }
\"(\\.|[^\\"])*\"         { return STRING;     }
[a-zA-Z_][a-zA-Z0-9_]*    { return IDENTIFIER; }

Тогда ключевые слова всегда будут совпадать перед идентификатором в соответствии с правилом № 2.

РЕДАКТИРОВАТЬ:

Спасибо за ваш комментарийКол.Я забыл добавить правило для строки. Но я не думаю, что мое решение неверно. Например, если будет применяться идентификатор с именем If_this_is_an_identifier, правило 1 , таким образом, правило идентификатора вступит в силу (так как оно соответствуетсамая длинная строка).Я написал простой тестовый пример и не нашел проблем в своем решении.Вот мой файл lex.l: 

%{
  #include <iostream>
  using namespace std;
%}

ID       [a-zA-Z_][a-zA-Z0-9_]*

%option noyywrap
%%

"If"                      { cout << "IF: " << yytext << endl;         }
"Then"                    { cout << "THEN: " << yytext << endl;       }
"Endif"                   { cout << "ENDIF: " << yytext << endl;      }
"While"                   { cout << "WHILE: " << yytext << endl;      }
"Do"                      { cout << "DO: " << yytext << endl;         }
"EndWhile"                { cout << "ENDWHILE: " << yytext << endl;   }
\"(\\.|[^\\"])*\"         { cout << "STRING: " << yytext << endl;     }
{ID}                      { cout << "IDENTIFIER: " << yytext << endl; }
.                         { cout << "Ignore token: " << yytext << endl; }

%%

int main(int argc, char* argv[]) {
  ++argv, --argc;  /* skip over program name */
  if ( argc > 0 )
    yyin = fopen( argv[0], "r" );
  else
    yyin = stdin;

  yylex();
}

Я проверил свое решение с помощью следующего контрольного примера: 

If If_this_is_an_identifier > 0 Then read(b); Endif
    c := "If I were...";
While While_this_is_also_an_identifier > 5 Do d := d + 1 Endwhile

, и он дает мне следующий вывод (другой вывод, не относящийся купомянутая вами проблема игнорируется.) 

IF: If
IDENTIFIER: If_this_is_an_identifier
......
STRING: "If I were..."
......
WHILE: While
IDENTIFIER: While_this_is_also_an_identifier

Программа lex.l модифицирована на основе примера из flex manual : (который использует тот же метод для сопоставления ключевого слова с идентификаторами)

Также взгляните на грамматику ANSI C, спецификацию Lex .

Я также использовал этот подход в своем личном проекте, и поэтомуПока я не нашел никаких проблем.

...