Resumo Fundamentos em Linguagem e Teoria da Computação

Prévia do material em texto

Resumo Fundamentos em Linguagem e Teoria da Computação 
1. Compiladores e linguagens de programação 
 
 
1 – O que é um compilador? 
R: É constituído internamente por passos ou fases. Cada fase comunicasse com a seguinte através de uma 
linguagem intermediária adequada. 
 
2-Quais e o que fazem as fases que constituem o compilador? 
R:O compilador é constituído de 2 fases: Fase de Análise(Front-End) que é constituída de Analisador Léxico que 
verifica como as palavras estão escritas(onde o programa fonte é lido), Analisador Sintático que verifica a ordem e 
a estrutura e Analisador Semântico que verifica o significa das palavras no código; e Fase de síntese(Back-End) 
que é constituída de Gerador de código Intermediário e Otimizador de código . 
 
3 – O que é Tabela de Literais e qual sua importância? 
R: Armazena constantes e cadeias de caracteres usados em um programa. Também é usada para construir 
endereços simbólicos para literais e definições de dados ao arquivo de código fonte. Ela é importante para reduzir 
o tamanho de um programa na memória, pois permite o reaproveitamento das constantes e das cadeias de 
caracteres. 
 
4 – O que é Tabela de Símbolos? 
R: É uma estrutura de dados (normalmente tabela de hashing, ou então árvore, lista, pilha) contendo um registro 
para cada nome e para seus atributos. 
 
5 – Como os erros são manipulados e tratados pelo compilador? 
R: Os erros estáticos (em tempo de compilação) devem ser reportados pelo compilador. É importante que ele 
gere mensagens de erro inteligíveis e conclua a compilação após cada erro. Cada fase requer um tratamento de 
erro diferente e qualquer fase analítica deve prosseguir em sua análise evitando a propagação do efeito do erro. 
 
6 – Como o programa fonte é lido pelo Analisador Léxico? 
R: O programa fonte é fornecido como uma sequencia de caracteres, as quais são organizadas como unidades 
significativas denominadas lexemas. Para cada lexema, é produzido, como saída, um token no formato: 
<nome_token, valor_atributo>, onde nome_token é um símbolo abstrato que será usado durante a análise 
sintática e valor_atributo aponta para uma entrada na Tabela de símbolos referente a esse token. 
 
7 – Qual a função do analisador léxico? 
R: Ler, caractere a caractere, o texto fonte, verificando se os caracteres lidos pertencem ao alfabeto da linguagem 
de programação, identificando tokens e desprezando comentários e brancos desnecessários. 
 
8 – O que são tokens e como podem ser representados? 
R: Os tokens constituem classes de símbolos tais como palavras reservadas, delimitadores, identificadores, etc, e 
podem ser representados, internamente, através do próprio símbolo(como no caso dos delimitadores, palavras 
reservadas,...) ou por um par ordenado(caso dos identificadores, por exemplo). 
 
9 – Cite outras duas funcionalidades do analisador léxico. 
R: Iniciar a Construção da Tabela de símbolos e de Literais. Enviar mensagens de erro caso identifique unidades 
léxicas não aceitas pela linguagem em questão. 
 
10 – Identifique quantos caracteres e quantos tokens há na expressão: 
a)a[index]=4+2; R: contem 13 caracteres e 9 tokens. 
A -> <id, 1> ; [ -> <[> ou <delin, 2>;index - > <id,3>; ] -> <]> ou <delin,4>;= -> <=>;4 -> <numero,5> ou <5>; + -> <+>; 
2 -> <numero,6>; ; -> <;> 
 
11- Como funciona o analisador sintático? 
R: Utiliza os primeiros componentes dos tokens produzidos pelo léxico para criar uma representação 
intermediaria tipo arvore, que mostra a estrutura gramatical da sequencia de tokens. Essa fase analisa a estrutura 
do programa : Determina os elementos estruturais do programa e seus relacionamentos, apresentando os 
resultados como uma árvore de análise sintática ou uma árvore sintática. 
 
12 – Como é representada uma árvore de análise sintática? 
R: Em uma árvore de análise sintática, os nós internos são rotulados pelos nomes das estruturas que elas 
representam e as folhas da árvore representam a sequencia de tokens. 
 
13 – Qual a função da árvore de análise sintática? 
R: É um recurso útil para visualizar a sintaxe de um programa(ou elemento de programa) e assim detectar erros 
sintáticos, identificando onde ocorre e o tipo de erro ocorrido. 
 
14 - Para que são usadas as gramáticas livres de contexto? 
R: São usadas para especificar a estrutura gramatical das linguagens de programação. 
 
15 – Qual a função da analise semântica? 
R: Verificar se as estruturas válidas do programa farão sentido durante a execução. Verifica se os aspectos 
semânticos do programa estão corretos; ou seja, se não existem incoerências quanto ao significado das 
construções utilizadas pelo programador. A analise semântica deve apontar os erros encontrados, bem como o 
tipo de erro e onde ocorre. 
 
16 – Quais tipos de incoerências são procurados pelo analisador semântico? 
R: Tipos de operandos incompatíveis com operadores, variáveis não declaradas, redeclaração de variáveis, 
chamadas de funções ou métodos com o número incorreto de parâmetros e comandos colocados fora de 
contexto. 
 
17 – Qual a função da Tabela de Símbolos? 
R: Na Tabela de Símbolos são armazenadas informações sobre as variáveis declaradas, funções, tipos de dados. 
Sem ela é impossível a validação semântica. 
 
18 – Quais as duas propriedades que um código intermediário deve ter? 
R: ser facilmente produzido e ser facilmente traduzido para a máquina alvo. 
 
19 – Qual a função do otimizador de código? 
R: Independente das arquiteturas de máquina, faz algumas transformações no código intermediário com o 
objetivo de produzir um código objeto melhor. Melhor pode significar mais rápido, código menor ou que 
consuma menos energia, por exemplo. 
 
20 – O que são compiladores otimizadores? 
R: São compiladores que exploram ao máximo as oportunidades de otimização. 
 
21 – Como funciona o Gerador de Código? 
R: Recebe como entrada uma representação intermediaria do programa fonte e o mapeia em uma linguagem 
objeto. Se a linguagem objeto for código de máquina de alguma arquitetura, devem ser selecionados os 
registradores ou localizações de memória para cada uma das variáveis usadas pelo programa. 
 
22 – Qual a diferença do código intermediário e do código objeto final? 
R: O intermediário não especifica detalhes tais como: quais registradores são usados, quais endereços de 
memória serão referenciados... 
 
 
 
2. Descrição de uma linguagem de programação 
 
Cadeias que pertencem á linguagem em questão são chamadas de SENTENÇAS. 
Gramática – Conjunto de regras que, quando seguidas, produzirá uma sentença válida na linguagem. Consiste em 
4 objetos: 
*Alfabeto (Σ), finito e não vazio. Elementos: terminais. Representão: letras minúsculas. 
*Conjunto N, finito e não vazio, de símbolos diferentes dos terminais. Representação: letras maiúsculas. 
*Um elemento S – elemento inicial 
*Conjunto P de regras de produção (ou substituição) 
Forma Sentencial – Qualquer cadeia (inclusive vazia) de símbolos que pertença a união do alfabeto com o 
conjunto dos não terminais(N). 
 L(σ) gerada por σ é a coleção de todas as cadeias possíveis de terminais (ou seja, sentenças) que são geradas a 
partir do símbolo inicial. 
Gramáticas Equivalentes – duas gramáticas que geram a mesma linguagem. Obs: uma mesma linguagem pode 
ser gerada por mais de uma gramática, mas uma gramática gera apenas uma linguagem. 
Gramáticas Ambíguas – existem duas árvores de derivação distintas para a mesma sentença. 
 
Tipo Classe de Linguagem Modelo de Gramática Modelo de Reconhecedor 
0 LRE Irrestrita Maquina de Turing(MT) 
1 LSC Sensível ao contexto MT com fita limitada 
2 LLC Livre de Contexto Autômato com pilha 
3 LRRegular Autômato finito 
LRE – Linguagens estritamente livres de contexto 
LSC – Linguagens estritamente sensíveis ao contexto 
LLC – Linguagens estritamente irrestritas (recursivamente inumeráveis) 
LR - Linguagens Regulares 
 
Autômatos finitos (AF) – São basicamente grafos, com algumas diferenças: 
*são reconhecedores: dizem sim ou não para cada possível cadeia de caractere. 
*são de 2 tipos: 
Deterministas – (AFD ou MEFD) para cada estado e para cada símbolo de seu alfabeto de entrada há exatamente 
1 aresta com esse símbolo saindo desse estado. 
MEFD – Máquina de Estado Finito Determinístico - são maquinas formadas por um número finito de estados, 
junto a um dispositivo de entrada, o qual lê, um por um(da esquerda para a direita), símbolos de uma cadeia de 
caracteres de entrada. É formada por: {Q, Σ,δ,Q0, F} 
Q – conjunto finito e não vazio de estados: {Q0, Q1, Q2...Qn} 
Σ – alfabeto de entrada 
Função de transição – (δ) regra que descreve o próximo estado para o qual a máquina se move. 
Q0 – estado inicial 
F – conjunto de estados finais (estados reconhecedores) 
Não Deterministas – (AFDN) não tem restrições sobre os rótulos de suas arestas. Quando a função de transição, 
para um dado estado e uma entrada, leva a mais de um estado como resultado.