Введение
В последнее время большинство новичков в программировании начинают с высокоуровневых языков, таких, как 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, или язык для вашей предметной области — все это можно реализовать при понимании всех специфик работы и устройства компилятора в общем виде.
С проектом можно ознакомиться тут
KvanTTT
Об этом было бы еще интересней узнать, поскольку материала по лексическому и синтаксическому анализу в целом больше.
Как понимаю, это иммутабельный класс. Поэтому его поля и свойства должны быть
readonly
. Ну и в C# принято обозначать локальные переменные без префиксов, а поля — с ними или без:mamalama Автор
В статье хотел показать примитивное устройство лексического анализатора, с простым функционалом и базовым набором методов, поэтому, думаю, что «велосипед» здесь отчасти оправдан. Со всем остальным полностью согласен, есть что исправить и изменить.
Siemargl
Ответ отказался простым.
KvanTTT
А в статье идет речь о серьезном компиляторе? И как определяется серьезность? Каким оказался ответ?
eandr_67
В Pascal ":=" — не единственная лексема из нескольких служебных символов. Есть ещё, как минимум, "<>" (не равно), ".." (тип-диапазон), "(*" и "*)" (альтернативный способ задания комментариев).
Лучше сразу предусматривать универсальную обработку лексем из нескольких служебных символов, чем каждый раз отдельно обрабатывать «особый случай».
kovserg
Паскаль это слишком просто. Вы попробуйте фортран разобрать, где пробелы игнорируются и «F OR» «F O R» тоже самое что «FOR».
mamalama Автор
«Вот так, с помощью нехитрых приспособлений буханку белого (или черного) хлеба можно превратить в троллейбус… Но зачем?»