Введение
В последнее время большинство новичков в программировании начинают с высокоуровневых языков, таких, как 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 (в переводе assign — присваивание). В случае определения буфера как ":", алгоритм просто добавит новую лексему, а если следующим знаком является "=", то будет добавлен уже один оператор присваивания.
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;
begin
c := 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, или язык для вашей предметной области — все это можно реализовать при понимании всех специфик работы и устройства компилятора в общем виде.
С проектом можно ознакомиться тут