Вопросы. Грамматика, для которой можно построить таблицу синтаксического анализа, называется LR-грамматикой

LR-грамматики

Грамматика, для которой можно построить таблицу синтаксического анализа, называется LR- грамматикой. Интуитивно, для того чтобы грамматика была LR-грамматикой, достаточно, чтобы ПС-анализатор, читающий поток слева направо, был способен распознавать основы при их появлении в стеке.

LR-анализатор не должен просматривать весь стек, чтобы распознать появление основы на вершине стека; более того, символ состояния на вершине стека содержит всю необходимую информацию. Если можно распознать основу, зная только символы грамматики в стеке, то существует конечный автомат, который в состоянии определить основу на вершине стека путем считывания грамматических символов в стеке сверху вниз. По сути, таким автоматом является функция goto таблицы LR-анализа. Однако автомату также не нужно читать стек при каждом переходе. Символ состояния на вершине стека представляет собой состояние распознающего основы конечного автомата, в котором бы он оказался после считывания грамматических символов в стеке снизу вверх. Следовательно, LR-анализатор может определить по состоянию на вершине стека все, что надо знать о содержимом стека.

Другой источник информации, который используется LR-анализатором для принятия решения о переносе/свертке, — очередные k символов входного потока. Практический интерес представляют случаи k = 0 и k = 1. Грамматика, для разбора которой LR анализатору требуется просмотр до k символов входного потока на каждом шаге, называется LR(k)-грамматикой.

Существует важное отличие между LL- и LR-грамматиками. Для того чтобы грамма­тика представляла собой LR(k)-грамматику, необходимо распознать появление правой части продукции, видя все, что из нее порождено, а также k входных символов. Это требование существенно менее строго, чем требование LL(k)-грамматики, где нужно распознать использование продукции, видя только k первых символов того, что порож­дено ее правой частью. Поэтому LR-грамматики могут описывать больше языков, чем LL-грамматики.

1. Какой алгоритм лежит в основе всех восходящих методов синтаксического анализа?

2. Какие преимущества имеют распознаватели на основе грамматик операторного предшествования перед распознавателями на основе грамматик простого предшествования?

3. Почему любая LL-грамматика является LR-грамматикой?

4. Как определяются отношения предшествования? Какие средства существуют для определения отношений предшествования?

5. Как используются отношения предшествования при выполнении синтаксического анализа?

6. Что является пунктом грамматики? Что показывает тот или иной пункт?

7. В чем особенности LR-технологий, используемых при разработке компиляторов?

8. Сравните рассмотренные методы синтаксического анализа. Отметьте достоинства и недостатки каждого метода.

Дата добавления: 2014-12-27