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

Question

[Егор Неймлес]

Здравствуйте, бьюсь уже несколько дней, надеюсь на помощь. Задача состоит в реализации синтаксического анализатора. Краткая суть такая: есть текстовый файл, в котором записан какой-то код программы, согласно моей грамматике. Он проверяется лексическим анализатором, который выделяет лексемы. А затем уже синтаксическим на наличие ошибок. Если ошибок нет, то всё хорошо. А если есть (например, в конце строки не стоит ";"), то выводится сообщение, в котором указано, где ошибка, и что это за ошибка, как в компиляторе. Вот у меня есть такой код, но не для моей грамматики. У меня не получается заставить его корректно работать. Дальше лексического анализа он не уходит.

<Программа> ::= <Объявление переменных> <Описание вычислений>
<Описание вычислений> ::= Begin <Список присваиваний> End
<О6ъявление переменных>::= <Тип переменных> <Список переменных>
<Тип переменных> ::= Integer|Long Integer
<Список переменных> ::= <Идент>| <Идент>,<Список переменных>
<Список присваиваний>::= <Присваивание>|<Присваивание> <Список присваиваний>
<Присваивание> ::= <Идент> = <Выражение> ;
<Выражение> ::= <Ун.оп.> <Подвыражение> | <Подвыражение>
<Подвыражение> :: = ( <Выражение> ) | <Операнд> |
 <Подвыражение> <Бин.оп.> <Подвыражение>
<Ун.оп.> ::= "-"
<Бин.оп.> ::= "-" | "+" | "*" | "/"
<Операнд> ::= <Идент> | <Константа>
<Идент> ::= <Буква> <Идент> | <Буква>
<Константа> ::= <Цифра> <Константа> | <Цифра>

Код программы приведу в комментарии, так как он сюда не влезет.

Comments

[Егор Неймлес]

Привожу код:

#define _CRT_SECURE_NO_WARNINGS
    
    #include <iostream>
    #include <stdio.h>
    #include <ctype.h>
    #include <fstream>
    #include <string>
    #include <vector>
    # include <conio.h>
    
    
    using namespace std;
    
    
    enum EState { S, Ai, Ac, As, Bs, Cs, At, E, F };
    enum ELexType { lSelect, lCase, lDefault, lEnd, lAs, lAo, lAm, lVar, lConst, lAt };
    struct Lex {
    	ELexType type;
    	//int index;
    	int pos;
    	string lexem;
    	Lex *next, *prev;
    } *pFirst = NULL, *pLast = NULL;
    
    int Syntax[10][13] =
    {/*   0   1   2   3   4   5   6   7   8   9   10  11  12*/
    	{ 1,  13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13 },//lSelect
    	{ 13, 13, 3,  13, 13, 13, 13, 3,  13, 13, 13, 13, 13 },//lCase
    	{ 13, 13, 13, 13, 13, 13, 13, 8,  13, 13, 13, 13, 13 },//lDefault
    	{ 13, 13, 13, 13, 13, 13, 13, 9,  13, 13, 13, 13, 9 }, //lEnd
    	{ 13, 13, 13, 13, 13, 6,  13, 13, 13, 13, 11, 13, 13 },//lAs
    	{ 13, 13, 1,  13, 13, 13, 13, 6,  13, 13, 13, 13, 11 },//lAo
    	{ 13, 13, 1,  13, 13, 13, 13, 6,  13, 13, 13, 13, 11 },//lAm
    	{ 13, 2,  13, 13, 5,  13, 7,  13, 10, 13, 13, 12, 13 },//lVar
    	{ 13, 2,  13, 4,  13, 13, 7,  13, 13, 13, 13, 12, 13 },//lConst
    	{ 13, 13, 13, 13, 13, 13, 13, 4,  13, 13, 13, 13, 8 } //lAt
    };
    
    int const P[7][8] = {
    	/*Ц  Б  = +,- *,/ ; E  F */
    	{ 2, 1, 3, 4, 5, 6, 7, 7 }, //S 
    	{ 1, 1, 3, 4, 5, 6, 7, 8 }, //Ai
    	{ 2, 7, 3, 4, 5, 6, 7, 8 }, //Ac
    	{ 2, 1, 7, 7, 7, 7, 7, 8 }, //As
    	{ 2, 1, 7, 7, 7, 7, 7, 8 }, //Bs
    	{ 2, 1, 7, 7, 7, 7, 7, 8 }, //Cs
    	{ 2, 1, 7, 7, 7, 7, 7, 8 }, //At
    };
    class ErrorFileExists
    {
    public:
    	void Print()
    	{
    		cout << "Файла не существует либо он пуст" << endl;
    	}
    };
    class ErrorLexAnalisis
    {
    private:
    	const char* word;
    public:
    	ErrorLexAnalisis(const char* s) : word(s)
    	{ }
    	void Print()
    	{
    		cout << "Ошибка лексического анализа: " << word << endl;
    	}
    };
    class ErrorSyntaxAnalisis
    {
    private:
    	const char* text;
    	int position = -1;
    public:
    	ErrorSyntaxAnalisis(const char* s) : text(s)
    	{ }
    	ErrorSyntaxAnalisis(const char* s, int pos) : text(s)
    	{
    		position = pos;
    	}
    public:
    	void Print()
    	{
    		if (position != -1)
    			cout << text << position << endl;
    		else
    			cout << text << endl;
    	}
    };
    
    class LexAnalis
    {
    private:
    	bool errorLex = false;
    	int size;
    	ifstream fin;
    
    	ELexType typeKeywords(int i)
    	{
    		switch (i)
    		{
    		case 0: return lSelect;
    		case 1: return lCase;
    		case 2: return lDefault;
    		default: return lEnd;
    		}
    	}
    	ELexType typeSpecialCharacter(const char t)
    	{
    		switch (t)
    		{
    		case '=': return lAs;
    		case '+': case '-':  return lAo;
    		case '*': case '/':  return lAm;
    		default: return lAt;
    		}
    	}
    	int gettype(char c)
    	{
    		if (isdigit(c))
    			return 0;
    		else if (isalpha(c))
    			return 1;
    		else if (c == '=')
    			return 2;
    		else if (c == '+' || c == '-')
    			return 3;
    		else if (c == '*' || c == '/')
    			return 4;
    		else if (c == ';')
    			return 5;
    		else if (!c)
    			return 7;
    		else return 6;
    	}
    	void LexAnalysis(const char* word)
    	{
    		const char *str = word, *lexstart = word;
    		int a, q = 0, prevQ;
    		while ((q != 7) && (q != 8))
    		{
    			prevQ = q;
    
    			a = gettype(*str);
    			q = P[q][a];
    
    			if (0 != prevQ && q != prevQ && q != 7) AddLex(prevQ, word, lexstart, str);
    			if ((q != prevQ) && (q == 1 || q == 2 || q == 3 || q == 4 || q == 5 || q == 6))
    				lexstart = str;
    			if ((q != 7) && (q != 8)) str++;
    		}
    		if (q == 7)
    			throw ErrorLexAnalisis(word);
    	}
    	bool isExistFile(const char*inputFile)
    	{
    		fin.open(inputFile);
    		fin.seekg(0, ios::end);//устанавливаем курсор в конец файла
    		size = (int)fin.tellg();
    		fin.seekg(0, ios::beg);//устанавливаем курсор в начало файла 
    		return (fin.is_open() && size);
    	}
    	void AddLex(int state, const char* txt, const char* lexPtr, const char* curPtr)
    	{
    		static int pos = 0;
    		char keywords[4][8] = { "select", "case", "default", "end" };
    
    		int k = strlen(lexPtr); //с какого символа начать(включительно)
    		int m = strlen(curPtr); //до какого символа
    
    
    		bool flag = false;
    
    		char t[255];
    		int i = 0;
    		for (i = 0; i < k - m; ++i)//k - m сколько символов
    		{
    			t[i] = lexPtr[i];
    		}
    		t[i] = '\0';
    
    		Lex *lex = new Lex;
    		lex->prev = pLast;
    		lex->next = NULL;
    		if (pLast) pLast->next = lex;
    		pLast = lex;
    		if (!pFirst) pFirst = pLast;
    
    		switch (state)
    		{
    		case 1:
    		{
    			ELexType type;
    			for (int i = 0; i < sizeof keywords / sizeof keywords[0]; i++)
    			{
    				if (!strcmp(keywords[i], t))
    				{
    					type = typeKeywords(i);
    
    					flag = true;
    					break;
    				}
    			}
    			if (flag)
    			{
    				cout << t << " - ключевое слово" << endl;
    				lex->lexem = t;
    				lex->type = type;
    				lex->pos = pos++;
    			}
    			else
    			{
    				cout << t << " - идентификатор" << endl;
    				lex->lexem = t;
    				lex->type = lVar;
    				lex->pos = pos++;
    			}
    			break;
    		}
    		case 2:
    		{
    			lex->type = lConst;
    			lex->pos = pos++;
    			lex->lexem = t;
    			cout << t << " - константа" << endl; break;
    		}
    		case 3: case 4: case 5: case 6:
    		{
    			lex->type = typeSpecialCharacter(*t);
    			lex->pos = pos++;
    			lex->lexem = t;
    			cout << t << " - специальный символ" << endl; break;
    		}
    		}
    	}
    public:
    	~LexAnalis()
    	{
    		fin.close();
    	}
    	Lex* getListLexs(const char* inputFile)
    	{
    		if (isExistFile(inputFile))
    		{
    			char *text = new char[size];
    
    			while (!fin.eof())
    			{
    				fin >> text;
    				LexAnalysis(text);
    			}
    			delete[] text;
    			cout << "Лексических ошибок нет" << endl;
    			return pFirst;
    		}
    		else
    		{
    			throw ErrorFileExists();
    			return NULL;
    		}
    	}
    };
    
    class SyntaxAnalis
    {
    private:
    	bool parsing(Lex *&p)
    	{
    		int prevState = 0, state = 0;
    		while (p)
    		{
    			prevState = state;
    			state = Syntax[getLt(p->type)][prevState];
    
    			if (state == 13)
    			{
    				Error(p, p->pos, p->lexem, prevState);
    				return false;
    			}
    			p = p->next;
    		}
    		if (state != 9)
    		{
    			cout << "Ожидается end" << endl;
    			return false;
    		}
    		return true;
    
    	}
    	void Error(Lex *&p, int pos, string &word, int state)
    	{
    		switch (state)
    		{
    		case 0: cout << "Перед '" + word + "'(позиция " << pos << ") ожидается " << "select" << endl; break;
    		case 1: cout << "Перед '" + word + "'(позиция " << pos << ")  ожидается " << "переменная или константа" << endl; break;
    		case 2: cout << "Перед '" + word + "'(позиция " << pos << ")  ожидается " << "арифметическая операция или case" << endl; break;
    		case 3: cout << "Перед '" + word + "'(позиция " << pos << ")  ожидается " << "константа" << endl; break;
    		case 4: cout << "Перед '" + word + "'(позиция " << pos << ")  ожидается " << "переменная" << endl; break;
    		case 5: cout << "Перед '" + word + "'(позиция " << pos << ")  ожидается " << "операция присвоить" << endl; break;
    		case 6: cout << "Перед '" + word + "'(позиция " << pos << ")  ожидается " << "переменная или константа" << endl; break;
    		case 7: cout << "Перед '" + word + "'(позиция " << pos << ")  ожидается " << "case, default, end, арифметическая операция или ;" << endl; break;
    		case 8: cout << "Перед '" + word + "'(позиция " << pos << ")  ожидается " << "переменная" << endl; break;
    		case 9: cout << "Лишние символы после end" << endl; break;
    		case 10: cout << "Перед '" + word + "'(позиция " << pos << ")  ожидается " << "операция присвоить" << endl; break;
    		case 11: cout << "Перед '" + word + "'(позиция " << pos << ")  ожидается " << "переменная или константа" << endl; break;
    		case 12: cout << "Перед '" + word + "'(позиция " << pos << ") ожидается " << "end, арифметическая операция, ;" << endl; break;
    		}
    	}
    	int getLt(ELexType elt)
    	{
    		switch (elt)
    		{
    		case lSelect: return 0;
    		case lCase: return 1;
    		case lDefault: return 2;
    		case lEnd: return 3;
    		case lAs: return 4;
    		case lAo: return 5;
    		case lAm: return 6;
    		case lVar: return 7;
    		case lConst: return 8;
    		case lAt: return 9;
    		}
    		return 0;
    	}
    public:
    	SyntaxAnalis(Lex *p)
    	{
    		if (parsing(p))
    			cout << "Синтаксических ошибок нет" << endl;
    		else
    			cout << "Синтаксическая ошибка" << endl;
    	}
    };
    
    int main()
    {
    	setlocale(LC_ALL, "Russian");
    
    	LexAnalis lexem;
    
    	try
    	{
    		SyntaxAnalis syntax(lexem.getListLexs("d:\\1\\input.txt"));
    	}
    	catch (ErrorFileExists &e)
    	{
    		e.Print();
    	}
    	catch (ErrorLexAnalisis &e)
    	{
    		e.Print();
    	}
    	catch (ErrorSyntaxAnalisis &e)
    	{
    		e.Print();
    	}
    	catch (...)
    	{
    		cout << "Неизвестная ошибка" << endl;
    	}
    	
    	_getch();
    	return 0;
    }

Answer 1

[Robur]

Вы хотите работу сокурсника переделать под свое задание что ли?

Если вы хотите научиться писать компиляторы-анализаторы, то стоит понимать что это тема фундаментальная и сначала надо вникнуть в теорию, а потом уже писать код. По другому не получится.
тут стоит начать с классики https://en.wikipedia.org/wiki/Compilers:_Principle...
ну или хотя бы вникнуть как работают синтаксические анализаторы, какие бывают, и все так далее. Разобрать текст на лексемы - это самый простой шаг, можно сказать примитивный.

взять код от одной грамматики и переделать его под другую без понимания что в нем вообще происходит - такое себе развлечение. А если понимание есть - то вы просто берете и пишете этот код.

Если вам просто надо чтобы кто-то за вас "код подправил", то это не тот ресурс.

Answer 2

[mayton2019]

Да тут не вопрос, а целое задание для фриланса. Не знаю чем автор занят, репостом ли чужих задач или решением своих но тут надо просто готовить котлету денег.

Или сильно сильно упростить вопрос чтобы он хотябы был осязаем для вопросника.