CONSCOMP (Материалы к контрольным работам), страница 9

сентенциальной формы.

s s s

/ | \ / | \

x1 x2... x1 x2...

/ / |

........... .............

/ / |

y y |

/|\ /|\ z

/ ... / ... /|\

a..........$ a...........$ a........b.......$

а) б) в)

Рис. 3.1

На рис. 3.2 приведена структура предсказывающего анализатора,

который определяет очередное правило из таблицы. Такую таблицу

множно построить непосредственно из грамматики.

+---------------+

Вход | a | + | b | $ |

+---------------+

^

|

+-+ +----------------------+

|x| | Программа предсказы- | Выход

Магазин |-|<---| вающего анализатора |--->

|y| +----------------------+

|z| |

|-| v

|$| +---------------------+

+-+ | Таблица анализатора |

+---------------------+

Рис. 3.2

Таблично-управляемый предсказывающий анализатор имеет входной

буфер, таблицу анализа и выход. Входной буфер содержит

распознаваемую строку, за которой следует $ - правый концевой

маркер, признак конца строки. Магазин содержит

последовательность символов грамматики с $ на дне. Вначале

магазин содержит начальный символ грамматики на верхушке и $

на дне. Таблица анализа - это двумерный массив m[a,a], где a -

нетерминал, и a - терминал или символ $.

Анализатор управляется программой, которая работает

следующим образом. Она рассматривает x - символ на верхушке

магазина и a - текущий входной символ. Эти два символа

определяют действие анализатора. Имеются три возможности.

1. Если x=a=$, анализатор останавливается и сообщает об

успешном окончании разбора.

2. Если x=a#$, анализатор удаляет x из магазина и продвигает

указатель входа на следующий входной символ.

3. Если x - нетерминал, программа заглядывает в таблицу

m[x,a]. По этому входу хранится либо правило для x, либо

ошибка. Если, например, m[x,a]={x->uvw}, анализатор заменяет x

на верхушке магазина на wvu {на верхушке u}. Будем считать,

что анализатор в качестве выхода просто печатает

использованные правила вывода. Если m[x,a]=error, анализатор

обращается к подпрограмме анализа ошибок.

Поведение анализатора может быть описано в терминах

конфигураций автомата разбора.

Алгоритм 3.1. Нерекурсивный предсказывающий анализ.

repeat x:=верхний символ магазина;

if x - терминал или $

then if x=insym

then удалить x из магазина;

insym:=очередной символ;

else error()

end

else /*x = нетерминал*/

if m[x,insym]=x->y1y2...yk

then удалить x из магазина;

поместить yk,yk-1,...y1 в магазин

(y1 на верхушку);

вывести правило x->y1y2...yk

else error() /*вход таблицы m пуст*/

end end

until x=$ /*магазин пуст*/

Рис. 3.3

Вначале анализатор находится в конфигурации, в которой магазин

содержит s$, (s - начальный символ грамматики), во входном

буфере w$ (w - входная цепочка), переменная insym содержит

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

анализатора m для осуществления разбора, изображена на рис.

3.3.

Пример 3.1. Рассмотрим грамматику арифметических выражений:

e -> t e'

e' -> + t e' | e

t -> f t' (*)

t' -> * f t' | e

f -> ( e ) | id

Таблица предсказывающего анализатора для нее изображена на

рис. 3.4. Здесь пустые клетки - входы ошибок. Непустые дают

правила, по которым делается развертка нетерминала.

---------------------------------------- -----------

Нетер-| Входной символ

|--------------------------------------- -----

минал | id | + | * | ( | ) | $

------+------+--------+--------+------+- ----+------

e |e->te'| | |e->te'| |

e' | |e'->+te'| | |e'->e|e'->e

t |t->ft'| | |t->ft'| |

t' | |t'->e |t'->*ft'| |t'->e|t'->e

f |f->id | | |f->(e)| |

---------------------------------------- -------------

Рис. 3.4

----------------------------------

Магазин | Вход | Выход

--------+-----------+-------------

$e | id+id*id$ |

$e't | id+id*id$ | e->te'

$e't'f | id+id*id$ | t->ft'

$e't'id | id+id*id$ | f->id

$e't' | +id*id$ | e

$e' | +id*id$ | t'->e / \

$e't+ | +id*id$ | e'->+te' / \

$e't | id*id$ | t e'

$e't'f | id*id$ | t->ft' /| / | \

$e't'id | id*id$ | f->id f t' + t e'

$e't' | *id$ | | / |

$e't'f* | *id$ | t'->*ft' id / |

$e't'f | id$ | f t'

$e't'id | id$ | f->id | /|\

$e't' | $ | id * f t'

$e' | $ | t'->e |

$ | $ | e'->e id

----------------------------------

Рис. 3.5 Рис. 3.6

На входе id+id*id предсказывающий анализатор совершает

последовательность шагов, изображенную на рис. 3.5. Указатель

входа указывает на самый левый символ в колонке Вход. Если

внимательно проанализировать действия анализатора, то видно,

что он осуществляет левый вывод, т.е. правила применяются в

соответствии с левым выводом. За уже просмотренными входными

символами следуют символы грамматики в магазине (сверху вниз),

что соответствует левым сентенциальным формам вывода.

Дерево разбора приведено на рис. 3.6.

3.2.2. Множества first и follow.

При построении предсказывающего анализатора полезными

оказываются две функции, связанные с грамматикой g. Эти

функции, first и follow, позволяют построить таблицу

предсказывающего разбора для g, если, конечно, это возможно.

Множества, даваемые этими функциями, могут, кроме того, быть

использованы при восстановлении после ошибок.

Если u - любая строка символов грамматики, положим first(u)

- множество терминалов, с которых начинаются строки, выводимые

из u. Если u=>*e, то e также принадлежит first(u).

Определим follow(a) для нетерминала a как множество

терминалов a, которые могут появиться непосредственно справа

от a в некоторой сентенциальной форме, т.е. множество

терминалов a таких, что существует вывод вида s=>*uaav для

некоторых u и v. Отметим, что между a и a в процессе вывода