LFA - Lista de exercicios

Prévia do material em texto

Universidade Paulista (UNIP) 
Ciência da Computação 
Linguagens Formais e Autômatos 
Prof. Nelson Batista Leitão Neto 
Aluno: Matheus Aloisio Caetano de Brito Neves 
RA: N1480F-2 
 
 
Exercícios 01: 
 
1) O que vem a ser um compilador, dentro de suas características predominantes? Dê 
exemplos e faça uma simulação. 
R. Simplificando, um compilador é um programa que lê um programa escrito em uma 
linguagem - a linguagem fonte - e a traduz em um programa equivalente em outra 
linguagem - a linguagem alvo. Um exemplo de compilador é o Android Studio que traduz 
instantaneamente a linguagem. 
 
2) Como se divide um compilador? Explique cada uma delas. A geração de Árvore Sintática 
é feita em qual das etapas? Como é executada? 
R. Existem duas partes na compilação: a ANÁLISE e a SÍNTESE: 
ANÁLISE: Divide o programa fonte nas partes constituintes e cria uma representação 
intermediária. 
SÍNTESE: Constrói o programa objeto desejado, a partir da representação intermediária. 
A geração de Árvore Sintática é feita na Análise. as operações implicadas pelo programa 
fonte são determinadas e registradas numa estrutura hierárquica. 
 
3) Quais são as 4 ferramentas que manipulam programas fontes? Explique cada uma delas. 
R. EDITORES DE ESTRUTURAS - Recebe como entrada um conjunto de comandos 
para construir um programa fonte. 
PRETTY PRINTERS (“impressoras bonitas”)- Analisa um programa e o imprime numa 
forma em que a sua estrutura se torne claramente visível. 
VERIFICADORES ESTÁTICOS - Lê um programa, analisa-o e tenta descobrir erros 
potenciais, sem executá-lo. 
INTERPRETADORES - Em lugar de produzir um programa objeto como resultado da 
tradução, um interpretador realiza as operações especificadas pelo programa fonte. 
 
4) Dado as fases do Compilador, explique detalhadamente cada uma delas: 
• Análise Léxica; 
R. Nesta fase o arquivo de entrada é varrido caractere a caractere. 
Símbolos especiais (espaço em branco, símbolos de pontuação e new line) são 
utilizados para estabelecer os limites das palavras. 
Eliminação de espaços em branco e comentários. 
Durante a análise léxica, as palavras ou lexemas são guardados na tabela de 
símbolos e classificados de acordo com a linguagem, em palavras reservadas, 
comandos, variáveis e tipos básicos. 
Identificação de erros léxicos ("overflow" de campo numérico, uso de símbolos não 
pertencentes ao alfabeto da linguagem). 
 
• Análise sintática; 
R. É responsável pela verificação da boa formação dos comandos da linguagem, 
de acordo com as regras especificadas pela gramática da linguagem. 
Sentenças mal formadas, geralmente, interrompem o processo de compilação e 
são apresentadas como mensagens de erro. 
No fim da análise sintática, temos a representação do programa original de forma 
hierárquica, onde o programa é representado por uma árvore sintática. 
Uma árvore sintática é uma representação compactada de uma árvore PARSE na 
qual os operadores aparecem como nós interiores e os operandos de um operador 
são os filhos do nó daquele operador. 
Os erros de sintaxe são mais frequentes que os erros léxicos. 
Identificação e recuperação de erros de sintaxe. 
Construções léxicas não requerem recursão, enquanto as sintáticas sim. 
As gramáticas livres de contexto são uma formalização de regras recursivas que 
podem ser usadas para guiar a análise sintática. 
 
• Análise Semântica; 
R. A Análise semântica mais comum consiste na verificação da consistência de 
tipos dos operandos envolvidos em operações aritméticas ou dos parâmetros 
passados a procedimentos. 
O código intermediário deve ser fácil de produzir e fácil de traduzir no programa 
objeto. 
 
• Geração do Código Intermediário; 
R. O gerador de código intermediário será acionado quando o programa for 
analisado léxica, sintática e semanticamente, se encontrando correto do ponto de 
vista das três análises citadas. 
Neste ponto do projeto, entra a parte de análise e entramos no processo de 
síntese. 
Para essa geração, deve-se percorrer a árvore em profundidade (depth first), para 
que o código seja gerado das folhas para os nós. 
 
• Otimizador de Código; 
R. Reorganiza o código para um melhor desempenho, em tempo de execução. 
 
• Tratamento de Erros; 
R. Tipos de erros: léxicos, sintáticos, semânticos e lógicos. 
Os erros sintáticos são os mais frequentes. 
 
• Estratégias de recuperação de erros; 
R. Estratégias de recuperação de erros: 
1) PANIC MODE (modo de pânico) - O compilador descarta símbolos de entrada 
até encontrar um token de sincronização (“;" ou "end"). 
2) PHASE LEVEL (nível de fase) - O compilador tenta corrigir o erro encontrado, 
sem alterar o código fonte. (colocar um ";" onde não tem ou trocar ":" por ";"). 
3) PRODUÇÃO DE ERRO - Pode ser usado quando se sabe, de antemão, quais 
são os erros mais prováveis de acontecer; acrescenta-se à gramática, algumas 
produções que usam as construções erradas. 
4) CORREÇÃO GLOBAL - Tenta calcular a sequência mínima de mudanças para 
a correção de um erro. 
 
• Gerenciamento da Tabela de Símbolos; 
R. Uma função essencial do compilador é registrar os identificadores usados no 
programa fonte e coletar as informações sobre os seus diversos atributos de um 
identificador, tais como: (memória alocada, tipo, escopo). 
Uma tabela de símbolos é uma estrutura de dados contendo um registro para 
cada identificador, com os campos contendo os atributos do identificador. 
 
• Geração do Código; 
R. O gerador de código objeto é a última parte de um compilador. 
A tarefa central desse gerador de código é transformar uma especificação de 
código intermediário vinda da etapa anterior para uma especificação de código 
assembly, para poder ser executado num PC. 
 
• Geração do Módulo Executável; 
R. Compilação é o processo de tradução de um programa escrito em linguagem 
de alto nível para código em linguagem de máquina. Compilação é um processo 
análogo ao da montagem (verificação / análise do código fonte, resolução das 
referências de memória, reserva de espaço em memória e conversão para código 
de máquina binário). O que diferencia a compilação do processo de montagem é 
sua maior complexidade. No processo de montagem, há uma relação de 1:1, ou 
seja, cada instrução do código fonte resulta em uma instrução de máquina, 
enquanto na compilação a relação é múltipla, cada instrução do código fonte 
gerando várias instruções de máquina. 
Durante a compilação, o código fonte é analisado (análise léxica, sintática e 
semântica), é gerado um código intermediário e são construídas tabelas de 
símbolos, alocam-se as áreas de memória para variáveis e atribui-se os 
registradores a serem utilizados, e é finalmente gerado o código objeto em 
linguagem binária de máquina. Em alguns compiladores, é gerado um código 
intermediário em Assembly (que pode ser visualizado pelo programador) e que em 
seguida passa pelo montador para gerar finalmente o código objeto em linguagem 
de máquina. 
O código objeto pode ser absoluto (os endereços constantes são endereços reais 
de memória) ou realocável (os endereços são relativos, tendo como referência o 
início do programa, e os endereços reais de memória são definidos apenas em 
tempo de execução). 
 
• Edição de Ligações; 
R. Assim, o código objeto preparado pelo compilador em geral não é 
imediatamente executável, pois ainda existe código (as rotinas de biblioteca) a ser 
incorporado ao programa. 
A cada chamada de biblioteca encontrada no código fonte, o compilador precisará 
incluir uma chamada para a rotina e o endereço dos dados que devam ser 
passados para a rotina. 
A tarefa de examinar o código objeto, procurar as referências a rotinas de 
biblioteca (que constituem referências externas não resolvidas), buscar a rotina da 
biblioteca, substituir a chamada pelo código ("resolver as referências externas") e 
obter os parâmetros para incluí-los no código objeto é executada por um programa 
chamado Ligador (LinkEditor). O resultado da execução do Ligador é o código 
final pronto paraser executado pelo computador, chamado módulo de carga ou 
código executável. 
O módulo de carga, após testado e depurado (isto é, depois de resolvidos todos 
os erros, também chamados "bugs") é armazenado em memória de massa para 
ser executado quando necessário. 
O processo de compilação e ligação é executado apenas pelo programador na 
fase de desenvolvimento e não mais precisará ser executado pelo usuário, 
quando da execução do programa. 
 
Lista 1 
 
1) Escreva 5 palavras para cada um dos alfabetos abaixo: 
 
∑ = { GU, DA, BA, JA } 
R. Palavra sobre ∑: JABA, GUDADA, BADA,JAGU,GUJABADA 
∑ = { a, b,...,z, A, B,...,Z } 
R. Palavra sobre ∑: Matheus, Maria, AMORA, Aloisio, ALOISIO 
∑ = { 0, 1,..., 9 } 
R. Palavra sobre ∑: 18, 10, 23 ,01, 52 
∑ = { +, *, @, #, ?, ! } 
R. Palavra sobre ∑: @#, ?!, +@?, *!#, #+ 
∑ = { w, q, b, s } 
R. Palavra sobre ∑: wb, wq, ws, sb,sq 
∑ = { ~, $, %, ^, \ } 
R. Palavra sobre ∑: ~?, ^%, $\, ~$\, %? 
∑ = { t1, t2, t3, t4, t5, t6 } 
R. Palavra sobre ∑:t1t2, t4t3,t2t6, t5t1, t5t4 
∑ = { aa, bb, cc, dd,..., zz } 
R. Palavra sobre ∑: aabbcc, aaccdd, bbaavv, zzaa, mmtt 
∑ = { ab, cd, ef, gh, ij, lm, no, pq, rs, tu, vxz} 
R. Palavra sobre ∑: abcdef, abef, nolm, tuvxz, pqrs 
∑ = { xX, yY, zZ, wW, tT } 
R. Palavra sobre ∑: xXzZ, tTwW, yYzZwW, wWtT, zZyY 
∑ = { 10, 20, 30, 40, 50, 60 } 
R. Palavra sobre ∑: 1020,1050, 6050, 204050, 6030 
∑ = { 1a, 2b, 3c, 4d, 5e, 6f, 7g, 8h } 
R. Palavra sobre ∑: 1a6f, 2b7g,8h5e2b,4d3c, 7g8h3c 
∑ = { V,F,X,W } 
R. Palavra sobre ∑: VF,XW, VW,FXW, VFXW 
Ø = { A, B, CC } 
R. Palavra sobre Ø: AB, BA, ACC,CCAB,BACC 
Y = { Maria, Joao, Jose, Sonia } 
R. Palavra sobre Y: MariaJoao, JoseSonia, SoniaMaria, JoaoMaria, JoseMariaJoao 
 
 
2) Dado ∑ = {a, b}, escreva: 
Todas as palavras possíveis sobre ∑ de comprimento 1 
R. |a|, |b| 
Todas as palavras possíveis sobre ∑ de comprimento 2 
R. |ab|, |ba|, |aa|, |bb| 
Uma palavra qualquer sobre o ∑ de comprimento 15 = 
R. |ababaabbaabbaab| 
Duas palavras quaisquer sobre o ∑ de comprimento 7 
R. |abbaaba|, |baabbab| 
Três palavras quaisquer sobre o ∑ de comprimento 5 
R. Palavra sobre ∑: abbab, baaba, bbbabb 
 
 
3) Dado ∑ = { dó, ré, mi, fá, sol, lá, si }, determine o comprimento da palavra: 
a) | ré | = 1 
b) | dórémifá | = 4 
c) | milámilámilámilá | = 8 
d) | solsisollásol | = 5 
e) | solsifámidórélá | = 7 
f) | solsolsol | = 3 
g) | miréfamirésolmirésimirélámiré | = 14 
 
LISTA 02 
 
 
1) Dado ∑ = { a,b } , x = aabbb, y = bbbaa e z = abab palavras sobre ∑, escreva: 
a) yε 
bbbaa 
b) xyy 
aabbbbbbaabbbaa 
c) xxx 
aabbbaabbbaabbb 
d) y3 
bbbaabbbaabbbaa 
e) xy2 
aabbbbbbaabbbaa 
f) y2εx2 
bbbaabbbaaaabbbaabbb 
g) xzy 
aabbbababbbbaa 
h) zxy 
ababaabbbbbbaa 
i) zεx2 
ababaabbbaabbb 
j)zzx 
ababaaabbb 
l) yzx2 
bbbaaababaabbbaabbb 
m)z4 
abababababababab 
n)z2x2y2 
ababababaabbbaabbbbbbaabbbaa 
o) z2x2y 
ababababaabbbaabbbbbbaa 
 
2) Dado ∑ = { a, b, c }, escreva: 
 
a)∑0 = { ε } 
 
b)∑1 = { a, b, c } 
 
c)∑2 = { a, b, c }{ a, b, c } = {aa,ab,ac,ba,bb,bc,ca,cb,cc} 
 
d)∑3 = { a, b, c }{ a, b, c }{ a, b, c } = { a, b, c }{aa,ab,ac,ba,bb,bc,ca,cb,cc} = 
{aaa,aab,aac,aba,abb,abc,aca,acb,acc,baa,bab,bac,bba,bbb,bbc,bca,bcb,bcc, 
caa,cab,cac,cba,cbb,cbc,cca,ccb,ccc } 
 
3) Dados as palavras x = wf, y = abab e z = vf, escreva o resultado da concatenação abaixo: 
 
a) xxy 
wfwfabab 
 
b) xyz 
wfababvf 
 
c) xzy 
wfvfabab 
 
d) z2y 
vfvfabab 
 
e) zεy3 
vfabababababab 
 
f) εyx 
ababwf 
 
g)x2y2z 
wfwfababababvf 
 
h)xy3x 
wfababababababwf 
 
4) Usando os alfabetos ∑ = { V,F } e Ø = { A, B, C } , determine os conjuntos abaixo: 
a) ∑0 ={ ε } 
 
b) ∑1 = { V,F } 
 
c) Ø2 = Ø Ø {A,B,C}{A,B,C}={AA,AB,AC,BA,BB,BC,CA,CB,CC} 
 
d) ∑2 = { V,F }{ V,F } = {VV,VF,FV,FF} 
 
e) ∑3 = { V,F }{ V,F }{ V,F } = { V,F }{VV,VF,FV,FF} ={ VVV,VVF,VFV,VFF, FVV,FVF,FFV,FFF } 
 
 
LISTA 03 
Exemplos: 
 
Dado ∑ = {a,b}, determinar as linguagens definidas pelas seguintes expressões regulares: 
 
a) a | b 
temos: L(a)={a} e L(b)={b} 
 
L(a | b) = L(a) U L(b) = { a } U { b } = {a,b} 
 
 
b) (a | b) (a | b) 
temos: L((a | b) (a | b)) = L(a | b) L(a | b) 
 
L((a | b) (a | b)) = {a,b} {a,b} = {aa, ab, ba, bb} 
 
c) a* 
temos: (L(a))* = L (a)* 
L(a)* = L(a)0 U L(a)1 U L(a)2 U L(a)3 U ... 
L(a)0 = { ε } 
L(a)1 = L(a) = {a} 
L(a)2 = L(a) L(a) = {a} {a} ={aa} 
L(a)3 = L(a)2L(a) = {aa} {a} = {aaa} 
L(a)* = { ε, a, aa, aaa, … } 
 
d) (a | b)2 
= L (a | b)2 = L(a | b) L(a | b) = {a,b}{a,b} = {aa, ab, ba, bb} idem letra “b” 
 
e) (a | b)* = 
temos: L( a | b)* = L(a | b)0 U L(a | b)1 U L(a | b)2 U L(a | b)3 U ... 
L(a | b)0 = { ε } 
L(a | b)1 = { a, b} 
L(a | b)2 = L( a | b ) L ( a | b) = { a,b } { a,b } = {aa, ab, ba, bb} 
L(a | b)3 = L( a | b)2 L( a | b) = {aa, ab, ba, bb } { a , b } = {aaa, aab, aba, abb, baa, bab, bba, 
bbb} 
 
L( a | b )* = { ε , a, b, aa, ab, ba, bb, aaa, ..., bbb, aaaa,...} 
 
f) (a | a*b) 
temos: L ( a | a*b) = L (a) | L(a*b) 
L (a) = { a } 
L (a*b) = L (a)* L(b) 
L(a)* = L(a)0 U L(a)1 U L(a)2 U L(a)3 U ... 
L(a)0 = { ε } 
L(a)1 = L(a) = {a} 
L(a)2 = L(a) L(a) = {a} {a} ={aa} 
L(a)3 = L(a)2L(a) = {aa} {a} = {aaa} 
L(a)* = { ε, a, aa, aaa, … } 
 
L(a*b) = { ε, a, aa, aaa, … }{b} 
L(a*b) = {b, ab, aab, aaab, ...} 
 
L(a | a*b) = {a} U {b, ab, aab, aaab, ...} = {a, b, ab, aab, aaab, ... } 
 
g) (a | b) a* 
temos: (L(a))* = L (a)* 
L(a)* = L(a)0 U L(a)1 U L(a)2 U L(a)3 U ... 
L(a)0 = { ε } 
L(a)1 = L(a) = {a} 
L(a)2 = L(a) L(a) = {a} {a} ={aa} 
L(a)3 = L(a)2L(a) = {aa} {a} = {aaa} 
L(a)* = { ε, a, aa, aaa, … } 
 
L(a) U L(b) = { a } U { b } = {a,b} 
 
L(a | b) a* = {a,b} { ε, a, aa, aaa, … } ={aε, aa, aaa, aaaa,... ,bε, ba, baa, baaa, … } 
 
h) b*a 
temos: (L(b))* = L (b)* 
L(b)* = L(b)0 U L(b)1 U L(b)2 U L(b)3 U ... 
L(b)0 = { ε } 
L(b)1 = L(b) = {b} 
L(b)2 = L(b) L(b) = {b} {b} ={bb} 
L(b)3 = L(b)2L(b) = {bb} {b} = {bbb} 
L(b)* = { ε, b, bb, bbb, … } 
L(a) = {a} 
Lb*a = { ε, b, bb, bbb, … }{a} = { εa, ba, bba, bbba, … } 
 
 
i) b+ a 
temos L(b+) e L(a) 
L (b+)= {b,bb,bbb,bbbb, ...} e L(a)={a} 
Lb+ a ={b,bb,bbb,bbbb, ...} {a} ={ba,bba,bbba,bbbba, ...} 
 
j) (a | b )+ 
temos: L( a | b)+ = L(a | b)1 U L(a | b)2 U L(a | b)3 U ... 
L(a | b)1 = { a, b} 
L(a | b)2 = L( a | b ) L ( a | b) = { a,b } { a,b } = {aa, ab, ba, bb} 
L(a | b)3 = L( a | b)2 L( a | b) = {aa, ab, ba, bb } { a , b } = {aaa, aab, aba, abb, baa, bab, bba, 
bbb} 
 
L( a | b )+ = { a, b, aa, ab, ba, bb, aaa, ..., bbb, aaaa,...} 
 
 
l) a ( a | b )* a 
temos: L( a | b)* = L(a | b)0 U L(a | b)1 U L(a | b)2 U L(a | b)3 U ... 
L(a | b)0 = { ε } 
L(a | b)1 = { a, b} 
L(a | b)2 = L( a | b ) L ( a | b) = { a,b } { a,b } = {aa, ab, ba, bb} 
L(a | b)3 = L( a | b)2 L( a | b) = {aa, ab, ba, bb } { a , b } = {aaa, aab, aba, abb, baa, bab, bba, 
bbb} 
 
L( a | b )* = { ε , a, b, aa, ab, ba, bb, aaa, ..., bbb, aaaa,...} 
 
La ={a} 
Então: {a} { ε , a, b, aa, ab, ba, bb, aaa, ..., bbb, aaaa,...} {a} = 
L a ( a | b )* a ={ aεa , aaa, aba, aaaa, aaba, abaa, abba, aaaaa, ..., abbba, aaaaaa,...} 
 
m) b ( a | b )+ b 
temos: L( a | b)+ = L(a | b)1 U L(a | b)2 U L(a | b)3 U ... 
L(a | b)1 = { a, b} 
L(a | b)2 = L( a | b ) L ( a | b) = { a,b } { a,b } = {aa, ab, ba, bb} 
L(a | b)3 = L( a | b)2 L( a | b) = {aa, ab, ba, bb } { a , b } = {aaa, aab, aba, abb, baa, bab, bba, 
bbb} 
 
L( a | b )+ = { a, b, aa, ab, ba, bb, aaa, ..., bbb, aaaa,...} 
Lb ={b} 
Então: {b}{ a, b, aa, ab, ba, bb, aaa, ..., bbb, aaaa,...}{b} 
L b ( a | b )+ b = { bab, bbb, baab, babb, bbab, bbbb, baaab, ..., bbbbb, baaaab,...} 
 
n) ab ( a | b )* 
temos: L( a | b)* = L(a | b)0 U L(a | b)1 U L(a | b)2 U L(a | b)3 U ... 
L(a | b)0 = { ε } 
L(a | b)1 = { a, b} 
L(a | b)2 = L( a | b ) L ( a | b) = { a,b } { a,b } = {aa, ab, ba, bb} 
L(a | b)3 = L( a | b)2 L( a | b) = {aa, ab, ba, bb } { a , b } = {aaa, aab, aba, abb, baa, bab, bba, 
bbb} 
 
L( a | b )* = { ε , a, b, aa, ab, ba, bb, aaa, ..., bbb, aaaa,...} 
Lab = Lab= {ab} 
Lab ( a | b )*={ab}{ ε , a, b, aa, ab, ba, bb, aaa, ..., bbb, aaaa,...} 
Lab ( a | b )*= { abε , aba, abb, abaa, abab, abba, abbb, abaaa, ..., abbbb, abaaaa,...} 
 
o) b+ ( a | b ) 
temos: L(a)={a} e L(b)={b} 
 
L(a | b) = L(a) U L(b) = { a } U { b } = {a,b} 
L(b)+ = {b, bb, bbb, … } 
Lb+ ( a | b ) = {b, bb, bbb, … }{a,b} 
Lb+ ( a | b ) = {ba,bba,bbba,... , bb,bbb,bbbb, ...} 
 
 
p) ( ( a* b ) | ( bab ) ) ( a | b ) 
temos ( a* b ) = L(a)* = { ε, a, aa, aaa, … } Lb ={b} 
(a*b)= { εb, ab, aab, aaab, … } 
Temos ( bab )= La ={a} Lb={b} La={a} 
(bab) = {a}{b}{a} = {aba} 
Temos (( a* b ) | ( bab )) = { εb, ab, aab, aaab, … } U {aba} 
Logo { εb, ab, aab, aaab, …,aba} 
Temos L(a)={a} e L(b)={b} 
L(a | b) = L(a) U L(b) = { a } U { b } = {a,b} 
Então =( ( a* b ) | ( bab ) ) ( a | b ) 
{ εb, ab, aab, aaab, …,aba}{a,b} 
{ εba, aba, aaba, aaaba, …,abaa, εbb, abb, aabb, aaabb, …,abab } 
 
 
q) ( ab ) ( a | b )* 
temos: L( a | b)* = L(a | b)0 U L(a | b)1 U L(a | b)2 U L(a | b)3 U ... 
L(a | b)0 = { ε } 
L(a | b)1 = { a, b} 
L(a | b)2 = L( a | b ) L ( a | b) = { a,b } { a,b } = {aa, ab, ba, bb} 
L(a | b)3 = L( a | b)2 L( a | b) = {aa, ab, ba, bb } { a , b } = {aaa, aab, aba, abb, baa, bab, bba, 
bbb} 
 
L( a | b )* = { ε , a, b, aa, ab, ba, bb, aaa, ..., bbb, aaaa,...} 
Lab = La ={a} Lb={b} 
Lab ( a | b )*= {a}{b}{ ε , a, b, aa, ab, ba, bb, aaa, ..., bbb, aaaa,...} 
Lab ( a | b )*= { aε , aa, ab, aaa, aab, aba, abb, aaaa, ..., abbb, aaaaa,..., bε , ba, bb, baa, bab, 
bba, bbb, baaa, ..., bbbb, baaaa,...}} 
 
 
r) a ( ba ) ( b | a )+ 
temos: L( a | b)+ = L(a | b)1 U L(a | b)2 U L(a | b)3 U ... 
L(a | b)1 = { a, b} 
L(a | b)2 = L( a | b ) L ( a | b) = { a,b } { a,b } = {aa, ab, ba, bb} 
L(a | b)3 = L( a | b)2 L( a | b) = {aa, ab, ba, bb } { a , b } = {aaa, aab, aba, abb, baa, bab, bba, 
bbb ...} 
Temos (ba)= Lb={b} e La ={a} 
L( ba ) ( b | a )+ = {b}{a}{aaa, aab, aba, abb, baa, bab, bba, bbb, ...} 
{baaa, baab, baba, babb, bbaa, bbab, bbba, bbbb, ... , aaaa, aaab, aaba, aabb, abaa, abab, 
abba, abbb, ...} 
Logo a ( ba ) ( b | a )+ = {a}{baaa, baab, baba, babb, bbaa, bbab, bbba, bbbb, ... , aaaa, aaab, 
aaba, aabb, abaa, abab, abba, abbb, ...} 
{abaaa, abaab, ababa, ababb, abbaa, abbab, abbba, abbbb, ... , aaaaa, aaaab, aaaba, aaabb, 
aabaa, aabab, aabba, aabbb, ...} 
 
Seja ∑1 = {a,b,...,z} e ∑2 = {0,1,...,9} os alfabetos sobre os quais foram definidos as linguagens 
L e D, respectivamente. Descreva as linguagens resultantes das seguintes operações 
realizadas sobre L e D: 
 
a) L+ D 
 
 
b) L ( L | D ) = 
 
c) D ( D | L ) 
 
 
 
 
 
 
LISTA 04 
 
1) Descreva o funcionamento do Analisador Léxico. 
R: Responsável por analisar o fluxo de entrada do compilador, que é o programa fonte, e 
retornar para o analisar sintático a sequência de tokens identificados, na forma da 
tupla (token,conteudo). 
2) Qual a funcionalidade do Analisador Sintático? 
R: Verificação da boa formação do comando. Esperamos que o analisador sintático 
relate quaisquer erros de quaisquer erros de sintaxe de uma forma inteligível. Deve também se 
recuperar dos erros que ocorram mais comumente, a fim de poder continuar processando o 
resto de sua entrada. 
3) Quais são os métodos mais usados para o desenvolvimento do Analisador Sintático? 
✓ R: Analisador Sintático Top-Down. 
 Constroem árvores do topo (raiz), para o fundo (folhas). 
✓ Analisador Sintático Botton-Up. 
Começam pelas folhas e trabalham a árvore acima até a raiz. Em ambos os casos, a 
entrada é varrida da esquerda para a direita, um símbolo de cada vez. 
4) Dentro do tratamento dos erros de sintaxe, quais são os níveis que podem conte-los? 
Explique cada um deles. 
R: Léxico: errar grafia de um identificador, palavra-chave ou operando. 
Sintático: expressão aritmética com parênteses não balanceados. 
Semântico: operando aplicado a um operando incompatível. 
Logico: chamada infinitamente recursiva. 
5) Explique como é feito e em que fase acontece esses tratamentos de erros de sintaxe. 
R: Na recuperação de erros, tenta-se colocar o analisador em um estado tal que o restante da 
sentença de entrada ainda possa ser analisado. Este processo pode envolver: a modificação da 
entrada (excluir tokens), a modificação da pilha, ou de ambos. 
6) Quais são as metas estabelecidas dentro do tratador de erros num analisador sintático? 
R: Deve relatar a presença de erros de forma clara, deve ser recuperar de cada erro 
suficientemente rápido a fim de se capaz de detectar erros subsequentes, não deve retardar o 
processamento de programas corretos. 
7) Descreva as estratégias de recuperação de erros: 
 a) Modalidade do desespero 
 Este é o método mais simples de implementar e pode ser usado pela maioria dos métodos 
de análise sintática. Ao descobrir um erro, o analisador sintático descarta símbolos de entrada, um de cada 
vez, até que seja encontrado um token pertencente a um conjunto designado de tokens de sincronização. A 
correção na modalidade do desespero, que frequentemente pula uma parte considerável da entrada sem 
verificá-la, procurando por erros adicionais, possui a vantagem da simplicidade e, diferentemente dos 
outros métodos a serem enfocados adiante, tem a garantia de não entrar num laço infinito. 
 b) Recuperação de Frases 
 Ao descobrir um erro, o analisador sintático pode realizar uma correção local na entrada 
restante. Isto é, pode substituir um prefixo da entrada remanescente por alguma cadeia que permita ao 
analisador seguir em frente. Correções locais típicas seriam substituir uma vírgula por ponto-e-vírgula, 
remover um ponto-e- vírgula estranho ou inserir um ausente. 
a) Produção de Erro 
Se tivéssemos uma boa idéia dos erros comuns que poderiam ser encontrados, poderíamos 
aumentar a gramática para a linguagem em exame com as produções que gerassem construções ilegais. 
Usamos, então, a gramática aumentada com essas produções de erro para construir um analisador 
sintático. Se uma produção de erro for usada pelo analisador, podemos gerar diagnósticos apropriados 
para indicar a construção ilegal que foi reconhecida na entrada. 
b) Correção Global 
Idealmente, gostaríamos que um compilador fizesse tão poucas mudanças quanto possível, 
ao processar uma cadeia de entrada ilegal. Existem algoritmos para escolher uma sequência mínima de 
mudanças de forma a se obter uma correção global de menor custo. Dadas uma cadeia de entrada 
incorreta x e uma gramática G, esses algoritmos irão encontrar uma árvore gramatical para uma cadeia 
relacionada y, de tal forma que as inserções, remoções e mudanças de tokens requeridas para 
transformar x em y sejam tão pequenas quanto possível. 
8) Descreva as partes de um Analisador Sintático. 
1 – TERMINAIS 
Símbolos básicos a partir dos quais a cadeia é formada. 
Ex.: if, then, else. 
2 – NÃO-TERMINAIS 
 Variáveis sintáticas que denotam cadeias de caracteres. 
Ex.: cmd, exp. 
3 – PRODUÇÃO 
 É a forma pela qual os terminais e os não-terminais podem ser combinados. 
4 – ESTADO DE PARTIDA (SENTENÇA) 
 Um não-terminal é distinguido como símbolo de partida, 
 então G = (T, NT, P, S). 
➢ SÍMBOLOS TERMINAIS 
a) Letra minúscula do inicio do alfabeto. 
b) . , ( ) + - * ... 
c) [id] [IF] [THEN]. 
➢ SÍMBOLOS NÃO-TERMINAIS 
c) Letras maiúsculas do alfabeto. 
d) Cadeias de terminais. 
e) Símbolo de partida (S). 
Ex.: ExPR → ExPr op exPr 
 ExPR → (ExPR) 
 ExPR → - ExPR 
 ExPR → id 
 OP → + 
 OP → * 
 OP → / 
 OP →  
 
TERMINAIS: id, +, -, *, /, , ( ). 
NÃO–TERMINAIS: ExPR e OP 
SÍMBOLO DE PARTIDA: ExPR. 
 
9) Resolver 3 exercícios do Módulo 1 e 3 exercícios do Módulo 2 de LFA, no sistema. do aluno 
on-line, no Portal da Unip. 
Módulo 1 
 
Módulo 2 
 
 
 
LISTA 05 – LFA – TRADUÇÃO DIRIGIDA PELA SINTAXE 
 
1)Dentro das produções e regras semânticas descritas no exemplo anterior, faça a 
implementação para que a calculadora de mesa também seja funcional para divisão e 
subtração;2) Agora, faça a representação da árvore gramatical para as seguintes expressões: 
 
o 5 * 4 + 7 
 F.val = 27 
 
 F.val = 20 T.val = 7 
 | | 
 F.val = 5 * T.val = 4 digito.lexval = 7 
 | | 
digito.lexval = 5 digito.lexval = 4 
 
Produção Regras Semânticas 
X → D n Imprimir (D. val) 
D → D1 + W D.val := D1.val + W.val 
D → W D.val := W.val 
W → W1 / G W.val := W1.val / W.val 
W → G W.val := G.val 
G → (D) G.val := D.val 
G → dígito G.val := dígito.lexval 
o 16 / 2 – 5 
 F.val = 3 
 
 F.val = 8 - T.val = 5 
 | | 
 F.val = 16 / T.val = 2 digito.lexval = 5 
 | | 
digito.lexval = 16 digito.lexval = 2 
 
o 6 * 8 + 9 / 3 
 
 F.val = 51 
 
 F.val = 48 + T.val = 3 
 | | 
 F.val = 6 * T.val = 8 W.val = 9 / T.val = 3 
 | | | | 
digito.lexval = 6 digito.lexval = 8 digito.lexval = 9 digito.lexval = 3 
 
o 18 / 6 – 2 * 1 
 F.val = 1 
 
 F.val = 3 - T.val = 2 
 | | 
 F.val = 18 / T.val = 6 W.val = 2 * T.val = 1 
 | | | 
digito.lexval = 18 digito.lexval = 6 digito.lexval = 2 digito.lexval = 1 
 
o 36 * 2 / 4 
 F.val = 18 
 
 F.val = 72 / T.val = 4 
 | | 
 F.val = 36 * T.val = 2 digito.lexval = 4 
 | | 
digito.lexval = 36 digito.lexval = 2 
 
 
 
 
o 20 – 10 / 2 + 4 
 F.val = 19 
 
 F.val = 15 + T.val = 4 
 | | 
 F.val = 20 - T.val = 5 dig.lexval = 4 
 
dig.lexval = 20 T.val = 10 / W.val = 2 
 | | 
 dig.lexval = 10 dig.lexval = 2 
 
 
3)Como são utilizados os atributos sintetizados? 
 
R: Estes são usados extensivamente na prática. Uma definição dirigida pela sintaxe que use 
exclusivamente atributos sintetizados é dita uma definição S-atribuida. Uma árvore gramatical 
para uma definição S-atribuida pode ser sempre anotada através da avaliação das regras 
semânticas para os atributos a cada nó, de baixo para cima, das folhas para raiz. 
 
4)Explique o principio de funcionamento completo da tradução dirigida pela sintaxe. 
 
R: Tradução dirigida pela sintaxe fundamentalmente funciona pela adição de ações às 
produções em uma gramática livre de contexto, resultando em uma Definição Dirigida pela 
Sintaxe. Ações são passos ou procedimentos que serão efetuados quando a produção for 
usada em uma derivação. Por convenção, colocam-se chaves ao redor de ações; as chaves 
forem necessárias como símbolos da gramática, utilizam-se aspas para diferenciar. Uma 
especificação de gramática incorporada com ações a serem executadas é chamada de 
esquema de tradução dirigida pela sintaxe (às vezes simplesmente 'esquema de tradução'). 
 
5)Como funciona o Analisador Semântico? 
R: A análise semântica percorre a árvore sintática relaciona os identificadores com 
seus dependentes de acordo com a estrutura hierárquica. 
Essa etapa também captura informações sobre o programa fonte para que as fases 
subsequentes gerarem o código objeto, um importante componente da análise 
semântica é a verificação de tipos, nela o compilador verifica se cada operador recebe 
os operandos permitidos e especificados na linguagem fonte. 
 
LISTA 06 
1-Dê a definição de atributos herdados. 
 
R: São convenientes para expressar construções de LPs em relação ao contexto em 
que aparecem. Bastante útil na verificação de tipos. Controlar se um identificador 
aparece do lado esquerdo (endereço) ou direito (valor) de uma atribuição 
 
2-Explique o princípio de funcionamento dos atributos herdados. 
 
R: Úteis para especificar dependência do contexto, por exemplo se um identificador 
aparece à esquerda ou direita de uma atribuição. 
 
 
3-Qual a finalidade de um compilador verificar se existem conversões, dentro de sua análise? 
 
R: Essa checagem, chamada de verificação estática, assegura que certos tipos de erro 
de programa serão detectados e reportados 
 
4-Quais são os tipos de verificações estáticas? Descrevê-las. 
 
R: Verificação de tipos: Um compilador deveria relatar um erro se um operador for 
aplicado a um operando incompatível. 
https://pt.wikipedia.org/wiki/Gram%C3%A1tica_livre_de_contexto
Verificação do fluxo de controle: os enunciados que fazem o fluxo de controle deixar 
uma construção precisam ter algum local onde transferir o controle. 
Ex.: um enunciado break em C faz com que o controle deixe o while, for ou switch 
envolvente mais interno; um erro ocorre se um tal enunciado envolvente não existir. 
 
Verificação de unicidade: Existem situações nas quais um objeto precisa ser definido 
exatamente uma vez. 
Ex.: em Pascal, um identificador precisa ser declarado univocamente (só admite uma 
interpretação), os rótulos precisam ser distintos, e os elementos num tipo escalar não 
podem ser repetidos. 
 
Verificação relacionada aos nomes: Algumas vezes, o mesmo nome precisa figurar 
duas ou mais vezes. 
Ex.: Na linguagem ADA, um laço ou bloco precisa ter um nome que apareça ao início e 
ao final da construção. O compilador precisa verificar se o mesmo nome é usado em 
ambos os locais. 
 
 
5-Faça o diagrama da posição do verificador de tipos. 
 
 
 
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? 
 
R: O uso de árvores sintáticas como forma de representação interna permite que a 
tradução seja desacoplada da análise sintática. Numa árvore sintática, os operadores e 
palavras-chave não figuram como folhas, mas, são associados ao nó interior que seria o 
pai daquelas folhas na arvore gramatical. Outra simplificação encontrada nas arvores 
sintáticas é que as cadeias de produções podem ser eliminadas.