Prova resolvida compiladores

UNILASALLE – Curso de Ciência da Computação
DISCIPLINA: COMPILADORES – Prof. Simão Sirineo Toscani

Prova 01 - 25/09/2009 GABARITO

Questão 1: Dada a gramática:

G = ( {S, A, B}, {a, b}, { S ( AbB, A ( a , B ( bB | b }, S )

(a) Qual é a linguagem gerada por G?

L(G) = {abb, abbb, abbbb, ...} = abb b* = ab b+= ab bn (n(1)

(b) Construa um analisador descendente recursivo preditivo para reconhecer L(G).

A gramática precisa ser LL(1). Para isso, ela precisa estar fatorada. As regras de B, fatoradas, ficam: B ( bX X ( B | (

Portanto, a gramática passa a ter as seguintes regras de produção:

S ( AbB A ( a B ( bX X ( B | (

begin /* programa principal */ token:= LETOKEN; if S then if token = ‘$’ then write(‘SUCESSO’) else write(‘ERRO’) else write(‘ERRO’) end function S ; if A then if token = ‘b‘ then { token := LETOKEN; if B then return TRUE else return FALSE } else return FALSE else return FALSE

(c) Construa a tabela de precedência de operadores para G.

Método mecânico:

As regras de produção são: S ( AbB, A ( a , B ( bB | b

primeiros(S) = {b. a} últimos de S= {b} primeiros(A) = {a} últimos de A= {a} primeiros(B) = {b} últimos de B= {b}

Nos lados direitos das regras de produção temos: “Ab” e “bB”

| |a |b |$ |
|a | |> | |
|b | |< |> |
|$ |< |< |AC |

Portanto: últimos de A > b {a} > b b < primeiros de B b < {b} $ < primeiros de S $ < {a, b} últimos S > $ {b} > $

| |a |b |$ |
|a | |> | |
|b | |< |> |
|$ |< |< |AC |

(d) Obtenha as funções