Gramática de Precedência Simples

Uma gramática é de precedência simples quando:

  1. entre seus elementos existe no máximo uma relação de Wirth Weber;
  2. se não tem derivação nula;
  3. todas produções possuem lados direitos únicos

 

Parser para Gramáticas de Precedência

Procedimento:

Seja uma forma sentencial.

A partir da esquerda para direita olhamos para 2 símbolos adjacentes, por vez, visando determinar o "último" (last) e a "cabeça" de um handle e, portanto, a regra que o derivou.

Assim, dada uma forma sentencial...........RS.........

R,S Î (VN È VT).

Em algum ponto da análise, ou R ou S ou ambos devem fazer parte de algum handle.

 

São 3 possibilidades:

 

  1. R é parte de um handle, mas S não é.

    Então dizemos que R > S (R precede S) ou seja, R será reduzido antes que S.

    Assim, R certamente será o "último" da regra U::= ......R.

    Além disso, como o handle está à esquerda de S, S necessariamente é um terminal (dmd)

     

  2. R e S estão ambos no mesmo handle.

    Então dizemos que R = S (têm mesma precedência).

    Portanto U::= .....RS.....

     

  3. S é parte de um handle, mas R não é.

Então dizemos que R < S (menor precedência que).

Portanto U::= S........

 

Ex1:

S ® bAb

A ® (B | a

B ® A a)

L(G)= {bab, b(aa)b, b((aa)a)b, b(((aa)a)a)b, ...}

As relações >, =, < são chamadas Relações de Wirth Weber.

 

Ex2:

S ® aSSb

S ® c

a = S, S = S, S = b

a < a, a < c, S < a, S < c

c > a, c > c, c > b, b > a, b > b, b > c

 

OBS: As relações não são simétricas:

X = Y não implica que Y = X

X < Y não implica que Y > X

 

Tabela de Precedência Simples:

 

OBS: $ < X para todo X tal que S Þ Xa

X > $ para todo X tal que S Þ a X

X Î (VN È VT)

 

Analisando $ bab $

estabelecemos as relações de Wirth Weber na cadeia de entrada, incrementalmente da esquerda para direita até encontrar um delimitador de handle, ou seja, uma relação >. A ocorrência de < à esquerda, mais próxima, delimita o início do handle. Obviamente, entre um e outro só haverá =

Por ter lados direitos únicos, a redução será única.

 

 

Sucesso!!!

 

Analisando b(aa)b

 

Sucesso!!!