Регулярные выражения используются для создания синтаксических анализаторов?
Это - просто вопрос из любопытства, так как я должен был добраться все больше в парсинг и использование regex в последнее время.. это кажется для вопросов, с которыми я сталкиваюсь в своих поисках относительно какого-то парсинга, кто-то всегда заканчивает тем, что говорил при выяснении у чего-то касающегося regex "regex не хорош для этого, используйте такой и такой синтаксический анализатор вместо этого"..., когда я приехал для лучше понимания regex, я думаю, что большая часть материала возможна, просто его довольно сложное и трудоемкое, так как необходимо объяснить много различных возможностей, и конечно, это должно быть объединено с условными операторами и циклами для создания любого вида синтаксического анализатора.. таким образом, я задаюсь вопросом, является ли regex тем, что используется для создания большинства синтаксических анализаторов или является там некоторым другим используемым методом.. Я просто задаюсь вопросом, так как у меня может быть потребность создать некоторые довольно сложные пользовательские синтаксические анализаторы, подходящие, где существует не обязательно существующий для использования.
спасибо за любую информацию, поскольку я, может казаться, не нахожу прямой ответ на это.
8 ответов
Как правило, вы будете использовать два (по крайней мере) типа инструментов при создании вашего синтаксического анализатора.
Первая часть - это лексический анализ - разделение символов на токены и фильтрация комментариев и пробелов. Эта часть обычно выполняется с помощью регулярных выражений.Что ж, еще чаще это делается с помощью генератора сканера, который преобразует набор пар регулярных выражений и кода в программу, которая выполняет соответствующий код, когда распознает регулярные выражения. Это оказывается более эффективным, чем проверка каждого регулярного выражения каждый раз, а также работает лучше по ряду других причин. FLEX - это обычный инструмент для этого в C.
Вторая часть вашего синтаксического анализатора - это грамматика. Наиболее типичным инструментом для этого является другой программный генератор, который принимает контекстно-свободную грамматику (CFG), аннотированную правилами интерпретации составляющих «частей речи», так сказать. CFG может выражать такие вещи, как сбалансированные круглые скобки, чего не может регулярное выражение (если оно не было расширено функциями CF, что делает его не строго «регулярным» в математическом смысле). Но CFG с правилами очень хорош, потому что вы можете придать семантическое значение фразовой структуре вашего языка. Зубр - обычный инструмент для этой части в C.
Но на самом деле я сказал вам небольшую ложь. Видите ли, в каждом реальном языке программирования есть части, которые нельзя выразить в контекстно-независимой структуре. Например, вам нужно связать определение переменной с ее использованием, чтобы вы знали, какие инструкции нужно сгенерировать, а также допустимость операции с ней. Обычно это считается выходящим за рамки синтаксического анализа, но есть такие вещи, как «грамматики атрибутов», которые похожи на CFG, расширенные функциями, которые могут значительно упростить кодирование и работу с этими зависимостями от контекста.
Итак, нет правила, которое гласит, что вы ДОЛЖНЫ использовать такие инструменты.Многие простые грамматики достаточно легко обрабатывать с помощью рукописных инструментов. Например, S-выражения LISP можно просто сканировать как:
Если оно начинается с цифры, прочтите число. Если он начинается с буквы, прочтите символ. Если это пробел, пропустите его. Если это открытый парен, то пропустите его, выполните рекурсию этой подпрограммы для значения и ожидайте закрытого парена.
Что ж, есть еще несколько сложностей для струнных и прочего, но это основная идея. Анализ FORTH еще проще, потому что он не строит рекурсивную структуру данных.
В любом случае, это должно подтолкнуть вас к тому, чем вы занимаетесь.
Нет, синтаксические анализаторы построены на основе грамматик .
Но большинство компиляторов (интерпретаторов) будут использовать отдельный сканер (лексер) для распознавания входных токенов. Сканер можно указать с помощью регулярных выражений, но, как правило, они не создаются с использованием обычных библиотечных классов RegEx.
Отдельный сканер - практический подход. Можно определить полную грамматику вплоть до уровня персонажа, но это непрактично. Регулярные выражения легче обрабатывают конечное подмножество грамматик.
Для справки см. Якк и Лекс . У них обоих есть современные преемники.
Регулярные выражения определены для произвольных токенов, но большинство программистов сталкиваются с ними только в контексте строк символов, и поэтому легко поверить, что они полезны только для строк.
Как чистая возможность, регулярные выражения (фактически, одиночное регулярное выражение) не могут анализировать любой язык, для которого требуется контекстно-свободная грамматика.
Что отличает контекстно-свободные грамматики от регулярных выражений, так это то, что вы можете определить большой набор именованных «распознавателей» субграмматик языка, которые могут рекурсивно ссылаться друг на друга. Эти правила все могут быть ограничены простой формой:
LHS = RHS1 RHS2 ... RHSn ;
(так назовите «форму Backus Naur» или BNF), где каждая LHS и RHSi являются именами примитивных языковых элементов или нетерминалов в языке. (Я создаю очень сложный инструмент обработки языка, который использует только эту форму; вам нужно больше правил, но она очень удобна).
Но большинство людей, пишущих грамматики, хотят более выразительной формы и поэтому используют «расширенный BNF». Если вы внимательно изучите эти EBNF, они обычно добавляют идеи из регулярных выражений (чередование, звезда клини / плюс) к формализму БНФ. Таким образом, вы можете найти EBNF со знаком «*» и «+».
Итак, далее следует EBNF для себя, использующий идеи регулярных выражений:
EBNF = RULE+ ;
RULE = IDENTIFIER '=' ALTERNATIVES ';' ;
ALTERNATIVES = RHS ( '|' RHS )* ;
RHS = ITEM* ;
ITEM = IDENTIFIER | QUOTEDTOKEN | '(' ALTERNATIVES ')' | ITEM ( '*' | '+' ) ;
Итак, идеи регулярных выражений могут использоваться для выражения грамматик. Генератор синтаксического анализатора, который принимает такую нотацию (в том числе вы делаете это вручную), необходим для создания синтаксического анализатора из экземпляра грамматики.
Что ж, создание синтаксического анализатора довольно сложно, и вы можете использовать регулярное выражение, но это не единственное, что вы используете.Я предлагаю прочитать Dragon Book
. В наши дни, на мой взгляд, вам следует использовать генератор парсеров, потому что вы можете сделать это с нуля, но это не просто и не быстро. Вы должны рассматривать, вообще говоря, регулярные выражения и конечные автоматы для лексического анализа; контекстно-свободные грамматики, парсеры LL, восходящие парсеры и парсеры LR для синтаксического анализа и т. д. и т. д.
Регулярные выражения можно использовать для синтаксического анализа определенного класса языка (язык с конечным числом состояний), но их возможности ограничены по сравнению с другими формализмами, и, как вы упомянули, они быстро становятся неудобными и трудными в обслуживании. .
Например, невозможно иметь регулярное выражение, которое могло бы гарантировать для каждой открытой круглой скобки наличие соответствующей закрывающей скобки - то, что есть в синтаксисе выражения большинства языков.
Регулярные выражения обычно используются для токенизации, а затем токены объединяются для создания желаемого синтаксиса.
(Большинство) парсеров созданы для рекурсивных языков, т.е. языки с рекурсивными функциями. RegExps не справляется с рекурсивностью, поэтому они не используются для создания синтаксического анализатора (без дополнительных приемов, таких как Perl Markdown). Однако регулярные выражения используются для разработки лексеров, так как таким образом они значительно облегчают жизнь.
«Регулярное выражение», как вы его знаете, представляет собой особую нотацию для создания детерминированных конечных автоматов . DFA - это устройство синтаксического анализа, поэтому регулярные выражения выполняют синтаксический анализ. Когда вы используете регулярные выражения для сопоставления чего-либо, вы анализируете строку, чтобы выровнять ее с шаблоном. Когда вы используете регулярные выражения для разбиения чего-либо на части в круглых скобках, вы выполняете синтаксический анализ.
DFA формально определяются как парсеры для определенной категории языков, называемых «обычными языками» (спасибо Гамбо за напоминание). Многие важные задачи не связаны с обычными языками.
Таким образом, DFA не подходят для решения многих проблем синтаксического анализа. Самыми известными примерами здесь являются XML и HTML. Причин много, но я укажу одну. По сути, это древовидные структуры. Чтобы проанализировать их, программа должна поддерживать состояние при спуске по дереву. Регулярные выражения этого не делают.
Синтаксические анализаторы, определенные грамматикой (например, LR (k) и LL (k)), делают это, синтаксические анализаторы с нисходящим кодированием вручную делают это.
Существуют книги и книги по различным альтернативным технологиям синтаксического анализа, которые обычно применяются для синтаксического анализа таких вещей, как C ++ или XML.
Обычно вы используете своего рода сопоставление с образцом (не обязательно регулярные выражения) в лексере, чтобы превратить ваш поток символов в поток токенов, и ваш синтаксический анализатор просматривает эти токены вместо необработанного ввода символа.
Если вы хотите создать свои собственные синтаксические анализаторы, вам, вероятно, лучше обратиться к чему-нибудь вроде Bison , чтобы помочь с этим.