Непейвода Н.Н., Скопин И.Н. Основания программирования

Подождите немного. Документ загружается.

10.3. СИНТАКСИЧЕСКИЕ ТАБЛИЦЫ

595

Таким образом,для систем конечных автоматов локальность условий игра-

ет более значительную роль, чем хранимые на стеке данные для автоматов со

стековой памятью. Именно поэтому класс систем конечных автоматов, свя-

занных стеком, значительно шире класса всех автоматов со стековой памя-

тью: он моделирует машины Тьюринга. Этот класс оказывается эффектив-

ным и содержательным для описания достаточно широкого класса алгорит-

мов, в частности анализаторов контекстно-свободных языков. Но путь ис-

пользования систем конечных автоматов общего вида уже ведет к сентенци-

альному программированию. Если же оставаться в рамках программирова-

ния от состояний, то нужно сузить обсуждаемый класс, рассматривая лишь

такие системы,которые позволяют работать при выполнении инварианта это-

го стиля. Для конкретной задачи синтаксического анализа такими являют-

ся системы, которые в состоянии работать без возвратов по обрабатываемой

строке.

Переход от автоматов в возвратами к безвозвратной схеме и условия ее

реализации рассмотрены Д. Кнутом в статье [Top-down analysis], в которой

формализуется класс так называемых нисходящих методов синтаксическо-

го анализа. Примечательно, что этот подход хорошо ложится в русло стиля

программирования от состояний, что будет показано в ближайших разделах.

10.3.2. Задача анализа простых выражений

Рассмотрим задачу, которая достаточно часто встречается на практике.

Она возникает в каждой программе, требующей распознавания и анализа

сложных структур исходных данных, прежде всего, таких, которые зада-

ны в виде последовательностей символов. Например, в каждом транслято-

ре требуется распознавать контекстно-свободную структуру анализируемого

текста. Именно в таком частном случае был осознан и кодифицирован опи-

сываемый ниже общий метод анализа.

Задача решается путем построения комплекта конечных автоматов, ка-

ждый из которых в состоянии распознать во входном потоке последователь-

ность символов,удовлетворяющую определению соответствующей конструк-

ции языка. В ходе такого распознавания автомату может потребоваться обра-

титься к другому автомату, который в состоянии выяснить наличие или отсут-

ствие во входном потоке вложенной конструкции. Чтобы обеспечить взаимо-

действие автоматов, нужно договориться о том, что они продуцируют в каче-

стве выхода, и как этот выход будет использован. Поскольку распознавание

вложенной конструкции для использующего автомата концептуально подоб-

но распознаванию лексемы (в нашем примере — символа), целесообразно

596

ГЛАВА 10. МЕТОДЫ ПРОГРАММИРОВАНИЯ ОТ СОСТОЯНИЙ

сделать эти две ситуации унифицированными. Иными словами, обращение

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

из состояния в состояние (см. рис. 10.4, на котором использование автомата

Действие

S13

Действие

S12

<Вложенная

конструкция>

Действие

S14

Рис. 10.4. Обращение к автомату для распознавания вложенной конструкции

изображено в виде его имени в угловых скобках).

Однако только что представленное прямое решение не является до кон-

ца продуманным. Здесь не учитывается, что при распознавании вложенной

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

По определению условия срабатывания перехода это означает, что, если кон-

струкция не распознана, то использующий автомат должен получить вход-

ной поток в том виде, в котором он был непосредственно перед обращением

к автомату. В результате придется моделировать двойное движение по пото-

ку. Это возможно (например, с помощью дополнительной памяти), однако

неэффективно.

По этой причине обычно принимаются дополнительные со-

Когда приходится прибегать к такому моделированию, это сигнал о том, что метод ко-

нечных автоматов для решаемой задачи начинает давать сбои. В таких случаях, быть может,

10.3. СИНТАКСИЧЕСКИЕ ТАБЛИЦЫ

597

глашения, которые отражают стратегию обработки потока, которая, в свою

очередь, делает так, что все экземпляры автоматов оказываются в состоянии

работать с одним потоком.

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

рядоченность проверок условий срабатывания: обращение к другому авто-

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

ваны. Чаще всего этого соглашения недостаточно, например, когда вариан-

ты включают распознавание нескольких конструкций, но в ряде случаев оно

позволяет сделать систему автоматов работоспособной. Более строгий под-

ход — ограничиваться применением метода ситуациями, когда все вариан-

ты переходов разделяются: множества символов, с которых могут начинать-

ся вложенные конструкции, не пересекаются между собой и с множеством

меток простых переходов. В этом случае по первому символу входного по-

тока можно детерминировать выбор простого перехода или перехода к рас-

познаванию соответствующей вложенной конструкции.

Тогда за счет загля-

дывания вперед можно решить, надо ли фактически обращаться к дополни-

тельному автомату.

Принятие этих соглашений влечет за собой неприятное следствие: нача-

ло конструкции обнаружено, обращение к дополнительному автомату про-

изошло, но он оказался не в состоянии распознать конструкцию. Это случай,

когда входной поток не соответствует требуемой структуре, иными словами,

в нем обнаружена ошибка. Таким образом, унифицированное для простых

переходов и для переходов к конструкциям представление должно предусма-

тривать в проверках возможность не двух, а трех исходов (для простых пе-

реходов возможны только первые два варианта исходов):

• T, если автомат завершил распознавание конструкции успешно;

• F, если автомат обнаружил без продвижения по входному потоку, что

данная конструкция отсутствует;

• E, если начато распознавание конструкции (т. е. произошло продвиже-

ние по входному потоку), но автомат завершил работу, выяснив, что

естественнее перейти к сентенциальному решению задачи, приспособленному к организа-

ции недетерминированного движения к цели и возвратам к пройденному, когда очередная

попытка оказывается неудачной.

Если допускается, что конструкция порождается как пустая последовательность симво-

лов, то условие детерминирования необходимо дополнить требованием отсутствия пересе-

чения указанных множеств с множеством символов, возможно следующих за конструкцией.

598

ГЛАВА 10. МЕТОДЫ ПРОГРАММИРОВАНИЯ ОТ СОСТОЯНИЙ

данная конструкция неправильна.

Выстраивание проверок в последовательность для выяснения условия сра-

батывания перехода дает дополнительную возможность повышения вырази-

тельности метода. Она связана с тем, что становится осмысленным припи-

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

проверок (см. рис. 10.5, на котором упорядоченные проверки условий сра-

…

Действие F

Sне<Вложенная констру кция>

ДействиеF

Sнеb

ДействиеF

Sнеa

ДействиеT

S13

ДействиеT

S12

<Вложенная конструкция>

ДействиеT

S14

…

ДействиеE

Sне<Вложенная конс трукция>

Рис. 10.5. Автомат с упорядоченными проверками условий срабатывания пе-

реходов

батывания переходов помечены символами исходов и вынесены за изобра-

жение состояния). Разумеется, с точки зрения теории вычислительная мощ-

ность автомата не меняется, однако для логики конкретных программ полез-

но иметь такую возможность. Заметим, что она потребует другого формата

таблиц, представляющих конечный автомат, нежели те, которые мы исполь-

зовали при решении задачи о длинах слов. Как и прежде, мы не будем опи-

сывать структуру таблиц в общем виде, а представим их на примере решения

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

Рассмотрим синтаксическое определение, порождающее простейшие вы-

10.3. СИНТАКСИЧЕСКИЕ ТАБЛИЦЫ

599

ражения языка

и оператор присваивания.

<оператор присваивания> ::=

<идентификатор> “=” <выражение>

<выражение> ::=

<множитель> [ “+” <выражение> |“-” <выражение>]*

<множитель> ::=

<терм> [ “*” <множитель> |“/” <множитель> ]*

<терм> ::= <идентификатор> |“(” <выражение> “)”

<идентификатор> ::= [ “a” |“b” |“c” ]

(10.1)

Эти правила несколько отличаются от используемых при определении вы-

ражений и приоритетов операций языка

. В прежнем стиле выражение и

множитель определялись в соответствии с правилами вычисления выраже-

ний:

<выражение> ::= <множитель> |

<выражение> [ “+” <множитель> |“-” <множитель>]*

<множитель> ::= <терм> |

<множитель> [ “*” <терм> |“/” <терм>]*

(10.2)

тогда как по определению (10.1) выражения с операциями одного уровня ста-

новятся правоассоциативными (сравните два вывода строки

"a-b-c"

в двух

грамматиках). Чуть ниже станет понятно, почему здесь выбраны “плохие”

правила,а также разъяснено,как их можно чисто формально исправить. Важ-

но подчеркнуть, что способ исправления демонстрирует метод работы безот-

носительно данного примера.

Система конечных автоматов для анализа контекстно-свободных языков

по их грамматике строится достаточно прямо. Для каждого нетерминального

символа составляется таблица — диаграмма автомата, отражающая все ва-

рианты его работы. Так, для присваивания строится следующая диаграмма

(см. таблицу 10.2). Первая строка таблицы — заголовок автомата. Она содер-

жит имя автомата, по которому происходит обращение к нему (мы исполь-

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

их связь с нетерминальными символами грамматики). Остальные строки та-

блицы описывают работу автомата.

Первая колонка используется для организации переходов между состо-

яниями (аналог первой колонки таблицы 10.1). Из-за простоты структуры

получающихся таблиц надобность в явном именовании всех состояний ка-

ждого автомата отпадает: большинство переходов при синтаксическом ана-

600

ГЛАВА 10. МЕТОДЫ ПРОГРАММИРОВАНИЯ ОТ СОСТОЯНИЙ

<оператор присваивания>

<идентификатор

> T /*

определен получатель значения

F /*

это не оператор присваивания

*/ F

E /*

это лишняя графа — см. ниже

*/ E

“=” T

F E

<выражение

> T /*

определен источник значения

*/ T

F /*

ошибка: нет выражения

*/ E

E /*

ошибка в выражении (распространя-

ется на оператор)

Таблица 10.2. Диаграмма для присваивания

лизе — это переходы к следующей строке, а для указания других переходов

оказывается достаточно простых меток.

Вторая колонка, которая используется для задания так называемых кон-

ституент, т. е. составляющих синтаксического правила (терминальных и

нетерминальных символов), аналогична второй колонке таблицы 10.1, т. е.

условиям срабатывания переходов. Но здесь нецелесообразно задавать про-

верки явно:само вхождение конституенты указывает на то,что надо сравнить

ее с символом входного потока или вызвать другой конечный автомат. В ре-

зультате выполнения такого сравнения должен быть выработан один из трех

исходов: T, F или E. Три или два (для терминальных символов) варианта ис-

хода выделены как три подстроки таблицы с соответствующими пометками

в третьей колонке.

Четвертая колонка предназначена для задания действия, ассоциирован-

ного с переходом, а точнее — c вариантом исхода проверки.

Наконец, пятая колонка, называемая полем продолжения, используется,

чтобы указать, куда должен переходить автомат в дальнейшем:

a) незаполненность поля продолжения означает переход к следующей стро-

ке;

b) если в поле продолжения указана метка (в нашей нотации задаются число-

вые метки), то следующее состояние автомата — это та строка, которая

помечена данной меткой (если такой строки нет, то таблица составлена

некорректно);

c) если в поле продолжения задан один из трех исходов T, F или E, то это

10.3. СИНТАКСИЧЕСКИЕ ТАБЛИЦЫ

601

означает, что текущий автомат завершает свою работу с указанным исхо-

дом, который передается автомату, вызвавшему данный автомат;

d) другое заполнение поля продолжения считается некорректным.

Если все таблицы оказались такими, что все варианты переходов разде-

ляются (это возможно для грамматик, относящихся к классу, получившему

название

LL(1)

), то система автоматов, вычисления которых интерпретиру-

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

Но чтобы она анализировала тексты правильно, необходимо правильно рас-

ставить все переходы (иначе мы имеем дело с автоматами, которые не соот-

ветствуют грамматике, и распознают другой язык).

Правила для составления таблиц-диаграмм можно восстановить по при-

водимым примерам (см. таблицы 10.3 – 10.6, каждая из которых соответству-

ет нетерминальному символу грамматики, указанному в заголовке таблицы).

Они сводятся к последовательному выписыванию конституент во второй ко-

лонке и связыванию их переходами, соответствующими вариантам правил и

повторениям конституент.

<выражение>

<множитель

> T

F /*

распознано, что выражения нет

*/ F

E /*

ошибка в множителе

*/ E

2 “+” T

F 1

<выражение

> T /*

зацикливание

*/ 2

F /*

после “+” нет выражения

*/ E

E /*

ошибка в выражении

*/ E

1 “-” T

F /*

распознано выражение

*/ T

<выражение

> T 2

F /*

после “-” нет выражения

*/ E

E /*

ошибка в выражении

*/ E

Таблица 10.3. Диаграмма для выражения

10.3.3. Синтаксические таблицы и рекурсивный спуск

602

ГЛАВА 10. МЕТОДЫ ПРОГРАММИРОВАНИЯ ОТ СОСТОЯНИЙ

<множитель> /*

все аналогично

<терм

> T

F F

E E

2 “*” T /*

пример того, что можно объединить

два вызова понятия (ср. c

<выраже-

ние>

)

F 1

1 “/” T

F T

0 <множитель> T 2

F E

E E

Таблица 10.4. Диаграмма для множителя

Приведенная система таблиц может быть без труда систематически пере-

писана в комплект рекурсивных процедур Например, для оператора присва-

ивания можно написать следующую функцию, закодировав T, F и E целыми

константами:

Программа 10.3.1

int Assignment()

{

switch (Identiﬁer())

{

case T:

if (current_symbol==‘=‘)

{ get_next_symbol();

switch (Expression())

{

case T: return T;

case F: return F;

case E: return E;

}

else return E;

}

10.3. СИНТАКСИЧЕСКИЕ ТАБЛИЦЫ

603

<терм>

<идентификатор

> T /*

терм — идентификатор

*/ T

F /*

возможен другой вариант

E E

“(” T /*

далее должны быть

<выражение>

“)”

F /*

распознано, что терма нет

*/ F

<выражение

> T

F E

E E

“)” T /*

терм — идентификатор

*/ T

F E

Таблица 10.5. Диаграмма для терма

<идентификатор>

“a” T T

“b” T T

“c” T T

F F

Таблица 10.6. Диаграмма для идентификатора

case F: return F;

case E: return E;

}

Функция

Assignment

вызывает функцию

Identiﬁer

и проверяет ее исход (три

варианта для оператора

switch

).Эти операторы и все другие действия,включая

выставление соответствующих исходов, в точности повторяют то, что запи-

сано в таблице 10.2. В принципе при составлении таких функций вполне

можно обойтись без таблиц, руководствуясь лишь грамматическими прави-

лами. В этом случае мы получим в точности то же самое решение, которое

было представлено в § 11.6 при обсуждении метода рекурсивного спуска,

включая появляющиеся в процедурах циклы. Однако есть причины, по кото-

рым диаграммное решение предпочтительнее:

604

ГЛАВА 10. МЕТОДЫ ПРОГРАММИРОВАНИЯ ОТ СОСТОЯНИЙ

a) наглядность табличных диаграмм гораздо выше, чем при прямом кодиро-

вании правил в методе рекурсивного спуска;

b) появляется возможность отделить в тексте программы часть, ответствен-

ную за контекстно-свободный анализ, от других частей транслирующей

системы: от анализа контекстных зависимостей и от генерации следую-

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

расширенного конечного автомата можно рассматривать как средство де-

композиции задачи;

c) ничто не препятствует и трансляционной реализации структуры управле-

ния программы (см. выше), которой по существу является рекурсивный

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

мать представление таблиц как задание для интерпретации. В ряде случа-

ев одно из этих решений может оказаться предпочтительнее;

d) отдельное описание синтаксиса может быть отдельно проверено, в част-

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

ства системы автоматов. В частности, довольно легко выяснить левую

бесконечную рекурсию, которая возникнет, если исходное определение

грамматики содержит леворекурсивные нетерминальные символы

10.3.4. Преобразования грамматики,сохраняющие язык. Вычислитель-

ная мощность синтаксических таблиц

Последнее замечание в перечне из предыдущего раздела заслуживает осо-

бого рассмотрения. Заметим, что леворекурсивные нетерминальные симво-

лы — непреодолимое препятствие для обсуждаемого метода.Если допустить

их, то ни при каких условиях не удастся достичь разделяемости правил грам-

матики (см. стр. 595), а значит, не удастся сохранить соглашение о едином по-

токе для всех конечных автоматов системы. Именно поэтому для иллюстра-

ции мы выбрали определение простых выражений в виде (10.2), посколь-

ку согласованное с порядком вычислений определение (10.3) привело бы к

построению некорректных таблиц (к рекурсивному зацикливанию процесса

анализа).

Нетерминальный символ

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

→ ∗

α, где α — любая строка из терминальных и нетерминальных символов. В этом

случае выбранный метод анализа ведет к зацикливанию работы автомата без продвижению

по анализируемой строке, т. е. к бесконечному зацикливанию.