Copiladores e Computabilidade UNIDADE 1

Prévia do material em texto

O processo de programar um computador para realizar uma determinada tarefa, quando analisado em relação às atividades que são necessárias desde a codificação do algoritmo até a execução propriamente dita do programa, pode ser visto como um processo complexo e que envolve vários elementos, cada qual com propósito bastante específico. Nesse contexto, assinale a alternativa que descreve o propósito e a principal tarefa realizada pelos compiladores.
		
	b. 
Possibilitar a programação de computadores utilizando linguagens de alto nível (que permitem descrever as ideias em termos mais abstratos e mais independentes da arquitetura da máquina), pois são responsáveis pela tradução do algoritmo em seu correspondente em um linguagem de baixo nível.
	Durante o processo de verificação da estrutura sintática de um programa, o analisador simula o processo de construção da árvore de derivação para o programa que está sendo compilado. Usualmente esse processo é realizado adotando-se uma dentre duas abordagens possíveis. a top-down, em que se parte do símbolo inicial da gramática e tenta-se alcançar os elementos que compõe o programa; e a botton-up, que segue o princípio contrário, partindo do código e realizado reduções na sentença até que se alcance o símbolo inicial que caracterize o elemento raiz da árvore. A respeito destas estratégias assinale a alternativa correta.
		Resposta Selecionada:
	a. 
Os métodos descendentes são usualmente mais convenientes em casos de implementação manual, enquanto os métodos ascendentes (botton-up) são considerados mais favoráveis para construtores automáticos de analisadores.
	
Uma das tarefas primordiais ao processo de compilação é que durante a verificação da sintática do programa o compilador reporte ao programador todos os erros detectados para que ele os corrija. Neste contexto, a adoção de uma estratégia que permita o tratamento e eventual recuperação diante de erros é parte das decisões que envolvem a construção dos analisadores. Assinale a alternativa que não descreve de maneira apropriada essas estratégias.
		Resposta Selecionada:
	a. 
O Modo Pânico é aquele em que o compilador exibe as mensagens de erro e interrompe qualquer outra atividade do sistema operacional, evitando problemas de gravação dos dados no disco e a corrupção dos dados armazenados.
	A gramática dada a seguir é LL(1). Nela os elementos +, *, (, ) e id configuram como símbolos terminais, enquanto os E, T, F, E’ e T’ são considerados não-terminais. A tabela de movimentos M fornece ao reconhecedor o número da regra que deve ser aplicada durante a análise da sentença, sendo necessário apenas conhecer o não-terminal a ser derivado e o primeiro símbolo presente no restante da entrada.
Sobre a construção de analisadores sintáticos deste tipo é incorreto afirmar que:
		Resposta Selecionada:
	d. 
A aplicação da regra 8 deve ser feita antes da regra 7, segundo a interpretação que temos da tabela. Esse fato se comprova ao observarmos que o símbolo “(“ poderia ocorrer imediatamente após um “id” segundo o que determina as produções da gramática.
	No modelo de Análise e Síntese o processo é dividido em duas grandes etapas. Na primeira, são realizadas todas as tarefas pertinentes a análise e compreensão do código fonte, enquanto na segunda, as atividades de otimização e a geração do código propriamente dito. Cada uma destas grandes etapas pode ser decompostas em fases, de propósito específico e cujo resultado de seu processamento servirá como dado de entrada para a próxima fase. Analise as alternativas a seguir e assinale aquela cuja atividade não corresponde a nenhuma das subfases deste modelo.
		Resposta Selecionada:
	e. 
A fase de link edição, ou ligação, é responsável por criar o arquivo executável combinando todos os arquivos objetos em um único módulo de carga.
	Assinale a alternativa que representa a principal tarefa realizada pela Análise léxica.
		Resposta Selecionada:
	c. 
Varrer o arquivo fonte, lendo-o caractere por caractere e agrupá-los em blocos de um ou mais elementos de acordo com o significado dentro da linguagem.
	Durante a varredura do código fonte pelo Scanner (Analisador Léxico) várias tarefas ditas secundárias são realizadas. Assinale a alternativa cuja tarefa não corresponde as atribuições esperadas para um analisador léxico.
		Resposta Selecionada:
	e. 
Detectar os marcadores de início e de fim de blocos para que os comandos possam ser agrupados em um único elemento e entregues para a fase de análise sintática com um comando único. 
	Os diferentes elementos básicos que compõe uma linguagem, tais como as palavras reservadas, identificadores, operadores e quaisquer outros lexemas estabelecidos por ela, também possuem uma estrutura sintática e podem ser descritos formalmente através de expressões regulares. Entretanto a tarefa de reconhecimento dos lexemas é realizada pelo Analisador Léxico, acontecendo de maneira separada da Análise Sintática do código.
Assim, um analisador léxico é antes de mais nada um elemento reconhecedor destas estruturas e pode ser definido como um autômato finito, dada a natureza regular dos elementos da linguagem.
Julgue cada uma das afirmativas a seguir e assinale a alternativa correta.
I) As gramáticas regulares não permitem a descrição de estruturas aninhadas e portanto não são capazes de descrever simultaneamente os lexemas e também as demais estruturas típicas nas linguagem de programação, tais como parênteses balanceados e comandos aninhados.
II) A separação das etapas permite utilizar gramaticas regulares, que são mais simples e mais eficientes, para a descrição dos lexemas tornado a implementação do reconhecedor mais fácil.
III) O analisador sintático ficaria muito mais complexo, pois estaria a todo momento preocupado em prever a ocorrência de símbolos irrelevantes, tais como espaços em branco, que teriam sido eliminados pela análise léxica.
		Resposta Selecionada:
	e. 
Todos itens são verdadeiros e os motivos apresentados justificam a separação dos analisadores.
	Um analisador sintático descendente constrói a árvore de derivação do programa de cima para baixo, isto é, partindo da raiz (símbolo inicial da gramática) e seguindo em direção as folhas (símbolos do programa). Todos os métodos que adotam esta estratégia seguem esta abordagem, variando pontualmente a forma como resolvem o problema de selecionar a regra a ser aplicada em cada momento. Pode-se afirmar sobre o Analisador Descendente Recursivo:
		Resposta Selecionada:
	a. 
É um reconhecedor obtido através da transcrição das regras de produção da gramática na forma de um conjunto de sub-rotinas. Assim, cada sub-rotina é responsável por verificar os elementos relativos a uma produção em particular. O processo de reconhecimento se inicia com a chamada da sub-rotina equivalente a regra que deriva o símbolo inicial da gramática. A partir disto, chamadas subsequentes para outras sub-rotinas são realizadas sempre que um símbolo não terminal é encontrado na produção. Quando todos os elementos são consumidos, a chamada inicial retorna sinalizando que se trata de uma sentença é válida.
	Supondo a gramática a seguir e a sentença (a,(a),(a,a)), quais seriam os movimentos realizados por um reconhecedor ascendente para esta cadeia?
G = ({L,S}, {“(“, ”)”, ”a”, ”,”}, L, P )
P. L → (S)
S → I,S | I
I → a | L
		Resposta Selecionada:
	a. 
(a,(a),(a,a)) ⇒ (I,(a),(a,a)) ⇒ (I,(I),(a,a)) ⇒ (I,(S),(a,a)) ⇒ (I,L,(a,a)) ⇒ (I,I,(a,a)) ⇒ (I,I,(I,a)) ⇒(I,I,(I,I)) ⇒ (I,I,(I,S)) ⇒ (I,I,(S)) ⇒ (I,I,L) ⇒ (I,I,I) ⇒ (I,I,S) ⇒ (I,S) ⇒ (S) ⇒ L.
Para o desenvolvimento de um compilador é possível que se adote um dos diferentes modelos de construção. Um destes é o que chamamos de modelo de múltiplas passagens, em que as atividades relacionadas a tradução e a escrita do código alvo são realizadas em etapas encadeadas. Cada fase realiza sua tarefa percorrendo todo o código fonte e, após uma conclusão bem-sucedida, inicia-se a etapa subsequente tendo como entrada o resultado da fase anterior. Acercadeste modelo analise as seguintes considerações.
- Trata-se de um modelo bastante didático, pois a modularização do processo permite o desenvolvimento gradativo do compilador enquanto se estuda com mais detalhes as atividades pertinentes a cada etapa.
- Por outro lado, uma desvantagem inerente ao modelo é que por exemplo um erro semântico localizado nas primeiras linhas do código fonte somente seria detectado após a conclusão das análises léxica e sintática de todas as linhas do programa.
Assinale a alternativa que representa o melhor juízo cabível sobre o que se afirmou.
	Resposta Selecionada:
	a. 
Ambas as assertivas são verdadeiras, sendo a segunda a justificativa da primeira.
	O processo de programar um computador para realizar uma determinada tarefa, quando analisado em relação às atividades que são necessárias desde a codificação do algoritmo até a execução propriamente dita do programa, pode ser visto como um processo complexo e que envolve vários elementos, cada qual com propósito bastante específico. Nesse contexto, assinale a alternativa que descreve o propósito e a principal tarefa realizada pelos compiladores.
		Resposta Selecionada:
	b. 
Possibilitar a programação de computadores utilizando linguagens de alto nível (que permitem descrever as ideias em termos mais abstratos e mais independentes da arquitetura da máquina), pois são responsáveis pela tradução do algoritmo em seu correspondente em um linguagem de baixo nível.
	Um analisador sintático LL(1) somente pode ser construído para uma classe restrita de gramáticas, que também recebem este mesmo nome. Uma de suas características é que suas produções não apresentem prefixos comuns para cadeias distintas derivadas a partir de um mesmo não-terminal. Ou seja, se duas produções que começam com o mesmo símbolo ou conjunto de símbolos (prefixo), por exemplo, como nas regras A→αβ e A→αδ e sendo First(α) ≠ ∅, implicará numa interseção entre os conjuntos First(αβ) e First(αδ) e o analisador não será capaz de decidir qual regra escolher utilizando um único símbolo da entrada. Usualmente o problema pode ser resolvido substituindo as produções da gramática que causam o problema por outras que acomodem essa restrição, mantendo a equivalência entre elas. Supondo a produção S → if E then S else S fi | if E then S fi | K e considerando ε como a sentença vazia, quais dentre as alternativas a seguir representa uma substituição válida para resolver o problema apresentado e obter uma gramática equivalente que seja LL(1)?.
		Resposta Selecionada:
	a. 
S → if E then S R fi | K
R → else S | ε
	Analisadores sintáticos do tipo LL(k) realizam a verificação da sentença de modo descendente, entretanto tem como restrição poderem ser aplicados apenas aos casos em que a gramática da linguagem é LL(k). Considerando a produção S → S x K | K qual, dentre as alternativas a seguir, poderia substituí-la de modo a eliminar a recursão a esquerda e criar uma gramática equivalente? (Considere ε representando a sentença vazia).
	
e. S -> K R
 R -> x K R |&
	Um processo algorítmico tem o objetivo de instruir o executor quanto às ações que deve realizar e a sua sequência. Para que isso ocorra é necessário que as instruções sejam dadas num formato compreensível àquele que as realizará. A programação de computadores é feita descrevendo o algoritmo em instruções de uma linguagem de programação e que, quando ditas de alto nível, apresentam características mais próximas à estrutura das linguagens humanas do que a das máquinas. Analise as alternativas a seguir e assinale a que julgar incorreta.
		Resposta Selecionada:
	d. 
Os conhecimentos relacionados à construção de compiladores encerram-se estritamente nesta atividade, oferecendo pouco ou mesmo nenhuma possibilidade de aplicação em outras áreas que não seja a tradução para linguagem de máquina.
	Os métodos ligados a análise sintática se agrupam em ascendentes e descendentes, de acordo com a forma como derivam a estrutura sintática da sentença do programa. Assinale a alternativa incorreta a respeito dos analisadores sintáticos.
		Resposta Selecionada:
	d. 
Dentre a categoria de analisadores descendentes podemos citar os parses Descendentes Recursivos, de Cocke‐Younger‐Kasami e os analisadores do tipo LR(k).