В.А. Серебряков - Теория и реализация языков программирования (1114953), страница 17
Текст из файла (страница 17)
Затем необходимо определить правило, которое должнобыть применено к X1 , и т. д. до тех пор, пока в процессе такого построениясентенциальной формы, соответствующей левому выводу, не будет примененоправило Y → a . . .. Этот процесс затем применяется для следующего самоголевого нетерминального символа сентенциальной формы.На рис.
4.2 условно показана структура предсказывающего анализатора,который определяет очередное правило с помощью таблицы. Такую таблицуможно построить и непосредственно по грамматике. Таблично-управляемыйпредсказывающий анализатор имеет входную ленту, управляющее устройство(программу), таблицу анализа, магазин и выходную ленту. Входная лентасодержит анализируемую строку, заканчивающуюся символом $ — маркеромконца строки. Выходная лента содержит последовательность примененныхправил вывода.Рис.
4.2Таблица анализатора — это двумерный массив M [A, a], где A — нетерминал, a — терминал или символ $. Значением M [A, a] может быть некотороеправило грамматики или элемент «ошибка».82Глава 4. Синтаксический анализМагазин может содержать последовательность символов грамматики с $на дне.
В начальный момент магазин содержит только начальный символграмматики на верхушке и $ на дне.Анализатор работает следующим образом. Вначале он находится в конфигурации, в которой магазин содержит S $, на входной ленте w$ (w —анализируемая цепочка), выходная лента пуста. На каждом такте анализаторрассматривает X — символ на верхушке магазина и a — текущий входнойсимвол. Эти два символа определяют действия анализатора. Имеются следующие возможности.1. Если X= a = $, то анализатор останавливается, сообщает об успешномокончании разбора и выдает содержимое выходной ленты.2. Если X= a 6= $, то анализатор удаляет X из магазина и продвигаетуказатель входа на следующий входной символ.3.
Если X — терминал, причем X 6= a, то анализатор останавливаетсяи сообщает о том, что входная цепочка не принадлежит языку.4. Если X — нетерминал, то анализатор обращается к таблице M [X , a].Возможны два случая.а) Значением M [X , a] является правило для X . В этом случае анализатор заменяет X на верхушке магазина на правую часть данногоправила, а само правило помещает на выходную ленту. Указательвхода не передвигается.б) Значением M [X , a] является «ошибка».
В этом случае анализаторостанавливается и сообщает о том, что входная цепочка не принадлежит языку.Работа анализатора может быть задана следующей программой:Поместить $,затем S в магазин;do {X = верхний символ магазина;if (X - терминал){ if (X ==InSym){удалить X из магазина;InSym = очередной символ;}else {error(); break;}else if (X - нетерминал)if (M [X , InSym]=="X->Y1Y2...Yk{удалить X из магазина;поместить Yk,Yk-1,...Y1 в магазин (Y1 на верхушку);вывести правило X->Y1Y2...Yk;}else {error(); break;} /*вход таблицы M пуст*/834.4. Предсказывающий разбор сверху-вниз}while (X != $); /*магазин пуст*/if (InSym != $) error(); /*Не вся строка прочитана*/Пример 4.6. Рассмотрим грамматику арифметических=({E , E ′ , T , T ′ , F }, {id, +, ∗, (, )}, P , E) с правилами:E → T E′;E ′ → +T E ′ ;E ′ → e;T → F T ′;выраженийG=T ′ → ∗F T ′ ;T ′ → e;F → (E);F → id.Ниже приведена таблица предсказывающего анализатора для этой грамматики(табл.
4.1). Пустые клетки таблицы соответствуют элементу «ошибка».Т а б л и ц а 4.1Нетер-Входной символминалidEE →T E ′E′T*()$E →T E ′E ′→+T E ′E ′→e E ′→eT →F T ′T′F+T →F T ′T ′ →eT ′ →∗F T ′F →idT ′→e T ′→eF →(E)При разборе входной цепочки id + id ∗ id$ анализатор совершает последовательность шагов, описанную в табл. 4.2. Заметим, что анализатор осуществляет в точности левый вывод. Если за уже просмотренными входными символами поместитьсимволы грамматики в магазине, то можно получить в точности левые сентенциальные формы вывода.
Дерево разбора для этой цепочки приведено на рис. 4.3.Рис. 4.384Глава 4. Синтаксический анализТ а б л и ц а 4.2МагазинВходE$id + id ∗ id$Выход′TE $id + id ∗ id$ E → T E ′F T ′E′$id + id ∗ id$ T → F T ′id T ′ E ′ $id + id ∗ id$ F → id′′T E$+id ∗ id$E′$+id ∗ id$T′ → e+T E ′ $+id ∗ id$E ′ → +T ET E′$id ∗ id$′FT E $id ∗ id$T → FT′id T ′ E ′ $id ∗ id$F → id′′′∗id$T E$∗F ′ T ′ E ′ $ ∗id$F T ′E′$′′id T E $′′T E$′T ′ → ∗F T ′id$id$F → id$E$$T′ → e$$E′ → e4.4.2. Функции F IRST и F OLLOW . При построении таблицыпредсказывающего анализатора нам потребуются две функции — F IRSTи F OLLOW .Пусть G = (N , T , P , S) — КС-грамматика.
Для α — произвольной цепочки, состоящей из символов грамматики, определим F IRST (α) как множествотерминалов, с которых начинаются строки, выводимые из α. Если α ⇒∗ e, то eтакже принадлежит F IRST (α).Определим F OLLOW (A) для нетерминала A как множество терминаловa, которые могут появиться непосредственно справа от A в некоторой сентенциальной форме грамматики, т. е.
множество терминалов a, таких, чтосуществует вывод вида S ⇒ ∗ αAaβ для некоторых α, β ∈ (N ∪ T )∗ . Заметим,что между A и a в процессе вывода могут находиться нетерминальные символы, из которых выводится e. Если A может быть самым правым символомнекоторой сентенциальной формы, то $ также принадлежит F OLLOW (A).4.4. Предсказывающий разбор сверху-вниз85Рассмотрим алгоритмы вычисления функции F IRST .Алгоритм 4.5. Вычисление F IRST для символов КС-грамматики.Вход. КС-грамматика G = (N , T , P , S).Выход. Множество F IRST (X) для каждого символа X ∈ (N ∪ T ).Метод.
Выполнить шаги 1–3:1. Если X — терминал, то положить F IRST (X) = {X}; если X — нетерминал, то положить F IRST (X) = ∅.2. Если в P имеется правило X → e, то добавить e к F IRST (X).3. Пока существуют множества F IRST (X), к которым можно добавлятьновые элементы, выполнять:do {continue = false;Для каждого нетерминала XДля каждого правила X → Y1 Y2 ...Yk{i=1; nonstop = true;while (i 6 k && nonstop){добавить F IRST (Yi ) \ {e} к F IRST (X );if (Были добавлены новые элементы)continue = true;if (e ∈/ F IRST (Yi )) nonstop = false;else i+ = 1;}if (nonstop) {добавить e к F IRST (X);continue = true;}}}while (continue)Алгоритм 4.6. Вычисление F IRST для цепочки.Вход. КС-грамматика G = (N , T , P , S).Выход.
Множество F IRST (X1 X2 . . . Xn ), Xi ∈ (N ∪ T ).Метод. Выполнить шаги 1–3:1. При помощи алгоритма 4.5 вычислить F IRST (X) для каждого X ∈ (N ∪∪ T ).2. Положить F IRST (X1 X2 . . . Xn ) = ∅.3. {i = 1; nonstop = true;while (i 6 n && nonstop){добавить F IRST (Xi ) \ {e} к F IRST (u);/ F IRST (Xi )nonstop = false;if (e ∈86Глава 4.
Синтаксический анализelse i+ = 1;}if (nonstop) {добавить e к F IRST (u);}Рассмотрим алгоритм вычисления функции F OLLOW .Алгоритм 4.7. Вычисление F OLLOW для нетерминалов грамматики.Вход. КС-грамматика G = (N , T , P , S).Выход. Множество F OLLOW (X) для каждого символа X ∈ N .Метод. Выполнить шаги 1–4:1. Положить F OLLOW (X) = ∅ для каждого символа X ∈ N .2. Добавить $ к F OLLOW (S).3. Если в P eсть правило вывода A → αBβ , где α, β ∈ (N ∪ T )∗ , то всеэлементы из F IRST (β), за исключением e, добавить к F OLLOW (B).4. Пока существуют множества F OLLOW (X), к которым можно добавлятьновые элементы, выполнять:если в P есть правило A → αB или A → αBβ , α, β ∈ (N ∪ T )∗ , гдеF IRST (β) содержит e (β ⇒∗ e), то все элементы из F OLLOW (A) добавить к F OLLOW (B).Пример 4.7.
Рассмотрим грамматику из примера 4.3. Для нее:F IRST (E) = F IRST (T ) = F IRST (F ) = {(, id};F IRST (E ′ ) = {+, e};F IRST (T ′ ) = {∗, e};F OLLOW (E) = F OLLOW (E ′ ) = { ), $};F OLLOW (T ) = F OLLOW (T ′ ) = {+, ), $};F OLLOW (F ) = {+, ∗, ), $}.Например, id и левая скобка добавляются к F IRST (F ) на шаге 3 при i = 1,поскольку F IRST (id) = {id} и F IRST (() = {(”} в соответствии с шагом 1.
На шаге3 при i = 1, в соответствии с правилом вывода T → F T ′ , к F IRST (T ) добавляютсятакже id и левая скобка. На шаге 2 в F IRST (E ′ ) включается e.При вычислении множеств F OLLOW на шаге 2 в F OLLOW (E) включается $. На шаге 3, на основании правила F → (E), к F OLLOW (E) добавляется также правая скобка. На шаге 4, примененном к правилу E → T E ′ ,в F OLLOW (E ′ ) включаются $ и правая скобка. Поскольку E ′ ⇒ ∗ e, они такжепопадают и во множество F OLLOW (T ).
В соответствии с правилом вывода E → T E ′на шаге 3 в F OLLOW (T ) включаются и все элементы из F IRST (E ′ ), отличныеот e.Мы определили F IRST как множество цепочек длины не более 1. Точнотак же можно определить функцию F IRSTk (α), где k — натуральное число4.4.
Предсказывающий разбор сверху-вниз87и α ∈ (N ∪ Σ)∗ : F IRSTk (α) = {w ∈ Σ∗ | либо |w| < k и α ⇒ G w, либо |w| = kи α ⇒ G wx для некоторого x ∈ Σ∗ }.Если α ∈ Σ∗ , то F IRSTk (α) = {w}, где w — это первые k символовцепочки α при |α| > k и w = α при |α| < k .4.4.3. Конструирование таблицы предсказывающего анализатора.Для конструирования таблицы предсказывающего анализатора по грамматикеG может быть использован алгоритм, основанный на следующей идее. Предположим, что A → α — правило вывода грамматики и a ∈ F IRST (α). Тогдаанализатор делает развертку A по α, если входным символом является a.Трудность возникает, когда α = e или α ⇒∗ e.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
