Рефлекс

Рефлекс

Разработчик(и)	Доктор Роберт ван Энгелен
Первоначальный выпуск	5 декабря 2016 г ( 05.12.2016 )
Стабильная версия	4.0 / 18 февраля 2024 г. ( 18 февраля 2024 г. )
Репозиторий	github .с / Дженивия /Рефлекс
Написано в	С++
Операционная система	Кросс-платформенный
Тип	Лексический анализ
Лицензия	Лицензия BSD
Веб-сайт	https://github.com/Genivia/RE-flex

RE/flex (регулярно-ориентированный, быстрый лексический анализатор) это бесплатная компьютерная программа с открытым исходным кодом , написанная на C++, которая генерирует быстрые лексические анализаторы (также известные как «сканеры» или «лексеры»). в С++. RE/flex предлагает полную поддержку Unicode , привязки отступов, границы слов, ленивые квантификаторы (нежадные, ленивые повторы) и параметры настройки производительности. RE/flex принимает спецификации лексера Flex и предлагает варианты создания сканеров для парсеров Bison. RE/flex включает в себя быструю библиотеку регулярных выражений C++ .

История

Проект RE/flex был разработан и реализован профессором Робертом ван Энгеленом в 2016 году и выпущен как бесплатный с открытым исходным кодом. Программное обеспечение развивалось благодаря вкладу других людей. Инструмент RE/flex создает лексические анализаторы на основе библиотек регулярных выражений («регулярных выражений») вместо фиксированных таблиц DFA , создаваемых традиционными генераторами лексических анализаторов.

Спецификация лексера

Генератор лексического анализатора RE/flex принимает на вход расширенный синтаксис спецификаций лексера Flex . Синтаксис спецификации RE/flex более выразителен, чем традиционный синтаксис спецификации лексера Flex , и может включать в себя привязки отступов, границы слов, ленивые квантификаторы (нежадные, ленивые повторы) и новые действия, такие как wstr() для получения совпадений широких строк Юникода.

Спецификация лексера имеет вид:

Definitions
%%
Rules
%%
User Code

Раздел «Определения» содержит объявления и параметры настройки, за которыми следуют пары «имя-шаблон» для определения имен для шаблонов регулярных выражений. На именованные шаблоны можно ссылаться в других шаблонах, включив их в { и }. В следующем примере определяются два имени для двух шаблонов, где второй шаблон number использует ранее названный шаблон digit:

%top{
  #include <inttypes.h> // strtol()
}

%class{
  public:
    int value; // yyFlexLexer class public member
}

%init{
  value = 0; // yyFlexLexer initializations
}

%option flex

digit     [0-9]
number    {digit}+

В разделе «Правила» определяются пары «шаблон-действие». В следующем примере определяется правило для преобразования числа в целое число класса лексера. value член:

{number}  value = strtol(yytext, NULL, 10);
\s        // skip white space
.         throw *yytext;

В разделе «Код пользователя» обычно определяются функции C/C++, например main программа:

int main()
{
  yyFlexLexer lexer;
  try
  {
    while (lexer.yylex() != 0)
      std::cout << "number=" << lexer.value << std::endl;
  }
  catch (int ch)
  {
    std::cerr << "Error: unknown character code " << ch << std::endl;
  }
}

The yyFlexLexer класс генерируется RE/flex в соответствии с инструкциями %option flex директива в спецификации лексера. Сгенерированный lex.yy.cpp исходный код содержит алгоритм лексического анализа, связанный с libreflex библиотека.

Вывод исходного кода

Сгенерированный алгоритм лексического анализа основан на концепции, согласно которой любой механизм регулярных выражений в принципе может использоваться для токенизации входных данных в токены : задан набор из n шаблонов регулярных выражений. $p_{i}$ для $i=1,\ldots ,n$, регулярное выражение формы "($p_{1}$)|($p_{2}$)|...|($p_{n}$)" с n альтернативами можно указать для сопоставления и маркировки входных данных. Таким образом, индекс группового захвата i соответствующего шаблона $p_{i}$ который возвращается средством сопоставления регулярных выражений, идентифицирует шаблон $p_{i}$ который частично и постоянно совпадал с входным текстом после предыдущего совпадения.

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

Следующие RE/flex-сгенерированные yyFlexLexer сорт yylex метод неоднократно вызывает сопоставитель scan (непрерывное частичное сопоставление) для токенизации ввода:

int yyFlexLexer::yylex()
{
  if (!has_matcher())
    matcher("(p1)|(p2)|...|(pn)"); // new matcher engine for regex pattern (p1)|(p2)|...|(pn)
  while (true)
  {
    switch (matcher().scan()) // scan and match next token, get capture index
    {
      case 0: // no match
        if (... EOF reached ...)
          return 0;
        output(matcher().input()); // echo the current input character
        break;
      case 1: // pattern p1 matched
        ... // Action for pattern p1
        break;
      case 2: // pattern p2 matched
        ... // Action for pattern p2
        break;
      ... // and so on for patterns up to pn
    }
  }
}

Если ни один из n шаблонов не соответствует и не достигается конец файла (EOF), применяется так называемое «правило по умолчанию». Правило по умолчанию отображает текущий входной символ и перемещает сканер к следующему входному символу.

Шаблон регулярного выражения "($p_{1}$)|($p_{2}$)|...|($p_{n}$)" создается RE/flex из спецификации лексера с n правилами пар шаблон-действие:

%%
p1    Action for pattern p1
p2    Action for pattern p2
...
pn    Action for pattern pn
%%

Из этой спецификации RE/flex генерирует вышеупомянутое yyFlexLexer класс с yylex() метод, который выполняет действия, соответствующие шаблонам, совпадающим во входных данных. Сгенерированный yyFlexLexer Класс используется в приложении C++, таком как анализатор, для разбивки входных данных на целочисленные токены, возвращаемые действиями в спецификации лексера. Например:

std::ifstream ifs(filename, std::ios::in);
yyFlexLexer lexer(ifs);
int token;
while ((token = lexer.yylex()) != 0)
  std::cout << "token = " << token << std::endl;
ifs.close();

Обратите внимание, что yylex() возвращает целочисленное значение при выполнении действия return token_value;. В противном случае, yylex() не возвращает значение и продолжает сканирование входных данных, что часто используется правилами, игнорирующими вводимые данные, например комментарии.

В этом примере токенизируется файл. Лексический анализатор часто служит токенизатором для синтаксического анализатора, созданного генератором синтаксических анализаторов, таким как Bison .

Совместимость

RE/flex совместим со спецификациями Flex, если %option flex используется. Это создает yyFlexLexer класс с yylex() метод. RE/flex также совместим с Bison, используя ряд опций RE/flex для полного охвата опций и функций Bison.

В отличие от Flex, сканеры RE/flex по умолчанию являются потокобезопасными при работе с реентерабельными парсерами Bison.

Поддержка Юникод

RE/flex поддерживает шаблоны регулярных выражений Unicode в спецификациях лексеров и автоматически маркирует входные файлы UTF-8, UTF-16 и UTF-32. Кодовые страницы могут быть указаны для токенизации входных файлов, закодированных в ISO/IEC 8859 от 1 до 16, от Windows-1250 до Windows-1258 , CP-437, CP-850, CP-858, MacRoman, KOI-8 , EBCDIC и т. д. . Нормализация до UTF-8 автоматически выполняется с помощью внутренней инкрементной буферизации для (частичного) сопоставления шаблонов с шаблонами регулярных выражений Юникода.

Соответствие отступов, узлов и отступов

RE/flex интегрирует сопоставление отступов и отступов непосредственно в синтаксисе регулярных выражений с новыми \i и \j якоря. строк Эти привязки отступов обнаруживают изменения отступов во входных данных. Это позволяет охватить множество практических сценариев токенизации языков программирования с блочными структурами с отступом. Например, следующая спецификация лексера обнаруживает и сообщает об изменениях отступов:

%%
^[ \t]+        std::cout << "| "; // nodent: text is aligned to current indent margin
^[ \t]*\i      std::cout << "> "; // indent: matched with \i
^[ \t]*\j      std::cout << "< "; // dedent: matched with \j
\j             std::cout << "< "; // dedent: for each extra level dedented
%%

Ленивые квантификаторы

Ленивые квантификаторы могут быть связаны с повторами в шаблонах регулярных выражений RE/flex, чтобы упростить выражения с использованием нежадных повторов, когда это применимо. Обычно сопоставление является «жадным», что означает, что сопоставляется самый длинный шаблон. Например, шаблон a.*b с жадным * повторять матчи aab, но также соответствует abab потому что .* соответствует любым символам, кроме новой строки и abab длиннее, чем ab. Использование ленивого квантификатора ? за ленивое повторение *?, шаблон a.*?b спички ab но не abab.

В качестве практического применения ленивых квантификаторов рассмотрим сопоставление многострочных комментариев C/C++ вида /*...*/. Шаблон спецификации лексера "/*"(.|\n)*?"*/" с ленивым повторением *? соответствует многострочным комментариям. Без лениво повторяет узор "/*"([^*]|(\*+[^*/]))*\*+"/" следует использовать (обратите внимание, что цитата вида "..." разрешено только в спецификациях лексера, эта конструкция сравнима с \Q...\E котировки, поддерживаемые большинством библиотек регулярных выражений.)

Другие сопоставители шаблонов

Помимо встроенного средства сопоставления шаблонов регулярных выражений RE/flex POSIX, RE/flex также поддерживает библиотеки сопоставления шаблонов PCRE2, Boost.Regex и std::regex. PCRE2 и Boost.Regex предлагают более богатый синтаксис шаблонов регулярных выражений с семантикой сопоставления шаблонов Perl, но работают медленнее из-за встроенного в них алгоритма сопоставления на основе NFA .

Перевод

Lex, Flex и RE/flex преобразуют регулярные выражения в DFA , которые реализуются в таблицах для сканирования во время выполнения. RE/flex отличается от Lex и Flex тем, что сгенерированные таблицы содержат список слов кода операции, выполняемых виртуальной машиной для сопоставления с образцом. Кроме того, DFA, реализованный в коде, а не в таблицах кодов операций, генерируется с помощью --fast вариант.

Например, следующий DFA с прямым кодом для шаблона \w+ генерируется с опцией --fast:

void reflex_code_INITIAL(reflex::Matcher& m)
{
  int c0 = 0, c1 = 0;
  m.FSM_INIT(c1);
S0:
  m.FSM_FIND();
  c1 = m.FSM_CHAR();
  if ('a' <= c1 && c1 <= 'z') goto S5;
  if (c1 == '_') goto S5;
  if ('A' <= c1 && c1 <= 'Z') goto S5;
  if ('0' <= c1 && c1 <= '9') goto S5;
  return m.FSM_HALT(c1);
S5:
  m.FSM_TAKE(1);
  c1 = m.FSM_CHAR();
  if ('a' <= c1 && c1 <= 'z') goto S5;
  if (c1 == '_') goto S5;
  if ('A' <= c1 && c1 <= 'Z') goto S5;
  if ('0' <= c1 && c1 <= '9') goto S5;
  return m.FSM_HALT(c1);
}

Список слов кода операции виртуальной машины для шаблона \w+ генерируется с опцией --full:

REFLEX_CODE_DECL reflex_code_INITIAL[11] =
{
  0x617A0005, // 0: GOTO 5 ON 'a'-'z'
  0x5F5F0005, // 1: GOTO 5 ON '_'
  0x415A0005, // 2: GOTO 5 ON 'A'-'Z'
  0x30390005, // 3: GOTO 5 ON '0'-'9'
  0x00FFFFFF, // 4: HALT
  0xFE000001, // 5: TAKE 1
  0x617A0005, // 6: GOTO 5 ON 'a'-'z'
  0x5F5F0005, // 7: GOTO 5 ON '_'
  0x415A0005, // 8: GOTO 5 ON 'A'-'Z'
  0x30390005, // 9: GOTO 5 ON '0'-'9'
  0x00FFFFFF, // 10: HALT
};

Отладка и профилирование

Встроенный профилировщик RE/flex можно использовать для автоматического измерения производительности созданного сканера. Профилировщик исходный код сканера для сбора показателей использует времени выполнения. Во время выполнения, когда инструментированный сканер завершает работу, профилировщик сообщает количество совпадений правила и совокупное время, затраченное на сопоставление правила. Профилирование включает время, проведенное в анализаторе, когда правило возвращает управление анализатору. Это позволяет точно настроить производительность сгенерированных сканеров и парсеров. Правила лексера, которые являются «горячими точками» , т.е. требуют больших вычислительных затрат, обнаруживаются и могут быть оптимизированы пользователем в исходном коде лексера.

Также поддерживается отладка созданного сканера с помощью опций, совместимых с Flex. Во время сканирования выводятся аннотированные правила лексера.

См. также

• Лексический анализ
• Сравнение генераторов парсеров

Внешние ссылки

• RE/гибкое руководство
• Страница проекта на GitHub