Introdução
Recentemente, a maioria dos novatos em programação começa com linguagens de alto nível, como Java, Python, C # ou qualquer outra linguagem que contenha um "conjunto de cavalheiros" na forma de um coletor de lixo, estruturas de dados prontas e assim por diante. Claro, essa abordagem tem suas vantagens, mas, como regra, um desenvolvedor novato que usa a funcionalidade de linguagem pronta perde o mais importante - sua estrutura e mecanismos de operação e implementação.
Não vou entrar em detalhes sobre alocação de memória e maneiras de interpretar o código, mas pelo contrário, gostaria de falar sobre o próprio compilador, ou seja, o analisador léxico, e tentar implementá-lo em C #. A esmagadora maioria conhece a linguagem que iremos analisar - é Pascal.
O analisador léxico é a primeira das “camadas” do compilador responsável por destacar tokens para processamento posterior.
Um lexema é a menor unidade de um dicionário que representa nossa língua. Palavras de serviço, operadores, identificadores e assim por diante podem servir como um token.
Implementação
Descrição da estrutura
A descrição formal da linguagem será armazenada em duas matrizes: na primeira - palavras de serviço, e na segunda - delimitadores e uma lista com 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>();O próprio lexema armazenará a chave, que será usada para determinar a associação do tipo (palavras de serviço, operadores, identificadores, números), o id do token e o próprio valor.
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;
}
}
A melhor solução para processar tokens é uma máquina de estado. Isso eliminará ifs desnecessários e também tornará mais fácil fazer alterações no loop. S é o estado inicial, NUM, DLM, ASGN, ID é o estado dos tipos correspondentes de tokens, ER será usado para erro e FIN para o 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; //
Os métodos principais são SearchLex, que procura um token em nosso array e retorna seu id e valor em uma tupla (sim, tuplas também podem ser úteis), e PushLex, que adiciona um novo token ao dicionário.
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);
}
}
Implementação de algoritmo
O primeiro passo é determinar o fim do loop - o estado FIN, e também implementar o 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;
}
}
O método GetNext permite que você obtenha o próximo caractere na string, ClearBuf, respectivamente, limpa o buffer que armazena o token
private void GetNext()
{
sr.Read(sm, 0, 1);
}
Deve-se prestar atenção especial ao operador de atribuição ": =", que consiste em dois operadores separados. A maneira mais simples de definir esse operador é adicionar uma condição e gravar o valor intermediário no buffer. Para isso, um estado ASGN separado foi implementado ( na tradução, atribuição - atribuição ). Se o buffer for definido como ":", o algoritmo simplesmente adicionará um novo token e, se o próximo sinal for "=", um operador de atribuição será adicionado.
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;
O estado final e o estado com erro são implementados apenas por mensagens de serviço. Você pode melhorar esta opção e verificar o erro também, mas talvez essa funcionalidade possa ser transferida para o analisador.
case States.ER:
MessageBox.Show(" ");
state = States.FIN;
break;
case States.FIN:
MessageBox.Show(" ");
break;
Testando
Você pode testar o algoritmo de diferentes maneiras: especifique o caminho do arquivo .pas diretamente , crie programaticamente uma string ou qualquer outra opção conveniente. Como estamos escrevendo em C #, não será difícil adicionar um formulário ao aplicativo, que terá 2 textBoxes, o primeiro para inserir o código do programa, o segundo - exibe o resultado do algoritmo.
Pressionando o botão, iniciaremos a análise do texto, e o resultado resultante será processado usando a construção do switch : além disso, exibiremos o tipo do 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;
}
}
}
Dados de entrada
program hellohabr;
var a, b, c : integer;
begin
c := a - b + 15;
end.
Resultado
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;
}
}
}
Conclusão
Pode parecer que o analisador léxico não é uma coisa muito clara e, na verdade, não é muito importante. Por que você não pode colocar tudo isso em um analisador? Como trabalhar com estruturas complexas? Sim, as maneiras de implementar o analisador léxico diferem de compilador para compilador, mas ao analisar todos esses princípios, você não só entenderá como a linguagem de programação X funciona, mas também terá uma base para desenvolver sua própria linguagem de programação: um segundo Python ou uma linguagem para seu domínio - tudo isso é possível perceber com compreensão de todas as especificidades do trabalho e do dispositivo do compilador em geral.
O projeto pode ser encontrado aqui