Но в теоретических исследованиях удобнее пользоваться аппара-
том формальных грамматик, на нем мы и остановимся поподробнее.
22.1. Определения и общие свойства порождающих грамматик
Упомянутые выше нормальные формы Бэкуса и синтаксические
диаграммы Вирта используются для представления синтаксиса и,
отчасти, семантики. Приведем пример описания понятия "иденти-
фикатор" с использованием формализма БНФ:
<идентификатор> ::= <буква> │ <буква> <буквы и цифры>
<буквы и цифры> ::= <буква> │ <цифра> │
<буква> <буквы и цифры> │
<цифра> <буквы и цифры>
<буква> ::= a │ b │ c │ d │ e │ f │ g │ h │ i │ j │ k │ l │ m
│ n │ o │ p │ q │ r │ s │ t │ u │ v │ w │ x │ y │ z
<цифра> ::= 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ 8 │ 9
- 19 -
Приведенные в угловых скобках обозначения называются ме-
талингвистическими переменными или нетерминальными символами.
В этих обозначениях проявляется семантика конструкций языка
программирования.
Запись вида "::=" читается как "это есть". Вертикальная
черта задает перечисление альтернативных определений данного
понятия. Оставшиеся символы называются терминальными.
Позже стали использоваться так называемые расширенные БНФ
(РБНФ). Их отличие в том, что в правых частях правил было раз-
решено использовать квадратные и фигурные скобки, не являющи-
еся терминальными. Квадратные скобки обозначают необязательный
элемент, а фигурные задают возможное повторение нуль или более
раз. Приведенный выше пример на РБНФ выглядит так:
<идентификатор> ::= <буква> {<буква или цифра>}
<буква или цифра> ::= <буква> │ <цифра>
<буква> ::= a │ b │ c │ d │ e │ f │ g │ h │ i │ j │ k │ l │ m
│ n │ o │ p │ q │ r │ s │ t │ u │ v │ w │ x │ y │ z
<цифра> ::= 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ 8 │ 9
В синтаксических диаграммах терминальные и нетерминальные
символы различаются внешним видом контура: терминальные эле-
менты размещаются в овалах или кружках, а нетерминальные - в
прямоугольниках. В данном тексте терминальные символы будут
записываться в синтаксических диаграммах без контура. Название
диаграммы соответствует определяемому нетерминальному символу.
Пути, ведущие от начала диаграммы к ее концу задают все син-
таксически корректные варианты. На рисунке 5 приведены диаг-
раммы понятий "идентификатор", "буква" и "цифра".
Нормальные формы Бэкуса, а вместе с ними и синтаксические
диаграммы Вирта, легко трансформируются в порождающие грамма-
тики. Для этого металингвистические переменные заменяются не-
терминальными символами грамматики, комбинация "::=" заменя-
ется стрелкой, терминальные символы остаются неизменными, а
каждой альтернативе соответствует свое правило грамматики.
- 20 -
ш1
┌─────┐
┌<─┤буква├─┐
Идентификатор ┌─────┐ │ └─────┘ │
─────────────>│буква├──┼──────────┼───────────────>
└─────┘ │ ┌─────┐ │
└<─┤цифра├─┘
└─────┘
┌──── a ────┐ ┌──── 0 ────┐
│ │ │ │
├──── b ────┤ ├──── 1 ────┤
│ │ │ │
Буква ││ Цифра ││
─────────┤ ├────> ───────┤ ├────>
│ │ │ │
└──── z ────┘ └──── 9 ────┘
Рис. 5. Пример синтаксических диаграмм
ш0
Дадим формальное определение грамматики [2].
2Определение 0. Порождающей грамматикой G называется четверка
объектов: <Vt, Vn, S,P>, где
Vt - конечное множество терминальных символов;
Vn - конечное множество нетерминальных символов, причем
множества Vt и Vn не пересекаются;
S - начальный символ грамматики, принадлежащий множеству
Vn;
P - множество правил вывода вида x -> y, где x и y цепоч-
ки терминальных и нетерминальных символов.
Здесь и в дальнейшем будем придерживаться следующих обоз-
начений: малые латинские буквы из начала алфавита будут обоз-
начать терминальные символы, малые латинские буквы из конца
алфавита будут обозначать цепочки как терминальных, так и не-
терминальных символов, большие латинские буквы будут обозна-
чать нетерминальные символы. При всех буквах допустимо указы-
вать индексы.
2Определение 0. Говорят, что цепочка x1 непосредственно вы-
водима из цепочки x0 в грамматике G (записывается так:
x0->/G/->x1 ), если цепочки x0, x1 представимы в виде
x0=w1yw2, x1=w1zw2, и среди правил вывода есть правило y->z.
2Определение 0. Если в грамматике G есть непосредственная
выводимость x[0]->x[1], x[1]->x[2], ..., x[n-1]->x[n], то го-
ворят, что цепочка x[n] выводима из x[0] в грамматике G (за-
писывается так: x[0]->/+G/->x[n]). Символ грамматики можно
опускать или писать его под знаком выводимости.
- 21 -
В частных случаях, x[0] может быть нетерминалом или тер-
минальной цепочкой, что позволяет определять выводимость из
нетерминала, выводимость терминальной цепочки.
2Определение 0. Множество терминальных цепочек, выводимых в
грамматике G из начального символа, называется языком, порож-
даемым этой грамматикой, и обозначается L(G).
2Пример. 0Рассмотрим следующую грамматику G:
1) Vt = { a, b, c, 0, 1, 2 },
2) Vn = { A, B, C, D },
3) начальный символ грамматики - A,
4) правила вывода S = { A -> BC; B -> a; B -> b; B -> c;
C -> B; C ->D; C -> CC; D -> 0; D -> 1; D -> 2 }.
В язык L(G), порождаемый данной грамматикой G, входят це-
почки, начинающиеся с одной из букв: a, b или c. Далее следуют
один или несколько буквенных (a, b, c), или цифровых (0, 1, 2)
символов. Покажем, как, например, выводится цепочка ab0с:
A -> BC -> aC -> aCC -> aCCC -> aBCC -> abCC -> abDC -> ab0C
-> ab0c. Перечислить все цепочки языка невозможно, так как их
количество бесконечно.
Одной из основных проблем, связанных с практическим при-
менением порождающих грамматик, является проблема распознава-
ния. Для конкретной грамматики алгоритмическая разрешимость
проблемы распознавания означает, что можно за конечное число
шагов проверить принадлежность произвольной терминальной це-
почки языку, порождаемому данной грамматикой. Очевидно, что
интерес представляют в первую очередь распознаваемые языки, но
существуют и нераспознаваемые языки.
Описанный выше язык L(G) является распознаваемым.
Действительно, рассмотрим произвольную цепочку символов над
терминальным алфавитом Vt. Пусть ее длина равна l. Если l<2,
то цепочка заведомо не принадлежит языку.
Пусть l>=2, тогда применим к начальному символу правило
вывода A -> BC. Далее применим (l-1) раз правило C -> CC. В
результате получим цепочку нетерминалов: BCC...C. Принадлеж-
ность цепочки языку определяется выводимостью каждого из ее
символов из соответствующего нетерминала. Последнее легко про-
верить полным перебором правил вывода.
2Определение 0. Количество символов, составляющих цепочку,
называется длиной цепочки (обозначение: l(x) или │x│ ). Если
- 22 -
l(x)=0, то цепочка называется пустой. Будем обозначать пустую
цепочку символом - 7e 0.
2Определение 0. Грамматика называется неукорачивающей, если
для любого правила вывода левая часть не длиннее правой.
2Теорема 0. Пусть G - неукорачивающая грамматика, тогда L(G)
- легко распознаваемый язык, то есть число шагов алгоритма
распознавания есть функция длины цепочки [2].
2Указание 0. Доказательство основывается на полном переборе
бесповторных выводов.
Неукорачивающие грамматики довольно громоздки и неудобны,
так как в них допускается замена терминальных цепочек, что
приводит к потере естественной интерпретации нетерминальных
символов как обозначений (имен) синтаксических конструкций.
22.2. Классификация грамматик
Существует несколько вариантов классификации порождающих
грамматик. Ниже приводится вариант классификации по Хомскому
[11]. Грамматики перечисляются в следующем порядке: произволь-
ные грамматики, неукорачивающие грамматики, грамматики не-
посредственных составляющих, контекстно-свободные грамматики,
укорачивающие контекстно-свободные грамматики, автоматные
грамматики.
1) 2Произвольные грамматики 0 - по Хомскому - 2тип 0 0.
2) 2Неукорачивающие грамматики 0 - 2тип 1 0.
3) 2НС - грамматики 0 (вид правил: xAy -> xty, t<> 7e 0 ).
Класс НС-грамматик эквивалентен классу неукорачивающих
грамматик (следовательно, по Хомскому тоже 2тип 1 0). Другое наз-
вание НС-грамматик - контекстно зависимые грамматики.
4) 2КС - грамматики 0(вид правил: A -> x, x<> 7e 0) - по
Хомскому - 2тип 2 0. Класс КС-языков уже класса НС-языков.
5) 2УКС - грамматики 0(вид правил: A -> x, где x, возмож-
но, пустая цепочка). По любой УКС-грамматике можно построить
- 23 -
почти эквивалентную ей КС-грамматику (тот же язык за исключе-
нием, возможно, пустой цепочки).
6) 2А - грамматики. 0 Лево и правоавтоматные или иначе - ре-
гулярные грамматики (вид правил: A -> aB, A -> a). По Хомскому
- 2тип 3 0.
2Упражнение. 0 L={xbx}. (В терминальной цепочке "x" терминал
"b" не присутствует.) Показать, что это НС-язык.
(Ответ: I->b; I->IA[i]a[i]; a[i]A[j]->A[j]a[i]; bA[i]->a[i]b)
2Пример. 0Рассмотрим скобочный язык. Он состоит из беско-
нечного множества цепочек, представленных правильной скобочной
структурой. Порождающая его грамматика очень проста:
1) E -> ( )
2) E -> ( E )
3) E -> E E
Судя по грамматике, язык является контекстно свободным.
Однако, пример КС-грамматики не означает, что не существует
грамматики с более жесткими ограничениями (в данном случае -
регулярной).
Докажем, что скобочный язык действительно не является ре-
гулярным.
Предположим противное: пусть существует регулярная грам-
матика (например, левоавтоматная). Тогда, правила вывода имеют
вид: A -> a, A -> aB. В качестве терминальных символов будут
выступать левые и правые скобки.
Предположим в искомой грамматике имеется k нетерминальных
символов. Рассмотрим скобочную цепочку, состоящую из k левых
скобок, за которыми следуют k правых скобок. Это правильная
скобочная цепочка. Построим вывод этой цепочки в нашей гипоте-
тической грамматике.
На каждом шаге вывода порождается один терминальный сим-
вол, поэтому всего будет 2k шагов. При этом, на каждом шаге в
получаемой цепочке будет присутствовать ровно один нетерминал.
Рассмотрим первую половину этого вывода (порождение k левых
скобок). Очевидно, что среди использованных в этой части выво-
да нетерминалов найдутся хотя бы два совпадающих, то есть:
E => ... => x 2Z 0 => ... => y 2Z 0 => t
- 24 -
Здесь x и y некоторые терминальные цепочки, а t - результирую-
щая цепочка. Пусть выделенная часть вывода содержит m шагов,
тогда цепочка y получается из цепочки x приписыванием m левых
скобок.
Понятно, что мы в рамках нашей грамматики можем построить
другой вывод, отличающийся от исходного тем, что в первой его
части будет выброшена выделенная ранее часть. И, следователь-
но, нашему языку будет принадлежать цепочка из (k-m) левых
скобок и k правых скобок. А это запрещено. Полученное противо-
речие означает, что не может существовать регулярная граммати-
ка, порождающая скобочный язык.
23. ВЫВОД ЦЕПОЧЕК
23.1. Задача разбора
Мы рассмотрели задачу порождения цепочек языка. Однако,
для компилятора важно уметь распознавать цепочки и устанавли-
вать их структуру. Эта задача называется задачей разбора.
Структура цепочки может быть задана графически в виде дерева.
В программе часто применяют иной способ - линейно скобочная
запись.
2Пример. 0 Пусть даны правила вывода порождающей грамматики
G с начальным символом E:
1) E -> E + T
2) E -> T
3) T -> T * F
4) T -> F
5) F -> ( E )
6) F -> a
7) F -> b
Здесь E - арифметическое выражение; T - терм; F - множи-
тель.
Рассмотрим цепочку (a+b)*a. Очевидно, что она принадле-
жит языку L(G). Попробуем построить вывод этой цепочки из на-
чального символа: E -> T -> T*F. На этом шаге возникает неоп-
ределенность: к какому нетерминалу применять следующее правило
- 25 -
вывода. Будем придерживаться принципа - правило вывода всякий
раз применяется к самому левому вхождению нетерминала. Тогда
последовательность вывода имеет вид:
E -> T -> T*F -> F*F -> (E)*F -> (E+T)*F -> (T+T)*F ->
-> (F+T)*F -> (a+T)*F -> (a+F)*F -> (a+b)*F -> (a+b)*a
Мы осуществили так называемый левосторонний вывод. Пе-
речиcлим номера правил: 2,3,4,5,1,2,4,6,4,7,6. Последователь-
ность порождающих правил левостороннего вывода называется ле-
восторонним или нисходящим (от начального символа к терминаль-
ной цепочке) разбором.
Обратите внимание: в нашем случае существует только один
левосторонний вывод; то есть, каждый раз после выбора самого
левого нетерминала существует единственное правило, ведущее к
результирующей терминальной цепочке.
Кроме левостороннего существуют правосторонние и смешан-
ные выводы.
Под правосторонним или восходящим (от терминальной цепоч-
ки к начальному символу) разбором понимается обратная последо-
вательность порождающих правил при правостороннем выводе. В
нашем примере с цепочкой (a+b)*a правосторонний вывод соот-
ветствует последовательности номеров: 2,3,6,4,5,1,4,7,2,4,6; а
правосторонний разбор - это номера: 6,4,2,7,4,1,5,4,6,3,2.
Позже будет показана связь левостороннего и правостороннего
разборов с порядком построения дерева вывода.
23.2. Дерево разбора
Найденный вывод цепочки можно представить в виде дерева,
где корню дерева соответствует начальный символ грамматики, а
терминальным символам соответствуют листья дерева. На рисунке
6 приведено дерево для цепочки из предыдущего примера. Обрати-
те внимание, в дереве не отражен порядок применения правил вы-
вода; то есть всем возможным выводам соответствует одно дере-
во, поэтому дерево называется деревом разбора. Структура дере-
ва наглядно показывает структуру терминальной цепочки. Номера-
ми обозначены применяемые правила.
- 26 -
ш1
E
│ 2
T
│ 3
┌─────────────┼─────────────┐
│ │ │
T * F
│ 4 │ 6
│ │
F a
│ 5
│
┌─────────┼────────┐
│
( E )
│ 1
┌─────┼─────┐
E + T
│ 2 │ 4
T F
│ 4 │ 7
F b
│ 6
a
Рис. 6. Пример дерева вывода
ш0
Теперь видно, что левосторонний разбор соответствует
построению дерева разбора в порядке сверху вниз. Правосторон-
ний разбор эквивалентен построению дерева снизу вверх.
Для этого же примера структура может быть задана в виде
линейно-скобочной записи:
(E (T (T (F '(' (E (E (T (F 'a'))) '+'
(T (F 'b'))) ')') * (F 'a')))
Принцип построения этой записи заключается в следующем.
Выписываем в скобках символ корня дерева и символы вершин сле-
дующего уровня. Если эти вершины являются корнями поддеревьев,
то для них выполняем ту же процедуру.
Оказывается, существуют грамматики, допускающие построе-
ние различных деревьев разбора для одной и той же цепочки. Та-
кие грамматики называются синтаксически неоднозначными. Языки,
все порождающие грамматики которых синтаксически неоднозначны,
называются существенно неоднозначными.
.
- 27 -
2Упражнение. 0Покажите, что следующая грамматика является
синтаксически неоднозначной:
1) S -> S + S
2) S -> a
Известна интерпретация построения дерева вывода, напоми-
нающая игру в домино. Эта интерпретация принадлежит Де Ремеру.
Она заключается в следующем [11].
Каждому правилу вывода соответствует кость домино, у ко-
торой одна сторона представлена половинкой квадрата с надписью
нетерминала левой части правила вывода, а другая сторона кости
содержит половинки квадратов для нетерминалов и целые квадраты
для терминальных символов. Их порядок следования определяется
порядком следования соответствующих символов в правой части
правила вывода.
Каждая половинка или целый квадрат помечены соответствую-
щим нетерминальным или терминальным символом. Считается, что
эти половинки и квадраты соединены эластичными нитями с поло-
винкой нетерминала левой части. Количество таких костей опре-
деляется потребностью игрока (потенциально их бесконечно мно-
го).
В начале игры на игровом поле расположена половинка квад-
рата, подписанная начальным символом грамматики. Далее необхо-
димо подбирать кости таким образом, чтобы половинки образовы-
вали полные квадраты. Естественно, как и в настоящем домино,
стыкуются только одинаково помеченные половинки.
Цель игры - добиться того, чтобы на игровом поле остались
только целые квадраты, образующие в порядке слева направо за-
данную в начале игры терминальную цепочку.
На рисунке 7 приведен пример размещения костей домино для
построения терминальной цепочки "a*b" (для грамматики из пунк-
та 3.1)
.
- 28 -
ш1
┌─────────┐
│ E │
├─────────┤
│ E │
└────┬────┘
┌────┴────┐
│ T │
├─────────┤
│ T │
└────┬────┘
┌──────────────┼───────────────┐
┌────┴────┐ │ ┌────┴────┐
│ T │ │ │ F │
├─────────┤ │ ├─────────┤
│ T │ │ │ F │
└────┬────┘ │ └────┬────┘
┌────┴────┐ │ │
│ F │ │ │
├─────────┤ │ │
│ F │ │ │
└────┬────┘ │ │
┌────┴────┐ ┌────┴────┐ ┌────┴────┐
│ │ │ │ │ │
│ a │ │ * │ │ b │
│ │ │ │ │ │
└─────────┘ └─────────┘ └─────────┘
ш0
Рис. 7. Пример игры Де Ремера
23.3. Классификация методов разбора
Методы разбора делятся на нисходящие, восходящие и сме-
шанные. Это деление определяется порядком построения дерева
разбора.
Отказ от принятого решения в процессе разбора цепочки на-
зывается возвратом.
Методы разбора делятся на детерминированные (без возвра-
тов) и недетерминированные (с возвратами). Недетерминированные
методы более дорогостоящи по сравнению с детерминированными с
точки зрения расхода времени и памяти. Сложность при осущест-
влении возврата связана с необходимостью аннулирования некото-
рых ранее выполненных действий. Конечно, здесь удобны ре-
курсивные алгоритмы, которые, однако, в свою очередь не очень
эффективны.
.
- 29 -
24. ЛЕКСИЧЕСКИЙ АНАЛИЗ
24.1. Регулярные выражения
Лексический анализ - это первая фаза компиляции. На этом
этапе осуществляется группирование строк литер в слова-симво-
лы. Примеры таких символов: идентификаторы, служебные слова,
числа, разделители. В однопроходных трансляторах лексический
анализ выполняется одновременно с грамматическим разбором и
генерацией кода, однако, имеет смысл представлять лексический
анализ как отдельную фазу.
Обычно символы входного языка могут быть сгенерированы с
помощью регулярных выражений.
2Определение. 0Регулярное выражение задается следующим об-
разом [11]:
21 0) любой символ исходного алфавита или пустая цепочка -
это регулярное выражение,
22 0) если P и Q - регулярные выражения, то PQ (за P следует
Q - операция конкатенации) - это регулярное выражение,
23 0) если P и Q - регулярные выражения, то P│Q (P или Q -
операция выбора) - это регулярное выражение,
24 0) если P - регулярное выражение, то P* (нуль или более
экземпляров из P. Здесь "*" - операция повторения) - это регу-
лярное выражение.
Приоритеты (в порядке убывания): повторение, конкатена-
ция, выбор.
Например, вещественное число в форме без порядка может
быть представлено формулой:
(+│-│)dd*.dd* , где d - произвольная цифра.
По регулярному выражению легко написать регулярную (авто-
матную) грамматику.
Автоматная грамматика называется регулярной, если в ней
нет правил вывода вида: S->aS, где S - начальный символ грамма-
тики. Легко заметить, что любая автоматная грамматика без тру-
да трансформируется в регулярную введением нового начального
символа.
.
- 30 -
Для предыдущего выражения из предыдущего примера регуляр-
ная грамматика будет следующей (здесь под номерами 4, 5, 7 и 8
приведены схемы правил, каждая из которых представляет по
десять правил с соответствующими десятью цифрами):
1) R -> + S 5) T -> d T
2) R -> - S 6) T -> . V
3) R -> S 7) V -> d
4) S -> d T 8) V -> d V
Существует полное соответствие между регулярными выраже-
ниями ( и, следовательно, регулярными грамматиками ) и конеч-
ными автоматами, описанными ниже.
24.2. Конечные автоматы
Приведем определение детерминированного конечного автома-
та [2].
2Определение. 0 Под конечным автоматом понимается совокуп-
ность следующих пяти объектов:
1) K - конечное множество состояний,
2) A - конечный алфавит,
3) S - начальное состояние (из множества K),
4) F - множество заключительных состояний (подмножество K).
5) D: K*A -> K - частично определенная функция переходов.
Говорят, что 2конечный автомат принимает 0(допускает) вход-
ную цепочку, если при ее анализе, начиная с начального состоя-
ния, функция D определена на каждом шаге, и последнее состоя-
ние автомата является заключительным.
Говорят, что 2конечный автомат не принимает 0 (не допускает)
входную цепочку, если или последнее состояние автомата не яв-
ляется заключительным, или на каком-либо шаге не определена
функция D.
Автомат называется недетерминированным, если отображение
D многозначно, то есть на всех или некоторых наборах парамет-
ров выходное значение состояния определяется неединственным
образом. Можно показать, что по всякому недетерминированному
- 31 -
автомату можно построить эквивалентный ему (то есть, допускаю-
щий тот же язык) детерминированный автомат.
2Определение. 0Входная цепочка допускается недетерминиро-
ванным конечным автоматом, если существует такой порядок при-
менения отображения D, при котором по окончанию входной цепоч-
ки последнее состояние является заключительным. В противном
случае говорят, что автомат не допускает входную цепочку.
Приведем пример конечного автомата для распознавания
идентификатора с возможными начальными пробелами, которые
обозначим через ' '. Для этого определим все составные части
автомата:
1) K = {0,1}
2) A = {a, b, ..., z, 0, 1, ..., 9, ' '}
3) S = 0
4) F = {1}
5) Функцию переходов зададим таблично (см. табл. 1). Си-
туацию недопустимого символа обозначим словом fail.
2Таблица 1
2Таблица переходов
ш1
┌─────┬─────────┬─────────┬─────┐
│K \ A│ a,...,z │ 0,...,9 │ ' ' │
├─────┼─────────┼─────────┼─────┤
│ 0 │ 1 │ fail │ 0 │
├─────┼─────────┼─────────┼─────┤
│ 1 │ 1 │ 1 │fail │
└─────┴─────────┴─────────┴─────┘
ш0
Удобно задавать конечный автомат графом (диаграммой пере-
ходов). В этом случае узлы графа соответствуют состояниям, а
направленные дуги помечаются символами. Для предыдущего приме-
ра граф представлен на рисунке 8.
ш1
┌───┐ a, b, ..., z ┌───┐
┌─────>│ 0 ├──────────────────>│ 1 │<──────────┐
│ └─┬─┘ └─┬─┘ │
│ │ │ │
│ ' ' │ │ 0, ..., 9 │
└────────┘ │ a, ..., z │
└─────────────┘
ш0
Рис. 8. Пример графа переходов
- 32 -
Можно показать, что по любому недетерминированному конеч-
ному автомату строится детерминированный автомат, распознающий
(допускающий) тот же язык.
2Упражнение. 0Покажите эквивалентность способов задания ре-
гулярного языка: лево - и право - автоматные грамматики, детер-
минированный и недетерминированный конечные автоматы, регуляр-
ные выражения и грамматики (то есть то, что любой язык из
класса регулярных языков можно задать каждым из перечисленных
способов).
24.3. Лексический анализатор
Написание лексического анализатора заключается в модели-
ровании различных автоматов для распознавания различных симво-
лов. В качестве примера рассмотрим задачу распознавания ве-
щественного числа в форме без порядка. Соответствующий конеч-
ный автомат представлен диаграммой (графом) переходов на
рисунке 9. Под стрелками указаны допустимые символы. Вещест-
венное число считается принятым конечным автоматом, если авто-
мат перейдет в четвертое состояние. Символ d обозначает как и
прежде произвольную цифру.
Например, строка "314.1Е-02" считается правильной записью
вещественной константы до момента чтения символа "Е" (автомат
последовательно находится в состояниях: ), но так
как при этом строка не исчерпана, то полная запись "314.1Е-02"
с точки зрения данного автомата считается некорректной.
Второй пример: строка "+.343" считается некорректной, так
как символ "." недопустим после знака "+".
ш1
┌─────────────────┐
│ │
┌───┴───┐ ┌───────┐│d ┌───────┐ ┌───────┐ ┌───────┐
│ 0 ├───>│ 1 │└──>│ 2 ├───>│ 3 ├───>│4(закл)│
│началь-│+/- │чтение ├───>│чтение │ . │чтение │ d │чтение │
│ное со-│ │знака │ d │целой │ │точки │ │дробной│
│стояние│ │числа │┌──>│части │ │ │┌──>│части │
└───────┘ └───────┘│ └───┬───┘ └───────┘│ └───┬───┘
│ d │ │ d │
└───────┘ └───────┘
ш0
Рис. 9. Граф переходов (пример вещественного числа)
- 33 -
Ниже приведен текст процедуры-функции, реализующей
распознавание числа.
function Read_Real:boolean;
const final=[4];
var s : 0..4;
ch : char;
{ Error - внешняя процедура обработки ошибок }
begin
s:=0;
while not eoln do
begin
read(ch);
if ch in ['+','-','0'..'9','.'] then
case s of
0 : if (ch='+') or (ch='-') then s:=1
else if ch in ['0'..'9'] then s:=2
else Error;
1 : if ch in ['0'..'9'] then s:=2
else Error;
2 : if ch='.' then s:=3
else if not(ch in ['0'..'9']) then Error;
3 : if ch in ['0'..'9'] then s:=4
else Error;
4 : if not(ch in ['0'..'9']) then Error;
end
end;
Read_Real:= (s in final)
end;
Обратите внимание, что приведенная программа "дословно"
соответствует диаграмме переходов, то есть наличие диаграммы
существенно облегчает процесс написания программы.
В приложении 1 приведен текст программы, включающей ска-
нер для распознавания лексем: целое число (возможно со зна-
ком), знак операции, конец строки.
.
- 34 -
24.4. Пример сканера для языка PL/0
В качестве примера лексического анализатора рассмотрим
сканер Вирта [3], предназначенный для распознавания лексем
специального учебного языка PL/0. В приложении 2 приведены
синтаксические диаграммы этого языка.
Сканер оформлен в виде процедуры Getsym и выполняет сле-
дующие действия:
1) пропускает пробелы,
2) распознает разделители,
3) распознает служебные слова,
4) распознает незарезервированные слова как идентификато-
ры,
5) распознает последовательности цифр в качестве целых
чисел (значение числа присваивается переменной num),
6) распознает знак присваивания ':='.
Внутри процедуры Getsym описана локальная процедура чте-
ния очередной литеры : Getch. В тексте используется внешняя
процедура обработки ошибок: Error.
Для хранения служебных слов учебного языка PL/0 предназ-
начен массив word. Дополнительно, в массиве wsym хранятся типы
(символы), приписанные служебным словам, а в массиве ssym хра-
нятся типы разделителей, таких как "равно", "запятая", "точка"
и пр. В следующем фрагменте приведены некоторые описания.
Const
norw=11; {количество служебных слов}
txmax=100; {длина таблицы имен}
nmax=14; {максимальное количество цифр в записи числа}
al=10; {максимальная длина идентификатора}
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 |
