Aspectos Teóricos da Computação

Prévia do material em texto

ICET – Instituto de Ciências Exatas e Tecnologia
Aspectos Teóricos da Computação
Prof. Nelson Batista Leitão Neto
Aluno: Felipe de Oliveira Barbosa
Sumário — Arquivos de origem
	Parte
	Arquivo (Google Drive)
	Nº questões
	Parte 1
	01 CompComputabe.pdf
	12
	Parte 2
	02 Analizador Léxico e Sintático.pdf
	15
	Parte 3
	03 Tradução Dirigida Pela Sintaxe.doc
	5
	Parte 4
	04 Atributos Herdados.doc
	7
Parte 1 — Compilador: Conceitos Gerais e Fases
📄 Arquivo de origem: 01 CompComputabe.pdf
Questão 1. O que é um compilador?
Resposta: É um programa que lê um programa escrito em uma linguagem fonte e o traduz em um programa equivalente em outra linguagem (a linguagem objeto/alvo), relatando ao usuário a presença de erros no programa fonte.
Questão 2. Na compilação, o que vem a ser análise e síntese?
Resposta: Análise: divide o programa fonte em suas partes constituintes e cria uma representação intermediária (a árvore sintática). Síntese: constrói o programa objeto desejado a partir dessa representação intermediária.
Questão 3. Exemplifique 4 ferramentas que manipulam programas fontes.
• Editores de Estruturas — recebem comandos para construir um programa fonte.
• Pretty Printers — imprimem o programa de forma que sua estrutura fique visível.
• Verificadores Estáticos — leem e analisam o programa buscando erros potenciais, sem executá-lo.
• Interpretadores — executam diretamente as operações especificadas pelo programa fonte, sem gerar um programa objeto.
Questão 4. Quais são as fases do compilador?
Resposta: Análise Léxica, Análise Sintática, Análise Semântica, Geração de Código Intermediário, Otimização de Código e Geração de Código — com o Tratamento de Erros e o Gerenciamento da Tabela de Símbolos atuando ao longo de todas as fases.
Questão 5. Como funciona a análise léxica? E a análise sintática?
Resposta: Léxica: varre o arquivo de entrada caractere a caractere, usando espaços em branco, pontuação e new line para delimitar as palavras; elimina espaços e comentários e classifica os lexemas na tabela de símbolos (palavras reservadas, comandos, variáveis, tipos), identificando erros léxicos. Sintática: verifica a boa formação dos comandos segundo a gramática da linguagem, gerando a árvore sintática e identificando/reportando erros de sintaxe (mais frequentes que os léxicos).
Questão 6. O que é interpretado na análise semântica?
Resposta: A consistência de tipos dos operandos envolvidos em operações aritméticas e dos parâmetros passados a procedimentos.
Questão 7. Para que serve o Gerador de Código Intermediário? E o Otimizador de Código?
Resposta: O Gerador de Código Intermediário produz uma representação fácil de gerar e de traduzir para o código objeto, percorrendo a árvore em profundidade (das folhas para os nós). O Otimizador de Código reorganiza esse código para melhorar o desempenho em tempo de execução.
Questão 8. Quais são os tratamentos de erros no compilador?
Resposta: Existem quatro tipos de erro: léxicos, sintáticos, semânticos e lógicos — sendo os sintáticos os mais frequentes.
Questão 9. Explique as estratégias de recuperação de erros que podem ser desenvolvidas em um compilador.
• Panic Mode — descarta símbolos de entrada até encontrar um token de sincronização (";" ou "end").
• Phase Level — tenta corrigir o erro sem alterar o código-fonte (ex.: inserir ";" ou trocar ":" por ";").
• Produção de Erro — acrescenta à gramática produções que reconhecem construções erradas conhecidas de antemão.
• Correção Global — calcula a sequência mínima de mudanças para a correção de menor custo.
Questão 10. Como funciona o Gerenciamento de Tabelas de Símbolos?
Resposta: Registra os identificadores usados no programa fonte numa estrutura de dados (tabela de símbolos), contendo um registro para cada identificador com seus atributos (memória alocada, tipo, escopo).
Questão 11. Como funciona a geração de código intermediário e a geração de módulo executável?
Resposta: O código intermediário é gerado após o programa passar pelas análises léxica, sintática e semântica, servindo de ponte entre a análise e a síntese do código objeto. O módulo executável surge quando o código objeto gerado passa pelo Ligador (Link Editor), que resolve as referências externas (chamadas a rotinas de biblioteca), produzindo o módulo de carga/código executável.
Questão 12. Explique a Edição de Ligações em um compilador.
Resposta: É o processo, executado pelo Ligador (Link Editor), de examinar o código objeto, localizar as referências externas não resolvidas (chamadas a rotinas de biblioteca), buscar essas rotinas, substituir as chamadas pelo código correspondente e incluir os parâmetros necessários — produzindo o código final pronto para execução (módulo de carga).
Parte 2 — Analisador Léxico e Sintático
📄 Arquivo de origem: 02 Analizador Léxico e Sintático.pdf
Questão 1. Defina Analisador Sintático e sua função básica.
Resposta: É a fase do compilador responsável por verificar a boa formação dos comandos da linguagem de acordo com a gramática, relatando erros de sintaxe de forma inteligível e recuperando-se dos erros mais comuns para continuar processando o restante da entrada. Sua função básica é reconhecer se a cadeia de entrada pertence à linguagem definida pela gramática, construindo a árvore sintática correspondente.
Questão 2. Quais são as partes de um analisador sintático?
• Terminais — símbolos básicos que formam a cadeia (ex.: if, then, else).
• Não-terminais — variáveis sintáticas que denotam cadeias de caracteres (ex.: cmd, exp).
• Produção — forma pela qual terminais e não-terminais podem ser combinados.
• Estado de partida (S) — não-terminal distinguido como símbolo de partida; G = (T, NT, P, S).
Questão 3. Demonstre, dado a derivação E → -E → -(E) → -(E+E) → -(id+E) → -(id+id), sua árvore gramatical.
E
└── – E
 └── ( E )
 └── E + E
 ├── id
 └── id
Resposta: Essa árvore é formada durante a análise sintática para verificar a boa formação do código; as operações implicadas pelo programa fonte são registradas nessa estrutura hierárquica. Em seguida, na análise semântica, verifica-se a consistência de tipos dos operandos e parâmetros envolvidos.
Questão 4. Descreva o funcionamento do Analisador Léxico.
Resposta: Varre o arquivo de entrada caractere por caractere; usa espaços em branco, pontuação e new line para estabelecer os limites das palavras; armazena os lexemas na tabela de símbolos, classificando-os conforme a linguagem (palavras reservadas, comandos, variáveis, tipos básicos).
Questão 5. Quais são os métodos mais usados para o desenvolvimento do Analisador Sintático?
Resposta: Top-Down (constrói a árvore do topo/raiz para as folhas) e Bottom-Up (começa pelas folhas e sobe até a raiz). Em ambos os métodos, a entrada é varrida da esquerda para a direita, um símbolo de cada vez.
Questão 6. Dentro do tratamento dos erros de sintaxe, quais são os níveis que podem contê-los? Explique cada um.
• Léxico — erro de grafia de um identificador, palavra-chave ou operando.
• Sintático — expressão aritmética com parênteses não balanceados.
• Semântico — operador aplicado a um operando incompatível.
• Lógico — chamada infinitamente recursiva.
Questão 7. Explique como é feito e em que fase acontecem os tratamentos de erros de sintaxe.
Resposta: Ocorrem principalmente na fase do analisador sintático, pois os erros ou são sintáticos por natureza, ou são expostos quando o fluxo de tokens vindo do analisador léxico desobedece às regras gramaticais da linguagem. Os métodos modernos de análise sintática conseguem detectar essa presença de erros com boa precisão.
Questão 8. Quais são as metas estabelecidas dentro do tratador de erros num analisador sintático?
• Relatar a presença de erros de forma clara.
• Recuperar-se de cada erro rápido o suficiente para detectar erros subsequentes.
• Não retardar o processamento de programas corretos.
Questão 9. Descreva as estratégias de recuperação de erros:
• a) Modalidade do desespero — descarta símbolos de entrada um a um até encontrarum token de sincronização (ex.: ponto-e-vírgula ou end).
• b) Recuperação de Frases — realiza correção local na entrada restante, substituindo um prefixo remanescente por uma cadeia que permita seguir em frente (ex.: inserir/remover uma vírgula ou ponto-e-vírgula).
• c) Produção de Erro — aumenta a gramática com produções que reconhecem construções ilegais conhecidas de antemão, usando essa gramática aumentada para construir o analisador.
• d) Correção Global — busca a sequência mínima de mudanças que resulta na correção global de menor custo.
Questão 10. Descreva as partes de um Analisador Sintático e dê exemplos.
Resposta: Terminais: id, +, –, *, /, (, ). Não-terminais: ExPR e OP. Produções: ExPR → ExPr op exPr | (ExPR) | – ExPR | id; OP → + | * | / | –. Símbolo de partida: ExPR.
Questão 11. Como se dá a construção de uma árvore gramatical? (Representação gráfica simulando a leitura de uma linha de código).
Resposta: Exemplo: MONTANTE := DEPOSITO_INICIAL + TAXA_DE_JUROS * 60
:=
├── id1 (MONTANTE)
└── +
 ├── id2 (DEPOSITO_INICIAL)
 └── *
 ├── id3 (TAXA_DE_JUROS)
 └── 60
Questão 12. Existe alguma forma para que possamos compreender como certos analisadores sintáticos funcionam? Explique.
Resposta: Sim — considerando as derivações mais à esquerda, nas quais a cada passo apenas o não-terminal mais à esquerda da forma sentencial é substituído. Esse tipo de derivação ajuda a entender o funcionamento de analisadores sintáticos, especialmente os do tipo top-down.
Questão 13. O que é Handle?
Resposta: É uma subcadeia que corresponde ao lado direito de uma produção e cuja redução ao não-terminal do lado esquerdo representa um passo de uma derivação mais à direita, tomada em ordem reversa. A cadeia à direita de um handle contém apenas símbolos terminais.
Questão 14. Faça a implementação de pilha de análise sintática de empilhar e reduzir.
Resposta: Rastreando a decomposição da cadeia id₁ + id₂ * id₃, com E → E+E | E*E | (E) | id:
	Pilha
	Entrada / Ação
	$
	id1 + id2 * id3 $ → Empilhar
	$ id1
	+ id2 * id3 $ → Reduzir por E → id
	$ E
	+ id2 * id3 $ → Empilhar
	$ E +
	id2 * id3 $ → Empilhar
	$ E + id2
	* id3 $ → Reduzir por E → id
	$ E + E
	* id3 $ → Empilhar
	$ E + E *
	id3 $ → Empilhar
	$ E + E * id3
	$ → Reduzir por E → id
	$ E + E * E
	$ → Reduzir por E → E * E
	$ E + E
	$ → Reduzir por E → E + E
	$ E
	$ → Aceitar
Questão 15. Quais são as ações possíveis de operações primárias do analisador sintático? Descreva cada uma delas.
• Empilhar — o próximo símbolo de entrada é colocado no topo da pilha.
• Reduzir — o analisador localiza o início à esquerda do handle na pilha e decide qual não-terminal irá substituí-lo.
• Aceitar — o analisador anuncia o término com sucesso da decomposição.
• Erro — o analisador descobre que ocorreu um erro sintático e aciona uma rotina de recuperação de erros.
Parte 3 — Tradução Dirigida pela Sintaxe
📄 Arquivo de origem: 03 Tradução Dirigida Pela Sintaxe.doc
Questão 1. Implemente a calculadora de mesa para que também funcione com divisão e subtração (produções e regras semânticas).
Resposta: Segue a mesma lógica S-atribuída do exemplo original — D no nível de soma/subtração, W no nível de multiplicação/divisão e G como fator, avaliados de baixo para cima.
	Produção
	Regras Semânticas
	X → D n
	Imprimir (D.val)
	D → D₁ – W
	D.val := D₁.val – W.val
	D → W
	D.val := W.val
	W → W₁ / G
	W.val := W₁.val / W.val
	W → G
	W.val := G.val
	G → (D)
	G.val := D.val
	G → dígito
	G.val := dígito.lexval
Questão 2. Represente a árvore gramatical das expressões abaixo (gramática combinada E/T/F, * e / com maior precedência que + e –).
a) 5 * 4 + 7 → resultado = 27
E
├── E → T (T = 20)
│ └── T → T * F (5 * 4)
│ ├── T → F → dígito (5)
│ └── F → dígito (4)
└── + T → F → dígito (7)
b) 16 / 2 – 5 → resultado = 3
E
├── E → T (T = 8)
│ └── T → T / F (16 / 2)
│ ├── T → F → dígito (16)
│ └── F → dígito (2)
└── – T → F → dígito (5)
c) 6 * 8 + 9 / 3 → resultado = 51
E
├── E → T (T = 48)
│ └── T → T * F (6 * 8)
└── + T (T = 3)
 └── T → T / F (9 / 3)
d) 18 / 6 – 2 * 1 → resultado = 1
E
├── E → T (T = 3)
│ └── T → T / F (18 / 6)
└── – T (T = 2)
 └── T → T * F (2 * 1)
e) 36 * 2 / 4 → resultado = 18
E → T
T → T / F
├── T → T * F (36 * 2 = 72)
└── F → dígito (4)
(associatividade à esquerda: (36*2)/4)
f) 20 – 10 / 2 + 4 → resultado = 19
E
├── E → E – T (E = 15)
│ ├── E → T → dígito (20)
│ └── T → T / F (10 / 2 = 5)
└── + T → F → dígito (4)
(avaliação da esquerda p/ direita entre + e –: (20 – 5) + 4)
Questão 3. Como são utilizados os atributos sintetizados?
Resposta: Carregam o valor calculado de um nó para o seu pai, sendo avaliados de baixo para cima (das folhas para a raiz). Numa definição S-atribuída, cada regra semântica calcula o atributo do símbolo à esquerda da produção a partir dos atributos dos símbolos à direita, permitindo anotar a árvore inteira seguindo a ordem de uma análise sintática bottom-up.
Questão 4. Explique o princípio de funcionamento completo da tradução dirigida pela sintaxe.
Resposta: A gramática livre de contexto é estendida com atributos (sintetizados e herdados) associados a cada símbolo gramatical, e cada produção recebe regras semânticas que definem como calcular esses atributos. As dependências entre atributos formam um grafo, do qual se deriva uma ordem de avaliação. Conforme a árvore gramatical é construída (ou percorrida), essas regras são aplicadas, produzindo como saída valor, tipo ou código intermediário — ligando a estrutura sintática à semântica da linguagem.
Questão 5. Como funciona o Analisador Semântico?
Resposta: Usa a estrutura hierárquica (árvore) gerada pelo analisador sintático para identificar operadores e operandos, verifica erros semânticos (como incompatibilidade de tipos) e coleta informações de tipo que serão usadas na geração do código intermediário — aplicando as regras semânticas da definição dirigida pela sintaxe sobre a árvore.
Parte 4 — Atributos Herdados
📄 Arquivo de origem: 04 Atributos Herdados.doc
Questão 1. Dê a definição de atributos herdados.
Resposta: É o atributo cujo valor em um nó da árvore gramatical é definido em função do pai e/ou dos irmãos daquele nó — ao contrário do atributo sintetizado, que é calculado a partir dos filhos.
Questão 2. Explique o princípio de funcionamento dos atributos herdados.
Resposta: Servem para propagar informação de contexto pela árvore, de cima para baixo ou lateralmente entre irmãos. No exemplo do texto (D → T L), o tipo determinado por T é herdado por L através da regra L.in := T.tipo, distribuindo essa informação para cada identificador da lista via L → L₁, id e L → id.
Questão 3. Qual a finalidade de um compilador verificar se existem conversões, dentro de sua análise?
Resposta: Garantir que operações entre operandos de tipos diferentes, mas compatíveis, sejam tratadas corretamente — o compilador precisa saber se deve inserir uma coerção de tipo implícita (ex.: int para real) para gerar código correto, reportando erro apenas quando os tipos forem realmente incompatíveis.
Questão 4. Quais são os tipos de verificações estáticas? Descrevê-las.
• Verificação de tipos — relata erro se um operador for aplicado a um operando incompatível (ex.: somar array com função).
• Verificação do fluxo de controle — garante que comandos de desvio (como break) tenham uma construção envolvente válida para onde transferir o controle.
• Verificação de unicidade — garante que certos objetos sejam definidos exatamente uma vez (ex.: identificador declarado uma única vez em Pascal).
• Verificação relacionada a nomes — confere que o mesmo nome apareça corretamente em dois pontos exigidos (ex.: nome de laço no início e no fim, em ADA).
Questão 5. Faça o diagrama da posição do verificador de tipos.
Analisador Sintático
 │ (árvore sintática)
 ▼
 Verificador de Tipos
 │ (árvore sintática anotada)
 ▼Gerador de Código Intermediário
Resposta: O verificador de tipos fica entre a análise sintática e a geração de código intermediário: recebe a árvore sintática, anota/valida os tipos e repassa a árvore anotada adiante.
Questão 6. Qual a finalidade do uso de árvores sintáticas como forma de representação interna? Como os operadores e palavras-chave funcionam dentro desta estrutura?
Resposta: Permitem desacoplar a tradução da análise sintática — a árvore sintática (abstrata) é uma forma condensada da árvore gramatical, eliminando cadeias de produções desnecessárias. Nela, operadores e palavras-chave não aparecem como folhas: ficam associados ao nó interior (pai) que agruparia essas folhas na árvore gramatical completa (ex.: if-then-else como nó interno, com B, S1, S2 como filhos).
Questão 7. Desenvolver o Analisador Semântico, interagindo com as fases anteriores (léxico e sintático).
Resposta: Trata-se de um exercício prático de implementação (entrega do projeto do compilador). O Analisador Semântico deve percorrer a árvore sintática gerada pelas fases anteriores, aplicar as regras semânticas (tabelas de atributos sintetizados/herdados vistas nas questões anteriores) para verificar tipos e demais checagens estáticas, e produzir a árvore anotada para a fase de geração de código intermediário.