pengantar
Baru-baru ini, sebagian besar pemula dalam pemrograman memulai dengan bahasa tingkat tinggi seperti Java, Python, C #, atau bahasa lain apa pun yang berisi "kumpulan pria" dalam bentuk pengumpul sampah, struktur data siap pakai, dan sebagainya. Tentu saja, pendekatan ini memiliki kelebihan, tetapi, sebagai aturan, pengembang pemula yang menggunakan fungsionalitas bahasa siap pakai kehilangan hal yang paling penting - struktur dan mekanisme operasi dan implementasinya.
Saya tidak akan membahas detail alokasi memori dan cara menafsirkan kode, tetapi sebaliknya, saya ingin berbicara tentang kompiler itu sendiri, yaitu penganalisis leksikal dan mencoba menerapkannya di C #. Sebagian besar mengetahui bahasa yang akan kami analisis - itu adalah Pascal.
Penganalisis leksikal adalah yang pertama dari "lapisan" kompiler yang bertanggung jawab untuk menyorot token untuk diproses lebih lanjut.
Lexeme adalah unit terkecil dari kamus yang mewakili bahasa kita. Kata-kata layanan, operator, pengenal, dan sebagainya dapat berfungsi sebagai token.
Penerapan
Deskripsi struktur
Deskripsi formal bahasa akan disimpan dalam dua larik: pada kata fungsi pertama, dan pada pembatas kedua dan daftar dengan token yang ditemukan
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>();Lexeme itu sendiri akan menyimpan kunci, yang akan digunakan untuk menentukan jenis (kata layanan, operator, pengidentifikasi, angka), id dari token dan nilainya itu sendiri.
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;
}
}
Solusi terbaik untuk memproses token adalah mesin negara. Ini akan menghilangkan if-s yang tidak perlu, dan juga memudahkan untuk membuat perubahan pada loop. S adalah status awal, NUM, DLM, ASGN, ID adalah status dari jenis token yang sesuai, ER akan digunakan untuk kesalahan, dan FIN untuk status akhir.
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; //
Metode utamanya adalah SearchLex, yang mencari token dalam array kita dan mengembalikan id dan nilainya dalam tupel (ya, tupel juga bisa berguna), dan PushLex, yang menambahkan token baru ke kamus.
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);
}
}
Implementasi algoritma
Langkah pertama adalah menentukan akhir dari siklus - status FIN, dan juga menerapkan status awal, yang akan menjadi
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;
}
}
Metode GetNext memungkinkan Anda untuk mendapatkan karakter berikutnya dalam string, ClearBuf, masing-masing, membersihkan buffer yang menyimpan token
private void GetNext()
{
sr.Read(sm, 0, 1);
}
Perhatian khusus harus diberikan pada operator penugasan ": =", yang terdiri dari dua operator terpisah. Cara termudah untuk mendefinisikan operator ini adalah dengan menambahkan kondisi dan menulis nilai antara ke buffer. Untuk ini, status ASGN terpisah diimplementasikan ( dalam terjemahan, penugasan - penugasan ). Jika buffer didefinisikan sebagai ":", algoritme hanya akan menambahkan token baru, dan jika tanda berikutnya adalah "=", maka satu operator penugasan akan ditambahkan.
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;
Status akhir dan status dengan kesalahan hanya diimplementasikan oleh pesan layanan. Anda dapat memperbaiki opsi ini dan memeriksa kesalahannya juga, tetapi mungkin fungsionalitas ini dapat ditransfer ke parser.
case States.ER:
MessageBox.Show(" ");
state = States.FIN;
break;
case States.FIN:
MessageBox.Show(" ");
break;
Menguji
Anda dapat menguji algoritme dengan berbagai cara: menentukan jalur file .pas secara langsung , membuat string secara terprogram, atau opsi praktis lainnya. Karena kita menulis dalam C #, tidak akan sulit untuk menambahkan formulir ke aplikasi, yang akan berisi 2 kotak teks, yang pertama untuk memasukkan kode program, yang kedua - menampilkan hasil dari algoritma.
Dengan menekan tombol tersebut, kita akan memulai analisis teks, dan hasil yang dihasilkan akan diproses menggunakan konstruksi sakelar : selain itu, kita akan menampilkan jenis token yang ditemukan.
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;
}
}
}
Memasukan data
program hellohabr;
var a, b, c : integer;
begin
c := a - b + 15;
end.
Keluaran
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: . |
Algoritme lengkap
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;
}
}
}
Kesimpulan
Tampaknya penganalisis leksikal bukanlah hal yang sangat jelas, dan sebenarnya tidak terlalu penting. Mengapa Anda tidak bisa memasukkan semua ini ke dalam parser? Bagaimana cara bekerja dengan struktur yang kompleks? Ya, cara untuk mengimplementasikan penganalisis leksikal berbeda dari compiler ke compiler, tetapi ketika Anda menganalisis semua prinsip ini, Anda tidak hanya akan memahami cara kerja bahasa pemrograman X, tetapi Anda juga akan memiliki dasar untuk mengembangkan bahasa pemrograman Anda sendiri: Python kedua, atau bahasa untuk domain Anda - semua ini mungkin untuk mewujudkan dengan pemahaman tentang semua pekerjaan spesifik dan perangkat kompilator secara umum.
Proyek tersebut dapat ditemukan di sini