Aula sobre JavaCC
Parsing
Tarciana Dias
[email protected]
Abril 2013
1
Roteiro
• Sobre o JavaCC – forma de especificação das gramáticas
• Instalando o plugin do JavaCC no eclipse
• Análise da gramática default gerada pelo JavaCC
• Analisando a linguagem de expressões 1
– Revisando conceitos básicos de gramáticas LL
– Aplicando os conceiros na gramática do exp1
• Referências
2
Exemplo 1
• Gramática
Start := NUMBER ( “+” NUMBER )
Classe do parser
options {
STATIC = false ;
}
PARSER BEGIN(Adder)
public class Adder {
static void main( String[] args )
throws ParseException, TokenMgrError {
Adder parser = null;
try {
parser = new Adder(new FileInputStream("input.txt"));
} catch (FileNotFoundException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
System.out.println(parser.start());}
}
PARSER END(Adder)
Analisador léxico
SKIP : { ” ” }
SKIP : { ”\n” | ”\r” | ”\r\n” }
TOKEN : { < PLUS : ”+” > }
TOKEN : { < NUMBER : ([”0”-”9”])+ > }
Gramática “EBNF”
void Start() :
{} {
<NUMBER>
(
<PLUS>
<NUMBER>
)*
<EOF>
}
Possiveis saidas
• Entrada válida: 1 + 5
• Token inválido: 1 – 3 ( Exceção)
• Erro sintático: 1 ++ 5 (Exceção)
Código gerado
final public void start() throws ParseException {
jj_consume_token(NUMBER);
label_1:
while (true) {
switch ((jj_ntk==-1)? jj_ntk() : jj_ntk) {
case PLUS:
;break;
default:
jj_la1[0] = jj_gen;
break label_1;
}
jj_consume_token(PLUS);
jj_consume_token(NUMBER);
}
jj_consume_token(0); }
Adicionando ações
int Start() throws NumberFormatException : {
}{
Token t ;
int i ;
int value ;
t = <NUMBER>
{ i = Integer.parseInt( t.image ) ; }
{ value = i ; }
(<PLUS>
t = <NUMBER>
{ i = Integer.parseInt( t.image ) ; }
{ value += i ; }
)*
<EOF>
{ return value ; }}
Roteiro
• Sobre o JavaCC – forma de especificação das gramáticas
• Instalando o plugin do JavaCC no eclipse
• Análise da gramática default gerada pelo JavaCC
• Analisando a linguagem de expressões 1
– Revisando conceitos básicos de gramáticas LL
– Aplicando os conceiros na gramática do exp1
• Referências
10
Plugin Eclipse
• Baixar o plugin:
– Pagina do plugin:
http://eclipse-javacc.sourceforge.net/
– Para atualizar o eclipse com o plugin:
• Pegar a pasta ...\sf.eclipse.javacc-1.5.27plugin\plugins\sf.eclipse.javacc_1.5.27 e copiá-la
para o caminho do eclipse ...\eclipse\plugins
• Fazer o mesmo para a pasta ...\sf.eclipse.javacc1.5.27plugin\features\sf.eclipse.javacc.feature_1.5.27 só
que para o caminho ...\eclipse\features
Quick start plugin eclipse
• Criar um projeto Java no eclipse
• Criar uma pasta foo submissa à pasta do projeto
• Em seguida, criar um novo projeto só que selecionando
a opção Other, escolhendo a pasta JavaCC e a opção
JavaCCTemplateFile, conforme mostrado a seguir:
New->Other, ir na opção javaCC-> JavaCC Template File
Quick start plugin eclipse [2]
Quick start plugin eclipse [3]
• Ao clicar em Next, a tela seguinte
aparece.
• Observe que se deve indicar a gramática
utilizada como referência. No caso default,
ele utiliza MyNewGrammar.jj
• Mas podemos colocar uma das
gramáticas disponíveis na página da
disciplina /~in101 e vistas até então
(iremos fazer depois):
– Expressoes1.jj ou Expressoes2.jj ou
Funcional1.jj
Quick start plugin eclipse [4]
Quick start plugin eclipse [5]
• Após escolhida a gramática, clica-se em
Finish:
Arquivos gerados
•
•
•
•
•
•
•
•
EG1
EG1Constants
EG1TokenManager
MyNewGrammar.jj
ParserException
SimpleCharStream
Token
TokenMgrError
Roteiro
• Sobre o JavaCC – forma de especificação das gramáticas
• Instalando o plugin do JavaCC no eclipse
• Análise da gramática default gerada pelo JavaCC
• Analisando a linguagem de expressões 1
– Revisando conceitos básicos de gramáticas LL
– Aplicando os conceiros na gramática do exp1
• Referências
18
Outro Exemplo
• Gramática
– Vide MyNewGrammar.jj
Roteiro
• Sobre o JavaCC – forma de especificação das gramáticas
• Instalando o plugin do JavaCC no eclipse
• Análise da gramática default gerada pelo JavaCC
• Analisando a linguagem de expressões 1
– Revisando conceitos básicos de gramáticas LL
– Aplicando os conceiros na gramática do exp1
• Referências
20
• Vamos agora analisar a gramática da
linguagem de expressões 1
• Antes disso, vamos revisar as técnicas de
fatorar uma gramática à esquerda e
eliminar recursões à esquerda
21
Conceitos Básicos
• Transformações de Gramática
– Fatoração à esquerda
– Ex;: XY | XZ equivale à X (Y | Z)
single-Command ::= V-name := Expression
| if Expression then single-Command
| if Expression then single-Command
else single-Command
single-Command ::= V-name := Expression
| if Expression then single-Command
( ε | else single-Command)
22
Conceitos Básicos
• Transformações de Gramática
– Eliminação de recursão à esquerda
N ::= X | NY, onde N é um símbolo não-terminal e X e Y
são REs estendidas. Esta produção é recursiva à esquerda.
Substituindo por uma regra EBNF
equivalente
N ::= X(Y)*
23
Conceitos Básicos
• Transformações de Gramática
Identifier ::= Letter
| Identifier Letter
| Identifier Digit
Fatorando
à esquerda
Identifier ::= Letter
| Identifier (Letter | Digit)
Eliminando
recursão à
esquerda
Identifier ::= Letter (Letter | Digit)*
24
Conceitos Básicos
• A necessidade da eliminação de recursão
à esquerda é melhor entendida depois
que se vai usar a abordagem top-down;
25
Estratégias de Parsing
•
Objetivo
– Reconhecimento de uma string de entrada (seqüência de tokens) e decisão se
esta é ou não uma sentença de G
– Determinação de sua estrutura de frases (pode ser representada por uma árvore
sintática)
– Gramática não ambígua: cada sentença tem exatamente uma syntax tree
•
Top-Down
– Examina os símbolos terminais da esquerda para a direita
– Forma a ST (syntax tree) de cima para baixo
– Parsing ok: string de entrada totalmente conectada à ST
• L(eft-to-right) L(eft-most-derivation) => LL
•
Bottom-Up
– Examina os símbolos terminais da esquerda para a direita
– Forma a ST (syntax tree) de baixo (nós terminais) para cima(nó raiz)
– Parsing ok: string de entrada reduzida a uma S-tree
• S(imple) L(eft-to-right) R(ight-most-derivation) => SLR
• L(eft-to-right) R(ight-most-derivation) => LR
• L(ook) A(head) L(eft-to-right) R(ight-most-derivation) => LALR
26
Estratégia Bottom-Up
•
Sentence ::= Subject Verb Object
Subject ::= I | a Noun | the Noun
Object ::= me | a Noun | the Noun
Noun ::= cat | mat | rat
Verb ::= like | is | see | sees
Exemplo:
Sentence
Object
Subject
Noun
the
Noun
Verb
cat sees
Aqui ele não
poderia ter
escolhido um
Subject?
a
rat .
27
Estratégia Top-Down
•
Sentence ::= Subject Verb Object
Subject ::= I | a Noun | the Noun
Object ::= me | a Noun | the Noun
Noun ::= cat | mat | rat
Verb ::= like | is | see | sees
Exemplo:
Sentence
Object
Subject
Noun
the
Noun
Verb
cat sees
a
rat .
28
Estratégias de Parsing
•
Qual estratégia de parsing devemos usar?
– Isso vai depender do tipo de gramática !
– Sempre é necessário escolher qual regra de produção aplicar
•
Isto é feito de acordo com o algoritmo de Parsing
– Recursive Descent é um algoritmo de parsing top-down
– Consiste de um grupo de métodos parseN, um para cada símbolo não-terminal
N de G. Estes métodos cooperam para fazer o parse das sentenças completas
parseSentence
parseSubject
parseVerb
parseObject
parseNoun
parseNoun
the
cat
sees
a
rat .
29
Gramáticas LL(1)
•
Deve-se expressar a gramática em EBNF, com uma regra de produção
simples para cada símbolo não-terminal, e realizar as transformações de
gramática necessárias, por exemplo, sempre eliminar recursão à esquerda
e fatorizar à esquerda sempre que possível
•
Gramáticas LL(1):
–
–
Se a gramática contém X | Y, starters[[ X ]] e starters[[ Y ]] devem ser disjuntos
Se a gramática contém X* , starters[[ X ]] deve ser disjunto do conjunto de tokens que
podem seguir X*
•
Na prática quase toda gramática de uma linguagem de programação pode
ser transformada em LL(1), sem mudar a linguagem que a gramática gera
•
Recursive-descent parsing é somente adequado para gramáticas LL(1)
–
Em geral, o projetista da linguagem projeta a sua sintaxe para ser adequada à um parsing
recursive-descent.
30
Gramáticas não-LL(1)
•
Exemplo de uma Gramáticas não LL(1):
Program ::= single-Command
Command ::= single-Command (; single-Command)*
V-name ::= Identifier
single-Command ::= V-name := Expression
| Identifier ( Expression )
| if Expression then single-Command
| if Expression then single-Command
else single-Command
…
Expression ::= primary-Expression (Operator primary-Expression)*
primary-Expression ::= Integer-Literal
| Identifier
…
31
Gramáticas não-LL(1)
•
Desenvolvimento do método parseSingleCommand:
private void parseSingleCommand(){
Uma simples
switch(currentToken.kind){
fatoração à
esquerda resolve
case Token.IDENTIFIER: {
parseVname();
o problema!
accept(Token.BECOMES);
parseExpression();
}
}
break;
case Token.IDENTIFIER: {
parseIdentifier ();
accept(Token.LPAREN);
parseExpression();
accept(Token.RPAREN);
}
break;
}
…
V-name ::= Identifier
single-Command ::= V-name := Expression
| Identifier ( Expression )
| …
…
single-Command ::= Identifier (:= Expression | ( Expression ) )
32
Gramáticas não-LL(1)
•
•
Exemplo de uma Gramáticas não LL(1):
…
Block::= begin Declaration (; Declaration)* ; Command end
Declaration ::= integer Identifier (, Identifier)*
…
Aqui, starters[[ ;Declaration ]] = {;} e o conjunto de terminais que seguem (;
Declaration)* neste contexto também é {;}
–
Como não são disjuntos, então a gramática não é LL(1)
private void parseBlock(){
accept(Token.BEGIN){
parseDeclaration();
while (currentToken.kind ==
Token.SEMICOLON)
acceptIt();
parseDeclaration();
}
accept(Token.SEMICOLON);
parseCommand();
accept(Token.END);
}
Como
resolver?
…
Block::= begin Declaration ; (Declaration;)*
Command end
…
33
Recursive Descent Parser
• Recursive Descent Parser
– Algoritmo de parsing para gramáticas LL
– Visão geral
• Para cada produção N, crie um método parseN
• Crie uma classe parser com um atributo currentToken
– E os métodos parseN
– E os métodos auxiliares: accept e acceptIt
– E um método público parse que chama parseS
• O código de cada método parseN depende da produção N
• A árvore é dada implicitamente pela chamada dos métodos
– Pode ser criada explicitamente
34
Roteiro
• Sobre o JavaCC – forma de especificação das gramáticas
• Instalando o plugin do JavaCC no eclipse
• Análise da gramática default gerada pelo JavaCC
• Analisando a linguagem de expressões 1
– Revisando conceitos básicos de gramáticas LL
– Aplicando os conceiros na gramática do exp1
• Referências
35
Criando a estrutura para a
linguagem exp1
• Baixar a gramática Expressoes1.jj contida em
http://www.cin.ufpe.br/~in1007/linguagens/Expresso
es1/expressao1.html
• Observar no início do arquivo que:
PARSER_BEGIN(Exp1Parser)
package plp.expressions1.parser;
import plp.expressions1.*;
import plp.expressions1.expression.*;
import plp.expressions1.util.*;
• Logo devemos criar o projeto java seguindo a
estrutura plp.expressions1 etc etc !
Criando a estrutura para a linguagem
exp1
• Criar um projeto java comum
• Em seguida criar um pacote chamado plp
e em seguida um chamado expressions1,
submisso à plp
• Em seguida criar uma pasta/pacote parser
dentro de expressions1
• Selecione a pasta parser e repita o
processo anterior de criar um projeto
JavaCC
Criando a estrutura para a linguagem
exp1
• File-> New->Other, ir na opção javaCC->
JavaCC Template File
Criando a estrutura para a linguagem
exp1
Criando a estrutura para a linguagem
exp1
• Vá até a pasta onde os arquivos foram
gerados, pasta parser, apague todos e
coloque na pasta apenas o arquivo da
gramática Expressoes1.jj
• Você vai notar que o eclipse gera todos os
arquivos novamente, de forma automática,
só que agora tendo como referência a
nova gramática.
Criando a estrutura para a linguagem
exp1
• Dois dos arquivos gerados, Exp1Parser e
Exp1ParserTokenManager apresentarão
erros de compilação.
• Isto porque estão faltando ainda algumas
classes básicas como por exemplo Valor,
ValorInteiro, etc, mencionadas no arquivo .jj
por isso referenciadas pelo Exp1Parser.java
gerado pelo JavaCC.
• Além desta a classe Programa também é
referenciada.
Criando a estrutura para a linguagem
exp1
• Baixar da página da disciplina as classe
listadas abaixo
Criando a estrutura para a linguagem
exp1
• Criar o pacote expression no mesmo nível do
pacote parser e colocar as classes listadas
anteriormente no pacote expression
• Ainda, classe Programa também é referenciada
nas classes geradas. Baixar a mesma na página
da disciplina e colocá-la no pacote expressions1
• Ainda, as classes Tipo e TipoPrimitivo também
são referenciadas. Baixá-las e colocá-las dentro
do pacote util, a ser criado no mesmo nível do
pacote parser e do pacote expression.
Referências
• WATT, D.; BROWN, D.
Programming Language Processors in Java.
– Capítulo 4
• Foco maior na abordagem LL
• Site do plugin JavaCC para eclipse:
– http://eclipse-javacc.sourceforge.net/
• Tutorial JavaCC:
– http://www.engr.mun.ca/~theo/JavaCC-Tutorial
• Site do JavaCC:
– http://javacc.java.net/
44
Aula sobre JavaCC
Parsing
Tarciana Dias
[email protected]
Abril 2013
45