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

{

QString text;

QString type;

int stringNumber;

};

struct synTreeItem

{

QString text;

QVector<synTreeItem*> childItems;

};

struct stackItem

{

QString text;

QString value;

synTreeItem* node;

};

synTreeItem* rootTreeItem;

synTreeItem* treeItem;

synTreeItem* treeItemChild;

QChar matrix[29][29];

QString rules[29];

lexemeDescription lexDesc;

QVector<lexemeDescription> lexemes;

QMap<QString, int> identifiers;

QStack<stackItem> stack;

stackItem sItem;

int stackSize;

int lexemesPos;

int stackPos;

void createMatrix();

void createRules();

int maxRuleLength;

void start();

QChar getMatrixValue(QString tTerm, QString fLex);

void shift(); //сдвиг

void reduce(); //свертка

QString getTopTerm();

int getTermNum(QString text);

QString topTerm;

QString curLex;

QString curRule;

QString SynAnalyser::getStackItemText();

 

signals:

void sendLog(QString, QString);

void setRedLine(int);

void setRootItem(synTreeItem*);

 

private slots:

void setError(int stringNumber);

void getLexemes(QVector<lexemeDescription>);

void getIdentifiers(QMap<QString, int>);

};

 

#endif //SYNANALYSER_H

 

SynAnalyser.cpp

 

#include "SynAnalyser.h"

 

#include <QMessageBox>

 

//Лексический анализатор

SynAnalyser::SynAnalyser(QObject* parent)

: QObject(parent)

{

createMatrix();

createRules();

}

 

//заполнение матрицы операторного предшествования

void SynAnalyser::createMatrix()

{

QChar matrixEx[29][29] = {

//    1    2    3    4    5    6    7    8    9   10   11   12   13   14   15   16   17   18   19   20   21   22   23   24   25   26   27   28   29

/*1  program*/{' ', '=', '<', '<', ' ', ' ', ' ', '<', ' ', '<', ' ', ' ', '<', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},

/*2  end.*/   {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '>'},

/*3  ;*/   {' ', '>', '>', '<', ' ', ' ', ' ', '<', '>', '<', ' ', ' ', '<', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},

/*4  if*/   {' ', ' ', ' ', ' ', '=', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '<', '<', ' ', '<', '<', '<', '<', '<', '<', '<', '<', ' ', '<', '<', '<', '<', ' '},

/*5  then*/   {' ', ' ', ' ', '<', ' ', '=', '=', '<', ' ', '<', ' ', ' ', '<', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},

/*6  else*/   {' ', ' ', ' ', '<', ' ', ' ', '=', '<', ' ', '<', ' ', ' ', '<', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},

/*7  endif*/  {' ', '>', '>', ' ', ' ', '>', '>', ' ', '>', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},

/*8  begin*/  {' ', ' ', '<', '<', ' ', ' ', ' ', '<', '=', '<', ' ', ' ', '<', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},

/*9  end*/    {' ', '>', '>', ' ', ' ', '>', '>', ' ', '>', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},

/*10 for*/    {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '<', '=', ' ', '<', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},

/*11 downto*/ {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '>', ' ', ' ', '=', '<', '<', ' ', ' ', ' ', ' ', '<', '<', '<', '<', '<', ' ', '<', '<', '<', '<', ' '},

/*12 do */    {' ', '>', '>', '<', ' ', '>', '>', '<', '>', ' ', ' ', ' ', '<', ' ', ' ', ' ', ' ', ' ', '<', '<', '<', '<', '<', ' ', '<', '<', '<', '<', ' '},

/*13 a*/      {' ', '>', '>', ' ', '>', '>', '>', ' ', '>', ' ', '>', '>', ' ', ' ', '=', '>', ' ', ' ', '>', '>', '>', '>', ' ', '>', '>', '>', ' ', ' ', ' '},

/*14 c*/      {' ', '>', '>', ' ', '>', '>', '>', ' ', '>', ' ', '>', '>', ' ', ' ', ' ', '>', ' ', ' ', '>', '>', '>', '>', ' ', '>', '>', '>', ' ', ' ', ' '},

/*15 :=*/     {' ', '>', '>', ' ', ' ', '>', '>', ' ', ' ', ' ', '>', ' ', '<', '<', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '<', ' ', '<', '<', ' ', ' ', ' '},

/*16 or*/     {' ', ' ', ' ', ' ', '>', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '<', '<', ' ', '>', '<', '<', '<', '<', '<', '<', '<', '>', '<', '<', '<', '<', ' '},

/*17 and*/    {' ', ' ', ' ', ' ', '>', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '<', '<', ' ', '>', '<', '<', '<', '<', '<', '<', '<', '>', '<', '<', '<', '<', ' '},

/*18 not*/    {' ', ' ', ' ', ' ', '>', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '<', '<', ' ', '>', '>', '<', '<', '<', '<', '<', '<', '>', '<', '<', '<', '<', ' '},

/*19 <*/      {' ', ' ', ' ', ' ', '>', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '<', '<', ' ', '>', '>', ' ', ' ', ' ', ' ', ' ', '<', '>', '<', '<', ' ', ' ', ' '},

/*20 >*/      {' ', ' ', ' ', ' ', '>', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '<', '<', ' ', '>', '>', ' ', ' ', ' ', ' ', ' ', '<', '>', '<', '<', ' ', ' ', ' '},

/*21 =*/      {' ', ' ', ' ', ' ', '>', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '<', '<', ' ', '>', '>', ' ', ' ', ' ', ' ', ' ', '<', '>', '<', '<', ' ', ' ', ' '},

/*22 <>*/     {' ', ' ', ' ', ' ', '>', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '<', '<', ' ', '>', '>', ' ', ' ', ' ', ' ', ' ', '<', '>', '<', '<', ' ', ' ', ' '},

/*23 (*/      {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '<', '<', ' ', '<', '<', '<', '<', '<', '<', '<', '<', ' ', '<', '<', '<', '<', ' '},

/*24 )*/      {' ', '>', '>', ' ', '>', '>', '>', ' ', '>', ' ', '>', '>', ' ', ' ', ' ', '>', '>', ' ', '>', '>', '>', '>', ' ', '>', '>', '>', ' ', ' ', ' '},

/*25 -*/      {' ', '>', '>', ' ', '>', '>', '>', ' ', '>', ' ', '>', '>', '<', '<', ' ', '>', '>', ' ', '>', '>', '>', '>', '<', '>', '>', '>', ' ', ' ', ' '},

/*26 +*/      {' ', '>', '>', ' ', '>', '>', '>', ' ', '>', ' ', '>', '>', '<', '<', ' ', '>', '>', ' ', '>', '>', '>', '>', '<', '>', '>', '>', ' ', ' ', ' '},

/*27 <<*/     {' ', ' ', ' ', ' ', '>', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '<', '<', ' ', '>', '>', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},

/*28 >>*/     {' ', ' ', ' ', ' ', '>', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '<', '<', ' ', '>', '>', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},

/*29 _|_н*/   {'<', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '}

};

 

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

{

for (int j=0; j<29; j++)

{

matrix[i][j] = matrixEx[i][j];

}

}

 

}

 

//Правила исходной грамматики

void SynAnalyser::createRules()

{      // 0               1    2      3     4                     5                6            7                8       9      10     11    12    13    14   15  

QString rulesEx[29] = {"programEend.", "E", "E;E", "E;", "ifBthenEelseEendif", "ifBthenEendif", "beginEend", "forEdowntoEdoE", "E","a:=E", "E-E", "E+E", "E", "(E)", "a", "c",//правила E->...

//   16     17    18     19     20    21     22     23     24      25     26      27     28

   "BorB", "B", "BandB", "B", "notB", "B", "E<E", "E>E", "E=E", "E<>E", "(B)", "E<<E", "E>>E"  //правила B->...

};

 

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

rules[i] = rulesEx[i];

}

 

//алгоритм сдвиг-свертка

void SynAnalyser::start()

{

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

sendLog(tr("Количество  лексем: %1").arg(lexemes.size()), "EVENT");

 

rootTreeItem = new synTreeItem; //корневой узел дерева

 

int lexemesPos=0; //позиция в цепочке лексем

int stackPos=0; //позиция в стеке

int flag=0; //флаг завершения алгоритма

stack.clear(); //очистка стека

stackSize=0; //размер стека

sItem.text="["; //маркер начала строки

sItem.value="[";

stack.push(sItem); //добавляем в стек маркер начала строки

stackSize++;

sendLog(tr("В стек  добавлен маркер начала строки"), "EVENT");

lexDesc.text="]"; //маркер конца строки

lexDesc.type="LINEEND";

lexemes.append(lexDesc); //добавить в конец входной цепочки маркер конца строки

sendLog(tr("В конец  входной цепочки добавлен маркер  конца строки"), "EVENT");

 

while (flag==0)

{

topTerm = getTopTerm(); //верхний терминал стека

sendLog(tr("Верхний  терминал стека: %1").arg(topTerm), "EVENT");

lexDesc = lexemes.at(lexemesPos); //считываем очередную лексему

curLex = lexDesc.text; //текущий символ входной цепочки

sendLog(tr("Текущий  символ входной цепочки: %1").arg(curLex), "EVENT");

if ((topTerm=="[") && (curLex=="]")) //если верхний терминал стека '[' и текущяя лексема ']', то алгоритм завершен

{

flag=1; //алгоритм завершен

rootTreeItem->text="E";

emit setRootItem(rootTreeItem); //послать указатель на корневой узел дерева

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

}

else

{

QChar matrixValue = getMatrixValue(topTerm, getStackItemText()); //значение в ячейке матрицы предшествования

emit sendLog(tr("Отношение %1 %2 %3").arg(topTerm).arg(matrixValue).arg(curLex), "MESSAGE");

if (matrixValue==' ') //если ячейка пуста

{

setError(lexDesc.stringNumber);

emit sendLog(tr("Синтаксическая ошибка, не найдено соответствие в матрице"), "ERROR");

flag=1;

}

else if ((matrixValue=='=') || (matrixValue=='<'))

{    

shift(); //сдвиг

lexemesPos++; //передвигаем считывающую головку

}

else if (matrixValue=='>')

{

reduce(); //свертка

}

else //вообще-то такого быть не должно

{

QMessageBox::critical(0, "ERROR", tr("Разработчик косяк!!"), "OK");

}

}

 

}

 

 

}

 

//сдвиг

void SynAnalyser::shift()

{

emit sendLog(tr("Сдвиг"), "END");

sItem.value=curLex;

sItem.text=getStackItemText();

sItem.node = new synTreeItem; //создаем указатель на узел дерева

sItem.node->text=sItem.value;

stack.push(sItem); //пишем текущую лексему в стек

stackSize++;

}

 

//свертка

void SynAnalyser::reduce()

{

emit sendLog(tr("Свертка:"), "END");

stackPos=0;

// int f=0;

curRule="";

QString curTerm; //текущий терминал (последний из добавленных в правило)

stackItem nextTerm; //терминал, который считывается в данный момент

bool isTopTerm=1; //флаг = терминал является самым верхним в стеке

QChar mtrxValue; //значение ячейки в матрице предшествования

bool ruleEnd=0; //флаг конца правила

 

treeItem = new synTreeItem; //создаем новый узел дерева

//для всех символов  стека, начиная с вершины

while (!ruleEnd) //пока не конец правила

{ 

nextTerm=stack.pop(); //следующий символ вытаскиваем из верхушки стека

stackSize--;

if ((nextTerm.text=="E") || (nextTerm.text=="B")) //если нетерминал

{

curRule.prepend(nextTerm.text); //добавляем в начало текущего правила

treeItem->childItems.prepend(nextTerm.node); //добавить указатель на узел в список потомков узла

 

}

else //если терминал

{

if (isTopTerm) //если верхний терминал стека

{

curTerm = nextTerm.text; //делаем терминал текущим

curRule.prepend(curTerm); //добавляем терминал в начало текущего правила

treeItem->childItems.prepend(nextTerm.node); //добавить указатель на узел в список потомков узла

isTopTerm=0;

}

 

else //не верхний терминал

{

//если этот терминал  связан с текущим символом  отношением '='

if (getMatrixValue(nextTerm.text, curTerm)=='=')

{

curTerm = nextTerm.text; //делаем терминал текущим

curRule.prepend(curTerm); //добавляем терминал в начало текущего правила

treeItem->childItems.prepend(nextTerm.node); //добавить указатель на узел в список потомков узла     

}

else

{

stack.push(nextTerm); //обратно добавляем неиспользованный символ в стек

stackSize++;

ruleEnd=1; //флаг конца правила

break; //выходим из цикла, правило считано

}

}

 

}

}

 

if (curRule.size()>MAXRULELENGTH)

QMessageBox::critical(0, "ERROR", tr("Превышена максимальная длина правила"), "OK");

if (!curRule.isEmpty()) //если правило не пустое, то ищем соответствующее правило

{

bool isRuleValid=0; //флаг = правило корректное

sendLog(tr("Поиск  правила, соответствующего '%1'").arg(curRule), "MESSAGE");

for (int j=0; j<RULENUM; j++)

{

stackItem curRuleStruct;

if (rules[j]==curRule) //если правило совпало

//добавляем Е  или В в зависимости от j

{

if (j<16) //Если правило Е (арифметическое)

{

curRuleStruct.text="E";

sendLog(tr("Соответствующее  правило найдено, заменяем на 'E'"), "MESSAGE");

treeItem->text="E"; //название узла дерева

}

else //правило B (логическое)

{

curRuleStruct.text="B";

sendLog(tr("Соответствующее  правило найдено, заменяем на 'B'"), "MESSAGE");

treeItem->text="B"; //название узла дерева

}

curRuleStruct.value = curRule; //значение символа