Доказать корректность приведенной выше нерекурсивной программы непосредственно, без ссылок на рекурсивную.

Решение. Рассмотрим наибольшее начало входа, являющееся K‑началом. Оно представляется в виде конкатенации (последовательного приписывания) нескольких непустых L‑слов и, возможно, одного непустого L‑начала, не являющегося L‑словом. Инвариант цикла: прочитано несколько из них; b <=> (последнее прочитанное является L‑словом).

Сохранение инварианта: если осталось последнее слово, это очевидно; если осталось несколько, то за первым B‑словом (из числа оставшихся) идет символ из Нач(B), и потому это слово —максимальным началом входа, являющееся B‑началом.

На практике при записи грамматики используют сокращения.

Если правила для какого-то нетерминала K имеют вид

K -> L K

K ->

(т.е. K‑слова —это последовательности L‑слов), то этих правил не пишут, а вместо K пишут L в фигурных скобках. Несколько правил с одной левой частью и разными правыми записывают как одно правило, разделяя альтернативные правые части вертикальной чертой.

Например, рассмотренная выше грамматика для <выр> может быть записана так:

<выр> ‑> <слаг> { + <слаг> } <слаг> ‑> <множ> { * <множ> } <множ> ‑> x | ( <выр> )

5.4.8. Написать процедуру, корректно для <выр>, следуя этой грамматике и используя цикл вместо рекурсии, где можно.