Home » Java » antlr » Tutorial ANTLR – parte 2 – Fases da Compilação

Tutorial ANTLR – parte 2 – Fases da Compilação

Fatos aparentemente ruins por vezes  geram bons resultados. Uma torção no joelho me deu a ‘quietude’ para dar uma renovada neste artigo, já escrito há algum tempo, portanto a moral é : “torça forte que as coisas acontecem”  !! wlEmoticon-smile.png

Quando aprendemos uma nova linguagem de programação, é comum encontrarmos como primeiro exemplo, uma versão do mítico Hello World. Esse é sempre o código mais simples possível para apresentar na tela(no terminal, no browser etc)  a string “Hello World”. Dessa forma começamos a conhecer os elementos básicos de uma linguagem de programação e os processos que envolvem sua compilação ou interpretação.

Na linguagem C o Helllo-World (um pouco mais eloquente) poderia ser algo assim:
… e vamos usá-lo como base para nossa discussão.
Para compilarmos usando o gcc, basta digitar  :
e ao executarmos,  mostrará no terminal :

A compilação é feita em milisegundos sem que possamos ver a magia acontecendo, logo veremos as etapas a seguir .

Compilação

A linha “gcc hello.cpp -o hello” executa o pré-processador, compilador e link editor respectivamente, no entanto o foco do artigo trata apenas da compilação, logo nos deteremos apenas a isto por que o assunto é realmente muito profícuo.

O processo de  compilação de uma linguagem normalmente envolve 3 etapas, são elas :
  •  Análise Léxica
  •  Análise Sintática
  •  Análise Semântica

Análise Léxica

Na análise léxica os caracteres, lidos um a um, são agrupados em entidades chamadas tokens.
token
Tokens são a identificação que certas palavras possuem em uma gramática de uma determinada  linguagem. Já os lexemas são as palavras propriamente ditas.
Por exemplo, o analisador léxico, ao encontrar os caracteres  ‘i’,  ‘n’,  ‘t’ e ‘ ‘ (linha 3) irá agrupá-los e criar um  lexema com a string “int” e identificá-lo com algum token que represente esta cadeia de caracteres. Os lexemas não são nada mais do que identificadores dos tipos de elementos existentes em nossa linguagem. A palavra reservada “int” (lexema) em C poderia ser representada através do token “type_specifier” .   Os tokens identificam um determinado tipo de palavra reservada .
Quando estudávamos português no primário, já funcionávamos como Analisador Léxico,  quando a tia Teteca nos pedia para identificarmos os verbos, substantivos, adjetivos e pronomes em uma frase. Naquele momento estávamos identificando os tokens  em uma frase; ou seja, o que era verbo, substantivo e assim por diante. Processo semelhante ao que ocorre nos compiladores.
 analisador-lexico
Análise Léxica é responsável por:
  • Ler o texto fonte, caracter a caracter
  • Identificar os “elementos léxicos” da linguagem, ou seja, suas  palavras reservadas, identificadores, constantes, operadores e identificar cada unidade através do par token / lexema.
  • Ignorar comentários, brancos, tabs
  • Processar imports, includes etc

Análise Sintática 

 Na análise sintática, os tokens identificados na análise léxica, são lidos um a um para verificar se na medida que estão sendo lidos formam estruturas definidas na gramática da linguagem. Por exemplo, voltando ao primário, se  tia Teteca nos disesse que toda frase deve obedecer unicamente a forma :
“Pronome + Verbo +  substantivo”
Uma frase que atenderia a essa estrutura seria “Ela comprou livros“, pois
Ela é pronome
comprou é verbo
livros é  substantivo
No entanto se a frase fosse “Ela livros comprou” estaria errada por que após o pronome Ela  esperaríamos um verbo e encontramos no lugar previsto o substantivo livros.  Erro !
O nosso analisador sintático humano é muito mais flexível que o das linguagens formais onde as regras devem ser explicitamente muito bem definidas.
Para representarmos uma regra em ANTLR usamos uma notação semelhante a  EBNF ou Extended Backus-Naur . EBNF  é uma meta-sintaxe, isto é, uma sintaxe usada para definir outras sintaxes susto
 Em ANTLR, alguns dos tipos primitivos da linguagem C poderiam ser representados assim:

Com a declaração acima definimos o token “type_specifier“, ou seja,  sempre que uma sequência de caracteres separados pelos delimitadores (veremos no próximo artigo para que servem e como são definidos) e que coincidam com uma das strings (lexemas) ‘void’, ‘char’, ‘short’, ‘int’ etc será gerado um token e identificado como type_specifier.
Já para termos em uma linguagem, a possibilidade de se declarar uma variável usando um dos tipos previamente definidos, temos de definir uma regra para identificá-las, para isso deveremos ter um  tipo (type_specifier) seguido de um identificador (nome da variável)  e finalizado com ponto-e-vírgula. Ex: “int valor;” (linha 4)

type_specifier LetterIdentifiervarDeclaration

A ordem de definição das regras não importa, ou seja , não prejudica nem modifica nada se varDeclaration vem antes ou depois type_specifier, no entanto todos os elementos referidos devem estar declarados, caso contrário ocorrerá um  erro  de referência não especificada. Normalmente parte-se das macro definições  para gradativamente particularizar cada vez mais. Mas tudo isto será visto no próximo artigo onde abordarei o assunto de como construir uma gramática para uma linguagem.

Durante a análise sintática os tokens serão lidos sequencialmente tentando identificar uma construção previamente definida na linguagem.  Mas veja que elementos da linguagem podem ser  constituídos por um ou mais elementos  e cada um destes representar outros elementos  recursivamente; dessa forma, o resultado final da análise sintática é conhecida como AST (Abstract Syntax Tree) ou Árvore Abstrata de Sintaxe.
Esse é um conceito muito importante, pois ao caminharmos pelo código para compilá-lo, interpretá-lo ou apenas para filtrar algo de nosso interesse, devemos ter em mente que as regras estabelecidas em nossa gramática estabelecerão ramos, logo quando estivermos manipulando os elementos da linguagem e quisermos, por exemplo, listar a definição de todas as variáveis declaradas no código fonte, será necessário apenas inserir um tratamento especial quando o ramo varDeclaration for visitado.

Portanto o trecho de código acima geraria um ramo na AST semelhante ao qual pode ser visto na imagem abaixo.. varDeclaration

Análise Sintática é responsável por: :
  • Reconhecer na sequência de elementos léxicos, reconhecidos na fase anterior, se existem  construções definidas na linguagem e construir a Árvore Sintática que representará o código fonte. 
      
 

Análise Semântica

 
A análise semântica verifica se os elementos identificados na análise sintática estão de acordo com as regras estabelecidas para a linguagem. Por exemplo, em java o if deverá sempre ser seguido por uma expressão booleana, logo o trecho :
 

geraria um erro semântico em java , pois 1 não é um operando booleano (são eles ‘true’ e ‘false’); no entanto tal código em C e C++ é correto. ANTLR provê “gratuitamente” a análise léxica e sintática, inclusive com a geração de erros para estas 2 primeiras etapas, no entanto a análise semântica deverá ser programada.

 A validação de variáveis e seus tipos, além da verificação do escopo destas também é um exemplo de uma verificação feita durante a fase da análise semântica.
 No próximo artigo veremos  como criar definir uma gramática e como ANTLR faz todo o “tarbalho sujo” ao gerar as classes que nos auxiliam para manipular todos os elementos da  linguagem.
 
 

Referência

  1. Extended Backus–Naur Form
  2. Formalismo de Backus-Naur
  3. AST
  4. Lista de gramáticas – ANTLR 4
3451 Total 9 Visualizações

About 

System development consultant
He graduated from UFF in Software development
A lot of experience in development process and management .
International expertise : USA (1 yr) and Italy (3 yrs) where He played as system team leader .
Fluently in italian and english.
He Lives now in Rio de Janeiro, Brazil

    Find more about me on:
  • googleplus
,
  • Pingback: Tutorial ANTLR – parte 1 – Apresentação | marceloaleks.com()

  • Marcus Aleks

    Parabéns! Belo artigo sobre Another Tool for Language Recognition (ANTLR)! Keep it up! =]

    • Marcelo Aleksandravicius

      Obrigado meu amigão!

  • John Goldsmith

    Perfect!! I´ve read it using the google translator and the translation was almost perfect. Please write about the grammar construction and how to create the visitors ans listeners classes ! Thanks !

    .

    • admin

      The next article will be just about how to parse the code using visitors and listeners. With a little knowledge about the grammar syntax and how to parse the code, everyone will be able to create its own language. Best Regards!!!

  • Roberto Tinoco da Silva

    Parabéns! Gostei muito do artigo, no entanto precisa escrever logo o artigo apresentando o código para implementar o parser da linguagem. Abraço e feliz ano novo !!!!

    • Marcelo Aleksandravicius

      Em breve ! Grande abraço !