Questões de compiladores e computabilidade

Prévia do material em texto

Questões de compiladores e computabilidade
1. A respeito do processo em que se define uma linguagem de programação, é importante lembrar que o trabalho realizado por um compilador consistirá, entre outras tarefas, no reconhecimento das sentenças válidas naquela linguagem. Desta maneira, qual das seguintes afirmativas pode ser considerada incorreta?
 Resposta
 a. Qualquer autômato finito tem um equivalente, autômato finito determinístico mínimo, que é único.
  b. Toda gramática livre de contexto gera linguagens reconhecíveis por autômatos de pilha. 
c. Em 1950, a tentativa de projetar uma linguagem universal, a UNCOL, não obteve sucesso, pois havia uma dificuldade em representar todas as linguagens, arquiteturas e conjuntos de instruções dentro de um mesmo projeto.
 d.  As linguagens livres de contexto são reconhecidas por autômatos de pilha.
 e.  As linguagens irregulares são reconhecidas por autômatos finitos.
2. [ENADE 2008] Qual tipo de software tradutor deve ser utilizado para programas em geral, quando a velocidade de execução é uma exigência de alta prioridade?
 Resposta
 a. Compiladores.
 
 b. Interpretadores.
 
c. Tradutores híbridos.
 
d. Macroprocessadores.
 
e. Interpretadores de macroinstruções.
3. Algumas linguagens exigem que o código fonte seja previamente traduzido para linguagem de máquina antes de ser executado. Chama-se esta fase de:
· A Linkedição. 
· B Interpretação. 
· C Tradução. 
· D Compliação. 
· E Edição. 
4. Na implementação de compiladores, a fase de parser do programa baseia-se, em parte, no resultado de um analisador léxico. 
Assinale a opção que descreve o papel de um analisador léxico. 
· A Representar as regras da gramática da linguagem. 
· B Verificar a conformidade do código fonte com as regras da gramática da linguagem. 
· C Definir a notação em que as regras da gramática são expressas. 
· D Identificar os tokens gramaticais no código fonte. 
· E Exprimir a semântica das construções da linguagem. 
5. São tarefas de responsabilidade de um montador Assembler:
i) A substituição dos mnemônicos pelos opcodes numéricos do conjunto ISA (Instruction Set of Architecture), seguindo uma tabela de associações que relaciona o mnemônico com a instrução-alvo.
ii) A substituição dos endereços simbólicos que representam destinos de saltos e constantes por endereços numéricos, determinando de maneira absoluta ou relativa em termos do registrador PC (Program Counter) o endereço de destino dos rótulos.
iii) Reservar espaço na memória para armazenamento de dados de acordo com o tipo associado a cada variável declarada no programa.
iv) Gerar constantes em memória para variáveis e constantes, determinando o valor associado ao modo de endereçamento do operando.
Resposta Selecionada:
e.Todos itens são verdadeiros.
7. 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.
R= Detectar os marcadores de início e de fi 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. 
8. 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
R=Todos itens são verdadeiros e os motivos apresentados justificam a separação dos analisadores.
9. 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.
R= Dentre a categoria de analisadores descendentes podemos citar os parses
Descendentes Recursivos, de Cocke‐Younger‐Kasami e os analisadores do
tipo LR(k).
10. 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
 R= 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.
11. 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:
R=É 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.
12.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.
	
	a.
	Durante a análise léxica o compilador varre o código fonte em busca dos lexemas da linguagem (isto é, caracteres que, expressos de modo simples ou combinados, apresentam relevância na linguagem), compondo estas sequência de caracteres em blocos chamados tokens.
	
	b.
	Na análise sintática são verificadas as estruturas gramaticais do código, como por exemplo, a sintaxe dos comandos e o emprego correto dos operadores. Os tokens que compõem o código fonte são verificados quanto a sequência em que aparecem e se todos os elementos esperados para aquela construção sintática estão corretos e presentes.
	
	c.
	A verificação semântica das construçõesdo código analisa aspectos que estão além da sintaxe, como por exemplo, a compatibilidade entre tipos e a declaração prévia de variáveis.
	
	d.
	Embora não obrigatório pelo modelo, a etapa de síntese pode ser decomposta em três subfases. a geração de código intermediário, em que se produz uma versão do algoritmo utilizando instruções de três endereços; a otimização, em que se procurar eliminar redundâncias e melhorar o produto anterior; e por fim, a geração de código final, em que o algoritmo é efetivamente escrito em linguagem alvo.
	
	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.
13.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.
	
	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.
	
	b.
	A estratégia chamada Recuperação de Frases consiste em rentar recuperar-se do erro detectado corrigindo localmente o restante da sentença por algum elemento que permita que a análise prossiga, por exemplo, eliminando os tokens da construção inválida até que se encontre um ponto e vírgula (que sinalizaria o fim daquele comando).
	
	c.
	O uso das chamadas Produções de Erros consiste na inclusão de novas regras de produção na gramática da linguagem de modo a acomodando as situações de erro mais comuns e, com isso, permitir que se conduza ao tratamento mais adequado para erros daquela natureza.
	
	d.
	A chamada Correção Global tem por objetivo escolher ações que permitam corrigir o código globalmente, escolhendo dentre a situações possível a solução que apresente a menor sequência de alterações ao programa.
	
	e.
	O uso de métodos muito complexos pode não se justificar por consumirem muito tempo em relação ao resultado que oferecem. Vale lembrar que cabe ao programador corrigir o código e não ao compilador. Além disto, em grande parte dos casos, os vários erros envolvem um único token como, por exemplo, na falta de declaração de uma variável que torna todas as suas ocorrências dentro do código desconhecidas. 
14.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. Acerca deste 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.
	
	a.
	Ambas as assertivas são verdadeiras, sendo a segunda a justificativa da primeira.
	
	b.
	Ambas as assertivas são verdadeiras e não apresentam relação de causa e consequência entre elas.
	
	c.
	Apenas a primeira assertiva é verdadeira, pois sendo um modelo didático deveria apresentar boa eficiência no processamento.
	
	d.
	Apenas a segunda assertiva é verdadeira, pois este modelo é o mais utilizado no desenvolvimento de compiladores comerciais dada a sua flexibilidade de reuso dos módulos.
	
	e.
	Ambas as assertivas são falsas, pois o modelo não pode ser considerado didático tampouco o exemplo dado na segunda asserção representaria uma debilidade.
15.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.
	
	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.
	
	b.
	Dada uma gramática G qualquer, sempre é possível obter tanto um analisador ascendente quanto descendente para ela. Assim, a escolha de qual abordagem será empregada no projeto é meramente uma questão de escolha ou preferência.
	
	c.
	O tempo de compilação de um programa independe do método utilizado em seu analisador. Isso se justifica pelo fato de que, se considerarmos o mesmo código, os aspectos sintáticos do programa em ambas abordagens são iguais (mesma árvore de derivação) e, portanto, serão verificados através das mesmas operações (expansões dos não-terminais e verificações dos terminais).
	
	d.
	Dentre os métodos top-down, a Análise Descente Recursiva é considerado o mais eficiente e que oferece melhor desempenho na verificação do código. Em meio aos métodos botton-up, o método LL(k) é o exemplo mais comum, pois a maioria das ferramentas automáticas geram analisadores deste tipo.
	
	e.
	O método descendente LR(1) é o mais eficiente em termos de tempo médio de análise, garantindo bom desempenho mesmo para programas bastante complexos em termos sintáticos. Por este motivo os métodos LR são os mais utilizados em projetos de compiladores comerciais.
16. 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.
	
	a.
	Apenas o item I é verdadeiros, justificando a separação dos analisadores.
	
	b.
	Apenas os itens I e III são verdadeiros, mas o item iii não justifica a separação dos analisadores.
	
	c.
	Apenas os itens I e II são verdadeiros, mas apenas o item ii justifica a separação dos analisadores.
	
	d.
	Todos itenssão verdadeiros, mas nenhum deles justificam a separação dos analisadores.
	
	e.
	Todos itens são verdadeiros e os motivos apresentados justificam a separação dos analisadores.
17.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
	
	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.
	
	b.
	(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,(S,a)) ⇒ Erro, cadeia inválida.
	
	c.
	(a,(a),(a,a)) ⇒ (a,(a),(a,I)) ⇒ (a,(a),(I,I)) ⇒ (a,(a),(S)) ⇒ (a,(a),(S)) ⇒ (a,(a),L) ⇒ (a,(a),I) ⇒ (a,(a),S) ⇒ (a,(I),S) ⇒ (a,(S),S) ⇒ (a,L,S) ⇒ (a,I,S) ⇒ (a,S) ⇒ (I,S) ⇒ (S) ⇒ L.
	
	d.
	L ⇒ (S) ⇒ (I,S) ⇒ (a,S) ⇒ (a,I,S) ⇒ (a,L,S) ⇒ (a,(S),S) ⇒ (a,(I),S) ⇒ (a,(a),S) ⇒ (a,(a),I) ⇒ (a,(a),L) ⇒(a,(a),(S)) ⇒ (a,(a),(I,S)) ⇒ (a,(a),(a,S)) ⇒ (a,(a),(a,I)) ⇒ (a,(a),(a,a)).
	
	e.
	L ⇒ (S) ⇒ (I,S) ⇒ (a,S) ⇒ (a,I,S) ⇒ (a,L,S) ⇒ (a,(S),S) ⇒ (a,(I),S) ⇒ (a,(a),S) ⇒ (a,(a),I) ⇒ (a,(a),L) ⇒(a,(a),(S)) ⇒ (a,(a),(I)) ⇒ (a,(a),(a)) ⇒ Erro, cadeia inválida. 
18.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:
	
	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.
	
	b.
	Consiste no uso de uma tabela de movimentos que determina quais regras de produção devem ser utilizadas em cada momento do processo. A análise tem início aplicando a regra dada na primeira entrada da tabela e termina quando todos os elementos da entrada forem consumidos pelo analisador.
	
	c.
	Diferencia-se de outros métodos descendentes por iniciar o processo de análise através de uma operação recursiva de empilhamento, em que cada token do programa é colocado em uma estrutura de dados para processamento posterior. A seguir, os símbolos são um a um desempilhados e confrontados com a sequência esperada na derivação mais à direita (right-most) invertida.
	
	d.
	Trata-se de um dos métodos descendentes mais eficientes e amplamente adotado no desenvolvimento de compiladores comerciais, pois seu caráter recursivo permite a análise recorrente das estruturas sintáticas da linguagem de maneira ótima além de consumir pouco recurso computacional. Adicionalmente, dada a capacidade de ser aplicado a qualquer tipo de gramática, é considerado um modelo universal.
	
	e.
	É considerado apenas um modelo teórico, pois os procedimentos recursivos são úteis apenas para a compreensão e formulação de problemas. Dentro da computação os algoritmos recursivos são os mais complexos e difíceis de serem compreendidos, tornando impossível a implementação de um reconhecedor sintático que use esta técnica. 
19.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).
20.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)?.
	
	a.
	S → if E then S R fi | K
R → else S | ε
	
	b.
	S → if E then S R
R → else S fi | ε
	
	c.
	S → if E then R fi
R → S else S | K
	
	d.
	S → if E then S R
R → else S fi | if E then S fi | K
	
	e.
	S → if E then R fi | ε
R → S | else S | K
21.Assinale a alternativa que representa a principal tarefa realizada pela Análise léxica.
	
	a.
	Ler o conteúdo do arquivo fonte, caractere a caractere, agrupando-os em palavras de acordo com a separação dada pelos espaços em branco do texto.
	
	b.
	Percorrer o arquivo fonte, palavra por palavra, analisando sua disposição e ordem em relação a estrutura da linguagem.
	
	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.
	
	d.
	Reconhecer os elementos utilizados como identificadores, verificando o seu tipo e validando sua compatibilidade em expressões.
	
	e.
	Eliminar elementos irrelevantes ao processo, tais como. comentários, macros e referências de caminhos para bibliotecas (path). 
22. Aspectos como a obrigatoriedade de declaração antes do uso, compatibilidade de tipos durante atribuições ou mesmo a adequação as regras de escopo na utilização dos identificadores, são exemplos de questões que estão além do domínio sintático de uma linguagem de programação. Assim a análise semântica é responsável, fundamentalmente, por realizar três tarefas básicas: construir uma descrição dos tipos e estruturas de dados definidas pelo programador; armazenar informações sobre os identificadores; e verificar os tipos e demais aspectos dependentes de contexto na estrutura do programa. 
Acerca da análise semântica de programas, assinale a alternativa correta. 
	
	a.
	Considera-se portanto que são atribuições do componente semântico de um compilador as tarefas de verificar o emprego correto dos identificadores, no que diz respeito ao seu escopo de uso, tipagem e declaração prévia. Deste modo, em linguagens ditas fracamente tipadas a fase de análise semântica do em compilador é inexistente, uma vez que não necessitam definir o tipo de uma variável e tampouco declará-la antecipadamente.
	
	b.
	Algumas atividades da análise semântica são ditas estática, pois relacionam-se estritamente com as questões de relacionamento entre os elementos do código fonte. Como exemplo de semântica estática, podemos citar as verificações de tipos e escopo para variáveis e sub-rotinas. Contudo, linguagens orientadas a objetos, a verificação de tipos durante a declaração de objetos não pode ser realizada em tempo de compilação dado os mecanismos de herança.
	
	c.
	Há aspetos semânticos que estão ligados a execução do programa e referem-se a forma como o programa realiza suas tarefas. Por exemplo, supondo o comando“SE (i<>0) E (K/I > 10) ...”, entende-se que, se concluirmos que a primeira parte é falsa não há necessidade de avaliar a segunda (uma vez que para o operador E é impossível obter um resultado verdadeiro nesta situação). Por outro lado, se o analisador semântico não considerar a relação que envolve estas duas cláusulas, a falsidade da primeira implicará em um erro de divisão por zero durante a avaliação da segunda cláusula.
	
	d.
	O processo de análise semântica não permite o uso de formalismos uma vez que suas atividades estão além do domínio sintático da linguagem. Na maioria dos casos suas tarefas são implementadas manualmente em meio as verificações de sintaxe, tornando estas duas fases indistinguíveis durante o processo de compilação.
	
	e.
	A tabela de símbolos é considerada uma estrutura de armazenamento secundária e de pouca importância, pois nela são encontrados apenas os dados sobre os identificadores presentes no programa. Sua existência se justifica pela necessidade de tornar os elementos definidos pelo programador conhecidos ao compilador, de modo que este não acuse tais elementos como erros durante o processo de compilação. 
23. A tabela de símbolos é uma estrutura de dados que tem por propósito armazenar todos os nomes declarados pelo programador juntamente com os seus respectivos atributos. É considerada fundamental para o processo de compilação, pois participa de várias etapas do processo inclusive para a geração de código. Durante a análise semântica o compilador busca nesta tabela as informações sobre os identificadores que participam de suas análises, como por exemplo, para recuperar os tipos dos identificadores envolvidos no cálculo de uma expressão com o propósito de verificar a compatibilidade entre eles. 
Sobre a tabela de símbolos e a análise semântica é incorreto afirmar que:
	
	a.
	Questões relacionadas a declaração prévia dos identificadores, escopo de utilização e a verificação dos argumentos informados como parâmetro durante a chamada de uma sub-rotina são aspectos pertinentes ao componente semântico de tempo de execução.
	
	b.
	Os tipos declarados pelo programador estendem os elementos básicos da linguagem, permitindo a definição de variáveis que estão além dos tipos primitivos oferecidos por ela. Desta forma, em uma linguagem de programação orientada a objetos, o analisador semântico desempenha um papel mais complexo uma vez que é responsável também pelas verificações de compatibilidade entre classes derivadas e pela resolução do escopo no caso da reescrita de métodos.
	
	c.
	A tabela de símbolos apresenta registros (tuplas) de tamanhos variados, de acordo com natureza do identificador armazenado. Por exemplo, para variáveis são importantes informações quanto ao tipo de dado que armazena, seu escopo de atuação e visibilidade; já para as sub-rotinas, além do nome que a identifica, é importante saber quantos parâmetros são esperados, assim como o tipo de cada um deles.
	
	d.
	Durante o processo de análise sempre que um novo identificador é encontrado, uma nova entrada na tabela símbolos é criada e as informações a ele relacionadas são armazenadas. Ao longo do código várias ocorrências dos mesmos identificadores poderão ser encontradas. Se o contexto for o de comandos e não o de declarações, apenas operações de consulta são realizadas na tabela. Com isso é possível validar o uso do identificador em quanto ao tipo e escopo, por exemplo, além da obrigatoriedade de sua declaração antes da utilização.
	
	e.
	A tabela de símbolos é importante para a geração de código, pois nela encontram-se reunidas as informações sobre todos os identificadores do programa. A partir de seus dados, é possível dimensionar a quantidade de memória que precisará ser alocada para o armazenamento das variáveis estáticas, por exemplo.
24.A tabela de movimentos de um analisador LR(1) é construída a partir de um autômato de pilha, cujos estados representam o processo de derivação do programa em relação a gramática de linguagem. As diferentes posições da tabela informam ao analisador qual a operação (empilhamento, redução ou aceitação) deve ser realizada em cada instante do processo de análise, tomando como referência apenas o estado corrente e o símbolo (token) dado na entrada. Acerca desta tabela e de sua construção, analise cada uma das afirmativas a seguir e selecione a alternativa correta. 
I - A operação de empilhamento equivale a retirada do símbolo da entrada e sua inserção na pilha para processamento. A célula da tabela equivalente a esta ação é dada pelo número correspondente ao estado que o autômato assume após a transição. 
II - Durante uma ação de redução, os símbolos (estados) equivalentes a cadeia derivada, são retirados da pilha e substituídos pelo não-terminal que os origina, realizando assim o processo inverso ao da derivação pela regra em questão. Na tabela essa ação é colocada em cada célula cuja linha corresponde ao estado que contém a regra completada e as colunas correspondentes aos símbolos pertencentes ao conjunto de seguidos (Follow) do não-terminal associado à regra. 
III - A aceitação da cadeia ocorre quando encontramos uma ocorrência do símbolo inicial da gramática. Desta forma, preenchemos a coluna correspondente ao símbolo inicial com esta ação para todas as linhas da tabela.
	
	a.
	Apenas o item I é verdadeiro.
	
	b.
	Apenas o item II é verdadeiro.
	
	c.
	Os itens I e II são verdadeiros.
	
	d.
	Os itens I e III são verdadeiros.
	
	e.
	Todos itens são verdadeiros.
25.Um analisador sintático dito ascendente é aquele que processa a cadeia de entrada e constrói sua árvore de derivação de baixo para cima, ou seja, partindo dos símbolos do programa (as folhas da árvore) em direção ao símbolo inicial da gramática (raiz). A esse respeito analise cada uma das afirmativas a seguir e marque a alternativa correta. 
I - Por conta de sua forma peculiar de construção da árvore, os passos executados pelo analisador correspondem ao processo de derivação conhecido como mais à direita ( right-most) invertido. O processo mais à direita é aquele em que sempre derivamos o símbolo não-terminal mais à direita antes dos demais. E é dito invertido para que a entrada possa ser processada de maneira natural, isto é, a leitura dos símbolos de entrada sendo feito do início para o fim do arquivo. 
II - Analisadores deste tipo realizam duas operações básica: de empilhamento (ou deslocamento) de s, em que o símbolo da entrada s é colocado na pilha; e a operação de redução pela regra A→α, em que os símbolos correspondentes a cadeia α são retirados da pilha e substituídos pelo não-terminal A. 
III - A validação do programa acontece quando o analisador processa todos os símbolos da entrada e alcança o fim de arquivo, independentemente do conteúdo da pilha de controle do processo. Este momento é conhecido como validação por entrada vazia.
	
	a.
	Apenas o item I é verdadeiro.
	
	b.
	Apenas o item II é verdadeiro.
	
	c.
	Apenas os itens I e II são verdadeiros.
	
	d.
	Apenas os itens I e III são verdadeiros.
	
	e.
	Todos itens são verdadeiros.
26. Em uma Gramática de Atributos podemos classificar cada um de seus atributos em duas categorias, herdados e sintetizados, de acordo com o símbolo a quem estão associados durante o seu cálculo. Os chamados atributos herdados são aqueles que aparecem ligados a elementos posicionados a direita do sinal de derivação, ou seja, em uma regra na forma A→α, seriam os atributos ligados a qualquer símbolo da sentença α. Por sua vez, os atributos ditos sintetizados são aqueles que aparecem associados ao elemento da esquerda do sinal de derivação, isto é, para o nosso exemplo, seriam aqueles que estiverem associados ao símbolo A. A respeito dos atributos analise os itens a seguir e assinale a alternativa correta. 
I) Entre outros aspectos, a categorização dos atributos é importante pois permite determinar o sentido em que devemos percorrer a árvore sintática para calculá-lo. No caso dos atributos herdados, como o próprio nome sugere, seu valor é calculadoa partir de elementos hierarquicamente superiores da árvore e dos quais este valor “deriva”. 
II) Atributos sintetizados são computados a partir de nós inferiores da árvore sintática, assim os sucessivos valores deste atributo podem ser calculados percorrendo a árvore de baixo para cima. Esta categoria de atributos é especialmente interessante para a propagação de características comuns a diferentes trechos do código, como por exemplo no trecho “int x, y, z;”, em que o tipo int pode ser propagado para um nó superior comum a todas as variáveis (x, y e z) declaradas no mesmo comando. 
III) Gramáticas que utilizam apenas atributos sintetizados são chamadas de S-Atribuídas. Na tradução dirigida pela sintaxe, assume‐se que os símbolos terminais tenham apenas atributos sintetizados uma vez que as definições não providenciem quaisquer regras semânticas, apenas ações para a geração de código. 
 
	
	a.
	Apenas o item I é verdadeiro.
	
	b.
	Apenas o item II é verdadeiro.
	
	c.
	Os itens I e II são verdadeiros.
	
	d.
	Os itens I e III são verdadeiros.
	
	e.
	Todos itens são verdadeiros.
27.Usualmente a geração de código acontece em duas etapas. Primeiramente ocorre a tradução da estrutura do programa para um código em linguagem intermediária e em seguida, esse código dado linguagem intermediária é então traduzido para a linguagem simbólica do processador-alvo. A esse respeito julgue as afirmativas a seguir e assinale a alternativa correta. 
I - Permitir o reaproveitamento de código, facilitando a portabilidade de um compilador para diversas plataformas, uma vez que apenas os módulos finais precisam ser refeitos a cada nova plataforma de hardware. 
II - Permitir a utilização de um otimizador de código que analise aspectos independentemente de máquina e melhore o código intermediário antes de uma tradução definitiva. 
III - Permitir uma compilação portável para diferentes arquiteturas e sistemas operacionais independente de qual seja a linguagem fonte. 
 
	
	a.
	Apenas o item I é verdadeiro.
	
	b.
	Apenas o item II é verdadeiro.
	
	c.
	Os itens I e II são verdadeiros.
	
	d.
	Os itens I e III são verdadeiros.
	
	e.
	Todos itens são verdadeiros.
28.São tarefas de responsabilidade de um montador Assembler: 
I - A substituição dos mnemônicos pelos opcodes numéricos do conjunto ISA (Instruction Set of Architecture), seguindo uma tabela de associações que relaciona o mnemônico com a instrução-alvo. 
II - A substituição dos endereços simbólicos que representam destinos de saltos e constantes por endereços numéricos, determinando de maneira absoluta ou relativa em termos do registrador PC (Program Counter) o endereço de destino dos rótulos. 
III - Reservar espaço na memória para armazenamento de dados de acordo com o tipo associado a cada variável declarada no programa. 
IV - Gerar constantes em memória para variáveis e constantes, determinando o valor associado ao modo de endereçamento do operando. 
 
	
	a.
	Apenas o item I é verdadeiro.
	
	b.
	Apenas os itens I e II é verdadeiro.
	
	c.
	Os itens I, II e III são verdadeiros.
	
	d.
	Os itens II, III e IV são verdadeiros.
	
	e.
	Todos itens são verdadeiros.
29.A memória é um recurso controlado pelo sistema operacional e um programa não deve ter posições de memória fixas e pré-estabelecidas para que funcione corretamente. Usualmente o programador desenvolve seu código despreocupado de qual será sua localização na memória, pois caberá ao sistema resolver os problemas relacionados com posicionamento do código quando colocar o programa na memória para execução. Este processo de resolução de endereços é chamado de relocação. 
A atividade de relocação é realizada conjuntamente por montadores e carregadores. Os montadores são encarregados de marcar as posições no código-objeto passíveis de alteração, enquanto os carregadores devem reservar espaço suficiente na memória para receber o código de máquina e atualizar suas posições a partir da localização base do programa na memória. 
A esse respeito analise as afirmativas a seguir e assinale a alternativa correta. 
I - As referências aos símbolos externos devem estar presentes no módulo-objeto e podem ocorrer quanto um símbolo é referenciado no segmento, mas, definido, ocorre em outro segmento (descrito como uma referência externa), ou ainda, quando um símbolo é definido neste segmento e poderá ser referenciado em outro segmento (descrito como uma definição local de um símbolo externamente referenciável). 
II - O Dicionário de Símbolos Externos contém todos os símbolos que estão envolvidos no processo de resolução de referências entre segmentos: símbolos associados a referências externas, a definições locais ou a definições de segmentos. 
III - O Diretório de Relocação e Ligação indica, para cada segmento, quais posições deverão ter seus conteúdos atualizados, de acordo com o posicionamento em memória deste e de outros segmentos. 
 
	
	a.
	Apenas o item I é verdadeiro.
	
	b.
	Apenas o item II é verdadeiro.
	
	c.
	Os itens I e II são verdadeiros.
	
	d.
	Os itens I e III são verdadeiros.
	
	e.
	Todos itens são verdadeiros.
30.A respeito dos Carregadores ( Loaders) é incorreto afirmar: 
 
	
	a.
	Avaliar a quantidade de memória necessária ao programa e solicitá-la ao SO.
	
	b.
	Copiar o programa para a memória principal e preparar sua execução.
	
	c.
	Ajustar os endereços do código executável de acordo com a posição base de carregamento.
	
	d.
	Resolver os endereços de código dinamicamente em situações de swapping, pois os processos não necessariamente retornam a mesma posição.
	
	e.
	Reunir os módulos objeto em um único elemento chamado de módulo absoluto de carga.
31.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
R= Aplicação da regra B 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 que determina as produções gramaticas.
 
32. O Linker tem a tarefa de reunir em um único programa os vários módulos objeto obtidos a partir da tradução dos diferentes arquivos fontes que compõe o programa. Esse arquivo resultante, dado por todas as partes devidamente encaixadas, damos o nome de Módulo Absoluto de Carga. Durante esse processo o linker deve ser capaz de resolver as chamadas Referências Cruzadas, isto é, referência a elementos externos ao módulo corrente e são conhecidos apenas após a ligação do módulos. Tendo em mente estas atribuições, é incorreto afirmar que cabe ao Linker: 
Resposta 
Selecionada: 
R= Copiar o módulo de carga para a memória principal, 
preparando o programa para a sua execução.