Analise_lexica_sintatica_revisao_gramatica

Prévia do material em texto

Lista 1 – Compiladores
Análise Léxica
Exercício 1: Quais são os nomes válidos de identificadores na linguagem reconhecida pelo autômato acima?
Resposta: Todos os nomes com um ou mais caracteres, iniciados em letra maiúscula ou minúscula acompanhados de caracteres maiúsculos ou minúsculos, ou números, ou _.
Exercício 2: Quais são as palavras reservadas reconhecidas pelo autômato acima?
Resposta: Todos os conjuntos de caracteres compostos apenas por letras minúsculas que foram definidos previamente como palavras reservadas pela linguagem (main, int, float, if, else, while, for, read, print).
Exercício 3: Explique como funciona o reconhecimento de números inteiros e de ponto flutuante no autômato acima. O AFD acima é capaz de reconhecer .5 ou 5.? Justifique.
Resposta: Ao ler um número inteiro de 0 a 9, o autômato passa do estado 0 ao estado 2. Do estado 2, é possível ler outros inteiros e continuar no estado 2, à fim de reconhecer números com mais dígitos. Caso leia algum caractere diferente de ., o autômato volta ao estado 0 e finaliza a leitura do número, tendo um inteiro. Caso leia um ., o autômato passa ao estado 3 e é possível receber mais números para preencher as casas decimais no estado 3 e 4. Caso leia algum caractere diferente de 0-9, o autômato volta ao estado 0 e finaliza a leitura do número, tendo um float.
O autômato não é capaz de reconhecer .5, pois teria que ler primeiro um número para passar do estado 0 para o estado 2.
O autômato não é capaz de reconhecer 5., pois 3 não é estado final.
Exercício 4: Explique como funciona o reconhecimento dos operadores < e <=.
Resposta: Ao ler o símbolo <, o autômato passa do estado 0 para o estado 5. Do estado 5, é possível ler o símbolo = para reconhecer <= ou um espaço para reconhecer apenas o <.
Exercício 5: Implemente em uma linguagem de programação de sua escolha um analisador léxico para a linguagem Csmall dada no portal.
Resposta: Enviada separadamente.
Revisão de Gramática
Exercício 1: Faça uma gramática que gera a linguagem dos parênteses balanceados.
Resposta: G = ({S}, {(, )}, P, S)
P:
S -> (), (S), SS | ε
G = ({S,Elist,E,Eopc,Termo},{;,ID,NUM,=,+,-},P,S), ondeP:
S → Elist
Elist → E ; Elist | ε
E → ID = Termo Eopc
Eopc → + Termo Eopc | - Termo Eopc | ε
Termo → ID | NUM
Exercício 2: Quais cadeias essa gramática gera? Dê exemplos.
Resposta: Zero ou mais expressões do tipo ID = soma ou subtração entre IDs ou NUMs
Exemplos: ID = NUM + NUM - NUM;
ID = ID + NUM - NUM + ID;
ID = ID; ID = NUM - NUM + ID;
Exercício 3: Mostre o passo a passo da derivação das cadeias: 
1) ID = ID; 
Resposta: 
S -> Elist
Elist -> E; Elist 
E; Elist -> ID = Termo Eopc; Elist 
ID = Termo Eopc; Elist -> ID = ID Eopc; Elist
ID = ID Eopc; Elist -> ID = ID ε; Elist
ID = ID ε; Elist -> ID = ID; Elist
ID = ID; Elist -> ID = ID; ε
ID = ID; ε -> ID = ID;
2) ID = ID + NUM; 
Resposta: 
S -> Elist
Elist -> E; Elist 
E; Elist -> ID = Termo Eopc; Elist
ID = Termo Eopc; Elist -> ID = ID Eopc; Elist 
ID = ID Eopc; Elist -> ID = ID + Termo Eopc; Elist
ID = ID + Termo Eopc; Elist -> ID = ID + NUM Eopc; Elist
ID = ID + NUM Eopc; Elist -> ID = ID + NUM ε; Elist
ID = ID + NUM ε; Elist -> ID = ID + NUM; Elist
ID = ID + NUM; ε -> ID = ID + NUM;
3) ID = NUM; ID = ID - ID;
Resposta: 
S -> Elist
Elist -> E; Elist
E; Elist -> ID = Termo Eopc; Elist
ID = Termo Eopc; Elist -> ID = NUM Eopc; Elist
ID = NUM Eopc; Elist -> ID = NUM ε; Elist
ID = NUM ε; Elist -> ID = NUM; Elist
ID = NUM; Elist -> ID = NUM; E; Elist
ID = NUM; E; Elist -> ID = NUM; ID = Termo Eopc; Elist
ID = NUM; ID = Termo Eopc; Elist -> ID = NUM; ID = ID Eopc; Elist
ID = NUM; ID = ID Eopc; Elist -> ID = NUM; ID = ID - Termo Eopc; Elist
ID = NUM; ID = ID - Termo Eopc; Elist -> ID = NUM; ID = ID - ID Eopc; Elist
ID = NUM; ID = ID - ID Eopc; Elist -> ID = NUM; ID = ID - ID ε; Elist
ID = NUM; ID = ID - ID ε; Elist -> ID = NUM; ID = ID - ID; Elist
ID = NUM; ID = ID - ID; Elist -> ID = NUM; ID = ID - ID; ε
ID = NUM; ID = ID - ID; ε -> ID = NUM; ID = ID - ID;
Exercício 4: A Cadeia ID + ID é válida? E ID = ? E NUM = ID; ? Justifique.
Resposta: 
- A cadeia 'ID + ID' não é válida, pois ao fazer a derivação, sempre obteremos expressões vazias ou iniciadas com "ID =".
- A cadeia 'ID =' não é válida, pois não existe Termo vazio. Dessa forma, sempre que houver ID =, aparecerá em seguida pelo menos um Termo (ID ou NUM). 
- A cadeia 'NUM = ID' não é válida, pois não existe derivação em que NUM apareça antes do sinal de igualdade.
E -> E + T | T
T -> T * F | F
F -> ( E ) | a F' | b F'
F' -> a F' | b F' | 0 F' | 1 F' | ε
Exercício 5: Existe mais de uma derivação para a cadeia a * a + a? Justifique.
Resposta: Não. Mesmo podendo escolher dois caminhos na derivação de E -> E + T | T, podemos escolher apenas o caminho E + T para que não haja parênteses no a + a e a precedência não mude.
Exercício 6: Derive a cadeia (a + b) * a.
Resposta:
E -> T
T -> T * F
T * F -> F * F
F * F -> (E) * F
(E) * F -> (E + T) * F
(E + T) * F -> (T + T) * F
(T + T) * F -> (F + T) * F
(F + T) * F -> (aF' + T) * F
(aF' + T) * F -> (aε + T) * F
(aε + T) * F -> (a + T) * F
(a + T) * F -> (a + F) * F
(a + F) * F -> (a + bF') * F
(a + bF') * F -> (a + bε) * F
(a + bε) * F -> (a + b) * F
(a + b) * F -> (a + b) * aF'
(a + b) * aF' -> (a + b) * aε
(a + b) * aε -> (a + b) * a
Exercício 7: O que acontece se eu começo a derivação de a * a + a escolhendo a regra E -> T?
Resposta: O 'a + a' fica entre parênteses, mudando a precedência.
 
Exercício 8: Dada as seguintes produções:
1) T -> T + ID
2) T -> ID , responda:
Existe conflito na escolha de regras? Justifique.
Caso exista conflito, explique qual é e transforme a gramática para remover o conflito.
Resposta: Existe conflito, pois é possível derivar a mesma cadeia de formas diferentes.
- Transformando a recursão à esquerda em recursão à direita:
T -> ID + T
T -> ID
- Fatoração:
T -> ID T'
T' -> +T | ε
Exercício 9: Remova os conflitos das produções dadas abaixo. Mostre as novas produções obtidas.
E -> T + E
E -> T
T -> F * T
T -> F
Resposta:
E -> T E'
E' -> + E | ε
T -> F T'
T' -> * T | ε
Análise Sintática
Exercício 1: Faça o passo a passo da análise sintática da cadeia ID MULT LBRACKET NUMPLUS ID RBRACKET (em outras palavras, id * (num + id)).
Resposta: 
	PILHA 
	RESTANTE DA ENTRADA
	AÇÃO
	E
	ID MULT LBRACKET NUM PLUS ID RBRACKET $
	Desempilha E empilha E' T
	E' T 
	ID MULT LBRACKET NUM PLUS ID RBRACKET $
	Desempilha T e empilha T' F
	E' T' F
	ID MULT LBRACKET NUM PLUS ID RBRACKET $ 
	Desempilha F e empilha ID
	E' T' ID 
	ID MULT LBRACKET NUM PLUS ID RBRACKET $
	Desempilha ID avança na entrada
	E' T' 
	MULT LBRACKET NUM PLUS ID RBRACKET $
	Desempilha T' e empilha T' F MULT
	E' T' F MULT
	MULT LBRACKET NUM PLUS ID RBRACKET $
	Desempilha MULT e avança na entrada
	E' T' F
	LBRACKET NUM PLUS ID RBRACKET $ 
	Desempilha F e empilha RBRACKET E LBRACKET
	E' T' RBRACKET E LBRACKET
	LBRACKET NUM PLUS ID RBRACKET $ 
	Desempilha LBRACKET e avança na entrada
	E' T' RBRACKET E 
	NUM PLUS ID RBRACKET $
	Desempilha E e empilha E' T
	E' T' RBRACKET E' T
	NUM PLUS ID RBRACKET $ 
	Desempilha T e empilha T' F
	E' T' RBRACKET E' T' F
	NUM PLUS ID RBRACKET $
	Desempilha F e empilha NUM
	E' T' RBRACKET E' T' NUM
	NUM PLUS ID RBRACKET $
	Desempilha NUM e avança na entrada
	E' T' RBRACKET E' T' 
	PLUS ID RBRACKET $
	Desempilha (ε)
	E' T' RBRACKET E'
	PLUS ID RBRACKET $ 
	Desempilha E' e empilha T E' PLUS
	E' T' RBRACKET T E' PLUS
	PLUS ID RBRACKET $ 
	Desempilha PLUS e avança na entrada
	E' T' RBRACKET T E' 
	ID RBRACKET $ 
	Desempilha (ε)
	E' T' RBRACKET T
	ID RBRACKET $ 
	Desempilha T e empilha T' F
	E' T' RBRACKET T' F
	ID RBRACKET $
	Desempilha F e empilha ID
	E' T' RBRACKET T' ID
	ID RBRACKET $ 
	Desempilha ID e avança na entrada
	E' T' RBRACKET T'
	RBRACKET $ 
	Desempilha T' (ε)
	E' T' RBRACKET
	RBRACKET $
	Desempilha RBRACKET E avança na entrada
	E' T' 
	$ 
	Desempilha T' (ε)
	E'
	$ 
	Desempilha E' (ε)
	Pilha vazia
	$ 
	Aceita a entrada
 
Exercício 2: Façao passo a passo da análise sintática da cadeia ID PLUS ID MULT ID (emoutras palavras, id + id * id).
Resposta:
	PILHA
	RESTANTE DA ENTRADA
	AÇÃO 
	E
	ID PLUS ID MULT ID $ 
	Desempilha E e empilha E' T
	E' T 
	ID PLUS ID MULT ID $ 
	Desempilha T e empilha T' F
	E' T' F 
	ID PLUS ID MULT ID $ 
	Desempilha F e empilha ID
	E' T' ID
	ID PLUS ID MULT ID $ 
	Desempilha ID e avança na entrada
	E' T'
	PLUS ID MULT ID $
	Desempilha T' (ε)
	E'
	PLUS ID MULT ID $
	Desempilha E' e empilha E' T PLUS
	E' T PLUS
	PLUS ID MULT ID $
	Desempilha PLUS e avança na entrada
	E' T 
	ID MULT ID $
	Desempilha T e empilha T' F
	E' T' F 
	ID MULT ID $
	Desempilha F e empilha ID
	E' T' ID
	ID MULT ID $
	Desempilha ID e avança na entrada
	E' T' 
	MULT ID $
	Desempilha T' e empilha T' F MULT
	E' T' F MULT
	MULT ID $
	Desempilha MULT e avança na entrada
	E' T' F 
	ID $
	Desempilha F e empilha ID
	E' T' ID 
	ID $
	Desempilha ID e avança na entrada
	E' T' 
	$
	Desempilha T' (ε)
	E'
	$
	Desempilha E' (ε)
	Pilha vazia
	$
	Aceita a entrada
Exercício 3: Calcule o conjunto First para a gramática abaixo.
Exp -> Exp Soma Termo | Termo
Soma -> + | -
Termo -> Termo Mult Fator | Fator
Mult -> * | /
Fator -> ( Exp ) | NUM | ID
Terminais = {+,-,*,/,(,),NUM,ID}
Resposta:
First(+) = +
First(-) = -
First(*) = *
First(/) = /
First(() = (
First()) = )
First(NUM) = NUM
First(ID) = ID
First(Exp) = {First(Exp Soma Termo), First(Termo)}
First(Termo) = {First(Termo Mult Fator), First(Fator)}
First(Fator) = ( First(Exp) ), NUM, ID
Então, 
First(Exp) = (, NUM, ID
First(Termo) = (, NUM, ID
First(Fator) = (, NUM, ID
First(Soma) = +, -
First(Mult) = *, /
Exercício 4: Calcule os conjuntos Follow dos não-terminais S, A, B e D na gramática abaixo.
S -> B x A D y
B -> b B | ε
A -> a A | ε
D -> d B | f B | ε
Resposta:
Follow(S) = {$}
Follow(B) = { x, Follow(D) } = {x, y}
Follow(A) = { First(D), y } = {d, f, y} 
Follow(D) = y
Exercício 5: Construa os conjuntos First e Follow e a tabela M para a gramática abaixo.
Responda às seguintes questões:
1. S -> if E then S S'
2. S -> s
3. S' -> else S
4. S' -> ε
5. E -> e
Onde Terminais = {if, then, else, s, e}. O terminal s representa um comando e o terminal e representa uma expressão.
Resposta:
First(if) = {if}
First(then) ={then}
First(else) = {else}
First(s) = {s}
First(e) = {e}
First(S) = {if, s}
First(S') = {else, ε}
First(E) = {e}
Follow(S) = {$, else}
Follow(S') = {$, else}
Follow(E)={then}
Regra 1:
M[S,if] = S -> if E then S S’
M[S,s] = S -> s
M[S’,else] = S’ -> else S
M[E,e] = E -> e
Regra 3:
S’ → ε
Follow(S’) = {else,$}
M[S',else] = S' -> ε
M[S',$] = S' ->ε
	
	if
	then
	s
	else
	e
	$
	S
	S -> if E then S S’
	
	S -> s
	
	
	
	S'
	
	
	
	S’ -> else S
ou
 S' -> ε
(conflito)
	
	S' ->ε
	E
	
	
	
	
	E -> e
	
Existe algum conflito na tabela M? 
Sim, pois há suas produções na linha S' e coluna else.
Como podemos resolver esse conflito?
Escolhendo a produção que não gera cadeia vazia, pois neste caso, não teremos projuízo na cadeia.
Exercício 6: Explique como o código acima reconhece a entrada ID MINUS NUM DIV ID. Mostre o passo a passo do reconhecimento destacando todas as chamadas de função realizadas.
Resposta: 
- A função E é executada e, como token == ID, a função T é executada dentro do if. Na função T, a função F é executada e match(ID) é encontrado, então ID é reconhecido.
- Voltando à função T, T_ é executada. Na função T_ não há nenhuma ação tomada. Voltando À função E dentro do if, a função E_ é executada. Como token == MINUS, match(MINUS) é encontrado, então MINUS é reconhecido. 
- Em seguida, dentro do mesmo if, a função T é executada. Dentro de T, F é executada e, como token == NUM, match(NUM) é encontrado e NUM é reconhecido.
- Voltando a T, T_ é executada e, como token == DIV, match(DIV) é encontrado e DIV é reconhecido.
- Em seguida, dentro do mesmo if, a função F é executada. Como token == ID, match(ID) é encontrado, então ID é reconhecido.
- Voltando a T_, T_ é executado sem que nada aconteça.
- Voltando a E_, E_ é executado sem que nada aconteça.
- Voltando a E, token == EOF e é o fim da análise (Entrada aceita).
Exercício 7: Explique como o código acima reconhece a entrada ID DIV LBRACKET NUM PLUS ID RBRACKET. Mostre o passo a passo do reconhecimento destacando todas as chamadas de função realizadas.
Resposta:
- A função E é executada e, como token == ID, a função T é executada dentro do if. Na função T, a função F é executada e match(ID) é encontrado, então ID é reconhecido.
- Voltando à função T, T_ é executada. Como token == DIV, match(DIV) é encontrado e DIV é reconhecido.
- Em seguida, dentro do mesmo if, a função F é executada. Em F, como token == LBRACKET, match(LBRACKET) é encontrado e LBRACKET é reconhecido.
- No mesmo if, a função E é executada. Como token == NUM, a função T é executada, a função F é executada e, como token == NUM, match(NUM) é encontrado e NUM é reconhecido.
- Voltando à função T, T_ é executado sem que nada aconteça.
- Voltando à função E, E_ é executado e como token == PLUS, match(PLUS) é encontrado e PLUS é reconhecido.
- No mesmo if, a função T é executada e F é executada. Como token == ID, match(ID) é encontrado e ID é reconhecido.
- Voltando a T, T_ é executado sem que nada aconteça.
- Voltando a E_, E_ é executada sem que nada aconteça.
- Voltando a F, acontece match(RBRACKET) e RBRACKET é reconhecido.
- Voltando a T_, T_ é executado sem que nada aconteça.
- Voltando a T, T_ é executada sem que nada aconteça.
- Voltando a E, token == EOF e é o fim da análise (Entrada aceita).