то это же предложение получит другую структуру, kotodv можно выразить как {а - {Ь - с)). Учитывая принятое зн чение вычитания, мы видим, что эти две формы вовсе не экв^ валентны с точки зрения семантики.

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

5.3. ПОСТРОЕНИЕ СИНТАКСИЧЕСКОГО ГРАФА

В предыдущем разделе был описан алгоритм нисходящего распознавания, применимый к грамматикам, которые удовлетворяют ограничениям 1 и 2. Теперь мы перейдем к реализации этого алгоритма в виде конкретной программы. При этом-можно использовать дбз различных метода. Один из них -это написать универсальную программу нисходящего грамматического разбора, пригодную для всех возможных грамматик (удовлетворяющих ограничениям 1 и 2). В этом случае конкретные грамматики задаются этой программе в виде данных некоторой структуры, которая в каком-то смысле управляет ее работой. Поэтому такая программа называется таблично-управляемой. Другой метод - разрабатывать программу нисходящего грамматического разбора специально для заданного конкретного языка; при этом его сит-таксис по определенным правилам отображается в последо- , вательность операторов, т. е. в программу. Мы по очереди рассмотрим оба этих метода, каждый из которых имеет свои преимущества и недостатки. При построении транслятора для конкретного языка программирования вряд ли потребуется высокая гибкость и параметризация, свойственные универсальной программе, тогда как программа грамматического разбора, предназначенная специально для данного языка, обычно оказывается более эффективной и с ней легче работать, поэтому такой подход предпочтителен. В обоих случаях полезно представлять заданный синтаксис в виде так называемого синтаксического графа, или графа распознавания-Такой граф отражает управление ходом работы при грамматическом анализе предложения.

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

о.а. построение синтаксического графа

Жим разбором. При построении программы грамматического збора можно воспользоваться этим очевидным соответ-jjbhem между нетерминальными символами и целями: для аясдого нетерминального символа строится своя процедура грамматического разбора. Цель каждой такой процедуры - распознавание части предложения, которая может порождаться из соответствующего нетерминального символа. По--р{{ел.ьку мы хотим построить граф, представляющий всю программу грамматического разбора, то каждый нетерминальный символ будет отображаться в подграф. Поэтому мы приходим к таким правилам построения синтаксического графа:

правила построения графа:

Д1. Каждый нетерминальный символ А с соответствующим множеством порождающих правил

Ш А::==Ш2\.--Л1п

Щ отображается в синтаксический граф Л, структура кото- рого определяется правой частью порождающего правила

в соответствии с А2 - А6. А2. Каждое появление терминального символа х в ,- соответствует оператору распознавания этого символа во входном предложении. На графе это изображается ребром, помеченным символом х, заключенным в кружок.

A3. Каждому появлению нетерминального символа В в g,- соответствует обращение к процедуре распознавания В. На графе это изображается ребром, помеченным символом

А4. Порождающее правило, имеющее вид

А::=1А.--\1п отображается в граф

-ч

<

>

где каждое получено применением правил А2.

Аб к Ь-А5. Строка I, имеющая вид

= а,а2 ... о„ отображается в граф

где каждое получено применением правил А2-Дб

Аб. Строка I, имеющая вид

отображается в граф

где получено применением правил А2-Аб к а.

Пример 5:

А

В С

-хНВ). АС, {+А}.

(5.7)

Здесь X, (, и) - терминальные символы, а { и } принадлежит расширенной БНФ и, следовательно, являются метасимволами. Язык, порождаемый из А, состоит из выражений с операндами х, знаком операции + и скобками. Примеры предложений:

(х+х) (W)

Графы, полученные с помощью применения шести правил построения графов, показаны на рис. 5.1. Заметим, что эту систему графов можно свести в один граф, подставив соответ' ственно С в В и В в А (см. рис. 5.2).

Синтаксический граф является эквкивалентным представлением грамматики языка; его можно использовать вместо