5.5.4 – Métodos para a construção da tabela de análise LR Tabela de análise LR = Tabela de análise LR = Tabela de ações Tabela de transições Gramáticas

Embed Size (px)

Text of 5.5.4 – Métodos para a construção da tabela de análise LR Tabela de análise LR = Tabela de...

  • Slide 1
  • 5.5.4 Mtodos para a construo da tabela de anlise LR Tabela de anlise LR = Tabela de anlise LR = Tabela de aes Tabela de transies Gramticas LR(k) ou simplesmente LR permitem a construo dessas tabelas Gramticas LR(k) ou simplesmente LR permitem a construo dessas tabelas Yacc usa essas tabelas Yacc usa essas tabelas Gramticas ambguas no so LR, mas em Yacc h dispositivos para resolver ambiguidades Gramticas ambguas no so LR, mas em Yacc h dispositivos para resolver ambiguidades
  • Slide 2
  • Numa gramtica LR, os analisadores por deslocamento e reduo tm a capacidade de reconhecer asas no topo da pilha Numa gramtica LR, os analisadores por deslocamento e reduo tm a capacidade de reconhecer asas no topo da pilha Na realidade, eles utilizam um autmato determinstico reconhecedor de prefixos viveis na pilha Na realidade, eles utilizam um autmato determinstico reconhecedor de prefixos viveis na pilha Nesses analisadores, no necessrio percorrer a pilha para saber quando uma asa aparece no topo: Nesses analisadores, no necessrio percorrer a pilha para saber quando uma asa aparece no topo: O estado no topo da pilha contm toda a informao necessria O estado no topo da pilha contm toda a informao necessria
  • Slide 3
  • So conhecidos trs mtodos para a construo de uma tabela de anlise LR: So conhecidos trs mtodos para a construo de uma tabela de anlise LR: Mtodo SLR (simple LR): aplica-se a um menor nmero de gramticas; o de mais fcil implementao Mtodo SLR (simple LR): aplica-se a um menor nmero de gramticas; o de mais fcil implementao Mtodo CLR (canonical LR): mais poderoso e de mais difcil implementao Mtodo CLR (canonical LR): mais poderoso e de mais difcil implementao Mtodo LALR (look-ahead LR): intermedirio em potncia e dificuldade de implementao Mtodo LALR (look-ahead LR): intermedirio em potncia e dificuldade de implementao
  • Slide 4
  • Mtodos SLR (simple LR), CLR (canonical LR) e LALR (look-ahead LR): O segundo e o terceiro mtodo usam os mesmos princpios do primeiro e acrescentam a esse informaes sobre os tomos seguintes do que est em anlise O segundo e o terceiro mtodo usam os mesmos princpios do primeiro e acrescentam a esse informaes sobre os tomos seguintes do que est em anlise O terceiro mtodo uma simplificao do segundo, diminuindo muito a memria gasta no processo O terceiro mtodo uma simplificao do segundo, diminuindo muito a memria gasta no processo o mais usado na prtica o mais usado na prtica Yacc usa o mtodo LALR Yacc usa o mtodo LALR
  • Slide 5
  • Mtodos SLR (simple LR), CLR (canonical LR) e LALR (look-ahead LR): Nesta disciplina ser apresentado somente o mtodo SLR Nesta disciplina ser apresentado somente o mtodo SLR Os outros dois usam os princpios bsicos desse primeiro Os outros dois usam os princpios bsicos desse primeiro Fundamental a concepo do autmato finito determinstico, reconhecedor de prefixos viveis, para o controle da pilha do analisador Fundamental a concepo do autmato finito determinstico, reconhecedor de prefixos viveis, para o controle da pilha do analisador
  • Slide 6
  • 5.5.5 Autmato finito no-determinstico LR Origem do autmato finito determinstico (AFD): Origem do autmato finito determinstico (AFD): Autmato finito no-determinstico (AFND) reconhecedor de prefixos viveis Autmato finito no-determinstico (AFND) reconhecedor de prefixos viveis O AFND transformado num AFD equivalente O AFND transformado num AFD equivalente Seja ento a concepo de um AFND reconhecedor de prefixos viveis de uma gramtica Seja ento a concepo de um AFND reconhecedor de prefixos viveis de uma gramtica
  • Slide 7
  • Os estados de um AFND so chamados itens de produes Os estados de um AFND so chamados itens de produes Item de produo de uma gramtica a mesma produo contendo um ponto (.) em alguma posio do lado direito Item de produo de uma gramtica a mesma produo contendo um ponto (.) em alguma posio do lado direito A produo A XYZ tem 4 itens, a saber: A produo A XYZ tem 4 itens, a saber: A. XYZ, A X. YZ, A XY. Z e A XYZ. A produo vazia A tem 1 item : A. A produo vazia A tem 1 item : A.
  • Slide 8
  • Interpretao de um item: Seja o item A . Seja o item A . um estado do AFND no qual j foi vista na entrada uma sub-sentena derivada de e se espera encontrar a seguir outra derivada de um estado do AFND no qual j foi vista na entrada uma sub-sentena derivada de e se espera encontrar a seguir outra derivada de O AFND de uma gramtica trabalha com a mesma aumentada de um novo smbolo inicial S e uma nova produo, S S
  • Slide 9
  • Exemplo: gramtica de expresses aumentada e seus 20 itens Um item pode ser representado por um par de inteiros: Um item pode ser representado por um par de inteiros: O primeiro sendo o nmero da produo e o segundo a posio do ponto O primeiro sendo o nmero da produo e o segundo a posio do ponto
  • Slide 10
  • Num AFND, h dois tipos de transies: De qualquer estado do tipo A.X para outro estado do tipo A X., cuja condio para transio o smbolo X (X {N }) De qualquer estado do tipo A.X para outro estado do tipo A X., cuja condio para transio o smbolo X (X {N }) De qualquer estado do tipo A.B para outro estado do tipo B., cuja condio para transio o smbolo (vazio) De qualquer estado do tipo A.B para outro estado do tipo B., cuja condio para transio o smbolo (vazio) A.X A X. A.B B. X O 2 tipo caracteriza o no-determinismo