этой грамматикой предложение имеет единственное синтаксическое дерево . В противном случае грамматика называется неоднозначной.
Многие компиляторы создаются на основе однозначных грамматик , однако при разработке компиляторов в ряде случаев возникают неоднозначные грамматики , для которых однако чаще всего находятся методы устранения неоднозначности . Неоднозначные языки , для которых не существует однозначной грамматики , обычно не
используются в языках программирования .
3.1.2.Семантика .
Семантика определяет смысловую интерпретацию конструкций языка.
Методы описания семантики как правило принадлежат к одному из
перечисленных ниже классов .
Денотационная семантика основывается на функциональных вычислениях , определяющих операции в языке в виде отображений
в однозначные математические понятия , которые затем используются для описания результата вычислений через входные и выходные данные .
Аксиоматическая семантика основывается на исчислении
предикатов ,где результат вычислений описывается через взаимоотношения между значениями переменных до и после применения определенных операций .
Операционная семантика предусматривает описание операций в языке через деятельность некой абстрактной машины , выполняющей вычисления .
3.2. Основные этапы компиляции.
Процесс компиляции обычно принято делить на три основных этапа :
предварительная обработка , анализ и синтез .
Предварительная обработка предусматривает выполнение так
называемых операций периода компиляции , которые включают в себя развертывание макросов , присоединение исходных файлов , удаление комментариев и т.п. . Данный этап представляется достаточно простым и поэтому в дальнейшем мы не будем его рассматривать,ограничившись лишь его кратким объяснением .
Этап анализа включает в себя три фазы .
1) Лексический анализ ;
2) Синтаксический анализ ;
3) Семантический анализ .
Лексический анализ выполняет формирование символов языка . Ключевые слова языка , идентификаторы , константы и другие элементы языка , представляющие объекты обработки лексического анализа , преобразуются в неделимые символы языка , которые в дальнейшем используются на фазах синтаксического и
семантического анализов. Кроме этого лексический анализатор осуществляет обработку пробелов , удаление комментариев и некоторые другие действия , необходимые для подготовки текста программы к последующим фазам . При формировании символов языка лексический анализатор не учитывает их последовательность , то есть как правило не работает с контекстом . Например , если в программе на языке PASCAL появится некорректная конструкция вида if b while P вместо if b then P , лексический анализатор не обнаружит никакой ошибки .
Синтаксический анализ строит древовидное представление текста программы , которое называется синтаксическим деревом . В процессе построения анализируется корректность структуры программы .
В отличие от лексического анализа , синтаксический анализатор полностью работает с контекстом . Например при анализе упомянутой выше некорректной конструкции синтаксический анализатор обнаружит ошибку .
Семантический анализ ориентирован на проверку тех свойств текста исходной программы , которые не могут быть проверены синтаксическим анализатором простым сканированием слева направо. Например , проверка корректного использования типов данных в операциях , функциях и операторах ( проверка совместимости типов ) , для которой необходимо предварительно построить таблицу переменных .
Этап синтеза состоит из следующих фаз .
1) Генерация машинно-независимого кода ;
2) Оптимизация машинно-независимого кода ;
3) Распределение памяти ;
4) Генерация машинного кода ;
6) Оптимизация машинного кода .
Если компиляция осуществляется непосредственно в машинный код ,
то первые две фазы отсутствуют . Однако часто в компиляторах
используется машинно-независимый код , поскольку в этом случае обеспечивается относительная независимость компилятора от конкретного класса компьютеров и входного языка .
Оптимизация кода позволяет получить эффективный код ,
обеспечивающий оптимальное сочетание двух важных свойств объектного кода : максимально возможная скорость выполнения и минимально возможный объем используемой памяти .
Распределение памяти обеспечивает резервирование памяти для переменных , констант и других объектов языка . Результатом работы этого этапа является создание адреса , содержащего полную информацию о структуре распределения памяти .
Этап анализа достаточно хорошо автоматизируется с точки зрения
создания компилятора компиляторов (наиболее удачными примерами такой автоматизации являются уже упомянутые выше генераторы лексического и синтаксического анализаторов LEX и YACC ) .
Автоматизация этапа синтеза представляется существенно более сложной задачей , поэтому средства инструментальной поддержки этого этапа не получили широкого распространения .
Кроме рассмотренных выше понятий для компиляторов важным является количество проходов компиляции. Большинство современных
компиляторов обеспечивает полный процесс компиляции при однократ-ном чтении кода ( однопроходные компиляторы ) . Ранние компиляторы были многопроходными в основном по причине малых размеров памяти
компьютеров того времени . Для современных компиляторов , как правило , такой проблемы не существует , однако имется ряд языков программирования , специфика которых в принципе не позволяет одного прохода (например ALGOL 68).
Важной составляющей инструментальных средств реализации современных систем программирования является интегрированная среда разработки ( IDE - Integrated Development Envirinment ) ,
обеспечивающая автоматизацию процессов разработки , программирования , отладки и компиляции . Понятие интегрированной среды разработки возникло с появлением объектно-ориентированного программирования .
3.3. Лексический анализ.
Лексический анализ выполняет формирование символов языка на основе так называемых лексем , к числу которых принадлежат следующие элементы языка.
1) Ключевые слова языка ( if , then , else , while ,do , var , integer и т.п) .
2) Идентификаторы ( custom, x1 ,y1 , name и т.п)
3) Константы ( 14 , 13.06 , 'abc' и т.п. ) .
4) Последовательности знаков (<= , <> ,>=, и т.п . ) .
7) Знаки пунктуации ( { } [ ] … , ; и т.п ) .
Лексемы преобразуются в неделимые символы языка , которые в дальнейшем используются на фазах синтаксического и
семантического анализов. Кроме этого лексический анализатор осуществляет обработку пробелов , удаление комментариев и некоторые другие действия , необходимые для подготовки текста программы к последу-ющим фазам . При формировании символов языка лексический анализатор не учитывает их последовательность , то есть как правило не работает с контекстом . Например , если в программе на языке PASCAL появится некорректная конструкция вида if b while P вместо if b then P , лексический анализатор не обнаружит никакой ошибки .
Для фазы лексического анализа наиболее удобным средством описания символов являются регулярные выражения . Например , идентификатор можно представить в виде буква(буква | цифра)* .
Несмотря на относительную простоту процесса лексического анализа, существует ряд языковых особенностей , усложняющих реализацию лексических анализаторов. В основном это - следующие особенности :
- ключевые слова разрешено использовать в качестве
идентификаторов ;
- интерпретация некоторых последовательностей лексем носит
контекстно-зависимый характер .
Например в языке FORTRAN можно использовать конструкцию вида
IF(K) =1 , которую можно интерпретировать как присвоение значения
K-ому элементу массива с именем IF . Однако распознавание именно
такой интерпретации может быть выполнено только по достижению конца строки , поскольку может появиться конструкция IF(K) 1,2,3 , интерпретируемая как оператор IF . Другим неудобством языка FORTRAN с точки зрения лексического анализа является воможность использования внутренних пробелов при обозначении
идентификаторов. Конструкция DO 7 K=1,5 определяет оператор цикла . В то же время , пока не считан символ запятой , начало строки можно спутать с идентификатором DO 7 K .
Для устранения подобных неоднозначностей используют предваритель-ный просмотр текста и приведение к некоторому каноническому виду ,
который уже лексическим анализатором воспринимается однозначным
образом .
3.4. Синтаксический анализ.
3.4.1. Цель синтаксического анализа.
Первоочередной задачей синтаксического анализа является
нахождение порождения (если оно существует) конкретного предложения языка с использованием данной грамматики.
В большинстве случаев искомыми являются единственные левые или единственные правые порождения . В случае неоднозначных грамматик порождение не является единственным и поэтому в этом случае требуется наличие правил устранения неоднозначностей .
Если анализируемое предложение не принадлежит языку ,
компилятор не должен прекращать свою работу , ограничившись сообщением об ошибке. В этом случае , как правило , компилятор сообщает об ошибке и указывает на последний символ , после которого возникла ошибка . Затем после соответствующей локализации ошибки процесс анализа продолжается .Далее строится синтаксическое дерево , вершина которого соответствует символу предложения , соединяемого с анализируемым предложением через поддеревья , соответствующие продукциям грамматики . Существует несколько подходов к построению синтаксического дерева.
Нисходящий синтаксический анализ (top-down parsing) предусматривает построение синтаксического дерева , начиная
с вершины (символа предложения ) с развертыванием дерева в направлении предложения языка .
Восходящий синтаксический анализ (bottom-up parsing)