Отрицательный взгляд вперед в алгоритме синтаксического анализа LR

Рассмотрим такое правило в грамматике для генератора синтаксического анализа семейства LR (например, YACC, BISON и т. д.):

Nonterminal : [ lookahead not in {Terminal1, ..., TerminalN} ] Rule ;

Это обычное правило, за исключением того, что оно имеет ограничение: фраза, созданная с помощью этого правила, не может начинаться с Terminal1, ..., TerminalN. (Конечно, это правило можно заменить набором обычных правил, но это приведет к увеличению грамматики). Это может быть полезно для разрешения конфликтов.

Вопрос в том, существует ли модификация алгоритма построения LR-таблицы, допускающая такие ограничения? Мне кажется, что такая модификация возможна (как и отношения предшествования).

Конечно, это можно проверить во время выполнения, но я имею в виду проверку во время компиляции (проверка, которая выполняется при построении таблицы синтаксического анализа, как директивы %prec, %left, %right и %nonassoc в генераторах, совместимых с yacc.)


conflict parsing generator resolve negative-lookahead
person skvadrik    schedule 20.04.2013    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Я не понимаю, почему это не должно быть возможно, но я также не вижу никакой очевидной причины, по которой это было бы полезно. Вы имеете в виду пример?

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

Базовое преобразование, с небольшим маханием руками:

Для любого производства с терминальными ограничениями:

  • Если производство начинается с необнуляемого нетерминала, замените нетерминал версией с ограничением терминала.

  • Если производство начинается с терминала в списке ограничений терминала, удалите производство

  • Если производство начинается с терминала, не включенного в список ограничений терминала, никаких изменений не требуется.

Если производство начинается с нулевого нетерминала, вы должны создать две версии нулевого нетерминала, одна из которых всегда нулевая, а другая не может быть нулевой; а затем создать две версии продукта, начиная с каждого из новых нетерминалов. Затем примените приведенные выше преобразования, но интерпретация «начинается с» означает «начинается с после любых всегда нулевых нетерминалов».

На самом деле вам не нужно изменять грамматику, так как приведенные выше преобразования могут быть выполнены на лету во время построения базовой машины SLR, по крайней мере, для конструкций LR(0) и LALR(1).

person rici    schedule 21.04.2013
comment
Спасибо за Ваш ответ! Да, я имею в виду пример, это грамматика ECMA-262 (ecma-international.org /ecma-262/5.1, например раздел 12.4). Поскольку эта грамматика использует производство Expression как с ограничениями, так и без них, мы должны удвоить ту грамматическую часть, которая описывает Experssion. В моем генераторе парсеров LALR(1) это приводит к гораздо большему количеству состояний (350 против 470). Было бы очень неплохо сохранить 350 штатов и удовлетворить ограничения. - person skvadrik; 21.04.2013