Gramática de Precedência de Operadores

Gramática de Operadores (G.Op) são gramáticas tais que, para toda regra de P, A ® b , então b¹e e b não possui 2 não-terminais consecutivos.

 

Ex1: A gramática

E ® EAE | (E) | -E | id

A ® + | - | * | / | ­

pode ser transformada numa G.Op:

E ® E+E | E-E | E*E | E/E | E­ E |
(E) | -E | id

Þ Parsers simples, eficientes

classe pequena de gramáticas

 

Relações de Precedência (entre 2 terminais)

 

a < b ® a dá precedência a b

a = b ® a e b têm mesma precedência

a > b ® a tem precedência sobre b

Cuidado: pode-se ter a > b e a > b ou a ? b

 

Como determinar as Relações de Precedência:

  1. Baseado na noção usual de precedência e associatividade de operadores

    Ex: + < * , * > + (Gramáticas Ambíguas)

  2. Constrói-se uma gramática não-ambígua e mecanicamente, obtem-se as relações de precedência.

 

Objetivo das Relações de Precedência:

Delimitar um handle:

 

Uma forma sentencial mais à direita numa G.Op tem a forma:

b0a1b 1........anb n ; ai Î VT; bi Î VN È {e }

 

Hipótese: ai R ai+1; R, único, Î {>, <, =}

$ < b e b > $; b Î VT e $ denota fim da cadeia-input

 

Tomando parte da Gramática do Ex1:

 

sentença: id + id * id

com as relações: $ <id> + <id> * <id> $

 

Processo para detectar o handle:

  1. Percorra cadeia a partir da ewquerda até encontrar o 1o >
  2. Volte, ignorando qualquer =, até encontrar um <
  3. O handle consiste de todos símbolos à esquerda do 1o > e à direita do <, incluindo qualquer não-terminal entre os terminais, ou nos seus limites.

Portanto: $ E + <id> * <id> $

Em 2 passos: $ E + E * E $

Considerando que: $ < + < * > $

a extremidade esquerda do próximo handle está entre + e *, e a direita entre * e $. Como os não-terminais "limites" fazem parte do handle, temos que, em E+E*E, o handle é E*E ou seja, $ < E + < E * E > $

 

Algoritmo Parsing Precedência Operadores

  1. faça p apontar o 1o símbolo de w $
  2. repeat forever
  3. if topo pilha = $ e p aponta $
  4. then return sucesso

    else begin

  5. topo = a e p aponta b;
  6. if a < b or a = b then

    begin

  7. empilha b; /* shif */
  8. avança p

    end

    else

  9. if a > b then
  10. repeat /* reduce */
  11. desempilha
  12. until topo < terminal desempilhado imediatamente antes
  13. else ERRO

end

 

OBS: VN "anônimos"

 

Métodos para Determinar Relações Precedência

 

a. Através de Heurísticas - para Gramáticas Expr. Ambíguas

 

  1. Se operador (terminal) q 1 tem maior precedência que operador q 2, faça q 1>q 2 e q 2<q 1, *>+ , +<*

     

  2. Se q 1 e q 2 têm igual precedência, faça:

     
  3. Faça q < id, id > q , q < (, (< q , q >), ) > q , q > $ e $ < q , para todo operador q .

E também:

(=) $<( $<id

(<( id>$ )>$

(<id id>) )>)

 

Tabela para Gramáticas do Ex1:

 

Operadores Unários

Por exemplo negação lógica ~ : Para todo operador q :

 

Exemplo:

~ < and

and > and

Portanto E and ~ E and E Þ ( E and (~ E)) and E

 

-: unário (prefix) e binários (infix)

Þ A.L. deve "lembrar" token anterior para distinguir entre um ou outro.

 

b. Através de Funções de Precedência

 

Ao invés de armazenar e consultar a matriz de Precedência, codificá-la em 2 funções - f e g - que mapeiam terminais em números inteiros.

 

Para 2 terminais a e b:

  1. f(a) < g(b) se a < b
  2. f(a) = g(b) se a = b
  3. f(a) > g(b) se a > b

 

2 passos:

  1. construir Matriz Precedência MP
  2. determinar f e g a partir de MP

 

(i)

Portanto se A ® a a g b b ;

A Î VN

a, b Î VT

a , b Î (VN È VT)* e g Î (VN È {e })

 

A ® a B b b e B ® d a g

A, B Î VN

a, b Î VT

g Î VN È {e }

a , b , d Î (VN È VT)*

 

A ® a a B b e B ® g b d

 

A, B Î VN

a, b Î VT

a , b , d Î (VN È VT)*

g Î VN È {e }

 

(ii) f e g para Gramática do Ex1:

* < id Þ f(*) = 4 < g(id) = 5

 

OBS: f(id) > g(id) embora id ? id

Rotinas de Erro devem detectar!

 

Algoritmo: Funções de Precedência

  1. Crie símbolos fa e ga para cada a Î VT È {$}
  2. Agrupe-os em tantos grupos tal que, se a = b então fa e ga estão no mesmo grupo.

    ( se a = b e c = b, fa e fc estarão num mesmo grupo. Se c = d então fa e gd estão juntos - embora a e d não se relacionem)

  3. Crie um dígrafo onde os nós são os grupos de 2. Para todo a e b, se a < b, faça uma aresta do grupo de gb para o grupo de fa. Se a > b, faça uma aresta do grupo de fa para o de gb.
  4. Se o dígrafo tiver ciclos – não existe função de precedência. Caso contrário f(a) = comprimento do maior caminho a partir do grupo de fa e g(a) = comprimento do maior caminho começando no grupo de ga.

 

Para a matriz da Gramática simplificada do Ex1:

 

Precedência de Operadores: Recuperação de Erros

  1. Reduce Error
  2. MP[a,b] = Error

 

a) Um handle foi encontrado, mas não há regra que o tenha do lado direito.

Estratégia: desempilhar handle (sem ações semânticas) e diagnosticar erro.

Diagnósticos: lado direito "parecido" ao handle desempilhado.

 

Exemplo: abc desempilhado e

 

b)

 

Estratégia: Modificar (subst, elim, inserir) símbolos da pilha e/ou input

 

Exemplo: Erros para Gramática Ex1:

 

E1: quando toda uma expressão é esperada

inserir id na cadeia input

diagnóstico: "missing operand"

 

E2: expressão começando com ‘)’

eliminar ) da cadeia

diagnóstico: "unbalanced right parenthesis"

 

E3: id ou ) é seguido por id ou ( :

inserir + na cadeia

diagnóstico: "missing operator"

 

E4: expressão terminando com ( :

desempilha (

diagnóstico: "missing right parenthesis"