Проще ли написать анализатор с рекурсивным спуском, используя EBNF или BNF?

Question

У меня есть BNF и EBNF для грамматики. БНФ явно более многословен. У меня есть довольно хорошая идея относительно использования BNF для создания синтаксического анализатора с рекурсивным спуском; Есть много ресурсов для этого. У меня возникают проблемы с поиском ресурсов для преобразования EBNF в синтаксический анализатор с рекурсивным спуском. Это потому что это сложнее? Из моих уроков теории CS я вспоминаю, что мы изучили EBNF, но мы не стали преобразовывать их в парсер рекурсивного спуска. Мы сделали пересмотрели преобразование BNF в парсер рекурсивного спуска.

Причина, по которой я спрашиваю, заключается в том, что EBNF более компактен.

Из рассмотрения EBNF в целом я замечаю, что термины, заключенные между { и }, можно преобразовать в цикл while. Существуют ли какие-либо другие руководящие принципы или правила?

Answer 1

Вам следует исследовать так называемые метакомпиляторы , которые по существу компилируют EBNF в парсеры рекурсивного спуска. Как они это делают - именно ответ на ваш вопрос. (Это довольно просто, но хорошо, чтобы понять детали).

Действительно замечательная статья - это статья MetaII Вала Шорре. Это технология метакомпилятора, созданная в 1964 году. На 10 страницах он показывает, как создать метакомпилятор, и предоставляет не только это, но и еще один компилятор и вывод обоих !. Есть удивительный момент, когда вы тоже приходите, если собираетесь создать один из них, когда вы поняли, как мета-компилятор компилирует себя, используя свою собственную грамматику. Этот момент меня достал подключил компилятор примерно в 1970 году, когда я впервые споткнулся о эту статью. Это одна из тех статей по информатике, которую каждый в бизнесе программного обеспечения должен прочитать.

Джеймс Сосед (изобретатель термина «домен» в разработке программного обеспечения и создатель первой системы преобразования программ [на основе этих метакомпиляторов]) предлагает замечательное онлайновое руководство по MetaII для тех, не хочу делать это с нуля. (Я не имею к этому никакого отношения, за исключением того, что мы с соседями были студентами вместе).

Оба способа - прекрасный способ узнать о метакомпиляторах и генерировать парсеры из EBNF.

Ключевые идеи заключаются в том, что левая часть правила создает функцию, которая анализирует этот нетерминал и возвращает true, если совпадение, и продвигает входной поток; false, если совпадения нет и входной поток не продвигается. Содержание функции определяется по правой стороне. Буквальные токены сопоставляются напрямую. Нетерминалы вызывают вызовы других функций, сгенерированных для других правил. Kleene * отображается на циклы while, чередования отображаются на условные ветви. На что ЕБНФ не обращается, и метакомпиляторы делают, как синтаксический анализ делает что-либо кроме того, чтобы сказать "совпал" или нет? Секрет в том, как ткать выходные операции в EBNF. Бумага MetaII делает все это кристально чистым.

Answer 2

Ни один не сложнее, чем другие. Это действительно разница между итеративной реализацией и рекурсивной реализацией. В БНФ все рекурсивно. В EBNF часть рекурсии выражается итеративно. Существуют различные вариации в синтаксисе EBNF, поэтому я просто буду использовать английский ... "ноль или более" - это простой цикл while, как вы обнаружили. «Один или несколько» - это то же самое, что и «0 или более». «Ноль или один раз» - это простое утверждение if. Это должно охватывать большинство случаев.

Answer 3

Ранние мета-компиляторы META II и TREEMETA и их род не совсем рекурсивный приличный парсер. Они были заявлены как использующие рекурсивные функции. Это просто означало, что они могут называть себя.

Мы не называем C рекурсивным языком. Функция C или C ++ рекурсивна так же, как ранние мета-компиляторы рекурсивны.

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

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