Analise Sintatica, notas

Page 1

Retirar recursão direta a esquerda

Ex: A -> Aa|d

A -> dW

W -> aW|labda

Fatorar regras da gramatica que possam gerar ambiguidade

Ex: A -> aA | aB | d

B -> bB | c

A -> aW | d

W -> A | B

B -> bB | c

First: é o conjunto de simbolos que iniciam derivações a partir de

uma sequência de simbolos terminais e não-terminais.

* Para calcular FIRST(X) de todos os símbolos X da gramatica, as

seguintes regras são aplicadas até que não haja mais terminais ou

lambda:

- se X é um símbolo terminal, então FIRST(X) = {X};

- se X é um símbolo não-terminal e x -> Y1 Y2 ... Yk é uma produção,

para algum k>=1 então:

- acrescenta-se 'a' a First(X) se, para algum i, a estiver em

first(Yi), e lambda estiver em todos os first(Y1) ... first(Yi-1);

- adicione lambda se lambda esta em first(Yj) para todo j = 1,2,...,k;

- se Y1 não derivar lambda, nada mais deve ser acrescentado a first(X)

Follow: é o conjunto de terminais que podem aparecer á direita de um

não-terminal A em uma sentença válida.

* Para calcular FOLLOW(X) de todos os não-terminais A, as seguintes regras devem ser aplicadas

até que nada mais possa ser acrescentado a nenhum dos conjuntos FOLLOW:

- se X é um simbolo inicial da grámatica, coloque $ em FOLLOW(X), onde $ é o marcador de

fim da entrada;

- se houver produção A -> a X b , então tudo em FIRST(b) exceto lambda está em Follow(X);

- se houver uma produção A -> aX, ou uma produção A - aXb, onde First(b) contém lambda,

então inclua o Follow(A) em Follow(X);

Gramaticas LL(1) não podem ter recursão direta a esquerda nem

regras que gerem ambiguidade (ou seja, devem estar fatoradas).