Linguagens Formais e Compiladores
Classificado em Computação
Escrito em em 
português com um tamanho de 3,02 KB
Qual a relação entre problemas decidíveis e problemas indecidíveis com a teoria das linguagens formais?
Problemas decidíveis podem ser representados por linguagens do tipo 1 ou superior, enquanto os indecidíveis, apenas por linguagens do tipo 0.
Diferencie aspectos léxicos, sintáticos e semânticos, correlacione-os com a hierarquia de Chomsky e explique a diferença entre linguagens formais e naturais.
- Aspectos léxicos: servem para analisar a estrutura das palavras. Podemos utilizar uma GR (Gramática Regular) para analisá-los.
- Aspectos sintáticos: referem-se à estrutura das frases. Podemos verificá-los com uma GLC (Gramática Livre de Contexto).
- Aspectos semânticos: servem para analisar o sentido das frases. Aqui é onde diferenciamos linguagens formais (ex: linguagens de programação) e linguagens naturais (ex: português, inglês…). Apenas as formais podem ter os seus aspectos semânticos validados por uma GSC (Gramática Sensível ao Contexto).
Quais as funções básicas de cada fase de um compilador?
- Tabela de símbolos: guarda as variáveis utilizadas no programa.
- Tratador de erros: tem a função de corrigir alguns erros encontrados na fase de análise.
- Analisador léxico, sintático e semântico: verificar se o código-fonte está de acordo com os aspectos léxicos, sintáticos e semânticos da linguagem, respectivamente.
- Gerador de código intermediário: gera o código intermediário, transformando as instruções do código-fonte, que estão em uma linguagem específica, para um programa mais genérico.
- Otimizador de código: procura melhorar o código intermediário, eliminando determinadas ocorrências, como por exemplo: comandos invariantes ao loop e código inalcançável.
- Gerador de código objeto: transforma o código intermediário, já otimizado, para o código objeto.
Prove que as Gramáticas Sensíveis ao Contexto são recursivas.
Para provar que elas são recursivas, precisamos provar que existe um algoritmo que permita verificar se uma palavra w é gerada pela gramática.
Seja uma GSC G | S → ε ∉ P
Seja a palavra w | |w| = n
Seja TM o conjunto de palavras formadas pela linguagem após m derivações | M ≤ n
T0 = S
M = 1
TM = TM-1 ∪ { α | β → α, onde β ∈ TM-1 ∧ |α| ≤ n }
Se TM = TM-1
M = M+1
Calcule o novo TM
Senão, se w ∈ TM
então w ∈ L(G)
senão w ∉ L(G)