Introducción
Recientemente, la mayoría de los principiantes en la programación comienzan con lenguajes de alto nivel como Java, Python, C # o cualquier otro lenguaje que contenga un "conjunto de caballeros" en forma de recolector de basura, estructuras de datos listas para usar, etc. Por supuesto, este enfoque tiene sus ventajas, pero, por regla general, un desarrollador novato que utiliza la funcionalidad prefabricada del lenguaje pierde lo más importante: su estructura y mecanismos de operación e implementación.
No entraré en detalles sobre la asignación de memoria y las formas de interpretar el código, sino por el contrario, me gustaría hablar sobre el compilador en sí, es decir, el analizador léxico e intentar implementarlo en C #. La inmensa mayoría conoce el idioma que analizaremos, es Pascal.
El analizador léxico es la primera de las "capas" del compilador responsable de resaltar los tokens para su posterior procesamiento.
Un lexema es la unidad más pequeña de un diccionario que representa nuestro idioma. Las palabras de servicio, operadores, identificadores, etc. pueden servir como token.
Implementación
Descripción de la estructura
La descripción formal del lenguaje se almacenará en dos matrices: en la primera - palabras de función, y en la segunda - delimitadores y una lista con tokens encontrados
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>();El propio lexema almacenará la clave, que se utilizará para determinar el tipo (palabras de servicio, operadores, identificadores, números), la identificación del token y el valor en sí.
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 mejor solución para procesar tokens es una máquina de estado. Esto eliminará los if-s innecesarios y también facilitará la realización de cambios en el bucle. S es el estado inicial, NUM, DLM, ASGN, ID es el estado de los tipos de tokens correspondientes, ER se utilizará para el error y FIN para el estado 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; //
Los métodos principales son SearchLex, que busca un token en nuestra matriz y devuelve su id y valor en una tupla (sí, las tuplas también pueden ser útiles), y PushLex, que agrega un nuevo token al diccionario.
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);
}
}
Implementación de algoritmos
El primer paso es determinar el final del ciclo, el estado FIN, y también implementar el estado inicial, que será
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;
}
}
El método GetNext le permite obtener el siguiente carácter de la cadena, ClearBuf, respectivamente, borra el búfer que almacena el token
private void GetNext()
{
sr.Read(sm, 0, 1);
}
Se debe prestar especial atención al operador de asignación ": =", que consta de dos operadores separados. La forma más sencilla de definir este operador es agregar una condición y escribir un valor intermedio en el búfer. Para esto, se implementó un estado ASGN separado ( en asignación de traducción - asignación ). Si el búfer se define como ":", el algoritmo simplemente agregará un nuevo token, y si el siguiente signo es "=", se agregará un operador de asignación.
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;
El estado final y el estado con error solo se implementan mediante mensajes de servicio. Puede mejorar esta opción y verificar el error también, pero tal vez esta funcionalidad se pueda transferir al analizador.
case States.ER:
MessageBox.Show(" ");
state = States.FIN;
break;
case States.FIN:
MessageBox.Show(" ");
break;
Pruebas
Puede probar el algoritmo de diferentes maneras: especifique la ruta del archivo .pas directamente , cree una cadena mediante programación o cualquier otra opción conveniente. Como estamos escribiendo en C #, no será difícil agregar un formulario a la aplicación, que tendrá 2 textBoxes, el primero para ingresar el código del programa, el segundo, muestra el resultado del algoritmo.
Al presionar el botón, iniciaremos el análisis de texto, y el resultado resultante se procesará usando la construcción del interruptor : además, mostraremos el tipo de token encontrado.
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;
}
}
}
Los datos de entrada
program hellohabr;
var a, b, c : integer;
begin
c := a - b + 15;
end.
Salida
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: . |
Algoritmo completo
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;
}
}
}
Conclusión
Puede parecer que el analizador léxico no es una cosa muy clara y, en realidad, no es muy importante. ¿Por qué no puedes poner todo esto en un analizador? ¿Cómo trabajar con estructuras complejas? Sí, las formas de implementar el analizador léxico difieren de un compilador a otro, pero cuando analice todos estos principios, no solo comprenderá cómo funciona el lenguaje de programación X, sino que también tendrá una base para desarrollar su propio lenguaje de programación: un segundo Python, o un lenguaje para su dominio, todo esto es posible. darse cuenta con comprensión de todos los detalles del trabajo y el dispositivo del compilador en general.
El proyecto se puede encontrar aquí