introduction
Récemment, la plupart des débutants en programmation commencent avec des langages de haut niveau tels que Java, Python, C # ou tout autre langage contenant un «gentleman's set» sous la forme d'un ramasse-miettes, de structures de données prêtes à l'emploi, etc. Bien sûr, cette approche a ses avantages, mais, en règle générale, un développeur novice utilisant la fonctionnalité prête à l'emploi du langage manque la chose la plus importante - sa structure et ses mécanismes de fonctionnement et de mise en œuvre.
Je n'entrerai pas dans les détails de l'allocation mémoire et des manières d'interpréter le code, mais au contraire, je voudrais parler du compilateur lui-même, à savoir l'analyseur lexical, et essayer de l'implémenter en C #. L'écrasante majorité connaît le langage que nous allons analyser - c'est Pascal.
L'analyseur lexical est la première des «couches» du compilateur responsable de la mise en évidence des jetons pour un traitement ultérieur.
Un lexème est la plus petite unité d'un dictionnaire qui représente notre langue. Les mots de service, les opérateurs, les identifiants, etc. peuvent servir de jeton.
la mise en oeuvre
Description de la structure
La description formelle du langage sera stockée dans deux tableaux: dans le premier - mots de service, et dans le second - délimiteurs et une liste avec les jetons trouvés
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>();Le lexème lui-même stockera la clé, qui sera utilisée pour déterminer l'appartenance au type (mots de service, opérateurs, identificateurs, nombres), l'identifiant du jeton et la valeur elle-même.
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;
}
}
La meilleure solution pour traiter les jetons est une machine à états. Cela éliminera les ifs inutiles et facilitera également la modification de la boucle. S est l'état initial, NUM, DLM, ASGN, ID est l'état des types de jetons correspondants, ER sera utilisé pour l'erreur et FIN pour l'état final.
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; //
Les principales méthodes sont SearchLex, qui recherche un jeton dans notre tableau et renvoie son id et sa valeur dans un tuple (oui, les tuples peuvent également être utiles), et PushLex, qui ajoute un nouveau jeton au dictionnaire.
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);
}
}
Implémentation d'algorithme
La première étape consiste à déterminer la fin du cycle - l'état FIN, et également à implémenter l'état initial, qui sera
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;
}
}
La méthode GetNext vous permet d'obtenir le caractère suivant dans la chaîne, ClearBuf, respectivement, efface le tampon qui stocke le jeton
private void GetNext()
{
sr.Read(sm, 0, 1);
}
Une attention particulière doit être accordée à l'opérateur d'affectation ": =", qui se compose de deux opérateurs distincts. La manière la plus simple de définir cet opérateur est d'ajouter une condition et d'écrire la valeur intermédiaire dans le tampon. Pour cela, un état ASGN séparé a été implémenté ( en traduction, assign - assignation ). Si le tampon est défini comme ":", l'algorithme ajoutera simplement un nouveau jeton, et si le signe suivant est "=", alors un opérateur d'affectation sera ajouté.
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;
L'état final et l'état avec une erreur sont implémentés uniquement par les messages de service. Vous pouvez améliorer cette option et vérifier également l'erreur, mais peut-être que cette fonctionnalité peut déjà être transférée vers l'analyseur.
case States.ER:
MessageBox.Show(" ");
state = States.FIN;
break;
case States.FIN:
MessageBox.Show(" ");
break;
Essai
Vous pouvez tester l'algorithme de différentes manières: spécifiez directement le chemin du fichier .pas , créez une chaîne par programme ou toute autre option pratique. Puisque nous écrivons en C #, il ne sera pas difficile d'ajouter un formulaire à l'application, qui contiendra 2 textBoxes, le premier pour entrer le code du programme, le second - affiche le résultat de l'algorithme.
En appuyant sur le bouton, nous allons lancer l'analyse de texte, et le résultat obtenu sera traité en utilisant la construction du commutateur : en plus, nous afficherons le type du jeton trouvé.
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;
}
}
}
Des données d'entrée
program hellohabr;
var a, b, c : integer;
begin
c := a - b + 15;
end.
Production
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: . |
Algorithme complet
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;
}
}
}
Conclusion
Il peut sembler que l'analyseur lexical n'est pas une chose très claire, et en fait pas très importante. Pourquoi ne pouvez-vous pas mettre tout cela dans un analyseur? Comment travailler avec des structures complexes? Oui, les façons d'implémenter l'analyseur lexical diffèrent d'un compilateur à l'autre, mais lorsque vous analyserez tous ces principes, vous comprendrez non seulement comment fonctionne le langage de programmation X, mais vous aurez également une base pour développer votre propre langage de programmation: un deuxième Python, ou un langage pour votre domaine - tout cela est possible réaliser avec compréhension de toutes les spécificités du travail et du dispositif du compilateur en général
Le projet peut être trouvé ici