Compiladores - Análise Preditiva - dcc.ufrj.brdcc.ufrj.br/~fabiom/comp20132/  · •Uma heurística

  • View
    214

  • Download
    0

Embed Size (px)

Text of Compiladores - Análise Preditiva - dcc.ufrj.brdcc.ufrj.br/~fabiom/comp20132/  · •Uma...

  • Compiladores - Anlise Recursiva

    Fabio Mascarenhas - 2013.2

    http://www.dcc.ufrj.br/~fabiom/comp

    http://www.dcc.ufrj.br/~fabiom/sem
  • Analisador Recursivo

    Maneira mais simples de implementar um analisador sinttico a partir de uma

    gramtica, mas no funciona com muitas gramticas

    A ideia manter a lista de tokens em um vetor, e o token atual um ndice

    nesse vetor

    Um terminal testa o token atual, e avana para o prximo token se o tipo for

    compatvel, ou falha se no for

    Uma sequncia testa cada termo da sequncia, falhando caso qualquer um

    deles falhe

    Uma alternativa guarda o ndice atual e testa a primeira opo, caso falhe

    volta para o ndice guardado e testa a segunda, assim por diante

  • Analisador Recursivo

    Um opcional guarda o ndice atual, e testa o seu termo, caso ele falhe volta

    para o ndice guardado e no faz nada

    Uma repetio repete os seguintes passos at o seu termo falhar: guarda o

    ndice atual e testa o seu termo

    Um no-terminal vira um procedimento separado, e executa o procedimento

    correspondente

    Construir a rvore sinttica um pouco mais complicado, as alternativas,

    opcionais e repeties devem jogar fora ns da parte que falhou!

  • Retrocesso Local

    Podemos definir o processo de construo de um parser recursivo com

    retrocesso local como uma transformao de EBNF para cdigo Java

    Os parmetros para nossa transformao so o termo EBNF que queremos

    transformar e um termo Java que nos d o objeto da rvore sinttica

    Vamos chamar nossa transformao de $parser

    $parser(termo, arvore) d o cdigo para anlise sinttica do termo,

    guardando o resultado em um ou mais ns de arvore caso seja bem sucedido

  • Retrocesso Local

    $parser(termo, arvore) d o cdigo para anlise sinttica do termo,

    guardando o resultado em um ou mais ns de arvore caso seja bem sucedido

    $parser(terminal, arvore) =

    ($arvore).child(match($terminal));

    $parser(t1...tn, arvore) =

    $parser(t1, arvore)

    ...

    $parser(tn, arvore)

    $parser(NAOTERM, arvore) =

    ($arvore).child(NAOTERM());

  • Retrocesso Local

    $parser(termo, arvore) d o cdigo para anlise sinttica do termo,

    guardando o resultado em um ou mais ns de arvore caso seja bem sucedido

    $parser(t1 | t2, arvore) =

    {

    int atual = pos;

    try {

    Tree rascunho = new Tree();

    $parser(t1, rascunho);

    ($arvore).children.addAll(rascunho.children);

    } catch(Falha f) {

    pos = atual;

    $parser(t2, arvore);

    }

    }

  • Retrocesso Local

    $parser(termo, arvore) d o cdigo para anlise sinttica do termo,

    guardando o resultado em um ou mais ns de arvore caso seja bem sucedido

    $parser([ termo ], arvore) =

    {

    int atual = pos;

    try {

    Tree rascunho = new Tree();

    $parser(termo, rascunho);

    ($arvore).children.addAll(rascunho.children);

    } catch(Falha f) {

    pos = atual;

    }

    }

  • Retrocesso Local

    $parser(termo, arvore) d o cdigo para anlise sinttica do termo,

    guardando o resultado em um ou mais ns de arvore caso seja bem sucedido

    $parser({ termo }, arvore) =

    while(true) {

    int atual = pos;

    try {

    Tree rascunho = new Tree();

    $parser(termo, rascunho);

    ($arvore).children.addAll(rascunho.children);

    } catch(Falha f) {

    pos = atual;

    break;

    }

    }

  • Um analisador recursivo para TINY

    Vamos construir um analisador recursivo para TINY de maneira sistemtica,

    gerando uma rvore sinttica

    O vetor de tokens vai ser gerado a partir de um analisador lxico escrito com o

    JFlex

    S -> CMDSCMDS -> CMD { ; CMD }CMD -> if EXP then CMDS [ else CMDS ] end

    | repeat CMDS until EXP| id := EXP| read id| write EXP

    EXP -> SEXP [ < SEXP | = SEXP ]SEXP -> TERMO { + TERMO | - TERMO }TERMO -> FATOR { * FATOR | / FATOR }FATOR -> "(" EXP ")" | num | id

  • Retrocesso local x global

    O retrocesso em caso de falha do nosso analisador local. Isso quer dizer que

    se eu tiver ( A | B ) C e A no falha mas depois C falha, ele no tenta B

    depois C novamente

    Da mesma forma, se eu tenho A | A B a segunda alternativa nunca vai ser bem

    sucedida

    As alternativas precisam ser exclusivas

    Retrocesso local tambm faz a repetio ser gulosa

    Uma implementao com retrocesso global possvel, mas mais complicada

  • Deteco de erros

    Um analisador recursivo com retrocesso tambm tem um comportamento ruim

    na presena de erros sintticos

    Ele no consegue distinguir falhas (um sinal de que ele tem que tentar outra

    possibilidade) de erros (o programa est sintaticamente incorreto)

    Uma heurstica manter em uma varivel global uma marca dgua que indica

    o quo longe fomos na sequncia de tokens

  • Recurso esquerda

    Outra grande limitao dos analisadores recursivos que as suas gramticas

    no podem ter recurso esquerda

    A presena de recurso esquerda faz o analisador entrar em um lao infinito!

    Precisamos transformar recurso esquerda em repetio

    Fcil quando a recurso direta:

    A -> A x1 | ... | A xn | y1 | ... | yn

    A -> ( y1 | ... | yn ) { x1 | ... | xn }

  • Eliminao de recurso sem EBNF

    A -> A x1

    ...

    A -> A xn

    A -> y1

    ...

    A -> yn

    A -> y1 A

    ...

    A -> yn A

    A -> x1 A

    ...

    A -> xn A

    A ->

  • Parsing Expression Grammars

    As parsing expression grammars (PEGs) so uma generalizao do parser

    com retrocesso local

    A sintaxe das gramticas adota algumas caractersticas de expresses

    regulares: * e + para repetio ao invs de {}, ? para opcional ao invs de []

    Usa-se / para alternativas ao invs de |, para enfatizar que esse um operador

    bem diferente do das gramticas livres de contexto

    Acrescentam-se dois operadores de lookahead: &t e !t

    Finalmente, uma PEG pode misturar a tokenizao com a anlise sinttica,

    ento os terminais so caracteres (com sintaxe para strings e classes)