Языки и трансляции. Мартыненко Б.К. - 165 стр.

UptoLike

ВУЗ: 

СПбГУ | Санкт-Петербург

Составители: 

Рубрика: 

163
Следствие 2.3. Итак, мы имеем два достаточных признака для того, чтобы
считать КС-грамматику не LL-грамматикой. Это — неоднозначность и лево-
рекурсивность.
§ 2.3. k-Предсказывающие алгоритмы анализа
Для класса LL(k)-грамматик существует адекватный класс анализаторов,
называемых k-предсказывающими алгоритмами анализа.
2.3.1. Неформальное описание
Это устройство (рис. 2.1) имеет разбитые на ячейки входную, выходную
ленты и ленту магазина. “Дно” магазина маркируется специальным символом,
например $, который постоянно находится на магазинной ленте. Конечное
устройство управления руководствуется управляющей таблицей, создаваемой
по грамматике, в которой производится синтаксический анализ. Она опреде-
ляет действия в зависимости от k символов, сканируемых единовременно
читающей головкой входной ленты — эта часть входной цепочки называется
аванцепочкой (u), и верхнего символа магазина (X). Заметим, что
u< k только
при y = ε. Этими параметрами определяются движения следующих двух типов:
1. Запись вместо верхнего символа магазина некоторой цепочки магазин-
ных символов и выдача на выходную ленту некоторой цепочки выходных
символов. Выходная головка при этом продвигается к ближайшей свободной
ячейке. В случае использования этого устройства для целей анализа на
выходную ленту записываются номера правил грамматики, образующих
левосторонний анализ входной цепочки, если она принимается. Этот тип
движений не продвигает входную головку.
2. Сброс верхнего символа магазина и продвижение читающей головки
вправо к следующей ячейке входной ленты. Такие движения происходят
только тогда, когда первый символ аванцепочки — такой же, как верхний
символ магазина. При этих движениях на выходную ленту ничего не пишется.
Существует возможность сигнализации о приёме входной цепочки или об
ошибке в ней.
k-Предсказывающий алгоритм анализа напоминает детерминированный
магазинный преобразователь, но отличается от него тем, что “видит” сразу до k
x
Управляющая
таблица
М
а
г
а
з
и
н
Вход:
Выход:
w
u
y
i
X
$
α
π
Рис. 2.1.

Страницы