Olá pessoal, como estamos?
No último post mostrei uma alternativa bacana para converter uma sequência de caracteres em sequência de tokens. Hoje, vou mostrar como implementar um parser simples para validar um programa conforme uma gramática LL(1).
A técnica utilizada é bastante simples e é chamada de “Recursive descendent parser”.
Gramática para avaliação de expressões matemáticas simples
Não pretendo dar tanta atenção a gramática que estaremos suportando. Para manter a simplicidade, escolhi uma gramática simples para expressões matemáticas. Considere:
expr : term term_tail;
term_tail
: add_op term term_tail | ;
term : factor factor_tail;
factor_tail
: mult_op factor factor_tail |;
factor : '(' expr ')' | NUMBER;
add_op : '+' | '-';
mult_op : '*' | '/';
A gramática acima, escrita na sintaxe do ANTLR (embora incompleta), indica como reconhecer expressões matemáticas. Perceba como tudo começa em expr. Perceba também que recorro a predição epsilon nas implementações term_tail e factor_tail.
Escrevendo um “Recursive descendent parser”
Escrever um “recursive descendent parser” é bem simples. Para começar, escrevemos um método correspondendo a cada não-terminal da gramática. Para facilitar a identificação, recomenda-se manter a mesma identificação.
No código de cada um dos métodos, chamamos o método relacionado, para não terminais, ou um método de encerramento (Match) para terminais. Além disso, mantemos um atributo chamado “input_token” com o “token de trabalho” . O método Match para “consome” e atualiza esse token.
Se ocorrer algum “match” imprevisto, então um erro de sintaxe é lançado. Veja a implementação (parcial) da classe Parser:
void Expr()
{
Begin("Expr");
switch (input_token.Id)
{
case "integer":
case "float":
case "lparen":
Term();
TermTail();
break;
default:
throw new UnexpectedTokenException(input_token);
}
End();
}
void TermTail()
{
Begin("TermTail");
switch (input_token.Id)
{
case "plus":
case "minus":
AddOp();
Term();
TermTail();
break;
case "rparen":
case "EOP":
Skip();
break;
default:
throw new UnexpectedTokenException(input_token);
}
End();
}
void Term()
{
Begin("Term");
switch (input_token.Id)
{
case "integer":
case "float":
case "lparen":
Factor();
FactorTail();
break;
default:
throw new UnexpectedTokenException(input_token);
}
End();
}
void FactorTail()
{
Begin("FactorTail");
switch (input_token.Id)
{
case "times":
case "divide":
MultOp();
Factor();
FactorTail();
break;
case "plus":
case "minus":
case "rparen":
case "EOP":
Skip();
break;
default:
throw new UnexpectedTokenException(input_token);
}
End();
}
void Factor()
{
Begin("Factor");
switch (input_token.Id)
{
case "float":
case "integer":
Match(input_token.Id);
break;
case "lparen":
Match("lparen");
Expr();
Match("rparen");
break;
default:
throw new UnexpectedTokenException(input_token);
}
End();
}
void AddOp()
{
Begin("AddOp");
switch (input_token.Id)
{
case "plus":
case "minus":
Match(input_token.Id);
break;
default:
throw new UnexpectedTokenException(input_token);
}
End();
}
void MultOp()
{
Begin("MultOp");
switch (input_token.Id)
{
case "times":
case "divide":
Match(input_token.Id);
break;
default:
throw new UnexpectedTokenException(input_token);
}
End();
}
Perceba que estou utilizando o Scanner do post anterior para gerar a lista de tokens que vou processar aqui. Os métodos Begin e End, que aparecem no código, servem para ajudar a instrumentar o resultado.
Faça um teste “de mesa” e perceba como o fluxo ocorre.
Interface pública e métodos de apoio do Parser
O código que apresentei acima consiste na “lógica” principal do parser. Entretanto, para funcionar, precisa de alguns métodos de apoio. Apresento esses métodos, junto com a interface pública da classe a seguir:
public class ExpressionParser : IDisposable
{
public IEnumerable Source { get; private set; }
public ExpressionParser(IEnumerable source)
{
this.Source = source;
}
IEnumerator SourceEnumerator;
Token input_token;
Token GetNextToken()
{
while (this.SourceEnumerator.MoveNext())
{
var result = this.SourceEnumerator.Current;
return result;
}
return new Token("EOP", null);
}
public void Dispose()
{
this.SourceEnumerator.Dispose();
}
public void Parse()
{
if (this.SourceEnumerator != null)
this.SourceEnumerator.Dispose();
this.SourceEnumerator = this.Source.GetEnumerator();
input_token = GetNextToken();
Expr();
Match("EOP");
}
void Skip()
{ Begin("Epsilon"); End(); }
void Match(string tokenType)
{
if (input_token.Id == tokenType)
{
Begin(input_token.ToString()); End();
input_token = GetNextToken();
}
else
throw new UnexpectedTokenException(input_token);
}
private void End()
{
ident--;
}
int ident = 0;
private void Begin(string p)
{
Console.WriteLine("{0}{1}", new String(' ', ident), p);
ident++;
}
// aqui entram os métodos indicados acima
}
Repare como o método Parse controla o estado do enumerator. Descartando-o se necessário.
Alguns resultados…
O código, como foi implementado, serve apenas para validar um código na gramática que foi proposta (Repare que uma Exception é lançada caso uma expressão inválida seja submetida). Para atender outras etapas de compilação, seria necessário criar alguma forma de representação “em árvore” que indicasse a relação dos tokens e a gramática.
Para não deixar a coisa totalmente “em branco”, introduzi algum código de log. O código desse log gera uma “representação” da árvore resultante do processo de parsing. Considere…
Solicitando o Parse de 2+2/2, temos:
Expr
Term
Factor
2 (integer)
FactorTail
Epsilon
TermTail
AddOp
+ (plus)
Term
Factor
2 (integer)
FactorTail
MultOp
/ (divide)
Factor
2 (integer)
FactorTail
Epsilon
TermTail
Epsilon
(EOP)
Agora, para 2*4-5.
Expr
Term
Factor
2 (integer)
FactorTail
MultOp
* (times)
Factor
4 (integer)
FactorTail
Epsilon
TermTail
AddOp
- (minus)
Term
Factor
5 (integer)
FactorTail
Epsilon
TermTail
Epsilon
(EOP)
Perceba nessas duas indicações, como o código reconhece e respeita as precedências para operações de multiplicação/divisão sobre a adição/subtração. Mais um exemplo 2*(4-5).
Expr
Term
Factor
2 (integer)
FactorTail
MultOp
* (times)
Factor
( (lparen)
Expr
Term
Factor
4 (integer)
FactorTail
Epsilon
TermTail
AddOp
- (minus)
Term
Factor
5 (integer)
FactorTail
Epsilon
TermTail
Epsilon
) (rparen)
FactorTail
Epsilon
TermTail
Epsilon
(EOP)
Veja como o resultado se ajusta lindamente devolvendo a precedência para os parênteses.
Em posts futuros apresento outras formas de fazer o parsing, bem como uma estrutra de dados para “armazenar” o resultado do parse.
Por hoje, era isso.
junho 1st, 2011 → 1:36 am
[...] dia falei sobre como reconhecer tokens em cadeias de caracteres. Depois, falei como fazer o parsing destes tokens conforme uma gramática LL(1). São conhecimentos fundamentais para quem pretende entender como [...]