Системное программирование пособие – Принципы построения компиляторов – фазы компиляции


В учебном пособии описаны принципы построения компиляторов. Рассмотрены фазы компиляции: лексический, синтаксический, семантический анализы, фазы генерации й оптимизации кода. Фазы лексического и синтаксического анализа изучаются более детально. Лексический анализатор демонстрируется на примерах распознавания типичных лексем языков программирования, а синтаксический — на примере вычисления математических формул.

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

Пособие содержит большое количество демонстрационных программ на С / C ++. Приведены варианты заданий для лабораторной работы «Элементы компиляции», а также пример выполнения типичной лабораторной работы.

Для студентов направления подготовки «Прикладная математика».

Понятие речевого процессора – Типы языковых процессоров

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

Подготовка произвольной программы начинается с создания и редактирования файла с текстом этой программы. Файл, как правило, стандартное для данного языка расширения. Далее выполняется компиляция (трансляция) программы, которая включает в себя несколько фаз, например, лексический, синтаксический, семантический анализы, фазы генерации й оптимизации кода. В результате трансляции получается объектный модуль готовой программы, который имеет стандартное расширение «.obj». Компоновка программы заключается в объединении одного или нескольких объектных модулей программы, объектных модулей со стандартными функциями, взятых из библиотечных файлов, и других полезных модулей. В результате компоновки получается загрузочный модуль в виде отдельного файла (программный файл) со стандартным расширением «.exe». Далее программный файл загружается в память и выполняется.

Программа, позволяющая выполнить директивы и предложения входного языка, которую использует программист, называется речевым процессором [1]. А сам процесс выполнения называют компиляцией (трансляцией, переводом). Компиляция состоит из двух частей:

  • анализ — разбиение исходной программы на составные части и создание промежуточного представления;

  • синтез — построение целевой программы по промежуточного представления.

    Языковые процессоры условно можно разделить на компиляторы, трансляторы, интерпретаторы и байт-код-трансляторы. Часто речевые процессоры обобщенно называют компиляторами.

    языковые процессоры

    Компиляторы трансляторы Интерпретаторы

    Байт-код-трнсляторы

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

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

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

происходит каждый раз, когда программа запускается на выполнение. Интерпретаторы, как правило, просты в написании чем трансляторы, но выполняются медленнее и не дают возможности создать исполняемый файл (exe-файл). Пример интерпретатора: Basic.

Байт-код-транслятор. Байт-код-транслятор — это речевой процессор, реализующий промежуточный подход, при котором программа превращается в промежуточный двоичный вид, который интерпретируется какой-то «виртуальной машиной» во время выполнения. При использовании байт-кода программы высокого уровня превращаются в промежуточный вид, способный исполняться на различных аппаратных платформах. Пример байт-код-транслятора: Java. Байт-код Java превращается в машинный код с помощью специального интерпретатора, что называется виртуальной машиной Java (Java Virtual Machine — JVM). JVM формирует выделенное пространство в памяти для хранения байт-кода и порождаемых структур. Эта память отделена от памяти основной системы.

JIT-компилятор (динамический just-in-time компилятор). JIT- компилятор НЕ интерпретирует промежуточный код виртуальной машиной, а превращает его в «родной» для данной машины код. JIT-компилятор генерирует машинный код прямо в оперативной памяти без сохранения. Это приводит к значительному увеличению скорости выполнения приложения. Именно так и устроена новая платформа Microsoft .NET.

Рассмотрим [9] схему трансляции в архитектуре платформы Microsoft .Net: исходные тексты программ здесь компилируются в специальное промежуточное представление (Microsoft Intermediate Language, часто употребляется сокращение IL или MSIL). Промежуточное представление содержит всю необходимую информацию о программе, но не привязано к какой-либо определенной языка программирования или к машинному коду какой-либо целевой платформы. Для запуска программы необходимо специальное окружение, которое выполняет программы, и библиотеки динамической поддержки (execution engine & runtime). Особенностью трансляции в .NET является то, что промежуточное представлении не интерпретируется; вместо этого используется механизм компиляции времени исполнения, генерирует машинный код.

Основные фазы речевого процессора – модели компилятора

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

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

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

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

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

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

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

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

организации таблиц. При построении компиляторов чаще всего используются хэш-таблицы (таблицы размещения).

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

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

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

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

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

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

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

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

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

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

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

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

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

В зависимости от сложности речевого процессора некоторые вышеперечисленные фазы могут отсутствовать или объединенными в

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

image

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

image

Выше приведен пример трипрохидного компилятора, где (1) — начальная программа, (2) — последовательность лексем (3) — промежуточный код,

  1. — машинный код.Далее будет подробно рассматриваться процесс построения речевого процессора для простой демонстрационной языка SPL [2]. Для упрощения будем считать, что промежуточный код — это код специальной мнимой(Виртуальной) машины, которую будем называть SPL-процессором. Фазы синтаксического анализа и генерации промежуточного кода объединим. Тогда модель компилятора будет выглядеть так:

image

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

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

Распознавание идентификаторов и констант

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

Лексический анализ и конечные автоматы

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

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

Формально [1] недетерминированным конечным автоматом M называется пятерка M (Q, , , q 0, F), где

Q — конечное множество состояний автомата Q = {q 0, q 1, …, q n};

— конечное множество входных символов = {a 1, a 2, …, a m};

— отображение множества Q в P (Q) (множество всех

подмножеств Q), что определяет поведение управляющего устройства (функция (q, a), где q Q, a , называют функцией переходов)

q Q

— начальное состояние управляющего устройства;

F Q — множество заключительных состояний.

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

  • это изменение управляющего устройства и смещение головки вправо на одну ячейку.

image

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

Конечный автомат M является детерминированным, если для каждых

a є , q є Q

существует не более одного состояния, в которое происходит

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

Функцию переходов автомата можно задавать как таблицу переходов или как диаграмму переходов.

Матрица (таблица) переходов — это двумерный массив, который для каждой пары «состояние (строка) и символ (столбец)» определяет новое состояние, в котором он переводится.Номер этого состояния и находится в матрице.

Диаграммой переходов (графом переходов) автомата M называется нагруженный граф, вершины которого нагружены именами состояний

автомата, и в диаграмме присутствует ребро (P, q), p, q є Q, если

подтверждается следующее соотношение:

q є (p, a), a є.ребра

нагруженные всеми символами a є, по которым есть переход из p в q.

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

Каждому состоянию автомата, на диаграмме отображается кружочком, отвечает «поведение» конечного автомата.

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

Вот так выглядит диаграмма переходов [10] автомата для распознавания обычной беззнаковую десятичной константы и идентификатора.

image

Проектирование конечного автомата с помощью диаграммы переходов происходит наглядно. Определяются состояния конечного

автомата, им присваивается «содержание», а затем определяется, при каких условиях происходит переход из одного состояния в другое.

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

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

Лексический анализатор целочисленных констант и идентификаторов

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

Напомним, что в языке С восьмеричная константа начинается с одного нуля и содержит цифры от до 7, шестнадцатеричная — начинается с символов 0x и содержит цифры от до 7 и буквы от a до f и от A до F.

В программе определяется переменная ST — текущее состояние детерминированного конечного автомата. Вся множество входных символов разбивается на непересекающиеся множества — классы CL. Классы выбираются таким образом, чтобы обеспечивалось однозначное переключение автомата, если анализируются не самые символы, а их классы. Итак, множество символов необходимо разбить на следующие классы:

класс символа

множество символов

цифра 0

1

цифры 1-7

2

цифры 8-9

3

буква x

4

буквы AF, af

5

другие буквы, кроме букв x, AF, af

6

другие символы

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

Поскольку лексический анализатор должен распознавать различные типы лексем, нужно определить различные типы заключительных состояний. Поэтому незаключительные состояния Занумеруем неотъемлемыми числами, а заключительные — отрицательными. Заключительный состояние -1 будет означать, что найдено идентификатор, -2 — найдено шестнадцатеричную константу, -3 — восьмеричную константу, -4 — десятичную, -5 — другой символ. Дуги нагрузим цифрами, соответствуют классу прочитанного символа. Будем считать, что после распознавания любой лексемы автомат переводится в исходное незаключительное состояние 0.

image

На диаграмме переходов, приведенной на рис.7, в состоянии 1 происходит накопление идентификатора, в состоянии 3 — накопление восьмеричной константы, в состоянии 4 — шестнадцатеричной, а в состоянии 5 — десятичной.

Для входного файла lex.dat с таким содержимым

123 «uuu» jjjjjjjj 0xAF66 077068 0xd 134 «string» 06

программа выдала следующие результаты:

Константа-10123 Идентификатор uuu Идентификатор jjjjjjjj Константа-16 0xAF66 Константа-8077

Константа-6 августа

Константа-10 августа Константа-16 0xd Константа-10134 Идентификатор string Константа-8 июня Конец работы

Лексический анализатор одной лексемы — действительное число

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

Здесь е — пустой символ, d — любая цифра от 0 до 9, вертикальные полосы означают альтернативу, круглые скобки окружают группу символов и меняют приоритет операций. Запись d * означает, что цифра может повторяться сколько угодно раз либо не повторяться ни разу. Запись d + означает последовательность из одной или более цифр. Запись d + можно записать так dd *.

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

image

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

Можно показать, что состояния А и В эквивалентны между собой, то есть такими, что вместо одного из них можно использовать другой. Итак, удалим состояние В (вместо него будем использовать состояние А) и получим такую ​​диаграмму переходов:

image

По диаграмме переходов построим таблицу переходов детерминированного конечного автомата.

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

Автоматное программирования на основе конструкции while-switch-case

Универсальная программная реализация детерминированного конечного автомата

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

Разбор и интерпретация математических формул

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

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

использование специальных математических пакетов как серверов автоматизации для вычисления формул;
интерпретация;
компиляция.

Первое направление рекомендуется использовать в том случае, когда есть установленными, например, математические пакеты MathLab, MathCad или Excel или другие пакеты. Эти пакеты достаточно мощные, но их код является закрытым и поэтому они являются «черным ящиком» для

программиста. Кроме того, при необходимости переноса готового проекта на другой компьютер возникает проблема наличия на нем нужного пакета. В качестве примера реализации первого направления, в [8] приведены программы, в которых вычисления формул происходит с помощью метода Evaluate объекта WorkSheet. Как сервер автоматизации использовано MS Excel (COM-сервер), а как средство разработки — Visual Basic .NET и Delphi (COM-клиент).

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

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

Нисходящий синтаксический анализ для интерпретации числовых выражений

Для объяснения принципов, лежащих в основе метода рекурсивного спуска, рассмотрим задачу вычисления значения арифметической формулы. Используем идеи, предложенные в [9]. Будем рассматривать формулы, состоящие из однозначных операндов, бинарных операций сложения ‘+’, вычитание ‘-‘, умножение ‘*’ и деления нацело ‘/’, а также круглых скобок. Как всегда, приоритеты операций умножения и деления уровне и их приоритет больше, чем приоритеты операций сложения и вычитания, причем приоритеты этих операций также уровне. Будем называть операции ‘+’ и ‘-‘ операциями типа сложения, а операции ‘*’ и ‘/’ — операциями типа умножения. Круглые скобки используются для изменения стандартного порядка выполнения операций. Наша задача заключается в написании программы, вычисляет значение числовой формулы.

Исследуемые нами формулы можно представить следующим образом:

T 1 + T 2 + … + T n,

где T i — это формула вида F 1i * F 2i * … * F mi.В свою очередь, F ji — это либо число, либо произвольная формула в круглых скобках.

Представим себе процесс вычисления значения формулы. Сначала вычисляется F 11, далее выясняется, какая операция следует за F 11. Если это операция типа умножения, то, зная его левый операнд,

вычисляется правый операнд и выполняется операция. Тем самым, получается левый операнд для возможных последующих операций типа умножения. Если после вычисления формулы F 1 * F 2 * … * F n, окажется, что далее следует операция типа сложения, то процесс вычисления такой формулы будет аналогичен описанному выше алгоритму.

Вычисление значения формулы

      • Для вычисления сложной формулы будем сначала вычислять ее части. Разделим все возможные формулы на 3 класса:
        1. простейшие формулы: числа и произвольные формулы в круглых скобках, например, 3 (1 + 3-8)
        2. формулы, содержащие операции типа умножения, то есть умножение и деление, например, 8 * 2 * (5 + 2) / 7. Операции типа умножения выполняются над простейшими формулами;
        3. формулы, содержащие операции типа сложения, то есть сложение и вычитание, например, 8 * 2 * (5 + 2) / 7 + 3 + (7 + 3 8) * (2-7). Операции типа сложения выполняются над формулами, содержащими операции типа умножения.

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

Expression (Term (Factor ())),

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

Опишем функцию, вычисляет значение простой формуле:

Отметим, что эта функция вызывает функция Term (), которую в свою очередь вызывает Expression (), то есть здесь задействована косвенная рекурсия, которая спускается к самому простому операнда с наивысшим приоритетом — числа. Отсюда следует название описанного метода вычисления формулы

  • нисходящий синтаксический анализ.

В функции вызывается вспомогательная функция error (), которая печатает сообщение и возвращает значение 0:

int error (char * s)

{

cputs (( «\ n \ r»); cputs (s) return 0;

}

Формула, содержащая операции типа умножения

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

F 1 * F 2 * … * F n.

Мы сможем понять, что имеем дело с подобной формулой только в момент встречи операции умножения или операции деления. Обрабатывать такие формулы будет процедура Term () параметром которой является целочисленных значения, представляет левый операнд формулы F 1 * F 2, то есть F 1.Для того, чтобы вычислить значение такой формулы, мы должны выбрать ее прав операнд, который может быть самой простой формуле, а затем выполнить операцию.

Формула, содержащая операции типа сложения

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

T 1 + T 2 + … + Tn.

Нетрудно заметить, что такая формула будет встречаться только в выражениях где есть операции сложения или вычитания. Такие формулы будет обрабатывать функция Expression () параметром которой является целочисленных значения, представляет левый операнд операции типа сложения. Алгоритм следующей функции такой же, как и функции Term ().

int Expression (int left)

{

char ch = getche ();

if (ch!= ‘+’ && ch!= ‘-‘)

{

ungetch (ch); return left;

}

int right = Term (Factor ());

if (ch == ‘+’) return Expression (left + right)

return Expression (left — right)

}

Функция вычисления числовой формулы выглядит так:

int Formula ()

{Return Expression (Term (Factor ()));}

Протестировать программу можно с помощью основной функции вида:

int main ()

{

cputs ( «\ n \ rЧислова Формула: ‘); cprintf ( «\ n \ rРезультат вычисления% d», Formula ()); return 0;

Синтаксический анализ и контекстно-свободные грамматики

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

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

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

Рассмотрим далее кратко грамматики Хомского и такие важные для синтаксического анализа их виды как контекстно-свободная и LA (1) — грамматика.

Грамматики Хомского. Основные понятия

Грамматикой Хомского называется четверка G = (N, T, P, S), где

T — алфавит определяемый языка, или множество терминальных символов (терминалов).

N — множество обозначений понятий языка, то есть нетерминальных символов (нетерминалов).

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

S начальный нетерминал из множества N, или главное понятие, которым обозначаются слова языка.

Грамматика G называется контекстно-свободной (безконтекстною), если каждое правило из P имеет вид: A

Нетерминалы E, T, F соответственно являются сокращениями слов «Expression»,

«Term», «Factor», то есть «выражение», «слагаемое», «множитель». Они обозначают выражения со знаками операций ‘+’ и ‘*’, слагаемые и множители в них соответственно. Вертикальная черта означает альтернативу выбора правила для развертывания нетерминалу. Развертывание нетерминалу — это

замена его на правую часть правила. Итак, правило

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

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

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

Все цепочки, которые принадлежат языке грамматики, выводятся из начального нетерминалу и состоят только из терминальных символов. Теоретически для анализа принадлежности некоторого цепочки языке грамматики G, можно разработать алгоритм анализа на основе переборки продукций, но он будет практически неприемлемым вследствие его оценки сложности. Один из путей к эффективных алгоритмов анализа заключается в ограничении структуры продукций и избавлении от переборки за счет сужения множества контекстно-свободных грамматик. Далее рассматриваются именно такие ограниченные грамматики (LA (1) -грамматики) и построение алгоритма анализа для них.

Часть 2 здесь

[Всего голосов: 4    Средний: 5/5]

Читать  МЕТОДИЧЕСКИЙ СБОРНИК индивидуальных практических заданий Turbo Pascal