Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
40
Выше были рассмотрены теоретические вопросы, связанные с теорией формаль ных языков и грамматик. В этом разделе пойдет речь о том, как эти теоретиче ские аспекты применяются на практике при построении трансляторов.
Для начала дадим несколько определений — что же все-таки такое есть уже мно гократно упоминавшиеся трансляторы и компиляторы.
Транслятор — это программа, которая переводит входную программу на исход ном (входном) языке в эквивалентную ей выходную программу на результирую щем (выходном) языке. В этом определении слово «программа» встречается три раза, и это не ошибка и не тавтология. В работе транслятора, действительно, уча ствуют всегда три программы.
Во-первых, сам транслятор является программой — обычно он входит в состав системного программного обеспечения вычислительной системы. То есть транс лятор — это часть программного обеспечения (ПО), он представляет собой на бор машинных команд и данных и выполняется компьютером, как и все прочие программы в рамках операционной системы (ОС). Все составные части трансля тора представляют собой фрагменты или модули программы со своими входны ми и выходными данными.
Во-вторых, исходными данными для работы транслятора служит текст входной программы — некоторая последовательность предложений входного языка про граммирования. Обычно это символьный файл, но этот файл должен содержать текст программы, удовлетворяющий синтаксическим и семантическим требова ниям входного языка. Кроме того, этот файл несет в себе некоторый смысл, оп ределяемый семантикой входного языка.
В-третьих, выходными данными транслятора является текст результирующей программы. Результирующая программа строится по синтаксическим правилам, заданным в выходном языке транслятора, а ее смысл определяется семантикой выходного языка. Важным требованием в определении транслятора является эк вивалентность входной и выходной программ. Эквивалентность двух программ означает совпадение их смысла с точки зрения семантики входного языка (для исходной программы) и семантики выходного языка (для результирующей про граммы). Без выполнения этого требования сам транслятор теряет всякий прак тический смысл.
Итак, чтобы создать транслятор, необходимо прежде всего выбрать входной и выходной языки. С точки зрения преобразования предложений входного язы ка в эквивалентные им предложения выходного языка транслятор выступает как переводчик. Например, трансляция программы с языка С в язык ассемблера по сути ничем не отличается от перевода, скажем, с русского языка на английский, с той только разницей, что сложность языков несколько иная (почему не суще ствует трансляторов с естественных языков — см. раздел «Классификация язы ков и грамматик», глава 9). Поэтому и само слово «транслятор» (английское: translator) означает «переводчик».
Результатом работы транслятора будет результирующая программа, но только в том случае, если текст исходной программы является правильным — не со держит ошибок с точки зрения синтаксиса и семантики входного языка. Если исходная программа неправильная (содержит хотя бы одну ошибку), то резуль татом работы транслятора будет сообщение об ошибке (как правило, с допол нительными пояснениями и указанием места ошибки в исходной программе). В этом смысле транслятор сродни переводчику, например, с английского, кото рому подсунули неверный текст.
Кроме понятия «транслятор» широко употребляется также близкое ему по смыс лу понятие «компилятор».
Компилятор — это транслятор, который осуществляет перевод исходной програм мы в эквивалентную ей объектную программу на языке машинных команд или на языке ассемблера.
Таким образом, компилятор отличается от транслятора лишь тем, что его ре зультирующая программа всегда должна быть написана на языке машинных ко дов или на языке ассемблера. Результирующая программа транслятора, в общем случае, может быть написана на любом языке — возможен, например, транслятор программ с языка Pascal на язык С. Соответственно, всякий компилятор являет ся транслятором, но не наоборот — не всякий транслятор будет компилятором. Например, упомянутый выше транслятор с языка Pascal на С компилятором яв ляться не будет.
Само слово «компилятор» происходит от английского термина «compiler» («со ставитель», «компоновщик»). Видимо, термин обязан своему происхождению способности компиляторов составлять объектные программы на основе исход ных программ.
Результирующая программа компилятора называется «объектной программой» или «объектным кодом». Файл, в который она записана, обычно называется «объ ектным файлом». Даже в том случае, когда результирующая программа порож дается на языке машинных команд, между объектной программой (объектным файлом) и исполняемой программой (исполняемым файлом) есть существенная разница. Порожденная компилятором программа не может непосредственно выполняться на компьютере, так как она не привязана к конкретной области па мяти, где должны располагаться ее код и данные.
Компиляторы, безусловно, самый распространенный вид трансляторов (многие считают их вообще единственным видом трансляторов, хотя это не так). Они име ют самое широкое практическое применение, которым обязаны широкому рас пространению всевозможных языков программирования. Далее всегда будем говорить о компиляторах, подразумевая, что выходная программа написана на языке машинных кодов или языке ассемблера (если это не так, то это будет спе циально указываться отдельно).
Естественно, трансляторы и компиляторы, как и все прочие программы, разраба тывает человек (люди) — обычно это группа разработчиков. В принципе они могли бы создавать его непосредственно на языке машинных команд, однако объем кода и данных современных компиляторов таков, что их создание на язы ке машинных команд практически невозможно в разумные сроки при разумных трудозатратах. Поэтому практически все современные компиляторы также соз даются с помощью компиляторов (обычно в этой роли выступают предыдущие версии компиляторов той же фирмы-производителя). И в этом качестве ком пилятор является уже выходной программой для другого компилятора, которая ничем не лучше и не хуже всех прочих порождаемых выходных программ.
Кроме схожих между собой понятий «транслятор» и «компилятор» существует принципиально отличное от них понятие интерпретатора.
Интерпретатор — это программа, которая воспринимает входную программу на исходном языке и выполняет ее.
В отличие от трансляторов интерпретаторы не порождают результирующую про грамму (и вообще какого-либо результирующего кода) — и в этом принципиаль ная разница между ними. Интерпретатор, так же как и транслятор, анализирует текст исходной программы. Однако он не порождает результирующей программы, а сразу же выполняет исходную в соответствии с ее смыслом, заданным семанти кой входного языка. Таким образом, результатом работы интерпретатора будет результат, заданный смыслом исходной программы, в том случае, если эта про грамма правильная, или сообщение об ошибке, если исходная программа неверна.
Конечно, чтобы исполнить исходную программу, интерпретатор так или иначе должен преобразовать ее в язык машинных кодов, поскольку иначе выполнение программ на компьютере невозможно. Он и делает это, однако полученные ма шинные коды не являются доступными — их не видит пользователь интерпрета тора. Эти машинные коды порождаются интерпретатором, исполняются и уничтожаются по мере надобности — так, как того требует конкретная реализация интерпретатора. Пользователь же видит результат выполнения этих кодов — то есть результат выполнения исходной программы (требование об эквивалентно сти исходной программы и порожденных машинных кодов и в этом случае, без условно, должно выполняться).
Первые программы, которые создавались еще для ЭВМ первого поколения, пи сались непосредственно на языке машинных кодов. Это была поистине адская работа. Сразу стало ясно, что человек не должен и не может говорить на языке машинных команд, даже если он специалист по вычислительной технике. Одна ко и все попытки научить компьютер говорить на языках людей успехом не увенчались и вряд ли когда-либо увенчаются (на что есть определенные объек тивные причины, рассмотренные в первой главе этого пособия).
С тех пор все развитие программного обеспечения компьютеров неразрывно свя зано с возникновением и развитием компиляторов.
Первыми компиляторами были компиляторы с языков ассемблера или, как они назывались, мнемокодов. Мнемокоды превратили «филькину грамоту» языка машинных команд в более-менее доступный пониманию специалиста язык мне монических (преимущественно англоязычных) обозначений этих команд. Соз давать программы уже стало значительно проще, но исполнять сам мнемокод (язык ассемблера) ни один компьютер неспособен, соответственно, возникла не обходимость в создании компиляторов. Эти компиляторы элементарно просты, но они продолжают играть существенную роль в системах программирования по сей день. Более подробно о языке ассемблера и компиляторах с него рассказано далее в соответствующем разделе.
Следующим этапом стало создание языков высокого уровня. Языки высокого уровня (к ним относится большинство языков программирования) представля ют собой некоторое промежуточное звено между чисто формальными языками и языками естественного общения людей. От первых им досталась строгая фор мализация синтаксических структуру предложений языка, от вторых — значи тельная часть словарного запаса, семантика основных конструкций и выражений (с элементами математических операций, пришедшими из алгебры).
Появление языков высокого уровня существенно упростило процесс программи рования, хотя и не свело его до «уровня домохозяйки», как самонадеянно пола гали некоторые авторы на заре рождения языков программирования. Сначала таких языков были единицы, затем десятки, сейчас, наверное, их насчитывается более сотни. Процессу этому не видно конца. Тем не менее, по-прежнему преоб ладают компьютеры традиционной, «неймановской», архитектуры, которые уме ют понимать только машинные команды, поэтому вопрос о создании компилято ров продолжает быть актуальным.
Как только возникла массовая потребность в создании компиляторов, стала раз виваться и специализированная теория. Со временем она нашла практическое приложение во множестве созданных компиляторов. Компиляторы создавались и продолжают создаваться не только для новых, но и для давно известных язы ков. Многие производители от известных, солидных фирм (таких, как Microsoft или Inprise) до мало кому знакомых коллективов авторов выпускают на рынок все новые и новые образцы компиляторов. Это обусловлено рядом причин, кото рые будут рассмотрены далее.
Наконец, с тех пор как большинство теоретических аспектов в области ком пиляторов получили свою практическую реализацию (а это, надо сказать, про изошло довольно быстро, в конце 60-х годов), развитие компиляторов пошло по пути их дружественности человеку — пользователю, разработчику программ на языках высокого уровня. Логичным завершением этого процесса стало создание систем программирования — программных комплексов, объединяющих в себе кроме непосредственно компиляторов множество связанных с ними компонен тов программного обеспечения. Появившись, системы программирования быстро завоевали рынок и ныне в массе своей преобладают на нем (фактически, обособ ленные компиляторы — это редкость среди современных программных средств).
Ныне компиляторы являются неотъемлемой частью любой вычислительной сис темы. Без их существования программирование любой прикладной задачи было бы затруднено, а то и просто невозможно. Да и программирование специали зированных системных задач, как правило, ведется если не на языке высокого уровня (в этой роли в настоящее время чаще всего применяется язык С), то на языке ассемблера, следовательно, применяется соответствующий компилятор. Программирование непосредственно на языках машинных кодов происходит ис ключительно редко и только для решения очень узких вопросов.
Несколько слов о примерах реализации компиляторов и интерпретаторов, а также о том, как они соотносятся с другими существующими программными средствами.
Компиляторы, как будет показано далее, обычно несколько проще в реализации, чем интерпретаторы. По эффективности они также превосходят их — очевидно, что откомпилированный код будет исполняться всегда быстрее, чем происходит интерпретация аналогичной исходной программы. Кроме того, не каждый язык программирования допускает построение простого интерпретатора. Однако ин терпретаторы имеют одно существенное преимущество — откомпилированный код всегда привязан к архитектуре вычислительной системы, на которую он ори ентирован, а исходная программа — только к семантике языка программирова ния, которая гораздо легче поддается стандартизации. Этот аспект первоначаль но не принимали во внимание.
Первыми компиляторами были компиляторы с мнемокодов. Их потомки — со временные компиляторы с языков ассемблера — существуют практически для всех известных вычислительных систем. Они предельно жестко ориентированы на архитектуру. Затем появились компиляторы с таких языков, как FORTRAN, ALGOL-68, PL/I. Они были ориентированы на большие ЭВМ с пакетной обра боткой задач. Из вышеперечисленных только FORTRAN, пожалуй, продолжает использоваться по сей день, поскольку имеет огромное количество библиотек различного назначения. Многие языки, родившись, так и не получили широ кого распространения — ADA, Modula, Simula известны лишь узкому кругу спе циалистов. В то же время на рынке программных систем доминируют компиля торы языков, которым не прочили светлого будущего. В первую очередь, сейчас это С и C++. Первый из них родился вместе с операционными системами типа UNIX, вместе с нею завоевал свое «место под солнцем», а затем перешел под ОС других типов. Второй удачно воплотил в себе пример реализации идей объектно-ориентированного программирования на хорошо зарекомендовавшей себя практической базе. Еще можно упомянуть довольно распространенный Pascal, который неожиданно для многих вышел за рамки чисто учебного языка для универ ситетской среды.
История интерпретаторов не столь богата (пока!). Как уже было сказано, изна чально им не предавали существенного значения, поскольку почти по всем пара метрам они уступают компиляторам. Из известных языков, предполагавших интерпретацию, можно упомянуть разве что Basic, хотя большинству сейчас из вестна его компилируемая реализация Visual Basic, сделанная фирмой Microsoft . Тем не менее сейчас ситуация несколько изменилась, поскольку вопрос о переносимости программ и их аппаратно-платформенной независимости приоб ретает все большую актуальность с развитием сети Интернет. Самый известный сейчас пример — это язык Java (сам по себе он сочетает компиляцию и интерпре тацию), а также связанный с ним JavaScript. В конце концов, язык HTML, на ко тором зиждется протокол HTTP, давший толчок столь бурному развитию Все мирной сети, — это тоже интерпретируемый язык. Но появляются и новые интерпретаторы — например, язык С# («си-диез», но название везде идет как «Си шарп»), анонсируемый фирмой Microsoft.
На рис. 13.1 представлена общая схема работы компилятора. Из нее видно, что в целом процесс компиляции состоит из двух основных этапов — синтеза и анализа.
На этапе анализа выполняется распознавание текста исходной программы, соз дание и заполнение таблиц идентификаторов. Результатом его работы служит некое внутреннее представление программы, понятное компилятору.
На этапе синтеза на основании внутреннего представления программы и инфор мации, содержащейся в таблице (таблицах) идентификаторов, порождается текст результирующей программы. Результатом этого этапа является объектный код.
Кроме того, в составе компилятора присутствует часть, ответственная за анализ и исправление ошибок, которая при наличии ошибки в тексте исходной про граммы должна максимально полно информировать пользователя о типе ошиб ки и месте ее возникновения. В лучшем случае компилятор может предложить пользователю вариант исправления ошибки.
Эти этапы, в свою очередь, состоят из более мелких этапов, называемых фазами компиляции. Состав фаз компиляции приведен в самом общем виде, их конкрет ная реализация и процесс взаимодействия могут, конечно, различаться в зави симости от версии компилятора. Однако в том или ином виде все представлен ные фазы практически всегда присутствуют в каждом конкретном компиляторе.
Компилятор в целом с точки зрения теории формальных языков выступает в «двух ипостасях», выполняет две основные функции.
Во-первых, он является распознавателем для языка исходной программы. То есть он должен получить на вход цепочку символов входного языка, проверить ее принадлежность языку и, более того, выявить правила, по которым эта цепочка была построена (поскольку сам ответ на вопрос о принадлежности «да» или «нет» представляет мало интереса). Интересно, что генератором цепочек входно го языка выступает пользователь — автор входной программы.
Во-вторых, компилятор является генератором для языка результирующей про граммы. Он должен построить на выходе цепочку выходного языка по опреде ленным правилам, предполагаемым языком машинных команд или языком ас семблера. Распознавателем этой цепочки будет выступать уже вычислительная система, под которую создается результирующая программа.
Далее дается перечень основных фаз (частей) компиляции и краткое описание их функций. Более подробная информация дана в подразделах, соответствую щих этим фазам.
Рис. 13.1. Общая схема работы компилятора
Лексический анализ (сканер) — это часть компилятора, которая читает литеры программы на исходном языке и строит из них слова (лексемы) исходного язы ка. На вход лексического анализатора поступает текст исходной программы, а выходная информация передается для дальнейшей обработки компилятором на этапе синтаксического разбора. С теоретической точки зрения лексический анализатор не является обязательной, необходимой частью компилятора. Одна ко существует причины, которые определяют его присутствие практически во всех компиляторах.
Синтаксический разбор — это основная часть компилятора на этапе анализа. Она выполняет выделение синтаксических конструкций в тексте исходной програм мы, обработанном лексическим анализатором. На этой же фазе компиляции проверяется синтаксическая правильность программы. Синтаксический разбор играет главную роль — роль распознавателя текста входного языка программи рования.
Семантический анализ — это часть компилятора, проверяющая правильность текста исходной программы с точки зрения семантики входного языка. Кроме непосредственно проверки, семантический анализ должен выполнять преобра зования текста, требуемые семантикой входного языка (такие, как добавление функций неявного преобразования типов). В различных реализациях компиля торов семантический анализ может частично входить в фазу синтаксического разбора, частично — в фазу подготовки к генерации кода.
Подготовка к генерации кода — это фаза, на которой компилятором выполняют ся предварительные действия, непосредственно связанные с синтезом текста ре зультирующей программы, но еще не ведущие к порождению текста на выход ном языке. Обычно в эту фазу входят действия, связанные с идентификацией элементов языка, распределением памяти и т. п.
Генерация кода — это фаза, непосредственно связанная с порождением команд, составляющих предложения выходного языка и в целом текст результирующей программы. Это основная фаза на этапе синтеза результирующей программы. Кроме непосредственного порождения текста результирующей программы, гене рация обычно включает в себя также оптимизацию — процесс, связанный с обра боткой уже порожденного текста. Иногда оптимизацию выделяют в отдельную фазу компиляции, так как она оказывает существенное влияние на качество и эффективность результирующей программы.
Таблицы идентификаторов (иногда — «таблицы символов») — это специальным образом организованные наборы данных, служащие для хранения информации об элементах исходной программы, которые затем используются для порожде ния текста результирующей программы. Таблица идентификаторов в конкрет ной реализации компилятора может быть одна, или же таких таблиц может быть несколько. Элементами исходной программы, информацию о которых нужно хра нить в процессе компиляции, являются переменные, константы, функции и т. п. — конкретный состав набора элементов зависит от используемого входного языка программирования. Понятие «таблицы» вовсе не предполагает, что это хранилище данных должно быть организовано именно в виде таблиц или других массивов информации — возможны и другие методы их организации.
Представленное на рис. 13.1 деление процесса компиляции на фазы служит ско рее методическим целям и на практике может не соблюдаться столь строго. Но фазы компиляции могут быть связаны между собой. Рассмотрим только общие аспекты тако го рода взаимосвязи.
Во-первых, на фазе лексического анализа лексемы выделяются из текста вход ной программы постольку, поскольку они необходимы для следующей фазы син таксического разбора. Во-вторых, как будет показано ниже, синтаксический раз бор и генерация кода могут выполняться одновременно. Таким образом, эти три фазы компиляции могут работать комбинированно, а вместе с ними может вы полняться и подготовка к генерации кода. Далее рассмотрены технические во просы реализации основных фаз компиляции, которые тесно связаны с поняти ем прохода.
Как уже было сказано, процесс компиляции программ состоит из нескольких фаз. В реальных компиляторах состав этих фаз может несколько отличаться от рас смотренного выше — некоторые из них могут быть разбиты на составляющие, другие, напротив, объединены в одну фазу. Порядок выполнения фаз компиля ции также может меняться в разных вариантах компиляторов. В одном случае компилятор просматривает текст исходной программы, сразу выполняет все фазы компиляции и получает результат — объектный код. В другом варианте он вы полняет над исходным текстом только некоторые из фаз компиляции и получает не конечный результат, а набор некоторых промежуточных данных. Эти данные затем снова подвергаются обработке, причем этот процесс может повторяться несколько раз.
Реальные компиляторы, как правило, выполняют трансляцию текста исходной программы за несколько проходов.
Проход — это процесс последовательного чтения компилятором данных из внеш ней памяти, их обработки и помещения результата работы во внешнюю память. Чаще всего один проход включает в себя выполнение одной или нескольких фаз компиляции. Результатом промежуточных проходов является внутреннее пред ставление исходной программы, результатом последнего прохода — результи рующая объектная программа.
В качестве внешней памяти могут выступать любые носители информации — оперативная память компьютера, различные накопители (p.ex., на магнитных дисках). Современные компиляторы, как правило, стремятся максимально использовать для хранения данных оперативную память компьютера, и только при недостатке объема доступной памяти используются накопители на жестких магнитных дисках. Другие носители информации в современных компиляторах не используются из-за невысокой скорости обмена данными.
При выполнении каждого прохода компилятору доступна информация, полу ченная в результате всех предыдущих проходов. Как правило, он стремится ис пользовать в первую очередь только информацию, полученную на проходе, не посредственно предшествовавшем текущему, но в принципе может обращаться и к данным от более ранних проходов вплоть до исходного текста программы. Информация, получаемая компилятором при выполнении проходов, недоступна пользователю. Она либо хранится в оперативной памяти, которая освобождает ся компилятором после завершения процесса трансляции, либо оформляется в виде временных файлов на диске, которые также уничтожаются после завер шения работы компилятора. Поэтому человек, работающий с компилятором, мо жет даже не знать, сколько проходов выполняет компилятор — он всегда видит только текст исходной программы и результирующую объектную программу. Но количество выполняемых проходов — это важная техническая характеристика компилятора, солидные фирмы — разработчики компиляторов обычно указыва ют ее в описании своего продукта.
Понятно, что разработчики стремятся максимально сократить количество про ходов, выполняемых компиляторами. При этом увеличивается скорость работы компилятора, сокращается объем необходимой ему памяти. Однопроходный ком пилятор, получающий на вход исходную программу и сразу же порождающий результирующую объектную программу, — это идеальный вариант.
Однако сократить число проходов не всегда удается. Количество необходимых проходов определяется прежде всего грамматикой и семантическими правилами исходного языка. Чем сложнее грамматика языка и чем больше вариантов пред полагают семантические правила — тем больше проходов будет выполнять ком пилятор (конечно, играет свою роль и квалификация разработчиков компилято ра). Например, именно поэтому обычно компиляторы с языка Pascal работают быстрее, чем компиляторы с языка С — грамматика языка Pascal более проста, а семантические правила более жесткие.
Однопроходные компиляторы — редкость, они возможны только для очень про стых языков. Реальные компиляторы выполняют, как правило, от двух до пяти проходов. Таким образом, реальные компиляторы являются многопроходными. Наиболее распространены двух- и трехпроходные компиляторы, например: пер вый проход — лексический анализ, второй — синтаксический разбор и семанти ческий анализ, третий — генерация и оптимизация кода (варианты исполнения, конечно, зависят от разработчика). В современных системах программирования нередко первый проход компилятора (лексический анализ кода) выполняется параллельно с редактированием кода исходной программы.
Интерпретатор — это программа, которая воспринимает входную программу на исходном языке и выполняет ее. Как уже было сказано выше, основное отличие интерпретаторов от трансляторов и компиляторов заключается в том, что интер претатор не порождает результирующую программу, а просто выполняет исход ную программу.
Термин «интерпретатор» (interpreter), как и «транслятор», означает «перевод чик». С точки зрения терминологии эти понятия схожи, но с точки зрения тео рии формальных языков и компиляции между ними большая принципиальная разница. Если понятия «транслятор» и «компилятор» почти неразличимы, то с понятием «интерпретатор» их путать никак нельзя.
Простейшим способом реализации интерпретатора можно было бы считать ва риант, когда исходная программа сначала полностью транслируется в машинные команды, а затем сразу же выполняется. В такой реализации интерпретатор, по сути, мало бы чем отличался от компилятора с той лишь разницей, что результи рующая программа в нем была бы недоступна пользователю. Недостатком тако го интерпретатора было бы то, что пользователь должен был бы ждать компиля ции всей исходной программы прежде, чем начнется ее выполнение. По сути, в таком интерпретаторе не было бы никакого особого смысла — он не давал бы никаких преимуществ по сравнению с аналогичным компилятором.
Поэтому подавляющее большинство интерпретаторов действует так, что испол няет исходную программу последовательно, по мере ее поступления на вход ин терпретатора. Тогда пользователю не надо ждать завершения компиляции всей исходной программы. Более того, он может последовательно вводить исходную программу и тут же наблюдать результат ее выполнения по мере ввода команд.
При таком порядке работы интерпретатора проявляется существенная особен ность, которая отличает его от компилятора, — если интерпретатор исполняет команды по мере их поступления, то он не может выполнять оптимизацию ис ходной программы. Следовательно, фаза оптимизации в общей структуре интерпретатора будет отсутствовать. В остальном же она будет мало отличаться от структуры аналогичного компилятора. Следует только учесть, что на последнем этапе — генерации кода — машинные команды не записываются в объектный файл, а выполняются по мере их порождения.
Отсутствие шага оптимизации определяет еще одну особенность, характерную для многих интерпретаторов: в качестве внутреннего представления программы в них очень часто используется обратная польская запись. Эта удобная форма представления операций обладает только одним существенным недостатком — она плохо подда ется оптимизации. Но в интерпретаторах именно это как раз и не требуется.
В обратной польской записи знаки выражений записываются непосредственно за операндами. Операнды следуют в том же порядке, а знаки операций – строго в порядке их выполнения. Здесь не требуется учитывать приоритет операций. Скобки не употребляются. Обратная польская запись эффективна, когда используется стек. Например,
6+7*(10+4)=104 ---- 6 7 10 4 + * +
6+(7+10)*4=74 ------ 6 7 10 + 4 * +
Далеко не все языки программирования допускают построение интерпретаторов, которые могли бы выполнять исходную программу по мере поступления команд. Для этого язык должен допускать возможность существования компилятора, выполняющего разбор исходной программы за один проход. Кроме того, язык не может интерпретироваться по мере поступления команд, если он допускает по явление обращений к функциям и структурам данных раньше их непосредствен ного описания. Поэтому данным методом не могут интерпретироваться такие языки, как С и Pascal.
Отсутствие шага оптимизации ведет к тому, что выполнение программы с помо щью интерпретатора является менее эффективным, чем с помощью аналогично го компилятора. Кроме того, при интерпретации исходная программа должна за ново разбираться всякий раз при ее выполнении, в то время как при компиляции она разбирается только один раз, а после этого всегда используется объектный файл. Таким образом, интерпретаторы всегда проигрывают компиляторам в про изводительности.
Преимуществом интерпретатора является независимость выполнения програм мы от архитектуры целевой вычислительной системы. В результате компиляции получается объектный код, который всегда ориентирован на определенную архи тектуру. Для перехода на другую архитектуру целевой вычислительной системы программу требуется откомпилировать заново. А для интерпретации программы необходимо иметь только ее исходный текст и интерпретатор с соответствующе го языка.
Интерпретаторы долгое время значительно уступали в распространенности ком пиляторам. Как правило, интерпретаторы существовали для ограниченного кру га относительно простых языков программирования (таких, например, как Basic). Высокопроизводительные профессиональные средства разработки программно го обеспечения строились на основе компиляторов.
Новый импульс развитию интерпретаторов придало распространение глобаль ных вычислительных сетей. Такие сети могут включать в свой состав ЭВМ раз личной архитектуры, и тогда требование единообразного выполнения на каждой из них текста исходной программы становится определяющим. Поэтому с разви тием глобальных сетей и распространением всемирной сети Интернет появилось много новых систем, интерпретирующих текст исходной программы. Многие языки программирования, применяемые во Всемирной сети, предполагают имен но интерпретацию текста исходной программы без порождения объектного кода.
В современных системах программирования существуют реализации программ ного обеспечения, сочетающие в себе и функции компилятора, и функции интер претатора — в зависимости от требований пользователя исходная программа либо компилируется, либо исполняется (интерпретируется). Кроме того, некото рые современные языки программирования предполагают две стадии разработ ки: сначала исходная программа компилируется в промежуточный код (некото рый язык низкого уровня), а затем этот результат компиляции выполняется с помощью интерпретатора данного промежуточного языка. Более подробно вари анты таких систем рассмотрены в главе «Современные системы программирова ния».
Широко распространенным примером интерпретируемого языка может служить HTML (Hypertext Markup Language) — язык описания гипертекста. На его осно ве в настоящее время функционирует практически вся структура сети Интернет. Другой пример — языки Java и JavaScript — сочетают в себе функции компиля ции и интерпретации. Текст исходной программы компилируется в некоторый промежуточный двоичный код, не зависящий от архитектуры целевой вычисли тельной системы, этот код распространяется по сети и выполняется на прини мающей стороне — интерпретируется.
Проверка правильности семантики и генерация кода требуют знания характери стик переменных, констант, функций и других элементов, встречающихся в про грамме на исходном языке. Все эти элементы в исходной программе, как пра вило, обозначаются идентификаторами. Выделение идентификаторов и других элементов исходной программы происходит на фазе лексического анализа. Их характеристики определяются на фазах синтаксического разбора, семантическо го анализа и подготовки к генерации кода. Состав возможных характеристик и методы их определения зависят от семантики входного языка.
В любом случае компилятор должен иметь возможность хранить все найденные идентификаторы и связанные с ними характеристики в течение всего процесса компиляции, чтобы иметь возможность использовать их на различных фазах компиляции. Для этой цели, как было сказано выше, в компиляторах использу ются специальные хранилища данных, называемые таблицами символов или таблицами идентификаторов.
Любая таблица идентификаторов состоит из набора полей, количество которых равно числу различных идентификаторов, найденных в исходной программе. Каждое поле содержит в себе полную информацию о данном элементе таблицы. Компилятор может работать с одной или несколькими таблицам идентификато ров — их количество зависит от реализации компилятора. Например, можно ор ганизовывать различные таблицы идентификаторов для различных модулей ис ходной программы или для различных типов элементов входного языка.
Состав информации, хранимой в таблице идентификаторов для каждого элемен та исходной программы, зависит от семантики входного языка и типа элемента. Например, в таблицах идентификаторов может храниться следующая информация:
Приведенный выше состав хранимой информации, конечно же, является только примерным. Конкрет ное наполнение таблиц идентификаторов зависит от реализации компилятора. Кроме того, не вся информация, хранимая в таблице идентификаторов, заполняется компилятором сразу — он может несколько раз выполнять обращение к данным в таблице идентификаторов на различных фазах компиляции. Например, имена переменных могут быть выделены на фазе лексического анализа, типы данных для переменных — на фазе синтаксического разбора, а область памяти связыва ется с переменной только на фазе подготовки к генерации кода.
Вне зависимости от реализации компилятора принцип его работы с таблицей идентификаторов остается одним и тем же — на различных фазах компиляции компилятор вынужден многократно обращаться к таблице для поиска информа ции и записи новых данных. Как правило, каждый элемент в исходной програм ме однозначно идентифицируется своим именем. Поэтому компилятору приходится часто выполнять поиск необходимого элемента в таблице идентификаторов по его имени, в то время как процесс заполнения таблицы выполняется нечасто — новые идентификаторы описываются в программе гораздо реже, чем используются. Отсюда можно сде лать вывод, что таблицы идентификаторов должны быть организованы таким об разом, чтобы компилятор имел возможность максимально быстрого поиска нуж ного ему элемента.
Простейший способ организации таблицы состоит в том, чтобы добавлять эле менты в порядке их поступления. Тогда таблица идентификаторов будет пред ставлять собой неупорядоченный массив информации, каждая ячейка которого будет содержать данные о соответствующем элементе таблицы.
Поиск нужного элемента в таблице будет в этом случае заключаться в последо вательном сравнении искомого элемента с каждым элементом таблицы, пока не будет найден подходящий. Тогда, если за единицу принять время, затрачиваемое компилятором на сравнение двух элементов (как правило, это сравнение двух строк), то для таблицы, содержащей N элементов, в среднем будет выполнено N/2 сравнений.
Заполнение такой таблицы будет происходить элементарно просто — добавлени ем нового элемента в ее конец, и время, требуемое на добавление элемента (Тз), не будет зависеть от числа элементов в таблице N. Но если N велико, то поиск потребует значительных затрат времени. Время поиска (Тп) в такой таблице можно оценить как Тп = О(N). Поскольку поиск в таблице идентификаторов является чаще всего выполняемой компилятором операцией, а количество раз личных идентификаторов даже в реальной исходной программе достаточно ве лико (от нескольких сотен до нескольких тысяч элементов), то такой способ организации таблиц идентификаторов является неэффективным.
Поиск может быть выполнен более эффективно, если элементы таблицы упоря дочены (отсортированы) согласно некоторому естественному порядку.
В нашем случае, когда поиск будет осуществляться по имени идентификатора, наиболее естественно расположить элементы таблицы в прямом или обратном алфавитном порядке. Эффективным методом поиска в упорядоченном списке из N элементов является бинарный или логарифмический поиск. Символ, который следует найти, сравнивается с элементом (N+1)/2 в середине таблицы. Если этот элемент не является искомым, то мы должны просмотреть только блок элемен тов, пронумерованных от 1 до (N+1)/2-1, или блок элементов от (N+1)/2+1 до N в зависимости от того, меньше или больше искомый элемент того, с кото рым его сравнили. Затем процесс повторяется над нужным блоком в два раза меньшего размера. Так продолжается до тех пор, пока либо элемент не будет найден, либо алгоритм не дойдет до очередного блока, содержащего один или два элемента (с которыми уже можно выполнить прямое сравнение искомого элемента).
Так как на каждом шаге число элементов, которые могут содержать искомый эле мент, сокращается наполовину, то максимальное число сравнений равно l+log2(N).
Тогда время поиска элемента в таблице идентификаторов можно оценить как Т = О(log2 N). Метод называют «бинарным поиском», поскольку на каждом шаге объем рас сматриваемой информации сокращается в два раза, а «логарифмическим» — по скольку время, затрачиваемое на поиск нужного элемента в массиве, имеет лога рифмическую зависимость от общего количества элементов в нем.
Недостатком метода является требование упорядочивания таблицы идентифи каторов. Так как массив информации, в котором выполняется поиск, должен быть упорядочен, то время его заполнения уже будет зависеть от числа элемен тов в массиве. Таблица идентификаторов зачастую просматривается еще до того, как она заполнена полностью, поэтому требуется, чтобы условие упорядоченно сти выполнялось на всех этапах обращения к ней. Следовательно, для построе ния таблицы можно пользоваться только алгоритмом прямого упорядоченного включения элементов.
При добавлении каждого нового элемента в таблицу сначала надо определить место, куда поместить новый элемент, а потом выполнить перенос части инфор мации в таблице, если элемент добавляется не в ее конец. Если пользоваться стандартными алгоритмами, применяемыми для организации упорядоченных массивов данных, а поиск места включения вести с помощью алгоритма би нарного поиска, то среднее время, необходимое на помещение всех элементов в таблицу, можно оценить следующим образом:
Тз = О(N*log2 N) + k*О(N2).
Здесь k - некоторый коэффициент, отражающий соотношение между времена ми, затрачиваемыми компьютером на выполнение операции сравнения и опера ции переноса данных.
В итоге при организации логарифмического поиска в таблице идентификаторов мы добиваемся существенного сокращения времени поиска нужного элемента за счет увеличения времени на помещение нового элемента в таблицу. Посколь ку добавление новых элементов в таблицу идентификаторов происходит сущест венно реже, чем обращение к ним, то этот метод следует признать более эффек тивным, чем метод организации неупорядоченной таблицы.
Логарифмическая зависимость времени поиска и времени заполнения таблицы идентификаторов — это самый хороший результат, которого можно достичь за счет применения различных методов организации таблиц. Однако в реальных исходных программах количество идентификаторов столь велико, что даже лога рифмическую зависимость времени поиска от их числа нельзя признать удов летворительной. Необходимы более эффективные методы поиска информации в таблице идентификаторов.
Лучших результатов можно достичь, если применить методы, связанные с использованием хэш-функций и хеш-адресации.
Хэш-функцией F называется некоторое отображение множества входных элемен тов R на множество целых неотрицательных чисел Z: F(r) = n, r R, n Z. Сам термин «хэш-функция» происходит от английского термина «hash function» (hash — «мешать», «смешивать», «путать»). Вместо термина «хеширование» ино гда используются термины «рандомизация», «переупорядочивание».
Множество допустимых входных элементов R называется областью определе ния хэш-функции. Множеством значений хэш-функций F называется подмно жество М из множества целых неотрицательных чисел Z: MZ, содержащее все возможные значения, возвращаемые функцией F: rR: F(r) M. Процесс ото бражения области определения хэш-функции на множество значений называет ся «хешированием».
При работе с таблицей идентификаторов хэш-функция должна выполнять ото бражение имен идентификаторов на множество целых неотрицательных чисел.
Областью определения хэш-функции будет множество всех возможных имен идентификаторов.
Хеш-адресация заключается в использовании значения, возвращаемого хэш-функцией, в качестве адреса ячейки из некоторого массива данных. Тогда размер массива данных должен соответствовать области значений используемой хэш-функции. Следовательно, в реальном компиляторе область значений хэш-функ ции никак не должна превышать размер доступного адресного пространства компьютера.
Метод организации таблиц идентификаторов, основанный на использовании хеш-адресации, заключается в размещении каждого элемента таблицы в ячейке, адрес которой возвращает хэш-функция, вычисленная для этого элемента. Тогда в иде альном случае для размещения любого элемента в таблице идентификаторов достаточно только вычислить его хэш-функцию и обратиться к нужной ячейке массива данных. Для поиска элемента в таблице необходимо вычислить хэш-функцию для искомого элемента и проверить, не является ли заданная ею ячей ка массива пустой (если она не пуста — элемент найден, если пуста — не най ден).
На рис. 13.3 проиллюстрирован метод организации таблиц идентификаторов с использованием хеш-адресации. Трем различным идентификаторам А1, А2, А3 со ответствуют на рисунке три значения хэш-функции n1, n2, n3. В ячейки, адресуе мые n1, n2, n3, помещается информация об идентификаторах А1, А2, А3. При поис ке идентификатора А3 вычисляется значение адреса n3 и выбираются данные из соответствующей ячейки таблицы.
Рис. 13.3. Организация таблицы идентификаторов с использованием хеш-адресации
Этот метод весьма эффективен — как время размещения элемента в таблице, так и время его поиска определяются только временем, затрачиваемым на вычисле ние хэш-функции, которое в общем случае несопоставимо меньше времени, не обходимого на многократные сравнения элементов таблицы.
Метод имеет два очевидных недостатка. Первый из них — неэффективное ис пользование объема памяти под таблицу идентификаторов: размер массива для ее хранения должен соответствовать области значений хэш-функции, в то вре мя как реально хранимых в таблице идентификаторов может быть существенно меньше. Второй недостаток — необходимость соответствующего разумного вы бора хэш-функции. Этому существенному вопросу посвящены следующие два подраздела.
Существуют различные варианты хэш-функции. Получение результата хэш-функции — «хеширование» — обычно достигается за счет выполнения над це почкой символов некоторых простых арифметических и логических операций. Самой простой хэш-функцией для символа является код внутреннего представ ления в ЭВМ литеры символа. Эту хэш-функцию можно использовать и для це почки символов, выбирая первый символ в цепочке. Так, если двоичное ASCII представление символа А есть 00100001, то результатом хэширования идентифи катора ATable будет код 00100001.
Хэш-функция, предложенная выше, очевидно не удовлетворительна: при ис пользовании такой хэш-функции возникнет новая проблема — двум различным идентификаторам, начинающимся с одной и той же буквы, будет соответство вать одно и то же значение хэш-функции. Тогда при хэш-адресации в одну ячей ку таблицы идентификаторов по одному и тому же адресу должны быть помеще ны два различных идентификатора, что явно невозможно. Такая ситуация, когда двум или более идентификаторам соответствует одно и то же значение функции, называется коллизией. Возникновение коллизии проиллюстрировано на рис. 13.4 — двум различным идентификаторам А1 и А2 соответствуют два совпадающих зна чения хэш-функции n1 = n2.
Естественно, что хэш-функция, допускающая коллизии, не может быть напря мую использована для хеш-адресации в таблице идентификаторов. Причем дос таточно получить хотя бы один случай коллизии на всем множестве идентифи каторов, чтобы такой хэш-функцией нельзя было пользоваться непосредственно. Но в примере взята самая элементарная хэш-функция. А возможно ли построить нетривиальную хэш-функцию, которая бы полностью исключала возникновение коллизий?
Рис. 13.4. Возникновение коллизии при использовании хеш-адресации
Очевидно, что для полного исключения коллизий хэш-функция должна быть взаимно однозначной: каждому элементу из области определения хэш-функции должно соответствовать одно значение из ее множества значений, но и каждому значению из множества значений этой функции должен соответствовать только один элемент из области ее определения. Тогда любым двум произвольным эле ментам из области определения хэш-функции будут всегда соответствовать два различных ее значения. Теоретически для идентификаторов такую хэш-функ цию построить можно, так как и область определения хэш-функции (все воз можные имена идентификаторов), и область ее значений (целые неотрицатель ные числа) являются бесконечными счетными множествами. Теоретически мож но организовать взаимно однозначное отображение одного счетного множества на другое, но практически это сделать исключительно сложно.
Практически существует ограничение, делающее создание взаимно однозначной хэш-функции для идентификаторов невозможным. Дело в том, что в реальности область значений любой хэш-функции ограничена размером доступного адрес ного пространства в данной архитектуре компьютера. При организации хеш-адресации значение, используемое в качестве адреса таблицы идентификаторов, не может выходить за пределы, заданные адресной сеткой компьютера2. Множество адресов любого компьютера с традиционной архитектурой может быть велико, но всегда конечно, то есть ограничено. Организовать взаимно однозначное ото бражение бесконечного множества на конечное даже теоретически невозможно. Можно учесть, что длина принимаемой во внимание строки идентификатора в реальных компиляторах также практически ограничена — обычно она лежит в пределах от 32 до 128 символов (то есть и область определения хэш-функции конечна). Но и тогда количество элементов в конечном множестве, составляю щем область определения функции, будет превышать их количество в конечном множестве области значений функции (количество всех возможных идентифи каторов все равно больше количества допустимых адресов в современных ком пьютерах). Таким образом, создать взаимно однозначную хэш-функцию практически ни в каком варианте невозможно. Следовательно, невозможно избежать возникновения коллизий.
Пока для двух различных элементов результаты хэширования различны, время поиска совпадает со временем, затраченным на хеширование. Однако возникает затруднение, когда результаты хеширования двух разных элементов совпадают.
Для решения проблемы коллизии можно использовать много способов. Одним из них является метод «рехеширования» (или «расстановки»). Согласно этому методу, если для элемента А адрес h(A), вычисленный с помощью хэш-функции, указывает на уже занятую ячейку, то необходимо вычислить значение функции n1 = h1(A) и проверить занятость ячейки по адресу n1. Если и она занята, то вы числяется значение h2(A), и так до тех пор, пока либо не будет найдена свободная ячейка, либо очередное значение hi(A) совпадет с h(A). В последнем случае считается, что таблица идентификаторов заполнена и места в ней больше нет — выдается информация об ошибке размещения идентификатора в таблице. Особенностью метода является то, что первоначально таблица идентификаторов должна быть заполнена информацией, которая позволила бы говорить о том, что все ее ячейки являются пустыми (не содержат данных). Например, если исполь зуются указатели для хранения имен идентификаторов, то таблицу надо предва рительно заполнить пустыми указателями.
Такую таблицу идентификаторов можно организовать по следующему алгорит му размещения элемента.
Шаг 1. Вычислить значение хэш-функции n = h(A) для нового элемента А.
Шаг 2. Если ячейка по адресу n пустая, то поместить в нее элемент А и завер шить алгоритм, иначе i:=l и перейти к шагу 3.
Шаг 3. Вычислить ni = hi(A). Если ячейка по адресу ni пустая, то поместить в нее элемент А и завершить алгоритм, иначе перейти к шагу 4.
Шаг 4. Если n = ni , то сообщить об ошибке и завершить алгоритм, иначе i:=i+l и вернуться к шагу 3.
Тогда поиск элемента А в таблице идентификаторов, организованной таким об разом, будет выполняться по следующему алгоритму.
Шаг 1. Вычислить значение хэш-функции n = h(А) для нового элемента А.
Шаг 2. Если ячейка по адресу n пустая, то элемент не найден, алгоритм завер шен, иначе сравнить имя элемента в ячейке n с именем искомого элемента А. Если они совпадают, то элемент найден и алгоритм завершен, иначе i:=l и перей ти к шагу 3.
Шаг 3. Вычислить ni = hi(A). Если ячейка по адресу n, пустая или n = ni , то эле мент не найден и алгоритм завершен, иначе сравнить имя элемента в ячейке ni с именем искомого элемента А. Если они совпадают, то элемент найден и алго ритм завершен, иначе i:=i+l и повторить к шаг 3.
Алгоритмы размещения и поиска элемента схожи по выполняемым операциям. Поэтому они будут совпадать и по оценкам времени, необходимого для их вы полнения.
При такой организации таблиц идентификаторов в случае возникновения кол лизии алгоритм размещает элементы в пустых ячейках таблицы, выбирая их оп ределенным образом. При этом элементы могут попадать в ячейки с адресами, которые потом будут совпадать со значениями хэш-функции, что приведет к воз никновению новых, дополнительных коллизий. Таким образом, количество опе раций, необходимых для поиска или размещения в таблице элемента, зависит от заполненности таблицы. Естественно, функции hi(A) должны вычисляться еди нообразно на этапах размещения и поиска элемента. Вопрос только в том, как организовать вычисление функций hi(A).
Самым простым методом вычисления функции hi(А) является ее организация в виде hi(A) = (h(A) + pi) mod Nm, где рi — некоторое вычисляемое целое число, a Nm — максимальное число элементов в таблице идентификаторов. В свою оче редь, самым простым подходом здесь будет положить рi = i. Тогда получаем формулу hi(A) = (h(A)+i) mod Nm. В этом случае при совпадении значений хэш-функции для каких-либо элементов поиск свободной ячейки в таблице начина ется последовательно от текущей позиции, заданной хэш-функцией h(А).
Этот способ нельзя признать особенно удачным — при совпадении хэш-адресов элементы в таблице начинают группироваться вокруг них, что увеличивает чис ло необходимых сравнений при поиске и размещении. Среднее время поиска элемента в такой таблице в зависимости от числа операций сравнения можно оценить следующим образом:
Тп= О((l-Lf/2)/(l- Lf)).
Здесь Lf — (load factor) степень заполненности таблицы идентификаторов — отношение числа занятых ячеек таблицы к максимально допустимому числу эле ментов в ней: Lf = N/Nm.
Выше в примере была рассмотрена весьма примитивная хэш-функция, которую никак нельзя назвать удовлетворительной. Хорошая хэш-функция распределя ет поступающие на ее вход идентификаторы равномерно на все имеющиеся в распоряжении адреса, так что коллизии возникают не столь часто. Существует большое множество хэш-функций. Каждая из них стремится распределить адре са под идентификаторы по своему алгоритму, но идеального хэширования дос тичь не удается.
В реальных компиляторах практически всегда так или иначе используется хэш-адресация. Алгоритм применяемой хэш-функции обычно составляет «ноу-хау» разработчиков компилятора. Обычно при разработке хэш-функций создатели компилятора стремятся свести к минимуму количество возникающих коллизий не на всем множестве возможных идентификаторов, а на тех их вариантах, кото рые наиболее часто встречаются во входных программах. Конечно, принять во внимание все допустимые исходные программы невозможно. Чаще всего выпол няется статистическая обработка встречающихся имен идентификаторов на не котором множестве типичных исходных программ, а также принимаются во вни мание соглашения о выборе имен идентификаторов, общепринятые для входного языка. Хорошая хэш-функция — это шаг к значительному ускорению работы компилятора, поскольку обращения к таблицам идентификаторов выполняются многократно на различных фазах компиляции.
То, какой конкретно метод применяется в компиляторе для организации таблиц идентификаторов, зависит от реализации компилятора. Один и тот же компиля тор может иметь даже несколько разных таблиц идентификаторов, организован ных на основе различных методов.
Как правило, применяются комбинированные методы. В этом случае, как и для метода цепочек, в таблице идентификаторов организуется специальное дополни тельное поле ссылки. Но в отличие от метода цепочек оно имеет несколько иное значение. При отсутствии коллизий для выборки информации из таблицы ис пользуется хэш-функция, поле ссылки остается пустым. Если же возникает кол лизия, то через поле ссылки организуется поиск идентификаторов, для которых значения хэш-функций совпадают по одному из рассмотренных выше методов: неупорядоченный список, упорядоченный список или же бинарное дерево. При хорошо построенной хэш-функций коллизии будут возникать редко, поэтому количество идентификаторов, для которых значения хэш-функций совпали, будет не столь велико. Тогда и время поиска одного среди них будет незначитель ным (в принципе при высоком качестве хеш-функции подойдет даже перебор по неупорядоченному списку).
Такой подход имеет преимущество по сравнению с методом цепочек: для хране ния идентификаторов с совпадающими значениями хэш-функции используют ся области памяти, не пересекающиеся с основной таблицей идентификаторов, а значит, их размещение не приведет к возникновению дополнительных колли зий. Недостатком метода является необходимость работы с динамически распре деляемыми областями памяти. Эффективность такого метода, очевидно, в пер вую очередь зависит от качества применяемой хэш-функции, а во вторую — от метода организации дополнительных хранилищ данных.
Хеш-адресация — это метод, который применяется не только для организации таблиц идентификаторов в компиляторах. Данный метод нашел свое приме нение и в операционных системах, и в системах управления базами данных.
Прежде чем перейти к рассмотрению лексических анализаторов, необходимо дать четкое определение того, что же такое лексема.
Лексема (лексическая единица языка) — это структурная единица языка, кото рая состоит из элементарных символов языка и не содержит в своем составе дру гих структурных единиц языка.
Лексемами языков естественного общения являются слова. Лексемами языков программирования являются идентификаторы, константы, ключевые слова язы ка, знаки операций и т. п. Состав возможных лексем каждого конкретного языка программирования определяется синтаксисом этого языка.
Лексический анализатор (или сканер) — это часть компилятора, которая читает исходную программу и выделяет в ее тексте лексемы входного языка. На вход лексического анализатора поступает текст исходной программы, а выходная ин формация передается для дальнейшей обработки компилятором па этапе син таксического анализа и разбора.
С теоретической точки зрения лексический анализатор не является обязатель ной частью компилятора. Все его функции могут выполняться на этапе син таксического разбора, поскольку полностью регламентированы синтаксисом входного языка. Однако существует несколько причин, по которым в состав практически всех компиляторов включают лексический анализ:
Функции, выполняемые лексическим анализатором, и состав лексем, которые он выделяет в тексте исходной программы, могут меняться в зависимости от версии компилятора. То, какие функции должен выполнять лексический анализатор и какие типы лексем он должен выделять во входной программе, а какие оставлять для этапа синтаксического разбора, решают разработчики компилятора. В основ ном лексические анализаторы выполняют исключение из текста исходной про граммы комментариев, незначащих пробелов, символов табуляции и перевода строки, а также выделение лексем следующих типов: идентификаторов, строко вых, символьных и числовых констант, ключевых (служебных) слов входного языка, знаков операций и разделителей.
В простейшем случае фазы лексического и синтаксического анализа могут вы полняться компилятором последовательно. Но для многих языков программиро вания на этапе лексического анализа может быть недостаточно информации для однозначного определения типа и границ очередной лексемы. Иллюстрацией та кого случая может служить пример оператора программы на языке FORTRAN, когда по части текста DO 10 1=1 невозможно определить тип оператора (а соот ветственно, и границы лексем). В случае DO 10 1=1.15 это присвоение веществен ной переменной D010I значения константы 1.15 (пробелы в языке FORNTAN игнорируются), а в случае DO 10 1=1,15 — цикл с перечислением от 1 до 15 по це лочисленной переменной I до метки 10.
Другим примером может служить оператор языка С, имеющий вид: k=i+++++j:. Существует только одна единственно верная трактовка этого оператора: k = 1++ + ++j: (если явно пояснить ее с помощью скобок, то данная конструкция имеет вид: k = (1++) + (++j);). Однако найти ее лексический анализатор может, лишь про смотрев весь оператор до конца и перебрав все варианты, причем неверные вари анты могут быть обнаружены только на этапе семантического анализа (напри мер, вариант k = (1++)++ + j; является синтаксически правильным, но семантикой языка С не допускается). Конечно, чтобы эта конструкция была в принципе допустима, входящие в нее операнды k, i и j должны быть описаны и должны до пускать выполнение операций языка ++ и +.
Поэтому в большинстве компиляторов лексический и синтаксический анализаторы — это взаимосвязанные части. Возможны два принципиально различных метода организации взаимосвязи лексического анализа и синтаксического разбора:
При последовательном варианте лексический анализатор просматривает весь текст исходной программы от начала до конца и преобразует его в структурированный набор данных. Этот набор данных называют также таблицей лексем. В таблице лексем ключевые слова языка, идентификаторы и константы, как правило, заме няются на специально оговоренные коды, им соответствующие (конкретная кодировка определяется при реализации компилятора). Для идентификаторов и констант, кроме того, устанавливается связь между таблицей лексем и табли цей идентификаторов, которая заполняется параллельно.
В этом варианте лексический анализатор просматривает весь текст исходной программы один раз от начала до конца. Таблица лексем строится полностью вся сразу, и больше к ней компилятор не возвращается. Всю дальнейшую обработку выполняют следующие фазы компиляции.
При параллельном варианте лексический анализ исходного текста выполняется поэтапно так, что синтаксический анализатор, выполнив разбор очередной кон струкции языка, обращается к сканеру за следующей лексемой. При этом он мо жет сообщить информацию о том, какую лексему следует ожидать. В процессе разбора при возникновении ошибки может происходить «откат назад», чтобы попытаться выполнить анализ текста на другой основе. И только после того, как синтаксический анализатор успешно выполнит разбор очередной конструкции языка (обычно такой конструкцией является оператор исходного языка), лекси ческий анализатор помещает найденные лексемы в таблицу лексем и таблицу идентификаторов и продолжает разбор дальше в том же порядке.
Работа синтаксического и лексического анализаторов в варианте их параллель ного взаимодействия изображена в виде схемы на рис. 13.7.
В качестве варианта таблицы лексем можно рассмотреть некоторый фрагмент кода на языке Pascal и соответствующую ему таблицу лексем, представленную в табл. 13.1:
Рис. 13.7. Параллельное взаимодействие лексического и синтаксического анализаторов
Таблица 13.1. Лексемы программы
|
Лексема |
Тип лексемы |
Значение |
|
begin |
Ключевое слово |
X1 |
|
for |
Ключевое слово |
Х2 |
|
I |
Идентификатор |
i : 1 |
|
:= |
Знак присваивания |
:= |
|
1 |
Целочисленная константа |
1 |
|
to |
Ключевое слово |
X3 |
|
N |
Идентификатор |
N : 2 |
|
do |
Ключевое слово |
Х4 |
|
fg |
Идентификатор |
fg : 3 |
|
:= |
Знак присваивания |
:= |
|
fg |
Идентификатор |
fg : 3 |
|
* |
Знак арифметической операции |
* |
|
0.5 |
Вещественная константа |
0.5 |
Поле «Значение» в табл. 13.1 подразумевает некое кодовое значение, которое бу дет помещено в итоговую таблицу лексем в результате работы лексического ана лизатора. Конечно, значения, которые записаны в примере, являются услов ными. Конкретные коды определяются при реализации компилятора. Важно отметить также, что для идентификаторов устанавливается связка таблицы лек сем с таблицей идентификаторов (в примере это отражено некоторым индексом, следующим после идентификатора за знаком :, а в реальном компиляторе все опять же определяется его реализацией).
Очевидно, что последовательный вариант организации взаимодействия лексиче ского анализа и синтаксического разбора является более эффективным, так как он не требует организации сложных механизмов обмена данными и не нуждает ся в повторном прочтении уже разобранных лексем. Этот метод является и более простым. Однако не для всех языков программирования возможно организовать такое взаимодействие. Это зависит в основном от синтаксиса языка, заданного его грамматикой. Большинство современных широко распространенных языков программирования, таких как С и Pascal, тем не менее позволяют построить лексический анализ по более простому, последовательному методу, что дает ряд определенных преимуществ.
Лексический анализатор имеет дело с такими объектами, как различного рода константы и идентификаторы (к последним относятся и ключевые слова). Язык констант и идентификаторов в большинстве случаев является регулярным — то есть может быть описан с помощью регулярных грамматик. Распознавателями для регулярных языков являются конечные автоматы. Существуют правила, с помощью которых для любой регулярной грамматики может быть построен недетерминированный конечный автомат, рас познающий цепочки языка, заданного этой грамматикой. Конечный автомат для каждой входной цепочки языка дает ответ на вопрос о том, принадлежит или нет цепочка языку, заданному автома том.
Однако в общем случае задача сканера несколько шире, чем просто проверка це почки символов лексемы на соответствие ее входному языку. Кроме этого, ска нер должен выполнить следующие действия:
Выделение границ лексем представляет определенную проблему. Ведь во вход ном тексте программы лексемы не ограничены никакими специальными симво лами. Если говорить в терминах программы-сканера, то определение границ лек сем — это выделение тех строк в общем потоке входных символов, для которых надо выполнять распознавание. В общем случае эта задача может быть сложной, и тогда требуется параллельная работа сканера (лексического анализатора), син таксического разбора и, возможно, семантического анализа. Для большинства входных языков границы лексем распознаются по заданным терминальным сим волам. Эти символы — пробелы, знаки операций, символы комментариев, а так же разделители (запятые, точки с запятой и т. п.). Набор таких терминальных символов может варьироваться в зависимости от синтаксиса входного языка.
Важно отметить, что знаки операций сами также являются лексемами и необхо димо не пропустить их при распознавании текста.
Как правило, сканеры действуют по следующему принципу: очередной символ из входного потока данных добавляется в лексему всегда, когда он может быть туда добавлен. Как только символ не может быть добавлен в лексему, то считается, что он является границей лексемы и началом следующей лексемы (если символ не является пустым разделителем — пробелом, символом табуляции или перево да строки, знаком комментария). Такой принцип не всегда позволяет правильно определить границы лексем в том случае, когда они не разделены пустыми сим волами. Например, приведенная выше строка языка С k=1+++++j; будет разбита на лексемы следующим образом: k = 1++ ++ + j; — и это разбиение неверное, ком пилятор должен будет выдать пользователю сообщение об ошибке, хотя пра вильный вариант распознавания строки существует.
Однако разработчики компиляторов сознательно идут на то, что отсекают неко торые правильные, но не вполне читаемые варианты исходных программ. По пытки усложнить лексический распознаватель неизбежно приведут к необходи мости его взаимосвязи с синтаксическим разбором. Это потребует организации их параллельной работы и неизбежно снизит эффективность работы всего ком пилятора. Возникшие накладные расходы никак не оправдываются достигаемым эффектом — чтобы распознавать строки с сомнительными лексемами, достаточ но лишь обязать пользователя явно указать с помощью пробелов (или других незначащих символов) границы лексем, что значительно проще.
Не для всех входных языков такой подход возможен. Например, для рассмот ренного выше примера с языка FORTRAN невозможно применить указанный метод — разница между оператором цикла и оператором присваивания слишком существенна, чтобы ею можно было пренебречь. Здесь придется прибегнуть к связи с синтаксическим разбором. В таком случае говорят о непрямой работе лексического анализатора.
Лексический анализатор работает прямо, если для данного входного текста (це почки символов входного языка) и текущего положения указателя в нем он оп ределяет лексему, расположенную непосредственно справа от указателя, и сдви гает сам указатель вправо от части текста, образующей эту лексему. При прямой работе лексического анализатора возможно его последовательное взаимодейст вие с синтаксическим распознавателем.
Лексический анализатор работает непрямо, если для данного входного текста (цепочки символов входного языка), заданного типа лексемы и текущего поло жения указателя в нем он определяет лексему, расположенную непосредственно справа от указателя, и если она соответствует требуемому типу, то сдвигает ука затель вправо от части текста, образующей эту лексему. В отличие от прямого варианта данному лексическому анализатору на входе требуется задавать также и тип ожидаемой лексемы. Поэтому при непрямой работе лексического анализа тора требуется его параллельное взаимодействие с синтаксическим распознава телем.
Выполнение действий в процессе распознавания лексем представляет для скане ра гораздо меньшую проблему. Фактически КА, который лежит в основе распо знавателя лексем, должен иметь не только входной язык, но и выходной. Он дол жен не только уметь распознать правильную лексему на входе, но и породить связанную с ней последовательность символов на выходе. В такой конфигура ции КА преобразуется в конечный преобразователь.
Для сканера действия по обнаружению лексемы могут трактоваться несколько шире, чем только порождение цепочки символов выходного языка. Сканер дол жен уметь выполнять такие действия, как запись найденной лексемы в таблицу лексем, поиск ее в таблице символов и запись новой лексемы в таблицу симво лов. Набор действий определяется реализацией компилятора. Обычно эти дейст вия выполняются сразу же по обнаружению конца распознаваемой лексемы.
В КА сканера эти действия можно отобразить сравнительно просто — достаточно иметь возможность с каждым переходом на графе автомата (или в функции пе реходов автомата) связать выполнение некоторой произвольной функции f(q,a), где q — текущее состояние автомата, а — текущий входной символ. Функция может выполнять произвольные действия, доступные сканеру, в том числе рабо тать с хранилищами данных, имеющимися в компиляторе (функция может быть и пустой — не выполнять никаких действий). Такую функцию, если она есть, обычно записывают на графе переходов КА под дугами, соединяющими состоя ния КА.
Теперь можно рассмотреть практическую реализацию сканеров. В принципе ком пилятор может иметь в своем составе не один, а несколько лексических анализа торов, каждый из которых предназначен для выборки и проверки определенного типа лексем.
Таким образом, обобщенный алгоритм работы простейшего лексического анали затора в компиляторе можно описать следующим образом:
В целом техника построения сканеров основывается на моделировании работы детерминированных и недетерминированных конечных автоматов с дополнением функций распознавателя вызовами функций обработки ошибок, а также заполнением таблиц символов и таблиц идентификаторов. Такая техника не требует сложной мат. обработки и принципиально важных преобразований входных грамматик. Для разработчика сканера важно решить, где заканчиваются функции сканера и начинаются функции синтаксического разбора.