Это должно быть очевидно из рекурсии по отсутствию переборов глубоко вложенных (рекурсивных) вариантов.
Пример:
УровеньУ:
СлучайУ_1: УровеньУ_1
СлучайУ_2: УровеньУ_2
...
иначе ПолярныйЛис

Требуется, чтобы все возможные направления СлучайУ_1, СлучайУ_2,... и т.д. были сразу же взаимно однозначны и вычислимы суммарно за константное время, т.е. не уходили в рек. перебор.
Можно записать и как:
если СлучайУ_1 то УровеньУ_1
иначе если СлучайУ_2 то УровеньУ_2
...
но суть не меняется - переход к любому случаю за константное время.

Скобочками для всех случаев перебора с углублением.

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

Отредактировано MihalNik (2019-01-03 17:50:28)

Еще раз: запись рабочего кода сопоставима по длине (в зависимости от ЯП м.б. длинее на коэффициэнт). И проверить его можно уже большим кол-вом способов, мало ли что там написано Кнутом (который в языкостроении и не авторитет).
Открываем какую-нибудь грамматику и смотрим:

Это строчка из синтаксиса КП.
В каком-нибудь любимом Лисом Паскале это можно записать как:

Relation_s: R:= S('=') or S('#') or S('<=') or S('<') or S('>=') or S('>') or W('IN') or W('IS');

И это будет работать правильно при соответствующем контексте. И сразу же очевидный порядок: вначале подстановка "<=" и ">=", а потом "<" и ">" соответственно.

Во-первых, для всех распространенных языков как правило уже известно, обладают они определенного класса грамматикой или нет. Во-вторых, нет ничего страшного, если где-то возникнет углубленный перебор, поэтому класс грамматики вообще не особо важен - парсер все равно ее разберет. В-третьих, не трудно и переделать и так, что парсер найдет любые неоднозначности для конкретного кода. Для примера выше это замена жадного оператора 'or' на добавление в список/массив с перебором всех последующих альтернатив независимо от совпадения предыдущих. Так что даже если грамматика допускает неоднозначности - все равно можно грамотно программировать на таком языке, неудовлетворящем фантазиям Кнута, если язык предоставляет механизм исправления любых неоднозначностей, например, скобками.

P.S.:

В анекдоте было 1000 или 1500. 400 - вполне достижимая средняя скорость набора обычных текстов.

Отредактировано MihalNik (2019-01-09 16:21:35)

Сравниваем еще раз - символ грамматики:

и кусок оператора выбора:

Что мешает добавить пояснения к программному коду и зачем тогда п.1 и п.3? А если бы Лис присмотрелся внимательно, то заметил бы, что код законченный, корректный и однозначный с точки зрения рекурсивного спуска.

И чем муторнее сразу написать указанный программный код по сравнению с соответствующей грамматикой?

Отредактировано MihalNik (2019-02-13 19:30:57)

Чуть поправлю. Можно проверить, является ли заданная грамматика LL(k)-грамматикой, является ли LL(1)-грамматикой. И если грамматика получилась LL(1), тогда можно использовать рекурсивный спуск. Вот о чём говорится в цитате. Подразумевается, что если грамматика получилась не LL(1), то нужно её привести к виду LL(1), потому что парсить LL(k) (или более общие) - боль.

Отредактировано atzx (2019-06-22 16:27:10)

Менее магическим, чем предлагает Лис.

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

И снова тот же вопрос: чем способ записи РБНФ понятнее записи кода?

Возвращаемся к #9 и сравниваем - аналогия не раскрыта. Как-то синтаксис Паскаля (в отличии от С) не намного сложнее РБНФ. Да и весь он не нужен (например, можно написать рекурсией без спец. операторов-циклов) и необходимое подмножество сопоставимо с РБНФ. Лис же предлагает решать проблемы однозначности, которых в коде просто не существует - компилятор гарантирует это. Паскаль, который практически все учат в средней школе - по сложности как ассемблер? Серьезно?

Отредактировано MihalNik (2019-02-13 22:05:45)