Recursive descendent parser

Posted on maio 30, 2011 by

1


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.

Smiley piscando

Posted in: C++, compiladores