Легче ли написать синтаксический анализатор с рекурсивным спуском, используя EBNF или BNF?

Ни один из них не сложнее другого. Это действительно разница между реализацией чего-либо итеративно и рекурсивно. В BNF все рекурсивно. В EBNF часть рекурсии выражается итеративно. Есть разные варианты синтаксиса EBNF, поэтому я просто буду использовать английский ... «ноль или более» - это простой цикл while, как вы обнаружили. «Один или несколько» означает «один или несколько», за которым следует «ноль или более». «Ноль или один раз» - это простое выражение «если». Это должно охватывать большинство случаев.

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

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

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

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

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

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

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

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

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