Разработка Компилятора
Введение
Предмет “Теория языков программирования и методы трансляции” изучается на 4 курсе студентами специальности 220400 - “Программное обеспечение вычислительной техники и автоматизированных систем”. Главная задача предмета обучить студентов знаниям и умениям в области современных методов и средств поэтапной разработки компиляторов.
Тема данного курсового проекта, это – разработка алгоритма компилятора и реализация созданного алгоритма на скриптовом языке программирования PHP.
В данном курсовом проекте будет поэтапно создан компилятор. Для разработки компилятора первым и наиболее главным шагом должна служить создание грамматики, посредствам которой компилятор должен будет производить анализ и синтез кода исходной программы во внутреннее представление. Написание компилятора заключается в создании трех основных модулей, во-первых, это лексический анализатор, который производит поиск лексем в исходном тексте обрабатываемой программы, во-вторых, разработка синтаксического анализатора, целью которого является поиск конструкции исходного языка и сравнение её с заранее определенной грамматикой, и, наконец, перевод во внутренние коды, который осуществляет преобразование исходного кода обрабатываемой программы во внутренние коды при учете удачной работы лексического и синтаксического анализатора.
Постановка задачи
Задание на проектирование
Разработать компилятор, который должен выполнять лексический, синтаксический анализ обрабатываемого текста и преобразовывать его во внутренние коды.
Входные данные
- Файл, содержащий обрабатываемый текст.
Выходные данные
- Внутренние коды, как результат обработки исходн
ого обрабатываемого текста.
Аналитическая часть
Анализ поставленной задачи
В данном курсовом проекте требуется разработать алгоритм компилятора, реализующий три основные задачи:
- лексический анализ текста исходной программы;
- синтаксический анализ текста исходной программы;
- перевод текста исходной программы во внутренние коды.
Исходя из этого, наиболее целесообразно будет разбить решение поставленной задачи на три главные составляющие, названные выше.
Первоначальными входными данными будет текст программы Pascal-подобного языка программирования. Первым шагом в написании компилятора, должно быть создание грамматики для лексического и синтаксического анализа.
Описание используемой грамматики
Для выполнения поставленной задачи была использована описанная ниже грамматика:
<program> ::= <variables_
<variables_definitions> ::=
<vars> : integer;
<vars> ::= <var> | <vars>, <var>
<var> ::= $<list>
<list> ::= <list><letter> | <list> <number>
<number> ::= <number> <digit> | <digit>
<digit> ::= 0 .. 9
<letter> ::= a .. z
<body> ::= begin <select_instruction> end
<select_instruction> ::= <
<instruction> ::= <var> := <operation>; |
if <compare> then <body> |
if <compare> then <body> else <body> |
while <compare> do <body>
<compare> ::= <select_
<operation> ::= <select_
<select_expression><
<select_expression> ::= <var> | <number>
<compare_operators> ::= <> | = | < | > | <= | >=
<arithmetic_operators> ::= + | - | * | /
Блок-схема алгоритма
Для простоты реализации и понимания алгоритма, его лучше всего разбить на 4 части:
- подключение файла с исходным обрабатываемым текстом, запуск анализа и синтеза компилятора при успешной обработке;
- лексический анализатор, который:
- осуществляет поиск совпадений лексем с заранее описанными шаблонами ключевых слов, идентификаторов, разделителей, комментариев;
- находит лексические ошибки, такие как отсутствие обязательных лексем, несовпадение количества взаимосвязанных лексем, нераспознанные лексемы.
- синтаксический анализатор, который:
- осуществляет сравнение текста исходной обрабатываемой программы с используемой в курсовом проекте грамматикой и выявляет ошибки, если таковые были найдены.
- перевод во внутренние коды, то есть преобразование исходного кода программы во внутренние коды.
Листинг программы, реализующей подключение файла с исходным обрабатываемым текстом, запуск анализа и синтеза компилятора при успешной обработке исходного текста, расположен в ПРИЛОЖЕНИИ 1.
Блок-схема алгоритма, описывающая используемый лексический анализатор, представлена на рисунке 2.1, а листинг программы, реализующей этот алгоритм – в ПРИЛОЖЕНИИ 2.
Рис 2.1
Блок-схема алгоритма, описывающая используемый синтаксический анализатор, представлена на рисунке 2.2, а листинг программы, реализующей этот алгоритм – в ПРИЛОЖЕНИИ 3.
Рис 2.2
Блок-схема алгоритма, осуществляющего перевод обрабатываемого текста во внутренние коды, представлена на рисунке 2.3, а листинг программы, реализующей этот алгоритм – в ПРИЛОЖЕНИИ 4.
Рис 2.3
Используя описанные выше блок-схемы алгоритмов, представляется возможным реализовать задачу, поставленную на курсовое проектирование, на любом языке программирования. В представленном курсовом проекте реализация была осуществлена на скриптовом языке программирования PHP.
Проектная часть
Общие сведения
Программы (скрипты), написанные для реализации данного курсового проекта, были созданы для работы с языком программирования PHP, который является очень удобным и мощным для разработчиков инструментарием. Основной функциональностью языка, которая использовалась в процессе разработки, являются регулярные выражения, действия которых основаны на сравнении обрабатываемой строки с заранее определенным шаблоном. При правильном и умелом использовании регулярных выражений, можно осуществлять поиск совершенно разнообразных подстрок в тексте, что и было использовано в данной курсовой работе.
Описание классов
Листинги всех программ, изложенные в Приложениях, были написаны с использованием знаний в области Объектно-Ориентированного Программирования (ООП), то есть в созданных в ходе проектирования программах описываются и используются следующие классы:
- Класс Compiller – является основным классом, который осуществляет чтение из файла с исходным кодом программы, запись содержимого в строковую переменную и передает эту переменную на обработку лексическому анализатору (классу Lexer).
- Класс Lexer – осуществляет лексический анализ текста, а именно поиск комментариев, поиск идентификаторов, поиск путем сравнения с шаблонами ключевых слов, а также заполняет информационную таблицу, которая реализована в виде разряженного (хеш) массива.
- Класс Grammar – содержит представление используемой грамматики.
- Класс Parser – выполняет синтаксический анализ текста, который в данной реализации осуществляется путем использования возможности языка программирования PHP – регулярных выражений, которые осуществляют сравнение строки с текстом с заранее предопределенными шаблонами.
- Класс Transform – осуществляет перевод текста исходной программы во внутренние коды.
Описание логической структуры
Структура программы изображена на рисунке 3.1.
Рис 3.1
Таким образом, основной частью программы является лексический и синтаксический анализаторы, а также не менее значимая процедура перевода текста исходной программы во внутренние коды.
Входные данные
Данными, требующимися для успешной работы программы, является файл с текстом исходной программы. Для успешной компиляции файла требуется, чтобы в обрабатываемом файле отсутствовали лексические и синтаксические ошибки, что проверяется сравнением текста файла с используемой Pascal-подобной грамматикой.
Выходные данные
Данными, результирующими работу программы, будут внутренние коды.
Контрольные примеры
Рис 4.1 – Пример ошибки на этапе лексического анализа
Рис 4.2 - Пример ошибки на этапе синтаксического анализа
Рис 4.3 – Успешная компиляция (Вариант 1)
Рис 4.4 - Успешная компиляция (Вариант 2 - начало)
Рис 4.5 - Успешная компиляция (Вариант 2 - продолжение)
Рис 4.6 - Успешная компиляция (Вариант 2 - конец)
Заключение
В ходе курсовой работы был составлен алгоритм компилятора на основе созданной в процессе разработки грамматики. Описанный в курсовой работе компилятор был реализован на скриптовом языке программирования PHP и является приложением, которое работает непосредственно на стороне сервера, на котором установлен и запущен web-сервер Apache.
Разработка компилятора началась с создания Pascal-подобной грамматики, которая в этапе разработки была переработана и приведена к виду, который описан в данной курсовой работе. Следующим этапом в создании компилятора было написание блок-схем алгоритмов, которые осуществляют немаловажное влияние при написании кода программ. В дальнейшем по составленному алгоритму была создана сама программа (скрипт), отвечающий за компиляцию исходных кодов обрабатываемых программ. При разработке кода компилятора, были использованы знания в области Объектно-Ориентированного Программирования (ООП), что позволило реализовать код программы в виде четырех классов: класса Compiller, который осуществляет подключение файла исходной программы, класса Lexer, производящего лексический анализ текста, класса Grammar, описывающего используемую грамматику, класса Parser, выполняющего синтаксический анализ текста и класса Transform, основной задачей которого является перевод обрабатываемого кода исходной программы во внутренние коды.
Рабочий код компилятора был проанализирован и отлажен, его работоспособность была проверена на основе нескольких обрабатываемых тексов программ с Pascal-подобной лексикой, тем самым можно утверждать, что задача данной курсовой работы была успешно выполнена.
Список использованной литературы
- Аляев Ю.А., Козлов О.А. Алгоритмизация и языки программирования Pascal, C++, Visual Basic: Учебно-справочное пособие. – М.: Финансы и статистика, 2002г., 320 с.
- Новичков В., Парфилова Н. Алгоритмизация и программирование на Турбо Паскале. Учебное пособие. – М.: Горячая линия - Телеком, 2005 г., 438 с.
- Профессиональное PHP программирование 2ое издание. – М.: Символ+, 2003 г., 1048 с.
- Ресурсы глобальной сети Internet.
- Цифровые информационные ресурсы.
Приложение 1
Файл <index.php>
<?php
include_once("include/
include_once("include/lexer.
include_once("include/grammar.
include_once("include/parser.
include_once("include/lexer_
include_once("include/
$p = new Compiller;
while ($f = $p->nextSourceFile()) {
if ($str = $p->readSourceFile($f)) {
echo $p->printSourceCode($str, $f);
$lexer = new LeXer($str, $lexer_keyws, $lexer_preerrors, $lexer_text_errors);
$lexer->lxScan();
if ($lexer->count == 0) {
echo $lexer->error_mess;
$parser = new Parser($str);
if ($parser->prsParse()) {
echo $parser->error_mes;
$transform = new Transform($str);
$transform->trfAriphmetic();
$transform->trfCompares();
$transform->trfCircles();
$transform->trfRemoveOther();
echo $transform->trfPrintResult();
} else {
echo $parser->error_mes;
}
} else {
echo $lexer->error_mess;
}
} else {
echo "Error: nocontent ...<br/>";
}
}
?>
Файл <compiller.php>
<?
class Compiller {
var
$path,
$link,
$source,
$files = array();
//--
function Compiller () {
$this->path = realpath(".");
$this->link = "http://".$
$this->source = $this->path."/
if ($dir = opendir($this->source)) {
while (false !== ($file = readdir($dir))) {
if ($file != "." && $file != "..") {
array_push($this->files,$this-
}
}
closedir($dir);
}
}
//--
function nextSourceFile () {
return array_pop($this->files);
}
//--
function printSourceCode ($str, $filename) {
$result = "<hr/><hr/><h3>Текст
исходного обрабатываемого
$result .= "<pre>".$str."</pre>";
$result .= "<hr/>";
Return $result;
}
//--
function readSourceFile ($file) {
return $str = @file_get_contents($file);
}
}
?>
Приложение 2
Файл <lexer_keyws.php>
<?
$lexer_keyws = array (
"keywords" => array (
"var" => array (
"regexp" => "\bvar\b",
"substr" => "var",
"matches" => array(),
),
"integer" => array (
"regexp" => "\binteger\b",
"substr" => "integer",
"matches" => array(),
),
"begin" => array (
"regexp" => "\bbegin\b",
"substr" => "begin",
"matches" => array(),
),
"end" => array (
"regexp" => "\bend",
"substr" => "end",
"matches" => array(),
),
"if" => array (
"regexp" => "\bif\b",
"substr" => "if",
"matches" => array(),
),
"then" => array (
"regexp" => "\bthen\b",
"substr" => "then",
"matches" => array(),
),
"else" => array (
"regexp" => "\belse\b",
"substr" => "else",
"matches" => array(),
),
"while" => array (
"regexp" => "\bwhile\b",
"substr" => "while",
"matches" => array(),
),
"do" => array (
"regexp" => "\bdo\b",
"substr" => "do",
"matches" => array(),
),
),
"identificators" => array (
"regexp" => "(\\$[\w|\d]*\b|[\d]+)",
"matches" => array(),
),
"delim" => array (
"notequal" => array (
"regexp" => "<>",
"matches" => array(),
),
"appoint" => array (
"regexp" => ":=",
"matches" => array(),
),
"equal" => array (
"regexp" => "=",
"matches" => array(),
),
"large" => array (
"regexp" => ">",
"matches" => array(),
),
"little" => array (
"regexp" => "<",
"matches" => array(),
),
"equalorlarge" => array (
"regexp" => ">=",
"matches" => array(),
),
"equalorlittle" => array (
"regexp" => "<=",
"matches" => array(),
),
"plus" => array (
"regexp" => "\+",
"matches" => array(),
),
"minus" => array (
"regexp" => "-",
"matches" => array(),
),
"star" => array (
"regexp" => "\*",
"matches" => array(),
),
"div" => array (
"regexp" => "\/",
"matches" => array(),
),
"twodots" => array (
"regexp" => ":",
"matches" => array(),
),
"dotandcomma" => array (
"regexp" => ";",
"matches" => array(),
),
"dot" => array (
"regexp" => "\.",
"matches" => array(),
),
"comma" => array (
"regexp" => ",",
"matches" => array(),
),
),
"comments" => array (
"slashnstar" => array (
"regexp" => "\/\*.*?\*\/",
"matches" => array(),
),
"slashes" => array (
"regexp" => "\/\/.*?\r",
"matches" => array(),
),
),
);
$lexer_preerrors = array (
"obligatory" => array (
"one" => array (
),
"more" => array (
"first" => array("key" => "keywords", "val" => "begin"),
"second" => array("key" => "keywords", "val" => "end"),
),
),
"pair" => array (
"equal" => array (
"terminators" => array (
"first" => array("key" => "keywords", "val" => "begin"),
"second" => array("key" => "keywords", "val" => "end"),
),
"cycle" => array (
"first" => array("key" => "keywords", "val" => "while"),
"second" => array("key" => "keywords", "val" => "do"),
),
"condition" => array (
"first" => array("key" => "keywords", "val" => "if"),
"second" => array("key" => "keywords", "val" => "then"),
),
),
"nomore" => array (
"condition" => array (
"first" => array("key" => "keywords", "val" => "if"),
"second" => array("key" => "keywords", "val" => "else"),
),
),
),
);
$lexer_text_errors = array (
"error" => " Компиляция на этапе лексического анализа завершилась неудачно, найдено @N@ ошибки(-ок).<hr/>",
"preerror" =>"На этапе лексического анализа были выявлены следующие ошибки:<br/>",
"noerror" => " Компиляция успешно прошла этап лексического анализа.<hr/>",
"unknown" => "@N@. Найден нераспознанный символ ['@key@'] в позиции @pos@.<br/>",
"obligatory" => array(
"one" => array(
"notfound" => "@N@. Не найдено ключевое слово ['@key@'], которое должно встречаться один.<br/>",
"moreone" => "@N@. Ключевое слово ['@key@'] встречается более одного раза, должно встречаться только один раз.<br/>",
),
"more" => "@N@. Не найдено ключевое слово ['@key@'], которое должно встречаться один или более раз",
),
"pair" => array(
"equal" => "@N@. Не найдено или найдено лишнее ключевое слово ['@key@'] в позиции @pos@.<br/>",
"nomore" => "@N@. Не найдено или найдено лишнее ключевое слово ['@key@'] в позиции @pos@.<br/>",
),
);
?>
Файл <lexer.php>
<?
class LeXer { // класс Лексера
var
$sourceString, // исходная строка
$resultString, // результрующая строка (не должна содержать символов после анализа)
$keyws, // массив шаблонов и совпадений ключевых слов, идентификаторов, комментариев, разделителей
$currentType, // массив текущего обрабатываемого шаблона (keywords, identificators, delim, comments)
$currentName,
// название текущего
$currentValue,
// массив, содержащий шаблон и
совпадения текущего
$currentPattern, // текущий обрабатываемый шаблон ("var", "<>", "\/\/.*?\r")
$preerrors, // заранее определенные ошибки (несовпадение пар либо объязательных символов)
$errors=array(), // массив с найденными ошибками
$text_errors, // массив сообщений об ошибках
$error_mess, // результирующие сообщение об ошибке
$count; // количество ошибок
//--
function LeXer ($string, $keyws, $preerrors, $lexer_text_errors) { // конструктор класса
$this->sourceString = $string;
$this->resultString = $string;
$this->keyws = $keyws;
$this->preerrors = $preerrors;
$this->text_errors = $lexer_text_errors;
$this->error_mess = "";
$this->count = 0;
}
//--
function lxGetPattern () { // достает шаблон (образец) для поиска по указанному элементу
if ($pattern = $this->currentValue['regexp']) {
if (is_array($pattern) ) {
$res=array();
foreach ($pattern as $pat) array_push($res, $pat);
return "'[".implode("|", $res)."]' si";
} else {
return "/".$pattern."/si";
}
}
return false;
}
//--
function lxListKeyws () { // сравнение шаблона со входным текстом, удаление совпадений из $resultString
if (($this->sourceString) && ($this->resultString) && ($this->currentPattern)) {
preg_match_all ($this->currentPattern, $this->sourceString, $matches);
if ($matches) {
foreach ($matches as $m) foreach ($m as $key=>$val) {
while (($strpos =
strpos($this->resultString, $this->currentValue['substr'])
if (!in_array($strpos,
$this->keyws['keywords'][$
$sourcelen = strlen($this->resultString);
$this->resultString = substr_replace ($this->resultString, "",$strpos, strlen($val));
array_push($this->keyws['
}
}
}
}
}
return false;
}
//--
function lxKeyws () { // поиск совпадений ключевых слов
$this->currentType = $this->keyws['keywords'];
foreach ($this->currentType as $keyValue => $valValue) {
$this->currentName = $keyValue; // название обрабатыываемого значения (if || for || array || // || ;)
$this->currentValue = $valValue; // само значение
$this->currentPattern = $this->lxGetPattern(); // само значение (рег выражение, массив совпадений)
$this->lxListKeyws();
}
}
//--
function lxRemoveComments () { // вырезание комментариев
$this->currentType = $this->keyws['comments'];
foreach ($this->currentType as $keyValue => $valValue) {
$this->currentName = $keyValue; // название обрабатыываемого значения (if || for || array || // || ;)
$this->currentValue = $valValue; // само значение
$this->currentPattern = $this->lxGetPattern(); // само значение (рег выражение, массив совпадений)
preg_match_all ($this->currentPattern, $this->sourceString, $matches);
if ($matches) {
foreach ($matches as $m) foreach ($m as $match) {
$strpos = strpos($this->resultString, $match);
if ($strpos !== false) {
if (!in_array($match, $this->keyws['comments'][$
$this->resultString = substr_replace ($this->resultString, "",$strpos, strlen($match));
array_push($this->keyws['
}
}
}
}
}
}
//--
function lxDelimeters () { // поиск разделителей
$this->currentType = $this->keyws['delim'];
foreach ($this->currentType as $keyValue => $valValue) {
$this->currentName = $keyValue;
$this->currentValue = $valValue;
$this->currentPattern = $this->lxGetPattern();
if ($this->currentPattern && $this->resultString) {
preg_match_all ($this->currentPattern, $this->resultString, $matches);
if ($matches) {
foreach ($matches as $m) foreach ($m as $match) {
$strpos = strpos($this->resultString, $match);
if ($strpos !== false) {
$this->resultString = substr_replace ($this->resultString, "",$strpos, strlen($match));
array_push($this->keyws['
}
}
}
}
}
}
//--
function lxIdentificators () { // отбражение результатов сканирования
$this->currentType = $this->keyws['identificators']
$this->currentName = 'identificators';
$this->currentValue = $this->currentType;
$this->currentPattern = $this->lxGetPattern();
if ($this->currentPattern && $this->sourceString) {
preg_match_all ($this->currentPattern, $this->sourceString, $matches);
if ($matches) {
foreach ($matches as $m) foreach ($m as $match) {
// echo "|".$match."|";
$strpos = strpos($this->resultString, $match);
if ($strpos !== false) {
$this->resultString = substr_replace ($this->resultString, "",$strpos, strlen($match));
array_push($this->keyws['
}
}
}
}
}
//--
function lxDiagnostics () { // поиск ошибок
//
preg_match_all ("/\S+?\s/si", $this->resultString, $matches); // поиск оставшихся ('неразобранных') слов
if ($matches) {
foreach ($matches as $m) foreach ($m as $match) {
$strpos = strpos($this->resultString, $match);
if ($strpos !== false) {
$this->count++;
$this->errors['unknown'][$
}
}
}
//
foreach ($this->preerrors['obligatory'
if (count($this->keyws[$val["key"
