Используются ли регулярные выражения для создания парсеров?

Question

Это просто вопрос из любопытства, так как в последнее время мне нужно было все больше и больше разбирать и использовать регулярные выражения ... кажется, что на вопросы, с которыми я сталкиваюсь в своих поисках относительно какого-либо анализа, кто-то всегда заканчиваетговоря, когда его спросили о чем-то, относящемся к регулярному выражению, «регулярное выражение не годится для этого, вместо этого используйте такой-то и такой-то синтаксический анализатор» ... так как я пришел к лучшему пониманию регулярного выражения, я думаю, что большинство вещей возможно, только его довольно сложно и времяпотребляя, так как вам приходится учитывать множество различных возможностей, и, конечно, его необходимо комбинировать с условными операторами и циклами для создания любого вида синтаксического анализатора ... поэтому мне интересно, является ли регулярное выражение тем, что используется для создания большинства синтаксических анализаторов или являетсятам используется какой-то другой метод ... Мне просто интересно, так как у меня может возникнуть необходимость создать довольно сложные пользовательские парсеры, которые не обязательно должны существовать.

спасибо за любую информацию, так какЯ не могу найти прямой ответ на это.

Answer 1

Нет, парсеры построены из грамматик .

Но большинство компиляторов (интерпретаторов) используют отдельный сканер (лексер) для распознавания входных токенов.Сканер может быть задан с регулярными выражениями, но на самом деле они не построены с использованием обычных классов библиотеки RegEx.

Практический подход - отдельный сканер.Можно определить полные грамматики вплоть до уровня персонажа, но это нецелесообразно.Регулярные выражения легче обрабатывают подмножество конечных точек грамматик.

Для справки см. Yacc и Lex .У них обоих есть современные преемники.

Answer 2

Как правило, вы будете использовать два (как минимум) типа инструментов при создании вашего парсера.

Первая часть - это лексический анализ - разделение символов на токены и фильтрация комментариев и пробелов. Эта часть обычно выполняется с помощью регулярных выражений. Что ж, это еще более типично делается с помощью генератора сканера, который преобразует набор пар регулярных выражений и кода в программу, которая выполняет соответствующий код, когда распознает регулярные выражения. Это оказывается более эффективным, чем тестирование каждого регулярного выражения каждый раз, и это также работает лучше по ряду других причин. FLEX является распространенным инструментом для этого в C.

Вторая часть вашего парсера - это грамматика. Наиболее типичным инструментом для этого является другой генератор программ, который принимает не зависящую от контекста грамматику (CFG), аннотированную правилами интерпретации составляющих «частей речи». CFG может выражать такие вещи, как сбалансированные круглые скобки, чего не может регулярное выражение (если оно не было расширено с помощью функций CF, что делает его не совсем «регулярным» в математическом смысле). Но CFG с правилами очень хорош, потому что вы можете придать смысловой смысл структуре слов вашего языка. ЗУБР является распространенным инструментом для этой части в C.

Но я на самом деле сказал тебе небольшую ложь. Видите ли, у каждого реального языка программирования есть части, которые не могут быть выражены в контексте без контекста. Например, вам нужно связать определение переменной с ее использованием, чтобы вы знали, какие инструкции нужно сгенерировать, а также, если операция над ней является допустимой. Обычно это рассматривается вне рамок синтаксического анализа, но есть такие вещи, как «грамматики атрибутов», которые похожи на CFG, расширенные функциями, которые могут значительно облегчить кодирование и работу даже с этими зависимостями контекста.

Теперь нет правила, согласно которому вы ДОЛЖНЫ использовать такие инструменты. Многие простые грамматики достаточно легко обрабатываются с помощью рукописных инструментов. Например, S-выражения LISP можно просто отсканировать как:

Если оно начинается с цифры, прочитайте число. Если это начинается с буквы, прочитайте символ. Если это пробел, пропустите его. Если это открытый парен, то пропустите его, повторите эту процедуру для значения и ожидайте близкого парена.

Ну, есть еще несколько сложностей для строк и что с тобой, но это основная идея. Разбор FORTH еще проще, потому что он не создает рекурсивную структуру данных.

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

Answer 3

Регулярные выражения определены над произвольными токенами, но большинство программистов сталкиваются с ними только в контексте строк символов, и поэтому легко поверить, что они полезны только для строк.

Как чистая возможность, регулярные выражения (фактически, single регулярное выражение) не могут анализировать любой язык, который требует контекстно-свободной грамматики.

Что делает контекстно-свободные грамматики отличными от регулярных выражений, так это то, что вы можете определить большой набор именованных «распознавателей» подграммеров языка, которые могут рекурсивно ссылаться друг на друга. Эти правила все может быть ограничено только простой формой:

 LHS =  RHS1 RHS2 ... RHSn ;

(так называемая «форма Бэкуса-Наура» или BNF), где каждый LHS и RHSi являются именами примитивных элементов языка или нетерминалами в языке. (Я создаю очень сложный инструмент обработки языка, который использует просто эту форму; вам нужно больше правил, но он очень удобен в использовании).

Но большинство людей, пишущих грамматики, хотят более выразительной формы и поэтому используют «расширенный BNF». Если вы внимательно изучите эти EBNF, то, как правило, они добавляют идеи из регулярных выражений (чередование, kleene star / plus) в БНФ формализм. Таким образом, вы можете найти EBNF с "*" и "+".

Итак, далее следует EBNF для себя, используя идеи регулярных выражений:

 EBNF = RULE+ ;
 RULE = IDENTIFIER '=' ALTERNATIVES ';' ;
 ALTERNATIVES = RHS ( '|' RHS )* ;
 RHS = ITEM* ;
 ITEM = IDENTIFIER | QUOTEDTOKEN | '(' ALTERNATIVES ')' | ITEM ( '*' | '+' ) ;

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

Answer 4

Регулярные выражения могут использоваться для анализа определенного класса языка (конечного государственного языка), но их мощность ограничена по сравнению с другими формализмами, и, как вы упоминаете, они быстро становятся непривлекательными и их трудно поддерживать.

Например, невозможно иметь регулярное выражение, которое может гарантировать для каждой открытой скобки наличие соответствующей закрывающей скобки - то, что большинство языков имеют в своем синтаксисе выражений.

Регулярные выражения обычно используются для выполнения токенизации, а затем токены объединяются для создания желаемого синтаксиса.

Answer 5

Ну, создание парсера довольно сложно, и вы можете использовать регулярные выражения, но это не единственное, что вы используете.Я предлагаю прочитать Книгу Дракона

В наши дни, на мой взгляд, вы должны использовать генератор парсеров, потому что вы можете сделать это с нуля, но это не просто и не быстро.Вы должны рассмотреть, вообще говоря, регулярное выражение и конечные автоматы для лексического анализа;контекстно-свободные грамматики, анализаторы LL, анализаторы снизу вверх и анализаторы LR для анализа синтаксиса и т. д. и т. д. ...

Answer 6

(Большинство) парсеры созданы для рекурсивных языков, т.е. языки, которые имеют рекурсивные особенности. RegExps не может обрабатывать рекурсивность, поэтому они не используются для построения синтаксического анализатора (без дополнительных хаков а-ля Perl Markdown). Однако RegExps используются для разработки лексеров, так как они значительно облегчают жизнь.

Answer 7

Регулярное выражение, как вы знаете, это особая нотация для создания детерминированных конечных автоматов .DFA - это устройство синтаксического анализа, и поэтому регулярные выражения выполняют синтаксический анализ.Когда вы используете регулярные выражения для сопоставления чего-либо, вы анализируете строку, чтобы выровнять ее с шаблоном.Когда вы используете регулярные выражения для разбиения чего-либо на части с круглыми скобками, вы анализируете.

DFA формально определяются как синтаксические анализаторы для определенной категории языков, называемых «обычные языки» (спасибо Gumbo за напоминание).Многие важные задачи не связаны с обычными языками.

Таким образом, DFA не являются хорошим подходом ко многим проблемам синтаксического анализа.Самые известные примеры здесь - это XML и HTML.Есть много причин, но я укажу одну.Эти вещи в основном являются древовидными структурами.Чтобы разобрать их, программа должна поддерживать состояние при спуске по дереву.Регулярные выражения не делают этого.

Парсеры, определенные грамматикой (такие как LR (k) и LL (k)), делают это, парсеры с кодированием сверху вниз делают это.

Существуют книги и книги по различным альтернативным технологиям синтаксического анализа, которые обычно применяются для анализа таких вещей, как C ++ или XML.

Answer 8

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

Если вы хотите создать свои собственные парсеры, вам, вероятно, лучше взглянуть на что-то вроде Bison , чтобы помочь с этим.