Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 20
Текст из файла (страница 20)
ниже замечания по литературе). Однако ясно, что необходимы дальнейшие исследования.. Совсем иной подход к проблеме создания надежных комяиляторов состоит в том, чтобы развить теорию, применимую к эмпирическим иСпытаниям компиляторов. Иначе говоря, предполагается, что мы „знаем", что наш алгоритм компиляции корректен, и хотим проверить, правильно лн реализует его конкретная программа, При первом из упомянутых выше подходов надо попытаться доказать эквивалентность написанной программы и абстрактного алгоритма компиляции.
Второй из предлагаемых подходов состоит в том, чтобы придумать конечное множество таких входных цепочек, что если они компилируются правильно, то с разумной уверенностью (скажем, иа 997е) можно сказать, что В программе компилятора ошибок нет.
Очевидно, нужно сделать некоторые предположения о частоте и природе ошибок программирования, встречающихся в программе самого компилятора, Замечания по литературе 95 94 е1.2.11. Сделайте синтаксически управляемый перевод, отображающий разбор, приведенный на рис. 1.3, прямо в код ассемблера (1,2.5), ') Строго говоря, нз-зз переполненнн н)нлн округления порядок может оказаться важным.
Резннтне компиляторов н техники компнлнцнн шхо пзрзхкедьно с рез. ннтнем языков прогрзммнронаннн. Псрным компнлнтаром, который дзеел зффектннпый объектный код, был компилятор с Фортрана)Бзкус н др., !957). С тех пор были нанесены многочнсленныс кампнляторы н появилось несколько попых л1етоднк компиляции. Большие успехи были достнгнуты н лексическом н сннтзксн ~соком анализах н н поннмзннн техпнкн генерзцнн кодов. Статьи, отнаснщнесн к построенн1а компиляторов, многачнсненны. Мы не будем пытзтьсн перечислить здесь есе нсточннкн. Исчерпывающие обзоры истории компнннторое н нх развития написаны Розеном )1967), Фельдманом н Грнсом )1968), Коком н Шварцем )1970).
Б ряде книг описывается техника ГЛ. 1 ВВЕЛЕНИЕ В КОМПИЛЯЦИЮ 1.3. друГие приложения АлГОРитмов РАЗБОРА и пеРеВОДА построения компиляторов< [Реиделл и Рассел, 1964], (Мак-Кимаи н др., 1970], [Кок и Шварц, 1970], (Грис, 1971(, Хопгуд (19Гэз] дает краткий, но хорошо написанный обзор техники компиляции. Элементарное изложение вопросов компиляции см. в (Ли, !9671. Написано несколько компиляторов (таких, как О!ТКАМ [Моултон н Мюллер, 1967[, ИТКАН [Дьюар и др.
19691), в которых особое внимание уделяется всесторонней диагностике ошибок. Написаны танже колшиляторы, которые пытаются исправить каждую ошибку и выполнить объектную программу независимо от того, сколько оказалось ошибок. Иден здесь состоит в том, чтобы несмотря на ошибки продолжать компиляцию и выполнение программы и выявить возможно больше ошибок. Такими компиляторами являются СОКС [Конвэй и Максвелл, 1963; Фримэн, !964[, СЬРь (Конвэй и Максвелл, 1963] и РЬ(С (Конвэй и др., 1970].
В программе часто встречаются орфографические ошибки. Фримэн (1964] и Морган [1970] описывают технику, которую они нашли эффективной для обнаружения и исправления таких ошибок. Общий обзор методов обнаружении ошибок прн компиляции можно найти в (Элспас и др., 1971!. Попытки создания теоретических основ доказательства хоррсктности компиляторов излагаются в [Мак-Карти, 1963], [Мак-Карти и Пейнтср, 1967], [Пейнтер, !970( и ]Флойд, 1967а]. Построение компялнтора †зада, требу<пщая болыпих за<рат труда.
Попытки сделать эту работу менее трудоемкой привели к появлснвю большого числа систем программирования, пазываеьых компиляторами компиляторов.(Врукер в Моррис, 19631,[Читзм и Стэндиш, 1970[, (Ингермаи, 1966], (Айронс, !9636], [Фельдман, 1966], (Мак-Клюр, 19<5], [Мак-Каман н др., 19701, [Рейнольдс, 1<651, [Шорре, 1904( н [Уаршолл и Шапиро, 1964] — только часть литературы по этому предмету.
На компилятор компиляторов люжио смотреть просто как иа изык программирования, в котором исходная программа — это описание компилятора для некоторого языка, а объектная программа-сам компилятор для этого языка. Исходная программа номпилнтора компиляторов — это просто формализм, служащий для описания компиляторов.
Следовательно, исходная программа должна явно или неявно содержать описание лексического анализатора, синтаксического анализатора. генератора кодов н разных других частеи создаваемого компилятора, Компилятор компиляторов отражает попытку создать средства, с помощью которых все это можно легко записать, В нескольких компиляторах компиляторов для задания компилиторов используется никой-нибудь вариант схемы синтаксически управляемого перевода, некоторые из ннх обеспечивают автоматический механизм синтаксического анализа. Система ТМО [Мак-Клюр, 1965[ — первая из систем этого типа. Другие компиляторы компиляторов, такие, как ТО5 [Читэм.
1965[, вместо этого обеспечивают искусный язык высокого уровня, на котором удобно описывать алгоритмы, используемые при создании компиляторов. Фельдман и Грие (!968] написали хороший обзор по компиляторам компиляторов. 4.3. ДРУГИЕ ПРИЛОЖЕНИЯ АЛГОРИТМОВ РАЗБОРА И ПЕРЕВОДА В этом разделе мы коснемся двух отличных от компиляции областей, в которых главную роль могут играть иерархические структуры, подобные тем, что встречаются в алгоритмах разбора и трансляции. Это перевод с естественных языков и распознавание образов. 4.3.4. Естественные языки Казалось бы, текст, написанный на естественном языке, можно переводить на другой естественный язык или на машинный язык (если этот текст описывает алгоритм) точно так же, как транслируются языки программирования. Однако проблемы возникают уже на стадии синтаксического анализа.
Языки, предназначенные для вычислительных мап<ин, имеют точное определение (не без исключений, разумеется) и легко распознаваемую структуру утверждений (ипредложений"), из которых они состоят. Обычная модель этой структуры †дере, описанное в разд, 1.2.4. Естественные языки прежде всего страдают двусмысленностью †к синтаксической, так и семантической. Возьмем в качестве очевидного примера естественного языка английский; предложение 1 ]<аче <(га<чп [эц[[ег имеет по крайней мере два смысла в зависимости от того, является бгашп в этом предложении прилагательным илн глаголом '). Таким образом, однозначный разбор можно провести не для всякого английского предложения, особенно если предложение рассматривается вне контекста. Более трудная проблема, касающаяся естественных языков, возникает из-за того, что слова, т.
е. терминальные символы языка, связаны с другими ел<>вами внутри предложения, вне его и, возможно, с общим окружением. Поэтому для описания всей информации об английском предложении, которую хотелось бы иметь, когда приходится переводить на другой язык (аналог генерации кода в случае языков программирования), не всегда достаточна простая древовидная структура.
Распространенный пример — английское существительное реп, имеющее по крайней мере два различных значения †руч (в выражении [они[а[и реп †автоматическ ручка) и загон (в выражении р(я реп — загон для свиней) '). Допустим, мы хотим переводить с английского на язык (например, русский), в котором [оцп(а[п реп и р[я реп обозначаются разными словами. Если нам дано для перевода предложение Т]<[Б реп!еа1<3, то как будто бы ясно, что правильным значением реп здесь будет „РУчка".
Однако если это пРедложеиие Взато из доклада иПРедУ- 1! Приведем пример двусмысленности в русском языке, извлеченный из одной статьи о синтаксическом анализе языков программирования: „Подъем по полю слоев захваченных поиятийГЗ Разные смыслы получаю~си в зависимости от того, к чему относится „слоев" — к „полю" или к „поиятий".— Дрим. перез. Есть более живые примеры, скажем название одного из органов в Акаде<шн наук: „Комиссия по изучевию четвертичного периода АН СССР",— 71 риз<. Ред, ') 1<ример омоннмии в русском языке: слово „ключ" имеет разные значения в выражениях „ключ в замке" и „прозрачный ключ".— Прим. перез. 4 А, Азо, Дж, Ульиаи.
з. 1 ГЛ.1. Бввдвиив и КОМПИЛЯЦИЮ Лг является программой. ') 9 честь Э. Дейкстры. 98 преждение насморка у свиней", то нам, вероятно, захочется пересмотреть наше решение. Отметим особо, что смысл и структуру предложения можно определить, только исследовав все его окружение: окружакпцие предложения, свойства предмета (например, во фразе „прозрачный ключ" имеется в виду не ключ от замка, так как он скорее всего не прозрачный) и даже информацию о говорящем н пишущем, Чтобы подробнее описать информацию, которую можно извлечь нз предложений естественного языка, лингвисты используют более сложные структурные системы, чем древовидные структуры, достаточные для языков программирования, Многие из них охватываются понятиями контекстно-зависимой грамматики и трансфорыационной грамматики.
Мы не будем рассматривать их подробно, хотя контекстно-зависимые грамматики определяготся в следующей главе, а некоторую упрощенную форму трансформационной грамматики можно трактовать как обобщение синтаксически управляемого перевода, заданного на деревьях. Это понятие будет определено в гл. 9. В замечаниях по литературе к этому разделу даны ссылки на литературу, из которой можно больше узнать о синтаксическом анализе естественных языков. !.3.2.
Структурное оомсаиые образов Некоторые важные классы образов допускают естественные описания, которые в каком-то смысле поддаются синтаксическому анализу. 111оу 119701, например, проанализировал фотографии, полученные с помощью камеры Вильсона, придав изображенным на них кривым подходящую древовидную структуру. "Мы опишем особенно привлекательный способ определения мно. жеста графов с помощью так называемых грамматик, порождающих графы [Пфальц и Розенфельд, 1969). Полное нх описание требует знакомства с равд. 2.1, так что здесь мы лишь приведем простой пример, иллюстрирующий основные идеи. Пример 1.6. Наш пример относится к графам, называемым г(-схемами')„которые можно представлять себе как блок-схемы программ некоторого языка программирования, определяемых следующими правилами: (1) Простой оператор присваивания является программой, (2) Если 5, и 5,--программы, то 5,; 5,— тоже программа.
(3) Если 5, и 5,— программы и А — предикат, то П А бйеп 5, е!ае 5, епб ьа. дРугие пРиложения АлгОРитмов РА3БОРА и переводА (4) Если 5 — программа и А — предикат, то АРИ11е А до 5 епд является программой. Все такие программы можно изобразить блок-схемами, вершины которых (блоки) представляют коды, либо проверяющие преднкаты, либо выполняющие простые присваивания.
Любую 11-схему можно построить, начиная с одной вершины, представляющей программу„и заменяя несколько раз вершины, представляющие программы, одной из трех структур, показанных о о Ю Рве. 1.8, Структуры, представлпюгкпе подпрограммы блок-схемы, иа рис. 1.8. Эти правила замены, нли подстановки, соответствуют приведенным выше правилам (2) — (4). Подставленные структуры соединяются с остальной частью графа по следующим правилам. Допустим, что вершина и, заменяется одной из структур а, б или а, изображенных на рнс. 1.8. (1) Дуги, входившие в п„теперь входят соответственно в л;, и., или и,.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
