Atividade Supervisionada

Prévia do material em texto

Compiladores
RIO DE JANEIRO
2015
Carlos Eduardo Araujo Aruante
Elton Araujo
Resolução de todas as listas de Exercícios
Trabalho apresentado como requisito parcial para obtenção de aprovação na Disciplina Compiladores, para Graduação no Curso de Ciência da Computação, do Centro Universitário Carioca.
Professora: Rogério Malheiros.
RIO DE JANEIRO
2015
- PRIMEIRA LISTA DE EXERCÍCIOS
MATÉRIA – COMPILADORES
Prof : Rogério Malheiros dos Santos
Defina o que é um compilador.
É um programa que traduz outro programa de uma linguagem de alto nível para outra de baixo nível.
O que é uma linguagem fonte? Dê dois exemplos.
É a linguagem usada para escrever programas que são entrada de processos de linguagem. Exemplos: Java e Pascal.
O Delphi é uma linguagem fonte? Por que?
Não! Por que delphi é uma IDE e não uma linguagem de programação. O código fonte da IDE delphi é o object pascal.
O que é um programa tradutor? Dê dois exemplos e explique por que eles são programas tradutores.
É um programa que traduz um programa escrito em uma linguagem fonte qualquer, para um programa equivalente escrito em outra linguagem denominada linguagem fonte.
Quais são as fases de compilação?
ANÁLISE ( Léxica: acompanhamento dos tokes na tabela de símbolos; Sintática: obedecer a estrutura na tabela de regras; Semântica: verificar o tipo de variável).
SÍNTESE ( Geração de Código Intermediário; Otimização do Código intermediário; Geração da Código Objeto).
O que é são o LEX e o YACC?
LEX é um gerador de analisadores léxicos. YACC é um gerador de analisadores sintáticos.
O que são Tokens?
São agrupamentos do código fonte que são separados em categorias.
Faça a árvore de derivação sintática das seguintes expressões :
a) C:= d*(c+e)/h-l	 b) L:= g/h*l-o	 c) J:=o+p+g*(m/q) d) S:=t*y+i-q
	
	9) Explique o que seria a análise léxica e exemplifique.
É a etapa que identifica erros ortográficos, e identificam sequências de caracteres que se constituem em tokens. Exemplo: “Carlos foi em minha sidade”, a palavra (“sidade”) está escrita de forma incorreta, se formos conferir no nosso “dicionário” veremos que essa palavra não se escreve desta forma, portanto, isso caracteriza um erro ortográfico.
10 ) O que seria o Gerenciador de tabelas? Exemplifique.
É a porção do compilador que manipula os nomes usados pelo programa e registra informações essenciais sobre cada um deles, tal como seu tipo.
Exemplo: IF y < 200 THEN 
Begin 
Write(y); 
End;
TABELA DE SÍMBOLOS:
	PR
	
	OP
	VAL
	PR
	DEL
	COM
	DEL
	
	DEL
	DEL
	DEL
	DEL
	IF
	(ID,1)
	<
	200
	THEN
	BEGIN
	WRITE
	(
	(ID,2)
	)
	;
	END
	;
11) Qual a diferença entre um compilador e um interpretador?
Os processos feitos em compilador são muito mais rápidos do que no interpretador. 
O interpretador é mais portável tanto em S.O. e hardware do que no compilador. 
O interpretador apresenta melhores testes do que no compilador, pois ele gera o código intermediário, fazendo com que tenhamos fácil disponibilidade e fácil correção nos mesmos. No compilador, o código é mais seguro do que no interpretador, pois no interpretador o Código fonte fica exposto.
12) Explique o que seria um parser e exemplifique.
Parser é uma estrutura da tabela de regras que possui símbolos terminais e não terminais.
Exemplo: IF (T) Expr_Bool(NT) THEN (T)
Begin (T) 
Comandos(NT);(T) 
End(T);(T)
- SEGUNDA LISTA DE EXERCÍCIOS
MATÉRIA – COMPILADORES
Prof : Rogério Malheiros dos Santos
Defina o que são símbolos terminais e não- terminais
Símbolos terminais e não terminais são elementos léxicos usados na especificação das regras de produção que constituem uma gramática formal.
TERMINAIS: símbolos básicos, tokens. Por exemplo: if, then, else. 
NÃO-TERMINAIS: variáveis sintáticas que denotam conjuntos de símbolos. Por exemplo, comando. 
Qual a fase da análise em que ocorre mais erros de compilação? Justifique sua resposta.
Na Análise Semântica. Pois nela é apurado se os tipos das variáveis que foram declaradas em seu código fonte são compatíveis com os comandos e as operações que foram utilizados no código. Isso permite a continuação nas etapas de síntese.
Quando ocorre a análise semântica e qual a sua finalidade? Dê dois exemplos e explique-os
Aqui verificações são realizadas para assegurar que a organização dos componentes do programa é feita de forma adequada e significativa. 
A análise semântica tem o objetivo de determinar se as estruturas sintáticas fazem sentido. Por exemplo, o seguinte comando IF, sintaticamente correto, pode existir em um programa: 
Exemplo 01: if a>7 then b:=5 else b:=10; Neste exemplo se a variável “a” seja do tipo string, a comparação realizada com um número não está semanticamente correta.
Exemplo 02: if(B == C)break; else continue; Erro de verificação de fluxo de controle, o comando break só pode ser usado para indicar o fim de um case ou para quebrar a sequência de um comando de iteração. Assim como o comando continue somente pode ser usado em um comando de iteração.
Há gerenciamento de tabelas na análise semântica? Por que? 
Sim. Para ir para a próxima fase da compilação que é a “síntese”, todas às informações sobre os objetos que estão no código fonte devem ser coletadas fazendo verificações se os tipos de variáveis são adequadas para os comandos e operações usadas, para evitar possibilidade de erros.
O que é o código intermediário e qual a sua função na compilação?
É um código gerado como resultado da análise sintática (geralmente de ações semânticas a ela associadas). 
Linguagem utilizada para a geração de um código em formato intermediário entre a linguagem de alto nível e a linguagem assembly deve representar, de forma independente do processador para o qual o programa será gerado, todas as expressões do programa original. Duas formas usuais para esse tipo de representação são a notação posfixa e o código de três endereços.
Um dos grandes objetivos do uso de linguagens intermediárias é o de permitir uma facilidade maior de manipulação com finalidades ligadas à otimização do código gerado (...) além de aumentar a portabilidade do programa-objeto, tornando o compilador menos dependente de máquina.
Todos os compiladores atualmente geram código intermediário? Por que?
Sim. Pois na atualidade é comum eles gerarem códigos intermediários como uma forma de realizar melhorias em seu código fonte, deixando esse cód. mais eficaz. 
No que o código intermediário difere primordialmente do código objeto?
A grande diferença entre o código intermediário e o código objeto final, é que o intermediário não especifica detalhes tais como registradores que serão usados e quais endereços de memória serão utilizados.
Considere os seguintes comandos abaixo em pascal :
Repeat
 J:=j+1;
 Until j > 1
Escreva este comando na linguagem de três endereços e depois otimize-o, explicando porque ele melhorou.
L0: temp:= j+1; 
j:= temp; 
L1: if j > 1 goto L2 (True) 
goto L0 (False) 
L2:
Otimizado: 
L0: j:= j+1; 
if<= 1 
goto L0
L1: ...
Há alguma influência na geração do código intermediário para uma melhor tradução para o código objeto? Justifique sua resposta
Sim. Pois ao geramos o código intermediário estamos fazendo o passo a passo do código fonte, para que quando tivermos otimizá-los podemos usar procedimentos automáticos que tornam o código mais eficaz, fazendo com que chegue uma melhor tradução para o código objeto.
Faça a árvore sintática de :
a:=L/M/(N+(5*2)/3)+4
b) b:= A*B/H*L+E/R/(T-J)
TERCEIRA lista DE COMPILADORES
PROFESSOR ROGÉRIO
O que é o LEX? Explique sua função. Para quais linguagens usualmente ele é usado?
LEX é um gerenciador de analisador léxico, que é utilizado na construção de compiladores, ele permite especificar um analisador léxico definidoexpressões regulares para descrever padrões para os tokens, geralmente utilizado nas linguagens C, C++ ou pascal.
2) Do que se compõe uma especificação em LEX?
A especificação de uma linguagem LEX é composta por definições, regras e sub-rotinas.
3) O que é uma definição e para que serve?
Definição é a parte do programa onde se pode dar nome à especificação, dar apelidos às regras do LEX e chamar a tabela de regras da análise sintática no arquivo ytab.h.
4) O que é uma regra e para que serve?
As regras consistem em um padrão que será pesquisado na entrada, esse padrão vem junto com uma ação, que será feita quando o padrão for especificado.
5) O que é uma ação no LEX ?
Ação é um bloco de código na linguagem de configuração do LEX, que é executado sempre que o padrão correspondente é reconhecido.
6) Explique o que é uma subrotina no LEX e dê um exemplo.
As sub-rotinas são utilizadas quando o código utilizado em ações pode ser escrito uma vez e utilizado várias vezes. 
Exemplo: Fortran
7) Para que serve o YACC? Que tipo de programa ele é?
YACC é o gerenciador de analisadores sintáticos, vem a ser um programa que recebe um texto com a descrição de uma gramática e ações associadas.
8) O que é um gerador de análise léxica e para que ela serve?
Geradores de analisadores léxicos são ferramentas que tem como entrada uma especificação da estrutura léxica de uma linguagem (na forma de texto) e produzem um analisador léxico correspondente a especificação.
9) Dê três exemplos diferentes de especificações em LEX, explicando cada parte de uma especificação e para que ela serve
Exemplo 01
Para contar quantas vezes determinado caracter ou token apareceu no texto de entrada, pode-se utilizar uma variável contadora, como no exemplo a seguir:
Caso queira-se imprimir uma mensagem notificando o usuário que determinada expressão foi encontrada, pode-se utilizar o comando da linguagem C printf, por exemplo: 
%% 
Mosca
Cachorro 
pessoa 
%%
Exemplo 02
Exemplo 03
10) Dê 7 exemplos de operadores de regras e explique cada um deles 
? especifica 0 ou 1 ocorrências na expressão 
* especifica 0 ou mais ocorrências na expressão 
+ especifica 1 ou mais ocorrências na expressão 
| alternância 
() agrupamento de expressões 
. especifica um único caracter 
$ especifica que o padrão deve ser reconhecido no final da linha
Quarta Lista de Exercícios-LISTA DE GRAMÁTICA 
 1)O que é um alfabeto ou vocabulário?Dê dois exemplos
São “palavras” ou símbolos primordiais. 
Ex.s: V = {0,1}, V = {A,...,Z}, V = {Substantivo,Verbo,Adjetivo,Boi}, sendo V um conjunto finito e não vazios de símbolos.
2) O que é uma palavra?Dê um exemplo
É uma junção de um ou mais símbolos do vocabulário, sendo, portanto finita. Exemplo: 1001001.
O que é uma linguagem?Dê um exemplo
É um conjunto de sentenças formadas por símbolos tomados de algum alfabeto, ou seja, uma linguagem sobre o alfabeto V é um subconjunto de V*(L C V).
Exemplo: O conjunto de sentenças válidas da língua portuguesa poderia ser definido como um subconjunto de {a,b,c,...,z}
Defina p o que é uma Gramática e dê dois exemplos
P é o conjunto finito de pares denominados regras de produção que relacionam os símbolos terminais e não-terminais. 
Uma gramática é um dispositivo formal usado para definir qual subconjunto de V* forma determinada linguagem. A gramática define uma estrutura sobre um alfabeto de forma a permitir que apenas determinadas combinações de símbolos sejam consideradas sentenças. O que é GRAMÁTICA? É um sistema gerador de linguagens; é um sistema de reescrita; é uma maneira finita de descrever uma linguagem; é um dispositivo formal usado para especificar de maneira finita e precisa uma linguagem infinita.
Gramática é Formalmente uma gramática G é definida como sendo uma quádrupla G = (N, T, P, S), onde: N é um conjunto finito de símbolos denominados símbolos não-terminais, usados na descrição da linguagem; T é um conjunto finito de símbolos denominados símbolos terminais, os quais são os símbolos propriamente ditos; P é conjunto finito de pares (α, β) denominados regras de produção (ou regras gramaticais) que relacionam os símbolos terminais e não-terminais; S é o símbolo inicial da gramática pertencente a N, a partir do qual as sentenças de uma linguagem podem ser geradas. 
Uma gramática G é de tipo 3, ou regular, se cada produção é da forma : 
A ::= aB, A ::= a ou A ::= ε, onde “A e B” são não-terminais e “a” é um terminal. 
Exemplo de Gramática Regular: 
S::= 0A|1A 
A::= 0B|1A 
B::= 0A|1B|ε
Dê dois exemplos de derivação em uma linguagem
Existem várias derivações para a construção da mesma cadeia de não‐terminais. 
Exemplo1: Derivação da cadeia (num + num) * num é apresentada abaixo:
	
Exemplo2:
Digamos que exista a seguinte seqüência de terminais (letras minúsculas) e não-terminais (letras maiúsculas): “aaaDbbb”, e que venha existir a produção “D::=ab” na gramática. Assim, dizemos que “aaaDbbb ->aaaabbbb” sendo, portanto, uma derivação válida na gramática dada.
O que é uma linguagem gerada pro uma gramática?Dê um exemplo
São chamadas de linguagens formais, se primeiro for definida a gramática, a linguagem serve como conseqüência da definição. Por outro lado, a linguagem como um conjunto de cadeias bem definidos, pode ser dada primeiro e então, procuramos uma gramática que a gere.
Ex: seja L o conjunto de todas as cadeias não vazias contendo um número par de algarismos iguais a 1. Então L é gerada pela gramática G=(V, Vt, S, P), onde V=(1,S), Vt=(1) e P={S - SS, S – 11}. Uma linguagem pode ser gerada por mais de uma gramática, L também é gerada pela gramática G’=(V’, V’t, S, P’) onde V’ = {1} e P’{S- 1S1, S – 11}.
 7 ) Segundo a Hierarquia de Chomsky quais são os tipos de Gramática e as características de cada uma?
Gramáticas Irrestritas ou Tipo 0: As linguagens geradas pelas Gramáticas Irrestritas ou do Tipo 0 são chamadas de Linguagens Irrestritas ou Linguagens do Tipo 0. 
Gramáticas Sensíveis ao Contexto ou Tipo 1: Se às regras de substituição for imposta a restrição de que nenhuma substituição possa reduzir o comprimento da forma sentencial à qual a substituição é aplicada, cria-se uma classe de gramáticas ditas sensíveis ao contexto. As gramáticas que obedecem a estas restrições pertencem, na hierarquia de Chomsky, ao conjunto das Gramáticas Sensíveis ao Contexto (GSC) ou do Tipo 1 
Gramáticas Livres de Contexto ou Tipo 2: 
São aquelas cujas regras de produção são da forma: A ->onde A Vn, V+, ou seja, quando do lado esquerdo da regra há apenas um símbolo não-terminal (uma variável). 
Gramáticas Regulares ou Tipo 3: Nas GRs, as produções são restritas às formas seguintes: A ->aB ou A -> a (linear unitária à direita) OU A -> Ba ou A -> a (linear unitária à esquerda) onde A,B Vn e a Vt Tem que escolher uma das duas formas acima. As GRs têm grande importância no estudo dos compiladores por possuírem propriedades adequadas para a obtenção de reconhecedores simples (AF). 25 As linguagens geradas pelas Gramáticas Regulares ou do Tipo 3 são chamadas de Linguagens Regulares (LR) ou Linguagens do Tipo 3. Resultado 3: Toda gramática do tipo 3 é também do tipo 2. Corolário 3: Toda LR é também uma LLC (mas nem toda LLC é LR).