В чем преимущества трансляторов интерпретаторов в сравнении с компиляторами

Языки программирования высокого уровня — Классификация языков программирования

Это продолжение увлекательной статьи про классификация языков программирования. . сложность программ выросла настолько, что превысила способность программистов управляться с ними, и это привело к огромным убыткам и застою в развитии информационных технологий[22]. Ответом на эту проблему стало появление массы языков высокого уровня, предлагающих самые разные способы управления сложностью (подробнее см. парадигма программирования и языки для программирования в мелком и крупном масштабе). Программы на языках «высокого уровня» гораздо легче модифицируются и совсем легко переносятся с компьютера на компьютер. На практике, наибольшее распространение получили языки третьего поколения, которые лишь претендуют на звание «высокоуровневых», но реально предоставляют лишь те «высокоуровневые» конструкции, что находят однозначное соответствие инструкциям в машине фон Неймана[23]. К языкам четвертого поколения относят языки высшего порядка>>>. Иногда выделяется категория языков пятого поколения, но она не является общепринятой — чаще используется термин «язык сверхвысокого уровня» (англ. very high level language). Это языки, реализация которых включает существенную алгоритмическую составляющую (то есть когда интерпретация небольшого исходного кода требует весьма сложных вычислений). Чаще всего так называют логические языки, про которые также говорят, что это просто языки четвертого поколения, дополненные базой знаний[24]. Кроме того, к «языкам сверхвысокого уровня» относят визуальные языки и языки, основанные на подмножестве естественного языка (например, так называемой «деловой прозы»). Важной категорией являются предметно-ориентированные языки (англ. DSL — Domain Specific Language). Отнесение языка к этой категории является весьма условным и зачастую спорным; на практике этот термин могут применять к представителям и третьего, и четвертого, и пятого поколений языков. Порой так даже классифицируют язык Си, который можно отнести к поколению «2,5». Он изначально позиционировался как «высокоуровневый ассемблер»; его также часто называют «языком среднего уровня». Он позволяет в значительной степени контролировать способ реализации алгоритма с учетом свойств, типичных для весьма большого числа аппаратных архитектур. Однако есть платформы, под которые реализации Си (даже с в нестандартном виде) отсутствуют по причине принципиальной невозможности или нецелесообразности их создания. Со временем появились и другие языки среднего уровня, например, LLVM, C—. Первые три поколения языков формируют императивную парадигму программирования, а последующие — декларативную[24]. Термин «императив» означает «приказной порядок», то есть программирование посредством пошагового инструктирования машины, или детального указания уже придуманного программистом способа реализации технического задания. Термин «декларатив» означает «описание», то есть программирование посредством предоставления формализации технического задания в виде, пригодном для автоматических преобразований[en], с предоставлением свободы выбора транслятору языка. Императивные языки нацелены на описание того, как получить результат, тогда как языки более высокого уровня нацелены на описание того, что требуется в результате. Поэтому первые называют как-языками (или языками, ориентированными на машину), а вторые — что-языками (или языками, ориентированными на человека). Для множества задач полностью автоматическое порождение по-настоящему эффективной реализации алгоритмически неразрешимо, так что на практике даже на что-языках нередко используются определенные алгоритмические ухищрения. Однако существуют методы получения эффективных реализаций из основанных на определении (реализаций «в лоб») — такие как изобретенная в СССР суперкомпиляция. В большинстве случаев языки высокого уровня порождают машинный код большего размера и исполняются медленнее. Однако некоторые языки высокого уровня для алгоритмически и структурно сложных программ могут давать заметное преимущество в эффективности, уступая низкоуровневым лишь на небольших и простых программах (подробнее см. эффективность языков). Иначе говоря, потенциальная эффективность языка меняется с повышением его «уровня» нелинейно и вообще неоднозначно. Однако скорость разработки и трудоемкость модификации, устойчивость и другие показатели качества в сложных системах оказываются гораздо важнее предельно возможной скорости исполнения — они обеспечивают различие между программой, что работает, и той, что нет[25] — так что экономически более целесообразна эволюция аппаратного обеспечения (исполнение большего числа инструкций в единицу времени) и методов оптимизирующей компиляции (более того, последние десятилетия эволюция аппаратного обеспечения движется в направлении поддержки методов оптимизирующей компиляции для языков высокого уровня). К примеру, автоматическая сборка мусора, присутствующая в большинстве высокоуровневых языков программирования, считается одним из важнейших улучшений, благотворно повлиявших на скорость разработки[26]. Поэтому в наши дни языки низкого уровня используются только в задачах системного программирования. Об этом говорит сайт https://intellect.icu . Распространено мнение, что в задачах, где необходим точный контроль за ресурсами, язык сам должен требовать как можно меньше преобразований, иначе все усилия программиста окажутся напрасными. В действительности есть примеры, опровергающие это. Так, язык BitC является представителем четвертого поколения (функциональной парадигмы программирования), но целиком и полностью ориентирован именно на системное программирование и уверенно конкурирует по скорости с Си. То есть, это «высокоуровневый язык», предназначенный для «низкоуровневого программирования». Языки третьего поколения C# и Limbo разрабатывались для использования одновременно как в системном программировании (с целью повышения отказоустойчивости операционной системы), так и в прикладном — это обеспечивает единство платформы, что сокращает потери при трансляции.

Языки программирования высокого уровня

• C++
• Java
• JavaScript
• PHP
• С#
• Visual Basic
• Python
• Perl
• Fortran
• Delphi(Pascal)
• Липс
• Фортран

C++ Си плюс плюс— компилируемый, статически типизированный язык программирования общего назначения.

Поддерживает такие парадигмы программирования как процедурное программирование, объектно-ориентированное программирование, обобщенное программирование, обеспечивает модульность, раздельную компиляцию, обработку исключений, абстракцию данных, объявление типов (классов) объектов, виртуальные функции. Стандартная библиотека включает, в том числе, общеупотребительные контейнеры и алгоритмы. C++ сочетает свойства как высокоуровневых, так и низкоуровневых языков. В сравнении с его предшественником — языком C, — наибольшее внимание уделено поддержке объектно-ориентированного и обобщенного программирования.

C++ широко используется для разработки программного обеспечения, являясь одним из самых популярных языков программирования. Область его применения включает создание операционных систем, разнообразных прикладных программ, драйверов устройств, приложений для встраиваемых систем, высокопроизводительных серверов, а также развлекательных приложений. Существует множество реализаций языка C++, как бесплатных, так и коммерческих и для различных платформ.

Java – это параллельный, объектно-ориентированный (а именно класс-ориентированный) язык программирования общего назначения. Java позволяет разработчикам приложений «написав однажды, запускать везде» . Это означает, что скомпилированный Java-код может быть запущен на всех платформах, которые поддерживают Java, без необходимости в перекомпиляции. Приложения на Java, как правило компилируются в байт-код, который может выполняться на любой виртуальной машине Java (JVM – англ. Java Virtual Maсhine) не зависимо от компьютерной архитектуры. По состоянию на 2015 год, Java является одним из наиболее популярных используемых языков программирования, особенно в сфере разработки клиент-северных web-приложений. Изначально язык Java был разработан в компании Sun Microsystems (которая была поглощена корпорацией Oracle в период с апреля 2009 года по январь 2010 года) Джеймсом Гослингом и опубликован в 1995 году как ядро программной платформы Java. Синтаксис Java по большей части взят из языков C и C++, но низкоуровневые возможности языка значительно ограничены по сравнению с любым из них. Оригинальная и эталонная реализации компиляторов Java, виртуальных машин и библиотек классов изначально были выпущены компанией Sun под проприетарными лицензиями. По состоянию на 2007 год, в соответствии со спецификациями Java Community Process, Sun сменила лицензию большинства своих Java-технологий на Открытое лицензионное соглашение GNU (англ. GNU General Public License). Так же существуют и сторонние реализации этих технологий, такие как GNU Compiler for Java (GCJ), GNU Classpath (свободная реализация стандартной библиотеки классов языка Java) и IcedTee-Web. Последняя версия – Java 8 – в настоящее время является единственной версией, поддерживаемой Oracle бесплатно. Более ранние версии поддерживаются Oracle и другими компаниями на коммерческой основе.

JavaScript ( /ˈdʒɑːvɑːˌskrɪpt/ ; аббр. JS /ˈdʒeɪ.ɛs./ ) — мультипарадигменный язык программирования . Поддерживает объектно-ориентированный , императивный и функциональный стили. Является реализацией стандарта ECMAScript (стандарт ECMA-262 [ ).

JavaScript обычно используется как встраиваемый язык для программного доступа к объектам приложений. Наиболее широкое применение находит в браузерах как язык сценариев для придания интерактивности веб-страницам .

Основные архитектурные черты: динамическая типизация, слабая типизация, автоматическое управление памятью, прототипное программирование, функции как объекты первого класса.

На JavaScript оказали влияние многие языки, при разработке была цель сделать язык похожим на Java, но при этом легким для использования непрограммистами. Языком JavaScript не владеет какая-либо компания или организация, что отличает его от ряда языков программирования, используемых в веб-разработке ] .

Название «JavaScript» является зарегистрированным товарным знаком корпорации Oracle в США

PHP — это популярный язык сценариев общего назначения, который особенно подходит для веб-разработки . Первоначально он был создан Расмусом Лердорфом в 1994 году; [ PHP изначально обозначал « Персональная домашняя страница» , , но теперь он обозначает рекурсивный инициализм PHP: Hypertext Preprocessor .

PHP-код обычно обрабатывается на веб-сервере интерпретатором PHP, реализованным в виде модуля , демона или исполняемого файла Common Gateway Interface (CGI). На веб-сервере результат интерпретируемого и исполняемого кода PHP — который может быть любым типом данных, таким как сгенерированные данные HTML или двоичные изображения — будет формировать весь или часть ответа HTTP. Существуют различные системы веб-шаблонов, системы управления веб- контентом и веб-структуры, которые можно использовать для организации или облегчения генерации такого ответа. Кроме того, PHP может использоваться для многих задач программирования вне веб-контекста, таких как автономный графические приложения и роботизированное управление дроном . [10] Произвольный код PHP также может быть интерпретирован и выполнен через интерфейс командной строки (CLI).

Стандартный интерпретатор PHP, работающий на Zend Engine , является свободным программным обеспечением, выпущенным под лицензией PHP . PHP широко портирован и может быть бесплатно развернут на большинстве веб-серверов практически на всех операционных системах и платформах .

C Sharp C# — (произносится [ siː ʃɑːp ])объектно-ориентированный язык программирования. Разработан в 1998—2001 годах группой инженеров под руководством Андерса Хейлсберга в компании Microsoft как язык разработки приложений для платформы Microsoft .NET Framework и впоследствии был стандартизирован как ECMA-334 и ISO/IEC 23270.

C# относится к семье языков с C-подобным синтаксисом, из них его синтаксис наиболее близок к C++ и Java. Язык имеет статическую типизацию, поддерживает полиморфизм, перегрузку операторов (в том числе операторов явного и неявного приведения типа), делегаты, атрибуты, события, свойства, обобщенные типы и методы, итераторы, анонимные функции с поддержкой замыканий, LINQ, исключения, комментарии в формате XML.

Переняв многое от своих предшественников — языков C++, Pascal, Модула, Smalltalk и Java — С# исключает некоторые модели, зарекомендовавшие себя как проблематичные при разработке программных систем, например, C# в отличие от C++ не поддерживает множественное наследование классов (между тем допускается множественное наследование интерфейсов).

Microsoft Visual Basic — язык программирования и интегрированная среда разработки программного обеспечения. Разрабатывался компанией Microsoft. Visual Basic унаследовал стиль и отчасти синтаксис языка BASIC, имеющего немало диалектов. Visual Basic сочетает в себе процедуры и элементы объектно-ориентированных и компонентно-ориентированных языков программирования, а интегрированная среда разработки VB содержит в себе инструменты для визуального проектирования пользовательского интерфейса, редактор кода с возможностью IntelliSense и подсветкой синтаксиса и инструменты для отладки приложений.

Python (произносится [ ˈpaɪ.θən ] )является широко используемым языком программирования общего назначения, высокого уровня. Его философия дизайна подчеркивает читаемость кода, а его синтаксис позволяет программистам, выразить понятия в меньшем количестве строк кода, чем было бы возможно в таких языках, как С ++ или Java. Язык обеспечивает конструкции, предназначенные для того, чтобы программы были четкие на обоих малых и больших масштабах.

Python поддерживает несколько парадигм программирования, в том числе объектно-ориентированного, императивном и функциональном программировании или процедурных стилей. Он имеет динамическую систему типов и автоматическое управление памятью и имеет большую и всеобъемлющую стандартную библиотеку.

Компиляторы Python имеются для установки на многих операционных системах, что позволяет выполнять код Python на самых разнообразных систем. Использование сторонних инструментов, таких как py2exe или Pyinstaller. Python код может быть собран в автономный исполняемый файл для некоторых из самых популярных операционных систем, что позволяет распространение программного обеспечения Python основе для использования на этих средах, не требуя установка интерпретатора Python.

CPython, ссылка реализация Python, является свободное и открытое программное обеспечение и имеет модель развития общин, как это делают почти все его альтернативные реализации. CPython управляется некоммерческой компанией Python Software Foundation.

Perl (произносится [ pɜːl ]) является языком общего назначения. Изначально он был предназначен для работы с текстом, но сейчас используется для решения широкого круга задач, включая администрирование, web-разработку, сетевое программирование, разработку графических пользовательских интерфейсов. Его основными достоинствами являются простота использования, встроенная обработка текстовых данных и наличие одной из самых впечатляющих коллекций сторонних библиотек.

Fortran (Фортран) — первый реализованный язык программирования высокого уровня (после Планкалкюля) для машин, построенных по классической схеме фон Неймана. Создан в период с 1954 по 1957 год группой программистов под руководством Джона Бэкуса (John Backus) в корпорации IBM. Через несколько лет начались его коммерческие поставки. До этого программирование велось либо непосредственно в машинных кодах, либо на символических ассемблерах. Название Fortran является аббревиатурой от FORmula TRANslator, то есть, переводчик формул.

Фортран широко используется в первую очередь для научных и инженерных вычислений. Одно из преимуществ современного Фортрана — большое количество написанных на нем программ и библиотек подпрограмм. Ряд пакетов языка создавались на протяжении десятилетий и популярны по сей день (главным образом в научной среде).

Современный Фортран (Fortran 95 и Fortran 2003) приобрел черты, необходимые для эффективного программирования для новых вычислительных архитектур; позволяет применять современные технологии программирования, в частности, ООП.

Delphi — (Де́лфи, произносится ˈdɛlˌfi:) — императивный, структурированный, объектно-ориентированный язык программирования со строгой статической типизацией переменных. Основная область использования — написание прикладного программного обеспечения. Первоначально носил название Object Pascal и исторически восходит к одноименному диалекту языка, разработанному в фирме Apple в 1986 году группой Ларри Теслера. Однако в настоящее время термин Object Pascal чаще всего употребляется в значении языка среды программирования Delphi. Начиная с Delphi 7, в официальных документах Borland стала использовать название Delphi для обозначения языка Object Pascal.

Лисп (LISP, от англ. LISt Processing language — «язык обработки списков»; современное написание: Lisp) — семейство языков программирования, программы и данные в которых представляются системами линейных списков символов. Лисп был создан Джоном Маккарти для работ по искусственному интеллекту и до сих пор остается одним из основных инструментальных средств в данной области. Применяется он и как средство обычного промышленного программирования, от встроенных скриптов до веб-приложений массового использования, хотя популярным его назвать нельзя.

Это один из старейших (наряду с Фортраном и Коболом) используемых по сей день высокоуровневых языков программирования , а также первый из сохранившихся в использовании языков, использующих автоматическое управление памятью и сборку мусора .

Традиционный Лисп имеет динамическую систему типов. Язык является функциональным, но начиная уже с ранних версий обладает также чертами императивности, к тому же, имея полноценные средства символьной обработки, позволяет реализовать объектно-ориентированность; примером такой реализации является платформа CLOS.

Является языком системного программирования для так называемых лисп-машин, производившихся в 1980-е годы, например, фирмой Symbolics

Фортра́н (англ. Fortran) — первый язык программирования высокого уровня, получивший практическое применение, имеющий транслятор и испытавший дальнейшее развитие . Создан в период с 1954 по 1957 год группой программистов под руководством Джона Бэкуса в корпорации IBM . Название Fortran является сокращением от FORmula TRANslator (переводчик формул). Фортран широко используется в первую очередь для научных и инженерных вычислений. Одно из преимуществ современного Фортрана — большое количество написанных на нем программ и библиотек подпрограмм .

Имеется большое количество написанных на Фортране (в большей части на старых версиях языка) различных математических библиотек для матричной алгебры и решения систем линейных уравнений, библиотеки для решения дифференциальных уравнений, интегральных уравнений и их систем, аппроксимации функций, специальных функций, быстрых преобразований Фурье, математической статистики и других математических дисциплин. Эти библиотеки поставляются, как правило, с компилятором. Ряд таких пакетов создавался на протяжении десятилетий и популярен в научной среде по сей день, например — IMSL .

Большинство таких библиотек является фактически достоянием человечества: они доступны в исходных кодах, хорошо документированы, отлажены и весьма эффективны.

Современный Фортран (Fortran 95 и Fortran 2003) приобрел черты, необходимые для эффективного программирования, для новых вычислительных архитектур; позволяет применять современные технологии программирования, в частности, обобщенное и модульное программирование, ООП, сохраняя при этом преемственность с более ранними версиями. Одна из главных концепций развития современного Фортрана — средства поддержки параллельности и векторные операции[

Безопасные и небезопасные языки

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

Системы типов языков делятся на динамические (потомки Lisp, Smalltalk, APL) и статические, а последние, в свою очередь, делятся на неполиморфные (потомки Алгола и BCPL) и полиморфные (потомки ML)[27]. Кроме того, они делятся на явные (англ. explicit) и неявные (англ. implicit) — другими словами, требующие манифестной[en] декларации типов для объектов в программе или статически выводящие их самостоятельно.

Системы типов бывают сильные и слабые. Сильная система типов назначает тип для всякого выражения раз и навсегда (когда бы конкретно это ни происходило — в динамике или в статике), а слабая позволяет впоследствии переназначать типы. Сильная типизация порой ошибочно отождествляется со статической.

В общем и целом, язык называется безопасным, если программы на нем, которые могут быть приняты компилятором как правильно построенные, в динамике никогда не выйдут за рамки допустимого поведения[28]. Это не значит, что такие программы не содержат ошибок вообще. Термин «хорошее поведение программы» (англ. good behavior) означает, что даже если программа содержит некий баг (в частности, логическую ошибку), то она тем не менее не способна нарушить целостность данных и обрушиться (англ. crash). Хотя термины неформальны, безопасность некоторых языков (например, Standard ML) математически доказуема[27]. Безопасность других (например, Ada) была обеспечена ad hoc-образом, без обеспечения концептуальной целостности, что может обернуться катастрофами, если положиться на них в ответственных задачах (см. концептуальная целостность языков). Неформальная терминология была популяризована Робином Милнером, одним из авторов теории формальной верификации и собственно языка Standard ML.

Степень контроля ошибок и реакция языка на них могут различаться. Простейшие системы типов запрещают, к примеру, вычитать строку из целого числа. Однако целыми числами могут представляться и миллиметры, и дюймы, но было бы логической ошибкой вычитать дюймы из миллиметров. Развитые системы типов позволяют (а наиболее развитые — принуждают) внедрять в программу такую логическую информацию. Для ЭВМ она является избыточной и полностью удаляется при порождении машинного кода тем или иным образом>>>. В частности, Standard ML не допускает над данными никаких операций, кроме тех, что разрешены явно и формализованы; однако программы на нем все же могут завершаться порождением необработанного исключения (например, при попытке деления на ноль). Его потомок, MLPolyR гарантирует также и отсутствие необработанных исключений. Такие языки называются «типобезопасными». Java и C# менее строги и контролируют лишь утечки памяти, поэтому в их контексте чаще используют более узкий термин «безопасность типов в отношении доступа к памяти» (англ. memory type safety) или (чаще) просто «безопасность доступа к памяти». Сильно динамически типизируемые языки отслеживают поведение программ в динамике (что влечет снижение быстродействия) и реагируют на ошибки порождением исключения. Все эти языки ориентированы на практичность, предоставляя оптимальный компромисс между пресечением серьезных сбоев и высокой скоростью разработки программ. Но существуют и языки, предназначенные для написания программ, которые верны по построению, то есть обеспечивают гарантию того, что исполнимая программа по структуре и поведению будет тождественна ее спецификации (см. параметричность[en], зависимый тип). Как следствие, программы на таких языках часто называют «исполнимыми спецификациями» (см. Соответствие Карри — Говарда). Трудоемкость разработки на таких языках возрастает на порядки, кроме того, они требуют очень высокой квалификации разработчика, поэтому они используются только в формальной верификации. Примерами таких языков служат Agda, Coq.

Языки Си и его потомок C++ являются небезопасными[29]. В программах на них обширно встречаются ситуации ослабления типизации (приведение типов) и прямого ее нарушения (каламбур типизации), так что ошибки доступа к памяти являются в них статистической нормой (но крах программы наступает далеко не сразу, что затрудняет поиск места ошибки в коде). Самые мощные системы статического анализа для них (такие, как PVS-Studio[30][31]) способны обнаруживать не более 70 — 80 % ошибок, но их использование обходится очень дорого в денежном смысле. Достоверно же гарантировать безотказность программ на этих языках невозможно, не прибегая к формальной верификации, что не только еще дороже, но и требует специальных знаний. У Си есть и безопасные потомки, такие как Cyclone или Rust.

Язык Forth не претендует на звание «безопасного», но тем не менее на практике существование программ, способных повредить данные, почти исключено, так как содержащая потенциально опасную ошибку программа аварийно завершается на первом же тестовом запуске, принуждая к коррекции исходного кода. В сообществе Erlang принят подход «let it crash» (с англ. — «дай ей обрушиться»), также нацеленный на раннее выявление ошибок.

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

Можно выделить три принципиально разных способа реализации языков программирования: компиляция, интерпретация и встраивание. Распространено заблуждение, согласно которому способ реализации является присущим конкретному языку свойством. В действительности, это деление до определенной степени условно. В ряде случаев язык имеет формальную семантику, ориентированную на интерпретацию, но все или почти все его действительные реализации являются компиляторами, порой весьма эффективно оптимизирующими (примерами могут служить языки семейства ML, такие как Standard ML, Haskell). Есть языки, размывающие границы между интерпретацией и компиляцией — например, Forth.

Компиляция означает, что исходный код программы сперва преобразуется в целевой (машинный) код специальной программой, называемой компилятором — в результате получается исполнимый модуль, который уже может быть запущен на исполнение как отдельная программа. Интерпретация же означает, что исходный код выполняется непосредственно, команда за командой (иногда — с минимальной подготовкой, буквально после разбора исходного кода в AST),— так что программа просто не может быть запущена без наличия интерпретатора. Встраивание языка можно философски рассматривать как «реализацию без трансляции» — в том смысле, что такой язык является синтаксическим и семантическим подмножеством некого другого языка, без которого он не существует. Говоря же более точно, встраиваемые языки добавляют к сказанному еще четыре способа реализации.

Естественный для языка способ реализации определяется временем связывания программных элементов с их характеристиками. В частности, в языках со статической типизацией переменные и другие объекты программы связываются с типом данных на этапе компиляции, а в случае типизации динамической — на этапе выполнения, как правило — в произвольной точке программы. Некоторые свойства элементов языка, такие как значение арифметических операторов или управляющих ключевых слов, могут быть связаны уже на этапе определения языка. В других языках возможно их переназначение (см. связывание имен[en]). Раннее связывание обычно означает бо́льшую эффективность программы, в то время как позднее — большую гибкость, ценой которого является меньшая скорость и/или усложнение соответствующего этапа[32]. Однако, даже из, казалось бы, очевидных случаев есть исключения — например, интенсиональный полиморфизм откладывает обработку статической типизации до этапа выполнения, но не замедляя, а повышая общее быстродействие (по крайней мере, в теории).

Для любого традиционно компилируемого языка (такого как Паскаль) можно написать интерпретатор. Но многие интерпретируемые языки предоставляют некоторые дополнительные возможности, такие как динамическая генерация кода (см. eval[en]), так что их компиляция должна быть динамической (см. динамическая компиляция). Таким образом, составной термин «язык + способ его реализации» в ряде случаев оказывается уместен. Кроме того, большинство современных «чистых» интерпретаторов не исполняют конструкции языка непосредственно, а компилируют их в некоторое высокоуровневое промежуточное представление (например, с разыменованием переменных и раскрытием макрокоманд). Большинство традиционно интерпретируемых или компилируемых языков могут реализовываться как встраиваемые, хотя метаязыков, которые были бы способны охватить другие языки как свое подмножество, не так много (наиболее ярким представителем является Lisp).

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

Лекции

6.Тестирование и отладка программы. (Отладка – это устранение ошибок. Тестирование- проверка правильности работы.) Разработка тестов и контрольных примеров.

7. Оценка полученных результатов. Сопоставление реальных и ожидаемых результатов. Если результаты неудовлетворительны, возврат к некоторым предыдущим этапам.

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

Жизненным циклом программы называют весь период ее разработки и эксплуатации.

Алгоритм – однозначная последовательность действий, приводящая к требуемому результату.

Свойства алгоритма

1. Определенность. Каждый шаг точно определяет какое-либо действие. Не допускается двусмысленность, аппеляции к «здравому смыслу» и т.п.

2. Детерминированность. После окончания выполненного шага должно быть однозначно определено какой шаг будет следующим.

3. Конечность (или результативность). Алгоритм должен (для корректно заданных исходных данных) приводить к решению задачи за конечное число шагов.

4. Массовость. Один и тот же алгоритм можно применять к различным исходным данным. При этом исходные данные могут выбираться из некоторой области, которая называется областью применимости алгоритма.

Не всегда выполняется свойство конечности. Например, некоторые диалоговые алгоритмы строятся как бесконечные, работу которых можно прекратить лишь внешним воздействием: нажатием некоторых клавиш, перезагрузкой компьютера. Такой подход считается непрофессиональным.

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

Способы описания алгоритмов

1.Блок-схемы. Детальное описание таким методом каждого оператора используется только для коротких алгоритмов, умещающихся в 1 страницу. Для больших алгоритмов блок-схема получается громоздкой, объем ее бывает больше самой программы, и переход с одной страницы на другую очень усложняет ее чтение. Часто применяется при укрупненном представлении алгоритма, когда одной фигурой изображается какая-то выделенная часть программы, а не отдельный оператор.

2. Псевдокод. Способ точного описания алгоритма предложениями на естественном языке. Применяется наиболее часто.

Современные системы программирования

Система программирования это комплекс программных средств, предназначенных для кодирования, тестирования и отладки программного обеспечения. Имеет интерфейс, удобный пользователю.

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

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

2. Компиляторы , предназначенные для перевода исходного текста на входном языке в язык машинных кодов. В результате создаются объектные модули. Это программы на машинном языке, они записываются на диск с расширением .exe.

3. Компоновщики, позволяющие объединять несколько объектных модулей, порождаемых компилятором, в одну программу. В результате создается загрузочный модуль.

4. Загрузчики, обеспечивающие подготовку готовой программы к выполнению.

5. Библиотеки прикладных программ , содержащие в себе наиболее часто используемые подпрограммы в виде готовых объектных модулей.

6. Отладчики , выполняющие программу в заданном режиме (например, пошаговом) с целью поиска, обнаружения и локализации ошибок. Используются на этапе компиляции.

Основным модулем системы программирования всегда является компилятор. Именно технические характеристики компилятора, прежде всего, влияют на эффективность результирующих программ, порождаемых системой программирования. Напомним основные термины и понятия.

Транслятор – это программа, которая переводит входную программу на исходном (входном) языке в эквивалентную ей выходную программу на результирующем (выходном) языке.

Близко по смыслу к этому понятию понятие компилятор.

Компилятор – это транслятор, который осуществляет перевод исходной программы в эквивалентную ей объектную программу на языке машинных команд или языке ассемблера (.exe файл). Таким образом, компилятор отличается от транслятора тем, что его результирующая программа написана обязательно на языке машинных команд или языке ассемблера. Результирующая программа транслятора в общем случае может быть написана на любом языке (например, транслятор с языка Pascal на язык С). Таким образом, компиляторы – это вид трансляторов.

Напомним также, что существует еще принципиально отличное понятие: интерпретатор.

Интерпретатор – это программа, которая воспринимает входную программу на исходном языке, переводит каждый оператор или строку в машинный язык и выполняет их. Интерпретатор не порождает результирующую программу и никакого результирующего кода.

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

Языки программирования

Самым первым языком программирования был язык машинных кодов (двоичный язык). Программа записывалась как элементарные машинные действия: сложение, сравнение двух величин, пересылка по заданному адресу, извлечение из ячейки памяти с заданным адресом. Причем все команды и числа записывались в двоичном коде. В настоящее время практически не применяется.

Следующий этап — язык Ассемблер (мнемокод) – это тот же язык процессора, но адреса и команды в двоичной системе заменены символьными именами. Он позволяет программисту присваивать удобные имена ячейкам и областям памяти, а также задавать наиболее удобные схемы адресации.

Язык Макроассемблер является расширением языка Ассемблера.

Программирование становилось более продуктивным, да и вообще, более привлекательным. Но даже на ассемблере программировать было не очень-то приятно, кроме того, ассемблеры аппаратно зависимы — то есть, если планировалось использовать программы на компьютере от Dec, а не Intel, их приходилось переписывать заново. Почему же ассемблер используется до сих пор?

Языки Ассемблера и Макроассемблера применяются системными программистами-профессионалами с целью использования всех возможностей оборудования ЭВМ и получения эффективной по времени выполнения и по требуемому объему памяти программы. На этих языках обычно разрабатываются относительно небольшие программы, входящие в состав системного программного обеспечения: драйверы, утилиты и другие. В программу, написанную на языке высокого уровня, можно делать вставки на ассемблере для повышения быстродействия программы.

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

К настоящему времени создано около 3 000 языков. Сейчас в практической деятельности применяются не более двух десятков языков. Некоторые известны узкому кругу специалистов определенной области. Другие, ранее широко известные, стали очень редко применяться в связи с созданием новых технологий (например, язык Кобол – язык экономических расчетов).

Языки высокого уровня не зависят от архитектуры компьютера . Чем более язык ориентирован на человека, тем выше его уровень.

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

1. процедурные
2. объектно-ориентированные
3. декларативные

Процедурное программирование

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

Классическое процедурное программирование требует от программиста детального описания того, как решать задачу, т.е. формулировки алгоритма и его специальной записи. При этом ожидаемые свойства результата обычно не указываются. Основные понятия языков этих групп – оператор и данные (переменные).

Переменная на языке процедурного типа получает атрибуты: имя, тип, значение.

При процедурном подходе операторы объединяются в группы – процедуры.

Первым был Fortran. Он появился в 1957 году. Fortran — это сокращение от двух английских слов FORmula TRANslator — что переводится как «транслятор формул». Как видно из названия, первоначально язык создавался с целью использования при математических расчетах. Он предназначался для написания программ, используемых при решении прикладных технических задач. Для него за время его существования было написано множество удобных и полезных библиотек, он до сих пор иногда используется при программировании сложных вычислений. К тому же Fortran до сих пор продолжают изучать при подготовке по некоторым физико-математическим специальностям во многих университетах, где он остается профилирующим языком программирования.

Basic (Beginners All-purpose Symbolic Instruction Code) —представляет собой простой язык программирования, разработанный в 1964 году для использования новичками. Он был разработан как простейший язык для непосредственного общения человека с вычислительной машиной. Поэтому первоначально работа велась в интерактивном режиме с использованием интерпретаторов. В настоящее время для этого языка имеются также и компиляторы.

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

Язык Си. Большой отпечаток на современное программное обеспечение наложил язык Си (первая версия – 1972г.), являющийся очень популярным в среде разработчиков систем программного обеспечения (включая и ОС). Си сочетает в себе черты, как языка высокого уровня, так и машинно-ориентированного языка, допуская программиста ко всем машинным ресурсам, что не обеспечивают другие языки.

Pascal является одним из наиболее популярных среди прикладных программистов процедурным языком программирования. Разработанный в 1970 году швейцарским специалистом в области вычислительной техники профессором Н. Виртом, язык назван в честь французского математика и по замыслу автора предназначался для обучения программированию. Однако язык получился настолько удачным, что стал одним из основных инструментов прикладных и системных программистов при решении задач вычислительного и информационно-логического характера. В языке Pascal реализован ряд концепций, рассматриваемых как основа «дисциплинированного» программирования и заимствованных впоследствии разработчиками многих языков.

Одним из существенных признаков языка Pascal является последовательная и достаточно полная реализация концепции структурного программирования. Кроме того, в языке реализована концепция определения новых типов данных на основе уже имеющихся.

Pascal реализован на компьютерах различных типов, но наиболее распространен и развит для персональных компьютеров.. В настоящее время широко используются такие версии этого языка для ПЭВМ, как BorlandPascal и TurboPascal.

Объектно-ориентированное программирование

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

Определения

Объект – это то, чем вы управляете с помощью программы ( например в Excel — ячейка, диапазон, диаграмма и т.п. В БД- это таблицы, формы, запросы). Каждый объект имеет свой тип (класс). Класс представляет собой тип данных, имеющий в составе данный объект.

Свойства — Параметры объекта (конечно, не все, а только необходимые в программе).

Методы — Действия, которые можно выполнять над объектом данного типа, или которые сам объект может выполнять. Это процедуры и функции.

Инкапсуляция. Инкапсуляция — это объединение данных и действий над ними. Это принцип, согласно которому любой класс должен рассматриваться как чёрный ящик — пользователь класса должен видеть и использовать только интерфейс (от английского interface — внешнее лицо, т. е. список декларируемых свойств и методов) класса и не вникать в его внутреннюю реализацию. Это свойство объектов, заключающееся в сокрытии информации о внутренней «жизни» объекта. Т.е. внешний пользователь объекта может использовать его возможности посредством определенного интерфейса, а непосредственно работа с данными и детали ее реализации от него скрыты. Так, в примере с жестким диском, нам для работы с ним достаточно знать, что он может хранить информацию, и позволяет записывать и считывать ее. При этом вовсе необязательно разбираться в том, каким образом хранится информация и как протекают процессы ее записи и чтения. Свойство инкапсуляции облегчает написание программ, и, что самое главное, их модификацию.

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

Полиморфизм Полиморфизмом называют явление, при котором для различных родственных объектов можно задать одинаковое название функции, но действия функция будет выполнять разные, в зависимости от конкретного объекта. Например, надо нарисовать прямоугольник или круг, в зависимости от типов: «прямоугольник», «круг». Но в обоих случаях функция будет иметь имя «Нарисовать». Т.е. действия с одинаковым именем вызывает различное поведение, в зависимости от типа данных.

К наиболее современным объектно-ориентированным языкам программирования относятся C++ и Java.

Языки C++ и Java. За основу языка С++ был взят язык С, дополненный элементами языков BCPL,Simula-67 и Algol-68.

Новая интегрируемая в Internet версия языка, получила название Java. С января 1995 года Java получает распространение в Internet. Принципиальной разницей между Java и C++ является то, что первый из них является интерпретируемым, а второй — компилируемым. Синтаксис языков практически полностью совпадает. С точки зрения возможностей собственно объектно-ориентированных средств язык Java обладает рядом преимуществ перед языком C++. Так, язык Java демонстрирует более гибкую и мощную систему, кроме того, он проще и надежнее.

В силу своей конструктивности идеи объектно-ориентированного программирования используются во многих универсальных процедурных языках, в которые входит специальная библиотека объектно-ориентированного программирования. Это системы программирования TurboVision, VisualBasic, Delphi и др.

Visual Basic подходит для написания небольших и нетребовательных к ресурсам программ. А так как он является языком создания приложений Microsoft Office, то он получил самое широкое распространение.

Delphi является очередным шагом в эволюции компиляторов Паскаля. Среда Delphi стала, по сути, лучшим средством программирования для операционной системы Windows. У языка Delphi есть еще одно очень важное преимущество перед остальными коммерчески успешными языками — он великолепно подходит для обучения программированию. Поэтому его рекомендуют в качестве первого языка для всех учеников и студентов, собирающихся стать профессиональными программистами.

Delphi, Java применяются для создания программ , используемым в Интернете.

Визуальное программирование

В последнее время многие программы, в особенности объектно-ориентированные, реализуются как системы визуального программирования. Отличительной особенностью таких систем является мощная среда разработки программ из готовых «строительных блоков», позволяющая создать интерфейсную часть программного продукта в диалоговом режиме, практически без кодирования программных операций. К числу объектно-ориентированных систем визуального программирования относятся; Visual Basic, Delphi, Visual C++.

Раньше, создание пользовательского интерфейса требовало уйму времени и сил, особенно когда программа должна была работать под управлением операционной системы Windows и иметь графический пользовательский интерфейс. Визуальное программирование сделало эту задачу доступной и начинающему программисту.

Декларативное программирование

Такие языки еще называют языками символьной обработки. Языки символьной обработки сыграли важную роль в программировании. Программист указывает исходные информационные структуры, взаимосвязи между ними и то, какими свойствами должен обладать результат. При этом процедуру его получения («алгоритм») программист не строит (по крайней мере, в идеале). В этих языках отсутствует понятие «оператор» («команда»). Декларативные языки можно подразделить на два семейства – функциональные (Лисп) и логические (типичный представитель – Пролог).

Функциональные языки. ЛИСП, Haskell

Логические языки. Пролог —

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

В последнее время в связи развитием Интернет-технологий получили распространение так называемые скриптовые языки. Скрипт — это набор команд на максимально понятном языке для человека, который может не знать стандартных языков программирования, но нуждается в автоматизации процесса работы с определенной программой. Программы такого типа существовали и раньше, они назывались командными файлами (файлами с расширением .bat).

Характерными особенностями данных языков являются, во-первых, их интерпретируемость (компиляция либо невозможна, либо нежелательна), во-вторых, простота синтаксиса. Было создано достаточно большое количество таких языков, наиболее часто используемые: PHP, TCL, JavaScript, Perl, Python.

Язык HTML (язык разметки Wed страниц в итернете) предоставляет авторам Web-страниц большие возможности для отображения текстовой и графической информации. Но создаваемые с помощью языка HTML страницы остаются статическими — пользователи не могут изменить информацию, расположенную на странице, а так же использовать большинство интерфейсных элементов. Для того чтобы сделать страницу по-настоящему интерактивной, нам нужен еще один язык, выполняемый в контексте браузера, — скриптовый язык.

Скриптовый язык используется для создания интерактивных страниц. Этот язык программирования предоставляет средства для управления браузером. Обычно он не содержит всех возможностей настоящих языков программирования, таких, например, как работа с файлами или управление графикой. Созданные с помощью скриптовых языков программы не могут выполняться самостоятельно — они работают только в контексте браузера, поддерживающего выполнения скриптовых программ. К таким браузерам относятся Microsoft Internet Explorer и Netscape Navigator. Создаваемые на скриптовых языках программы, называемые сценариями или скриптами, включаются в состав Web-страниц и распознаются и обрабатываются браузером отдельно от остального HTML — кода.

Отметим общую тенденцию в развитии языков программирования. Языки развиваются в сторону все большей и большей абстракции. И это сопровождается падением эффективности. Вопрос: а стоит ли этого абстракция? Ответ: стоит. Стоит, так как повышение уровня абстракции влечет за собой повышение уровня надежности программирования. С низкой эффективностью можно бороться путем создания более быстрых компьютеров. Если требования к памяти слишком высоки, можно увеличить ее объем. Это, конечно, требует времени и средств, но это решаемо. А вот с ошибками в программах можно бороться только одним способом: их надо исправлять. А еще лучше — не совершать. А еще лучше максимально затруднить их совершение. И именно на это направлены все исследования в области языков программирования. А с потерей эффективности придется смириться. Но это пока не относится к системному программированию, где эффективность программы важна.

При обучении программированию в настоящее время чаще всего используют универсальные процедурные языки, в которые входят специальные библиотеки объектно-ориентированного и визуального программирования. Это системы программирования TurboVision, VisualBasic, Delphi и др.

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

Требования к программе

1. Правильность. Программа должна соответствовать алгоритму, а значит – приводить к правильному результату.

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

3. Эффективность. Под эффективностью понимают время выполнения программы и требуемый объем оперативной памяти. Чем эти величины меньше, тем эффективнее программа.

4. Удобство пользования. Удобство ввода исходных данных и чтения результатов. Читаемость программы.

Первые два пункта должны безусловно выполняться. А 3-й и 4-й пункты иногда приходят в противоречие. Что из них должно приоритетным?

На начальном этапе программирования старались получить наиболее эффективную программу, не заботясь об удобстве пользования. Этому способствовали очень слабые ресурсы вычислительной техники и отсутствие опыта. Это приводило к тому, что программой мог пользоваться только ее автор, да и тот через некоторое время с трудом мог это делать. Использовать и модифицировать чужую программу иногда было сложнее, чем составить новую. Практически все профессиональные программисты в настоящее время согласились с тем, что к созданию программы надо относиться так же, как к созданию любого товара. Поэтому в настоящее время эффективность уступает удобству пользования. (Конечно все это делается в разумных пределах. Кроме того, бывают исключения, когда главной становится эффективность). Возникли специальные методы и правила составления программ. К этим методам относится:

Структурное программирование

Это понятие относится к процедурному программированию. В широком смысле – структурное программирование – создание удобных в пользовании программ. В узком смысле – программирование в соответствии со структурной теоремой. Ее доказали итальянцы Бом и Якопини.

Теорема: Всякая программа может быть составлена из 3-х основных блоков: функционального блока, развилки и обобщенного цикла.

Основное свойство этих конструкций – 1 вход и 1 выход. Кроме того, две последние конструкции можно представить как обобщенный функциональный блок. Эти блоки в программе не будут пересекаться. Поэтому программа будет читаться свеху-вниз, без переходов. Основой структурного программирования является отказ от оператора GO TO – оператора безусловного перехода. Программа становится легко читаемой. Если нет переходов, то отпадает необходимость рисовать блок-схемы. Алгоритмы пишут на псевдокоде. Блок-схемы рисуют лишь укрупнено, изображая лишь отдельные модули, чтобы показать связи.

Жесткое требование структурного программирования – использовать только эти 3 конструкции. Более мягкое – разрешается использовать оператор выбора и другие операторы, не нарушающие свойство блоков: «1 вход – 1 выход». Оператор GO TO разрешается использовать в исключительных случаях, и только вперед. Обычно исключительными случаями бывают досрочный выход из цикла и досрочное окончание выполнения программы. В современных языках программирования есть для этого специальные операторы.

Дополнительные требования структурного программирования

1.Ввод исходных данных. Ввод должен быть оформлен так, чтобы было понятно, что нужно вводить. Если данные должны находиться в какой-то области, отобразить это на экране. Например:

Если это размерная величина, задать размерность.

2. Вывод результатов должен быть понятным и наглядным.

3. Программа должна быть, по возможности, универсальной. В том смысле, что исходные данные должны вводиться через операторы ввода, а не быть в формулах и операторах виде чисел.

4. В программе должны быть комментарии. Должен быть заголовок, показывающий назначение программы, метод решения, обозначение входных и выходных данных, фамилия программиста и дата последнего изменения программы.

5. Имена переменных должны быть такими же, как в алгоритме, а те имена, которых нет в алгоритме, должны быть информативными. Не ленитесь применять длинные имена.

6. Использование отступов при наборе программы. Лучше сразу набирать с отступами, чем делать это на конечном этапе оформления программы, т.к. это ускоряет процесс отладки.

Модульное программирование

Модулем, в данном случае, будем называть отдельные, особо оформленные части программы (процедуры и функции). Модули имеют 1 точку входа и 1 точку выхода.

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

Дальнейшее развитие этой технологии привело к тому, что модульная программа – это такая программа, в которой изменения в любом модуле не вызывает изменений в остальных частях программы. Значит, главная особенность – это независимость модулей. Каждый модуль, в свою очередь, может быть разделен на несколько модулей. В результате программа будет иметь иерархическую структуру.

1.Отдельные модули можно изменять, заменять их на другие — это не вызовет изменения в других частях программы. Это делает программу более гибкой и уменьшает количество ошибок. Такую программу легче составлять и отлаживать.

2.Отдельные модули могут программировать разные люди, причем им необязательно знать, как работает вся программа. Позволяет использовать коллективный труд, и необязательно все программисты должны иметь высокую квалификацию. Это повышает производительность и уменьшает стоимость программы.

3. Позволяет более рационально использовать память.

Программирование сверху-вниз

Его называют иногда нисходящим программированием. Существует такое определение: это проектирование программ путем последовательного разбиения большой задачи на меньшие подзадачи. Но это общее определение.

Это понятие относится к технологии разработки программы. Эта технология возникла при разработке больших программ, над которыми работали несколько программистов. Каждый разрабатывал и отлаживал свои модули. Затем все это надо было соединить и провести отладку и тестирование всей системы. Обычно этот процесс занимает длительное время. Каждый модуль работает правильно, а система неработоспособна и ошибку найти трудно. Испытание систем в некоторых разработках длилось от 2 до 3 лет, что иногда вызывало отказ от проекта.

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

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

Отладка главной программы начинается до того, как разработаны подпрограммы, которые на этом этапе заменяются фиктивными подпрограммами ( называются заглушками), они содержат только вход и выход. На этом этапе производятся только связи между главной программой и подпрограммами первого уровня (обычно через формальные и фактические параметры). Далее разрабатываются сами подпрограммы первого уровня, а подпрограммы более низкого уровня заменяются заглушками и т.д.

На каждом этапе основное внимание уделяется связям. К отладке приступают до того, как завершена вся программа.

Основная идея – на каждом уровне не обращают внимания на описания модулей нижних уровней.

При отладке на каждом уровне разработанные модули добавляют в программу по одному.

Основное достоинство – упрощает отладку и тестирование. Исключает отладку на уровне системы.

Иногда сочетают нисходящее (сверху — вниз) и восходящее (снизу-вверх) программирование. Бывает так, что уже имеются ранее разработанные и отлаженные модули или стандартные модули. В этом случае поступают в соответствии с порядком нисходящего программирования, т.е. включают модули по одному на нужном уровне.

Программирование на языке Visial Basic

Язык программирования Visial Basic сокращенно (VB), встроенный в EXCEL, обладает всеми возможностями языка VB и имеет дополнительные возможности EXCEL. Поэтому он называется Excel Visial Basic (EVB).

Этот язык относится к процедурным языкам с возможностями объектного и визуального программирования. (Об объектном и визуальном программировании вам будет рассказано позже).

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

Для создания модуля надо выполнить:

Сервис – Макрос – Редактор Visial Basic,

Далее — Insert – Module или Вставка – Модуль.

После этого можно набирать текс программы. Программа записывается в виде процедур. В VB существуют 2 вида процедур: процедура – подпрограмма (Sub) и процедура – функция ( Function). Начнем с процедуры – подрограммы, она имеет вид:

Переменные

Переменная – именованная область памяти, отведенная для временного хранения данных, которые могут изменяться в ходе выполнения программы. Каждая переменная должна иметь имя. Переменная может иметь или не иметь указанный тип данных.

Значение переменной – это содержимое тех ячеек памяти, в которых хранится переменная.

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

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

Типы данных

Byte — имеет размер 1 байт и может принимать значения от 0 до 255 (целые числа).

Boolean имеет размер 2 байта и может принимать значения да или нет. Применяется в логических операциях

Integer – целое, имеет размер 2 байта и может принимать значения от -32 768 до + 32 767.

Long Integer – длинное целое, имеет размер 4 байта и может принимать значения от – 2.1*10 9 до + 2.1*10 9 .

Для вещественных чисел используются типы:

Single – 4 байта

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

Создание переменной называется объявлением или описанием переменной. Для этого используется инструкция Dim . Оператор Dim имеет следующий синтаксис:

Dim имя переменной As тип переменной.

Dim x As Integer, y As Single

Если вы не сделаете описание переменной, то она примет тип Variant .

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

где слева от знака равенства находится имя переменной, а справа – выражение. Выражение может содержать числа, переменные, функции, которые могут быть объединены знаками арифметических операций. Если несколько операторов находится на одной строке, между ними ставится знак : (двоеточие).

Основное правило программирования : Все переменные в правой части выражения должны быть заранее определены, т.е. им должны быть присвоены значения.

Приоритет выполнения операций

Если в выражении использовано несколько операций, то результат может зависеть от последовательности, в которой эти операции выполняются. VB выполняет операции в соответствии с их приоритетом:

1. Вызов функций и скобки
2. ^ — возведение в степень
3. *, / — умножение и деление
4. + сложение и вычитание.

Для изменения порядка выполнения действий используются скобки. В VB используются только круглые скобки. Скобки могут быть вложенными в другие скобки.

Имена (переменных и не только) должны начинаться с буквы, не могут содержать пробелов и знаков, кроме _ ( нижнее подчеркивание). Большие и маленькие буквы воспринимаются одинаково.

Ввод данных

1.С помощью оператора присваивания

2. Ввод в диалоговом окне. Используется функция InputBox.

x=(InputBox(“Введите x”, “Ввод x”).

При запуске программы появится диалоговое окно, в которое надо ввести число – значение переменной x.

3. Ввод из ячеек таблицы.

в этом случае с листа 1 из ячейки A2 введется число, которое присвоится как значение переменной x. Value – функция, преобразующая данные в численные. Возможен другой способ:

где i – номер строки, j – номер столбца. Они должны быть определены

Вывод результатов

1.С использованием диалогового окна

Можно вывести несколько переменных:

MsgBox “z=”& z & “ y=” & y

Вывод в заданном формате

Количество значков # перед точкой показывает количество знаков целой части числа, а после точки – количество десятичных знаков.

2. Вывод в ячейки таблицы

Некоторые встроенные функции VB

Sin(x), Cos(x), tan(x), -синус, косинус, тангенс соответственно

Abs(x) означает |x|

asin(x), acos(x), atan(x) – арксинус, арккосинус, арктангенс соответственно

log(x) означает натуральный логарифм ln x

log(x)/log(10) — десятичный логарифм lg x

sqr(x) — квадратный корень

Аргумент функции обязательно должен быть в скобках. Аргументом может быть любое выражение.

Линейные вычислительные процессы

Пример. Вычислить выражение:

Запишем в виде программы. Вначале надо задать исходные данные. Исходными данными являются a и y.

a = InputBox(«Введите а», «Ввод a»)

Z = Exp(Sin(y) ^ 3) + a ^ (1 / 3) * (Log(Atn(a * y)) + 3) / (3 * Sin(a) + 1 / Tan(a))

MsgBox «z Введите а», «Ввод a»)

chis=Log(Atn(a * y)) + 3

znam=3 * Sin(a) + 1 / Tan(a)

Z = Exp(Sin(y) ^ 3) + a ^ (1 / 3) * chis/znam

MsgBox «z center»>Разветвляющиеся вычислительные процессы

Условный оператор, линейная форма, общий вид:

If условие then оператор_1 else оператор_2

Условия – это логические выражения, т.е выражения, объединенные знаками: >, =, (означает неравно), and (и), or (или). Например:

Y= 1+(z-a) 2 , если a+z > b

Y=b 2 – (z+a), если a+z

оператор будет иметь вид:

if a+z >b then y=1+(z-a) 2 else y= b 2 – (z+a)

Линейную форму используют для простых выражений и если имеются два условия.

Блочная форма

Блочную форму используют при более сложных выражениях и если условий больше двух. Общий вид:

If условие_1 then

Elseif условие_2 then

Elseif условие_3 then

Блок остальных операторов

Z=0 в других случаях.

Оператор будет иметь вид:

Elseif x>o and x

Операторы циклов

Оператор For … next

For счетчик = начало To конец [ step шаг]

Операторы и переменные в квадратных скобках – это необязательные параметры, которые могут быть опущены. Число выполнений этого оператора определяется параметрами начало и конец. Переменная счетчик при выполнении увеличивается на величину, заданную параметром шаг. Если шаг равен единице, то он может быть опущен. Необязательный параметр Exit For служит для экстренного прекращения цикла. Нельзя изменять значение счетчика внутри цикла.

Пример . Вычислить функцию y = (x 2 + 1)*e x +1 при x от -4 до 6 с шагом 0,5. Результаты вывести на лист в первый и второй столбцы.

For x=-4 to 6 step 0.5

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

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

Пример. Последовательность чисел з адана формулой x n +2 = x n +1 2 – 0,6x n +0,1, где n – номер элемента. Каждый элемент вычисляется по значениям двух предыдущих элементов. Такая последовательность называется последовательностью второго порядка. Необходимо задать первые 2 значения.

x 0 =1; x 1 = 2. Вычислить x 20 .

Циклы с условиями

Исследование и реализация базовой вычислительной машины с внутренним языком высокого уровня тема диссертации и автореферата по ВАК РФ 05.13.15, кандидат технических наук Чернов, Сергей Александрович

Оглавление диссертации кандидат технических наук Чернов, Сергей Александрович

1. ПРЕДПОСЫЛКИ К СОЗДАНИЮ ЭВМ С ВНУТРЕННИМ ЯЗЫКОМ ВЫСОКОГО УРОВНЯ.

1.1 Преимущества и недостатки ЯВУ в сравнении с языком Ассемблера.

1.2 Традиционные ЭВМ с оптимизирующими компиляторами ЯВУ.

1.3 Машины языков высокого уровня.

1.4 МВК Эльбрус и язык Эль-76.

1.5 Базовая вычислительная машина с внутренним языком высокого уровня.

2. ТЕОРЕТИЧЕСКАЯ МОДЕЛЬ МАШИННОГО ЯЗЫКА ВЫСОКОГО

2.2 Абстрактная FALGOL-машина. Операционная семантика языка.

2.3 Трансформационная семантика.

3. ПРИНЦИПЫ РЕАЛИЗАЦИИ ЭВМ С ВНУТРЕННИМ ЯЗЫКОМ ВЫСОКОГО УРОВНЯ.

3.1 Основные положения.

3.2 Базовая вычислительная машина.

3.3 Язык ассемблера и система программирования.

4. СТРУКТУРА БАЗОВОЙ ВЫЧИСЛИТЕЛЬНОЙ МАШИНЫ.

4.2 Память переменных.

4.3 Память подпрограмм и память структур.

5. СИСТЕМА КОМАНД.

5.1 Представление команд в БВМ и их мнемоническое обозначение.

5.2 Схемы выполнения команд.

5.3 Базисные команды.

5.4 Команда сохранения.

5.6 Элементарные объектные константы.

5.7 Индексы вхождения переменных.

5.9 Указатели переменных.

5.11 Логические константы.

5.12 Команды условного выполнения.

5.13 Объектные команды и объектные термы.

5.14 Элементарные функциональные константы.

5.15 Пустая команда и команда останова.

5.16 Команды индексного доступа к элементам структур.

5.18 Упаковка термов и их последовательностей.

6. ФУНКЦИОНИРОВАНИЕ БВМ.

6.1 Ситуационный принцип дешифрации команд.

6.2 Машинный цикл.

6.3 Представление константных процедур.

6.4 Выполнение подпрограмм с использованием регистров IP, РР.

6.5 Определение характеристик процедур.

6.6 Динамическое связывание переменных. Обработка подстановки.

6.7 Обработка рекурсивных процедур.

6.8 Сборка мусора.

6.9 Исследование влияния структурных параметров БВМ на производительность.

6.9.1 Постановка задачи.

6.9.2 Описание стратегий управления активными регистрами.

6.9.3 Разработка программы, реализующей укрупненную имитационную модель вычислительной системы.

6.9.4 Исходные данные и анализ результатов моделирования.

7.3 Виртуальная машина компилятора.

8. ПРЕДСТАВЛЕНИЕ Л4£С4£-ПРОГРАММ СРЕДСТВАМИ БАЗОВОГО МАШИННОГО ЯЗЫКА.

8.1 Организация выбора по условию.

8.2 Циклическое выполнение.

8.3 Определение и использование структур и массивов.

8.4 Строки символов.

8.5 Процедуры и функции.

8.6 Сравнение характеристик P^sc^l-программ и программ на базовом машинном языке.

Рекомендованный список диссертаций по специальности «Вычислительные машины и системы», 05.13.15 шифр ВАК

Разработка обрабатывающих и управляющих компонент организации вычислительных процессов в проблемно-ориентированных вычислительных системах 1985 год, кандидат технических наук Смольников, Владимир Александрович

Вычислительные устройства с параллельной и изменяемой архитектурой для задач обработки изображения 2002 год, кандидат технических наук Аряшев, Сергей Иванович

Современные методы статического и динамического анализа программ для автоматизации процессов повышения качества программного обеспечения 2012 год, доктор физико-математических наук Аветисян, Арутюн Ишханович

Автоматизированная система проектирования математического обеспечения бортовых вычислительных комплексов 1984 год, кандидат физико-математических наук Зуев, Андрей Львович

Исследование методов оптимизации программ м разработка оптимизирующего компилятора с языка паскаль для центрального процессора АС-6 1984 год, кандидат физико-математических наук Челноков, Валерий Павлович

Введение диссертации (часть автореферата) на тему «Исследование и реализация базовой вычислительной машины с внутренним языком высокого уровня»

Актуальность. Постоянно совершенствуя ЭВМ, основанные на принципах, предложенных Фон-Нейманом еще в середине прошлого века, разработчикам удается получать все более высокие уровни производительности вычислительных машин, при этом сохраняя машину Фон-Неймана практически незыблемым стандартом. Стандартизация и повсеместное использование ЭВМ с фон-Неймановской архитектурой при постоянном росте капитала, вкладываемого компаниями в компьютерный бизнес, являются сдерживающими факторами развития альтернативных архитектур ЭВМ.

Анализ производительности отдельно взятого семейства промышленно выпускаемых процессоров, реализующих фон-Неймановскую модель вычислений (например, процессоров корпорации Intel), показывает практически линейную её зависимость от степени интеграции и тактовой частоты. Таким образом, можно утверждать, что серьёзный рост производительности достигается за счет развития технологии элементной базы, а различные широко рекламируемые нововведения в структуру, функционирование и систему команд процессоров и ЭВМ, в целом, влияют на их производительность крайне мало.

Развитие технологии элементной базы ЭВМ, основанной на современных физических принципах, не может продолжаться бесконечно долго и в силу известных ограничений, рано или поздно, этот фактор повышения производительности будет исчерпан. По-видимому, именно с этого момента проблема повышения эффективности вычислительного процесса за счет применения новых принципов его организации станет актуальной и, возможно, тогда начнется активное развитие и внедрение альтернативных архитектур ЭВМ, прототипом одной из которых как раз и является архитектура базовой вычислительной машины (БВМ), разрабатываемой и исследуемой в рамках настоящей диссертации.

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

Сознание программистов все более абстрагируется от аппаратуры, на которой будет выполняться программа, и оперирует объектами и конструкциями, предоставляемыми ЯВУ. В этом смысле компилятор с языка высокого уровня является нежелательным посредником между программистом и машиной, поскольку при компиляции теряется информация о структуре программы и внутренних семантических связях её объектов. В результате, пусть даже эквивалентная содержательно, машинная программа представляет собой застывший набор элементарных операций, выполнение которых не может быть основано на глубоком анализе и использовании семантических зависимостей описанных программистом в исходном тексте. Рост эффективности выполнения такой машинной программы возможен только за счет применения средств общего плана, таких как организация конвейера элементарных операций, спекулятивные вычисления, суперскалярность и т.д. Сказанное является одним из аспектов существующей и хорошо известной проблемы «семантического разрыва» [1], т.е. проблемы рассогласования уровней машинных языков и языков программирования, применяемых человеком для непосредственного решения поставленных перед ним задач. Преодоление семантического разрыва в будущем, безусловно, откроет новые перспективы развития и применения вычислительной техники.

Научная новизна. Попытки устранения семантического разрыва предпринимались неоднократно. Разработано множество аппаратных интерпретаторов, широко известных в программной индустрии языков высокого уровня, например, Lisp-, Prolog-, Рефал- машины (см. разд. 1.3) и т. д.

Каждая из названных машин была специально разработана для интерпретации программ конкретного ЯВУ, но их системы команд не являются машинным представлением множества примитивов реализуемого языка. Разработка этих машин исходила из потребностей компилятора конкретного языка. Отличия в архитектуре машин реализующих один и тот же язык, но созданных разными разработчиками, приводили к появлению различных диалектов реализуемых языков программирования, поскольку для достижения приемлемого уровня эффективности выполнения программ на конкретной машине, как правило, было необходимо некоторое ограничение или изменение исходного языка, что в результате приводило к проблеме переносимости программ даже между машинами, создававшимися, в принципе, для интерпретации одного и того же языка.

Возможно первым проектом ЭВМ, базирующимся на новых архитектурных принципах, был проект ЭВМ «Украина» [2], разработанный в СССР в конце 60-х годов прошлого века. В основу этого проекта положена идея структурной интерпретации языка высокого уровня. Впоследствии, эта идея нашла практическое воплощение в ЭВМ серии МИР [3]. Позднее были созданы МВК семейства Эльбрус и язык Эль-76 [1] (см. разд. 1.4).

Развитие идеи структурной интерпретации языков программирования высокого уровня продолжалось в работах В.Н Фалька [4], который в 1987 г. опубликовал теоретическую модель языков высокого уровня, имеющую «двойное применение». Дело в том, что эту модель можно рассматривать не только как модель языков программирования высокого уровня, но и как модель архитектуры перспективных ЭВМ с внутренним ЯВУ.

Самое главное FALGOL-модель не была ориентирована ни на какой конкретный язык программирования высокого уровня, ни на какую определенную архитектуру ЭВМ, являясь строгим формальным описанием наиболее общих, фундаментальных механизмов реализации ЯВУ, инвариантных относительно того, какой -аппаратной или программной эта реализация будет являться.

В результате исследований вариантов реализации программного интерпретатора FALGOL’а [5-7], сформировались основные принципы его структурной организации, принципы представления символов теоретического языка, а также фрагменты алгоритма функционирования интерпретатора FALGOL-щотфамм, например, алгоритмы подсчета дефицита и объектности, необходимые для выявления константных процедур (см. основную часть работы).

Начиная с 1992 г. предпринимались попытки комплексной программной реализации интерпретатора расширенного языка FALGOL, однако, до создания относительно законченной, отчуждаемой системы ни одна из этих попыток доведена не была. Тем не менее, выполненные НИР внесли существенный вклад в развитие принципов построения механизмов, положенных в основу архитектуры базовой вычислительной машины, разработке и исследованию которой полностью посвящена данная диссертация.

В ходе работы над диссертацией удалось на основе усовершенствованной теоретической модели разработать базовый машинный язык (БМЯ), структуру и алгоритм функционирования базовой вычислительной машины, сделав тем самым ещё один шаг на пути создания ЭВМ с внутренним ЯВУ (см. рис.1.2).

Резюмируя сказанное, научная новизна диссертации состоит в следующем:

1) Модифицирована и расширена элементарными константами теоретическая модель языков высокого уровня FALGOL. На основе этой модели разработан базовый машинный язык высокого уровня и программно, на платформе Intel х86, MS Windows 98, реализован его интерпретатор — базовая вычислительная машина, являющаяся прототипом ЭВМ с внутренним ЯВУ. Создание такой ЭВМ, предполагается, позволит:

• решить проблему семантического разрыва, препятствующую полному переводу программирования на ЯВУ (см. разд.1.1);

• повысить производительность и обеспечить программную совместимость вновь разрабатываемых архитектур.

2) Предложен новый принцип формирования системы команд ЭВМ с внутренним ЯВУ, обеспечивающий её непротиворечивое расширение (применение механизма макроопределения новых команд через уже существующие, при этом выделяется некоторое множество базисных команд). Этот принцип позволяет точно, в виде TviLGOL-nporpaMMbi, определить семантику каждой команды БВМ, что необходимо как разработчику аппаратуры, так и программисту.

3) Сформулирован и опробован на практике новый подход к организации вычислительного процесса, сочетающий в рамках одной ЭВМ такие средства как:

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

• эквивалентные преобразования программы во время вычислений, направленные на сокращение числа выполняемых операций и времени выполнения программы;

• стековый принцип обработки, т.е. размещение операндов в стеке;

• переменный формат команды, обеспечивающий высокую компактность программного кода.

Практическая ценность. БВМ реализована в виде программной модели и интегрирована в программный комплекс Falgol Virtual Machine (FVM), обладающий полным набором средств, необходимых для дальнейшего развития БВМ в направлении реальной ЭВМ с внутренним ЯВУ. FVM может также использоваться в качестве программного средства учебного назначения (ПСУН) в учебном процессе, поскольку предоставляет возможность изучения БМЯ и принципов работы БВМ.

Программы на БМЯ могут быть откомпилированы средствами FVM в двоичные файлы, что позволяет, еще до появления аппаратно реализованной БВМ, сформировать пакеты системных и прикладных программ, готовых к исполнению. Программная модель БВМ допускает загрузку файлов программ, содержащих машинный код БМЯ, что обеспечивает возможность выполнения и отладки программ, созданных с использованием средств, не входящих в состав программного комплекса.

Кроме БВМ, в состав указанного выше программного комплекса включены виртуальная машина компилятора (ВМК), оптимизатор машинного кода (ОМК), средства отображения состояния БВМ и среда ассемблера БВМ. ОМК обеспечивает высокую степень компактности машинного кода программ на БМЯ и может осуществлять упаковку программ в любой системе команд, к которой применимы средства упаковки термов, используемые в БВМ.

Разработанный блок ситуационного дешифратора команд обеспечивает высокую скорость дешифрации команд и может применяться для реализации вычислительных машин трансформационного типа. Средства описания ситуаций, в особенности это относится к средствам описания ситуаций, используемым при реализации ВМК, позволяют описывать ситуации в виде компактно хранимых и определяемых в наглядной форме декартовых произведений множеств значений тегов регистра команд и активных регистров, что допускает автоматическую генерацию загрузочных таблиц АЗУ блока дешифрации ситуации (см. основную часть работы).

Компоненты программного комплекса являются функционально законченными объектами и могут быть оформлены в виде отдельных программ, что допускает их раздельное использование и дальнейшее развитие.

Цель и задачи диссертации. Диссертация преследовала две главные цели:

I. Разработку и исследование архитектуры базовой вычислительной машины, как макета для отладки и проверки принципиальных научно-технических решений, необходимых для создания реальной ЭВМ с внутренним языком высокого уровня.

II. Создание программной модели БВМ и комплекса инструментальных средств, позволяющих исследовать и развивать БВМ.

Для достижения поставленных целей требовалось, чтобы были решены следующие основные задачи.

• сформулированы принципы создания базовой вычислительной машины с внутренним языком высокого уровня;

• разработана структура БВМ, структуры ситуационного дешифратора команд, процессора и компонентов памяти;

• разработана система команд БВМ и алгоритмы выполнения каждой из команд БВМ;

• определен алгоритм машинного цикла БВМ;

• разработан алгоритм функционирования БВМ в целом;

• разработан и исследован метод компактного представления структур данных, найдены эффективные алгоритмы их обработки;

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

• разработана программная модель БВМ;

• разработан язык ассемблера БВМ;

• разработан и испытан программный комплекс, обеспечивающий полный цикл создания, отладки и прогона программ на базовом машинном языке, включающий: редактор ассемблерного кода, ВМК с языка ассемблера в машинный код БВМ, ОМК, средства отображения и изменения состояния БВМ (среду отладки и прогона программ).

В основе решения перечисленных выше задач лежит теоретическая модель языков высокого уровня, основанная на применении нового фундаментального языка FALGOL [8], и изложенные в [9] основные принципы машинного представления FALGOL-щютфамм.

Основной материал диссертации сгруппирован в восемь глав.

Похожие диссертационные работы по специальности «Вычислительные машины и системы», 05.13.15 шифр ВАК

Методы и средства программирования софт-архитектур для реконфигурируемых вычислительных систем 2012 год, кандидат технических наук Коваленко, Василий Борисович

Нечисловая обработка информации на вычислительной машине нетрадиционной архитектуры потока данных 1999 год, кандидат технических наук Провоторова, Анна Олеговна

Методы и средства кроссовой реализации языков высокого уровня для микро-ЭВМ и микропроцессорных систем 1984 год, кандидат технических наук Сархан, Сами Ибрагим

Аппаратная интерпретация основных механизмов работы с данными структурированного типа языков программирования высокого уровня 1984 год, кандидат технических наук Разумовский, Геннадий Васильевич

Методы организации параллельных вычислений в системах обработки данных на базе процессоров с суперскалярной архитектурой 1999 год, доктор технических наук Скворцов, Сергей Владимирович

Заключение диссертации по теме «Вычислительные машины и системы», Чернов, Сергей Александрович

1) Основные конструкции ЯВУ блочно-процедурного типа таких, как Pascal, С или Java могут быть эффективно реализованы в виде макросов базового машинного языка. Это обеспечивает быстрый переход к программированию на БМЯ, программистов знакомых с ЯВУ указанного типа. Освоение базового машинного языка может происходить поэтапно, за счет постепенного вытеснения из программ макросов, приведенных в данной главе, и замены их более эффективными последовательностями команд БМЯ.

2) Программы на базовом языке по объему исходного текста сравнимы с аналогичными по смыслу программами языка Pascal, а по объему машинного кода значительно более компактны и сравнимы с программами на ассемблере для процессоров семейства х86.

3) Недостатком БМЯ, не устраненным на данном этапе исследований, является генерация мусора в памяти БВМ при выполнении ей циклических конструкций программ. Этот недостаток, возможно, будет устранен за счет разработки более совершенных макроопределений для циклов, а также за счет создания эффективных алгоритмов сборки мусора. Однако, для полного устранения эффекта «замусоривания» памяти, скорее всего, необходимы: дополнительное исследование и разработка нового механизма распределения памяти под переменные блока.

Цели, поставленные в процессе подготовки диссертации, полностью достигнуты. В ходе проведенных исследований были получены следующие основные результаты.

1) Разработана архитектура базовой вычислительной машины с внутренним языком высокого уровня, принципы реализации которой обеспечивают её непротиворечивое и обоснованное расширение.

2) Разработан базовый машинный язык высокого уровня, реализованный в виде системы команд БВМ.

3) Разработана структура базовой вычислительной машины. Определен состав и функции всех её компонентов. Показана реализуемость компонентов структуры средствами существующей элементной базы, в виде набора отдельных интегральных модулей. Возможна также, реализация БВМ на одном кристалле. Исследованы зависимости наиболее важных структурных характеристик БВМ от применяемых стратегий управления и параметров потоков команд.

4) Разработаны алгоритмы функционирования БВМ — алгоритм выполнения машинного цикла и алгоритмы выполнения каждой из команд внутреннего языка. Алгоритмы выполнения команд формализованы в программной форме в виде обработчиков ситуаций, что, при аппаратной реализации БВМ, позволяет выделить логику обработки каждой команды и реализовать её на микропрограммном уровне.

5) Детально проработан алгоритм выполнения машинного цикла БВМ. Операции общие для всех команд выявлены и вынесены из обработчиков ситуаций в алгоритм машинного цикла, что позволяет свести к минимуму объем памяти, требуемый для хранения микропрограмм обработки ситуаций. Алгоритм машинного цикла БВМ с незначительными изменениями используется и в ВМК, что говорит о возможности применения данного подхода к организации машинного цикла в вычислительных машинах различного назначения.

6) Предложена схема аппаратного ситуационного дешифратора команд, обеспечивающего полиморфность команд и высокую скорость их дешифрации. Разработаны программные средства описания ситуаций. Обнаружено, что принцип ситуационной дешифрации может применяться не только в БВМ, но и при реализации широкого класса вычислительных машин, что подтверждено применением указанного принципа при создании ВМК.

7) Разработаны и алгоритмически реализованы эффективные методы обработки рекурсивных процедур, удаления неконстантных процедур и команд вызовов переменных.

8) В БВМ реализована прямая аппаратная поддержка сложных структур данных. Предложен и исследован способ компактного представления структур данных, согласующийся с их семантикой. Разработаны алгоритмы выполнения команд индексного доступа к структурам данных, основанные на строгих макроопределениях операций индексной записи и чтения. Предложен алгоритм структуризации, обеспечивающий динамическое расширение структур на стадии обработки. Алгоритм структуризации основан на макроопределении, но реализован в БВМ более эффективным эквивалентным алгоритмом.

9) Разработан язык ассемблера БВМ, обеспечивающий быстрое создание программ на БМЯ, за счет использования мнемонического представления команд, расширенных средств описания переменных и операций над ними и средств описания данных с минимальным указанием на их типы. Синтаксис языка ассемблера описан в расширенной форме Бэкуса-Наура. Текстуально программы на ассемблере БВМ схожи с программами на языке FALGOL. Семантика любой программы на ассемблере совпадает с семантикой /vlLGOL-программы, получаемой подстановкой макроопределений команд БВМ в программу на БМЯ. Поэтому для программирования на БМЯ программисту достаточно знания семантики FALGOL»а и макроопределений команд БВМ, и нет необходимости в детальном изучении особенностей структуры БВМ и реализации алгоритмов выполнения каждой из её команд.

10) Разработаны виртуальная машина компилятора и оптимизатор машинного кода. Выявлено, что ВМК и ОМК могут быть эффективно реализованы аппаратно, на существующей элементной базе. Это открывает возможность создания интерактивной вычислительной системы, интерпретирующей исходные тексты программ на ассемблере БВМ. Разработанный ОМК может применяться для упаковки программ в любой системе команд, к которой применимы средства упаковки термов, используемые в БВМ.

11) Выявлено, что программы на БМЯ по уровню абстракции и объему исходного текста сравнимы с аналогичными в семантическом отношении Pascal-программами, а по объему машинного кода — с ассемблерными программами микропроцессоров семейства х86. Малый объем семантически нагруженного кода открывает перспективы использования БМЯ в качестве языка межмашинного взаимодействия.

12) Обнаружено, что недостатком БМЯ, не устраненным на данном этапе исследований, является генерация значительного объема мусора в памяти БВМ при выполнении ей циклических конструкций программ. Этот недостаток, возможно, будет устранен за счет разработки более совершенных макроопределений для циклов, а также за счет создания эффективных алгоритмов сборки мусора. Однако, для полного устранения эффекта «замусоривания» памяти, скорее всего, необходимы дополнительное исследование и разработка нового механизма распределения памяти под переменные блока.

13) Разработан программный комплекс под рабочим названием Falgol Virtual Machine, включающий программную модель БВМ, ВМК, ОМК, средства отображения и изменения состояния БВМ, среду программирования на ассемблере БВМ. Программный комплекс может использоваться для исследования и изучения БМЯ, создания и отладки программ на БМЯ в отсутствии аппаратно реализованной БВМ, а также в качестве основы для дальнейшего совершенствования БМЯ и БВМ.

14) Основным и наиболее значимым практическим результатом диссертации можно считать создание FVM, поскольку он явился первой отчуждаемой реализацией БВМ, основанной на теоретической модели языка FALGOL. Ожидается, что программный комплекс позволит существенно расширить круг лиц занимающихся разработкой или, по крайней мере, изучением БМЯ.

15) Комплекс программ Falgol Virtual Machine доведен до уровня программного средства учебного назначения и может быть применен в учебном процессе кафедр МЭИ (ТУ) для углубленного изучения принципов работы вычислительных машин с внутренними ЯВУ.

Список литературы диссертационного исследования кандидат технических наук Чернов, Сергей Александрович, 2003 год

1. Пентковский В.М. Язык программирования Эль-76. Принципы построения языка и руководство к пользованию. 2-е изд. испр. и доп. — М.: Наука. Гл. ред. физ.-мат. лит., 1989 (Б-чка программиста).

2. Глушков В.М., Михновский С.Д., Рабинович 3.JI. ЭВМ со структурной интерпретацией языков высокого уровня // Кибернетика.-1981№4. С. 73-81.

3. Глушков В.М., Стогний А.А., Молчанов И.Н. Алгоритмический язык малой электронной цифровой вычислительной машины МИР, Т.2, кн. 1, изд-во «Нау-кова думка», Киев, 1971.

4. Криницкий Н.А., Мороховец Ю.Е., Мусина М.Д., Фальк В.Н. Разработка принципов построения бортовой ЭВМ с языком высокого уровня. Отчет о НИР № 02860000485, М., МИРЭА, 1985 92с.

5. Мороховец Ю.Е., Мусина М.Д., Фальк В.Н. «Принципы построения и возможности реализации базового машинного языка высокого уровня», Труды МЭИ №86, 1986 г.

6. Мороховец Ю.Е., Фальк В.Н. «Принципы построения аппаратно-программного обеспечения ВС с внутренним языком высокого уровня», Отчет о НИР №02890006301, МИРЭА, 1989 г.

7. Фальк В.Н. Теоретическая модель языка программирования высокого уровня // Программирование, №4, 1987. С. 3-12

8. Мороховец Ю.Е., Фальк В.Н. Разработка архитектуры вычислительной машины с внутренним языком высокого уровня. Отчет о НИР № 01980005592. Инв. № 02.99.00 04466. М.: МЭИ, 1999. 34 с.

9. Майерс Г. Аритектура современных ЭВМ. М.: Мир, 1985.

10. Computer architecture: some old ideas that have not quite made in yet / Dening P.-CACM, 24, 1981.

11. Ананьев JI.И. Перемещение задач в МВК Эльбрус. Препринт / ИТМ и ВТ

12. АН СССР. М., 1985. — №5. — 37 с.

13. Валиев К.А. и др. Развитие элементной базы высокопроизводительных ЭВМ // Информационные технологии и вычислительные системы. 1996. — №1.

14. Ж.К. Голенкова, А.В. Заблоцкий, M.JI. Мархасин, С.С. Порошин,

15. Б.В. Цесин, A.M. Шугаев. Руководство по архитектуре IBM PC AT. М.: ООО «Консул», 1992.-950 с.

16. Искусственный интеллект: В 3-х кн. Кн. 3. Программные и аппаратные средства: Справочник/ Под ред. В.Н. Захарова, В.Ф. Хорошевского. М.: Радио и связь, 1990. — 368 с.

17. Андреев В.М., Голосов И.С., Самойленко С.М. Особенности проведения оптимизирующих преобразований // Методы трансляции и конструирования программ. Новосибирск: ВЦ СО АН СССР, 1986. — С.55-59.

18. Дж. Айлиф. Принципы построения базовой машины. М.: Издательство «Мир», 1973.- 120 с.

19. Задыхайло И.Б., Камынин С.С., Любимский Э.З., Вопросы конструирования вычислительных машин из блоков повышенной квалификации, изд-во ИПМ АН СССР, М., 1971, препринт №68.

20. J. Backus. Can Programming be Liberated from the Von Neumann Style? A Functional Style and its Algebra of Programs. Communications of ACM, 21 (8), 613-641 (Aug., 1978).

21. Department of Defense. Reference manual for the Ada Programming Language. Superintendent of Documents, US Government Printing Office, Wahington, D.C. 20402, 1980.

22. Вегнер П. Программирование на языке АДА / Пер.с англ. ред. В.Ш.Кауфмана. М.: Мир, 1983. — 240 с.

23. Allen J. Anatomy of LISP. New-York: McGraw-Hill, 1978. — 273 p.

24. Турчин В.Ф- Метаязык для формального описания алгоритмических языков // Цифровая вычислительная техника и программирование. М.: Сов. радио,1966.-С. 116-124.

25. Турчин В.Ф. Метаалгоритмический язык // Кибернетика. 1968. — №4 -С. 45-54.

26. Базисный Рефал и его реализация на вычислительных машинах / ЦНИИПИАСС. М„ 1977. — 238 с.

27. R.W. Doran High-Level Language Computer Architecture. Academic Press, New York, 1975, pages 63-108. Chapter: Architecture of Stack Machines.

28. Пентковский B.M. Языковые основы проектирования системы Эльбрус // Системное и теоретическое программирование: Тез. докл. 4 Всесоюзн. симпоз. -Кишинев.: Кишиневский государственный университет, 1983. С. 294—296.

29. Java Virtual Machine Specification // Sun Microsystems, Inc http://java.sun.com/docs/books/

30. Чернов C.A. «Разработка и исследование механизмов выполнения программ процессором с внутренним языком высокого уровня». Дис. на соискание степени магистра, М.: МЭИ, 2000 457 с.

31. Чернов С.А. Ассемблер виртуальной FALGOL-uam\mb\ // «Радиоэлектроника, электротехника и энергетика»: Тез. докл. Девятой Междунар. науч.-техн. конф. студентов и аспирантов. В 3-х т. М.: Изд-во МЭИ, 2003. — Т. 1. С. 351 -352.

32. Б. Страуструп. Язык программирования С++. Пер. с англ. Киев: «ДиаСофт», 1993.

33. Собоцинский В.В. Практический курс Turbo С++. Основы объектно-ориентированного программирования. М.: Изд-во «Свет», 1992. — 236 с.

34. К. Рейсдорф. Borland С++ Builder 3. Освой самостоятельно: Пер. с англ. -М.: ЗАО «Издательство БИНОМ», 1999. 736 с.

35. Гладков С.А. Фролов Г.В. Программирование в Microsoft Windows: В 2-х ч.-М.: «ДИАЛОГ-МИФИ», 1992. ч.1 — 320 е., ч.2.-288 с.

36. Э. Органик. Организация системы Интел 432: Пер. с англ. М.: Мир, 1987. i • — 446 с.

37. Е. W. Dijkstra, L. Lamport, A. J. Martin, С. S. Scholten, E. M. F. Steffens. On-the-Fly Garbage Collection: An Exercise in Cooperation. Communications of the ACM 20, 966-975 (November, 1978).

38. Burroughs Corporation. The Descriptor A definition of the В 5000 Information Processing System. Burroughs Corp. Detroit, Michigan, 1961.1 45) http://www.citforum.ru/hardware/svk/glava3.shtml Оценка производительности вычислительных систем.

39. Шеннон Р. Иммитационное моделирование систем: искусство и наука . -М.: Мир, 1978,-424 с.

40. Армстронг Дж. Р. Моделирование цифровых систем на языке VHDL. М.:1. Мир, 1992.

41. Поляков А.К. Моделирование ЭВМ на языке VHDL. М.: Изд-во МЭИ,1994.

42. Р. Хантер. Проектирование и конструирование компиляторов / Пер. с англ. М.: Финансы и статистика, 1984. — 232 с.

43. Ф. Вайнгартен. Трансляция языков программирования. М.: Мир, 1977.190 с.

44. Фельдман Дж., Грайс Д., Системы построения трансляторов, пер. с англ., «Алгоритмы и алгоритмические языки», вып. 5, 1971.

45. Рейуорд-Смит В.Дж. Теория формальных языков. Вводный курс / Пер. с англ. М.: Радио и связь, 1988. — 128 с.

46. Фаронов В.В. Программировнаие на персональных ЭВМ в среде Турбо-Паскаль. М.: Изд-во МГТУ, 1991. — 580 с.

47. Пильщиков В.Н. Программирование на языке ассемблера IBM PC. М.: «ДИАЛОГ-МИФИ», 1994.-288 с.

48. The Unicode Standard: Worldwide Character Encoding, Version 1.0, Volume 1, ISBN 0-201-56788-1, and Volume 2, ISBN 0-201-60845-6. Доп. информация no Unicode 1.1 есть на ftp://unicode.org

Обратите внимание, представленные выше научные тексты размещены для ознакомления и получены посредством распознавания оригинальных текстов диссертаций (OCR). В связи с чем, в них могут содержаться ошибки, связанные с несовершенством алгоритмов распознавания. В PDF файлах диссертаций и авторефератов, которые мы доставляем, подобных ошибок нет.

• Разработка обрабатывающих и управляющих компонент организации вычислительных процессов в проблемно-ориентированных вычислительных системах
• Вычислительные устройства с параллельной и изменяемой архитектурой для задач обработки изображения
• Современные методы статического и динамического анализа программ для автоматизации процессов повышения качества программного обеспечения
• Автоматизированная система проектирования математического обеспечения бортовых вычислительных комплексов
• Исследование методов оптимизации программ м разработка оптимизирующего компилятора с языка паскаль для центрального процессора АС-6
• Методы и средства программирования софт-архитектур для реконфигурируемых вычислительных систем
• Нечисловая обработка информации на вычислительной машине нетрадиционной архитектуры потока данных
• Методы и средства кроссовой реализации языков высокого уровня для микро-ЭВМ и микропроцессорных систем
• Аппаратная интерпретация основных механизмов работы с данными структурированного типа языков программирования высокого уровня
• Методы организации параллельных вычислений в системах обработки данных на базе процессоров с суперскалярной архитектурой

Digital Science & Education LP (Company number LP022131), 85 Great Portland Street, First Floor, London, United Kingdom, W1W 7LT

Konstruirovanie kompilyatorov 9783659716652, 3659716650

Table of contents :
Глава 1. Языки программирования и их реализация
Язык и его реализация
Компилятор, интерпретатор, конвертор
Метаязыки
Глава 2. Теоретические основы трансляции
Формальные языки и грамматики
Основные термины и определения
Примеры языков
Порождающие грамматики (грамматики Н. Хомского2F )
Примеры грамматик. Порождение предложений языка
Еще несколько определений
Дерево вывода
Задача разбора
Для чего надо решать задачу разбора
Домино Де Ремера
Разновидности алгоритмов разбора
Эквивалентность и однозначность грамматик
Иерархия грамматик Н. Хомского
Примеры грамматик различных типов
Автоматные грамматики и языки
Граф автоматной грамматики
Конечные автоматы
Преобразование недетерминированного конечного автомата (НКА) в детерминированный конечный автомат (ДКА)
Таблица переходов детерминированного конечного автомата
Программная реализация автоматного распознавателя
Дерево разбора в автоматной грамматике
Пример автоматного языка
Синтаксические диаграммы автоматного языка
Регулярные выражения и регулярные множества
Эквивалентность регулярных выражений и автоматных грамматик
Для чего нужны регулярные выражения
Регулярные выражения как языки
Расширенная нотация для регулярных выражений
Контекстно-свободные (КС) грамматики и языки
Однозначность КС-грамматики
Левосторонние и правосторонние выводы в КС-граматике
Алгоритмы распознавания КС-языков
Распознающий автомат для КС-языков
Самовложение в КС-грамматиках
Синтаксические диаграммы КС-языков
Определение языка с помощью синтаксических диаграмм
Язык многочленов
Синтаксический анализ КС-языков методом рекурсивного спуска
Пример: анализатор многочленов
Основная программа анализатора
Константы, переменные и вспомогательные процедуры
Распознающие процедуры
Требование детерминированного распознавания
LL-грамматики
Левая и правая рекурсия
Синтаксический анализ арифметических выражений
Включение действий в синтаксис
Семантические процедуры
Пример: умножение многочленов
Проектирование
Умножение и вывод
Транслятор многочленов
Обработка ошибок при трансляции
Табличный LL(1)-анализатор
Табличный транслятор многочленов
Стек
Реализация стека
LL(1)-драйвер
Использование множеств символов
Обработка ошибок
Рекурсивный спуск и табличный анализатор
Трансляция выражений
Польская запись
Алгоритм вычисления выражений в обратной польской записи
Схема трансляции выражений
Перевод выражений в обратную польскую запись
Алгоритм Э. Дейкстры перевода выражений в обратную польскую запись (метод стека с приоритетами)
Интерпретация выражений
Семантическое дерево выражения
Представление дерева
Построение дерева
Получение постфиксной записи
Получение префиксной записи
Функциональная запись выражения
Четверки
Вычисление (интерпретация) выражения по его семантическому дереву
Упражнения для самостоятельной работы
Варианты заданий
Варианты обработки
Глава 3. Трансляция языков программирования
Описание языков программирования
Метаязыки
БНФ
Синтаксические диаграммы
Расширенная форма Бэкуса-Наура (РБНФ)
Описания синтаксиса языков семейства Си
Описания синтаксиса языка Ада
Язык программирования «О»
Краткая характеристика языка «О»
Синтаксис «О»
Пример программы на «О»
Структура компилятора
Многопроходные и однопроходные трансляторы
Компилятор языка «О»
Вспомогательные модули компилятора
Драйвер исходного текста
Обработка ошибок
Лексический анализатор (сканер)
Виды и значения лексем
Лексический анализатор языка «О»
Виды лексем языка «О»
Программирование сканера
Распознавание имен
Таблица ключевых слов
Сканирование числовых литералов
Пропуск комментариев
Тестирование сканера
Синтаксический анализатор
Контекстный анализ
Таблица имен
Блочная структура и области видимости
Блок стандартных идентификаторов
Таблица имен компилятора «О»
Информация в таблице имен
Программный модуль OTable
Заполнение таблицы имен
Поиск имен
Контекстный анализ модуля
Трансляция списка импорта
Трансляция описаний
Трансляция определений констант
Трансляция описаний переменных
Контекстный анализ выражений
Контекстный анализ операторов
Генерация кода
Виртуальная машина
Архитектура виртуальной машины
Память
Процессор
Программный счетчик
Стек и указатель стека
Система команд
Программирование в коде виртуальной машины
Программирует компилятор
Программируем вручную
Реализация виртуальной машины
Генератор кода
Распределение памяти
Генерация кода для выражений
Генерация кода для множителей
Трансляция вызовов стандартных функций
Функция ABS
Функции MAX и MIN
Функция ODD
Генерация кода для слагаемых
Генерация кода для простых выражений
Генерация кода для выражений общего вида
Генерация кода для операторов
Трансляция оператора присваивания
Трансляция вызовов стандартных процедур
Трансляция оператора WHILE
Трансляция оператора IF
Завершение генерации
Назначение адресов переменным
Трансляция процедур
Расширенный набор команд виртуальной машины
Процедуры без параметров и локальных переменных
Трансляция заголовка процедуры
Трансляция вызова процедуры
Вход в процедуру и возврат из процедуры
Процедуры с параметрами-значениями без локальных переменных
Распределение памяти для формальных параметров и локальных переменных
Статическое распределение памяти
Распределение памяти в стеке
Трансляция вызова процедуры с параметрами-значениями
Доступ к параметрам процедуры
Трансляция описания процедуры
Вход в процедуру
Выход из процедуры
Процедуры с параметрами-значениями и локальными переменными
Трансляция описаний локальных переменных
Вход в процедуру
Выход из процедуры
Простейшая оптимизация кода
Процедуры-функции с параметрами-значениями и локальными переменными
Вход в процедуру-функцию
Выход из процедуры-функции
Трансляция оператора RETURN
Особенность трансляции параметров-переменных
Подстановка фактического параметра вместо параметра-переменной
Доступ к параметрам-переменным
Пример программы на языке «О с процедурами»
Конструкция простого ассемблера
Язык ассемблера виртуальной машины
Пример программы на ассемблере
Формальный синтаксис языка ассемблера
Программирование на ассемблере
Программа, печатающая себя
Реализация ассемблера
Главная программа и вспомогательные модули
Ассемблирование
Первый и второй проходы ассемблера
Программирование распознавателя
Автоматизация построения и мобильность трансляторов
Автоматический анализ и преобразование грамматик
Автоматическое построение компилятора и его частей
Конструкторы сканеров
Генераторы синтаксических анализаторов
Компиляторы компиляторов
Компиляторы компиляторов и программирование вручную
Использование языков высокого уровня
T-диаграммы трансляторов
Самокомпилятор. Раскрутка
Реализация старого языка для новой машины
Разработка компилятора нового языка раскруткой
Улучшение качества кода при раскрутке
Примеры раскрутки
Унификация промежуточного представления
Промежуточные языки
П-код и виртуальные машины
Модульные компиляторы
Приложение 1. Язык программирования Оберон-2
От переводчика
1. Введение
2. Синтаксис
3. Словарь и представление
4. Объявления и области действия
5. Объявления констант
6. Объявления типов
6.1 Основные типы
6.2 Тип массив
6.3 Тип запись
6.4 Тип указатель
6.5 Процедурные типы
7. Объявления переменных
8. Выражения
8.1 Операнды
8.2 Операции
8.2.1 Логические операции
8.2.2 Арифметические операции
8.2.3 Операции над множествами
8.2.4 Отношения
9. Операторы
9.1 Присваивания
9.2 Вызовы процедур
9.3 Последовательность операторов
9.4 Операторы IF
9.5 Операторы CASE
9.6 Операторы WHILE
9.7 Операторы REPEAT
9.8 Операторы FOR
9.9 Операторы LOOP
9.10 Операторы возврата и выхода
9.11 Операторы WITH
10. Объявления процедур
10.1 Формальные параметры
10.2 Процедуры, связанные с типом
10.3 Стандартные процедуры
11. Модули
Приложение A: Определение терминов
Целые типы
Вещественные типы
Числовые типы
Одинаковые типы
Равные типы
Поглощение типов
Расширение типов (базовый тип)
Совместимость по присваиванию
Совместимость массивов
Совместимость выражений
Совпадение списков формальных параметров
Приложение B: Синтаксис Оберона-2
Приложение C: Модуль SYSTEM
Приложение D: Среда Оберон
D1. Команды
D2. Динамическая загрузка модулей
D3. Сбор мусора
D4. Смотритель
D5. Структуры данных времени выполнения
Приложение 2. Текст компилятора языка «О» на Паскале
Приложение 3. Текст компилятора языка «О» на Обероне
Отличия версий для компиляторов JOB и XDS
Изменение обозначений
Изменения в структуре компилятора
Приложение 4. Текст компилятора языка «О» на Си/Си++
Приложение 5. Текст компилятора «О» на языке программирования Ява
Приложение 6. Текст компилятора «О» на языке программирования Си#
Литература

• Author / Uploaded
• unknown author

• 000
• Like this paper and download? You can publish your own PDF file online for free in a few minutes!Sign Up

File loading please wait.

Citation preview

ОГЛАВЛЕНИЕ ГЛАВА 1. ЯЗЫКИ ПРОГРАММИРОВАНИЯ И ИХ РЕАЛИЗАЦИЯ. 9 Язык и его реализация. 9 Компилятор, интерпретатор, конвертор . 9 Метаязыки . 16 ГЛАВА 2. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ТРАНСЛЯЦИИ . 17 ФОРМАЛЬНЫЕ ЯЗЫКИ И ГРАММАТИКИ . 17 Основные термины и определения . 17 Примеры языков . 20 Порождающие грамматики (грамматики Н. Хомского) . 22 Еще несколько определений. 27 Дерево вывода . 29 Задача разбора . 31 Для чего надо решать задачу разбора. 32 Домино Де Ремера . 33 Разновидности алгоритмов разбора. 34 Эквивалентность и однозначность грамматик . 35 Иерархия грамматик Н. Хомского . 38 АВТОМАТНЫЕ ГРАММАТИКИ И ЯЗЫКИ . 43 Граф автоматной грамматики. 43 Конечные автоматы . 45 Преобразование недетерминированного конечного автомата (НКА) в детерминированный конечный автомат (ДКА). 47

Таблица переходов детерминированного конечного автомата . 50 Программная реализация автоматного распознавателя . 51 Дерево разбора в автоматной грамматике . 52 Пример автоматного языка . 53 Синтаксические диаграммы автоматного языка . 57 Регулярные выражения и регулярные множества . 60 Эквивалентность регулярных выражений и автоматных грамматик . 62 Для чего нужны регулярные выражения . 63 Регулярные выражения как языки . 64 Расширенная нотация для регулярных выражений . 65 КОНТЕКСТНО-СВОБОДНЫЕ (КС) ГРАММАТИКИ И ЯЗЫКИ . 66 Однозначность КС-грамматики . 66 Алгоритмы распознавания КС-языков . 68 Распознающий автомат для КС-языков . 69 Самовложение в КС-грамматиках . 69 Синтаксические диаграммы КС-языков. 70 Определение языка с помощью синтаксических диаграмм .. 73 Синтаксический анализ КС-языков методом рекурсивного спуска . 77 Требование детерминированного распознавания . 87 LL-грамматики . 88 Левая и правая рекурсия . 89 Синтаксический анализ арифметических выражений . 89 Включение действий в синтаксис . 97 2

Обработка ошибок при трансляции . 109 Табличный LL(1)-анализатор . 113 Рекурсивный спуск и табличный анализатор . 128 ТРАНСЛЯЦИЯ ВЫРАЖЕНИЙ . 130 Польская запись . 130 Алгоритм вычисления выражений в обратной польской записи . 132 Перевод выражений в обратную польскую запись . 135 Интерпретация выражений . 137 Семантическое дерево выражения. 139 Упражнения для самостоятельной работы . 152 ГЛАВА 3. ТРАНСЛЯЦИЯ ЯЗЫКОВ ПРОГРАММИРОВАНИЯ . 160 ОПИСАНИЕ ЯЗЫКОВ ПРОГРАММИРОВАНИЯ . 160 Метаязыки . 161 БНФ . 161 Синтаксические диаграммы . 162 Расширенная форма Бэкуса-Наура (РБНФ) . 162 Описания синтаксиса языков семейства Си . 164 Описания синтаксиса языка Ада . 165 ЯЗЫК ПРОГРАММИРОВАНИЯ «О» . 166 Краткая характеристика языка «О» . 167 Синтаксис «О» . 168 Пример программы на «О» . 170 СТРУКТУРА КОМПИЛЯТОРА . 171 3

Многопроходные и однопроходные трансляторы . 173 КОМПИЛЯТОР ЯЗЫКА «О» . 176 Вспомогательные модули компилятора . 178 ЛЕКСИЧЕСКИЙ АНАЛИЗАТОР (СКАНЕР). 181 Виды и значения лексем . 183 Лексический анализатор языка «О» . 184 СИНТАКСИЧЕСКИЙ АНАЛИЗАТОР . 204 КОНТЕКСТНЫЙ АНАЛИЗ . 209 Таблица имен . 209 Контекстный анализ модуля. 220 Трансляция списка импорта . 223 Трансляция описаний . 225 Контекстный анализ выражений . 229 Контекстный анализ операторов. 233 ГЕНЕРАЦИЯ КОДА. 236 Виртуальная машина . 236 Архитектура виртуальной машины . 238 Программирование в коде виртуальной машины . 246 Реализация виртуальной машины . 252 Генератор кода . 258 Распределение памяти . 260 Генерация кода для выражений . 263 Генерация кода для операторов . 277 Завершение генерации . 288 Назначение адресов переменным . 289 4

ТРАНСЛЯЦИЯ ПРОЦЕДУР . 293 Расширенный набор команд виртуальной машины . 293 Процедуры без параметров и локальных переменных . 294 Процедуры с параметрами-значениями без локальных переменных . 297 Процедуры с параметрами-значениями и локальными переменными . 302 Простейшая оптимизация кода . 304 Процедуры-функции с параметрами-значениями и локальными переменными. 305 Трансляция оператора RETURN . 308 Особенность трансляции параметров-переменных . 308 Пример программы на языке «О с процедурами» . 310 КОНСТРУКЦИЯ ПРОСТОГО АССЕМБЛЕРА . 314 Язык ассемблера виртуальной машины . 315 Реализация ассемблера . 321 АВТОМАТИЗАЦИЯ ПОСТРОЕНИЯ И МОБИЛЬНОСТЬ ТРАНСЛЯТОРОВ . 330 Автоматический анализ и преобразование грамматик . 331 Автоматическое построение компилятора и его частей. 332 Использование языков высокого уровня . 339 Самокомпилятор. Раскрутка . 343 Примеры раскрутки . 349 Унификация промежуточного представления. 350 ПРИЛОЖЕНИЕ 1. ЯЗЫК ПРОГРАММИРОВАНИЯ ОБЕРОН-2 . 357 5

ОТ ПЕРЕВОДЧИКА . 357 1. ВВЕДЕНИЕ . 361 2. СИНТАКСИС . 362 3. СЛОВАРЬ И ПРЕДСТАВЛЕНИЕ . 362 4. ОБЪЯВЛЕНИЯ И ОБЛАСТИ ДЕЙСТВИЯ . 365 5. ОБЪЯВЛЕНИЯ КОНСТАНТ. 367 6. ОБЪЯВЛЕНИЯ ТИПОВ . 367 6.1 Основные типы . 368 6.2 Тип массив . 368 6.3 Тип запись . 369 6.4 Тип указатель . 370 6.5 Процедурные типы . 371 7. ОБЪЯВЛЕНИЯ ПЕРЕМЕННЫХ. 371 8. ВЫРАЖЕНИЯ. 372 8.1 Операнды . 372 8.2 Операции . 374 9. ОПЕРАТОРЫ. 378 9.1 Присваивания . 378 9.2 Вызовы процедур . 379 9.3 Последовательность операторов . 380 9.4 Операторы IF . 380 9.5 Операторы CASE . 381 9.6 Операторы WHILE . 382 9.7 Операторы REPEAT . 383 9.8 Операторы FOR . 383 6

9.9 Операторы LOOP . 384 9.10 Операторы возврата и выхода . 384 9.11 Операторы WITH . 385 10. ОБЪЯВЛЕНИЯ ПРОЦЕДУР . 385 10.1 Формальные параметры . 387 10.2 Процедуры, связанные с типом . 389 10.3 Стандартные процедуры . 390 11. МОДУЛИ . 394 ПРИЛОЖЕНИЕ A: ОПРЕДЕЛЕНИЕ ТЕРМИНОВ . 396 Целые типы . 396 Вещественные типы . 396 Числовые типы . 396 Одинаковые типы . 396 Равные типы . 396 Поглощение типов . 397 Расширение типов (базовый тип). 397 Совместимость по присваиванию . 397 Совместимость массивов . 398 Совместимость выражений . 398 Совпадение списков формальных параметров . 399 ПРИЛОЖЕНИЕ B: СИНТАКСИС ОБЕРОНА-2 . 400 ПРИЛОЖЕНИЕ C: МОДУЛЬ SYSTEM . 403 ПРИЛОЖЕНИЕ D: СРЕДА ОБЕРОН . 405 D1. Команды. 406 D2. Динамическая загрузка модулей . 407 7

D3. Сбор мусора. 408 D4. Смотритель . 408 D5. Структуры данных времени выполнения. 409 ПРИЛОЖЕНИЕ 2. ТЕКСТ КОМПИЛЯТОРА ЯЗЫКА «О» НА ПАСКАЛЕ . 411 ПРИЛОЖЕНИЕ 3. ТЕКСТ КОМПИЛЯТОРА ЯЗЫКА «О» НА ОБЕРОНЕ . 443 ОТЛИЧИЯ ВЕРСИЙ ДЛЯ КОМПИЛЯТОРОВ JOB И XDS . 443 ИЗМЕНЕНИЕ ОБОЗНАЧЕНИЙ . 444 ИЗМЕНЕНИЯ В СТРУКТУРЕ КОМПИЛЯТОРА . 444 ПРИЛОЖЕНИЕ 4. ТЕКСТ КОМПИЛЯТОРА ЯЗЫКА «О» НА СИ/СИ++ . 480 ПРИЛОЖЕНИЕ 5. ТЕКСТ КОМПИЛЯТОРА «О» НА ЯЗЫКЕ ПРОГРАММИРОВАНИЯ ЯВА . 511 ПРИЛОЖЕНИЕ 6. ТЕКСТ КОМПИЛЯТОРА «О» НА ЯЗЫКЕ ПРОГРАММИРОВАНИЯ СИ# . 540 ЛИТЕРАТУРА . 568

ГЛАВА 1. ЯЗЫКИ ПРОГРАММИРОВАНИЯ И ИХ РЕАЛИЗАЦИЯ С начала 50-х годов XX века создаются и развиваются языки программирования. Чтобы язык программирования можно было реально применять — писать программы на этом языке и исполнять их на компьютере, язык должен быть реализован. Язык и его реализация Реализацией языка программирования называют создание комплекса программ, обеспечивающих работу на этом языке. Такой набор программ называется системой программирования. Основу каждой системы программирования составляет транслятор. Это программа, переводящая текст на языке программирования в форму, пригодную для исполнения (на другой язык). Такой формой обычно являются машинные команды, которые могут непосредственно исполняться компьютером. Совокупность машинных команд данного компьютера (процессора) образует его систему команд или машинный язык. Программу, которую обрабатывает транслятор, называют исходной программой, а язык, на котором записывается исходная программа — входным языком этого транслятора. Компилятор, интерпретатор, конвертор Различают несколько видов трансляторов: компиляторы, интерпретаторы, конверторы (рис. 1.1). Компилятор, обрабатывая исходную программу, создает эквивалентную программу на машинном языке, которая называется также объектной программой или объектным кодом. Объектный код, как правило, записывается в файл, но не обязательно представляет собой готовую к исполнению программу. Для программ, состоящих из многих модулей, может образовываться много объектных файлов. Объектные файлы объединяются в ис9

полняемый модуль с помощью специальной программыкомпоновщика, которая входит в состав системы программирования. Возможен также вариант, когда модули не объединяются заранее в единую программу, а загружаются в память при выполнении программы по мере необходимости. Интерпретатор, распознавая, как и компилятор, исходную программу, не формирует машинный код в явном виде. Для каждой операции, которая может потребоваться при исполнении исходной программы, в программе-интерпретаторе заранее заготовлена машинная команда или команды. «Узнав» очередную операцию в исходной программе, интерпретатор выполняет соответствующие команды, потом — следующие, и так всю программу. Интерпретатор — это переводчик и исполнитель исходной программы. Различие между интерпретаторами и компиляторами можно проиллюстрировать такой аналогией. Чтобы пользоваться каким-либо англоязычным документом, мы можем поступить поразному. Можно один раз перевести документ на русский, записать этот перевод и потом пользоваться им сколько угодно раз. Это ситуация, аналогичная компиляции. Заметьте, что после выполнения перевода переводчик (компилятор) больше не нужен. Интерпретация же подобна чтению и переводу «с листа». Перевод не записывают, но всякий раз, когда нужно воспользоваться документом, его переводят заново, каждый раз при этом используя переводчика 1.

Одно из основных значений английского interpreter — устный (синхронный) переводчик. 1

Рис. 1.1. Схема работы компилятора и интерпретатора

Нетрудно понять преимущества и недостатки компиляторов и интерпретаторов. Компилятор обеспечивает получение быстрой программы на машинном языке, время работы которой намного меньше времени, которое будет затрачено на исполнение той же программы интерпретатором. Однако компиляция, являясь отдельным этапом обработки программы, может потребовать заметного времени, снижая оперативность работы. Откомпилированная программа представляет собой самостоятельный продукт, для использования которого компилятор не требуется. Программа в машинном коде, полученная компиляцией, лучше защищена от внесения несанкционированных искажений, раскрытия лежащих в ее основе алгоритмов. Интерпретатор исполняет программу медленно, поскольку должен распознавать конструкции исходной программы каждый раз, когда они исполняются. Если какие-то действия расположены в цикле, то распознавание одних и тех же конструкций происходит многократно. Зато интерпретатор может начать испол11

нение программы сразу же, не затрачивая времени на компиляцию, — получается оперативней. Интерпретатор, как правило, проще компилятора, но его присутствие требуется при каждом запуске программы. Поскольку интерпретатор исполняет программу по ее исходному тексту, программа оказывается незащищенной от постороннего вмешательства. Но даже при использовании компилятора получающаяся машинная программа работает, как правило, медленнее и занимает в памяти больше места, чем такая же программа, написанная вручную на машинном языке или языке ассемблера квалифицированным программистом. Компилятор использует набор шаблонных приемов для преобразования программы в машинный код, а программист может действовать нешаблонно, отыскивая оптимальные решения. Разработчики тратят немало усилий, стремясь улучшить качество машинного кода, порождаемого компиляторами. В действительности различие между интерпретаторами и компиляторами может быть не столь явным. Некоторые интерпретаторы выполняют предварительную трансляцию исходной программы в промежуточную форму, удобную для последующей интерпретации. Некоторые компиляторы могут не создавать файла объектного кода. Например, Turbo Pascal может компилировать программу в память, не записывая машинный код в файл, и тут же ее запускать. А поскольку компилирует Turbo Pascal быстро, то такое его поведение вполне соответствует работе интерпретатора. Существуют трансляторы, переводящие программу не в машинный код, а на другой язык программирования. Такие трансляторы иногда называют конверторами. Например, в качестве первого шага при реализации нового языка часто разрабатывают конвертор этого языка в язык Си. Дело в том, что Си — один из самых распространенных и хорошо стандартизованных языков. 12

Обычно ориентируются на версию ANSI Си — стандарт языка, принятый Американским Национальным Институтом Стандартов (American National Standards Institute, ANSI). Компиляторы ANSI Си есть практически в любой системе. Кросскомпиляторы (cross-compilers) генерируют код для машины, отличной от той, на которой они работают. Пошаговые компиляторы (incremental compilers) воспринимают исходный текст программы в виде последовательности задаваемых пользователем шагов (шагом может быть описание, группа описаний, оператор, группа операторов, заголовок процедуры и др.); допускается ввод, модификация и компиляция программы по шагам, а также отладка программ в терминах шагов. Динамические компиляторы (Just-in-Time — JIT compilers), получившие в последнее время широкое распространение, транслируют промежуточное представление программы в объектный код во время исполнения программы. Двоичные компиляторы (binary compilers) переводят объектный код одной машины (платформы) в объектный код другой. Такая разновидность компиляторов используется при разработке новых аппаратных архитектур, для переноса больших системных и прикладных программ на новые платформы, в том числе — операционных систем, графических библиотек и др. Транслятор — это большая и сложная программа. Размер программы-транслятора составляет от нескольких тысяч до сотен тысяч строк исходного кода. Вместе с тем разработка транслятора для не слишком сложного языка — задача вполне посильная для одного человека или небольшого коллектива. Методы разработки трансляторов и будут рассмотрены в этой книге.

Рис. 1.2. Компилятор языка Оберон, написанный Никлаусом Виртом, с его «автографом» (NW). Фрагмент исходного текста основного модуля показан в левом окне Оберон-системы, частью которой является компилятор. Компилятор написан на языке Оберон и может компилировать сам себя

Транслятор связан в общем случае с тремя языками. Во-первых, это входной язык, с которого выполняется перевод. Во-вторых, целевой (объектный) язык, на который выполняется перевод. И, наконец, третий язык — это язык, на котором написан сам транслятор, — инструментальный язык. Трансляторы удобно изображать в виде Т-диаграмм 2 (рис. 1.3), которые предложил Х. Брэтман (H. Bratman) в 1961 году. Слева на такой диаграмме записывается исходный язык, справа — объектный, снизу — инструментальный.

Кроме того, что диаграмма имеет форму буквы «Т», примечательно, что с этой буквы начинается и само слово «транслятор», как русское, так и английское. 2

Рис. 1.3. Диаграммы трансляторов

Первые трансляторы, появившиеся в 1950-е годы, программировались на машинном языке или на языке низкого уровня — языке ассемблера (автокоде, как принято было говорить в то время). Сейчас для разработки трансляторов используются языки высокого уровня. Изображая Т-диаграммы, мы можем не знать, на каком языке написан транслятор. В этом случае, а также когда недоступен исходный текст транслятора (т.е. мы располагаем только его исполняемой откомпилированной версией), на Т-диаграмме в качестве инструментального записывают машинный язык или обозначение того компьютера, на котором этот транслятор работает. Можно считать, что на рис. 1.3а изображен компилятор Turbo Pascal, Delphi или Free Pascal, транслирующий с языка Паскаль в машинный код IBM PC-совместимого компьютера и существующий в виде программы в машинном коде IBM PC. На рис. 1.3б показана Т-диаграмма компилятора c языка Оберон (см. рис. 1.2), транслирующего в машинный код компьютера Ceres и написанного на языке Оберон. Рисунок 1.3в соответствует конвертору. Си# — язык программирования, созданный в корпорации Microsoft. Первая реализация Си# вполне могла 15

быть выполнена по такой схеме. В дальнейшем мы еще обратимся к Т-диаграммам и узнаем, как они могут сочетаться подобно костям домино, иллюстрируя процесс получения одних трансляторов с помощью других. Интерпретатор, кстати, можно изобразить в виде I-диаграммы (Interpreter — интерпретатор). Сверху записываем название входного, а внизу — инструментального языка. Пример диаграммы для интерпретатора Бейсика, работающего на IBM PC, можно видеть на рис. 1.3г. Метаязыки Говоря о Т-диаграммах, мы забыли еще об одном, четвертом языке, который неизбежно присутствует в разговоре о трансляторах и языках программирования. Это язык, например, русский, на котором мы ведем сам разговор. Язык, используемый для описания других языков, и называется метаязыком. В дальнейшем мы рассмотрим формализованные метаязыки, а пока в этой роли будем применять родной, естественный язык. Понятно, что бессмысленно обсуждать сколько-нибудь содержательно сразу многие языки программирования, если не знаешь и одного, не имеешь хотя бы небольшого опыта программирования. Я рассчитываю, что у вас такой опыт есть. Я даже предполагаю, что вы, скорее всего, знакомы с языком Паскаль или, может быть, Си. Эти языки в нашем обзоре тоже будут в известном смысле играть роль метаязыков. Рассматривая другие языки, мы будем сравнивать имеющиеся в них средства с теми, что есть в Паскале или Си.

ГЛАВА 2. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ТРАНСЛЯЦИИ Языки программирования — искусственно созданные формальные системы, которые могут изучаться математическими методами. Теория формальных языков и грамматик — это обширная область математики, примыкающая к алгебре, математической логике и теории автоматов. Цель этой главы — познакомиться с понятиями и результатами теории формальных языков и грамматик в той мере, как это требуется для понимания принципов конструирования трансляторов.

Формальные языки и грамматики Основные термины и определения Введем в обиход основные понятия, которые будут использованы в определении формального языка. Алфавит — конечное непустое множество символов. Термин символ следует понимать здесь в самом широком смысле. Это может быть буква, цифра или знак препинания. Но символом можно считать и любой другой знак, рассматриваемый как нечто неделимое — служебное слово языка программирования, иероглиф и т. д. Будем обозначать алфавиты буквой Σ (сигма). Примеры алфавитов: Σ1 = Σ2 = Σ3 =

Алфавит — это множество, поэтому при перечислении его элементов использованы фигурные скобки, как это принято в мате17

матике. Алфавит Σ1 содержит два символа, алфавит Σ2 — три. Под Σ3 подразумевается алфавит языка Паскаль. Цепочка над алфавитом Σ — произвольная конечная последовательность символов из Σ. Примеры цепочек над алфавитом Σ2:

α = abbca β = ab γ = ba δ =c Цепочки будем обозначать греческими буквами. Пустая цепочка — цепочка, не содержащая символов (содержащая ноль символов). Обозначается буквой ε. Если α и β — цепочки, то запись αβ означает их конкатенацию (склеивание), то есть αβ — это цепочка, образованная приписыванием к цепочке α цепочки β справа. Если α — цепочка, то αn означает цепочку, образованную nкратным повторением цепочки α: α n = αα αα

В частном случае, если a — символ, то a n = aa  aa .    n раз

Будем обозначать Σ* — (бесконечное) множество всех цепочек над алфавитом Σ, включая пустую цепочку; Σ+ — множество всех цепочек над алфавитом Σ, не включая пустой цепочки. Например, если Σ1 = , то Σ1* представляет собой множество всех цепочек, которые могут быть составлены из символов 0 и 1. В это множество входят пустая цепочка, все цепочки, состоящие 18

из одного символа, все цепочки, состоящие из двух символов и т. д.: Σ1* = . Σ * = Σ + ∪ , где ∪ — знак операции объединения множеств.

Теперь можно дать и определение формального языка. Языком над алфавитом Σ называется произвольное множество цепочек, составленных из символов Σ. Будем обозначать язык над алфавитом (с алфавитом) Σ — L(Σ) или просто L, если алфавит ясен из контекста. Таким образом, речь идет о том, что язык — это некоторое, тем или иным образом определенное, подмножество множества всех цепочек, которые могут быть построены из символов данного алфавита. L(Σ) ⊆ Σ * . На рисунке 2.1 наглядно показано соотношение множеств Σ* и L(Σ).

Рис. 2.1 Язык — подмножество множества всех цепочек над алфавитом Σ

Принадлежащие языку цепочки называют также предложениями языка. Еще раз отметим, что множество цепочек Σ* всегда бесконечно, в то время как множество цепочек, образующих язык, может быть и конечным. Практический интерес представляют, конечно, языки, содержащие бесконечное множество цепочек; к числу таких языков относятся и языки программирования. 19

Примеры языков Пример 1. Определим язык L1 = , используя принятую в теории множеств нотацию, как множество всех цепочек, содержащих вначале некоторое количество символов a, а затем такое же количество символов b. Заметим, что L1 включает и пустую цепочку, поскольку n может равняться нулю. Записанное выше правило, определяющее язык L1, разделяет все цепочки над алфавитом , то есть состоящие из символов a и b, на принадлежащие L1 и не принадлежащие ему. Примеры цепочек, принадлежащих языку:

ε ∈ L1 — пустая цепочка принадлежит L1; ab ∈ L1 — цепочка из одной буквы a, за которой следует b; aaabbb ∈ L1. Цепочки, не принадлежащие языку L1: aaab ∉ L1 — неодинаковое количество символов a и b; abba ∉ L1 — порядок следования символов не соответствует определению L1. Пример 2. Язык L2 = — множество всех цепочек, содержащих вначале некоторое (возможно нулевое) количество символов a, затем такое же количество символов b, затем — столько же букв c. Например, aaabbbccc ∈ L2, в то время как aaabbc ∉ L2. Далеко не всегда удается определить язык, особенно если речь идет о языках, представляющих практический интерес, используя нотацию, примененную при определении L1 и L2. Значительная часть последующего материала будет посвящена рассмотрению порождающих грамматик, позволяющих компактно и однозначно определить обширный класс формальных языков. Пока 20

же, в следующих примерах, дадим словесное описание некоторых представляющих интерес языков. Пример 3. Рассмотрим язык правильных скобочных выражений, составленных только из круглых скобок, известный также как язык Дика. Обозначим его L3. Алфавит языка Дика — это множество из двух символов — открывающей «(» и закрывающей «)» скобок: Σ3 = < (, ) >. Цепочки, содержащие правильно расставленные скобки принадлежат языку Дика, все остальные последовательности открывающих и закрывающих круглых скобок — нет. Например: (())()() ∈ L3; ()(()))( ∉ L3. Пример 4. Язык L4 — множество всех цепочек, содержащих одинаковое количество символов a и b. Несмотря на простое «устройство», задать язык L4 формулой, подобной формулам для L1 или L2, оказывается затруднительно. Можно заметить, что рассмотренный ранее язык L1 является подмножеством языка L4: L1 ⊆ L4, поскольку любая цепочка, принадлежащая L1, принадлежит и языку L4. Но не наоборот. Так, aabb ∈ L1, aabb ∈ L4, abba ∈ L4, но abba ∉ L1. Пример 5. В качестве языка L5 рассмотрим множество всех правильных арифметических выражений языка Паскаль, составленных из символов алфавита Σ5 = . Например, a*(b+c) ∈ L5, но c++ ∉ L5.

Порождающие грамматики (грамматики Н. Хомского 3) Порождающие грамматики — это простой и мощный механизм, позволяющий задавать обширный класс языков, содержащих бесконечное множество цепочек. С помощью порождающих грамматик мы сможем, в частности, определить языки L3, L4 и L5, для задания которых раньше ограничивались словесными формулировками. Порождающие грамматики используются и при описании синтаксиса языков программирования. Порождающей грамматикой называется четверка: G = (T, N, P, S), где T — конечное множество терминальных (основных) символов — основной алфавит. Элементами множества T являются символы, из которых в конечном итоге и состоят цепочки языка, порождаемого данной грамматикой. Терминальный (от лат. terminus — предел, конец) и означает «конечный, концевой». T — это не что иное, как алфавит языка, порождаемого грамматикой. В дальнейшем, если не оговорено особо, терминальные символы или просто терминалы будут обозначаться малыми буквами латинского алфавита: a, b, c и т. д. N — конечное множество нетерминальных (вспомогательных) символов — вспомогательный алфавит. Нетерминальные символы, по-другому нетерминалы, — это понятия грамматики (языка), которые используются при его описании. Нетерминалы бу-

Ноам Хомский (Noam Chomsky, р. 1928) — американский лингвист и политический активист. Начиная с 1957 года, опубликовал ряд работ, заложивших основы математической лингвистики. Выступал против войны США во Вьетнаме, автор нескольких десятков книг на политические темы. Участник движения антиглобалистов. В отечественной прессе его фамилия иногда звучит как Чомски, однако в научных публикациях на русском языке, начиная с 1962 года, принято написание Хомский. 3

дем обозначать заглавными латинскими буквами: A, B, C, D, E и т. д. P — конечное множество правил вывода, называемых также продукциями. Каждое правило множества P имеет вид:

α → β, где α и β — цепочки терминальных и нетерминальных символов. Цепочка α не должна быть пустой, цепочка β может быть пуста: α ∈ (T ∪ N ) + ; β ∈ (T ∪ N )* . Правило α → β определяет возможность подстановки β вместо α в процессе вывода (порождения) цепочек языка. S (S∈N) — начальный символ грамматики — один из множества нетерминальных символов, начальный (стартовый) нетерминал. Начальный нетерминал — это понятие, соответствующее правильному предложению языка. Например, начальный нетерминал грамматики выражений обозначает «выражение», а начальный нетерминал грамматики языка Паскаль — «Программа». Примеры грамматик. Порождение предложений языка

Пример 1. Рассмотрим грамматику G1 = ( , , , S ). Здесь все элементы четверки записаны явно. Множество терминальных символов T = ; множество нетерминалов содержит один элемент: N = , а множество правил — два: P = ; роль начального нетерминала исполняет S. Грамматика может использоваться для порождения (вывода) цепочек — предложений языка. Процесс порождения начинается с начального нетерминала, в нашем примере это S. Если среди правил есть такое, в левой части которого записана цепочка S, то начальный нетерминал может быть заменен правой частью лю23

бого из таких правил. Оба правила грамматики G1 содержат в левой части S. Применим подстановку, заданную первым правилом, заменив S на aSb: S ⇒ aSb (1)

К получившейся цепочке aSb снова, если удастся, можно применить одно из правил грамматики. Если в цепочке есть подцепочка, совпадающая с левой частью хотя бы одного из правил, то эту подцепочку можно заменить правой частью любого из таких правил. В цепочке aSb есть подцепочка S, совпадающая с левой частью обоих правил грамматики G1. Мы вправе применить любое из этих правил. Используем снова правило (1) для продолжения вывода: S ⇒ aSb ⇒ aaSbb (1)

Теперь к получившейся цепочке применим правило (2) (S → ε), заменив S пустой цепочкой. Получим такую последовательность подстановок (саму букву ε в последней цепочке записывать, конечно, не нужно): S ⇒ aSb ⇒ aaSbb ⇒ aabb (1)

Очевидно, что к получившейся цепочке ни одно из правил грамматики G1 больше не применимо. Процесс порождения завершен. Нетрудно заметить, что с помощью грамматики G1 можно породить любую цепочку языка L1 = , применив к начальному нетерминалу правило (1) (S → aSb) n раз, а затем один раз правило (2). В то же время, грамматика G1 не порождает ни одной цепочки терминальных символов, не принадлежащей языку L1. То есть множество терминальных цепочек, порождаемых грамматикой G1, совпадает с языком L1. Другими словами, грамматика G1 порождает язык L1: L(G1) = L1 . 24

Обычно при записи грамматики не выписывают четверку ее элементов явно. При соблюдении соглашений об обозначениях терминалов и нетерминалов достаточно записать только правила. Правила с одинаковой левой частью можно объединять в одно, отделяя альтернативные правые части вертикальной чертой. Первым записывается правило, содержащее в левой части начальный нетерминал. С учетом этого грамматика G1 может быть записана так: G1:

Пример 2. Рассмотрим грамматику G2 (цифры справа — номера правил) G2:

Проведем вывод цепочек из начального нетерминала грамматики G2. Под стрелкой, обозначающей подстановку, будем указывать, как и раньше, номер примененного правила. Итак: S ⇒ aSBc ⇒ aabcBc ⇒ aabBcc ⇒ aabbcc (1)

Еще одна серия подстановок: S ⇒ aSBc ⇒ aaSBcBc ⇒ aaabcBcBc ⇒ aaabBccBc ⇒ aaabBcBcc ⇒ (1)

aaabBBccc ⇒ aaabbBccc ⇒ aaabbbccc ( 4)

Можно убедиться, что грамматика G2 порождает цепочки терминалов вида anbncn и никакие другие. Количество повторений символов в результирующей цепочке определяется тем, на каком шаге применяется правило (2). Наличие правила (5) позво25

ляет получить пустую цепочку, если применить это правило первым, в то время как попытка использования этого правила на последующих шагах не позволит вывести цепочку терминалов. Грамматика G2 порождает множество терминальных цепочек, совпадающее с языком L2 = : L(G2) = L2 . Пример 3. Грамматика, порождающая язык правильных скобочных выражений (язык Дика). G3:

Нетрудно понять логику построения правил этой грамматики. Смысл первого правила таков: заключив в скобки правильное скобочное выражение S, мы снова получим правильное скобочное выражение. Второе правило означает, что два правильных скобочных выражения, записанные одно за другим, дают новое правильное выражение. Наконец, по правилу (3) пустая цепочка считается правильным выражением. Если бы мы решили, что не следует разрешать пустые выражения, правило (3) можно было бы заменить на S → () . Пример 4. Грамматика простых арифметических выражений. Единственным нетерминалом этой грамматики (он же начальный) будет Выражение: G4:

Выражение → Выражение + Выражение | Выражение – Выражение | Выражение * Выражение | Выражение / Выражение | a | b | c | ( Выражение ) .

Такая грамматика порождает цепочки терминалов, являющиеся правильными арифметическими выражениями. Символы a, b и c в таких выражениях обозначают операнды, а «+», «–», «*», и 26

«/» — знаки операций. Разрешаются круглые скобки (в том числе вложенные). Примеры правильных выражений: (a+b)/(b*c), (a). Все операции двуместные, унарные плюс и минус не предусмотрены, поэтому, например, цепочка –a не принадлежит языку, порождаемому этой грамматикой. Выражение — одно из основных понятий языков программирования. В дальнейшем грамматикам выражений будет уделено немалое внимание. Чтобы запись этих грамматик была короче, заменим нетерминал Выражение на E (от expression — выражение), вернувшись тем самым к принятым раньше соглашениям об именовании нетерминалов. Тогда грамматика, которую обозначим G5, запишется следующим образом: G5:

Очевидно, что она порождает тот же язык, что и грамматика G4. А именно: L(G5) = L5 . Еще несколько определений В предыдущих примерах мы уже пользовались такими терминами как «вывод», «язык, порождаемый грамматикой». Теперь дадим формальные определения для этих и ряда других понятий. Пусть имеются грамматика G = (T, N, P, S) и цепочка α1, составленная из терминалов и нетерминалов грамматики G, причем α1 представима в виде α1 = γ1αγ2, где γ1, γ2 — цепочки терминалов и нетерминалов грамматики G, α — непустая цепочка терминалов и нетерминалов грамматики G: γ1, γ2 ∈ (T ∪ N)*; α ∈ (T ∪ N)+. Пусть также среди множества правил P грамматики G есть правило α → β. Тогда подцепочка α цепочки α1 может быть заменена цепочкой β, в результате чего будет получена цепочка α2 = γ1βγ2. В этом случае говорят, что цепочка α2 непосредст27

венно выводится (порождается) из цепочки α1 в грамматике G, что записывается следующим образом: α1 ⇒α 2 или просто α1⇒ α2, G

если используемая грамматика очевидна. Если имеется последовательность цепочек α1, α2, …, αn (n > 1), таких что α1 ⇒ α 2  ⇒ α n , G

то говорят, что цепочка αn нетривиально выводится из α1 в грамматике G (выводится за один или более шагов), что обозначается так: +

α1 ⇒α n или просто α1 ⇒α n . G

Последовательность цепочек α1, α2, …, αn в этом случае называется выводом цепочки αn из α1 в грамматике G. В дальнейшем выводом будем называть также запись, подобную (*). Используется также запись *

α1 ⇒α n или α1 ⇒α n , G

означающая, что цепочка αn выводится из α1 в грамматике G (выводится за ноль или более шагов), что следует понимать так, +

что, либо αn совпадает с α1, либо α1 ⇒α n . Сентенциальной формой грамматики G называется цепочка, выводимая из начального нетерминала грамматики G. Цепочка α — есть сентенциальная форма грамматики G, если *

Сентенцией (от sentence — предложение) грамматики G называется сентенциальная форма, состоящая только из терминальных символов. Язык, порождаемый грамматикой, есть множество всех её сентенций. Можно сказать, что сентенции грамматики — это предложения порождаемого ею языка. Дерево вывода В последующем рассмотрении предполагается, что мы имеем дело с грамматиками, все правила которых в своей левой части содержат единственный нетерминал. Именно такие грамматики, называемые контекстно-свободными, представляют для нас наибольший практический интерес. Рассмотрим грамматику G6:

Выполним вывод цепочек в этой грамматике. Вначале используем правило (1): S ⇒ AB . Будем сопровождать процесс вывода построением дерева (рисунок 2.2). Корнем дерева будет вершина, соответствующая начальному нетерминалу S. Дочерними вершинами корня будут вершины A и B, соответствующие правой части первого примененного правила (рис. 2.2а). Вершины A и B следуют в дереве слева направо в том же порядке, что и в правиле (1): слева — А, справа — B.

Рис. 2.2. Построение дерева вывода

Продолжая вывод, мы можем выбрать, как правило для нетерминала A — правило (2), так и правило для B — правило (3). Используем вначале первую часть правила (2) (A → aA): S ⇒ AB ⇒ aAB и продолжим построение дерева (рис. 2.2б). Теперь выполним подстановку вместо нетерминала B цепочки bB по правилу (3): S ⇒ AB ⇒ aAB ⇒ aAbB , добавив к имеющейся вершине B дочерние вершины b и B (рис. 2.2в). Еще раз применим правило A → aA и, чтоб получить цепочку, состоящую только из терминалов, выполним подстановки по правилам A → a и B → b. После этого вывод приобретет следующий вид: S ⇒ AB ⇒ aAB ⇒ aAbB ⇒ aaAbB ⇒ aaabB ⇒ aaabb , a получившееся дерево показано на рис. 2.2г. ВОПРОС

Какой язык порождает грамматика G6?

Получившееся дерево называется деревом вывода, деревом разбора или синтаксическим деревом 4. Его корень — начальный К сожалению, в литературе на русском языке существует путаница в терминах. Одни авторы (и их переводчики) [Грис, 1975] считают «дерево разбора» и «синтаксическое дерево» синонимами, другие [Ахо, 2001] придают понятию «синтак-

символ грамматики, внутренние вершины — нетерминалы, листья дерева (концевые вершины) — терминалы. Обход листьев дерева слева направо дает цепочку терминалов, выведенную из начального символа грамматики (сентенцию) 5. Нетрудно заметить, что построенное нами дерево будет соответствовать и другим выводам цепочки aaabb в грамматике G6. Вот один из них: S ⇒ AB ⇒ AbB ⇒ aAbB ⇒ aAbb ⇒ aaAbb ⇒ aaabb . Рассмотрение дерева вместо вывода позволяет игнорировать порядок применения правил, если он не важен. Задача разбора Задача разбора состоит в восстановлении дерева вывода для заданной сентенции. Разбор — это построение вывода для заранее заданной цепочки. Другими словами, разбор — это тот же вывод, прослеженный в обратном порядке. Последовательность сентенциальных форм, приводящая к цепочке терминалов (сентенции, предложению языка, порождаемого грамматикой), определяет структуру этой цепочки. Дерево вывода представляет структуру цепочки нагляднее и независимо от последовательности применения правил. Результатом решения задачи разбора в случае, если удалось восстановить дерево для заданной терминальной цепочки, является выявление структуры этой цепочки. Построенное дерево назысическое дерево» иной смысл. Я буду придерживаться первого варианта, поскольку термины «разбор» и «синтаксический анализ» означают одно и то же, и было бы странно их различать, говоря о деревьях. Могут рассматриваться и деревья вывода, листьями которых являются как терминалы, так и нетерминалы. В этом случае обход листьев дает сентенциальную форму грамматики. Однако такие деревья нам не потребуются.

вается деревом разбора. Успешное восстановление дерева разбора для заданной цепочки означает, что эта цепочка есть правильное предложение языка, порождаемого грамматикой. Наоборот, если для некоторой цепочки терминалов дерево разбора в данной грамматике построить невозможно, это значит, что цепочка не принадлежит порождаемому грамматикой языку. Для чего надо решать задачу разбора Разбор (по-английски — parsing) называют также распознаванием или синтаксическим анализом. Синтаксический анализ имеет две цели — выяснение принадлежности цепочки языку и выявление ее структуры. Работа любого транслятора основана на распознавании структуры предложений транслируемого языка. Синтаксический анализ — обязательная фаза в работе компиляторов и интерпретаторов языков программирования. Синтаксический анализатор — это часть транслятора, составляющая его основу. Только распознавая структуру входной программы, определяя наличие или отсутствие отдельных ее частей — описаний, операторов, выражений и подвыражений — транслятор может выполнить работу по переводу программы на другой язык. Часто трансляторы в явном виде строят дерево программы, которое представляется внутренними динамическими структурами данных транслятора, а затем используется при формировании эквивалентной выходной программы. Если в ходе распознавания дерево вывода не строится, оно присутствует неявно, отражаясь в последовательности выполняемых синтаксическим анализатором действий. Рассмотрению способов решения задачи разбора — синтаксического анализа будет посвящена большая часть этой главы.

Домино Де Ремера Де Ремер (De Remer F. L.) предложил наглядную интерпретацию задачи разбора, представив ее как игру в своеобразное домино. Играющий располагает «костями» домино нескольких типов. Типов столько, сколько правил в грамматике. Каждое правило дает один тип пластинки. Типы домино для грамматики G6 показаны на рис. 2.3. Считается, что «костяшек» каждого типа имеется сколько необходимо.

Рис. 2.3. Домино Де Ремера для грамматики G6

Верхняя часть каждого домино соответствует левой части правила грамматики, нижняя — правой. Верхняя и нижние пластинки соединены «резиновыми» нитями. Пластинки можно приставлять друг к другу плоскими сторонами полукруга, если на них записаны одинаковые символы. Фигуры домино нельзя переворачивать, и нельзя менять порядок следования символов (перекрещивать нити). В начале игры в верхней части поля помещается полукруг, обращенный выпуклостью вверх, в котором записан начальный нетерминал грамматики. В нижней части игрового поля в полукругах, обращенных плоской частью вверх, размещаются терминальные символы распознаваемой цепочки. На рис. 2.4 показана начальная конфигурация игры для цепочки aaabb.

Рис. 2.4. Начало игры в домино Де Ремера

Цель состоит в том, чтобы соединить с помощью имеющихся фигур символы терминальной цепочки и начальный нетерминал. Полученная конфигурация домино для цепочки aaabb и грамматики G6 (набор домино на рис. 2.3) показана на рис. 2.5.

Рис. 2.5. Дерево разбора, построенное из домино Де Ремера

Разновидности алгоритмов разбора Имея в виду интерпретацию Де Ремера, можно представить себе и различные подходы к решению задачи разбора. Если подбор костей удается осуществлять так, что однажды поставленную кость никогда не придется убирать, мы имеем дело с детерминированным алгоритмом разбора — выбор применяемого правила грамматики всегда однозначен. Если принятые решения о выборе типа домино приходится отменять — алгоритм работает с возвратами, он недетерминирован. Детерминированные алгоритмы эффективней и, конечно, всегда существует стремление 34

найти и использовать такой алгоритм для синтаксического анализа. Если дерево строится сверху вниз от начального нетерминала в сторону терминальной цепочки, алгоритм относится к классу нисходящих; от цепочки в сторону корня дерева — восходящий (рис. 2.6). Можно вначале подбирать домино для левых символов терминальной цепочки, а можно вначале для правых — соответственно говорят о левосторонних или правосторонних алгоритмах разбора.

Рис. 2.6. Начало нисходящего и восходящего разбора в грамматике G6

Эквивалентность и однозначность грамматик Возьмем для примера грамматику арифметических выражений G5:

Рассмотрим деревья вывода терминальных цепочек в этой грамматике. На рис. 2.7 показаны два различных дерева разбора выражения a+b*c. Возможность построить эти деревья убеждает в том, что цепочка a+b*c действительно принадлежит языку арифметических выражений.

Рис. 2.7. Деревья разбора цепочки a+b*c в грамматике G5

Но два разных дерева дают две разные трактовки структуры этой цепочки. Дерево слева объединяет a+b в одно подвыражение, которое затем участвует в роли операнда в операции умножения. Такая трактовка не соответствует общепринятому приоритету арифметических операций — умножение должно выполняться раньше сложения. Дерево справа представляет структуру, соответствующую правильному порядку выполнения операций. Грамматика G называется однозначной, если любой сентенции x ∈ L(G) соответствует единственное дерево вывода. Грамматика G5 неоднозначна, и это, безусловно, ее серьезный недостаток, который не позволяет применить ее на практике для определения языка выражений, поскольку эта грамматика не позволяет однозначным образом выявить структуру выражения. Попробуем построить однозначную грамматику выражений. Для этого используем еще один нетерминал, обозначив его X: G7:

Содержательно X можно понимать как операнд выражения. Теперь для цепочки a+b*c можно построить единственное дерево разбора. Оно показано на рис. 2.8 слева. Можно убедиться, что в грамматике G7 единственное дерево вывода соответствует любому правильному выражению. Грамматика G7 однозначна.

Рис. 2.8. Дерево разбора выражения a+b*c в грамматике G7

Справа на рисунке показано редуцированное (упрощенное) дерево того же выражения в грамматике G7. Такие деревья могут служить для представления структуры выражений в трансляторе. Будем называть их семантическими деревьями 6. Семантическое дерево может быть получено из дерева разбора устранением нетерминальных вершин и помещением знаков операций во внутренние вершины, в то время как операнды остаются листьями дерева. Несмотря на однозначность, G7 непригодна для использования в трансляторе, поскольку приписывает выражениям неподходящую структуру. Уже на примере цепочки a+b*c (см. рис. 2.8) видно, что операции и операнды связываются неправильно. Нетрудно заметить, что G7 предполагает выполнение операций без учета их приоритета в порядке слева направо. Исправить положение можно, определив нетерминалы для двух категорий подвыражений — слагаемых и множителей. После этого выражение представляется как последовательность сла-

Как уже говорилось, существует несогласованность в использовании терминов, относящихся к синтаксическим и семантическим деревьям. В этой книге мы будем, следуя [Рейуорд-Смит, 1988], придерживаться названия «семантическое дерево». В то же время в издании [Ахо, 2001] в этом случае говорится о синтаксическом дереве, что противоречит терминологии классической монографии [Грис, 1975] и, по моему мнению, создает путаницу, поскольку трудно видеть разницу между синтаксическим деревом и деревом разбора. 6

гаемых, разделенных знаками плюс и минус. В свою очередь слагаемые образуются из элементарных операндов — множителей, соединенных знаками умножения и деления. Слагаемые обозначим T (от term — элемент), множители — M (от multiplier). G8:

Дерево вывода цепочки a+b*c в грамматике G8 показано на рис. 2.9. Эта грамматика однозначна и приписывает арифметическим выражениям структуру, соответствующую правильному порядку выполнения операций.

Рис. 2.9. Дерево выражения a+b*c в грамматике G8

Все три рассмотренные выше грамматики выражений (G5, G7, G8), хотя и различаются и обладают разными свойствами, задают один и тот же язык. Грамматики называются эквивалентными, если порождают один и тот же язык. Грамматики G5, G7, G8 эквивалентны, поскольку L(G5) = L(G7) = L(G8). Иерархия грамматик Н. Хомского Н. Хомский предложил разделение порождающих грамматик на 4 типа в зависимости от вида их правил. 38

Тип 0. Произвольные грамматики. На вид их правил не накладывается каких-либо ограничений. Правила имеют вид:

α→β, где α и β — цепочки терминалов и нетерминалов. Цепочка α не должна быть пустой. Тип 1. Контекстно-зависимые грамматики. Правила таких грамматик имеют вид:

αΑβ → αγβ, где α, β, γ — цепочки терминалов и нетерминалов; A — нетерминальный символ. Такой вид правил означает, что нетерминал A может быть заменен цепочкой γ только в контексте, образуемом цепочками α и β. Тип 2. Контекстно-свободные грамматики. Их правила имеют вид:

Α → γ, где, A — нетерминал; γ — цепочка терминалов и нетерминалов. Характерная особенность — в левой части правил всегда один нетерминальный символ. Тип 3. Автоматные грамматики. Все правила автоматных грамматик имеют одну из трех форм:

Α → aB Α→a Α → ε, где A, B — нетерминалы; a — терминал; ε — пустая цепочка. Автоматные грамматики называют также регулярными. Как можно видеть, грамматики типа 1 являются частным случаем грамматик типа 0, грамматики типа 2 — частный случай кон39

текстно-зависимых грамматик, автоматные — частный случай контекстно-свободных. То есть, грамматика типа 3 является и грамматикой типа 2, и типа 1, и типа 0. Однако в дальнейшем, если не оговорено особо, будет иметься в виду что, например, контекстно-свободной называется грамматика, не являющаяся автоматной. Языки, порождаемые грамматиками типа 0–3, называются соответственно языками без ограничений, контекстно-зависимыми, контекстно-свободными и автоматными (регулярными) языками. Но контекстно-свободным языком называют язык, для которого существует порождающая его контекстно-свободная, но не автоматная грамматика. Такой же подход применяется к контекстно-зависимым языкам и языкам без ограничений. Примеры грамматик различных типов

Рассмотрим грамматику G2, порождающую язык L2 = . G2:

Справа около каждого правила помечен тип грамматики, к которой оно может быть отнесено. Типом грамматики естественно считать минимальный из типов ее правил. Следовательно, грамматика G2 — это грамматика типа 0 — произвольная. Утверждается, однако, что может быть построена контекстно-зависимая грамматика (типа 1), порождающая тот же язык, что и G2. Проверку этого утверждения предоставлю читателям.

Примером контекстно-свободной грамматики может служить грамматика арифметических выражений. С помощью контекстно-свободных грамматик задается и синтаксис языков программирования. Грамматики этого класса будут подробно обсуждаться и в дальнейшем, сейчас же возьмем конкретный пример. G9:

Это грамматика типа 2, поскольку правила (2) и (3) относятся именно к этому типу. Рассмотрим язык L9 = L(G9), порождаемый этой грамматикой. Цепочка a принадлежит L9 по правилу (1). Если к правильному предложению N языка приписать справа символ a, то снова получится правильное предложение (по правилу (2)). Аналогично, приписывание к N символа b снова дает предложение языка L9. Принадлежащие языку L9 цепочки начинаются символом a, за которым могут следовать a и b в произвольном порядке. Если под a понимать любую латинскую букву, а b воспринимать как цифру, то G9 можно считать грамматикой идентификаторов. Она порождает последовательности букв и цифр, начинающиеся с буквы, которые используются в языках программирования в роли имен переменных, типов и т. д. Опираясь на такую содержательную трактовку G9 и L9, попытаемся сконструировать автоматную грамматику, порождающую язык идентификаторов. Первое правило грамматики G9 может быть сохранено. Оно, вопервых, соответствует одному из допустимых видов правил автоматных грамматик, во-вторых, определяет, что идентификатор, состоящий из одного символа может быть только буквой. N→a

Нетерминал N — это начальный символ нашей грамматики. Он и обозначает само понятие «идентификатор». Как синоним термина «идентификатор» будем использовать также слово «имя». Можно считать, что название N происходит от Name — имя. Обозначим B часть идентификатора, которая может следовать за первой буквой. Тогда можно записать правило (2): N → aB

Запишем правила для B. «Хвост» может быть буквой или цифрой: B→a

Если B — это «хвост» идентификатора, то, записав его за буквой или цифрой, снова получим правильный «хвост»: B → aB

Обозначим сконструированную грамматику G10. Она автоматная, поскольку все ее правила удовлетворяют ограничениям автоматных грамматик. G10: N → a

Грамматика G10 эквивалентна G9, поскольку порождает тот же язык: L(G10) = L(G9). Этот язык — язык идентификаторов — следует считать автоматным. Нетрудно увидеть возможности упро42

щения грамматики G10. Отложим, однако, на некоторое время такое упрощение.

Автоматные грамматики и языки Рассмотрим автоматные грамматики и языки подробнее, имея целью построение алгоритмов распознавания этого класса языков. Граф автоматной грамматики Для каждой автоматной грамматики можно построить направленный граф по следующим правилам: 1. Каждому нетерминальному символу грамматики ставится в соответствие вершина графа, которая помечается этим символом. 2. При наличии правил вида A→a добавляется дополнительная вершина, которая помечается символом K. 3. Каждое правило вида A → aB порождает дугу графа, ведущую из вершины A в вершину B.

Дуга помечается символом a. 4. Каждое правило вида A→a порождает дугу графа, ведущую из вершины A в вершину K.

Дуга помечается символом a. 5. Вершина, соответствующая начальному нетерминалу, помечается стрелкой.

6. Вершина K и вершины, соответствующие нетерминалам, для которых есть правило A → ε, помечаются как конечные. Мы будем изображать их двойным кружком.

Построим граф автоматной грамматики G10 (рис. 2.10). Двум нетерминалам этой грамматики будут соответствовать вершины N и B (п. 1). Поскольку в грамматике есть несколько правил, в правой части которых записан единственный терминал, добавим вершину K (п. 2).

Рис. 2.10. Граф автоматной грамматики G10

Соединим вершины дугами, как это предписывается п. 3 и п. 4. Вершину N пометим стрелкой как начальную (п. 5). Граф автоматной грамматики может использоваться для порождения цепочек языка. Любой путь из начальной вершины графа в одну из конечных вершин порождает цепочку терминалов, соответствующую проходимым дугам. Эта цепочка принадлежит 44

языку, порождаемому грамматикой. И, наоборот, для любой сентенции грамматики можно найти путь, ведущий из начальной вершины в одну из конечных и проходящий по дугам, помеченным символами этой сентенции. Грамматика G10 порождает язык идентификаторов. Нетрудно убедиться, что для любого идентификатора найдется путь из вершины N в вершину K, а любой путь из N в K соответствует правильному идентификатору. Граф автоматной грамматики идентичен диаграмме переходов конечного автомата — абстрактного устройства, являющегося моделью определенного класса реальных автоматических устройств и объектом изучения теории автоматов. Конечные автоматы Конечным автоматом (КА) называется пятерка: A = (N, T, P, S, F), где N — конечное множество состояний автомата. T — входной алфавит — конечное множество символов. P — функция переходов автомата (в общем случае неоднозначная), отображающая множество пар состояние–входной символ в множество состояний 7. S — начальное состояние. S ∈ N. F — множество конечных (финитных) состояний. F ⊆ N. Конечный автомат действует следующим образом. Вначале он находится в состоянии S. На вход КА поступают символы, принадлежащие входному алфавиту. Последовательность входных Вместо того чтоб считать функцию переходов неоднозначной, можно было бы говорить, что ее значениями для данной пары символ–состояние являются не отдельные состояния, а множества состояний.

символов образует входную цепочку. Находясь в некотором состоянии и получив на вход очередной символ, автомат переходит в следующее состояние, определяемое значением функции переходов для данной пары символ–состояние, и считывает очередной символ. В общем случае функция переходов может определять переход в несколько состояний для данной пары символ–состояние. В этом случае говорят о недетерминированным конечном автомате (НКА). Автомат останавливается, когда заканчиваются символы на его входе. Если, прочитав входную цепочку α, автомат остановился в некотором состоянии B, говорят, что цепочка α перевела автомат из начального состояния в состояние B. Если B — одно из конечных состояний (B ∈ F), то говорят, что автомат принимает (допускает) цепочку α. Множество всех цепочек, переводящих конечный автомат А из начального в одно из конечных состояний (множество цепочек, принимаемых КА), образует язык L(A), принимаемый (допускаемый) КА. Язык, порождаемый автоматной грамматикой G, совпадает с языком, принимаемым соответствующим конечным автоматом A. L(G) = L(A) Как мы уже видели, КА может задаваться с помощью диаграммы переходов. Например, граф автоматной грамматики G10, показанный на рис. 2.10, может считаться диаграммой переходов автомата A10. При этом L(G10) = L(A10).

Преобразование недетерминированного конечного автомата (НКА) в детерминированный конечный автомат (ДКА) То обстоятельство, что при переходе от автоматной грамматики к КА мы получаем в общем случае НКА, затрудняет его использование в роли распознавателя автоматного языка. Недетерминированность автомата выражается в том, что для некоторых вершин его диаграммы переходов имеется несколько дуг, выходящих из этих вершин и помеченных одним и тем же символом. Так, автомат, изображенный на рис. 2.10, является недетерминированным. Из вершины N исходят две дуги, помеченные символом a, из вершины B — по две дуги, помеченных символами a и b. Было бы крайне желательно иметь возможность строить для автоматной грамматики детерминированный конечный автомат. Теорема Клини. Для каждого НКА можно построить ДКА, допускающий тот же язык. Рассмотрим алгоритм построения ДКА, эквивалентного данному НКА. Для иллюстрации алгоритма будем применять его к НКА A10 (см. рис. 2.10), принимающему язык идентификаторов. 1. Пусть исходный НКА имеет k состояний. Для построения ДКА возьмем 2k – 1 состояний, каждое из которых соответствует одному элементу множества всех подмножеств состояний исходного автомата, кроме пустого множества. Автомат A10 имеет три (k=3) состояния: N, B и K. У нового автомата будет 23 – 1 = 7 состояний. Они соответствуют таким множествам состояний исходного НКА: , , , , , , . Будем обозначать состояния нового автомата просто последовательностями букв: N, B, K, NB, BK, NK, NBK. 47

2. Из каждого состояния S нового автомата направим не более чем один переход, помеченный данным символом, в такое состояние, которое соответствует множеству состояний НКА, в которые есть переходы по этому символу хотя бы из одного состояния НКА, образующего S. У НКА A10 из состояния N есть переход по символу a в состояния B и K (см. рис. 2.10). Следовательно, из состояния N нового автомата дугу, помеченную символом a, направляем в состояние BK. Рассматривая состояние NB нового автомата, выясняем, что переходы из состояния N по символу a в исходном автомате есть в состояния B и K, из состояния B исходного автомата — также в состояния B и K. Направляем дугу, помеченную a, из состояния NB в состояние BK (рис. 2.11). Перехода по символу b из состояния N в исходном автомате нет. Из состояния B исходного автомата есть переходы, помеченные b, в состояния B и K. Направляем дугу b из состояния NB в состояние BK.

Рис. 2.11. Детерминированный конечный автомат A11, эквивалентный недетерминированному автомату A10

Аналогично формируем переходы из других состояний нового автомата A11, который будет эквивалентен A10. В нашем примере 48

оказывается, что все дуги, помеченные как символом a, так и символом b ведут в состояние BK. 3. В качестве начального состояния ДКА отметим состояние, имеющее то же обозначение, что и начальное состояние исходного НКА. Как конечные отметим все состояния ДКА, в которые входит хотя бы одно из конечных состояний исходного НКА. В нашем примере начальным будет состояние N. Конечными состояниями ДКА будут все состояния, включающие состояние K исходного автомата, то есть K, BK, NK, NBK (см. рис. 2.11). Получившийся автомат является детерминированным (из любого состояния исходит не более одной дуги, помеченной данным символом) и принимает тот же язык, что и исходный недетерминированный автомат. Детерминированный автомат A11 имеет больше состояний, чем исходный НКА A10. Нетрудно, однако, увидеть возможности упрощения получившегося ДКА. Большинство его состояний (B, K, NB, NK, NBK) недостижимы из начального состояния, поэтому могут быть отброшены. Получающийся после этого ДКА A12 показан на рис. 2.12. Обозначение состояния BK упрощено, оно снова названо просто B. Этот автомат не только детерминирован, но и проще исходного НКА A10.

Рис. 2.12. Минимальный ДКА A12, распознающий идентификаторы

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

фикаторов, эквивалентную грамматике G10, но содержащую меньше правил: G12: N → aB B → aB | bB | ε Кстати, смысл нетерминала B в новой грамматике сохранился — это «хвост», завершающий идентификатор. Детерминированный конечный автомат можно рассматривать как распознаватель автоматного языка — устройство, с помощью которого просто и эффективно решается задача разбора для автоматной грамматики. В связи с этим, наряду с автоматами принимающими (допускающими) некоторый язык, будем говорить об автоматах, распознающих язык. Для любого автоматного языка можно построить детерминированный конечный автомат, распознающий этот язык. Задача получения возможно более простого ДКА также имеет общее решение. Для любого автоматного языка можно построить единственный ДКА, распознающий этот язык и имеющий минимально возможное число состояний. С алгоритмом построения ДКА с минимальным числом состояний можно познакомиться в книгах [Ахо, 2001], [Карпов, 2002], [Хопкрофт, 2002]. Таблица переходов детерминированного конечного автомата Наряду с представлением графом, функция переходов ДКА может быть задана таблицей, что, безусловно, больше подходит для программной реализации конечного автомата (табл. 2.1). Рассмотрим таблицу переходов ДКА A12, распознающего язык идентификаторов. 50

Таблица 2.1. Таблица переходов конечного автомата A12 Символ

В таблице записано состояние, в которое переходит автомат, находясь в состоянии, соответствующем данной строке таблицы и, получив входной символ, обозначенный в соответствующем столбце. Конечное состояние автомата B помечено в таблице жирным шрифтом. Наряду с состояниями N и B предусмотрено дополнительное состояние E — состояние ошибки. Это сделано для того, чтобы функция переходов была определена для всех возможных пар символ–состояние. Иначе переход из состояния N при поступлении на вход символа b был бы не определен. Попав в состояние E, автомат остается в нем. Состояние E не является конечным. На практике при программной реализации, кроме символов входного алфавита, потребуется, скорее всего, определить реакции автомата и на любые другие символы, которые, очевидно, должны переводить автомат в состояние E. Программная реализация автоматного распознавателя В листинге 2.1 приведен эскиз программы, моделирующей работу детерминированного конечного автомата. Эта программа и является универсальным распознавателем (синтаксическим анализатором) автоматных языков. В ней есть лишь некоторые условности: предполагается, что состояния обозначаются латинскими буквами (S — начальное состояние), а входной алфавит — малые латинские буквы. Не конкретизированы также способы считывания символов и проверки их наличия на входе, 51

а также то, как автомат реагирует на принятие или непринятие входной цепочки — эти части программы записаны по-русски. Листинг 2.1. Универсальный распознаватель автоматных языков type tCondition = tAlpha = tJump = < Таблица

(S, A, B, C, …, E, …); < Состояния >‘a’..’z’; < Алфавит >array [tCondition, tAlpha] of tCondition; переходов >

tFinish = set of tCondition; < Тип множества конечных состояний >var Cond Ch P Fin

tCondition; tAlpha; tJump; tFinish;

Текущее состояние Входной символ Функция переходов Конечные состояния

… < Здесь задаются значения P и Fin >… Cond := S; while Есть символы do begin Читать(Ch); Cond := P[Cond, Ch] end; if Cond in Fin then Цепочка принята else Цепочка не принята

Дерево разбора в автоматной грамматике Говоря о задаче синтаксического анализа, мы сводили ее к построению дерева разбора. Между тем, в предыдущих разделах на роль распознавателя автоматных языков предложен конечный автомат, который дерево не строит. Нет ли здесь противоречия? Нет. Дерево разбора цепочки в автоматной грамматике может быть однозначно построено, если известна последовательность переходов конечно-автоматного распознавателя. То есть распознающий автомат не только дает ответ на вопрос о принадлежности цепочки языку, но и позволяет выявить структуру цепочки. Структура при этом представлена последовательностью переходов автомата. 52

Рассмотрим, какой вид имеет дерево разбора терминальной цепочки в автоматной грамматике. Из трех видов правил автоматной грамматики правила вида A → a и A → ε могут быть использованы в процессе порождения цепочки ровно один раз, после чего процесс порождения заканчивается. Все остальные подстановки выполняются по правилам вида A → aB. Каждая такая подстановка приводит к появлению в дереве новой внутренней вершины, помеченной нетерминалом. Её левая дочерняя вершина помечается терминалом (рис. 2.13).

Рис. 2.13. Дерево разбора в автоматной грамматике

Если для грамматики типа 3 построен ДКА, то входная цепочка однозначно определяет последовательность проходимых автоматом состояний и дерево вывода. Пример автоматного языка Рассмотрим язык целых чисел со знаком. Примеры правильно записанных чисел: 177

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

Начальное состояние автомата обозначим S (рис. 2.14). Находясь в этом состоянии, автомат ожидает символ, с которого может начинаться запись числа. Это знаки «+», «–» и цифры. Соответственно, из состояния S должны исходить дуги, помеченные этими символами. Десять дуг, помеченных цифрами от 0 до 9, заменим одной, пометив ее символом ц. После того как принят знак числа, автомат должен перейти в состояние, в котором он ожидает первую цифру. Обозначим такое состояние A. Таким образом, переходы по символам «+» и «–» ведут из состояния S в состояние A.

Рис. 2.14. Конечный автомат, распознающий целые числа со знаком

Если, находясь в начальном состоянии S, автомат получил цифру, он должен перейти в состояние (обозначим его B), в котором могут быть приняты последующие цифры, если они есть. Из состояния A при получении цифры автомат также переходит в состояние B. Состояние B следует пометить как конечное, поскольку переход в это состояние означает, что на вход автомата поступила правильная запись целого числа. Дуга, помеченная символом ц, ведущая из состояния B в него же, позволяет автомату принять вторую и последующие цифры числа, если они есть. По диаграмме переходов можно записать и грамматику, порождающую язык целых чисел со знаком. Каждой дуге соответствует правило. Конечные состояния порождают правила с пустой цепочкой в правой части. S → +A | –A | цB 54

A → цB B → цB | ε На практике, как уже говорилось, приходится учитывать возможность поступления на вход автомата не только символов входного алфавита, но и любых других символов. В этой ситуации можно предполагать, что из любого состояния исходит дуга, ведущая в состояние ошибки E (рис. 2.15). Кроме того, удобно считать, что входная цепочка всегда завершается специальным символом «конец текста», который обозначают ⊥.

Рис. 2.15. Конечный автомат с состоянием ошибки и дополнительным конечным состоянием

При использовании символа ⊥ к автомату следует добавить состояние K, которое будет единственным конечным, и в которое из «бывших» конечных состояний будут направлены дуги, помеченные ⊥. Не составило бы труда заполнить для полученного автомата таблицу переходов и использовать универсальный распознаватель (см. листинг 2.1), моделирующий поведение ДКА. Но здесь мы рассмотрим другую возможность. Пользуясь диаграммой переходов (см. рис. 2.14 и рис. 2.15), напишем программу, которая ведет себя подобно конечному автомату, но не моделирует его поведение напрямую.

В начале работы, то есть, находясь в исходном состоянии, программа считывает первый символ входной цепочки и проверяет его допустимость: Читать(Символ); if not (Символ in [‘+’, ‘-‘, ‘0’.. ‘9’]) then Ошибка

Будем считать, что обращение к процедуре Ошибка останавливает работу распознавателя. Далее (по-прежнему оставаясь в начальном состоянии) проверяем, какой именно из допустимых символов поступил на вход. Если это знак, читаем следующий символ, переходя к состоянию А и предусматривая действия, которые автомат выполняет, находясь в этом состоянии: else if Символ in [‘+’, ‘-‘] then begin Читать(Символ); < Состояние A >if Символ in [‘0’..’9′] then Читать(Символ) else Ошибка end else < Символ – цифра (в состоянии S) >Читать(Символ);

Если в состоянии S поступил символ цифры, считывается следующий входной символ и происходит переход к состоянию B. После выполнения приведенного выше фрагмента программа или останавливается по причине ошибки, или приходит в состояние, аналогичное состоянию B конечного автомата. Находясь в состоянии B, автомат должен принимать все поступившие на вход цифры, оставаясь при этом в состоянии B: < Состояние B >while Символ in [‘0’.. ‘9’] do Читать(Символ);

Выход из цикла происходит, если очередной считанный символ — не цифра. Если это символ ⊥ — «конец текста», то входная цепочка закончена и автомат переходит в состояние K (см. 56

рис. 2.15), принимая входную цепочку. Если цикл прекращен по причине поступления символа, отличного от цифры и ⊥, автомат переходит в состояние ошибки: if Символ = ⊥ then Цепочка принята else Ошибка;

Как видим, распознаватель автоматного языка, каким и является наша программа, можно написать, не прибегая к прямому моделированию поведения конечного автомата с использованием таблицы переходов. Такой подход может иметь свои преимущества. Технология программирования распознавателя оказывается довольно простой: программа пишется по диаграмме переходов ДКА, которая исполняет роль схемы алгоритма. Синтаксические диаграммы автоматного языка В построенной программе-распознавателе состояния конечного автомата не фигурировали явно. Они просто соответствовали некоторым точкам программы. В противоположность состояниям, символы, которыми помечены дуги диаграммы переходов, явно используются в распознавателе. Устраним с диаграммы переходов обозначения состояний (заглавные буквы и кружки). Те места диаграммы, где были состояния автомата, превращаются в точки ветвления и соединения дуг. Терминальные символы, отмечающие переходы-дуги, наоборот разместим в кружках на этих дугах. Результат такого преобразования для диаграммы переходов автомата, распознающего целые числа, или, что то же самое, для графа автоматной грамматики, порождающей целые числа, показан на рис. 2.16а. Полученный граф носит название синтаксической диаграммы автоматного языка или автоматной грамматики.

Рис. 2.16. Синтаксические диаграммы грамматики целых чисел

Синтаксическая диаграмма может использоваться для тех же целей, что грамматика и граф переходов автомата, то есть для порождения и для распознавания предложений языка. Любой путь от входа диаграммы (соответствует начальному состоянию автомата) к её выходу (конечному состоянию K) порождает цепочку символов, являющуюся правильным предложением языка (сентенцией грамматики). Решение же задачи распознавания сводится к поиску такого пути от входа к выходу диаграммы, который соответствует заданной цепочке. По сравнению с порождающей грамматикой и конечным автоматом синтаксические диаграммы гораздо наглядней и лучше подходят для спецификации языка при его конструировании. Очень удобна диаграмма в роли схемы алгоритма при написании синтаксического анализатора. Используя другую манеру начертания дуг, переместив символ ц на дугу, ведущую в бывшее состояние B и отказавшись от явного изображения конца текста, получим более простую диаграмму, задающую синтаксис целых со знаком (рис. 2.16б). Упрощение диаграммы можно продолжить и дальше (рис. 2.16в), сохраняя ее эквивалентность исходной (рис. 2.16а). Однако, при программировании анализатора на Паскале эта последняя диаграмма не удобней предыдущей. 58

Перепишем анализатор целых чисел, пользуясь синтаксической диаграммой, показанной на рис. 2.16б, как схемой алгоритма (листинг 2.2). Чтобы избавиться от условностей будем считать, что программа имеет доступ к глобальной переменной Ch, которая хранит текущий символ. Чтение следующего входного символа выполняет процедура NextCh, которая помещает прочитанное значение в переменную Ch. Считается, что константа EOT (от End Of Text) обозначает конец текста. Реакция на ошибку возложена на процедуру Error, которая выдает сообщение об ошибке и останавливает работу программы-распознавателя. В случае принятия входной цепочки никакого специального сообщения не предусматривается. Листинг 2.2. Распознаватель целых со знаком NextCh; < Прочитать первый символ >if Ch in [‘+’, ‘-‘] then NextCh; if Ch in [‘0’..’9′] then NextCh else Error; while Ch in [‘0’..’9′] do NextCh; if Ch EOT then Error;

Следует отметить ряд важных черт получившейся программы. Она состоит из нескольких частей, разделенных в листинге пустыми строками. Первая и последняя части, как нетрудно понять, должны присутствовать всегда: перед началом анализа надо получить первый символ, а по завершении — убедиться, что в момент, соответствующий выходу из диаграммы, входная цепочка исчерпана.

Три других части строго соответствуют структуре синтаксической диаграммы (см. рис. 2.16б). На диаграмме выделяются три последовательно соединенных участка, и программа содержит три последовательно записанных и выполняемых фрагмента. Первый из них (if–then) проверяет наличие (необязательного) знака. Второй (if–then–else) — наличие обязательной цифры. Цикл while (который, как известно, может не выполниться ни разу) соответствует циклу на диаграмме, задающему последовательность из нуля или более цифр. Программа-распознаватель может быть написана по синтаксической диаграмме автоматной грамматики с использованием формальных приемов. Регулярные выражения и регулярные множества Регулярные выражения — альтернативный, отличный от порождающих грамматик и синтаксических диаграмм и имеющий свои преимущества, способ задания языка. Регулярное выражение обозначает (порождает) множество цепочек, которое называют регулярным множеством. Множество цепочек, соответствующее регулярному выражению R, будем обозначать R^. Регулярные выражения над алфавитом Σ образуются по следующим правилам: 1. Отдельный символ алфавита a ∈ Σ является регулярным выражением. Обозначаемое таким выражением множество цепочек есть , то есть состоит из одной цепочки a. 2. Пустая цепочка ε есть регулярное выражение. Обозначает регулярное множество . 3. Если R и Q — регулярные выражения над алфавитом Σ, то запись RQ (конкатенация) также является регулярным выражением. Множество, обозначаемое RQ, состоит из всех цепочек, образованных конкатенацией двух цепочек, так, что первая 60

цепочка пары порождается выражением R, а вторая — выражением Q. Формально это может быть записано так: (RQ)^ = . 4. Если R и Q — регулярные выражения над алфавитом Σ, то запись R | Q (читается «R или Q») также является регулярным выражением и обозначает регулярное множество R^ ∪ Q^, то есть множество всех цепочек, порождаемых как выражением R, так и выражением Q. 5. Если R — регулярное выражение над алфавитом Σ, то запись R* (итерация R) также является регулярным выражением, и обозначает множество всех цепочек, полученных повторением цепочек, порождаемых R, ноль или более раз. 6. Если R — регулярное выражение над алфавитом Σ, то (R) (R в скобках) также является регулярным выражением, которое обозначает то же множество, что и R. Предполагается определенный приоритет операций, с помощью которых образуются регулярные выражения. Наивысший приоритет имеет итерация (знак «*»), далее — конкатенация, далее — «или» (знак «|»). Скобки используются для изменения порядка операций. Пример 1. С помощью регулярного выражения можно задать правила записи целых чисел со знаком: (+ | – | ε ) цц*, где ц обозначает любую цифру от 0 до 9. Если это не вызывает разночтения, символ ε можно не записывать. Повторение один или более раз иногда обозначают знаком «+». R+=RR*. Другая форма выражения, определяющего целые: (+ | – | ) ц+.

Нетрудно, впрочем, записать выражение, обозначающее множество всех целых со знаком, не прибегая к условному обозначению цифр с помощью «ц»: (+ | – | ) (0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 )+ Пример 2. Регулярное выражение, задающее множество идентификаторов: б (б | ц)*. где б — буква; ц — цифра. Эквивалентность регулярных выражений и автоматных грамматик Автоматные языки являются регулярными множествами. Регулярные множества являются автоматными языками. Сказанное означает, что для любой автоматной грамматики можно записать такое регулярное выражение, что обозначаемое этим выражением множество цепочек совпадает с языком, порождаемым грамматикой. И, наоборот, для любого регулярного выражения можно найти автоматную грамматику, порождающую то же множество цепочек, что и регулярное выражение. Будем считать, что автоматный язык задается синтаксической диаграммой. Можно установить взаимно однозначное соответствие между конструкциями, из которых строятся регулярные выражения (правила 1–6) и фрагментами, из которых состоят синтаксические диаграммы автоматных грамматик. Это соответствие показано в таблице 2.2. Таблица 2.2. Эквивалентность регулярных выражений и автоматных грамматик Номер правила

Участок диаграммы Не удается отобразить связанный рисунок. Возможно, этот файл был перемещен, переименован или удален. Убедитесь, что ссылка указывает на правильный файл и верное размещение.

Используя такое соответствие, по выражению можно построить диаграмму, а по диаграмме — регулярное выражение. Уточнение деталей таких построений [Свердлов, 2008], которым мы не будем здесь заниматься, и доказывает справедливость сформулированного выше утверждения об эквивалентности. Уместно напомнить, что автоматные грамматики называют также регулярными. Для чего нужны регулярные выражения Автоматные грамматики, регулярные выражения и синтаксические диаграммы являются эквивалентными способами задания автоматных языков. По сравнению с грамматиками синтаксические диаграммы обладают большей наглядностью. Регулярные же выражения имеют то важное достоинство, что представляют собой строки символов, которые могут быть легко обработаны с помощью компьютерных программ. Обработка регулярного выражения, выступающего в роли исходных данных для некоторой программы, может иметь целью его анализ, преобразование и даже… создание распознавателя автоматного языка, порождаемого этим выражением. Последнее представляет безусловный интерес, поскольку открывает возможность автоматизации построения синтаксических анализато63

ров. Работа подобной программы может происходить по одной из схем, показанных на рисунке 2.17.

Рис. 2.17. Использование регулярных выражений

Регулярные выражения наглядней порождающих грамматик. Это обусловлено тем, что предусмотрено явное обозначение повторения (знак итерации «*»). В нотации грамматик итерация задается с помощью рекурсии. Сравните, например, грамматики G10 и G12, задающие язык идентификаторов, с эквивалентным регулярным выражением из примера 2. Регулярные выражения как языки Регулярное выражение над алфавитом Σ — это цепочка символов в расширенном алфавите Σ ∪ < |, *, (, ) >. Множество всех таких цепочек-выражений образует язык. Возникает естественный вопрос, к языкам какого типа по классификации Н. Хомского этот язык принадлежит. К автоматным? Тогда, быть может, правила записи регулярных выражений можно задать регулярным выражением? Нет, нельзя. Синтаксис регулярных выражений может быть определен только контекст64

но-свободной, но не автоматной грамматикой. Вот эта грамматика: R → a | RR | R* | R ″|″ R | ( R ) | ε В этой записи есть ряд условностей: a обозначает любой символ алфавита Σ, запись ″|″, представляет знак «|», используемый в регулярных выражениях и совпадающий с аналогичным знаком, применяемым при записи грамматик. Приведенная грамматика не отражает принятый для регулярных выражений порядок операций. Грамматика, трактующая структуру регулярного выражения в соответствии с приоритетами операций, может быть записана так: R → T | R ″|″ T T → M | RM M → a | M* | ( R ) | ε Расширенная нотация для регулярных выражений Регулярные выражения — это строки символов, и тем они интересны как средство задания автоматных языков. Но использование надстрочных знаков «*» и «+» несколько затрудняет запись выражений и их считывание компьютерной программой. Получили распространение другие варианты обозначений. Повторение ноль или более раз обозначают фигурными скобками: R* = . Используются также квадратные скобки, обозначающие необязательность заключенного в них выражения: [ R ] = ( R | ε ). Знаки «*» и «+» в этом случае уже не используются. Соглашения о способах записи символов, с помощью которых строятся сами выражения (скобки, знак «|»), в случае, если они также входят в 65

терминальный алфавит, могут быть разными. Можно заключать такие метасимволы в кавычки «″». При необходимости записать саму кавычку ее заключают в апострофы «′», а апостроф, если нужно, записывается в кавычках. По этим правилам регулярные выражения, обозначающие множество целых со знаком и множество идентификаторов, будут выглядеть так: [+ | – ] ц б . На этом мы заканчиваем рассмотрение автоматных грамматик, в ходе которого удалось построить простые и эффективные методы распознавания автоматных языков. С помощью автоматных грамматик определяется синтаксис простейших элементов языков программирования: идентификаторов, чисел, других констант, знаков операций и разделителей.

Контекстно-свободные (КС) грамматики и языки К классу контекстно-свободных относятся грамматики, у которых не накладывается никаких ограничений на вид правых частей их правил, а левая часть каждого правила — единственный нетерминал. С помощью КС-грамматик задают синтаксис языков программирования. Однозначность КС-грамматики Как уже формулировалось выше, однозначной называется грамматика, в которой каждой сентенции соответствует единственное дерево вывода. Однако, как мы видели, дерево вывода не всегда строится явно в ходе решения задачи разбора. Поэтому имеет смысл сформулировать определение однозначности без привлечения понятия «дерево вывода». 66

Левосторонние и правосторонние выводы в КС-граматике

Рассмотрим (однозначную) грамматику G8, задающую синтаксис арифметических выражений. G8:

Построим два различных вывода цепочки a + b*c в этой грамматике. В первом случае, если сентенциальная форма содержит более одного нетерминала, будем выполнять подстановку (замену нетерминала правой частью одного из правил) для самого левого нетерминала этой сентенциальной формы: E ⇒ E + T ⇒ T + T ⇒ M + T ⇒ a + T ⇒ a + T*M ⇒ a + M*M ⇒ a + b*M ⇒ a + b*c Такой вывод называется левосторонним. Аналогично, вывод, в ходе которого замене всегда подвергается самый правый нетерминал сентенциальной формы, называется правосторонним. Для цепочки a + b*c в грамматике G8 он будет таким: E ⇒ E + T ⇒ E + T*M ⇒ E + T*c ⇒ E + M*c ⇒ E + b*c ⇒ T + b*c ⇒ M + b*c ⇒ a + b*c Нетрудно убедиться, что обе эти последовательности подстановок соответствуют одному и тому же дереву вывода, хотя и разному порядку его построения. Для цепочки a + b*c в грамматике G8 и левосторонний и правосторонний вывод строятся однозначно. Это же справедливо и для любой другой цепочки, порождаемой G8. КС-грамматика называется однозначной, если для каждого предложения языка, порождаемого этой грамматикой, существует единственный левосторонний вывод. 67

Алгоритмы распознавания КС-языков Существует алгоритм, позволяющий для любой КС-грамматики, проверить принадлежность произвольной цепочки терминальных символов языку, порождаемому этой грамматикой, и получить вывод этой цепочки. Наличие такого алгоритма и принцип его устройства следуют из того простого соображения, что, если имеется конечная цепочка терминалов, то для проверки ее принадлежности языку достаточно построить все возможные сентенциальные формы грамматики, имеющие длину, совпадающую с длиной этой цепочки. Количество этих сентенциальных форм конечно. Такого рода алгоритм действует по принципу полного перебора. Объем перебора может быть сокращен, если процесс порождения сентенциальных форм будет организован так, что станет возможным определить тупики в ходе перебора еще до получения сентенциальной формы нужной длины. Переборные алгоритмы работают с возвратами и вследствие своей неэффективности мало пригодны для практического использования. Для организации перебора с возвратами используют стек — структуру данных, подчиняющуюся дисциплине «последним пришел — первым ушел» (LIFO — Last In First Out). В то же время для достаточно обширных подклассов КСграмматик, подчиняющихся некоторым дополнительным ограничениям, существуют эффективные алгоритмы распознавания, которые мы будем в дальнейшем рассматривать и применять. Для синтаксического анализа КС-языков используются как нисходящие (строящие дерево разбора от корня к листьям), так и восходящие алгоритмы.

Распознающий автомат для КС-языков Для автоматных языков роль распознавателя может выполнять детерминированный конечный автомат. Существует ли универсальный автоматный распознаватель КС-языков? Да, существует. Для произвольной КС-грамматики может быть построен недетерминированный автомат с магазинной памятью, принимающий язык, порождаемый этой грамматикой. Автомат с магазинной памятью (магазинный автомат, МПавтомат) подобен конечному автомату, оснащенному дополнительным запоминающим устройством со стековой 8 дисциплиной «последним пришел — первым ушёл». Переходы МП-автомата определяются не только входным символом и текущим состоянием, но и значением вершины стека — элемента, поступившего в магазин последним. Недетерминированный МП-автомат — это не что иное, как устройство, реализующее перебор с возвратами. В этом смысле он эквивалентен обсуждавшемуся выше общему алгоритму распознавания КС-языков и так же неэффективен. Для КС-грамматик, подчиняющихся определенным ограничениям, могут быть построены эффективные детерминированные магазинные автоматы, которые могут использоваться на практике для трансляции языков программирования. Самовложение в КС-грамматиках Если в грамматике G есть нетерминал A, для которого

В литературе на русском языке стек часто называют «магазином» по аналогии с магазином автоматического оружия: патрон, заряженный в магазин последним, выстреливается первым. 8

то есть из A нетривиально выводится цепочка α1Aα2, где α1, α2 — непустые цепочки терминалов и нетерминалов, то говорят, что такая грамматика содержит самовложение. Например, грамматика арифметических выражений G8 содержит самовложение, поскольку из ее начального нетерминала E выводится цепочка (E). E ⇒ T ⇒ M ⇒ ( E ). Содержит самовложение и грамматика регулярных выражений, +

поскольку: R ⇒(R) . Самовложение — характерный признак КС-грамматик. КС-грамматика, не содержащая самовложения, эквивалентна автоматной грамматике. Языки арифметических и регулярных выражений являются контекстно-свободными и не могут быть заданы автоматными грамматиками. Синтаксические диаграммы КС-языков Синтаксические диаграммы КС-языка могут быть построены по его грамматике на основании следующих правил: 1. Для каждого нетерминала грамматики строится отдельная диаграмма, обозначенная названием этого нетерминала. 2. Нетерминалы из правых частей правил изображаются на диаграммах прямоугольниками, внутри которых записывается название нетерминала. Терминальные символы изображаются в кружках или овалах. 3. Для каждой правой части правила строится ветвь, представляющая собой последовательно соединенные прямоугольники 70

и круги (овалы), следующие в том же порядке слева направо, что и соответствующие нетерминалы и терминалы правой части правила. 4. Ветви, соответствующие альтернативным правым частям правил для одного нетерминала, соединяются параллельно и образуют диаграмму для данного нетерминала. Рассмотрим примеры построения диаграмм. Пусть в некоторой грамматике имеется правило A → a, тогда на диаграмме для нетерминала A будет ветвь

Правило A → BcDe порождает ветвь

Если других правил для нетерминала A в грамматике нет, то диаграмма для этого нетерминала получается параллельным соединением ветвей. Правила для А удобней объединить в одно с альтернативными правыми частями: A → a | BcDe.

Продолжим пример. Поскольку в правилах для A фигурируют нетерминалы B и D, то в грамматике должны быть правила, в которых B и D записаны в левой части. Пусть правило для B имеет вид: B → c | bB. Тогда строится такая диаграмма:

Можно, однако, заметить, что правила для B удовлетворяют ограничениям автоматных грамматик. А синтаксические диаграммы автоматных грамматик не должны содержать нетерминалов. Противоречия нет. Диаграмма для B может быть преобразована. Поскольку прохождение прямоугольного блока, обозначающего B, равносильно (порождает такую же цепочку терминалов) повторному входу в диаграмму, вход в блок B можно заменить повторным входом в диаграмму.

Такое преобразование, устранившее с диаграммы нетерминальный блок B, стало возможным благодаря тому, что нетерминал B был самым правым символом в одной из альтернативных правых частей правил для B. В результате преобразования концевая (правая) рекурсия заменена циклом. Выполнив элементарное преобразование, можно нарисовать диаграмму нетерминала B в традиционном виде:

Замена правой рекурсии циклом всегда возможна (и желательна) при построении синтаксических диаграмм КС-грамматики 9. ИнЗамена концевой рекурсии циклом возможна и в программах. Если в некоторой процедуре последним выполняется рекурсивный вызов этой процедуры, то он может быть заменен переходом к началу процедуры, то есть циклом.

тересно заметить, что сами правила 1–4 не предусматривают циклов, в то время как на практике циклы на диаграммах имеются почти всегда. Такую же диаграмму для B можно было получить, построив фрагмент конечного автомата, а затем устранив из него состояния.

Завершая пример, зададим правило для нетерминала D: D → fBD | ε и построим диаграмму.

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

Определение языка с помощью синтаксических диаграмм В действительности синтаксические диаграммы строятся, как правило, не по имеющейся грамматике, а служат самостоятельным средством проектирования языков, в том числе и языков программирования. При этом язык определяется совокупностью диаграмм, первая из которых соответствует начальному нетерминалу грамматики. 73

Определять синтаксис в виде совокупности диаграмм, на которых имеются нетерминальные блоки, можно не только для контекстно-свободных, но и для автоматных языков. Только из-за отсутствия самовложения диаграммы автоматного языка всегда можно объединить в одну, не содержащую нетерминалов. Для этого достаточно «подставить» в диаграмму начального нетерминала другие диаграммы вместо соответствующих прямоугольных блоков. Для КС-языка такая подстановка невозможна из-за самовложения. Язык многочленов

Для примера построим синтаксические диаграммы, задающие правила записи (синтаксис) многочленов от x c постоянными целочисленными коэффициентами, то есть определяющие язык многочленов. Примеры таких многочленов: 5×3 + x2 – 12x + 10 –x 199 Последний пример может вызвать возражение, поскольку не содержит переменной x. Условимся, однако, и такую запись считать правильным многочленом нулевой степени. Чтобы запись многочленов могла быть обработана компьютерной программой (транслятором или вычислителем многочленов), предусмотрим возможность записи символов «в строку» без надстрочных показателей степени. Возведение в степень будем обозначать, как это принято в языке Бейсик и некоторых диалектах Алгола, с помощью знака «^». Тогда первый пример многочлена запишется так: 5x^3 + x^2 – 12x + 10

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

нетерминала, который в нашем случае есть не что иное как «Многочлен». Многочлен состоит из отдельных слагаемых, между которыми записываются знаки операций. Перед первым слагаемым также можно записать знак. Слагаемых должно быть не меньше одного. С учетом этого получается диаграмма, показанная на рисунке 2.18.

Рис. 2.18. Синтаксическая диаграмма многочлена

Теперь надо построить диаграмму для нетерминала «Слагаемое», который мы ввели в грамматику многочленов. Вначале изобразим ветвь диаграммы, соответствующую полному варианту слагаемого, когда присутствуют все его элементы: коэффициент, буква x, знак возведения в степень и сама степень (рис. 2.19а).

Рис. 2.19. Синтаксическая диаграмма слагаемого

Затем проведем «обходные» ветви, позволяющие предусмотреть такие варианты слагаемого, когда нет коэффициента (предполагается равным единице), буквы x и последующей степени, или 75

только степени (см. рис. 2.19б). При этом не должно появиться такого пути на диаграмме, пройдя по которому мы минуем как коэффициент, так и x. Коэффициент перед слагаемым и показатель степени записываются как целые числа без знака. Соответствующий нетерминал назван «Целое». В дальнейшем мы всегда будем считать (если не оговорено иное), что «целое» означает целое без знака. Целое без знака есть последовательность, состоящая из одной или более цифр (рис. 2.20а). Диаграмма для нетерминала «Цифра» показана на рис. 2.20б.

Рис. 2.20. Синтаксические диаграммы для целого и для цифры

Поскольку арабские цифры используются в самых разнообразных языках, было бы неудобно каждый раз приводить диаграмму, подобную изображенной на рис. 2.20б. В дальнейшем будем вместо нетерминального блока «Цифра» использовать на диаграммах овал (рис. 2.20в), считая что «цифра» — это «почти терминальный символ». Нетрудно понять (хотя бы по отсутствию самовложения), что язык многочленов — автоматный. Все диаграммы можно было бы объединить в одну, не содержащую нетерминальных блоков. Однако делать этого мы не будем. Во-первых, несколько несложных диаграмм воспринимаются проще, чем одна громоздкая. Во-вторых, использование промежуточных понятий, таких 76

как, например, «Целое», позволяет избежать дублирования: нетерминал «Целое» встречается на диаграмме слагаемого дважды. В-третьих, представив автоматный язык с помощью КСдиаграмм, мы на простом примере рассмотрим методы распознавания КС-языков, не потеряв при этом общности подхода. Синтаксический анализ КС-языков методом рекурсивного спуска Рекурсивный спуск — это эффективный и простой нисходящий алгоритм распознавания. Он состоит в следующем. Для каждого нетерминала грамматики (понятия, конструкции языка), то есть для каждой синтаксической диаграммы, записывается отдельная распознающая процедура. При этом соблюдаются следующие соглашения: 1. Перед началом работы процедуры текущим является первый символ анализируемого понятия (см. рис. 2.21). 2. В процессе работы процедура считывает все символы входной цепочки, относящиеся к данному нетерминалу (выводимые из данного нетерминала) или сообщает об ошибке. Если правила для данного нетерминала содержат в правых частях другие нетерминалы (синтаксическая диаграмма данного нетерминала содержит другие нетерминалы), то процедура обращается к распознающим процедурам этих нетерминалов для анализа соответствующих частей входной цепочки. 3. По окончании работы процедуры текущим становится первый символ, следующий во входной цепочке за данной конструкцией языка (символами, выводимыми из данного нетерминала).

Рис. 2.21. Текущий символ в начале и конце работы распознающей процедуры нетерминала А

Распознавание начинается вызовом распознающей процедуры начального нетерминала. При этом текущим символом, как это следует из п. 1, должен быть первый символ входной цепочки. По завершении работы начальной процедуры текущим должен быть символ «конец текста». Таким образом, анализ методом рекурсивного спуска всегда строится по следующей схеме: NextCh; S; if Ch EOT then Error;

Название «рекурсивный спуск» обусловлено тем, что при наличии в грамматике самовложения вызовы распознающих процедур будут рекурсивными. Процесс распознавания развивается от начального нетерминала (корень дерева разбора) через вызов процедур для промежуточных нетерминалов (внутренние вершины дерева) к анализу отдельных терминальных символов (листья дерева). Это нисходящий разбор. Каждая распознающая процедура строится по соответствующей синтаксической диаграмме, которая играет роль схемы алгоритма. Соответствие участков диаграмм и фрагментов распознающих процедур показано в табл. 2.3. В таблице участки диаграмм обозначаются D, D1, D2, …, Dn. Соответствующие этим участкам фрагменты программы-распознавателя (распознающих процедур) обозначены P(D), P(D1), P(D2), …, P(Dn).

Таблица 2.3. Правила построения распознавателя по синтаксической диаграмме Диаграмма D

if Ch = ′a′ then NextCh else Error;

Анализ отдельного терминального символа

Анализ нетерминала: вызов распознающей процедуры нетерминала A

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

if Ch in first(D1) then P(D1) else if Ch in first(D2) then P(D2) …

else if Ch in first(Dn) then P(Dn) else Error;

Ветвление. first(D1), first(D2), …, first(Dn) — множества направляющих символов ветвей D1, D2, …, Dn. Множество направляющих символов ветви Di образуют терминальные символы, которые могут встретиться первыми при движении по ветви Di.

if Ch in first(D1) then P(D1);

Ветвление с пустой альтернативой (необязательное вхождение D1)

while Ch in first(D1) do

Повторение D1 ноль или более раз

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

Пользуясь методом рекурсивного спуска, запрограммируем синтаксический анализатор многочленов, правила записи которых определены диаграммами на рис. 2.18–2.20. Будем считать, что анализатор должен просто отвечать на вопрос, является ли введенная пользователем строка правильно записанным многочленом. Основная программа анализатора

Вначале необходимо подготовить текст для чтения анализатором. Было бы неправильно делать так, чтобы в основной программе и распознающих процедурах отражались особенности представления входной цепочки, то есть программировать таким образом, чтобы основные части анализатора зависели от того, считываются ли символы из файла, вводятся с терминала, извлекаются из окна редактора текста или получаются как-либо подругому. Эта специфика будет скрыта в нескольких процедурах, которые только и будут зависеть от конкретного представления входной цепочки. Предусмотрим, что подготовка входного текста к чтению выполняется процедурой ResetText: begin ResetText;

Далее вызываем распознающую процедуру начального нетерминала, которым в нашей задаче является «Многочлен»: Polynom;

Процедура Polynom считывает символы входной цепочки, проверяя, соответствует ли их порядок синтаксису многочленов. Если необходимо, она обращается к другим распознающим процеду80

рам. В случае, когда входная цепочка действительно содержит многочлен, процедура Polynom оставляет текущим (содержащимся в переменной Ch) символ, следующий за многочленом. Если при анализе многочлена обнаруживается ошибка, вызывается процедура Error, останавливающая работу всего анализатора. Для завершения анализа остается проверить, не содержится ли за правильно записанным многочленом во входной цепочке лишних символов, то есть, следует ли за многочленом символ «конец текста»: if Ch EOT then Error(‘Ожидается конец текста’) else WriteLn(‘Правильно’); WriteLn; end.

Константы, переменные и вспомогательные процедуры

Теперь можно записать начало программы с описаниями констант и переменных, использованными в основном блоке. Кроме глобальной переменной Ch, обозначающей текущий символ, предусмотрим глобальную переменную Pos, которая будет хранить номер этого символа во входной цепочке. program ParsePoly; const EOT = chr(0); < Признак "конец текста" >var Ch : char; < Очередной символ >Pos : integer;

Взаимодействие с входным текстом будут выполнять процедуры ResetText — готовит входную цепочку к считыванию распознавателем, и NextCh — читает очередной символ входной цепочки, помещая его в переменную Ch.

Использование глобальных переменных в процедурах, вообщето, плохая практика. Хотя мы еще не начали обращаться к Ch и Pos в процедурах распознавателя, но вот-вот сделаем это. Оправданием служит специфика задачи. Синтаксический анализатор и компилятор — своеобразные программы, в которых используется не слишком много переменных. А в нашем анализаторе переменных будет и вовсе две — только что определенные Ch и Pos. Их передача в процедуры через параметры загромоздила бы программу, в то время как обращение за очередным символом, например, к процедуре NextCh все равно выглядело бы всегда одинаково: NextCh(Ch, Pos). Предусмотрим чтение исходных данных (записи многочлена) из стандартного входного файла (по умолчанию — ввод с клавиатуры). Сообщения распознавателя будут выводиться в стандартный выходной файл (т.е. на экран). В этом случае процедура, подготавливающая текст, запишется так: < Подготовить текст >procedure ResetText; begin WriteLn(‘Введите многочлен от x с целыми коэфф-тами’); Pos := 0; NextCh; < Чтение первого символа >end;

При чтении очередного символа будем игнорировать пробелы, считая их незначащими. Это позволит при записи исходного многочлена применять пробелы, например, для отделения одного слагаемого от другого. procedure NextCh; < Читать следующий символ >begin repeat Pos := Pos+1; if not eoln then Read(Ch) else begin ReadLn; Ch := EOT;

end; until Ch ‘ ‘; end;

Такой пропуск пробелов делает их допустимыми в любом месте записи многочлена. К примеру, такая строка должна теперь считаться правильной: 1 2 3 x ^ 4 + 5 6 7 x + 8 9

Это не соответствует соглашениям современных языков программирования. Более совершенное решение вопроса о пробелах будет рассмотрено в следующей главе, пока же примем простейший подход, который все же предпочтительней полного запрета пробелов. Процедура, реагирующая на ошибку, тоже зависит от соглашений по вводу и выводу. Как мы уже условились, она будет выдавать сообщение на экран: procedure Error(Message: string); < Ошибка > < Message - сообщение об ошибке >begin WriteLn(‘^’: Pos); WriteLn(‘Синтаксическая ошибка: ‘, Message); Halt; < Прекращение работы анализатора >end;

Вывод знака ‘^’ в позиции Pos позволяет указать стрелкой на символ, вызвавший ошибку. Диалог с анализатором может быть таким: Введите многочлен от Х с целыми коэфф-тами 2x + 1.2 ^ Синтаксическая ошибка: Ожидается конец текста

Реакция программы в этом примере может показаться непонятной, хотя она совершенно корректна. Получение такого сообщения означает: «Если бы на этом месте запись многочлена закончилась, было бы синтаксически правильно. Но в указанном месте стоит неподходящий символ». Понятно, что распознаватель 83

не может знать наших желаний и содержательно реагировать на попытку записать вещественное число вместо целого. Распознающие процедуры

Для каждого нетерминала грамматики многочленов, то есть для каждой синтаксической диаграммы (рис. 2.18 – 2.20) записываем одну распознающую процедуру. Первой — процедуру для нетерминала «Многочлен» — начального нетерминала грамматики (рис. 2.18). Трудность, однако, состоит в том, что диаграмма на рис. 2.18 неудобна для программирования — она содержит цикл с выходом из середины, в то время как в Паскале такого цикла нет. Заменим диаграмму эквивалентной, содержащей цикл с предусловием (с выходом в начале).

Рис. 2.22. Преобразованная диаграмма «Многочлен»

Теперь не составляет труда записать распознающую процедуру, структура которой в точности повторяет структуру диаграммы: на диаграмме три последовательно соединенных участка — в процедуре три оператора, выполняемых один за другим: if, вызов процедуры Addend, цикл while. procedure Polynom; < Многочлен >begin if Ch in [‘+’, ‘-‘] then NextCh; Addend; < Слагаемое >while Ch in [‘+’, ‘-‘] do begin NextCh; Addend; end; end;

Следующий нетерминал — «Слагаемое». Однако диаграмма, показанная на рис. 2.19, не разделяется на типовые фрагменты, что затрудняет программирование распознавателя. Неструктурированность обусловлена фрагментом, который помечен на рисунке знаком «?». Преобразуем диаграмму в эквивалентную, но состоящую только из совокупности типовых структур (рис. 2.23). Для этого изобразим отдельно две ветви: одна соответствует слагаемому, начинающемуся с числа, другая — с буквы x. Фрагмент, выделенный на исходной диаграмме пунктирной рамкой, преобразуем в нетерминал «Степень».

Рис. 2.23. Синтаксические диаграммы «Слагаемое» и «Степень»

Программирование распознающих процедур Addend (слагаемое) и Power (степень) теперь выполняется легко: диаграммы служат схемами алгоритмов. procedure Addend; < Слагаемое >begin if Ch = ‘x’ then begin NextCh; Power; < Степень >end else begin Number; < Целое >if Ch = ‘x’ then begin NextCh; Power; end; end; end; procedure Power; < Степень >begin if Ch = ‘^’ then begin

NextCh; Number; end; end;

Полезно обратить внимание на дисциплину вызова процедуры NextCh. Следующий символ считывается, когда опознан текущий. Последняя распознающая процедура — для «Целого». И в этом случае тоже можно преобразовать исходную диаграмму (см. рис. 2.20), отделив блок, соответствующий первой цифре (обязательной), от остальных блоков (рис. 2.24).

Рис. 2.24. Синтаксическая диаграмма «Целое»

Предусматривать отдельную распознающую процедуру для «почти терминального символа» «цифра» неразумно. Проще и наглядней непосредственно проверять принадлежность очередного знака множеству цифр. procedure Number; < Целое >begin if Ch in [‘0’..’9′] then NextCh else Error(‘Число начинается не с цифры’); while Ch in [‘0’..’9′] do NextCh; end;

Распознаватель готов. Осталось только расположить в программе написанные процедуры в правильном порядке — описание процедуры поместить перед ее вызовом. Поскольку рекурсии в этом примере нет, сделать это легко.

На рассмотренном примере мы продемонстрировали, что синтаксический анализатор методом рекурсивного спуска можно написать «почти так же быстро, как мы вообще можем писать» [Хантер, 1984]. Требование детерминированного распознавания Уже в ходе предыдущего рассмотрения можно было заметить, что рекурсивный спуск позволяет построить анализатор не для любой КС-грамматики. Ограничения возникают при анализе направляющих символов отдельных ветвей синтаксической диаграммы. Множество направляющих символов first(D) ветви D синтаксической диаграммы образуют терминальные символы, которые могут встретиться первыми при движении по диаграмме вдоль этой ветви. Движение по диаграмме предполагает, что при достижении прямоугольного блока, изображающего нетерминал, оно продолжается по диаграмме этого нетерминала с последующим возвратом на исходную диаграмму. Порядок действий анализатора, работающего по методу рекурсивного спуска, и определяется анализом направляющих символов отдельных ветвей синтаксической диаграммы. Чтобы алгоритм работал без возвратов, выбор направления движения по диаграмме выполнялся однозначно должно соблюдаться требование детерминированного распознавания: В каждом разветвлении синтаксической диаграммы множества направляющих символов отдельных ветвей не должны попарно пересекаться.

В рассмотренной выше грамматике многочленов требование детерминированного распознавания всегда соблюдается. Возьмем, например, диаграмму, показанную на рис. 2.22. На ней две точки ветвления. Первая — на входе в диаграмму, вторая — на выходе. В первом разветвлении три ветви. Множества направляющих символов этих ветвей: [‘+’] — верхняя ветвь; [‘0’..’9′, ‘X’] — средняя ветвь; [‘–’] — нижняя ветвь. Как видно, эти множества не пересекаются. В правой точке происходит ветвление на два направления. Одно ведет на выход из диаграммы, множество направляющих символов этой ветви состоит из символа «конец текста»: [⊥]. Другая ветвь соответствует очередному витку цикла, ее множество направляющих символов равно [‘+’, ‘–’]. Пересечения множеств снова нет. Нетрудно убедиться, что не пересекаются и множества направляющих символов отдельных ветвей диаграмм, показанных на рисунках 2.23 и 2.24. LL-грамматики LL(k)-грамматикой называется КС-грамматика, в которой выбор правила в ходе левостороннего вывода однозначно определяется не более чем k очередными символами входной цепочки, считываемой слева направо. Название «LL» происходит от двух слов «left» (левый), встречающихся в описании хода распознавания в LL-грамматике: левосторонний вывод при чтении слева. Самыми удобными для распознавания, конечно же, являются LL(1) грамматики, в кото88

рых выбор направления распознавания однозначно определяется очередным входным символом. Сформулированное выше требование детерминированного распознавания при рекурсивном спуске есть не что иное, как необходимость того, чтобы используемая грамматика относилась к классу LL(1). Рекурсивный спуск — это детерминированный метод нисходящего разбора КС-языков, порождаемых LL(1)-грамматиками. Левая и правая рекурсия Рассмотрение грамматик с левой и правой рекурсией позволит нам получить некоторые признаки, помогающие определить наличие или отсутствие LL(1) свойства у КС-грамматик. Если в грамматике G существует нетерминал A, для которого +

, где α — непустая цепочка, грамматика содержит левую рекурсию. G

Грамматика, содержащая левую рекурсию, не может быть LL(1) грамматикой. Если в грамматике G существует нетерминал A, для которого +

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

рекурсию. Леворекурсивная грамматика всегда может быть преобразована в эквивалентную праворекурсивную. Синтаксический анализ арифметических выражений Рассмотрим арифметические выражения, синтаксис которых задается грамматикой G8:

E→T|E+T|E–T T→M|T*M|T/M 89

M→a|b|c|(E) Эта КС-грамматика, построенная нами раньше, обладает рядом достоинств. Она однозначна и ассоциирует операнды в соответствии с общепринятым порядком выполнения операций, когда вначале выполняются умножение и деление, затем — сложение и вычитание. Однако нетрудно видеть, что G8 леворекурсивна. Действительно, для нетерминала E справедливо: E ⇒ E + T. Наличие левой рекурсии препятствует использованию рекурсивного спуска. G8 может быть заменена эквивалентной (порождающей тот же язык) праворекурсивной грамматикой: G13: E → T | T + E | T – E T→M|M*T|M/T M→a|b|c|(E) Хотя левой рекурсии больше нет, грамматика G13 не является LL(1)-грамматикой. Чтоб убедиться в этом, достаточно обратиться к правилам для нетерминала E: E→T|T+E|T–E Напомню, что эту строку следует рассматривать как сокращенную запись трех альтернативных правил для нетерминала E. Очевидно, что выбор одного из этих трех правил на основе анализа одного входного символа невозможен, поскольку правая часть каждого правила начинается одним и тем же нетерминалом T. На рис. 2.25 показана синтаксическая диаграмма нетерминала E грамматики G13, рассмотрение которой также убеждает, что требование детерминированного распознавания не выполнено: множества направляющих символов всех трех ветвей совпадают: first1 = first2 = first3 = < a, b, c, ( >.

Рис. 2.25. Диаграмма нетерминала E грамматики G13

Грамматика G13 и соответствующие синтаксические диаграммы могут быть преобразованы так, чтобы использование рекурсивного спуска стало возможным. Особенно легко увидеть возможность преобразования диаграмм. Действительно, достаточно вынести блок T из трех параллельных ветвей и поместить его в общую ветвь, как требование детерминированного распознавания для диаграммы нетерминала E будет соблюдено (рис. 2.26).

Рис. 2.26. Преобразованная диаграмма нетерминала E грамматики выражений

Аналогичное изменение может быть выполнено и для диаграммы слагаемого (нетерминал T). Менее очевиден способ преобразования грамматики. Потребуется два дополнительных нетерминала. Обозначим их A и B. Тогда новая грамматика может быть записана так: G14: E → T A A→ε|+E|–E T→MB B→ε|*T|/T 91

M→a|b|c|(E) Содержательно A и B можно трактовать как «выражение без первого слагаемого» и «слагаемого без первого множителя» соответственно. G14 — это LL(1)-грамматика для арифметических выражений. Но и она не вполне может нас устроить. Дело в том, что G14, как и G13 (но не G8), связывает операнды нескольких идущих подряд операций одного приоритета неподходящим образом, группируя их справа налево. На рис. 2.27а показано дерево вывода выражения a – b – c в грамматике G14.

Рис. 2.27. Дерево выражения a – b – c

Устранив из этого синтаксического дерева нетерминалы (и ε) и перенося знаки операций во внутренние вершины, получим семантическое дерево выражения (рис. 2.27б), которое, увы, не соответствует правильному порядку его вычисления: оно подразумевает группировку операндов a – (b – c), в то время как a – b – c = (a – b) – c. Правильное семантическое дерево можно видеть на рис. 2.27в. Модернизируем G14 с целью обеспечить правильную ассоциацию операций и операндов. Получаем грамматику G15: 92

G15: E → T A A → ε | + TA | – TA T→MB B → ε | * MB | / MB M→a|b|c|(E) Эта однозначная праворекурсивная LL(1)-грамматика приписывает выражению правильную структуру. По ней без труда может быть написан синтаксический анализатор, работающий по алгоритму рекурсивного спуска. Интересно отметить, что программа-распознаватель, написанная по этой грамматике, будет рекурсивной (что, как известно, эквивалентно итерации), но не будет содержать циклов. Недостатками такой грамматики является некоторая ее громоздкость и наличие нетерминалов A и B с неочевидным смыслом. Удовольствие написать распознаватель по грамматике G15 предоставлю читателям. Запрограммировать его вы сможете так же быстро, как быстро умеете писать. А теперь мы воспользуемся теми выразительными средствами, которые дают синтаксические диаграммы. Это в первую очередь возможность использования цикла вместо рекурсии. Вообще, можно заметить, что некоторые трудности, возникающие на практике при использовании грамматик Хомского, обусловлены тем, что с их помощью приходится выражать повторение через рекурсию. Так, о выражении, представляющем собой просто последовательность слагаемых, мы вынуждены думать как о рекурсивной конструкции: выражение — это первое слагаемое, за которым после знака снова записано выражение (правая рекурсия, неподходящая группировка слагаемых: первое слагаемое складывается со всем остальным выражением). Или: если к выражению прибавить или от выражения отнять слагаемое, то сно93

ва получится выражение (левая рекурсия, правильная группировка слагаемых). Эти проблемы могут быть устранены добавлением в нотацию формальных грамматик явного обозначения для повторения, что и будет сделано при рассмотрении грамматик языков программирования. Синтаксические диаграммы также позволяют обойтись без рекурсии там, где она служит всего лишь для задания повторений. Рассмотрим диаграмму нетерминала E (см. рис. 2.26). Налицо рекурсия: на диаграмме E присутствует нетерминальный блок E. Но это правая, концевая рекурсия. Обращение к блоку E можно заменить переходом на вход диаграммы (рис. 2.28а).

Рис. 2.28. Синтаксическая диаграмма выражения, не содержащая рекурсии

Такую диаграмму для выражения можно было построить и без выписывания и преобразования грамматики. Суть изображенного проста: выражение — это последовательность одного или более слагаемых, между которыми записываются знаки «+» или «– ». Поскольку обработка слагаемых в ходе синтаксического анализа будет происходить последовательно в цикле, не составит труда организовать трансляцию так, чтобы это соответствовало выполнению операций слева направо. Чтобы программировать распознаватель на Паскале было удобней, преобразуем диаграмму в эквивалентную, содержащую цикл с предусловием (рис. 2.28б). Аналогично строится диаграмма слагаемого (нетерминал T) (рис. 2.29а). Диаграмма множителя соответствует правилам для нетерминала M в грамматиках G8, G13, G14, G15 (рис. 2.29б). 94

Рис. 2.29. Синтаксические диаграммы слагаемого и множителя

Теперь можно программировать анализатор. Запишем только распознающие процедуры. Константы, переменные и вспомогательные процедуры предполагаются такими же, как в распознавателе многочленов. Начать естественно с процедуры, соответствующей начальному нетерминалу, то есть с процедуры E: procedure E; begin T; while Ch in [‘+’, ‘-‘] do begin NextCh; T; end; end;

Далее записываем распознаватель слагаемого: procedure T; begin M; while Ch in [‘*’, ‘/’] do begin NextCh; M; end; end;

И, наконец, распознающую процедуру для нетерминала M — множителя: procedure M; begin if Ch in [‘a’, ‘b’, ‘c’] then NextCh else if Ch = ‘(‘ then begin NextCh; E; if Ch = ‘)’ then NextCh else Error(‘Ожидается «)»‘); end else Error(‘Ожидается a, b, c или «(«‘); end;

Остается только один вопрос: как разместить три эти процедуры в программе? По общему правилу языка Паскаль любой идентификатор может быть использован только после его описания. Процедура E вызывает процедуру T, поэтому должна располагаться после нее. Процедура T вызывает M, поэтому М надо разместить перед T. Получается такой порядок: M; T; E. Но из процедуры M вызывается E, в то время как описание E мы разместили после M. Выходом из этой ситуации, которая возникла из-за наличия в нашей программе косвенной рекурсии, является использование директивы forward для опережающего описания процедуры E. Структура программы будет такой: procedure E; forward; procedure M; …

Есть и другое, весьма изящное решение проблемы: использование вложенных процедур. Такой распознаватель представлен в листинге 2.3. 96

Листинг 2.3. Распознаватель арифметических выражений procedure E; procedure T; procedure M; begin if Ch in [‘a’, ‘b’, ‘c’] then NextCh else if Ch = ‘(‘ then begin NextCh; E; if Ch = ‘)’ then NextCh else Error(‘Ожидается «)»‘); end else Error(‘Ожидается a, b, c или «(«‘); end ; begin M; while Ch in [‘*’, ‘/’] do begin NextCh; M; end; end ; begin T; while Ch in [‘+’, ‘-‘] do begin NextCh; T; end; end ;

Включение действий в синтаксис Синтаксический анализатор отвечает на вопрос о принадлежности входной цепочки языку. В ходе распознавания выявляется структура входного текста. Эта структура может быть представлена явно, например, в виде дерева, или неявно — последовательностью действий, совершенных распознавателем.

На основе распознавания структуры входного текста строится и его содержательная обработка, трансляция. Синтаксический анализатор служит основой, остовом транслятора, предоставляя возможность выполнить необходимые действия по смысловой (семантической) обработке в нужные моменты в соответствии со структурой входной цепочки. Семантические процедуры

Встраиваемые в распознаватель действия, предназначенные для выполнения смысловой обработки входного текста, будем называть семантическими процедурами. Слово «процедура» употребляется здесь в широком смысле, как определённая последовательность действий. В программераспознавателе это может быть не обязательно процедураподпрограмма, но и просто один или несколько операторов. Рассмотрим использование семантических процедур на простом примере. Пусть речь идет о распознавателе целых чисел без знака, который был использован в программе анализаторе многочленов. Теперь в его задачу будет входить получение значения числа, представленного последовательностью цифр. Обозначив семантические процедуры P1 и P2, разместим на синтаксической диаграмме «Целое» (рис. 2.30) соответствующие им треугольные значки в тех местах, при прохождении которых во время анализа эти процедуры должны выполняться.

Рис. 2.30. Семантические процедуры на диаграмме целого без знака

Процедура P1 будет выполняться в начале обработки и присвоит искомому числу исходное нулевое значение. Переменная y — это формируемое значение числа. P1: y := 0;

Задача P2 — добавлять к числу справа очередную цифру. Для этого «старое» значение y умножим на 10 (основание десятичной системы счисления) и добавим значение прочитанной цифры. Условимся, что семантическая процедура, значок которой размещен перед обозначением терминального символа, выполняется в тот момент, когда этот символ является текущим (содержится в переменной Ch). Надо побеспокоиться и о том, чтобы при вычислениях не произошло переполнения — то есть не получилось, число, превышающее максимально допустимое целое. P2: d := ord(Ch) – ord(‘0’); if y 1 ) and ( a[i]0 ) then Write(‘^’, i) end; end;

Нам осталось реализовать транслятор (процедуру GetPoly), преобразующий введенную запись многочлена в массив коэффициентов. Его задача — считывать символы из входной строки, выполнять распознавание многочлена и вычислять его коэффициенты. Распознающие процедуры будут вложены внутрь GetPoly, а сама эта процедура лишь подготовит чтение входной строки, вызовет распознаватель и убедится, что за многочленом во входной строке ничего не содержится. < Ввод и трансляция многочлена >procedure GetPoly(var P: tPoly); const EOT = chr(0); < Конец текста >var Pos: integer;

begin Pos := 0; NextCh; Poly(P); if Ch EOT then Error(‘Ожидается конец текста’); end;

Разместим на синтаксических диаграммах значки семантических процедур и определим содержание этих процедур. Вначале на диаграмме многочлена (рис. 2.31).

Рис. 2.31. Синтаксическая диаграмма многочлена с семантическими процедурами

Перед началом обработки массив коэффициентов многочлена заполняется нулями, а его степень принимается равной нулю. Эту работу выполнит семантическая процедура P3, вызвав уже написанную нами процедуру ClearPoly. P3: ClearPoly(P);

P4 и P5 отвечают за запоминание знака перед слагаемым. Знак сохраняется в локальной переменной Op. P4: Op := Ch; P5: Op := ‘+’;

Каждое слагаемое многочлена имеет вид akxk. Транслятор слагаемого вычислит значения коэффициента a и степени k. Получив эти значения, семантическая процедура P6 в зависимости от 105

знака добавит или отнимет значение a из k-й ячейки массива коэффициентов: P6: if Op = ‘+’ then P.a[k] := P.a[k] + a else P.a[k] := P.a[k] — a;

Было бы неправильно просто записывать значение коэффициента в a[k], поскольку в записи многочлена могут быть несколько членов с одинаковой степенью x —синтаксис этого не запрещает. Складывая или вычитая каждый коэффициент с предыдущей суммой, транслятор как бы приводит подобные. Определение степени n многочлена P выполняет семантическая процедура P7. P7: P.n := nmax; while (P.n > 0) and (P.a[P.n] = 0) do P.n := P.n-1;

Теперь, пользуясь диаграммой и вставляя в текст анализатора в соответствующих местах определенные нами семантические процедуры, можно записать распознаватель многочлена. < Многочлен >procedure Poly(var P: tPoly); var a : integer; < Модуль коэффициента >k : integer; < Степень слагаемого >Op : char; < Знак операции >begin ClearPoly(P); < P3 if Ch in ['+','-'] then begin Op := Ch; < P4 NextCh; end else Op := '+'; < P5 Addend(a, k); if Op = '+' then < P6 P.a[k] := P.a[k] + a < else < P.a[k] := P.a[k] - a; < while Ch in ['+','-'] do begin Op := Ch; < P4

NextCh; Addend(a, k); if Op = ‘+’ then P.a[k] := P.a[k] + a else P.a[k] := P.a[k] — a; end; P.n := nmax; while (P.n > 0) and (P.a[P.n] = 0) do P.n := P.n-1; end;

Задача транслятора слагаемого, как уже говорилось, состоит в определении коэффициента (точнее, модуля коэффициента) a и степени k слагаемого. В соответствии с этим предусмотрим и необходимые семантические процедуры (рис. 2.32).

Рис. 2.32. Синтаксическая диаграмма слагаемого с семантическими процедурами

Процедура P8 присваивает коэффициенту a значение, равное величине целого числа, которое вычисляется транслятором целого. P8:

a := значение целого;

В программе это будет реализовано подстановкой переменной a в качестве параметра при вызове процедуры Number. Если коэффициент отсутствует, он принимается равным единице. P9:

Значение степени либо берется равным вычисленному распознавателем степени, либо нулевым, если в записи слагаемого отсутствует x. P10:

k := значение степени;

Теперь записать распознаватель-транслятор слагаемого не составляет труда. < Слагаемое >procedure Addend(var a, k : integer); begin if Ch in [‘0’..’9′] then begin Number(a); < P8 >if Ch = ‘x’ then begin NextCh; Power(k); < P10 >end else k := 0; < P11 >end else if Ch = ‘x’ then begin a := 1; < P9 >NextCh; Power(k); < P10 >end else Error(‘Ожидается число или «x»‘); end;

Реализация распознавателя нетерминала «Степень» не вызывает затруднений и выполняется по соответствующей синтаксической диаграмме, на которой обозначены семантические процедуры P11 и P12 (рис. 2.33). Чтобы защитить программу от ошибки при обращении к массиву коэффициентов, в процедуре P11 предусмотрен контроль величины показателя степени. Вычисляемая степень обозначена p.

Рис. 2.33. Синтаксическая диаграмма степени с семантическими процедурами P12:

p := значение целого; if p > nmax then Error(‘Слишком большая степень’); p := 1;

Обратите внимание, что в случае, когда семантическая процедура (P13) расположена на ветви диаграммы, где не было терминальных и нетерминальных блоков, она сама играет роль блока, что несколько меняет структуру программы-распознавателя (в нашем случае появляется ветвь else). < Степень >procedure Power(var p : integer); begin if Ch = ‘^’ then begin NextCh; Number(p); if p > nmax then Error(‘Слишком большая степень’); end else p := 1; end;

Обработка ошибок при трансляции В рассмотренных примерах обработка ошибок выполнялась с помощью процедуры Error, которая после выдачи сообщения прекращала работу всей программы. Такой способ реакции на ошибку упрощает синтаксический анализатор, но далеко не идеален. Можно рассмотреть несколько вариантов его усовершенствования: 

Завершение работы распознавателя (транслятора) после обнаружения первой ошибки без прерывания работы вызвавшей его программы. Продолжение работы распознавателя после обнаружения первой ошибки с целью обнаружения других.

Второй вариант реакции на ошибки используется во многих трансляторах языков программирования. В литературе можно найти немало рекомендаций по способам восстановления распознавателя после обнаружения ошибки с целью продолжения анализа [Грис, 1975], [Хантер, 1984], [Вирт, 1985], [Wirth, 1996], [Ахо, 2001]. Однако, общего решения задачи не существует. 109

Многое зависит от конкретного языка. Качественное восстановление, обеспечивающее выдачу осмысленных сообщений, предполагает, в том числе, использование эмпирических приемов. Рассмотрение таких подходов выходит за рамки этой книги. Любознательным читателям могу рекомендовать посмотреть названные источники или проделать собственные опыты. Обсудим и реализуем более простой первый вариант. Он совсем неплох. В условиях, когда скорость работы компьютеров неизмеримо возросла, время, необходимое для компиляции программы 10, невелико, и его потери, связанные с тем, что компилятор не сообщил программисту о нескольких ошибках сразу, исчезающе малы. Итак, необходимо организовать реакцию на ошибку таким образом, чтобы после выдачи сообщения, анализатор не останавливал всю программу, а лишь завершил свою работу, давая возможность продолжить исполнение вызвавшей его программе. Первый вариант усовершенствования состоит в том, чтобы после вызова каждой распознающей процедуры проверять успешность ее завершения и, если при анализе нетерминала обнаружена ошибка, пропускать оставшиеся части вызывающей процедуры. В этом случае процедура Error уже не прерывает программу с помощью Halt, а формирует признак ошибки, который может быть проверен в распознающих процедурах. Такой подход, однако, сильно загромоздит программы анализатора, сделает их неудобочитаемыми. Используем другое решение. Проблема при обработке ошибок состоит лишь в том, чтобы после обнаружения ошибки завершить все процедуры, цепочка вызова которых привела к процедуре, обнаружившей ошибку. Это можно сделать, если при об10

Точнее, одной единицы компиляции, например, модуля.

наружении ошибки процедура Error установит признак ошибки и прочитает текст до конца. Текущим символом станет «конец текста». Поскольку этот символ не может встретиться в анализируемом тексте, он будет отвергнут всеми частями анализатора, который завершит свою работу без прерывания программы в целом. В качестве признака ошибки разумно использовать номер ошибочного символа (обозначим ErrPos), ненулевое значение которого соответствует наличию ошибки и несет информацию о ее местоположении. Перед началом работы анализатора до первого вызова NextCh нужно выполнить ErrPos := 0. Исправленные процедуры Error и NextCh теперь выглядят так: < Ошибка >procedure Error(Message : string); < Message - сообщение >var e : integer; begin if ErrPos = 0 then begin WriteLn(‘^’: Pos); WriteLn(‘Синтаксическая ошибка: ‘, Message); e := Pos; while Ch EOT do NextCh; ErrPos := e; end; end;

Процедура Error «самоблокируется», проверяя значение ErrPos и обходя выдачу сообщений при повторных вызовах. Пользоваться ею можно так же, как и раньше, как бы считая, что после вызова Error работа анализатора прерывается. Дополнительные проверки на наличие ошибки после обращения к распознавателям нетерминалов не нужны. после обнаружения ошибки всегда возвращает «конец текста». NextCh

< Читать следующий символ >procedure NextCh; begin if ErrPos 0 then

Надо, однако, беспокоиться о том, чтобы при обнаружении ошибки не оставались неопределенными или недопустимыми данные, связанные с семантической обработкой. Они могут использоваться в вычислениях, которые будут выполняться после выдачи сообщения об ошибке при возврате из распознающих процедур. При этом не должно возникнуть недопустимых ситуаций: деление на ноль, разыменование неопределенного или равного nil указателя, выход индекса за границы массива и т. п. Например, распознаватель степени, в задачу которого входит определение величины p, при использовании нашей технологии следует записать так: < Степень >procedure Power(var p : integer); begin if Ch = ‘^’ then begin NextCh; Number(p); if p > nmax then begin Error(‘Слишком большая степень’); p := 0; end end else p := 1; end;

Требуются еще одно уточнение. Поскольку по завершении работы распознавателя, обнаружившего ошибку, текущим символом станет EOT, его проверка уже не будет достаточным условием успешного окончания анализа. Использовавшееся выше завершение: if Ch EOT then Error(‘Ожидается конец текста’) else WriteLn(‘Правильно’);

должно быть заменено следующим: if (ErrPos = 0) and (Ch = EOT) then WriteLn(‘Правильно’) else Error(‘Ожидается конец текста’);

Существует мнение, что лучшим вариантом выхода из состояния ошибки в анализаторе, работающем по алгоритму рекурсивного спуска, является использование исключений, обработка которых предусмотрена в некоторых языках программирования. Вы можете поэкспериментировать и составить свое суждение на этот счет. Табличный LL(1)-анализатор Рассматривая автоматные языки, мы использовали детерминированный конечный автомат в роли эффективного универсального распознавателя. Один из вариантов его реализации — программная интерпретация таблицы переходов автомата. На похожих принципах может быть построен и распознаватель для LL(1)-грамматик, который будет представлять собой реализацию определенного подкласса упоминавшихся выше МП-автоматов. Вначале модифицируем таблицу переходов конечного автомата. Ее обычный формат таков: Таблица 2.3. Таблица переходов конечного автомата Состояние

Все состояния пронумерованы. В колонках символов для примера записаны буквы из начала латинского алфавита. Для реальных языков количество допустимых символов может быть довольно большим. Если же рассматривать практические аспекты реализации, то придется учесть, что на вход программы, моделирующей автомат, может поступать вообще любой символ. Чтобы сократить размер таблицы, будем размещать различные символы в одном столбце. В каждом состоянии будет проверяться совпадение с единственным символом. Число состояний при этом может увеличиться. Для примера возьмем конечный автомат, распознающий целые числа без знака. Таблица 2.4, имеющая традиционный вид, задает его переходы. Таблица 2.4. Таблица переходов КА, распознающего целые без знака Состояние

K Здесь E означает состояние ошибки, а K — конечное состояние автомата. Следующая таблица 2.5 имеет модифицированный вид. Символы записываются во втором столбце, состояние в которое переходит автомат при совпадении входного символа и символа в таблице — в третьем. В четвертом столбце отмечено, возникает ли ошибка, если входной символ не совпадает с символом, записанным в таблице для данного состояния. Если в графе «Ошиб114

ка» записано «Нет», то при несовпадении символов автомат переходит в следующее по порядку состояние. Таблица 2.5. Модифицированная таблица переходов КА, распознающего целые Состояние

По причинам, которые мы вскоре выясним, состояния нового автомата пронумерованы не с 1. Переход в состояние 0, который происходит при получении автоматом, находящемся в состоянии 12, любого символа (например, символа «конец текста») означает завершение его работы с принятием (части) входной цепочки. Автомат, распознающий целые, можно попробовать применить при построении автомата, распознающего, «Степень» из примера про многочлены (см. рис. 2.33), а также многочлен в целом. Начнем с автомата, распознающего степень. Построим таблицу переходов (табл. 2.6). Пусть состояния этого автомата начинаются с 20. Таблица 2.6. Таблица переходов распознавателя степени Состояние

Потребовалось также добавить два новых столбца. Столбец «Читать» управляет чтением следующего символа: если в этом столбце стоит «Да», то при совпадении входного символа и символа, записанного во втором столбце для данного состояния, читается следующий символ входной цепочки. В предыдущей табл. 2.5 предполагалось, что при совпадении следующий символ считывается всегда. Распознавание начинается, когда автомат находится в состоянии 20. Если текущим символом является «^», автомат переходит в состояние 22, считывая следующий символ. Если первый символ не равен «^» автомат переходит в состояние 21 и принимает часть входной цепочки, за которую он отвечает — запись степени в этом случае пуста. Попав в состояние 22, автомат ожидает целое число. Распознаватель целого в нашем примере начинается с состояния 10 (нумерация не с единицы, чтоб подчеркнуть, что этот распознаватель не составляет законченный автомат, а только его часть). Поэтому в состоянии 22 запрограммирован переход в состояние 10. Но это не обычный переход, а переход с возвратом. По окончании распознавания целого должен произойти возврат из состояния 12 в состояние 23. Чтобы отметить особенность таких переходов, в таблицу введена графа «Вызов», в которой записывается «Да», если происходит переход с возвратом. Автомат, распознающий степень, как бы вызывает автомат, распознающий целое. Нетрудно догадаться, что суть происходящего подобна вызову одной подпрограммы из другой. Значение 0 в графе «Переход» следует теперь воспринимать как возврат в состояние, следующее за тем, из которого произошел вызов. Важно понимать, что при разных вызовах это может быть разное состояние. Например, вызовы целого могут выполняться распознавателем степени, а могут — распознавателем слагаемого. 116

Табличный транслятор многочленов

Пользуясь выработанным форматом таблицы переходов, заполним ее для распознавателя многочленов (который будет, как свои части, включать уже рассмотренные распознаватели целого и степени). Имея в виду, что должен выполняться не только синтаксический анализ, но и трансляция многочлена, предусмотрим в таблице графу «Процедура», в которой будем записывать номер семантической процедуры (из числа предусмотренных раньше для примера про многочлены). Эта процедура будет вызываться при совпадении входного символа и символа в таблице. Если указан нулевой номер семантической процедуры, вызов не происходит (или процедура P0 не выполняет никаких действий). Некоторые состояния добавляются в таблицу лишь для того, чтобы предусмотреть в нужные моменты выполнение необходимых семантических процедур (например, состояния 1, 6, 25). Таблица 2.7. Таблица переходов LL(1)-распознавателя многочленов Сост.