Einführung
In letzter Zeit beginnen die meisten Programmieranfänger mit Hochsprachen wie Java, Python, C # oder einer anderen Sprache, die einen „Gentleman-Satz“ in Form eines Garbage Collectors, vorgefertigter Datenstrukturen usw. enthält. Natürlich hat dieser Ansatz seine Vorteile, aber in der Regel übersieht ein unerfahrener Entwickler, der vorgefertigte Sprachfunktionen verwendet, das Wichtigste - seine Struktur und seine Funktions- und Implementierungsmechanismen.
Ich werde nicht auf die Details der Speicherzuweisung und die Interpretationsmöglichkeiten des Codes eingehen, sondern im Gegenteil, ich möchte über den Compiler selbst sprechen, nämlich den lexikalischen Analysator, und versuchen, ihn in C # zu implementieren. Die überwiegende Mehrheit kennt die Sprache, die wir analysieren werden - es ist Pascal.
Der lexikalische Analysator ist die erste der „Ebenen“ des Compilers, die für das Hervorheben von Token für die weitere Verarbeitung verantwortlich sind.
Ein Lexem ist die kleinste Einheit eines Wörterbuchs, die unsere Sprache darstellt. Servicewörter, Operatoren, Bezeichner usw. können als Token dienen.
Implementierung
Beschreibung der Struktur
Die formale Beschreibung der Sprache wird in zwei Arrays gespeichert: in den ersten Dienstwörtern und in den zweiten Trennzeichen und einer Liste mit gefundenen Token
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>();Das Lexem selbst speichert den Schlüssel, mit dem der Typ (Servicewörter, Operatoren, Bezeichner, Zahlen), die ID des Tokens und der Wert selbst bestimmt werden.
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;
}
}
Die beste Lösung für die Verarbeitung von Token ist eine Zustandsmaschine. Dadurch werden unnötige if-s beseitigt und es ist auch einfach, Änderungen an der Schleife vorzunehmen. S ist der Anfangszustand, NUM, DLM, ASGN, ID ist der Zustand der entsprechenden Token-Typen, ER wird für Fehler verwendet und FIN für den Endzustand.
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; //
Die Hauptmethoden sind SearchLex, das in unserem Array nach einem Token sucht und dessen ID und Wert in einem Tupel zurückgibt (ja, Tupel können ebenfalls nützlich sein), und PushLex, das dem Wörterbuch ein neues Token hinzufügt.
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);
}
}
Implementierung des Algorithmus
Der erste Schritt besteht darin, das Ende des Zyklus - den FIN-Zustand - zu bestimmen und auch den Anfangszustand zu implementieren, der sein wird
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;
}
}
Mit der GetNext-Methode können Sie das nächste Zeichen in der Zeichenfolge abrufen. ClearBuf löscht den Puffer, in dem das Token gespeichert ist
private void GetNext()
{
sr.Read(sm, 0, 1);
}
Besondere Aufmerksamkeit sollte dem Zuweisungsoperator ": =" gewidmet werden, der aus zwei separaten Operatoren besteht. Die einfachste Möglichkeit, diesen Operator zu definieren, besteht darin, eine Bedingung hinzuzufügen und den Zwischenwert in den Puffer zu schreiben. Hierzu wurde ein separater ASGN-Status implementiert ( in Übersetzung, Zuweisung - Zuweisung ). Wenn der Puffer als ":" definiert ist, fügt der Algorithmus einfach ein neues Token hinzu, und wenn das nächste Vorzeichen "=" ist, wird ein Zuweisungsoperator hinzugefügt.
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;
Der Endzustand und der Zustand mit einem Fehler werden nur durch Dienstnachrichten implementiert. Sie können diese Option verbessern und den Fehler auch überprüfen, aber möglicherweise kann diese Funktionalität auf den Parser übertragen werden.
case States.ER:
MessageBox.Show(" ");
state = States.FIN;
break;
case States.FIN:
MessageBox.Show(" ");
break;
Testen
Sie können den Algorithmus auf verschiedene Arten testen: Geben Sie den Pfad der .pas- Datei direkt an , erstellen Sie programmgesteuert eine Zeichenfolge oder eine andere praktische Option. Da wir in C # schreiben, wird es nicht schwierig sein, der Anwendung ein Formular hinzuzufügen, das 2 Textfelder enthält, das erste zur Eingabe des Programmcodes, das zweite - zeigt das Ergebnis des Algorithmus an.
Durch Drücken der Schaltfläche starten wir die Textanalyse und das resultierende Ergebnis wird mithilfe der Schalterkonstruktion verarbeitet. Außerdem wird der Typ des gefundenen Tokens angezeigt.
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;
}
}
}
Eingabedaten
program hellohabr;
var a, b, c : integer;
begin
c := a - b + 15;
end.
Ausgabe
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: . |
Kompletter Algorithmus
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;
}
}
}
Fazit
Es scheint, dass der lexikalische Analysator keine sehr klare Sache ist und tatsächlich nicht sehr wichtig. Warum können Sie das alles nicht in einen Parser schreiben? Wie arbeite ich mit komplexen Strukturen? Ja, die Möglichkeiten zur Implementierung des lexikalischen Analysators unterscheiden sich von Compiler zu Compiler. Wenn Sie jedoch alle diese Prinzipien analysieren, werden Sie nicht nur verstehen, wie die Programmiersprache X funktioniert, sondern Sie haben auch eine Grundlage für die Entwicklung Ihrer eigenen Programmiersprache: ein zweites Python oder eine Sprache für Ihre Domäne - all dies ist möglich mit Verständnis aller Besonderheiten der Arbeit und des Geräts des Compilers im Allgemeinen zu realisieren.
Das Projekt finden Sie hier