Virt N. Algoritmy struktury dannyh = programmy (ru)(T)(410s) (522393), страница 56
Текст из файла (страница 56)
(5.7) Здесь «+ъ, х, (, н) — терминальные символы, а ( к ) прннадлежит расшнренной БНФ и, следовательно, являются мета- символами. Язык, порождаемый нз А, состоит нз выраженнй с операндами х, знаком операцнн «+» и скобками. Примеры предложений: (х) (х+ х) ((х)) Графы, полученные с помощью прнмевення шести правил построения графов, показаны на рнс. 5А, Заметим, что зту снстему графов можно свести в один граф, подставив соответственно С в В и В в А (см. рнс. 5.2). (Сннтакснческнй граф является зквкнвалентным представленнем грамматики языка; его можно использовать вместо зз1 дз.
Построение синтаксического графа множества порождающих правил БНФ. Это очень удобная форма, и во многих (если ие в большинстве) случаев она предпочтительнее БНФ. Разумеется, граф дает более ясное и точное представление о структуре языка, а также позволяет лучше представить себе процесс грамматического разбора. Рнс. 5.1. Синтаксические графы ддн сннтакснса прим. $. Граф является подкодяи1им представлением, котоцое может служить отправкой точкой для разработчика языка..',Примеры полных определений языков с помощью синтаксйческих графов даны в равд.
5.7 для ПЛ/О и в приложении В для Паскаля. Рнс. $.2, Сводный синтаксический граф, соответствующнй прим. 3. ) Для того чтобы обеспечить детерминированный грамматический разбор с просмотром вперед на один символ, были установлены ограничения 1 и 2. Как проявляются эти ограничения при графическом представлении синтаксиса? Здесь особенно наглядно видны удобство и ясность такого представления.
1. Ограничению 1 соответствует требование, чтобы при каж. дом разветвлении можно было выбрать ветвь, по которой А Структура»вико« и трансляторы будет идти дальнейший разбор по очередному символу на этой ветви. Это означает, что никакие две ветви не должны начинаться с одного и того же символа.
2. Ограничению 2 соответствует требование, чтобы если какой-либо граф А можно пройти, не читая вообще никаких входных символов, то такая «нулевая ветвь» должна помечаться всеми символами, которые могут следовать за А. (Это влияет на решение о переходе на эту ветвь.) Легко проверить, удовлетворяет ли некоторая система графов этим двум ограничениям, не обращаясь к представлению грамматики с помощью БНФ.
В качестве вспомогательного шага для каждого графа А определяются множества 1(тз((А) и 1о((оту(А). Затем непосредственно можно проверить выполнение ограничений 1 и 2. Систему графов, которая удовлетворяет этим двум ограничениям, мы будем называть детерминированным синтаксическим графом " Эии ПОСТРОЕНИЕ ПРОГРАММЫ ГРАММАТИЧЕСКОГО РАЗБОРА ДПЯ ЗАДАННОГО СИНТАКСИСА Г Программу, которая распознает какай-либо язык, легко построить на основе его детерминированного синтаксического графа (если такой граф существует).
Этот граф фактически представляет собой блок-схему программы. Но при ее разработке рекомендуется строго следовать правилам преобразования, подобным тем, с помощью которых можно предварительно получить из БНФ графическое представление синтаксиса. Эти правила перечислены ниже. Они применяются в определенном контексте, который предполагает наличие основной программы, содержащей процедуры, которые соответствуют различным подцелям, а также процедуру перехода к очередному символу. Для простоты мы будем считать, что предложение, которое нужно анализировать, представлено файлом (нри1 н что терминальные символы — отдельные значения типа сйаг, Пусть символьная переменная сй; сйат всегда содержит очередной читаемый символ.
Тогда переход к следующему символу выражается оператором теис((сй) Основная программа будет состоять из оператора чтения первого символа, за которым следует оператор активации основной цели грамматического разбора. Отдельные процедуры, соответствукпцие целям грамматического разбора или графам, получаются по следующим правилам. Пусть оператор, полученный с помощью преобразования графа 5, обозначаетсяя через Т (л) . б,в. Посгроемаа программы грамма»а««свого разбора 333 Привила преобризовипия графа в программу; В1. Свести систему графов к как можно меньшему числу отдельных графов с помощью соответствующих подстановок.
В2, Преобразовать каждый граф в описание процедуры в соответствии с приведенными ниже правилами ВЗ вЂ” В7. ВЭ. Последовательность элементов переводится в составной оператор В4. Выбор элементов переводится в выбирающий или условный оператор и сй 1я г, тмев У(а1) е1яе | 11 сй 1в Ь„!Ьеп Т(Я„) е1зе епог где Ь означает множество начальных символов конструкции 5; (»л = 11гз1(5~)). Примечание. Если Ь состоит из одного символа и, то, разумеется, вместо «сй)п(.,» нужно писать «сй = и». Вб. Цикл вида б.
Структура яаыкоа и тряисяяторы 334 переводится в оператор где Т(о) есть отображение о в соответствии с правилами ВЗ вЂ” В7, а т". есть множество Е *1(гз1(8) (см. предыдущее примечание). Вб. Элемент графа, обозначавший другой граф А — Е)- переводится в оператор обращения к процедуре А. В7. Элемент графа, обозначающий терминальный символ переводится в оператор где еггог — процедура, к которой обращаются при по. явлении неправильной конструкции. Теперь покажем применение этих правил на примере преобразования редуцированного графа, изображенного на ргейгага роше (1лриб оигрта); чаг сЬ: сйаг; ргесейше А; Ъеяа Ы сЬ 'х' йеп геаа(сЬ) е1ае М сЬ ° '(' тйеп Ьей)п гсаА(сЬ); А; ттййе сЬ = '+' йо Ьея)п гоаб(сЬ); А евй; Ы сЬ ')' Феп геаА(сЬ) е)ае еггог епй е1яе сггог епй; Ъея)п ген(сЬ); А епй Программа 3.1.
Грамматический разбор дяя синтаксиса из прим. б рис. 5,2 (пример 5), в программу грамматического разбора (программа 5.1): 6.4. Построение нрограммы грамматического разбора ЗЗЗ При этом преобразовании свободно применялись некоторые очевидные правила программирования, позволяющие упростить программу. Например, при буквальном переводе четвертая строка имела бы внд Кой =- 'х'гпеп И сй = 'х' 1йеп теагг(сй) еЬе еггот е!зе. ° ..
Ясно, что ее можно сократить, как это сделано в программе. Операторы чтения в пятой н седьмой строках тоже получены с помощью такого же упрощения. '(По-видимому, полезно определить, когда вообще возможны подобные упрощения, и показать это непосредственно в анде графов. Два основных случая покрываются следующими дополнительными правилами: В4а Вба Кроме того, часто встречающуюся конструкцию таам(сй); Т(о) ттЫ!е гг Фе Ъаигп геай(сй); Т(о) епй Ь. Структура взыков и тракт.итвры можно, разумеется, выразить короче: гереа1 геад(сп); Т(5) ппШ В (5.8) й(ы намеренно не описываем пока процедуру еггог («ошибка>).
Поскольку сейчас нас интересует лишь, как определить, правильно ли входное предложение, мы можем считать, что эта процедура заканчивает работу программы. Конечно, на практике в случае появления неправильных конструкций нужно использовать более тонкие приемы. Они будут рассматриваться в равд. 5,9, 3.%. ПОСТРОЕНИЕ ТАБЛИЧНО«УПРАВЛЯЕМОЙ ПРОГРАММЫ ГРАММАТИЧЕСКОГО РАЗБОРА Вместо того чтобы для каждого языка составлять специальную программу по правилам, изложенным в предыду. шем разделе, можно построить одну, универсальную программу грамматического разбора, Конкретные грамматики задаются этой универсальной программе в виде исходных данных, предшествующих предложениям, которые нужно разобрать.
Универсальная программа работает в строгом соогветствии с методом простого нисходящего грамматического разбора; поэтому она довольно проста, если основана на детерминированном синтаксическом графе, т. е. если предложения можно анализировать с просмотром вперед на один символ без возврата. Итак, грамматика,~мы предполагаем, что она представлена в виде детерминированного множества синтаксических графов) преобразуется в подходящую структуру данных а не в структуру программ (5.2]. Естественный способ представить граф — это ввести узел для' каждого символа н связать эти узлы с помощью ссылок.
Следовательно, «таблиц໠— это не просто массив. Правила преобразования очевидны н приведены ниже. Узлы этой структуры представляют собой записи с вариантами, один для терминального, а другой — для нетерминального символа. Первый идентифицируется терминальным символом, который он обозначает, второй — ссылкой на структуру данных, представляющую соответствующий нетерминальный символ. Оба варианта содержат две ссылки: одна указывает на следующий символ, последователь (зис), а другая связана со списком возможных альтернатив (аВ).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
