Gramática de Precedência Simples
Uma gramática é de precedência simples quando:
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:
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)
Então dizemos que R = S (têm mesma precedência).
Portanto U::= .....RS.....
Então dizemos que R < S (menor precedência que).
Portanto U::= S........
Ex1:
S
® bAbA
® (B | aB
® 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
® aSSbS
® ca = 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 Þ XaX > $ para todo X tal que S
Þ a XX
Î (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!!!