Type symbol=(nul, ident, number, plus, minus, times,
slash, oddsym, eql, lss, gtr,
lparen, rparen, comma, semicolon, period,
becomes, beginsym, endsym, ifsym, thensym,
whilesym, dosym, callsym, constsym, varsym,
procsym);
alfa = packed array [1..al] of char;
- 35 -
Var
ch:char; {последняя прочитанная литера входной строки}
sym:symbol; {последний опознанный символ языка}
id:alfa; {последний прочитанный идентификатор}
num:integer; {последнее прочитанное число}
res_words: array [1..norw] of alfa;{ зарезервированные
слова }
wsym: array [1..norw] of symbol;
ssym: array [char] of symbol;
Прежде чем воспользоваться процедурой Getsym, необходимо
выполнить некоторые начальные присваивания, а, именно, запол-
нить массивы res_words, wsym и ssym. Ниже приведен соответс-
твующий фрагмент программы:
for i:=0 to 255 do ssym[ord(i)]:=nul;
ssym['+']:=plus; ssym['-']:=minus;
ssym['*']:=times; ssym['/']:=slash;
ssym['(']:=lparent; ssym[')']:=rparent;
ssym['=']:=eql; ssym[',']:=comma;
ssym['.']:=period; ssym['>']:=gtr;
ssym['<']:=lss; ssym[';']:=semicolon;
{ В оригинале заполнены также односимвольные элементы:
"меньше либо равно", "больше либо равно", "не равно"
(такое может быть в некоторых реализациях) }
res_words[1] :='BEGIN '; res_words[2] :='CALL ';
res_words[3] :='CONST '; res_words[4] :='DO ';
res_words[5] :='END '; res_words[6] :='IF ';
res_words[7] :='ODD '; res_words[8] :='PROCEDURE ';
res_words[9] :='THEN '; res_words[10]:='VAR ';
res_words[11]:='WHILE ';
wsym[1] :=beginsym; wsym[2] :=callsym;
wsym[3] :=constsym; wsym[4] :=dosym;
wsym[5] :=endsym; wsym[6] :=ifsym;
wsym[7] :=oddsym; wsym[8] :=procsym;
wsym[9] :=thensym; wsym[10]:=varsym;
wsym[11]:=whilesym;
Getch; { чтение очередной литеры входной строки }
- 36 -
Перейдем к основной процедуре обсуждаемой темы - процеду-
ре Getsym. (Процедуру Getch оставим для самостоятельного на-
писания.)
procedure Getsym:
var i, j,k : integer;
procedure Getch:
begin
{ текст процедуры Getch здесь опущен }
end;
begin
while ch=' ' do Getch; { пропуск "лишних" пробелов }
if ch in ['A'..'Z'] then
begin
{ опознание идентификатора или служебного слова }
k:=0;
repeat
if k<al then
begin
k:=k+1;
a[k]:=ch
end;
Getch { лишние (сверх al) литеры игнорируются }
until not(ch in ['A'..'Z','0'..'9']);
{ Следующая строка отличается от оригинала }
for i:=k+1 to al do a[k]:=' ';{дополнение пробелами}
id:=a;
i:=1;
j:=norw;
repeat
k:=(i+j) div 2;
if id <= res_words[k] then j:=k-1;
if id >= res_words[k] then i:=k+1
until i>j;
if (i-1)>j then
sym:=wsym[k]
else
sym:=ident
end
- 37 -
else
{ распознавание числа }
if ch in ['0'..'9'] then
begin
k:=0;
num:=0;
sym:=number;
repeat
num:=10*num + (ord(ch)-ord('0'));
k:=k+1;
Getch;
{ Внимание! Контроля за переполнением здесь нет! }
until not (ch in ['0'..'9']);
if k>nmax then Error
end
else
{ распознавание многолитерных разделителей }
if ch = ':' then
begin
Getch;
if ch = '=' then
begin
sym:=becomes;
Getch
end
else sym:=nul
end
else
begin
sym:=ssym[ch];
Getch
end
end; { Getsym }
2Упражнение 0. Добавьте в процедуру Getsym распознавание
двухлитерных разделителей.
- 38 -
24.5. Выход из лексического анализатора
Прочитанные анализатором символы заносятся в различные
таблицы: идентификаторы заносятся в таблицу идентификаторов,
константы заносятся в таблицу констант и т. д. При этом могут
осуществляться различные проверки. Например, недопустимо двой-
ное описание идентификатора на одном уровне и тому подобное.
Служебные таблицы могут иметь специальную структуру, ускоряю-
щую работу с ними. Должна быть предусмотрена проверка на воз-
можное переполнение служебных таблиц. В последнем случае долж-
но выдаваться соответствующее сообщение.
Иногда лексическому анализатору приходится заглядывать
немного вперед. Приведем пример, ставший классическим. В языке
Фортран допустима следующая конструкция: 'DO 7 I=1,10' - это
пример оператора цикла, задающего повторение действий до стро-
ки с номером 7 при I, изменяющемся от 1 до 10. Так как пробелы
в Фортране незначащие, то этот оператор эквивалентен строке:
'DO7I=1,10'. С другой стороны, оператор присваивания в Фортра-
не имеет вид: <идентификатор>=<выражение>. Следовательно,
лексический анализатор не в состоянии правильно идентифициро-
вать оператор цикла, пока он не прочитает запятую после знака
равенства.
В истории программирования ошибка, связанная с заменой
запятой в операторе цикла на десятичную точку, известна как
самая дорогая. Цикл при этом превращается в оператор присваи-
вания с правой частью - вещественной константой: 'DO7I=1.10'.
Причем, синтаксически эта конструкция вполне корректна
(естественно, для Фортрана!). Обнаружение подобных ошибок
обойдется слишком дорого, а еще дороже - если они не будут об-
наружены вовсе. Горький опыт того, как космический корабль
"Маринер", запущенный на Венеру, потерялся из-за отсутствия
обязательного объявления (описания) переменных в Фортране учит
нас тому, что избыточность в современных языках благое дело.
Как уже упоминалось, на стадии лексического анализа обыч-
но исключаются комментарии, кроме прагматических, которые
несут информацию для следующих фаз компиляции.
.
- 39 -
25. АВТОМАТЫ С МАГАЗИННОЙ ПАМЯТЬЮ И КС-ГРАММАТИКИ
Контекстно-свободные грамматики традиционно служат осно-
вой для синтаксического анализа. Реальный язык программирова-
ния не описывается полностью КС-грамматикой, однако, нам вы-
годнее все-таки, может быть, с какими-то ограничениями, но
описать синтаксис средствами КС-грамматик. Тогда некоторые
особенности языка придется контролировать дополнительными
средствами.
Следовательно, нам нужно уметь определять, является ли
данный язык КС-языком. Следующая лемма дает возможность опре-
делить это [11].
2ЛЕММА ПОДКАЧКИ. 0 Для любого КС-языка L существует такая
константа k, что любое предложение z языка L, длина которого
превышает k, можно записать в виде z = uvwxy, где l(vwx)<=k,
l(v)>0, l(x)>0, а строка u((v)^i)w((x)^i)y - принадлежит языку
L при любом i>=0.
2Упражнение. 0 Пусть L={xx}, где x - произвольная цепочка,
состоящая из нулей и единиц. Докажите, что язык L не является
контекстно-свободным.
2Упражнение. 0 Покажите, что для скобочного языка выполня-
ется условие леммы подкачки.
Если для распознавания регулярных языков было достаточно
конечных автоматов, то для распознавания контекстно-свободных
языков требуются конечные автоматы с магазинной памятью
(МП-автоматы). Между КС-языками и МП-автоматами существует
полное соответствие; то есть всякий допускаемый МП-автоматом
язык является КС-языком и, наоборот, для всякого КС-языка мож-
но сконструировать МП-автомат, распознающий этот язык. Однако
следует иметь в виду, что, как и конечные автоматы, МП-автома-
ты могут быть детерминированными и недетерминированными. Можно
показать, что не всегда по недетерминированному МП-автомату
возможно построить детерминированный МП-автомат, распознающий
тот же язык. Соответственно, КС языки можно разделить на языки
детерминированные и недетерминированные.
Дадим 2определение 0 МП-автомата.
Под МП-автоматом понимается следующая шестерка:
1) конечное множество состояний,
2) конечный входной алфавит,
- 40 -
3) конечный алфавит символов магазина,
4) начальное состояние,
5) граничный маркер магазина,
6) множество переходов.
Множество переходов задает, как по текущему состоянию,
символу магазина и символу на входной ленте определяются новое
состояние и символы на вершине магазина. В начальный момент
времени автомат находится в начальном состоянии, в магазине
(стеке) находится граничный маркер и во входной строке разме-
щена анализируемая цепочка.
2Определение. 0 Говорят, что детерминированный автомат до-
пускает входную цепочку, если на каждом его шаге работы опре-
делен переход, и по концу анализа магазин содержит только мар-
кер конца. Соответственно можно определить, когда детерминиро-
ванный автомат не допускает входную цепочку.
2Определение. 0 Говорят, что недетерминированный МП-автомат
допускает входную цепочку, если существует последовательность
переходов, после которых входная цепочка исчерпана, и в мага-
зине находится только маркер. В противном случае МП-автомат не
допускает цепочку.
2Пример. 0 Построим МП-автомат для распознавания языка, по-
рождаемого следующей КС грамматикой:
1) E -> aa
2) E -> bb
3) E -> aEa
4) E -> bEb
Понятно, что успешный анализ любой цепочки данного языка
требует определения середины цепочки, после чего можно прове-
рить соответствие левой и правой половин. При разовом просмот-
ре входной цепочки невозможно установить, в какой половине мы
находимся. Следовательно, наш МП-автомат будет недетерминиро-
ванным.
В таблице 2 представлен пример задания множества перехо-
дов МП-автомата. При этом, входной алфавит {a, b}, алфавит ма-
газина - {#,A, B), множество состояний {0,1}. Начальное состоя-
ние 0 соответствует просмотру левой половины цепочки, а состо-
яние 1 означает просмотр правой половины.
.
- 41 -
2Таблица 2
2Пример задания множества переходов МП-автомата
ш1
┌─────────┬───────────┬────────────┬───────────┬──────────┐
│ Символ │ Текущее │ Символ │ Новое │ Новые │
│ входной │ состояние │ на вершине │ состояние │ символы │
│ цепочки │ автомата │ магазина │ автомата │ магазина │
├─────────┼───────────┼────────────┼───────────┼──────────┤
│ a │ 0 │ # │ 0 │ #A │
├─────────┼───────────┼────────────┼───────────┼──────────┤
│ b │ 0 │ # │ 0 │ #B │
├─────────┼───────────┼────────────┼───────────┼──────────┤
│ a │ 0 │ A │ 1 │ │
├─────────┼───────────┼────────────┼───────────┼──────────┤
│ b │ 0 │ B │ 1 │ │
├─────────┼───────────┼────────────┼───────────┼──────────┤
│ a │ 1 │ A │ 1 │ │
├─────────┼───────────┼────────────┼───────────┼──────────┤
│ b │ 1 │ B │ 1 │ │
├─────────┼───────────┼────────────┼───────────┼──────────┤
│ a │ 0 │ A │ 0 │ AA │
├─────────┼───────────┼────────────┼───────────┼──────────┤
│ a │ 0 │ B │ 0 │ BA │
├─────────┼───────────┼────────────┼───────────┼──────────┤
│ b │ 0 │ A │ 0 │ AB │
├─────────┼───────────┼────────────┼───────────┼──────────┤
│ b │ 0 │ B │ 0 │ BB │
└─────────┴───────────┴────────────┴───────────┴──────────┘
ш0
Попытка перейти в состояние 1 предпринимается только тог-
да, когда читаемый символ входной ленты соответствует символу
на вершине магазина. Считается, что верхний символ магазина
согласно приведенной таблице заменяется на символы, указанные
в последнем столбце. Если в этом столбце символы отсутствуют,
то значит верхний символ магазина удаляется из него.
2Упражнение. 0 Опишите детерминированный МП-автомат для
распознавания скобочного языка.
2Упражнение. 0 Докажите, что по любой КС-грамматике может
быть построен МП-автомат, распознающий язык, порождаемый этой
грамматикой.
2Упражнение. 0Покажите, что любой недетерминированный
МП-автомат распознает КС-язык.
26. СИНТАКСИЧЕСКИЙ АНАЛИЗ. МЕТОД РЕКУРСИВНОГО СПУСКА
Метод рекурсивного спуска относится к числу самых простых
методов синтаксического анализа. Он может быть запрограммиро-
- 42 -
ван достаточно быстро при наличии грамматики или синтакси-
ческих диаграмм заданного языка. Однако, забегая вперед, отме-
тим, что грамматика должна обладать определенными свойствами.
Рассмотрим следующий язык, заданный через БНФ:
<Программа> ::= program <Имя> <Операторы> <Значения>. │
program <Имя> <Операторы> .
<Операторы> ::= <Выражение> -> <Имя> │
<Выражение> -> <Имя> ; <Операторы>
<Значения> ::= where <Константы>
<Константы> ::= <Имя> = <Число> │
<Имя> = <Число> , <Константы>
<Выражение> ::= <Слагаемое> │ <Слагаемое> + <Выражение>
<Слагаемое> ::= <Имя> │ <Число>
Конструкции <Имя> и <Число> будем считать терминалами.
Синтаксический анализатор по методу рекурсивного спуска
состоит из набора процедур: каждому нетерминалу соответствует
своя процедура. Будем считать, что у нас имеются процедуры
Getsym (см. 4.4) и Error. Последняя процедура печатает сообще-
ние об ошибке, после чего обработка программы прекращается.
Ниже приводится набросок программы анализатора.
program Analis;
procedure Prog;
{ анализ конструкции <Программа> }
begin
if sym=Progsym then
begin
Getsym;
if sym=ident then
begin
Getsym;
Statements;
if sym<>pointsym then
begin
Value;
if sym<>pointsym then Error
end
end
- 43 -
else Error
end
else Error
end;
procedure Statements;
{ анализ конструкции <Операторы> }
var flag : boolean;
begin
flag:=false;
repeat
Expression;
if sym=assignsym then Getsym else Error;
if sym=ident then Getsym else Error;
if sym=semicolon then Getsym else flag:=true
until flag
end;
procedure Expression;
{ анализ конструкции <Выражение> }
begin
if (sym=ident) or
(sym=number) then Getsym else Error;
if sym=plus then
begin
Getsym;
Expression
end;
end;
procedure Value;
{ анализ конструкции <Значения> }
begin
if sym=wheresym then ListConst else Error;
end;
procedure ListConst;
{ анализ конструкции <Константы> }
var flag : boolean;
begin
flag:=false;
repeat
if sym=ident then Getsym else Error;
- 44 -
if sym=eqlsym then Getsym else Error;
if sym=number then Getsym else Error;
if sym=comma then Getsym else flag:=true
until flag
end;
begin
Getsym;
Prog
end.
Перед первым вызовом процедуры Prog определяется началь-
ная лексема. Далее всякая процедура при успешном завершении
анализа через Getsym читает следующую лексему.
27. LL - ГРАММАТИКИ
27.1. Безвозвратный анализ по первому символу
При нисходящем анализе без возвратов нам необходимо вся-
кий раз по очередному символу входной цепочки делать правиль-
ный выбор правила вывода. Обсудим эту проблему выбора на сле-
дующих примерах [3].
2Пример 1. 0Рассмотрим грамматику: S->aA, A->c, A->bA, по-
рождающую язык L={a(b*)c}. Будем строить дерево вывода для це-
почки x=abbc (рис. 10).
Обратите внимание, при построении дерева вывода по оче-
редному символу входной цепочки однозначно выбирается необхо-
димое правило вывода.
S
┌────────┤
a A
┌─────┤
b A
┌──┤
b A
│
c
Рис. 10. Дерево вывода для грамматики из примера 1
- 45 -
2Пример 2. 0Рассмотрим грамматику: S->A, S->B, A->aA, A->b,
B->aB, B->c, порождающую язык L={a*(b│c)}={a*b│a*c}. Если мы
сейчас попробуем построить дерево вывода для цепочки x=aaac,
то на первом же шаге возникает проблема выбора правила вывода.
Допустим, мы выберем первое правило вывода, тогда дерево при-
мет вид, приведенный на рис 11.
S
│
A
┌────────┤
a A
┌─────┤
a A
┌──┤
a A
│
?
Рис. 11. Дерево вывода для грамматики из примера 2
Оказалось, что мы попали в тупик. Здесь возможны два ва-
рианта: или цепочка не принадлежит языку, или где-то раньше
было выбрано неверно правило вывода. Следовательно, необходимо
возвращаться назад.
Для того, чтобы исключить возвраты, наложим на грамматики
два ограничения.
2Ограничение 1. 0 Для каждого нетерминала, для которого есть
несколько правил вывода, потребуем, чтобы множества начальных
терминальных символов (определяемых для каждой правой части
правила вывода) попарно не пересекались. Такое множество по
отношению к цепочке x, обозначается через first(x).
2Пример 3. 0 Грамматику из предыдущего примера легко переде-
лать так, чтобы остался прежний язык, и грамматика удовлетво-
ряла ограничению 1: S->C, S->aS, C->b, C->c. Здесь множества
начальных терминальных символов попарно не пересекаются.
Для нетерминала S: first(C)={b, c}, first(aS)={a}. Для нетерми-
нала C: first(b)={b}, first(c)={c}.
.
- 46 -
2Пример 4. 0Рассмотрим грамматику: S->Aa, A->Aa, A-> 7e 0. По-
пытаемся построить дерево вывода для цепочки x=a. Первый сим-
вол входной цепочки - "a". Для начального символа грамматики S
существует всего одно правило вывода, применяем его:
S
├───┐
A a
│
?
Какое выбрать продолжение? Первым символом по-прежнему
является символ "a", поэтому из двух правил для нетерминала A
выбираем то, во множестве first которого присутствует "a". При
этом мы попадаем в тупик, так как оказывается, что входная це-
почка закончилась, а в дереве вывода присутствует еще один
символ несопоставленный "a".
S
├───┐
A a
│
a
Трудность возникла из-за того, что символ A является уко-
рачивающим (то есть из него возможен вывод пустой цепочки).
Поэтому нам потребуется еще одно ограничение.
2Ограничение 2. 0 Для каждого укорачивающего нетерминала N
(то есть N=*> 7e 0) потребуем, чтобы множества first(N) и
follow(N) не пересекались, где follow(N) - это множество тер-
минальных символов, следующих за N среди всех цепочек, выводи-
мых в грамматике.
2Пример 5. 0 Рассмотрим грамматику: S->A, S->SA, S-> 7e 0, A->a.
Легко видеть, что здесь нарушено ограничение 2. Следующая
УКС-грамматика: { S-> 7e 0, S->AS, A->a } - порождает тот же
язык, и при этом выполняется ограничение 2.
К сожалению, не всегда удается переработать грамматику
таким образом, чтобы сохранились язык и синтаксическая струк-
тура всех цепочек, и при этом были бы выполнены ограничения 1
и 2.
- 47 -
27.2. Грамматики и синтаксические диаграммы
Процесс написания синтаксического анализатора можно фор-
мализовать. Можно предложить следующий порядок: сначала по
грамматике с ограничениями 1 и 2 строится детерминированный
синтаксический граф, а затем по графу выписывается программа
анализатора [3].
Отметим, что можно сформулировать правила построения син-
таксического графа (синтаксических диаграмм) по заданной грам-
матике [3].
Рассмотрим второй этап (написание анализатора) поподроб-
нее. Для этого сформулируем правила написания программы по
имеющимся диаграммам. Будем считать, что анализируемая цепочка
читается процедурой Getsym и в переменной sym хранится значе-
ние последней прочитанной лексемы. Для каждой конструкции S
заранее считается вычисленным множество first(S), содержащее
начальные лексемы этой конструкции.
2Правила преобразования графа в программу
21. 0Уменьшить по возможности количество отдельных диаг-
рамм, так как каждая диаграмма - это будущая процедура.
22. 0 Преобразовать каждую диаграмму в процедуру по правилам
3-7.
23. 0 Последовательность элементов S1, S2, ..., Sn в диаг-
рамме:
ш1
┌────┐ ┌────┐ ┌────┐
──────┤ S1 ├───┤ S2 ├─ . . . ───┤ Sn ├──
└────┘ └────┘ └────┘
ш0
преобразуется в составной оператор:
begin T(S1); T(S2); ...; T(Sn) end, где T(Si) - это оператор,
получившийся после преобразования элемента Si.
.
- 48 -
24. 0 Выбор в диаграмме:
ш1
┌────┐ преобразуется в оператор выбора
┌─────┤ S1 ├── case sym of
│ └────┘ L1 : T(S1);
│ ┌────┐ L2 : T(S2);
─────┼─────┤ S2 ├──
│ └────┘ Ln : T(Sn)
│ . . . else Error
│ ┌────┐ где Li=first(Si)
└─────┤ Sn ├──
└────┘
25. 0 Повторение: ─┬─────────┬──>
│ ┌────┐ │
└<─┤ S ├─┘
└────┘
ш0
преобразуется в цикл while sym in first(S) do T(S)
26. 0 Ссылка на другую диаграмму:
ш1
┌────┐
───┤ A ├─── заменяется вызовом процедуры A.
└────┘
ш0
27. 0 Если в диаграмме встречается терминальный символ "a",
то в программе записывается условный оператор:
if sym=a_sym then Getsym else Error
2Упражнение. 0 Преобразуйте некоторую грамматику в синтакси-
ческий граф, а затем составьте по графу программу анализатора.
27.3. Определение LL-грамматик
2Определение. 0Грамматика с ограничениями 1 и 2 называется
LL(1)-грамматикой. В этом названии первая буква L обозначает
чтение анализируемой цепочки слева направо, вторая буква L
обозначает левосторонний разбор, а число 1 обозначает, что
анализатор "заглядывает" на один символ вперед.
2Определение. 0Можно сформулировать ограничения 1 и 2 не
для одиночных терминальных символов, а для цепочек длины k.
Тогда соответствующая грамматика будет называться LL(k)-грам-
матикой.
- 49 -
Естественно возникает вопрос: "Можно ли по заданной
КС-грамматике, не являющейся LL(1) грамматикой определить, су-
ществует ли эквивалентная ей (то есть порождающая тот же язык)
LL(1)-грамматика?" К сожалению, в общем случае эта проблема
алгоритмически неразрешима. Однако, можно формулировать неко-
торые рекомендации по преобразованию грамматики к виду LL(1).
В частности следует избегать использовать левую рекурсию.
Одно из возможных решений - это использование правой рекурсии.
Существуют специальные системы автоматического преобразо-
вания грамматики к виду LL(1). Поэтому, если доступна подобная
система, то можно порекомендовать такой путь:
1) по языку строим грамматику,
2) проверяем и при необходимости пытаемся преобразовать
грамматику с помощью нашей системы к виду LL(1),
3) оставшиеся противоречия пытаемся устранить "вручную",
4) если последнее не удалось, то или переделываем исход-
ный язык, или пишем для отдельных "плохих" конструкций специ-
альные методы анализа (например, с заглядыванием на большее
число символов вперед).
27.4. Таблично-управляемый анализатор для LL(1)-грамматик
Пусть грамматика задана синтаксическим графом с ограни-
чениями 1, 2. Наша задача: написать таблично-управляемый ана-
лизатор. Для этого необходимо каким-либо образом представить
информацию о грамматике. Нас по-прежнему интересуют, в первую
очередь, безвозвратные методы.
2Пример 1. 0Рассмотрим следующий примитивный язык, описыва-
емый синтаксическими диаграммами (рис. 12, 13).
Представим эти синтаксические диаграммы в виде многосвяз-
ной структуры. Узлы этой структуры представляют собой записи с
вариантами. Один вариант будет соответствовать терминальному
символу в диаграмме, а второй - нетерминальному. Ниже приведе-
но соответствующее описание и графическое представление [3].
.
- 50 -
Type ref = ^ node
node = record {Графическое представление узла:}
alt, suc : ref; {┌─────────────┐}
case terminal:boolean of {│ sym │}
true : (tsym : sym ); {├──────┬──────┤}
false: (nsym : ref ) {│ alt │ suc │}
end {└──────┴──────┘}
Поле sym используется для задания терминального символа
(литерой) или нетерминала (соответствующей ссылкой на начало
представления данной конструкции). Поле alt - это ссылка на
альтернативный вариант продолжения в диаграмме (nil -
отсутствие таковых). Поле suc - это ссылка на узел продолжения
в диаграмме. Дополнительно вводится в рассмотрение специальный
терминальный символ empty, обозначающий пустую последователь-
ность.
Иногда бывает удобно определить заголовок для каждого не-
терминального символа. Его наличие позволяет в необходимых
случаях ссылаться на имя разбираемой конструкции, что полезно
для более полной диагностики ошибок. Соответствующее описание
приведено ниже:
Type hptr = ^ header;
header = record
entry : ref;
name_sym : string
end
В описании узла node следует внести изменение: поле nsym
будет иметь тип hptr:
Type ref = ^ node
node = record {Графическое представление узла:}
alt, suc : ref; {┌─────────────┐}
case terminal:boolean of {│ sym │}
true : (tsym : sym ); {├──────┬──────┤}
false: (nsym : hptr) {│ alt │ suc │}
end {└──────┴──────┘}
- 51 -
Для набора синтаксических диаграмм можно сформулировать
правила их преобразования в заполненные структуры данных.
Отсылаем любознательного читателя в этом месте к первоисточни-
ку [3]. Далее будет приведен пример такого представления наших
диаграмм.
ш1
2Выражение
┌─────────┐
───┬─> ( ──┬──│выражение│──┬── ) ──┬────>
│ │ └─────────┘ │ │
│ │ │ │
│ │ │ │
│ └────── + <─────┘ │
│ │
│ ┌─────────┐ 2 0 │
└─────────>│ имя │──────────┘
└─────────┘
Рис.12. Синтаксическая диаграмма "Выражение"
2Имя
┌─────> a ─────┐
│ │
│ │
│ │
────┼─────> b ─────┼─────>
│ │
│ │
│ │
└─────> c ─────┘
Рис.13. Синтаксическая диаграмма "Имя"
ш0
2Пример 2. 0Вернемся к предыдущему примеру. Для описанных
конструкций можно построить многосвязную структуру (рис. 14).
В заголовке указано имя основной конструкции "Выр." (выраже-
ние). Конструкция "Имя" исчезла после преобразования синтакси-
ческих диаграмм. Символ "ref S" обозначает ссылку на элемент
S, "nil" обозначает пустую (неопределенную) ссылку. Прочие
обозначения ("(", ")", "а" и т. д.) соответствуют терминальным
символам.
2Упражнение. 0Приведите пример фрагмента программы на
Паскале для создания и заполнения структуры, изображенной на
рисунке 14.
- 52 -
ш1
┌───────┐
─────>│ Выр. │<──────┐
└─┬───┬─┘ │
│ nil │ ┌──────────────────┐
┌─┴─────┐ ┌─┴───┴─┐ ┌───────┐ │
│ ( │ ┌─>│ ref S │ ┌─>│ + │ │
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 |
