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

Ответ 1

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

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

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

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

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

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

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

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

Ответ 2

Нет, парсеры построены из grammars.

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

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

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

Ответ 3

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

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

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

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

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

Ответ 4

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

Ответ 5

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

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

Ответ 6

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

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

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

Ответ 7

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

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

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

 LHS =  RHS1 RHS2 ... RHSn ;

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

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

Итак, что следует за EBNF для себя, используя идеи regexp:

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

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

Ответ 8

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

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