compiladores e computabilidade

Prévia do material em texto

11/04/2019 Fazer teste: QUESTIONÁRIO UNIDADE I – D571_13701_A_D_20191
https://ava.ead.unip.br/webapps/assessment/take/launch.jsp?course_assessment_id=_148624_1&course_id=_31148_1&content_id=_500285_1… 1/7
 
Fazer teste: QUESTIONÁRIO UNIDADE I
COMPILADORES E COMPUTABILIDADE D571_13701_A_D_20191 CONTEÚDO
Informações do teste
Descrição
Instruções
Várias tentativas Este teste permite 3 tentativas. Esta é a tentativa número 1.
Forçar conclusão Este teste pode ser salvo e retomado posteriormente.
a.
b.
c.
d.
e.
PERGUNTA 1
 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 pre�xos 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
(pre�xo), 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
� | if E then S � | 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)?.
S → if E then S R � | K 
R → else S | ε
S → if E then S R 
R → else S � | ε
S → if E then R � 
R → S else S | K
S → if E then S R 
R → else S � | if E then S � | K
S → if E then R � | ε 
R → S | else S | K
0,5 pontos   Salva
PERGUNTA 2
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
0,5 pontos   Salva
?
 Estado de Conclusão da Pergunta:
ASSOCIADA / COLIGADA BIBLIOTECAS MURAL DO ALUNO
Clique em Salvar e Enviar para salvar e enviar. Clique em Salvar todas as respostas para salvar todas as respostas.
CONTEÚDOS ACADÊMICOS MICHELLE CHANTAL
11/04/2019 Fazer teste: QUESTIONÁRIO UNIDADE I – D571_13701_A_D_20191
https://ava.ead.unip.br/webapps/assessment/take/launch.jsp?course_assessment_id=_148624_1&course_id=_31148_1&content_id=_500285_1… 2/7
a.
b.
c.
d.
e.
analisadores sintáticos.
Nos métodos chamados de descendentes (ou top‐down), para cada nó da
árvore de derivação, o analisador deve decidir qual é a regra A→α que
deve ser aplicada ao nó corrente (rotulado com o não terminal A), criando
nós �lhos rotulados com cada um dos símbolos de α.
Os métodos ascendentes (ou bottom‐up) constroem a árvore de baixo
para cima, então o analisador deve encontrar os vários símbolos que
compõem a sentença α e escolher quando deve ser aplicada redução pela
regra A→α.
Independentemente de como os métodos de análise constroem
verticalmente a árvore (quer sejam de baixo para cima ou de cima para
baixo), em ambos os nós da árvore surgem da esquerda para a direita. A
razão disso é que, tanto em um quanto em outro, a escolha das regras
baseiam-se na cadeia a ser gerada (programa) e o arquivo sempre é lido
do início para o �m.
Dentre a categoria de analisadores descendentes podemos citar os parses
Descendentes Recursivos, de Cocke‐Younger‐Kasami e os analisadores do
tipo LR(k).
Os parses do tipo LR(k) e LALR são exemplos de analisadores que
constroem árvores de maneira ascendente. 
a.
b.
c.
d.
e.
PERGUNTA 3
 Analisadores sintáticos do tipo LL(k) realizam a veri�caçã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).
0,5 pontos   Salva
a.
PERGUNTA 4
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 a�rmar sobre o Analisador Descendente
Recursivo:
0,5 pontos   Salva
 Estado de Conclusão da Pergunta:
Clique em Salvar e Enviar para salvar e enviar. Clique em Salvar todas as respostas para salvar todas as respostas.
11/04/2019 Fazer teste: QUESTIONÁRIO UNIDADE I – D571_13701_A_D_20191
https://ava.ead.unip.br/webapps/assessment/take/launch.jsp?course_assessment_id=_148624_1&course_id=_31148_1&content_id=_500285_1… 3/7
b.
c.
d.
e.
É 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 veri�car 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.
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.
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.
Trata-se de um dos métodos descendentes mais e�cientes 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.
É 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. 
a.
b.
c.
PERGUNTA 5
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
codi�caçã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í�co. Nesse contexto, assinale a alternativa que
descreve o propósito e a principal tarefa realizada pelos compiladores. 
Facilitar a programação de computadores, pois oferecem recursos que
possibilitam a escrita do código (edição de textos), assim funcionalidades
ligadas a execução e depuração (debug).
Possibilitar a programação de computadores utilizando linguagens de alto
nível (que permitem descrever as ideias em termosmais 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.
Auxiliar na tarefa de desenvolvimento, permitindo a criação de programas
com menos erros. Para isso, devem oferecer recursos tais como. Auto
0,5 pontos   Salva
 Estado de Conclusão da Pergunta:
Clique em Salvar e Enviar para salvar e enviar. Clique em Salvar todas as respostas para salvar todas as respostas.
11/04/2019 Fazer teste: QUESTIONÁRIO UNIDADE I – D571_13701_A_D_20191
https://ava.ead.unip.br/webapps/assessment/take/launch.jsp?course_assessment_id=_148624_1&course_id=_31148_1&content_id=_500285_1… 4/7
d.
e.
completar para comandos, veri�cação de declarações de variáveis, inícios
e términos de blocos, além de outras veri�cações estruturais.
Apoiar o processo de desenvolvimento portável, oferecendo tradução do
código para diferentes arquiteturas e plataformas.
Permitir que as atividades ligadas a programação de computadores sejam
realizadas em um ambiente integrado, provendo recursos relacionados
desde a escrita do código até a sua execução no sistema operacional. 
 
a.
b.
c.
d.
e.
PERGUNTA 6
 A gramática dada a seguir é LL(1). Nela os elementos +, *, (, ) e id con�guram
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 a�rmar que:
A tabela indica que a regra 1 deve ser aplicada quando um símbolo não-
terminal E estiver sendo derivado e na entrada houver algum elemento
que pertença ao conjunto First(TE’).
Por ser uma produção que deriva para vazio, a regra 3 somente será
aplicada se o símbolo não-terminal sendo derivado for o E’ e o símbolo
corrente na entrada pertencer ao conjunto Follow(E’).
Células marcadas com “-“ indicam um movimento não previsto e assim,
qualquer situação que leve o reconhecedor a uma delas deve ser
entendida como um problema sintático da sentença e reportado como um
erro.
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.
Regras de produção que apresentam pre�xos comuns para o mesmo não-
terminal impedem a construção de um analisador deste tipo, pois
implicarão em duas ou mais regras válidas (aplicáveis) para a mesma
combinação de símbolos. Ou seja, a tabela �caria com dois ou mais
valores em uma mesma célula.
0,5 pontos   Salva
PERGUNTA 7
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 )
0,5 pontos   Salva
 Estado de Conclusão da Pergunta:
Clique em Salvar e Enviar para salvar e enviar. Clique em Salvar todas as respostas para salvar todas as respostas.
11/04/2019 Fazer teste: QUESTIONÁRIO UNIDADE I – D571_13701_A_D_20191
https://ava.ead.unip.br/webapps/assessment/take/launch.jsp?course_assessment_id=_148624_1&course_id=_31148_1&content_id=_500285_1… 5/7
a.
b.
c.
d.
e.
G = ({L,S}, { ( , ) , a , , }, L, P ) 
P. L → (S) 
S → I,S | I 
I → a | L
(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.
(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.
(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.
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)).
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. 
a.
b.
c.
d.
e.
PERGUNTA 8
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.
Quando a linguagem de codi�cação do algoritmo é de alto nível,
precisamos de um compilador para que o algoritmo original seja traduzido
para um equivalente dado em linguagem de baixo nível.
A construção de compiladores envolve conhecimentos relativos à
estrutura da linguagem e à capacidade de tradução de uma para outra,
preservando �elmente cada uma das funcionalidades descritas no código
fonte.
O uso de métodos formais permite tanto a especi�cação das linguagens
de programação quanto a implementação de reconhecedores para as
suas estruturas, compreendendo assim os fundamentos teóricos para o
estudo e a construção de compiladores.
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.
A compreensão das estruturas de uma linguagem e dos processos que
envolvem a sua de interpretação permite que tais conhecimentos sejam
aplicados não apenas na construção de compiladores, mas também na
interpretação de documentos estruturados, com as páginas da web;
parâmetros em linhas de comandos ou padrões de endereços na web, por
exemplo. 
0,5 pontos   Salva
 Estado de Conclusão da Pergunta:
Clique em Salvar e Enviar para salvar e enviar. Clique em Salvar todas as respostas para salvar todas as respostas.
11/04/2019 Fazer teste: QUESTIONÁRIO UNIDADE I – D571_13701_A_D_20191
https://ava.ead.unip.br/webapps/assessment/take/launch.jsp?course_assessment_id=_148624_1&course_id=_31148_1&content_id=_500285_1… 6/7
a.
b.
c.
d.
e.
PERGUNTA 9
Assinale a alternativa que representa a principal tarefa realizada pela Análise
léxica.
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.
Percorrer o arquivo fonte, palavra por palavra, analisando sua disposição e
ordem em relação a estrutura da linguagem.
Varrer o arquivo fonte, lendo-o caractere por caractere e agrupá-los em
blocos de um ou mais elementos de acordo com o signi�cado dentro da
linguagem.
Reconhecer os elementos utilizados como identi�cadores, veri�cando o
seu tipo e validando sua compatibilidade em expressões.
Eliminar elementos irrelevantes ao processo, tais como. comentários,
macros e referências de caminhos para bibliotecas (path). 
0,5 pontos   Salva
a.
b.
c.
d.
e.
PERGUNTA 10
Os diferentes elementos básicos que compõe uma linguagem, tais como as
palavras reservadas, identi�cadores, 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 daAnálise Sintática do código. 
Assim, um analisador léxico é antes de mais nada um elemento reconhecedor
destas estruturas e pode ser de�nido como um autômato �nito, dada a natureza
regular dos elementos da linguagem. 
Julgue cada uma das a�rmativas 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 e�cientes, para a descrição dos lexemas tornado a
implementação do reconhecedor mais fácil. 
III) O analisador sintático �caria 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.
Apenas o item I é verdadeiros, justi�cando a separação dos analisadores.
Apenas os itens I e III são verdadeiros, mas o item iii não justi�ca a
separação dos analisadores.
Apenas os itens I e II são verdadeiros, mas apenas o item ii justi�ca a
separação dos analisadores.
Todos itens são verdadeiros, mas nenhum deles justi�cam a separação
dos analisadores.
Todos itens são verdadeiros e os motivos apresentados justi�cam a
separação dos analisadores. 
0,5 pontos   Salva
 Estado de Conclusão da Pergunta:
Clique em Salvar e Enviar para salvar e enviar. Clique em Salvar todas as respostas para salvar todas as respostas.
11/04/2019 Fazer teste: QUESTIONÁRIO UNIDADE I – D571_13701_A_D_20191
https://ava.ead.unip.br/webapps/assessment/take/launch.jsp?course_assessment_id=_148624_1&course_id=_31148_1&content_id=_500285_1… 7/7
 Estado de Conclusão da Pergunta:
Clique em Salvar e Enviar para salvar e enviar. Clique em Salvar todas as respostas para salvar todas as respostas.