Параметр регулярных выражений для разбора вложенных структур

Question

Регулярные выражения - это стандартный инструмент, используемый для синтаксического анализа строк на разных языках. Однако их применимость ограничена. Регулярные выражения могут соответствовать только списку. Невозможно описать произвольные глубокие вложенные структуры с использованием регулярных выражений. Вопрос: что такое технология/структура, которая широко используется/распространена и как стандартная, поскольку регулярные выкупа могут соответствовать древовидным структурам (производить АСТ).

Answer 1

Генераторы Parser, такие как Yacc, Bison и производные, - вот что вам нужно. Они не так широко распространены, как регулярные выражения, потому что они генерируют фактический код C. Есть такие переводы, как Jison, например, которые реализуют синтаксис Yacc/Bison, используя javascript. Я знаю, что есть аналогичные инструменты для других языков.

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

Answer 2

Регулярные выражения описывают конечный автомат.

С конца 1960-х годов «анализ хлеба с маслом» (хотя и не обязательно «современное состояние») был автоматическим способом, созданным генераторами парсера в соответствии с алгоритмами «LR», такими как LALR (1) ,

Соединение с регулярными выражениями: синтаксический анализатор фактически использует правила, очень похожие на регулярные выражения, чтобы распознавать жизнеспособные префиксы. Переходы состояния «сдвига» среди «основных элементов LR (0)» составляют конечный автомат и могут быть описаны регулярным выражением. Рекурсия обрабатывается благодаря семантическому действию нажатия символов на стек при выполнении «сдвигов» и удалении их («сокращение»). Сокращения переписывают часть стека и выполняют «переход» в другое состояние. Этот тип goto вместе с стекем отсутствует в автомате регулярного выражения.

Грамматика выражения выражения также связана с регулярными выражениями. Самостоятельные выражения могут быть наделены рекурсией. Во-первых, мы можем взять куски регулярных выражений и дать им имена, а затем построить большие регулярные выражения, написав выражения, которые вызывают эти имена. (Например, функция найдена в инструменте lex, где вы можете определить именованные выражения, такие как letters [A-Za-z]+, и ссылаться на него позже как {letters}. Теперь предположим, что вы разрешаете круговые ссылки, например letters [A-Za-z]{letters}?. Теперь у вас есть рекурсия, единственная проблема заключается в настройке модели для того, чтобы осуществить это.

реализации так называемых «регулярных выражений» в различных современных языков и сред в том, поддержка рекурсии. Perl-совместимые регулярные выражения (PCRE) поддерживают его, например.

выражения, которые рекурсия функций или обратная связь не обрабатываются классическим маршрутом компиляции NFA (возможно, преобразованным в DFA), они не могут быть.

Как описано выше, рекурсия может быть обработана с фактической рекурсией. Оператор ? может быть реализован как функция, которая пытается сопоставить свой соответствующий объект аргумента. Если он преуспеет, он потребляет все, что он сопоставил, иначе он ничего не потребляет. То есть, регулярное выражение может быть преобразовано в дерево синтаксиса и интерпретировано как «как есть», а не скомпилировано на конечный автомат (или тривиально скомпилировано для функций, соответствующих узлам дерева), и такая интерпретация, естественно, может обрабатывать рекурсии. Таким образом, интерпретация представляет собой эффективный синтаксический рекурсивный спускающий парсер. (Обратите внимание, как я избегал левой рекурсии при определении letters, чтобы этот пример был совместим с этим подходом).

Пример: скобка сопоставления регулярное выражение:

par-match := ({par-match})| 

Это компилируется к дереву:

   branch-op <-- "par-match" name points at this node 
      / \ 
    catenate-op  <empty> 
    / \ 
    "("  catenate-op 
      /  \   
      {par-match} ")" 

Это может затем преобразуется в метод рекурсивного спуска, или интерпретируемым непосредственно.

Соответствие шаблону начинается с вызова «ветви-операции» верхнего уровня. Этот оператор просто пытается использовать все альтернативы. Предположим, что вход пуст. Тогда левая альтернатива потерпит неудачу: она требует открытой круглой скобки. Итак, правильная альтернатива будет успешной: пустые совпадения пустые. (Операторы либо «сбой», либо указывают «успех» и потребляют вход.)

Но предположим, что ваш вход (()). Левый catenate-op, в свою очередь, вызывается его левым поддеревом, которое соответствует и потребляет левую круглую скобку, оставляя ()). Затем он вызовет его правое поддерево, другое catenate-op. Этот catenate-op соответствует левому поддереву, которое вызывает рекурсию на верхний уровень с помощью названных ссылок par-match. Эта рекурсия будет соответствовать и потреблять (), оставив ). Затем catenate-op вызывает свое правое поддерево, которое соответствует ). Контроль возвращается до branch-op. (Хотя в левой части branch-op согласованного то, branch-op надо еще попробовать другой альтернативы, более чем одна ветвь может соответствовать, и некоторые из них могут соответствовать больше, чем другие.)

Это тесно связано с Parsing Expression Grammars работы.

Практически говоря, рекурсивное определение может быть каким-то образом закодировано в синтаксисе регулярного выражения. Скажем, мы придумываем какой-то новый оператор, как (?name:definition), что означает «матч definition который могут содержать вызовы самого себя через name. Синтаксис вызова может быть (*name), так что мы можем написать par-match пример, как (?par-match:\((*par-match)\)|). Комбинации (? и (* являются недопустимыми в соответствии с «классический» синтаксис регулярных выражений и поэтому мы можем использовать их для расширения.

В качестве окончательного примечания регулярные выражения соответствуют грамматикам. Это фундаментальное соединение между регулярными выражениями и синтаксическим разборами. То есть, регулярные выражения соответствуют определенному подмножеству грамматики описывают только обычные языки. Пример грамматики, которая описывает правильный язык:

S -> A | B 
B -> b 
A -> A a | c 

Хотя есть рекурсия A -> A ..., это по-прежнему является регулярным и соответствует регулярному выражению ac*|b, что является более компактным способом для обозначения одного и того же языка. Грамматика позволяет нам обозначать языки, которые не являются регулярными и для которых мы не можем писать регулярное выражение, но, как мы видели, мы можем расширить обозначение и семантику регулярных выражений, чтобы выразить некоторые из этих вещей. Регулярные выражения не отделены от грамматик. Эти два не являются аналогами, а скорее являются особым случаем или подмножеством другого.