Exercícios Capítulo 4 Paradigmas

Prévia do material em texto

Nome: Amanda Kelly Rodrigues Cândido
	Giovanna de Sousa Sampaio
	Giulianni dos Santos Oliveira
Professor: José Olímpio
PARADIGMAS DE LINGUAGENS DE PROGRAMAÇÃO
CAPÍTULO 4
1. Quais são as três razões pelas quais os analisadores sintáticos são baseados em
gramáticas?
O formalismo mais usado para descrição de sintaxe é a gramática livre de contexto, ou BNF. Usar BNF, de modo oposto ao uso de algumas descrições informais de sintaxe, tem ao menos três vantagens significativas. Primeiro, as descrições em BNF da sintaxe dos programas são claras e concisas, tanto para humanos quanto para os sistemas de software que as utilizam. Segundo a descrição em BNF pode ser usada como a base direta para o analisador sintático. Terceiro, implementações baseadas em BNF são relativamente fáceis de manter em função de sua modularidade.
2. Explique as três razões pelas quais a análise léxica é separada da análise sintática.
3. Defina lexema e token.
O analisador léxico coleta caracteres e os agrupa logicamente, atribuindo código internos aos agrupamentos de acordo com sua estrutura. Esses agrupamentos lógicos são chamados de lexemas, e os códigos internos para as categorias desses agrupamentos são chamados de tokens.
4. Quais são as tarefas primárias de um analisador léxico?
5. Descreva brevemente as três abordagens para a construção de um analisador
léxico.
1. Escrever uma descrição formal dos padrões de tokens da linguagem usando uma linguagem descritiva relacionada a expressões regulares 1. Essas descrições são usadas como entrada para uma ferramenta de software que gera automaticamente um analisador léxico.
2. Projetar um diagrama de transições de estado que descreva os padrões de tokens da linguagem e escrever um programa que implementa o diagrama.
3. Descrever um diagrama de transições de estado que descreva os padrões de tokens da linguagem e construir manualmente uma implementação dirigida por tabela do diagrama de estados.
6. O que é um diagrama de transição de estados?
7. Por que são usadas classes de caracteres, em vez de caracteres individuais, para as
transições de letras e dígitos de um diagrama de estados de um analisador léxico?
Como dígitos específicos não são uma preocupação do analisador léxico, podemos construir um diagrama de estados muito mais compacto se definirmos uma classe de caracteres chamada DIGIT para dígitos e usarmos uma única transição em qualquer caractere nessa classe para um estado que coleta literais inteiros.
8. Quais são os dois objetivos distintos da análise sintática?
9. Descreva as diferenças entre analisadores sintáticos descendentes e ascendentes.
Um analisador sintático descendente percorre ou constrói uma árvore de análise sintática em pré ordem. Isso corresponde a uma derivação mais à esquerda. Já um analisador sintático ascendente constrói uma árvore de análise sintática comçando pelas folhas e progredindo em direção à raiz. Essa ordem de análise sintática corresponde ao inverso de uma derivação mais à direita.
10. Descreva o problema de análise sintática para um analisador sintático descendente.
11. Descreva o problema de análise sintática para um analisador sintático ascendente.
 análise sintática transforma um texto na entrada em uma estrutura de dados, em geral uma árvore, o que é conveniente para processamento posterior e captura a hierarquia implícita desta entrada. Através da análise léxica é obtido um grupo de tokens, para que o analisador sintático use um conjunto de regras para construir uma árvore sintática da estrutura.
Análise sintática ascendente, também chamada de bottom-up, o analisador pode iniciar com uma entrada de dados e tentar reescrevê-la até o símbolo inicial. Intuitivamente, o analisador tentar localizar os elementos mais básicos, e então elementos maiores que contêm os elementos mais básicos, e assim por diante. Exemplo: analisador sintático LR
12. Explique por que os compiladores usam algoritmos de análise sintática que funcionam em apenas um subconjunto de todas as gramáticas.
13. Por que as constantes nomeadas são usadas, em vez de números, para códigos de
tokens?
Como um forma de simplificar o diagrama de transição, os tokens são representados. Existem 10 caracteres que podem iniciar um lexema de literal inteiro. Isso iria requerer 10 transições a partir do estado inicial do diagrama de estados. Como dígitos específicos não são uma preocupação do analisador léxico, podemos construir um diagrama de estados muito mais compacto se definirmos uma classe de caracteres chamada DIGIT para dígitos e usarmos uma única transição em qualquer caractere nessa classe para um estado que coleta literais inteiros.
14. Descreva como um subprograma de análise sintática descendente recursiva é
escrito para uma regra com um único lado direito.
15. Explique as duas características das gramáticas que as proíbem de serem usadas
como a base para um analisador sintático descendente.
Duas características distintas das gramáticas previnem a construção de um analisador sintático descendente recursivo baseado na gramática. Uma delas é a recursão à esquerda. O processo de eliminar a recursão à esquerda direta de uma gramática é relativamente simples. O outro problema é detectado com o teste de disjunção par a par, que testa se um subprograma de análise sintática pode determinar qual lado direito está sendo analisado sintaticamente com base no próximo token de entrada.
16. O que é o conjunto FIRST para uma gramática e forma sentencial?
17. Descreva o teste de disjunção par a par.
Para cada não terminal, A, na gramática que tem mais de um lado direito, para cada par de regras, A → α i e A → α j, deve ser verdadeiro que FIRST(α i ) ∩ FIRST(α) = φ (A intersecção dos dois conjuntos, FIRST(α i ) e FIRST(α j ), deve ser vazia.)
18. O que é fatoração à esquerda?
19. O que é uma frase de uma forma sentencial?
β é uma frase da forma sentencial à direita γ se, e somente se, S =>* γ = α 1 Aα 2 =>+ α 1 βα 2
20. O que é uma frase simples de uma forma sentencial?
21. O que é o manipulador de uma forma sentencial?
β é o manipulador da forma sentencial direita γ = αβw se, e apenas se, S =>* rm αAw => rm αβw.
22. Qual é a máquina matemática em que os analisadores sintáticos descendentes e
ascendentes são baseados?
23. Descreva três vantagens dos analisadores sintáticos LR.
1. Eles podem ser construídos para todas as linguagens de programação.
2. Eles podem detectar erros de sintaxes o mais cedo possível em uma varredura da esquerda para a direita.
3. A classe de gramáticas LR é um superconjunto da classe analisável sintaticamente por analisadores LL.
24. Qual foi a descoberta de Knuth ao desenvolver a técnica de análise sintática LR?
25. Descreva o propósito da tabela ACTION de um analisador sintático LR.
O processo de deslocamento é simples: o próximo símbolo da entrada é inserido na pilha, com o símbolo de estado que é parte da especificação de deslocamento na tabela ACTION.
26. Descreva o propósito da tabela GOTO de um analisador sintático LR.
27. A recursão à esquerda é um problema para analisadores sintáticos LR?
Não, mas a recursão à esquerda causa um problema catastrófico para analisadores sintáticos LL.