[.NET, C#, Компиляторы, Разработка под Windows] Введение в теорию компиляторов: лексический анализ языка Pascal средствами C#

Ответить на тему

Автор

Сообщение

news_bot ^®

Стаж: 6 лет 9 месяцев
Сообщений: 27286

news_bot ^® написал(а)
17-Авг-2020 14:31

Цитировать

Введение
В последнее время большинство новичков в программировании начинают с высокоуровневых языков, таких, как 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;
begin
c := a - b + 15;
end.

Выходные данные

Полный алгоритм

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, или язык для вашей предметной области — все это можно реализовать при понимании всех специфик работы и устройства компилятора в общем виде.
С проектом можно ознакомиться по ссылке
===========
Источник:
habr.com
===========
Похожие новости:

Теги для поиска: #_.net, #_c#, #_kompiljatory (Компиляторы), #_razrabotka_pod_windows (Разработка под Windows), #_c#, #_.net, #_kompiljatory (компиляторы), #_razrabotka (разработка), #_razrabotka_po (разработка по), #_.net, #_c#, #_kompiljatory (
Компиляторы
), #_razrabotka_pod_windows (
Разработка под Windows
)

Профиль ЛС

Ответить на тему

Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы

Текущее время: 22-Ноя 10:47
Часовой пояс: UTC + 5