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

Приложение В.  Исходный текст программы

 

Сhain.h

 

//Метод цепочек

#ifndef CHAIN_H

#define CHAIN_H

 

#include <QObject>

#include <QVector>

 

class Chain : public QObject

{

Q_OBJECT

 

public:

Chain();

void hashTableInit();

 

private:

struct idItem //элемент ТИ

{

QString text; //текст

int next; //указатель на следующий элемент

};

int getHash(QString); //получить hash

void addItem(int hash, QString myString);

QVector<int> hashTable;

QVector<idItem> idTable;

int cnt;

int nCnt;

int comparisonsCnt;

QString storeFileName;

double mediumComparisonsCnt;

int freePtr;

double totalTime;

double mediumTime;

 

private slots:

void addElement(QString);

void readFile(QString);

void findText(QString);

void findAll();

void resetCounters();

//  void setItems();

 

signals:

void setLabel(QString);

void sendItem(QString hash, QString left, QString right=0, int hasParent=0, QString parent=0);

 

};

 

#endif

 

Chain.cpp

 

#include "Chain.h"

#include <QFile>

#include <QMessageBox>

#include <QTextStream>

 

Chain::Chain()

{

resetCounters();

hashTableInit();

}

 

//добавить  элемент в таблицу идентификаторов

void Chain::addElement(QString text)

{

int hash = getHash(text);

    addItem(hash, text); //добавить элемент в ТИ

}

 

//получить hash = сумма 1го, 2го и последнего символов

int Chain::getHash(QString text)

{

int intCode = (unsigned int) text[0].toAscii();

 

if (text.size()>1)

{

intCode += (unsigned int) text[1].toAscii();

if (text.size()>2)

intCode += (unsigned int) text[2].toAscii();

else

intCode += (unsigned int) text[1].toAscii();

}

else

{

intCode += (unsigned int) text[0].toAscii();

intCode += (unsigned int) text[0].toAscii();

}

 

return intCode;

}

 

//добавление элемента  в ТИ

void Chain::addItem(int hash, QString text)

{

if (hashTable[hash]==-1) //если ячейка ХТ пуста

{

hashTable[hash]=freePtr;

}

else

{

int cur=hashTable[hash];

while(true)

{

if (idTable[cur].next==-1)

{

idTable[cur].next=freePtr;

break;

}

else

cur=idTable[cur].next;

}

}

Chain::idItem newItem; //создать новый элемент ТИ

newItem.next=-1;

newItem.text=text;

idTable.append(newItem); //добавить в ТИ

freePtr++;

}

 

//чтение файла

void Chain::readFile(QString fileName)

{

storeFileName = fileName; //запомним имя файла

QFile file(fileName); //файл

if (!file.open(QIODevice::ReadOnly | QIODevice::Text))

QMessageBox::critical(0, "Error", "Cannot open file for read", "OK");

 

QTextStream in(&file);

while (!in.atEnd()) //пока не конец файла

{

QString line = in.readLine(); //считываем очередную строку

    addElement(line); //посылаем строку для добавления втаблицу идентификаторов

}

QMessageBox::information(0, tr("Метод цепочек"), tr("Метод  цепочек:\nТаблица идентификаторов  успешно заполнена"), tr("ОК"));

}

 

//сбросить счетчики

void Chain::resetCounters()

{

cnt=0;

nCnt=0;

comparisonsCnt=0;

mediumComparisonsCnt=0;

hashTable.resize(500);

QString stringLabel;

stringLabel = QString(tr("Сравнений: %1\nВсего сравнений: %2\nВ среднем сравнений: %3").arg(comparisonsCnt).arg(cnt).arg(mediumComparisonsCnt));

emit setLabel(stringLabel);

}

 

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

void Chain::hashTableInit()

{

freePtr=0;

for (int i=0;i<500;i++)

hashTable[i]=-1; //забиваем ХТ нулями

idTable.clear(); //очищаем ТИ

}

 

//поиск текста

void Chain::findText(QString text)

{

comparisonsCnt=0;

nCnt++;

bool flag=0;

int hash = getHash(text);

if (hashTable[hash]==-1)

{

QMessageBox::warning(0, "Error", tr("Строка '%1' не найдена").arg(text), "OK");

return;

}

int next = hashTable[hash];

while (true)

{

int cur = next;

comparisonsCnt++; //счетчик сравнений

if (idTable[cur].text==text)

{

//   QMessageBox::information(0, "OK", tr("Строка '%1' успешно найдена на '%2' шаге").arg(text).arg(comparisonsCnt), "OK");

break;

}

if (idTable[cur].next==-1)

{

QMessageBox::warning(0, "Error", tr("Строка '%1' не найдена").arg(text), "OK");

return;

}

else

next = idTable[cur].next;

}

cnt+=comparisonsCnt; //всего сравнений

mediumComparisonsCnt = (double) cnt / (double) nCnt; //в среднем сравнений

QString stringLabel;

stringLabel = QString(tr("Сравнений: %1\nВсего сравнений: %2\nВ среднем сравнений: %3").arg(comparisonsCnt).arg(cnt).arg(mediumComparisonsCnt));

emit setLabel(stringLabel);

}

 

//найти все идентификаторы

void Chain::findAll()

{

resetCounters(); //сбросить счетчики

QFile file(storeFileName); //файл

if (!file.open(QIODevice::ReadOnly | QIODevice::Text))

QMessageBox::critical(0, "Error", tr("Невозможно  открыть файл на чтение"), "OK");

 

QTextStream in(&file);

while (!in.atEnd()) //пока не конец

{

QString line = in.readLine(); //считываем очередную строку

    findText(line); //ищем строку в ТИ

}

}

 

 

ReHash.h

 

#ifndef REHASH_H

#define REHASH_H

 

#include <QObject>

#include <QVector>

 

class ReHash : public QObject

{

Q_OBJECT

 

public:

ReHash();

void hashTableInit();

 

private:

int getHash(QString); //получить hash

//  void getTree(int hash, QString myString);

QVector<QString> hashTable;

int cnt;

int nCnt;

int comparisonsCnt;

QString storeFileName;

double mediumComparisonsCnt;

//  void ReHash::getChilds(treeNode* parentNode);

QVector<int> randList;

void generateRandList();

 

private slots:

void addElement(QString);

void readFile(QString);

void findText(QString);

void findAll();

void resetCounters();

//  void setTreeItems();

 

signals:

void setLabel(QString);

//  void sendTreeItems(QString hash, QString left, QString right=0, int hasParent=0, QString parent=0);

 

};

 

#endif

 

 

ReHash.cpp

 

#include "ReHash.h"

#include <QFile>

#include <QMessageBox>

#include <QTextStream>

#include <stdlib.h>

 

 

ReHash::ReHash()

{

resetCounters();

hashTableInit();

generateRandList();

}

 

//генерация списка псевдослучаных чисел

void ReHash::generateRandList()

{

for (int i=0; i<1000; i++)

{

int random=rand();

randList.append(random); //добавляем в список псевдослучайное число

}

}

 

//добавить элемент  в таблицу идентификаторов

void ReHash::addElement(QString text)

{

int hash = getHash(text);

if (hashTable[hash].isEmpty()) //если ячейка по адресу hash пуста, добавляем элемент

{

hashTable[hash]=text;

}

else //иначе применяем рехэширование

{

int maxHash = 1000; //делаем с запасом максимальный хэш

int hi=0;

for (int i=0; i<1000; i++)

{

//hi = (hash + randList[i]) mod maxHash;

hi = (hash + randList[i]);

int mod =  (int) hi/maxHash;

mod = hi - mod*maxHash;

if (hashTable[mod].isEmpty()) //если ячейка по адресу mod пуста

{

hashTable[mod]=text; //добавляем элемент

break; //выходим из цикла

}

}

}

}

 

//получить hash = сумма  1го, 2го и последнего символов

int ReHash::getHash(QString text)

{

int intCode = (unsigned int) text[0].toAscii();

 

if (text.size()>1)

{

intCode += (unsigned int) text[1].toAscii();

if (text.size()>2)

intCode += (unsigned int) text[2].toAscii();

else

intCode += (unsigned int) text[1].toAscii();

}

else

{

intCode += (unsigned int) text[0].toAscii();

intCode += (unsigned int) text[0].toAscii();

}

 

return intCode;

}

 

//чтение файла

void ReHash::readFile(QString fileName)

{

storeFileName = fileName; //запомним имя файла

QFile file(fileName); //файл

if (!file.open(QIODevice::ReadOnly | QIODevice::Text))

QMessageBox::critical(0, "Error", "Cannot open file for read", "OK");

 

QTextStream in(&file);

while (!in.atEnd()) //пока не конец файла

{

QString line = in.readLine(); //считываем очередную строку

    addElement(line); //посылаем строку для добавления втаблицу идентификаторов

}

QMessageBox::information(0, tr("Рехэширование"), tr("Рехэширование  с псевдослучайными числами:\nТаблица идентификаторов успешно заполнена"), tr("ОК"));

}

 

//сбросить счетчики

void ReHash::resetCounters()

{

cnt=0;

nCnt=0;

comparisonsCnt=0;

mediumComparisonsCnt=0;

QString stringLabel;

stringLabel = QString(tr("Сравнений: %1\nВсего сравнений: %2\nВ среднем сравнений: %3").arg(comparisonsCnt).arg(cnt).arg(mediumComparisonsCnt));

emit setLabel(stringLabel);

}

 

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

void ReHash::hashTableInit()

{

hashTable.resize(1000);

for (int i=0;i<1000;i++)

{

hashTable[i].clear(); //очищаем ТИ

}

}

 

//поиск текста

void ReHash::findText(QString text)

{

comparisonsCnt=0;

nCnt++;

int hash = getHash(text);

comparisonsCnt++; //счетчик сравнений

if (hashTable[hash].isEmpty()) //если ячейка по адрему hash пуста, элемент не найден

{

QMessageBox::warning(0, "Error", tr("Строка '%1' не найдена").arg(text), "OK");

return;

}

else if (hashTable[hash]==text) //если текст совпал, элемент найден

{

 

}

else //иначе применяем рехэширование

{

int maxHash = 1000; //делаем с запасом максимальный хэш

int hi=0;

for (int i=0; i<1000; i++)

{

comparisonsCnt++;

//hi = (hash + randList[i]) mod maxHash;

hi = (hash + randList[i]);

int mod =  (int) hi/maxHash;

mod = hi - mod*maxHash;

if (mod>999)

QMessageBox::warning(0, "Error", tr("Ахтунг Ахтунг! mod=%1").arg(mod), "OK");

if (hashTable[mod].isEmpty()) //если ячейка по адресу mod пуста

{//элемент не найден

QMessageBox::warning(0, "Error", tr("Строка '%1' не найдена").arg(text), "OK");

return;

}

else if (hashTable[mod]==text) //если текст совпал, то элемент найден

{

break; //выходим из цикла

}

}

}

 

cnt+=comparisonsCnt; //всего сравнений

mediumComparisonsCnt = (double) cnt / (double) nCnt; //в среднем сравнений

QString stringLabel;

stringLabel = QString(tr("Сравнений: %1\nВсего сравнений: %2\nВ среднем сравнений: %3").arg(comparisonsCnt).arg(cnt).arg(mediumComparisonsCnt));

emit setLabel(stringLabel);

}

 

//найти все идентификаторы

void ReHash::findAll()

{

resetCounters(); //сбросить счетчики

QFile file(storeFileName); //файл

if (!file.open(QIODevice::ReadOnly | QIODevice::Text))

QMessageBox::critical(0, "Error", "Cannot open file for read: %1", "OK");

 

QTextStream in(&file);

while (!in.atEnd()) //пока не конец

{

QString line = in.readLine(); //считываем очередную строку

    findText(line); //ищем строку в ТИ

}

}

 

 

 

LexFSM.h

 

#ifndef LEXFSM_H

#define LEXFSM_H

 

#include <QObject>

#include <QString>

#include <QMap>

class QList;

 

class LexFSM : public QObject

{

Q_OBJECT

 

public:

LexFSM();

 

enum stateName

{

START, //начальное состояние

ID, //переменная

CONSTANT, //константа

SEPARATOR, //разделитель (;)

ERROR,

P, PR, PRO, PROG, PROGR, PROGRA, PROGRAM, //program

E, EN, END, //end

    ENDD, //end.

ENDI, ENDIF, //endif

   EL, ELS, ELSE, //else

I, IF, //if

T, TH, THE, THEN, //then

B, BE, BEG, BEGI, BEGIN, //begin

A, AN, AND, //and

O, OR, //or

N, NO, NOT, //NOT

LBRACKET, // (

  LASTER, RASTER, COMMENT, //комментарий (* *)

RBRACKET, // )

ADD, // +

SUB, // -

EQUAL, // =

LESS, // <

  NONEQUAL, // <>

  LSHIFT, // << - дополнительная операция

MORE, // >

  RSHIFT, // >> - дополнительная операция

TWOSPOT, ASSIGN, // :=

FINITE, //конечное состояние

STOP,

 

//дополнительные  состояния, соответствующие варианту  задания

F, FO, FOR, //for

D, DO, //do

       DOW, DOWN,DOWNT, DOWNTO //downto

};

 

private:

QChar cReserved;

QString lexeme;

stateName state;

void setNextState(stateName);

QString stateString(LexFSM::stateName name);

QString finiteStateString(LexFSM::stateName name);

QList<QChar> idFiniteList;

 

private slots:

void startFSM();

void analyseNextChar(QChar c);

 

signals:

void getNextChar();

void lexError();

void addNewTableItem(QString);

void setAddLexeme(QString, QString, QString type);

void sendLog(QString text, QString description);

};

 

#endif

 

LexFSM.cpp

 

#include "LexFSM.h"

#include <QFile>

#include <QMessageBox>

#include <QTextStream>

#include <QChar>

#include <QList>

 

//Конечный автомат

LexFSM::LexFSM()

{

emit sendLog(tr("Модуль LexFSM подключен"), "MESSAGE");

state=START;

}

 

//Запуск автомата

void LexFSM::startFSM()

{

//Допустимые символы,  следующие за переменными

idFiniteList<<' '<<'\n'<<'\0'<<':'<<';'<<'('<<')'<<'>'<<'<'<<'+'<<'-'<<'=';

 

state=START;

emit sendLog(tr("Начало работы лексического анализатора"), "END");

emit sendLog(tr("Запуск конечного автомата"), "END");

getNextChar();//Запросить входной символ

}

 

//Переход в новое состояние

void LexFSM::setNextState(LexFSM::stateName nextState)

{

if (state==STOP) //Если автомат остановлен, стоять

{

}

else

{

emit sendLog(tr("Переход из состояния %1 в %2").arg(stateString(state)).arg(stateString(nextState)), "EVENT");

if (nextState==STOP)//Остановка автомата

{

lexeme=lexeme.remove(QChar('\0'));

lexeme=lexeme.remove(QChar(65534));

if (!lexeme.simplified().isEmpty())

emit setAddLexeme(lexeme.simplified(), finiteStateString(state), stateString(state));

state=STOP;

emit sendLog(tr("Остановка конечного автомата"), "END");

emit sendLog(tr("Выполнение лексического анализа успешно завершено"), "END");

}

 

else if (nextState==FINITE) //Если конечное состояние

{

lexeme=lexeme.remove(QChar('\0'));

if (state==COMMENT) //Если обнаружен комментарий

{

emit sendLog(tr("Проигнорирован комментарий: %1").arg(lexeme.simplified()), "COMMENT");

lexeme="";

}

else if (state==CONSTANT)

{

bool constOk;

int cst=lexeme.simplified().toInt(&constOk, 2);

if ((!constOk) || (cst<0) || (cst>255))

{

QMessageBox::critical(0, "CONSTANT ERROR", tr("Ошибочная константа %1!\nКонстанты типа Byte  - это беззнаковое целое от 0 до 255!").arg(cst), "OK");

setNextState(ERROR);

return;

}

else

{

emit setAddLexeme(lexeme.simplified(), finiteStateString(state), stateString(state));

emit sendLog(tr("Добавление новой строки: %1 (%2)").arg(lexeme.simplified()).arg(finiteStateString(state)), "END");

lexeme="";

}

}

else //Обнаружена новая лексема

{

 

emit setAddLexeme(lexeme.simplified(), finiteStateString(state), stateString(state));

emit sendLog(tr("Добавление новой строки: %1 (%2, %3)").arg(lexeme.simplified()).arg(finiteStateString(state)).arg(stateString(state)), "END");

lexeme="";

}

 

state=START; //Сброс автомата в начальное состояние

emit sendLog(tr("Новое состояние: %1").arg(stateString(state)), "MESSAGE");

analyseNextChar(cReserved); //Повторный анализ символа, приведшего в переходу в конечное состояние

}

 

else if ((state!=nextState) && (nextState==ID)) //переход в состояние идентификатора

{

state=ID;

emit sendLog(tr("Новое состояние: %1").arg(stateString(state)), "MESSAGE");

analyseNextChar(cReserved);

}

 

else if (nextState==ERROR) //Ошибка

{

emit sendLog(tr("Лексическая ошибка!"), "ERROR");

emit lexError();

state=ERROR;

emit sendLog(tr("Новое состояние: %1").arg(stateString(state)), "MESSAGE");

setNextState(STOP);

}

 

else //Обычный переход

{

lexeme.append(cReserved); //добавление символа в цепочку

state=nextState;

emit sendLog(tr("Новое состояние: %1").arg(stateString(state)), "MESSAGE");

emit getNextChar();//Запросить следующий символ

}

}

 

}

 

//Названия  состояний, использующиеся для лога

QString LexFSM::stateString(LexFSM::stateName name)

{

QString string="";

switch(name)

{

case START:

string="START";

break;

case ID:

string="ID";

break;

case CONSTANT:

string="CONSTANT";

break;

case SEPARATOR:

string="SEPARATOR";

break;

case ERROR:

string="ERROR";

break;

case P:

string="P";

break;

case PR:

string="PR";

break;

case PRO:

string="PRO";

break;

case PROG:

string="PROG";

break;

case PROGR:

string="PROGR";

break;

case PROGRA:

string="PROGRA";

break;

case PROGRAM:

string="PROGRAM";

break;

case E:

string="E";

break;

case EN:

string="EN";

break;

case END:

string="END";

break;

case ENDD:

string="ENDD";

break;

case ENDI:

string="ENDI";

break;

case ENDIF:

string="ENDIF";

break;

case EL:

string="EL";

break;

case ELS:

string="ELS";

        break;

case ELSE:

string="ELSE";