re2c

re2c - это бесплатный генератор лексеров с открытым исходным кодом для C , C ++ и Go . Он компилирует декларативные спецификации регулярных выражений в детерминированные конечные автоматы . Первоначально написанный Питером Бумбулисом и описанный в его статье, ^[1] re2c стал общественным достоянием и с тех пор поддерживается добровольцами. ^[2] Это генератор лексера, принятый в таких проектах, как PHP , ^[3] SpamAssassin , ^[4] Ninja build system ^[5] и другие. Вместе с лимономГенератор парсеров, re2c используется в BRL-CAD . ^[6] Эта комбинация также используется с STEPcode, реализацией стандарта ISO 10303 . ^[7]

Философия [ править ]

Основная цель re2c - генерировать быстрые лексеры: ^[1] как минимум такие же быстрые, как разумно оптимизированные лексеры C, написанные вручную. Вместо использования традиционного подхода, управляемого таблицами, re2c кодирует сгенерированный конечный автомат непосредственно в форме условных переходов и сравнений. Полученная программа работает быстрее, чем ее аналог, управляемый таблицами ^[1], и ее намного проще отлаживать и понимать. Более того, этот подход часто приводит к меньшим лексерам ^[1], поскольку re2c применяет ряд оптимизаций, таких как минимизация DFA и построение туннельного автомата. ^[8]Другой отличительной особенностью re2c является его гибкий интерфейс: вместо использования фиксированного шаблона программы, re2c позволяет программисту писать большую часть кода интерфейса и адаптировать сгенерированный лексер к любой конкретной среде. Основная идея заключается в том, что re2c должен быть абстракцией с нулевой стоимостью для программиста: его использование никогда не должно приводить к более медленной программе, чем соответствующая реализация , написанная вручную.

Особенности [ править ]

• Извлечение подматча: ^[9] re2c поддерживает как POSIX-совместимые группы захвата, так и автономные теги ^[10] (с крайним левым жадным устранением неоднозначности и дополнительной обработкой повторяющихся подсовпадений). Реализация основана на алгоритме lookahead-TDFA. ^[11]

• Поддержка кодирования: ^[12] re2c поддерживает ASCII, UTF-8, UTF-16, UTF-32, UCS-2 и EBCDIC.
• Гибкий пользовательский интерфейс: ^[13] сгенерированный код использует несколько примитивных операций для взаимодействия с окружающей средой (чтение вводимых символов, переход к следующей позиции ввода и т. Д.); пользователи могут переопределить эти примитивы так, как им нужно.
• Сохраняемое состояние: ^[14] re2c поддерживает как лексеры вытягивающей модели (когда лексер работает без прерываний и извлекает больше входных данных по мере необходимости), так и лексеры выталкивающей модели (когда лексер периодически останавливается и возобновляется для анализа новых блоков ввода).
• Условия запуска: ^[15] re2c может генерировать несколько взаимосвязанных лексеров, каждый из которых запускается определенным условием в программе.
• Самостоятельная проверка: ^[16] re2c имеет специальный режим, в котором он игнорирует весь используемый код интерфейса и генерирует самодостаточную программу- скелет . Кроме того, re2c генерирует два файла: один со входными строками, полученными из обычной грамматики, и один со сжатыми результатами сопоставления, которые используются для проверки поведения лексера на всех входных данных. Входные строки генерируются таким образом, что они широко охватывают переходы и пути DFA. Генерация данных происходит сразу после построения DFA и до любых оптимизаций, но сам лексер полностью оптимизирован, поэтому скелетные программы способны выявлять любые ошибки при оптимизации и генерации кода.
• Предупреждения: ^[17] re2c выполняет статический анализ программы и предупреждает пользователей о возможных недостатках или ошибках, таких как неопределенный поток управления, недостижимый код, неправильно сформированные escape-символы и возможное неправильное использование примитивов интерфейса.
• Отладка. Помимо создания удобочитаемых лексеров, re2c имеет ряд опций, которые сбрасывают различные промежуточные представления сгенерированного лексера, такие как NFA , несколько этапов DFA и результирующий граф программы в формате DOT . ^[18]

Синтаксис [ править ]

Программа re2c может содержать любое количество /*!re2c ... */блоков. Каждый блок состоит из последовательности правил , определений и конфигураций (их можно смешивать, но обычно лучше сначала помещать конфигурации, затем определения, а затем правила). Правила имеют форму REGEXP { CODE }или REGEXP := CODE;где REGEXP- это регулярное выражение и CODEпредставляет собой блок кода C. Когда REGEXPсоответствует входная строка, поток управления передается в связанный CODE. Есть одно специальное правило: правило по умолчанию с *вместо REGEXP; он запускается, если не совпадают другие правила. re2c жадныйсемантика соответствия: если совпадают несколько правил, предпочтительнее правило, соответствующее более длинному префиксу; если конфликтующие правила соответствуют одному и тому же префиксу, более раннее правило имеет приоритет. Определения имеют форму NAME = REGEXP;(а также NAME { REGEXP }в режиме совместимости с Flex ). Конфигурации имеют вид, re2c:CONFIG = VALUE;где CONFIG- имя конкретной конфигурации, а VALUEэто число или строка. Для более продвинутого использования см. Официальное руководство re2c. ^[19]

Регулярные выражения [ править ]

re2c использует следующий синтаксис для регулярных выражений:

• "foo" строковый литерал с учетом регистра
• 'foo' строковый литерал без учета регистра
• [a-xyz], [^a-xyz]класс персонажа (возможно, отрицательный)
• . любой символ кроме новой строки
• R \ S различие классов персонажей
• R* ноль или более случаев R
• R+ одно или несколько вхождений R
• R? необязательный R
• R{n}повторение Rровно nраз
• R{n,}повторение Rхотя бы nраз
• R{n,m}повторение Rот nдо mраз
• (R)просто R; круглые скобки используются для переопределения приоритета или для подчиненного соответствия в стиле POSIX
• R Sконкатенация: Rза которым следуетS
• R | Sальтернатива: RилиS
• R / Slookahead: Rза ним следует S, но Sне потребляется
• nameрегулярное выражение, определенное как name(кроме режима совместимости с Flex )
• @stagАнь з-тег : сохраняет последнюю позицию ввода , при которой @stagсоответствует в переменной с именемstag
• #mtagм-тег : сохраняет все позиции ввода , при котором #mtagматчи в переменной с именемmtag

Классы символов и строковые литералы могут содержать следующие управляющие последовательности: \a, \b, \f, \n, \r, \t, \v, \\, восьмеричной ускользает \oooи шестнадцатеричной ускользает \xhh, \uhhhhи \Uhhhhhhhh.

Пример [ править ]

Вот очень простая программа на re2c (example.re). Он проверяет, что все входные аргументы являются шестнадцатеричными числами. Код для re2c заключен в комментарии /*!re2c ... */, все остальное - простой код на C. См. Более сложные примеры на официальном сайте re2c. ^[20]

#include  <stdio.h>статический  int  lex ( const  char  * YYCURSOR ) {  const  char  * YYMARKER ;  / *! re2c  re2c: define: YYCTYPE = char;  re2c: yyfill: enable = 0; конец = "\ x00";  шестнадцатеричный = "0x" [0-9a-fA-F] +; * {printf ("ошибка \ п"); возврат 1; }  шестнадцатеричный конец {printf ("шестнадцатеричный \ п"); возврат 0; }  * / }int  main ( int  argc ,  char  ** argv ) {  для  ( int  i  =  1 ;  i  <  argc ;  ++ i )  {  lex ( argv [ i ]);  }  return  0 ; }

Учитывая это, re2c -is -o example.c example.reгенерирует приведенный ниже код (example.c). Содержание комментария /*!re2c ... */заменяется детерминированным конечным автоматом, закодированным в форме условных переходов и сравнений; остальная часть программы дословно копируется в выходной файл. Есть несколько вариантов генерации кода; Обычно re2c использует switchоператоры, но может использовать вложенные ifоператоры (как в этом примере с -sопцией) или генерировать растровые изображения и таблицы переходов. Какой вариант лучше, зависит от компилятора C; Пользователям re2c предлагается поэкспериментировать.

/ * Создано re2c 1.2.1 в пятницу 23 августа 21:59:00 2019 * / #include  <stdio.h>статический  int  lex ( const  char  * YYCURSOR ) {  const  char  * YYMARKER ; { char  yych ; yych  =  * YYCURSOR ; если  ( yych  ==  '0' )  goto  yy4 ; ++ YYCURSOR ; гг3 : {  printf ( "ошибка \ п " );  возврат  1 ;  } yy4 : yych  =  * ( YYMARKER  =  ++ YYCURSOR ); если  ( yych  ! =  'x' )  goto  yy3 ; yych =  * ++ YYCURSOR ; если  ( yych  > =  0x01 )  goto  yy8 ; yy6 : YYCURSOR  =  YYMARKER ; goto  yy3 ; yy7 : yych  =  * ++ YYCURSOR ; yy8 : if  ( yych  <=  '@' )  { если  ( yych  <=  0x00 )  goto  yy9 ; если  ( ггч  <=  '/' )  перейти yy6 ; если  ( yych  <=  '9' )  goto  yy7 ; goto  yy6 ; }  else  { если  ( yych  <=  'F' )  goto  yy7 ; если  ( yych  <=  '' ' )  goto  yy6 ; если  ( yych  <=  'f' )  goto  yy7 ; goto  yy6 ; } yy9 : ++ YYCURSOR ; {  printf( "шестнадцатеричный \ п " );  возврат  0 ;  } }}int  main ( int  argc ,  char  ** argv ) {  для  ( int  i  =  1 ;  i  <  argc ;  ++ i )  {  lex ( argv [ i ]);  }  return  0 ; }

См. Также [ править ]

• Сравнение генераторов парсеров

Ссылки [ править ]

Внешние ссылки [ править ]

• Официальный веб-сайт