Введение
В последнее время большинство новичков в программировании начинают с высокоуровневых языков, таких, как Java, Python, C#, или любой другой язык, содержащий в себе джентльменский набор в виде сборщика мусора, готовых структур данных и так далее. Конечно, такой подход имеет свои плюсы, но, как правило, начинающий разработчик, использующий готовый функционал языка, упускает самое главное его устройство и механизмы работы и имплементации.
Я не буду вдаваться в подробности распределения памяти и способы интерпретации кода, а наоборот, хотелось бы поговорить о самом устройстве компилятора, а именно о лексическом анализаторе и попробовать реализовать его на языке C#. Язык, который мы будем анализировать, знает подавляющее большинство это Pascal.
Лексический анализатор первый из слоев компилятора, отвечающий за выделение лексем для последующей обработки.
Лексема минимальная единица некоего словаря, представляющего наш язык. В роли лексемы могут служить служебные слова, операторы, идентификаторы и так далее.
Реализация
Описание структуры
Формальное описание языка будет храниться в двух массивах: в первом служебные слова, а во втором ограничители и список с найденными лексемами
private string[] Words = { "program", "var", "integer", "real", "bool", "begin", "end", "if", "then", "else", "while", "do", "read", "write", "true", "false" };private string[] Delimiter = { ".", ";", ",", "(", ")", "+", "-", "*", "/", "=", ">", "<" };public List<Lex> Lexemes = new List<Lex>();
Сама лексема будет в себе хранить ключ, с помощью которого будет определяться принадлежность к типу (служебные слова, операторы, идентификаторы, числа), id лексемы и само значение.
class Lex{ public int id; public int lex; public string val; public Lex(int _id, int _lex, string _val) { id = _id; lex = _lex; val = _val; }}
Наилучшим решением для обработки лексем будет служить некий конечный автомат. Это позволит избавиться от лишних if-ов, а также даст возможность легко вносить изменения в цикл. S начальное состояние, NUM, DLM, ASGN, ID состояния соответствующих видов лексем, ER будет использоваться для ошибки, а FIN для конечного состояния.
private string buf = ""; // буфер для хранения лексемыprivate char[] sm = new char[1];private int dt = 0;private enum States { S, NUM, DLM, FIN, ID, ER, ASGN, COM } // состояния state-машиныprivate States state; // хранит текущее состояниеprivate StringReader sr; // позволяет посимвольно считывать строку
Основными методами являются SearchLex, который ищет лексему в нашем массиве и возвращает ее id и значение в кортеже (да, кортежи тоже бывают полезными), а также PushLex, который добавляет новую лексему в словарь.
private (int, string) SerchLex(string[] lexes){ var srh = Array.FindIndex(lexes, s => s.Equals(buf)); if (srh != -1) return (srh, buf); else return (-1, "");}private (int, string) PushLex(string[] lexes, string buf){ var srh = Array.FindIndex(lexes, s => s.Equals(buf)); if (srh != -1) return (-1, ""); else { Array.Resize(ref lexes, lexes.Length + 1); lexes[lexes.Length - 1] = buf; return (lexes.Length - 1, buf); }}
Реализация алгоритма
Первым делом стоит определить конец работы цикла состояние FIN, а также реализовать начальное состояние, которое будет
sr = new StringReader(text); // Получение исходного кода программыwhile (state != States.FIN){ switch (state) { case States.S: if (sm[0] == ' ' || sm[0] == '\n' || sm[0] == '\t' || sm[0] == '\0' || sm[0] == '\r' ) GetNext(); else if (Char.IsLetter(sm[0])) { ClearBuf(); AddBuf(sm[0]); state = States.ID; GetNext(); } else if (char.IsDigit(sm[0])) { dt = (int)(sm[0]-'0'); GetNext(); state = States.NUM; } else if (sm[0] == '{') { state = States.COM; GetNext(); } else if (sm[0] == ':') { state = States.ASGN; ClearBuf(); AddBuf(sm[0]); GetNext(); } else if (sm[0] == '.') { AddLex(Lexemes, 2, 0, sm[0].ToString()); state = States.FIN; } else { state = States.DLM; } break; } }
Метод GetNext позволяет получить следующий символ в строке, ClearBuf, соответственно, очищает буфер, хранящий в себе лексему
private void GetNext(){ sr.Read(sm, 0, 1);}
Особое внимание стоит уделить оператору присваивания ":=", который состоит из двух отдельных операторов. Самым простым способом определения данного оператора является добавление условия и запись промежуточного значения в буфер. Для этого было реализовано отдельное состояние ASGN (в переводе assing присваивание). В случае определения буфера как ":", алгоритм просто добавит новую лексему, а если следующим знаком является "=", то будет добавлен уже один оператор присваивания.
case States.ASGN: if (sm[0] == '=') { AddBuf(sm[0]); AddLex(Lexemes, 2, 4, buf); ClearBuf(); GetNext(); } else AddLex(Lexemes, 2, 3, buf); state = States.S;break;
Конечное состояние и состояние с ошибкой реализованы только служебными сообщениями. Можно доработать данный вариант и проверять также ошибку, но, пожалуй, данный функционал можно перенести уже в синтаксический анализатор.
case States.ER: MessageBox.Show("Ошибка в программе"); state = States.FIN; break;case States.FIN: MessageBox.Show("Лексический анализ закончен"); break;
Тестирование
Протестировать алгоритм можно по-разному: указать напрямую путь .pas файла, программно создать строку или любой другой удобный вариант. Так как мы пишем на C#, не составит труда добавить форму в приложение, на которой будет 2 textBox-а, первый для ввода кода программы, второй выводит результат работы алгоритма.
По нажатию кнопки будем запускать анализ текста, а полученный результат будем обрабатывать с помощью switch конструкции: дополнительно выведем к какому типу относится найденная лексема.
private void button1_Click(object sender, EventArgs e){ textBox2.Clear(); TplMain tpl = new TplMain(); tpl.Analysis(textBox1.Text); foreach(var lex in tpl.Lexemes) { switch (lex.id) { case 1: textBox2.Text += "id: " + lex.id + " lex: " + lex.lex + " val: " + lex.val + " |" + " служебные слова "+ Environment.NewLine; break; case 2: textBox2.Text += "id: " + lex.id + " lex: " + lex.lex + " val: " + lex.val + " |" + " ограничители " + Environment.NewLine; break; case 3: textBox2.Text += "id: " + lex.id + " lex: " + lex.lex + " val: " + lex.val + " |" + " числа " + Environment.NewLine; break; case 4: textBox2.Text += "id: " + lex.id + " lex: " + lex.lex + " val: " + lex.val + " |" + " идентификатор " + Environment.NewLine; break; } } }
Входные данные
program hellohabr;var a, b, c : integer;beginc := a - b + 15;end.
Выходные данные
id: 1 lex: 0 val: program | служебные слова id: 4 lex: 1 val: hellohabr | идентификатор id: 2 lex: 1 val: ; | ограничители id: 1 lex: 1 val: var | служебные слова id: 4 lex: 1 val: a | идентификатор id: 2 lex: 2 val: , | ограничители id: 4 lex: 1 val: b | идентификатор id: 2 lex: 2 val: , | ограничители id: 4 lex: 1 val: c | идентификатор id: 2 lex: 3 val: : | ограничители id: 1 lex: 2 val: integer | служебные слова id: 2 lex: 1 val: ; | ограничители id: 1 lex: 5 val: begin | служебные слова id: 4 lex: 1 val: c | идентификатор id: 2 lex: 4 val: := | ограничители id: 4 lex: 1 val: a | идентификатор id: 2 lex: 6 val: - | ограничители id: 4 lex: 1 val: b | идентификатор id: 2 lex: 5 val: + | ограничители id: 3 lex: 1 val: 15 | числа id: 2 lex: 1 val: ; | ограничители id: 1 lex: 6 val: end | служебные слова id: 2 lex: 0 val: . | ограничители
Полный алгоритм
public void Analysis(string text){ sr = new StringReader(text); while (state != States.FIN) { switch (state) { case States.S: if (sm[0] == ' ' || sm[0] == '\n' || sm[0] == '\t' || sm[0] == '\0' || sm[0] == '\r') GetNext(); else if (Char.IsLetter(sm[0])) { ClearBuf(); AddBuf(sm[0]); state = States.ID; GetNext(); } else if (char.IsDigit(sm[0])) { dt = (int)(sm[0] - '0'); GetNext(); state = States.NUM; } else if (sm[0] == '{') { state = States.COM; GetNext(); } else if (sm[0] == ':') { state = States.ASGN; ClearBuf(); AddBuf(sm[0]); GetNext(); } else if (sm[0] == '.') { AddLex(Lexemes, 2, 0, sm[0].ToString()); state = States.FIN; } else { state = States.DLM; } break; case States.ID: if (Char.IsLetterOrDigit(sm[0])) { AddBuf(sm[0]); GetNext(); } else { var srch = SerchLex(Words); if (srch.Item1 != -1) AddLex(Lexemes, 1, srch.Item1, srch.Item2); else { var j = PushLex(TID, buf); AddLex(Lexemes, 4, j.Item1, j.Item2); } state = States.S; } break; case States.NUM: if (Char.IsDigit(sm[0])) { dt = dt * 10 + (int)(sm[0] - '0'); GetNext(); } else { var j = PushLex(TNUM, dt.ToString()); AddLex(Lexemes, 3, j.Item1, j.Item2); state = States.S; } break; case States.DLM: ClearBuf(); AddBuf(sm[0]); var r = SerchLex(Delimiter); if (r.Item1 != -1) { AddLex(Lexemes, 2, r.Item1, r.Item2); state = States.S; GetNext(); } else state = States.ER; break; case States.ASGN: if (sm[0] == '=') { AddBuf(sm[0]); AddLex(Lexemes, 2, 4, buf); ClearBuf(); GetNext(); } else AddLex(Lexemes, 2, 3, buf); state = States.S; break; case States.ER: MessageBox.Show("Ошибка в программе"); state = States.FIN; break; case States.FIN: MessageBox.Show("Лексический анализ закончен"); break; } }}
Заключение
Может показаться, что лексический анализатор штука не очень понятная, да и собственно не очень важная. Почему нельзя вынести все это в синтаксический анализатор? Как работать со сложными конструкциями? Да, способы реализации лексического анализатора разнятся от компилятора к компилятору, но при разборе всех этих принципов появится не только понимание работы языка программирования X, но и появится фундамент для разработки собственного языка программирования: второй Python, или язык для вашей предметной области все это можно реализовать при понимании всех специфик работы и устройства компилятора в общем виде.
С проектом можно ознакомиться по ссылке
