1 Aula sobre JavaCC Parsing Tarciana Dias [email protected] Abril 2013

1

Aula sobre JavaCC

Parsing

Tarciana Dias

[email protected]

Abril 2013

2

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

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 blocke.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 geradofinal 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çõesint 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 ; }}

10





• Referências

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.27-plugin\

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.javacc-1.5.27-plugin\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

18





• Referências

Outro Exemplo

• Gramática– Vide MyNewGrammar.jj

20





• Referências

• 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

22

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)

23

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.

N ::= X(Y)*

Substituindo por uma regra EBNF equivalente

24

Conceitos Básicos• Transformações de Gramática Identifier ::= Letter

| Identifier Letter | Identifier Digit

Identifier ::= Letter | Identifier (Letter | Digit)

Identifier ::= Letter (Letter | Digit)*

Fatorando à

esquerda

Eliminando recursão

à esquerda

25

Conceitos Básicos

• A necessidade da eliminação de recursão à esquerda é melhor entendida depois que se vai usar a abordagem top-down;

26

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

27

Estratégia Bottom-Up• Exemplo: 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

the cat sees a rat .

Noun

Subject

Verb Noun

Object

SentenceAqui ele

não poderia ter escolhido

um Subject?

28

Estratégia Top-Down• Exemplo: 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


Noun

Subject

Verb Noun

Object

Sentence

29

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

parseSubject parseVerb parseObject

parseSentence


parseNoun parseNoun

30

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.

31

Gramáticas não-LL(1)

• Exemplo de uma Gramáticas não LL(1):

Program ::= single-CommandCommand ::= single-Command (; single-Command)*V-name ::= Identifiersingle-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 …

32

Gramáticas não-LL(1)• Desenvolvimento do método parseSingleCommand:

private void parseSingleCommand(){switch(currentToken.kind){

case Token.IDENTIFIER: { parseVname();

accept(Token.BECOMES); parseExpression(); } break;

case Token.IDENTIFIER: { parseIdentifier ();

accept(Token.LPAREN); parseExpression(); accept(Token.RPAREN); } break;

}}

Uma simples fatoração à

esquerda resolve o problema!

…V-name ::= Identifiersingle-Command ::= V-name := Expression | Identifier ( Expression ) | …

…single-Command ::= Identifier (:= Expression | ( Expression ) )

33

Gramáticas não-LL(1)• Exemplo de uma Gramáticas não LL(1):

• 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)

…Block::= begin Declaration (; Declaration)* ; Command endDeclaration ::= integer Identifier (, Identifier)*…

private void parseBlock(){ accept(Token.BEGIN){ parseDeclaration(); while (currentToken.kind == Token.SEMICOLON) acceptIt(); parseDeclaration(); } accept(Token.SEMICOLON); parseCommand(); accept(Token.END);}

…Block::= begin Declaration ; (Declaration;)* Command end…

Como resolver?

34

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

35





• Referências

Criando a estrutura para a linguagem exp1

• Baixar a gramática Expressoes1.jj contida emhttp://www.cin.ufpe.br/~in1007/linguagens/

Expressoes1/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 !


• 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


• File-> New->Other, ir na opção javaCC-> JavaCC Template File



• 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.


• 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.


• Baixar da página da disciplina as classe listadas abaixo


• 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.

44

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/

45

Aula sobre JavaCC

Parsing

Tarciana Dias

[email protected]

Abril 2013

Documents

1 Aula sobre JavaCC Parsing Tarciana Dias [email protected] Abril 2013