Таблицы имен при рекурсивном спуске с возвратами

В заметке "Пишем транслятор" я сетовал на ситуации, когда грамматику не впихнуть в LL(n). В частности, это оборачивается необходимостью поддерживать транзакционность (!) добавления имен в таблицы имен.

Например, есть правило типа

p1 -> condition ; statement1
p1 -> condition ; statement11 statement2

statement1 -> statement EOL
statement11 -> statement ;
statement2 -> statement EOL

где EOL - конец строки.

Преобразовать правила в простой LL(1)-разбор по наследственным причинам не представляется возможным (изначально, каждый оператор должен заканчиваться EOL, данный пример - редкое исключение). А было бы очень просто в таком случае:

p1 -> condition ; statement1 EOL
p1 -> condition ; statement1 ; statement2 EOL

С разбором

if ParseStatement1 then
  if EOL then OK
  else if ; then
    if ParseStatement2 then OK

Но в нашем варианте на рекурсивном спуске имеем такую последовательность

if ParseStatement1 then OK
else if ParseStatement11 then
  if ParseStatement2 then OK

Если после неудачного ParseStatement1 следует возврат, все добавленные этим разбором имена должны быть вычищены из таблиц.

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

if ParseStatement1 then
  if ParseStatement2 then OK
  else if ParseStatement3 then OK

Здесь откатить нужно только изменения таблиц в ParseStatement2, не трогая подтвержденные имена, добавленные предшествующим разбором ParseStatement1. Сложность нарастает с глубиной разбора, и бороться с ней приходится все теми же рекурсивными вызовами.

Да, в ситуации изначально правильно спроектированных грамматик такого можно избежать. Поэтому всегда сначала проектируйте грамматику, а потом уже её реализуйте и расширяйте.