Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 21
Текст из файла (страница 21)
(2) Дуга, ведущая из и, в и, заменяется либо (в случае а) дугой из и, в и, либо (в случае б) дугами, ведущими нз обеих вершин и, й и, в вершину п, либо (в случае а) дугой из а, в и. В веРшинах па и и, пРовеРЯютсЯ пРедикаты, гюэтомУ их нельзя заменять структурами. Другие вершины представляют программы и их можно заменять далее. Построим с(-схему, соответствующую программе вида П В, бтеп ыгИ1!е В, до 11 В, 1Иеп 5, е1ае 5, епд спи; !.а. дРуГие пРилОжения АПГОРитмОВ РА3БОРА и пеРБВодА ГЛ. !. ВВЕДЕНИЕ В КОМПИЛЯЦИЮ Рис.
!.!О. Окоичатсаьиая !1-схема; рис, 1,11. Вершины дерева помечены соответствующими вершинами или контурами 6-схемы. !"! Приведенный пример в некотором смысле является подделкой. Структура д-схел!ы, 'изображенная на рис. 1.11,— это по существу структура, которую построит для первоначальной программы компилятор па этапе синтаксического анализа. Таким образом, похоже, что мы обсуждаем тот же тип синтаксического анализа, что и в равд. !.2.3.
Однако следует иметь в виду, что этот структурный анализ можно проделать, не ссылаясь на программу, а глядя только на !1-схему. Более того, мы привели этот пример графопорождающей грамматики из-за его связи Рис. 1.9. Построеиие д-схемы; с! ' Вз Вк Л! Пк Са Ва ВБ Нв Рис. 1.11. Лереио, описыиа!ои!ее структуру с1-схемы, е1зе И В, Фен 5,; 5,; лт!111е В, Йо 5, епд е1зе 5а еп!! ей!! Всю программу можно представить в виде И В, !!лен 5, е1зе 5, епс1, где 5, представляет всю часть от первого АУЫ!е до 5„ а 5, представляет И В, ...
5, епе!. Это первый шаг анализа программы, соответствующий замене одной вершины структурой б на рис. 1.3. Продолжая анализ, представим 5„в виде 5а,; 5, (5!е — это АУЫ!е В, ... 5, епе! епс!). Таким образом, этот шаг анализа соответствует замене вершины л, на рис.
1.3, б графом а. Результат показан на рис. 1.9, а. Далее, 5„имеет вид лт!л!1е В, е!о 5п епе1, где 5,„— это И Ва... 5, епе!. Тогда можно заменить левого прямого потомка корня дерева на рис. 1.9, и структурой, изображенной на рис. 1.8, а. Результат показан на рис. 1.9, б. Окончательный результат нашего анализа данной программы показац иа рис. 1.10. Здесь мы позволили себе нарисовать контуры вокруг зал!еняемых вершин; заметим, что каждая из последовательных замен осуществляется внутри контура. Таким образом, на г1-схему можно наложить естественную древовидную структуру, в которой вершины г1-схемы будут листьями, а контуры — Внутренними вершинами дерева. 11рямым предком вершины дерева будет контур, непосредственно окружающий ее представление в д-схеме. Соответствующее дерево показано на / l / / / / / / ! ! ! ! ! ! ! ! ! ! ! л с Се ~ 1 1 ! 1 ! / / l I / ЗАМЕЧАНИЯ ПО ЛИТЕРАТУРЕ Замечания по литературе 103 с языками программирования, но существует много чисто теоретико-графовых понятий, которые можно определить с помощью грамматик, порождаюрдих графы (обобщив подходящим образом пример 1.8),— класс планарных графов, например, или класс бинарных деревьев, Трудности, возникающие при попытках найти удовлетворительную грзммзтнческую модель для зпглийского языка, хороню представлены в книге Хомского [1965[.
Бобров [1963] дает обзор усилий, пзпрзвлеииых нз использовзние английского языка, илн, точнее, некоторого его подмножества, в кзчсстве языка программирования. Обзор теоретических аспектов лингвистики соде жится в кинге Бзр-Хнллелз [1964] '). Ь онятие гпзммзтикн, порождающей графы, взято нз работы Пфзльпв н Розенфельде [!969], теории этих грамматик посвящены статьи Моитзнзри [1970] н Пзвлндисз [1972). Одна из первых работ по синтаксическому внзлизу образов припедлежит Шоу [1970]. Обзор некоторых результатов, полученных в этой области, можно найти у Миллере н Шоу [1968]').
') Рекомендуем также сборник „Автоматический перевод" [1971], книгу Виногрздз [1972] н статьи Цейтннз [1971] и Вудса !1970),— 17рим. перев. з) См. также [Абэ н др., 1973] н [Фу, 1974].— Прим. перев. 2 элеиенты тео~ии языков В этой главе мы займемся аспектами теории формальных языков, существенными с точки зрения синтаксического анализа и перевода, Вначале рассмотрим синтаксические аспекты языка, Но так как ббльш ю часть синтаксиса сов еменпы язык в нога йя можно опуса о ью контекс -сво- о ных г амматик мы обратим особое внимание на теорию контекстно-свободных языков.
Сначала изучим один важный подкласс контекстно-свободных языков, а именно регулярные множества. Понятия теории регулярных множеств находят широкое применение и встречаются во многих разделах этой книги. Другой важный подкласс языков образуют детерминированные контекстно-свободные языки. Это контекстно-свободные языки, грамматики которых допускают простой синтаксический анализ. По счастливому случаю или из-за того, что нх преднамеренно создают такими, современные языки программирования можно с хорошим, хотя и нс полным приближением считать детерминированнымн контекстно-свободными языками. Для этих трех классов языков--контекстно-свободных, регулярных и детерминированных контекстно-свободных — мь1 дадим их точные определения и опишем основные свойства. Так как теория языков очень обширна и нс все в ней имеет отношение к синтаксическому анализу и переводу, доказательства некоторых ее важных теорем приводятся в виде наброска или выносятся в упражнения.
Аты стараемся особо выделять только те аспекты теории языков, которые полезны для изложения дальнейшего материала книги. Как и в гл. О и 1, читатель, знакомый с теорией языков, может пропустить или бегло просмотреть эту главу. 2.1. СПОСОБЫ ОПРЕДЕЛЕНИЯ ЯЗЫКОВ В этом разделе с общей точки зрения будут рассмотрены два основных механизма определения языков — механизм порождения, или генератор, и механизм распознавания, или распозна- ГЛ. 2. ЭЛЕМЕИТЫ ТЕОРИИ ЯЗЫКОВ ватель. Мы обсудим только генераторы самого распространенного типа — грамматики Хамского, з распознаватели рассмотрим с несколько большей степенью общности и введем в последующих разделах некоторые из многих типов распознаватече, те.чей, изучавшихся в литературе.
2ЛЛ. Мотивировка Мы определяем язык Ь как множество цепочек конечной длины в алфавите Х, опрос: как описать я в убтг-случке; кбгда он бесконечен. Разумеется, если Е состоит из конечного числа цепочек, то самый очевидный способ — составить список всех цепочек йз Е. Однако для многих языков нельзя (или, быть может, нежелательно) установить верхнюю границу длины самой длинной цепочки языка. Следовательно, приходится рассматривать языки, содержащие сколь угодно много цепочек. Очевидно, что такие языки нельзя определить исчерпывающим перечислением входящих в них цепочек, и, стало быть, надо искать другие способы их описания. Как и прежде, мы хотим, чтобы описание языка было конечным (имело конечный „объем"), хотя описываемый язык может быть и бесконечным.
Известно несколько методов описания языков, удовлетворяющих этому требованию. Один из них состоит в использовании порождающей системы, называемой грамматикой. Цепочки языка строятся точно определенными способами с применением правил грамматики, Одно из преимуществ определения языка с помощью грамматики в том, что операции, производимые в ходе синтаксического анализа и перевода, можно сделать проще, если воспользоваться структурой, которую грамматика приписывает цепочкам („предложенням") языка.
Грамматики, особенно контекстно- свободные, мы язучим очень подробно. Второй метод описания языка использует частичный алгоритм, который для произвольной входной цепочки остановится и ответит „да" после конечного числа шагов, если эта цепочка принадлсжит языку. В самом общем случае мы могли бы позволить частичному алгоритму либо остановиться и ответить „нет", либо продолжать работать бесконечно, если цепочка не принадлежит языку.
Однако в практических ситуациях мы должны потребовать, чтобы этот частичный алгоритм был алгоритмом, т. е. чтобы ои прекращал работу дчя всех входных цепочек, Мы будем представлять частичные алгоритмы, определяющие языки, в виде несколько схематизированного устройства. Это устройство, называемое Раапазнавате,есхч, будет введено в равд. 2.1.4, 2 ! СПОСОбЫ ОПРЕДЕЧЕИИЯ ЯЗЫКОВ 2Л.2.
Грамматики Грамматики образуют, по-видимому, наиболее важный класс генераторов языков. Грамматика — это математическая система, и еделяющая язык. о она является ус которое придает епочкам („ предложениям" ) языка полезную структуру. В этом разделе мы рассмотрим класс грамматик, называемых грамматиками Хамского или грамматиками составляющих. В грамматике, определяющей язык Ь, используются два конечных непересекающихся множества символов — множество нетерминальных символов, которое часто будет обозначаться буквой в)'), и множество терминальных символов, обозначаемое Х. Из терминальных символов образуются слова (цепочки) определяемого языка.
Нетерминальные символы служат для порождения слов языка Е способом, который будет объяснен позднее. Сердцевину грамматики составляет конечное множество Р правил образования, которые описывают процесс порождения цепочек языка. Правило — это просто пара цепочек, или, точнее, элемент множества (ХОю)*Н(1ч()Х)" х (Х0Х)'. Иначе говоря, первой компонентой правила является любая пеночка, содержащая хотя бы один нетерминал, а второй компонентой — любая цепочка. Например, правилом может быть пара (АВ, СОЕ). Если уже установлено, что некоторая цепочка сс порождается грамматикой (или „выводится" в ней) и сс содержит АВ, т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
