Грамматика:

G({for, do, <, >, =, a, :=, (, ), ;}, {S, F, T, E}, P, S) с правилами P:

S → F;

F → for (T) do F│a:=a

T → F;E;F│;E;F│F;E;│;E;

E → a<a│ a>a│ a=a

 

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

 

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

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

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

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

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

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

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

 

       Конечный автомат задается пятеркой:

       M=(Q,S,d,q₀,F), где:

       Q - конечное множество состояний автомата;

       S - конечное множество допустимых входных символов;

       d – множество функций перехода автомата;

       q₀ÎQ - начальное состояние автомата;

       FÎQ - множество конечных состояний автомата.

       Работа  автомата выполняется по тактам. На каждом очередном такте i автомат, находясь в некотором состоянии q_iÎQ, считывает очередной символ vÎV из входной цепочки символов и изменяет свое состояние на q_i+1=d(q_i,v), после чего указатель в цепочке входных символов передвигается на следующий символ и начинается такт i+1. Так продолжается до тех пор, пока цепочка входных символов не закончится. Конец цепочки символов часто помечают особым символом ^. Считается также, что перед тактом 1 автомат находится в начальном состоянии q₀.

       Графически  автомат отображается нагруженным  однонаправленным графом, в котором  вершины представляют состояния, дуги отображают переходы  из одного состояния  в другое, а символы нагрузки (пометки) дуг соответствуют входному символу. Если функция перехода предусматривает переход из состояния 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);