Проще ли написать синтаксический анализатор с рекурсивным спуском, используя EBNF или BNF?
У меня есть BNF и EBNF для грамматики. БНФ явно более многословен. У меня есть довольно хорошая идея относительно использования BNF для создания синтаксического анализатора с рекурсивным спуском; Есть много ресурсов для этого. У меня проблемы с поиском ресурсов для преобразования EBNF в синтаксический анализатор с рекурсивным спуском. Это потому, что это сложнее? Из моих уроков теории CS я вспоминаю, что мы изучили EBNF, но не стали преобразовывать их в синтаксический анализатор с рекурсивным спуском. Мы перешли к преобразованию BNF в парсер рекурсивного спуска.
Причина, по которой я спрашиваю, заключается в том, что EBNF более компактен.
Из рассмотрения EBNF в целом, я заметил, что условия, заключенные между { а также } может быть преобразован в while петля. Есть ли какие-либо другие руководящие принципы или правила?
3 ответа
Ни один не сложнее, чем другие. Это действительно разница между итеративной реализацией и рекурсивной реализацией. В БНФ все рекурсивно. В EBNF часть рекурсии выражается итеративно. Существуют разные вариации в синтаксисе EBNF, поэтому я просто буду использовать английский... "ноль или более" - это простой цикл while, как вы обнаружили. "Один или несколько" - это то же самое, что и "0 или более". "Ноль или один раз" - это простое утверждение if. Это должно охватывать большинство случаев.
Вы должны исследовать так называемые метакомпиляторы, которые по существу компилируют EBNF в парсеры рекурсивного спуска. Как они это делают - именно ответ на ваш вопрос. (Это довольно просто, но хорошо, чтобы понять детали).
Действительно замечательная статья - это статья MetaII Вала Шорре. Это технология метакомпилятора, созданная в 1964 году. На 10 страницах он показывает, как создать метакомпилятор, и предоставляет не только это, но и другой компилятор, а также вывод обоих! Есть удивительный момент, когда вы тоже приходите, если собираетесь создать один из них, где вы поняли, как мета-компилятор компилирует себя, используя свою собственную грамматику. Этот момент заставил меня зацепить компилятор примерно в 1970 году, когда я впервые споткнулся о эту статью. Это одна из тех статей по информатике, которую должен прочитать каждый в сфере программного обеспечения.
Джеймс Сосед (изобретатель термина "домен" в разработке программного обеспечения и создатель первой системы трансформации программ [на основе этих метакомпиляторов) предлагает отличное онлайн- руководство по MetaII для тех из вас, кто не хочет делать это опыт с нуля. (Я не имею к этому никакого отношения, за исключением того, что мы с соседями были студентами вместе).
Оба способа являются отличным способом узнать о метакомпиляторах и генерировать парсеры из EBNF.
Ключевые идеи заключаются в том, что левая часть правила создает функцию, которая анализирует этот нетерминал и возвращает true, если совпадение, и продвигает входной поток; false, если совпадения нет и входной поток не продвигается. Содержание функции определяется по правой стороне. Буквальные токены сопоставляются напрямую. Нетерминалы вызывают вызовы других функций, сгенерированных для других правил. Kleene * отображается на циклы while, чередования отображаются на условные ветви. Что не решает EBNF, как это делают метакомпиляторы, так это то, как синтаксический анализ делает что-либо, кроме как сказать "соответствует" или нет? Секрет в том, как ткать выходные операции в EBNF. Бумага MetaII проясняет все это.
Ранние мета-компиляторы META II и TREEMETA и их род не совсем рекурсивный приличный парсер. Они были заявлены как использующие рекурсивные функции. Это просто означало, что они могут называть себя.
Мы не называем C рекурсивным языком. Функция A C или C++ рекурсивна так же, как и ранние мета-компиляторы.
Рекурсия может быть использована. Это были языки программирования. Как правило, рекурсия используется только при анализе языковых конструкций. Например, выражение в скобках и блоки в следующем.
Больше рекурсивной приличной комбинации LR. CWIC, последний документально подтвержденный, имеет расширенные функции отслеживания и отслеживания. Оператор "-" может соответствовать любой языковой конструкции. И инвертирует это успех или неудачу. -термин терпит неудачу, если термин соответствует, например. Ввод никогда не продвигается. '?' смотрит в будущее и соответствует любой языковой конструкции. Например, expr попытается проанализировать expr. Взгляд в будущее совпавшая конструкция не сохраняется или является расширенной.