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

ЛИЧНЫЙ КАБИНЕТ 

 

Здравствуйте гость!

 

Логин:

Пароль:

 

Запомнить

 

 

Забыли пароль? Регистрация

Повышение уникальности

Предлагаем нашим посетителям воспользоваться бесплатным программным обеспечением «StudentHelp», которое позволит вам всего за несколько минут, выполнить повышение уникальности любого файла в формате MS Word. После такого повышения уникальности, ваша работа легко пройдете проверку в системах антиплагиат вуз, antiplagiat.ru, etxt.ru или advego.ru. Программа «StudentHelp» работает по уникальной технологии и при повышении уникальности не вставляет в текст скрытых символов, и даже если препод скопирует текст в блокнот – не увидит ни каких отличий от текста в Word файле.

Результат поиска


Наименование:


лабораторная работа Таблица идентификаторов. Проектирование лексического анализатора

Информация:

Тип работы: лабораторная работа. Добавлен: 26.04.2012. Сдан: 2011. Страниц: 23. Уникальность по antiplagiat.ru: < 30%

Описание (план):


ФЕДЕРАЛЬНОЕ АГЕНТСТВО МОРСКОГО И РЕЧНОГО ТРАНСПОРТА  
РОССИЙСКОЙ ФЕДЕРАЦИИ
 

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ  ОБРАЗОВАТЕЛЬНОЕ  УЧРЕЖДЕНИЕ ВЫСШЕГО  ПРОФЕССИОНАЛЬНОГО  ОБРАЗОВАНИЯ 

САНКТ-ПЕТЕРБУРГСКИЙ  ГОСУДАРСТВЕННЫЙ  УНИВЕРСИТЕТ
ВОДНЫХ  КОММУНИКАЦИЙ
 
Факультет информационных технологий
 
Кафедра вычислительных систем и информатики
 
 
 
ЯЗЫКИ ПРОГРАММИРОВАНИЯ
 
 
 
 
 
Лабораторная  работа 1, 2
 
 
Таблица идентификаторов.
Проектирование  лексического анализатора
 
 
 
 
 
 
 
 
 
 
Выполнила: студент группы ИП-31
 
 
     Проверила :Крупенина Н.В.
 
 
 
 
 
 
 
 
2010 г.
 

Оглавление
 

Введение

 
       Компилятор  – программный модуль, задачей которого является перевод программы, написанной на одном из языков программирования (исходный язык) в программу на языке ассемблера или языке машинных команд.
       Целью данной курсовой работы является изучение составных частей, основных принципов построения и функционирования компилятора, практическое освоение методов построения составных частей компилятора для заданного входного языка.
       Курсовая работа заключается в реализации отдельных фаз компиляции заданного языка.
       В первой части работы требуется разработать программный модуль, который получает на входе набор идентификаторов, организует таблицу идентификаторов по заданным методам и позволяет осуществить многократный поиск идентификатора в этой таблице. Программа должна подсчитывать число коллизий и среднее количество сравнений, выполняемых для поиска идентификатора.
       Во  второй части работы требуется разработать программный модуль, выполняющий лексический анализ входного текста по заданной грамматике и порождающий таблицу лексем с указанием их типов.
       В качестве среды разработки для реализации приложения использован язык программирования С++ и система программирования MS Visual C++ v.6.
 

Организация таблицы идентификаторов

         Исходные данные

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

         Назначение таблиц идентификаторов

 
       Проверка  правильности семантики и генерация кода требуют знания характеристик идентификаторов, используемых в программе на исходном языке. Эти характеристики выясняются из описаний и из того, как идентификаторы используются в программе и накапливаются в таблице символов, или таблице идентификаторов. Любая таблица идентификаторов состоит из набора полей, количество которых равно числу идентификаторов программы. Каждое поле содержит в себе полную информацию о данном элементе таблицы. Под идентификаторами подразумеваются константы, переменные, имена процедур и функций, формальные и фактические параметры.
       В данной работе сравниваются два метода организации таблицы идентификаторов: метод простого рехэширования и метод цепочек.
       Данные  методы основаны на хеш-адресации, то есть на использовании значения, возвращаемого хеш-функцией, в качестве адреса ячейки из некоторого массива данных. Хеш-функция вычисляется путем выполнения над цепочкой символов некоторых простых арифметических и логических операций. Самой простой хеш-функцией для символа является ASCII-код символа.
       В данной курсовой работе принята хэш-функция - сумма ASCII-кодов первых, среднего и последнего символов цепочки.
       При хэш-адресаци возможна ситуация, когда  двум или более идентификаторам  соответствует одно и то же значение хэш-функции. Такая ситуация называется коллизией. Сравниваемые в данной работе методы организации таблицы идентификаторов - простого рехэширования и метод цепочек - отличаются по способу разрешения коллизий. Ниже каждый метод рассмотрен подробнее.
 

          Метод простого рехэширования

 
       Согласно  данному методу, если для элемента А адрес п() = h(A), указывает на уже занятую ячейку, то есть в случае возникновения коллизии, необходимо вычислить значение функции n1 = h1(A) и проверить занятость ячейки по адресу n1. Если и она занята, то вычисляется значение h2(A). И так до тех пор, пока либо не будет найдена свободная ячейка, либо очередное значение hi(A) не совпадет с h(A). В последнем случае считается, что таблица идентификаторов заполнена и места в ней больше нет - выдается сообщение об ошибке размещения идентификатора в таблице.
      Согласно  методу простого рехэширования, hi(A) = (h(A)+i) mod Nm, где Nm- максимальное значение хэш-функции.
       В данной курсовой работе принята хэш-функция - сумма ASCII-кодов первых двух символов цепочки, максимальное значение хэш-функции равно 512.
       Поскольку при заполнении таблицы идентификаторов  основными операциями являются добавление элемента в таблицу и поиск  элемента в ней, на рис. 1 и рис. 2 представлены блок-схемы этих операций для рассматриваемого метода.
 
 

       
Рис. 1.  Блок-схема добавления элемента в таблицу идентификаторов по методу простого рехэширования
 
      
Рис. 2.  Блок-схема алгоритма поиска элемента в таблице идентификаторов, организованной по методу простого рехэширования

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

 
       Можно сократить время поиска искомого элемента в таблице идентификаторов, не увеличивая значительно время, необходимое  на ее заполнение. Для этого надо отказаться от организации таблицы в виде непрерывного массива данных.
       Существует  метод построения таблиц, при котором  таблица имеет форму бинарного  дерева. Каждый узел дерева представляет собой элемент таблицы, причем корневой узел является первым элементом, встреченным при заполнении таблицы.
       Для данного метода число требуемых  сравнений и форма получившегося  дерева во многом зависят от того порядка, в котором поступают идентификаторы.
       Если  предположить, что последовательность идентификаторов в исходной программе является статистически неупорядоченной (что в целом соответствует действительности), то можно считать, что построенное бинарное дерево будет невырожденным. Тогда среднее время на заполнение дерева (ТЗ) и на поиск элемента в нем (ТП) можно оценить следующим образом:
       ТЗ = N*О(log2 N).
       TП  = О(log2 N).
       В целом метод бинарного дерева является довольно удачным механизмом для организации таблиц идентификаторов. Он нашел свое применение в ряде компиляторов. Иногда компиляторы строят несколько различных деревьев для идентификаторов разных типов и разной длины.
 

Блок-схема  принципа работы бинарного дерева

Рис. 1. 1 – Блок-схема метода бинарного  дерева; а) – Блок-схема алгоритма метода бинарного дерева; б) – Блок-схема функции добавления идентификатора;
в) – Блок-схема функции поиска идентификатора
 

Результаты  работы программы:

 
 
Из данного  примера видно, что метод рехеширования  для поиска идентификаторов эффективнее  в 5 раз.
 
 

Следующий результат приведён для поиска всех идентификаторов.
 

 
Входной файл содержит 39 идентификаторов:
 

bbbb
bbbbbb
bbbbbbbbbbb
bbbbbbbbbbbbb
bbbbb
uygygbhk
b
aaa
aaaa
aaaaa
cccccc
cccccccc
ergeg
 
etgtrhr
txt
texet
teeexeeet
gersgtpekh
shryrphjlksrpjlks
ryjsrpyjkrsypkj
rsyjpkrsypjk
ffff
fffff
fddffffffff
fewrgleprgl
ewthorjksohk
 
e
bbbbbbbb
bbbbbbb
bbbbbbbbb
sthosrkhoe
hrtohkrtokh
setjhkgjseth
sehtsert
hsethsethsrtbvtsrhb
resthsrh
srthsrhg
brsh
ggg  
 

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

Проектирование  лексического анализатора

  Исходные данные

 
      Для выполнения данной части курсовой работы требуется написать программу, которая выполняет лексический анализ входного текста в соответствии с заданием и порождает таблицу лексем с указанием их типов и значений. Текст на входном языке задан в виде текстового файла. Программа должна выдавать сообщения о наличие во входном тексте ошибок, которые могут быть обнаружены на этапе лексического анализа. Программа должна допускать наличие комментариев неограниченной длины во входном файле.
      В соответствии с заданием должны распознаваться:
    - ключевые слова : «for», «do»
    - идентификаторы: любые последовательности латинских символов и цифр; идентификатор должен начинаться с символа;
    - константы: целые, десятичные числа в экспоненциальной форме и с плавающей точкой;
    - знаки операций: «=», «<»,«>»
    - оператор присваивания: «:=»;
    - разделитель: «;»;
      - комментарии, заключенные в «/*», «*/».
      Грамматика:
G({for, do, <, >, =, a, :=, (, ), ;}, {S, F, T, E}, P, S) с правилами P:
S > F;
F > for (T) doa:=a
T > F;E;;E;F¦F;E;¦;E;
E > a<a¦ a>a¦ a=a
 

  Принципы работы лексического анализатора

 
      Лексический анализатор (или сканер) - это часть  компилятора, которая читает литеры программы на исходном языке и  строит из них слова (лексемы) исходного  языка. На вход лексического анализатора  поступает текст исходной программы, а выходная информация передается для дальнейшей обработки компилятором на этапе синтаксического анализа и разбора.
      С теоретической точки зрения лексический  анализатор не является обязательной, необходимой частью компилятора. Его  функции могут выполняться на этапе синтаксического разбора. Однако существует несколько причин, исходя из которых в состав практически всех компиляторов включают лексический анализ. Эти причины заключаются в следующем:
    упрощается работа с текстом исходной программы на этапе синтаксического разбора и сокращается объем обрабатываемой информации, так как лексический анализатор структурирует поступающий на вход исходный текст программы и выкидывает всю незначащую информацию;
    для выделения в тексте и разбора лексем возможно применять простую, эффективную и теоретически хорошо проработанную технику анализа, в то время как на этапе синтаксического анализа конструкций исходного языка используются достаточно сложные алгоритмы разбора;
    сканер отделяет сложный по конструкции синтаксический анализатор от работы непосредственно с текстом исходный программы, структура которого может варьироваться в зависимости от версии входного языка - при такой конструкции компилятора при переходе от одной версии языка к другой достаточно только перестроить относительно простой сканер.
      Функции, выполняемые лексическим анализатором, и состав лексем, которые он выделяет в тексте исходной программы, могут  меняться в зависимости от версии компилятора. В основном лексические  анализаторы выполняют исключение из текста исходной программы комментариев и незначащих пробелов, а также выделение лексем следующих типов: идентификаторов, строковых, символьных и числовых констант, ключевых (служебных) слов входного языка.
       В простейшем случае фазы лексического и синтаксического анализа могут выполняться компилятором последовательно. Но для многих языков программирования информации на этапе лексического анализа может быть недостаточно для однозначного определения типа и границ очередной лексемы.
       Поскольку в данной курсовой работе входной язык является регулярным и может быть задан с помощью регулярной грамматики, распознавателем  для него будет служить конечный автомат.
      Вид представления информации после  выполнения лексического анализа целиком  зависит конструкции компилятора. Но в общем виде ее можно представить как таблицу лексем, которая в каждой строчке должна содержать информацию о виде лексемы, ее типе и, возможно, значении. Обычно такая таблица имеет два столбца: первый – строка лексемы, второй – указатель на информацию о лексеме, может быть включен и третий столбец – тип лексем.
 
       Конечный автомат задается пятеркой:
       M=(Q,S,d,q0,F), где:
       Q - конечное множество состояний автомата;
       S - конечное множество допустимых входных символов;
       d – множество функций перехода автомата;
       q0IQ - начальное состояние автомата;
       FIQ - множество конечных состояний автомата.
       Работа  автомата выполняется по тактам. На каждом очередном такте i автомат, находясь в некотором состоянии qiIQ, считывает очередной символ vIV из входной цепочки символов и изменяет свое состояние на qi+1=d(qi,v), после чего указатель в цепочке входных символов передвигается на следующий символ и начинается такт i+1. Так продолжается до тех пор, пока цепочка входных символов не закончится. Конец цепочки символов часто помечают особым символом ^. Считается также, что перед тактом 1 автомат находится в начальном состоянии q0.
       Графически  автомат отображается нагруженным  однонаправленным графом, в котором  вершины представляют состояния, дуги отображают переходы  из одного состояния  в другое, а символы нагрузки (пометки) дуг соответствуют входному символу. Если функция перехода предусматривает переход из состояния q в q’ по нескольким символам, то между ними строится одна дуга, которая помечается всеми символами, по которым происходит переход из q в q’.

  Схема распознавателя

 
       Граф  конечного автомата
 
 
       Начальное состояние автомата на рисунке обозначено "h". В случае ошибочной входной цепочки автомат попадает в состояние ошибки e. При этом работа автомата останавливается.
       Кроме того, типичными для автомата являются состояния a (переменная) и O (константа). Остальные состояния автомата определяются допустимыми для компилятора исходного языка лексемами.
       Каждый  переход в конечное состояние  "h" сообщает о конце текущей входной цепочки. В этом случае производится анализ распознанной цепочки и перезапуск автомата для очередной входной цепочки символов.
 

  Результат работы лексического анализаора

 
       На  входе была получена строка
       for ( abc = 10.5E-1 ; i < 0 ; i > oo ) do /* kommentarii g:=5; */
       bom := 10.5 ;
       n := 45.7*10-3 ;
       34.67E+3 ;
 
       В ходе выполнения программы получились следующие результаты

 
Лексический анализатор распознал входную строку и распределил входные лексемы. Комментарии игнорируются.
 

Если  в программе присутсвуют ошибки, то при определении ошибки лексический анализатор прекращает свою работу с сообщением об ошибке.
 
Пример  входной строки с ошибкой:
for ( abc = 10.5EE-1 ; i < 0 ; i > oo ) do /* kommentarii g:=5; */
bom := 10.5 ;
n := 45.7*10-3 ;
34.67E+3

 

Приложение

Код программы организации таблицы идентификаторов:

/***/
CString ToString(int dig){
 const size_t newsize = 100;
 char nstring[newsize];
 itoa(dig,nstring, 10);
 CString cstring(nstring);
 
return cstring;
}
void CLabaDlg::OnButload()
{
UpdateData(TRUE);
 int k;
 TCHAR    szBuffer[dim*256];
 CFile inputf;
 inputf.Open(m_EditFile, CFile::modeRead);
 inputf.Read(szBuffer, sizeof(szBuffer));
 k=inputf.GetLength();
 int id, id2;
 a=0;
 CString string;
 int i=0; int j=0;
 while (szBuffer[i]>0){
 while ((szBuffer[i]!='\n')&&(i<k+1)) {
 string+=szBuffer[i];
 i++;
 }
 j=0;
 cntr=0;
 j=string.GetLength();
 string.Delete(j-1, 1);
 id=hash(string);
 id2=id;
 bool flag=false;
 while ((cntr<dim)&&(!flag)) {
 if (table[id]=="p") {table[id]=string; flag=true;}
 else {
 cntr+=1; id=rehs(id2, cntr);
 }
 }
 m_ListB.AddString(string);
 arr[a]=string;
 i++; a++; cntr=0;
 string="";  
 }
 UpdateData(false);
}
void CLabaDlg::OnDblclkList1()
{
 UpdateData(TRUE);
 int k;
 k=m_ListB.GetCurSel();
 m_ListB.GetText(k, m_Edd);
 UpdateData(false);
 
}
struct Node{
CString d;
Node *left;
Node *right;
};
int counter=0;
int result=0;
Node * search_insert(Node *root, CString d){
Node *pv=root, *prev;
bool found = false;
while (pv && !found){
 prev = pv;
 if (d==pv->d) {found=true;}
 else
 if   (d <pv->d) {pv= pv->left; }
 else { pv=pv->right;}
}
if (found) return pv;
Node *pnew  = new Node;
pnew->d = d;
pnew->left = 0;
pnew->right = 0;
if (d < prev->d)
prev->left =pnew;
else prev->right=pnew;
return pnew;
}
 
Node *first(CString d){
 Node *pv = new Node;
 pv->d=d;
 pv->left = 0;
 pv->right=0;
 return pv;
};
int itog=-1;
void findsimb(Node *p, int level, CString s, bool flag){
 if (!p) {
 flag=false;
 result=-1;}//m_Tree="NO";
 if ((!flag)&&(p))
 if (strcmp(s,p->d)==0) {flag=true;
 result+=1;itog+=1;}//
 else
  if ((strcmp(s,p->d)) < 0){result+=1; itog+=1;
  findsimb(p->left, level+1, s, flag);}
  else
 if ((strcmp(s,p->d)) > 0) {result+=1;itog+=1;
 findsimb(p->right, level+1, s, flag);}
 };
 
void CLabaDlg::OnButsearch()
{
//TREEE
 UpdateData(TRUE);
Node * search_insert(Node *root, CString d);
 Node *root = first(arr[0]);
 for (int i = 1; i<dim; i++)
 search_insert(root, arr[i]);
 CString simb=m_Edd;
 bool flag=false;
 findsimb(root, 0, simb, flag);
 if (result==-1) m_Tree="no found!"; else
 {m_Tree="comparisons "+(ToString(result));
 totaltree+=result;
 }
 flag=false;
 m_Statall="all comparisons "+(ToString(totaltree));
 
//Hash-Rehash//////////////////
 int id, id2;
 simb=m_Edd;
 id=hash(simb);
 id2=id;
 flag=false;
 cntr=0;
 compare=0;
 double a,b;
 while ((cntr<dim)&&(!flag)) {
 total+=1;
 compare+=1;
 if ((table[id]!="p")&&(table[id]==simb))
           {m_StatHash="FIND!!!!"; flag=true;
            m_StatCompare="comparisons " +ToString(compare);
            m_StatAll2="all comparisons " +ToString(total);
            a=compare; b=total;
            hsh=(a/b);
            a=result; b=totaltree;
            tre=(a/b);
            if (hsh<1) {
            m_StatHash=DoubleToString(hsh);
            m_StatMid=DoubleToString(tre);}
            else {m_StatHash=ToString(hsh);
            m_StatMid=ToString(tre);
            }
 cntr+=1;
 
 }
 else {cntr+=1; id=rehs(id2, cntr);}
 }
 result=0;
 if (!flag) {m_StatHash="no found!!!!"; m_Statall="";};
 UpdateData(false);
 };
 
void CLabaDlg::OnCancelBut()
{
 UpdateData(true);
 total=0;
 compare=0;
 itog=0;
 totaltree=0;
 m_StatAll2="all comparisons 0";
 m_StatHash="0";
 m_StatCompare="comparisons";
 m_Tree="comparisons";
 m_Statall="all comparisons 0";
и т.д.................


Перейти к полному тексту работы


Скачать работу с онлайн повышением уникальности до 90% по antiplagiat.ru, etxt.ru или advego.ru


Смотреть полный текст работы бесплатно


Смотреть похожие работы


* Примечание. Уникальность работы указана на дату публикации, текущее значение может отличаться от указанного.