Восходящий синтаксический анализ

Вопросы

LL(1)-грамматики

Грамматика, таблица анализа которой не имеет множественных записей, называется LL(1). Первое "L" означает просмотр входного потока слева направо, второе "L" — левое порождение, а "1"— просмотр одного символа из входного потока на каждом шаге для принятия решения о дальнейших действиях.

Для некоторых грамматик таблица разбора М может иметь несколько записей в одной ячейке таблицы. Например, если грамматика G — леворекурсивная или неоднозначная, то таблица разбора М будет иметь как минимум одну ячейку с несколькими записями.

LL(1)-грамматики имеют ряд отличительных свойств. Такая грамматика не может быть неоднозначной или леворекурсивной. Можно показать, что грамматика G яв­ляется LL(1)-грамматикой тогда и только тогда, когда для любых двух различных ее продукций А→α | β выполняются следующие условия.

1. Не существует такого терминала а, для которого и α, и β порождают строку, начи­нающуюся c а.

2. Пустую строку может порождать только одна из продукций αили β.

3. Если β=> λ, то а не порождает ни одну строку, начинающуюся с терминала из FOLLOW(A).

Грамматика для арифметических выражений является LL(1)-грамматикой. Грамматика, моделирующая инструкции if-then-else, таковой не яв­ляется.

Если таблица анализа имеет ячейки с несколькими запи­сями, выход состоит в преобразовании грамматики, устраняющем левую рекурсию, и левой факторизации, чтобы получить грамматику, в таблице анализа которой от­сутствуют ячейки с несколькими записями. К сожалению, имеются грамматики, никакие изменения которых не приведут к LL(1)-грамматике. Не существует универсальных правил, с помощью которых ячейки с несколькими записями можно превратить в однозначно определенные без воздействия на язык, распознаваемый синтаксическим анализатором.

Основная сложность в использовании предиктивного анализа состоит в написании для исходного языка такой грамматики, которая позволяет построить предиктивный синтаксический анализатор.

1. На каком алгоритме основана работа распознавателя для LL(1) – распознавателя?

2. Какие преобразования необходимо выполнить с грамматикой, чтобы к ней можно было применить нисходящие методы разбора?

3. Почему распознаватели с возвратами (откатами) назад не нашли широкого применения?

4. Какие грамматики является LL(k)-грамматиками?

5. Как описывается один такт работы LL(1)-анализатора?

Основной метод восходящего синтаксического анализа - синтаксический анализ типа "перенос/свертка" или сокращенно ПС-анализ. В процессе ПС-анализа дерево разбора для входной строки строится начиная с листа (снизу) иработая по направлению к корню дерева (вверх). Этот процесс можно рассматривать как свертку строки w к стартовому символу грамматики. На каждом шаге сверткинекоторая подстрока, соответствующая правой части продукции, заменяется символом из левой части этой продукции, и если на каждом шаге подстроки выбираются корректно, то получается обращенное правое порождение.

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