Construção de Compiladores com JFlex e JCup

Prévia do material em texto

*
*
*
Universidade Federal da Paraíba
Departamento de Informática
Construção de Compiladores
JFLEX e CUP
*
*
*
Universidade Federal da Paraíba
Departamento de Informática
Introdução
Analisadores léxicos e sintáticos são construídos a partir de especificações formais
Gramáticas Regulares / Autômatos finitos
Gramáticas Livre de contexto
A formalidade das descrições permite que tais analisadores sejam automaticamente construídos
Programas que geram programas
*
*
*
Universidade Federal da Paraíba
Departamento de Informática
Introdução
Analisadores Léxicos em C
Lex
Flex
Analisadores Sintáticos em C
Bison
YACC
Léxico e Sintático em C
ANTLR
Analisadores Léxicos em Java
JLex
JFlex
Analisadores Sintáticos em Java
JCup
BYACC/B
Léxico e Sintático em Java
JavaCC
SableCC
ANTLR
*
*
*
Universidade Federal da Paraíba
Departamento de Informática
JFLex e JCup
Esquema da operação
JFLex
JCup
.jflex
Descrição em gramática regular
.java
Analisador 
Léxico
.class
Arquivo fonte
Arquivo de tokens
.cup
Descrição em gramática livre de contexto
.java
javac
Analisador 
Sintático
Arvore sintática
*
*
*
Universidade Federal da Paraíba
Departamento de Informática
Gerador de Analisadores Léxicos
http://jflex.de/index.html
JFLEX
*
*
*
Universidade Federal da Paraíba
Departamento de Informática
JFlex
Arquivo de especificação (.jflex)
Dividido em três seções:
Código do usuário
Diretivas
Regras de Expressões Regulares
Cada seção é separada da seção seguinte por uma linha contendo apenas ‘%%’
*
*
*
Universidade Federal da Paraíba
Departamento de Informática
JFlex
Código do usuário
O código escrito nessa seção é copiado diretamente no topo do arquivo do scanner
Útil para declarar “imports” e nome de pacotes
*
*
*
Universidade Federal da Paraíba
Departamento de Informática
JFlex
Diretivas
Permite a definição de diretivas, macros e nome de estados
Principais diretivas:
%init{...%init}
Tudo que você escrever entre as chaves vai ser copiado diretamente para o método construtor da classe do scanner
%eof{...%eof}
Permite declarar código que vai ser executado quando o scanner encontrar o fim do arquivo de entrada
%char
Ativa o contador de caracteres através da variável inteira yychar
*
*
*
Universidade Federal da Paraíba
Departamento de Informática
JFlex
Principais diretivas (continuação)
%line
Ativa o contador de linhas através da variável inteira yyline
%cup
Ativa a compatibilidade com o JCup. Isso significa que a classe gerada do scanner vai implementar a interface java_cup.runtime.Scanner
%class <nome>
Muda o nome da classe do scanner (default = Yylex).
%debug
Gera o public static void main(...)
*
*
*
Universidade Federal da Paraíba
Departamento de Informática
JFlex
Código incluído entre %...% é copiado literalmente na classe gerada
Declaração de variáveis
Declaração de funções
Identificadores para variáveis e funções não devem ser iniciados com yy
*
*
*
Universidade Federal da Paraíba
Departamento de Informática
JFlex
Diretivas (Macros)
São abreviações para expressões regulares
Cada macro deve estar contida numa única linha
Formato:
<nome> = <definição>
O nome da macro deve começar com uma letra ou ‘_’.
A definição da macro é uma expressão regular.
*
*
*
Universidade Federal da Paraíba
Departamento de Informática
JFlex
Diretivas (Macros)
Macros podem conter outras macros.
Exemplos:
DIGITO = [0-9]
ALFA = [A-Za-z]
ESPACO_EM_BRANCO = [\n\r\x20\t]
NUM_NATURAL = {DIGITO}+
*
*
*
Universidade Federal da Paraíba
Departamento de Informática
JFlex
Diretivas (Estados)
Permite implementar uma máquina de estados no scanner.
Todo scanner tem pelo menos um estado (declarado internamente) chamado YYINITIAL.
Exemplo:
%state COMMENT
*
*
*
Universidade Federal da Paraíba
Departamento de Informática
JFlex
Regras de expressões regulares
Formato das regras:
[<estados>] <expressão> { <ação> }
[<estados>] – opcional. Formato:
<estado0, estado1, ..., estadoN>
Se uma regra for precedida por uma lista de estados, o scanner só tentará aplicar a regra se ele estiver em um dos estados listados
Se uma lista de estados não for especificada para uma regra, o scanner sempre tentará aplicar a regra independentemente do seu estado atual
*
*
*
Universidade Federal da Paraíba
Departamento de Informática
JFlex
Regras de expressões regulares
<expressão> – obrigatório.
Baseadas em expressões regulares
Símbolos especiais:
| - representa uma opção. Exemplo: e|f significa que a expressão pode casar com e ou f.
. (ponto) - casa com qualquer caráter, exceto o ‘\n’.
* - casa com zero ou mais repetições da expressão regular precedente
	Exemplo: [a-z]* casa com {ε, a, aa, ab, ...}
+ - casa com uma ou mais repetições da expressão regular precedente.
	Exemplo: [0-9]+ casa com qualquer número natural.
*
*
*
Universidade Federal da Paraíba
Departamento de Informática
JFlex
Regras de expressões regulares
<expressão> – obrigatório.
Símbolos especiais (cont.):
? – casa com zero ou uma ocorrência da expressão regular precedente. Exemplo: [+ -]?[0-9]+ casa com números naturais precedidos ou não por um sinal de ‘-’ ou ‘+’  {0, 1, -1, +1, -123, +456, ...}
(...) – os parênteses são usados para agrupar expressões regulares.
	Exemplo: (ab)*  {ε, ab, abab, ababac, ...} enquanto que ab*  {a, ab, abb, abbb, ...}
*
*
*
Universidade Federal da Paraíba
Departamento de Informática
JFlex
Regras de expressões regulares
<expressão> – obrigatório.
Símbolos especiais (cont.):
[...] – usado para denotar uma classe de caracteres
Exemplo: [a-z] casa com qualquer letra de ‘a’ até ‘z’
Se o símbolo seguinte ao ‘[‘ for o circunflexo (^), o conteúdo do [...] é negado.
Exemplo: [^0-9] casa com tudo exceto dígitos.
*
*
*
Universidade Federal da Paraíba
Departamento de Informática
JFlex
Regras de expressões regulares
<expressão> – obrigatório.
Expressões podem conter macros desde que essas sejam escritas entre chaves
Exemplos:
{DIGITO}+ representa uma expressão que casa com os números naturais
{ALFA}({ALFA}|{DIGITO}|_)* é a expressão que casa com nomes de variáveis na maioria das linguagens de programação
*
*
*
Universidade Federal da Paraíba
Departamento de Informática
JFlex
Regras de expressões regulares
<ação> - obrigatório.
Uma ação é o trecho de código que deve ser executado quando uma regra for aplicada pelo scanner
É possível trocar o estado do scanner dentro de uma ação através de chamada ao método interno yybegin(nome_do_estado)
Você pode fazer uso das variáveis yytext (String), yychar (int) e yyline (int) dentro do código de suas ações.
*
*
*
Universidade Federal da Paraíba
Departamento de Informática
JFlex
Regras de expressões regulares (observações)
Se mais de uma regra casar com a string de entrada, o scanner escolhe a regra que casa com a maior substring da string. Exemplo:
String: abcd
Regra 1: “ab” { acao1(); }
Regra 2: [a-z]+ { acao2(); }
O scanner vai escolher a regra 2.
Todas as seqüências de caracteres passadas como entrada para o scanner devem casar com alguma das regras. Caso isso não ocorra, o scanner vai gerar um erro
*
*
*
Universidade Federal da Paraíba
Departamento de Informática
Gerador de Analisadores Sintáticos
http://www2.cs.tum.edu/projects/cup/
JCup
*
*
*
Universidade Federal da Paraíba
Departamento de Informática
JCup
Dividido em quatro seções:
Seção 1: declaração de “packages” e “imports” que serão inseridos no topo do arquivo gerado pelo JCup e diretivas do JCup
Seção 2: declaração de terminais e não-terminais
Seção 3: precedência e associatividade de terminais
Seção 4: gramática
*
*
*
Universidade Federal da Paraíba
Departamento de Informática
JCup
Seção1 -Especificação de “packages” e “imports”. Exemplo:
package compilador.parser;
import compilador.scanner;
Diretivas
parser code {: ... :};
Permite que você declare variáveis e métodos na classe do parser. Similar à diretiva %{...%} do JFlex
init with {: ... :};
O código entre chaves vai ser executado antes que o parser peça o primeiro token ao scanner
scan with {: ... :};
Serve para que você escreva o código que o parser vai executar sempre que ele quiser pedir um token ao scanner. Se essa diretiva não for utilizada, o parser chama scanner.next_token() para receber tokens.
*
*
*
Universidade Federal da Paraíba
Departamento de Informática
JCup
Seção 2 - Lista de símbolos
terminal [classe] nome0, nome1, ...;
non terminal [classe] nome0, nome1, ...;
Em tempo de execução, os símbolos são representados por objetos da classe java_cup.runtime.Symbol. Essa classe possui uma variável chamada “value” que contém o valor do símbolo. Exemplo:
terminal Integer NUMERO;
Quando o parser recebe do scanner um NUMERO, ele cria um objeto da classe Symbol. A variável “value” será um objeto da classe Integer. Assim, o valor do número pode ser obtido através de simbolo.value.intValue();
Se não for fornecida uma classe na declaração do (non) terminal, a variável “value” ficará com valor null.
Os nomes dos (non) terminais não podem ser palavras reservadas do JCup: "code", "action", "parser", "terminal", "non", "nonterminal", "init", "scan", "with", "start", "precedence", "left", "right", "nonassoc", "import", e "package"
*
*
*
Universidade Federal da Paraíba
Departamento de Informática
JCup
Seção 3 - Precedência e Associatividade
precedence left terminal[, terminal...];
precedence right terminal[, terminal...];
precedence nonassoc terminal[, terminal...];
A precedência cresce de cima para baixo, por exemplo:
precedence left ADD, SUBTRACT;
precedence left TIMES, DIVIDE;
Significa que a multiplicação e a divisão têm maior precedência.
*
*
*
Universidade Federal da Paraíba
Departamento de Informática
JCup
Seção 4 - Gramática
Especifica as produções da gramática da linguagem.
start with non-terminal; (diretiva opcional)
Indica qual é o não-terminal inicial da gramática. Se essa diretiva for omitida, o parser assume o primeiro não-terminal declarado nas produções da gramática.
As produções têm o formato:
	não-terminal ::= <símbolos e ações>
Os símbolos à direita de “::=“ podem ser terminais ou não-terminais.
As ações correspondem ao código que é executado quando a regra de produção é aplicada
*
*
*
Universidade Federal da Paraíba
Departamento de Informática
JCup
Seção 4 – Gramática
Exemplo:
	expr ::= NUMBER:n
		 {:
		 RESULT=n;
		 :}
		 | expr:r PLUS expr:s
 {:
		 RESULT=new Integer(r.intValue() + s.intValue());
		 :}
Observe que pode-se especificar várias produções para um mesmo não terminal através do uso da barra “|”. Pode-se nomear símbolos para poder referenciá-los no código da ação. O resultado da produção deve ser armazenado na variável implícita “RESULT”. O tipo de “RESULT” é o mesmo que foi declarado na seção 2.