Como seu compilador (v2.

1) trata a seguinte entrada: { x = 3; print(x); ; }

Primeiramente o tokenizer irá atuar verificando se todos os tokens são válidos e, nesse
caso são. Após isso o parse entra em ação, ele primeiro espera receber um token “{” no
parse_block, como esse token existe ele é consumido e esse método chama o
parse_statement até que ele leia um token “}” ou “EOF” e , no último caso, lança um erro.
Os possíveis caminhos para o parse_statemen podem ser vistos no diagrama abaixo:

Como seu compilador (v2.1) trataria os erros das saguintes entradas:

{ print( 3 & 2 ); } ,{ print( 3 ** 2 ); } {print( y ) ;}

1. Logo no tokenizer lançaria uma exceção já que & não faz parte do alfabeto.

2. No parse_term, ao encontrar um token “ * ” ou “ / ” ele chama o factor que, recebe o

token “ * ” lança um erro já que não possui caminho possível no digrama sintático.

[Link]ós retornar a raíz e ao tentar fazer o evaluate de y lançaria um erro já que ele não foi
criado no symbol_table.

Explique alfabeto, cadeias, linguagens e gramáticas. Relacione os tópicos com o seu

compilador.

Um alfabeto é o conjunto de símbolos como letras(a-z), digitos(0-9), operadores(+,-,*,/),

simbolos especiais ({,},(,)) que são usados para formar cadeias em um compilador.
Cadeias são sequências desses símbolos, representando instruções no código-fonte,
como x = 5 + 3. Uma linguagem é o conjunto de todas as cadeias válidas de acordo
com as regras da sintaxe, ou seja, os programas que o compilador pode processar como if
(x > 10) { printf(“maior que 10”);}. Gramáticas definem as regras que descrevem como as
cadeias são estruturadas, usando símbolos terminais e não-terminais, além das
produções que orientam o parsing. No contexto do compilador, o Tokenizer identifica os
tokens a partir do alfabeto, o Parser usa a gramática para validar a estrutura das cadeias,
e a AST é construída conforme as regras da gramática, representando o código em uma
estrutura hierárquica para execução.
Seja a Linguagem: L = |am bn cn |m >= 0, n >= 0| Faça uma gramática livre de contexto
que representa L.

G = (V, §, P, A) L = {y, a, bc, abc, abbcc...}

§ = {a, b, c} i. p /lambda ) A -> B -> y E L

N = {A, B} ii. p /bbcc ) A -> B -> bBc -> bbBcc -> bbcc E L

V=§UN

P = A -> aA, A -> B, B -> bBc, B-> vazio

Faça um automato de pilha (PDA) que reconhece L .

Faça uma maquina de Turing que reconhece L .

Prove que (am bn cn) não é regular:

 Portanto, a linguagem L = (am bn cn) não é regular.

Dada a linguagem: L = {wcw | w E |a,b |*}

Ao analisa-la um individuo fez as seguintes afirmações:
 • Essa linguagem é claramente Livre de Contexto, pois precisa de memória para
contar o número de letras em w.
• Essa linguagem não é recursivamente Enumerável porque ela é livre de
contexto
• Eu sei que não é regular porque não consegui fazer nenhuma gramática que
representa a linguagem
• É possível fazer uma máquina de Turing para validar uma cadeia dessa
linguagem

Aponte os erros e acertos da análise acima. Justifique sua resposta.

1. Essa linguagem requer o armazenamento completo de www para verificar se a parte

após o símbolo ccc é igual ao prefixo. Isso exige um tipo de memória que uma gramática
sensível ao contexto ou uma máquina de Turing poderia oferecer, mas uma gramática
livre de contexto não consegue manipular esse tipo de comparação entre partes
separadas da cadeia.

2. Uma máquina de Turing pode ser construída para validar essa linguagem ao armazenar
o prefixo www e, posteriormente, comparar o sufixo com o prefixo. Portanto, LLL é
recursivamente enumerável.

3. A linguagem LLL não é regular porque uma linguagem regular não pode realizar
comparações entre duas partes diferentes de uma cadeia, como é exigido por LLL. O
Lema de Bombeamento poderia ser utilizado para mostrar formalmente que essa
linguagem não é regular.

4. Correto

Usado como base a versão v2.2 do compilador explique como implementaria um

operador que simplifica a operação de uma variável. A sintaxe é a mesma do python,
por exemplo: x += 1, mas posso usar qualquer aritimético

Primeira alteração seria alterar o tokenizer, onde adiccionaria os quatro novos tokens (+=,-
=, *=, /=). Após isso no assigment eu adicionaria mais essas condições conforme
estruturado abaixo:
Discorra sobre o determinismo e não determinismo para um reconhecedor de uma
linguagem livre de contexto

Determinismo: Em um reconhecedor determinístico, como o PDA determinístico, cada

estado tem no máximo uma transição possível para um dado símbolo de entrada e topo
da pilha. Isso torna o processo previsível e eficiente, já que apenas um caminho é seguido,
permitindo o reconhecimento de um subconjunto das CFLs, chamadas DCFLs (linguagens
livres de contexto determinísticas). Parsers como LL(1) e LR(1) são exemplos de
reconhecedores determinísticos usados em compiladores. Porém, o determinismo é
limitado, pois não consegue lidar com todas as linguagens livres de contexto,
especialmente as ambíguas.

Não Determinismo: Em um reconhecedor não determinístico, como o PDA não

determinístico, várias transições são possíveis para um mesmo estado e símbolo de
entrada. O autômato explora todas as possíveis execuções simultaneamente, o que torna
o não determinismo mais expressivo, permitindo o reconhecimento de todas as
linguagens livres de contexto. No entanto, essa flexibilidade vem com maior complexidade
computacional, pois é necessário considerar múltiplos caminhos de execução.

Crie uma linguagem L sobre o alfabeto §={a,b,c} que cumpra:

- Um número par da letra a; - Até três letras b; - Termina com a letra c
L pertence a qual classe de linguagens?

A linguagem LLL, definida pelas condições de conter um número par de letras 'a', no
máximo três letras 'b', e terminar com a letra 'c', pertence à classe das Linguagens
Regulares. Isso ocorre porque todas essas restrições podem ser reconhecidas por um
autômato finito. A exigência de um número par de 'a' pode ser facilmente tratada com uma
máquina de estados que alterna entre dois estados ao ler 'a'. O limite de até três letras 'b'
pode ser controlado por um número finito de estados, já que apenas até três ocorrências
são permitidas. Além disso, exigir que a cadeia termine com a letra 'c' é uma condição
simples que pode ser verificada por um autômato finito. Portanto, como essas
características podem ser descritas por um autômato finito, LLL é uma linguagem regular.
Um aluno afirmou na aula de logComp
- AST é a implementação da arvore de derivação do comp
- Existem linguagems que nao possuem reconhecedores
- Existem diversas expressões regulares e diversos AF que são equivalentes
- Power set e fecho de kleene representam a mesma operação

1. AST é a implementação da árvore de derivação do compilador

Falso. A AST (Abstract Syntax Tree), ou árvore sintática abstrata, não é
exatamente a árvore de derivação completa. A AST é uma representação
simplificada que omite detalhes sintáticos desnecessários, como parênteses ou
operadores que não afetam a lógica principal. A árvore de derivação completa, por
outro lado, inclui todas as regras de gramática usadas na derivação.
2. Existem linguagens que não possuem reconhecedores
Verdadeiro. Existem linguagens, como as linguagens não computáveis (por
exemplo, o Problema da Parada), que não podem ser reconhecidas por nenhuma
máquina ou algoritmo, ou seja, não possuem reconhecedores.
3. Existem diversas expressões regulares e diversos AF que são equivalentes
Verdadeiro. Uma linguagem regular pode ser descrita por múltiplas expressões
regulares diferentes, e também pode haver vários autômatos finitos (AF) que
 reconhecem a mesma linguagem. Assim, expressões regulares e autômatos finitos
equivalentes podem ser diferentes em forma, mas descrevem a mesma linguagem.
4. Power set e fecho de Kleene representam a mesma operação
Falso. O fecho de Kleene é uma operação que, aplicada a um conjunto de strings,
permite formar qualquer concatenação de zero ou mais strings do conjunto. Já o
power set é o conjunto de todos os subconjuntos de um conjunto, que é uma
operação de conjuntos, não relacionada diretamente com o fecho de Kleene.
Portanto, são operações diferentes.

Explique com detalhes quais erros que o compilador (v2.1) consegue detectar e
sinalizar (emitir para o usuário). Utilize exemplos.

i) Primeiro temos o tokenizer que vai separar e verificar se o as cadeias estão de

acordo com o alfabeto. Então o erro de um símbolo que não está presente é
emitido. Exemplo: {print(x)} -> erro pois “{” não esta no alfabeto
ii) Ocorre a análise sintática no Parser que é responsável por verificar se as cadeias
pertencem a gramática. Exemplo: x==2 -> erro pois n pode dois == seguidos
iii) Análise semântica que acontece quando chamamos a função evaluate(). Que é
sensível ao contexto, confere variáveis declaradas ou não. Ex: print(z) (z n existe)

Linguagens naturais não são iguais (em complexidade) às linguagens de

programação. Discorra tecnicamente sobre linguagens no contexto da disciplina

As linguagens naturais e as linguagens de programação diferem bastante em termos de

complexidade e formalidade. As linguagens naturais, como o português e o inglês, são
ambíguas, têm redundâncias e são altamente irregulares. Elas evoluem com o tempo, e
sua interpretação depende do contexto, o que dificulta a criação de sistemas que as
processem de maneira eficiente e exata. Por conta dessas características, é quase
impossível criar um sistema formal que capture toda a complexidade das linguagens
naturais. Para processar essas linguagens, são usados modelos computacionais
baseados em probabilidades e aprendizado de máquina.

Por outro lado, as linguagens de programação são projetadas para serem precisas e sem
ambiguidades. Elas possuem uma sintaxe e semântica bem definidas, o que permite que
sejam processadas de maneira determinística por máquinas como compiladores ou
interpretadores. Isso significa que, dada uma instrução em uma linguagem de
programação, a máquina pode executar exatamente o que foi especificado sem espaço
para interpretações múltiplas. Além disso, as linguagens de programação pertencem a
classes formais, como linguagens regulares e livres de contexto, que podem ser
descritas por autômatos finitos e gramáticas formais.

Em termos de complexidade, as linguagens naturais são muito mais difíceis de modelar e

interpretar automaticamente, enquanto as linguagens de programação são construídas
para serem processadas por máquinas de maneira eficiente e previsível.

Como você implementaria na versão (v2.1) o operador de incremento unitário de

variável (i++) segue o exemplo:
x=2
x++
print(x) imprimi 3
x++
print(x) imprimi 4
i) Primeiro passo seria atualizar o tokenizer para reconhecer a nova operação de
incremento unitário.
ii) Também temos que fazer um novo node para que possa ser feito o evaluate().
Então do node incrementa unitário deve ser acessado o valor atual da variável na
symbol table, incrementado 1 e após o incremento escrever o novo valor na
symbol table
iii) Alterar o diagrama do nosso compilador na fase statement

Oq são reconhecedores? explique detalhadamente

Reconhecedores são modelos computacionais utilizados para determinar se uma

determinada cadeia de símbolos (string) pertence ou não a uma linguagem específica.
Eles recebem uma entrada (string) e, com base nas regras da linguagem, decidem se a
cadeia é aceita ou rejeitada.

Os reconhecedores estão fortemente relacionados com as linguagens formais e

autômatos na Teoria da Computação. Cada classe de linguagem tem um tipo específico
de reconhecedor capaz de processá-la:

5. Autômato Finito Determinístico (AFD): Reconhece linguagens regulares. Ele lê

uma cadeia de símbolos de entrada e, ao terminar, decide se a cadeia pertence à
linguagem ou não. Funciona com um número finito de estados e transições entre
eles.
 6. Autômato com Pilha (AP): Reconhece linguagens livres de contexto. Ele usa uma
pilha para armazenar símbolos temporários, permitindo reconhecer estruturas
recursivas, como parênteses balanceados.
7. Máquina de Turing: Reconhece as linguagens recursivamente enumeráveis. É o
modelo mais poderoso de reconhecedor, podendo simular qualquer algoritmo. Ele
é capaz de processar qualquer linguagem computável.

Em resumo, um reconhecedor é qualquer mecanismo (como um autômato ou uma

máquina de Turing) que, dado uma cadeia de entrada, verifica se ela faz parte da
linguagem para a qual foi projetado.