JavaCC
| Versão estável | 4.0 (2 de janeiro de 2006) |
| Gênero(s) | gerador de analisador sintático |
| Licença | BSD |
| Página oficial | javacc.dev.java.net |
JavaCC (Java Compiler Compiler) é um gerador de analisador sintático aberto para a linguagem Java. É similar ao yacc na medida em que gera um analisador sintático duma gramática fornecida num Formalismo de Backus-Naur Estendido, exceto pelo fato da saída ser em Java. Entretanto, o JavaCC gera analisadores sintáticos descendentes, o que o limita às classes gramaticais LL(k) (excluindo, por exemplo, recursividade à esquerda).
Ver também
[editar | editar código-fonte]Ligações externas
[editar | editar código-fonte]
Breve histórico
JavaCC é um gerador de analisador sintático e um gerador de analisador léxico. Analisadores sintáticos e analisadores léxicos são componentes de software para lidar com entrada de seqüências de caracteres. Compiladores e interpretadores incorporam analisadores léxicos e analisadores sintáticos para decifrar arquivos contendo programas, entretanto, analisadores léxicos e analisadores sintáticos podem ser utilizados em uma grande variedade de outras aplicações,.
Então, quais são os analisadores léxicos e analisadores sintáticos? Analisadores léxicos podem quebrar uma sequência de caracteres em uma subsequência chamada de tokens e também classificar os tokens.
Em 1996, a Sun Microsystems lançou um gerador de analisador chamado Jack.
Os desenvolvedores responsáveis por Jack criaram sua própria empresa chamada Metamata e mudou o nome para Jack JavaCC. Metamata eventualmente tornou-se parte de WebGain.
Após WebGain encerrar suas operações, JavaCC foi transferida para sua atual casa.
JavaCC (Java Compiler Compiler) é um gerador de analisador sintático aberto para a linguagem Java.
É similar ao YACC na medida em que gera um analisador sintático de uma gramática fornecida num Formalismo de Backus-Naur Estendido, exceto pelo fato da saída ser em Java, entretanto, o JavaCC gera analisadores sintáticos descendentes, o que o limita às classes gramaticais LL(k) (excluindo, por exemplo, recursividade à esquerda).
JavaCC é um gerador para lexers Java e analisadores de Java. A lexer Java é um gerador de analisador, é uma ferramenta que lê uma especificação de gramática e converte-o para um programa em Java que pode reconhecer partidas com a gramática.
Análise léxica, ou "léxico", é o processo de converter uma seqüência de caracteres em uma seqüência de tokens.
A funcionalidade que realiza a análise léxica é chamado de analisador léxico, um analisador léxico, ou um scanner.
Um Analisador léxico normalmente existe como uma única função chamada por um parser.
Por exemplo, enquanto um léxico típico reconhece parênteses como tokens, que não faz nada para garantir que um parênteses de abertura é acompanhada por um parênteses de fechamento, o que é uma tarefa para um parser.
2 JAVACC – Java Compiler Compiler
JavaCC (Java Compiler-Compiler) é uma ferramenta gratuita desenvolvida em Java que gera analisadores sintáticos e léxicos em Java. Similar aos já bem conhecidos Lex e YACC para ambientes Unix, a vantagem é que o código gerado pelo JavaCC é muito mais simples de ser lido por um ser humano.
O JavaCC toma como entrada um arquivo de especificação de gramática. Este arquivo tem uma estrutura muito similar a notação BNF (Backus Naur Form). Além da descrição da gramática, o arquivo pode conter também código Java embutido entre as construções da gramática, o que provém grande flexibilidade para os analisadores gerados.
Entretanto, o JavaCC não tem disponível muita documentação, excetuando-se os exemplos que acompanham o pacote de instalação e (num nível mais avançado) os repositórios de gramáticas disponíveis na Internet. Kodaganallur(2004) oferece um tutorial sobre o uso do JavaCC, com casos de uso do mesmo.
O JavaCC disponibiliza uma extensão da linguagem Java que permite especificar gramáticas para linguagens de programação, desenvolvido inicialmente pela Sun Microsystems e atualmente mantido pelo Java.net.
Duas ferramentas suportam a implementação com JavaCC:
· Java JJDoc Documentation que, baseado nas especificações do JavaCC, produz documentação nos padrões BNF, permitindo também a geração de um arquivo HTML da estrutura EBNF.
· JavaTree Reference Documentation, que é um pré-processador do JavaCC que produz e manipula árvores sintáticas (representação estruturada em termos de nós) baseadas na especificação da Gramática do JavaCC.
O processo de implementação através do JavaCC passa pela execução de três tarefas principais: análise léxica, análise sintática, geração de código ou execução.
A análise léxica ou gerenciador de tokens examina o código fonte e o divide em tokens. Um token é uma parte do programa com significado específico e, como exemplo têm-se os números, caracteres e pontuação. Em seguida os tokens serão combinados com as respectivas definições da gramática especificada anteriormente com as características da linguagem.
O processo da análise sintática consiste da extração, pelo parser, de significado do programa (sequência de tokens) fonte através da construção de uma representação interna do programa e pela garantia da correta especificação sintática do mesmo.
Durante a análise sintática, o compilador examina o código fonte de acordo com as regras definidas na gramática (define regras para a construção de programas sintaticamente corretos) da linguagem. Se alguma regra desta gramática é violada o compilador reporta uma mensagem de acordo com a violação da regra em questão, ao mesmo tempo gera uma representação interna do código do programa.
3 Principais Particularidades
O JavaCC é o principal compilador em Java, é uma ferramenta que facilita a construção de analisadores sintáticos léxicos pelos métodos de funções recursivas. Dessa forma, os scanners são gerados usando a técnica descendente na obtenção da árvore sintática.
O programa JavaCC é um gerador de analisador léxico e sintático que gera um código Java, dessa forma nosso compilador deve ser desenvolvido na linguagem Java, O JavaCC foi inicialmente desenvolvido pela Sun e atualmente o seu desenvolvimento fica por conta da Oracle.
Este gerador é definido por uma linguagem própria para descrição dos seus afazeres, tanto o analisador léxico como o sintático são descritos no mesmo arquivo, na análise léxica um token pode ser definido na forma de uma expressão regular, veja a tabela abaixo:
|
EXPRESSÃO REGULAR SIMPLES |
|
TOKEN : { < CLASSE : “classe”> |< SENAO : “senao”> |< VIRGULA : “,”> } |
|
EXPRESSÃO REGULAR COMPLEXA |
|
TOKEN : { < STRING_CONST : “\””(~[“\””,”\n”,”\r”])* “\””> } // constante string, “abcd badc” |
Além de Tokens, podem ser definidos para o analisador léxico quais caracteres ou expressões serão ignoradas (SKIP) e também os tokens especiais que são tokens que não são passados para o analisador sintático, mas armazenados e recuperados a partir de um token normal, na tabela abaixo é apresentada a sintaxe do código JavaCC para a análise sintática.
|
ANÁLISE SINTÁTICA | |
|
void Start(): {} { <NUMBER> ( <PLUS> <NUMBER> )* <EOF> } |
Válida a entrada de expressões matemáticas, apenas, com a operação de adição: Ex: 5+8+45 |
Segue abaixo algumas vantagens e desvantagens do compilador JavaCC, além de algumas de suas principais características.
Vantagens
• Gerador de parser 100% Java
– O mais utilizado pela comunidade Java
Analisadores sintáticos (Parsers)
Programas que recebem como entrada um arquivo fonte e diz se ele está correto sintaticamente, segundo uma gramática pré-definida.
• Desenvolvido inicialmente pela Sun
– Hoje é mantido pela java.net
• É um parser top-down
– Mais fácil de depurar
• Utiliza uma sintaxe muito próxima de Java
Desvantagens
– Mistura código Java com a gramática
– Não checa a correção do código Java inserido
– Pode gerar classes que não compilam
4 Características
O JavaCC tem integrado em uma única ferramenta um analisador sintático e léxico, gera um código independente de qualquer biblioteca externa, o que lhe confere uma propriedade interessante de independência em relação ao meio ambiente.
Abaixo temos algumas particularidades do javaCC:
· Gera analisadores descendentes, permitindo o uso de gramáticas de uso geral usando tanto sintetizados e atributos herdados durante a construção da árvore de sintaxe.
· As especificações léxicas e sintáticas estão localizadas em um único arquivo. Assim a gramática pode ser lida e mantida mais facilmente.
· Suporta o uso de estados léxicos e a capacidade de adicionar ações léxicas, incluindo um bloco de códigos Java após a identificação de um TOKEN.
· Incorpora diferentes tipos de TOKEN: Normal (TOKEN), Especial (ESPECIAL_TOKEN), Espaçadores (espaço). Isso permite trabalhar com especificações mais claras, permitindo uma melhor gestão de erro e mensagens de aviso de compilação de tempo Java.
· Símbolos especiais são ignorados pelo analisador gerado, mas estão disponíveis para serem processados pelo desenvolvedor.
· A especificação léxica pode definir os TOKENS para que letras maiúsculas e minúsculas não diferenciem de forma global ou em um padrão específico.
· Adota uma notação BNF próprio usando símbolos próprios regulares.
· Entre os geradores de analisadores descendentes, o JavaCC é o que que melhor faz tratamento de erros. Os analisadores gerados são capazes de localizar a posição exata dos erros, fornecendo informações de diagnóstico completo.
· Permite a entrada de dados Unicode.
· Ativa a depuração tanto através do analisador sintático como no léxico, ou através de algumas opções: DEBUG_PARSER, DEBUG_LOOKAHEAD, DEBUG_TOKEN_MANAGER.
· O JavaCC oferece muitas opções diferentes para personalizar o seu comportamento e desempenho nos analisadores gerados.
· Possui uma ferramenta incluída, o JJTree, é uma ferramenta que possui um pré-processador para o desenvolvimento de árvores com características muito poderosas.
· Inclui ainda a ferramenta JJDoc, que converte os arquivos de gramática em arquivos de documentação.
· Altamente eficiente, sendo adequado para ambientes profissionais, se tornando um dos compiladores mais difundidos.
Exemplos:
O emprego de um analisador está em ler um fluxo de entrada e determinar se ou não o fluxo de entrada está de acordo com a gramática.
Essa determinação, em sua forma mais geral pode ser bastante demorado. Considere o seguinte exemplo:
void Input() :
{}
{
"a" BC() "c"
}
void BC() :
{}
{
"b" [ "c" ]
}
Neste exemplo simples, é bastante claro que há exatamente duas cordas que correspondem a gramática acima, a saber:
abc
ABCC
A forma geral para executar este jogo é percorrer a gramática com base na sequência da seguinte maneira. Aqui, usamos "abc", como a cadeia de entrada:
· Passo 1. Só há uma escolha aqui - o primeiro caractere de entrada deve ser 'a' - e uma vez que é de fato o caso, estamos OK.
· Passo 2. Vamos agora avançar para a não-terminal BC. Aqui, novamente, há apenas uma opção para o caractere de entrada seguinte - deve ser 'b'. A entrada coincide com este também, por isso ainda estamos OK.
· Passo 3. Chegamos agora a um "ponto de escolha" na gramática. Ou nós podemos ir para dentro do [...] e combiná-lo ou ignorá-lo completamente. Decidimos ir para dentro. Assim, o caractere de entrada próximo deve ser um 'c'. Estamos novamente em OK.
· Passo 4. Agora temos concluído com os não-terminal BC e voltar para a entrada de não-terminal. Agora, a gramática diz que o próximo caractere deve ser mais um 'c'. Mas não há mais caracteres de entrada.Então, nós temos um problema.
· Passo 5. Quando temos um problema, no caso geral, podemos concluir que pode ter feito uma má escolha em algum lugar. Neste caso, nós fizemos a má escolha no Passo 3. Então, vamos refazer nossos passos de volta para a etapa 3 e fazer uma outra escolha e tentar isso. Este processo é chamado de "retrocesso".
· Passo 6. Temos agora que voltar atrás e fazer uma outra escolha que poderíamos ter feito no Passo 3 - ou seja, ignorar a [...]. Agora temos concluído com os não-terminal BC e voltar para a entrada de não-terminal.Agora, a gramática diz que o próximo caractere deve ser mais um 'c'. O próximo caractere de entrada é um 'c', por isso estamos bem agora.
· Passo 7. Nós percebemos que chegamos ao fim da gramática (final da entrada não-terminal) com sucesso. Isso significa que temos acompanhado com sucesso a string "abc" para a gramática.
Como o exemplo acima indica, o problema geral de combinar uma entrada com uma gramática pode resultar em grandes quantidades de retrocesso e fazer novas escolhas e isso pode consumir muito tempo. A quantidade de tempo necessário pode também ser uma função de como a gramática está escrito. Note-se que muitas gramáticas podem ser escritas para cobrir o mesmo conjunto de entradas - ou a mesma língua (ou seja, não pode haver várias gramáticas equivalentes para a mesma linguagem de entrada).
Por exemplo, a seguinte gramática vai acelerar a análise de uma mesma língua, em comparação com a gramática anterior:
void Input() :
{}
{
"a" "b" "c" [ "c" ]
}
Enquanto a seguinte gramática retarda ainda mais uma vez que o analisador tem que retroceder todo o caminho até o início:
void Input() :
{}
{
"a" "b" "c" "c"
|
"a" "b" "c"
}
{
Pode-se até ter uma gramática que se parece com o seguinte:
void Input() :
{}
{
"a" ( BC1() | BC2() )
}
void BC1() :
{}
{
"b" "c" "c"
}
void BC2() :
{}
{
"b" "c" [ "c" ]
}
Esta gramática pode igualar "ABCC" de duas maneiras, e, portanto, é considerada "ambígua".
O impacto no desempenho de tal retrocesso é inaceitável para a maioria dos sistemas que incluem um analisador. Daí a maioria dos analisadores não recuar dessa maneira geral (ou não voltar atrás em tudo), em vez de tomar decisões em pontos de escolha com base em informações limitadas e, em seguida, se comprometer com ele.
Analisadores geradas pelo Java CC tomam decisões em pontos de escolha com base em alguma exploração de tokens mais à frente no fluxo de entrada, e uma vez que tomar tal decisão, eles se comprometer com ele, ou seja, nenhum retrocesso é realizado uma vez tomada uma decisão.
O processo de explorar ainda mais fichas no fluxo de entrada é chamada de "olhar em frente" para o fluxo de entrada - daí o uso do termo "visão antecipada".
Uma vez que algumas destas decisões pode ser feita com menos de informação perfeita (JavaCC [tm] irá avisá-lo nestas situações, para que você não precisa se preocupar), você precisa saber algo sobre lookahead para fazer seu trabalho de gramática corretamente.
As duas maneiras em que você faz as decisões de escolha funcionam corretamente são:
· Modifique a gramática para torná-lo mais simples.
· Insira dicas para os pontos de escolha mais complicadas para ajudar o analisador fazer as escolhas certas.
Mais Exemplos:
Vamos supor que desejamos implementar um analisador sintético que reconheça expressões aritméticas com apenas um número inteiro positivo ou com uma adição ou uma subração de dois números inteiros positivos (por exemplo: 2+3, 1-4, 5). De seguida apresenta se uma gramatica com a especificação do símbolo terminal utilizando uma expressão regular:
INTEGER = [0-9]+ // símbolo terminal
doubleexpr(): {}
{ term() ( "+" expr() | "-" expr() )*
}
doubleterm(): {}
{ unary() ( "*" term() | "/" term() )*
}
Exemplo: Gramática
Lembre-se de que o JavaCCnão permite recursão à esquerda, por isso, é necessário modificar a gramática antes de traduzí-la.
options
{ LOOKAHEAD=2;
STATIC=false;
}
PARSER_BEGIN(Arithmetic) publicclassArithmetic { }PARSER_END(Arithmetic)
Referências
AHO, A. V.; SETHI, R.; ULLMAN, J. D. Compiladores: princípios, técnicas e ferramentas. Tradução Daniel de Ariosto Pinto. Rio de Janeiro: LTC, 1995.
GRUNE, D. et al. Projeto moderno de compiladores: implementação e aplicações. Tradução Vandenberg D. de Souza. Rio de Janeiro: Campus, 2001.
LOUDEN, K. Compiladores: princípios e práticas. Tradução Flávio soares Corrêa da Silva. São Paulo: Pioneira Thomson Learning, 2004.
SEBESTA, R. W. Conceitos de linguagens de programação. 4. ed. Tradução José Carlos Barbosa dos Santos. Porto Alegre: Bookman, 2000.
JAVACC. JavaCC features. [S.l.], 2014. Disponível em: <https://web.archive.org/web/20140829033337/https://javacc.java.net/doc/javaccgrm.html>. Acesso em: 20 Junho de 2014.
JavaCC Java Compiler Compiler - The Java Parser Generator. SUN Microsystems. Disponível em: <https://web.archive.org/web/20080924103934/https://javacc.dev.java.net/>. Acesso em: 10 de março de 2006.
Java.net disponível em < https://javacc.de[ligação inativa] v .java.net/doc/docindex.html, > Acesso em: 5 de março de 2006.
JJDOC disponível em <https://web.archive.org/web/20070709232144/https://javacc.dev.java.net/doc/JJDoc.html> Acesso em 21 de Maio de 2006.
JavaTree disponível em <https://web.archive.org/web/20070709230943/https://javacc.dev.java.net/doc/JJTree.html> Acesso em 21 de Maio de 2006.
Viswanathan Kodaganallur. Incorporating language processing into java applications: a javacc tutorial. IEEE Software, 21(4):70–77, 2004.
YAMANE, Emilio Eiji, 2006, Modelagem e Implementação de uma Ferramenta de Autoria para a Construção de Tutores Inteligentes. Tese de Mestrado, UFSC, Florianópolis, SC.