Turmas - 2º Semestre de 2024
Turmas
2º Semestre de 2024

Desenvolva um programa na linguagem de programação SIMPLE, que apresente a sequência de Tribonacci, definida recursivamente pela fórmula F_n = F_n-1 + F_n-2 + F_n-3, sendo F₀ = 0, F₁ = 1 e F₂ = 1.

O valor de n será fornecido pelo usuário, devendo ser um valor inteiro maior ou igual a zero.

Por exemplo, caso o valor fornecido pelo usuário para n seja 6, o programa deverá apresentar como resposta a sequência de números 0 1 1 2 4 7 13.

Caso o usuário forneça um valor inválido para n, o programa deverá apresentar como resposta o valor -1.

10 input n
15 if n < 0 goto 75
20 let a = 0
25 let b = 1
30 let c = 1
35 print a
40 if n < 1 goto 85
45 let x = a + b
50 let a = b
55 let b = c
60 let c = c + x
65 let n = n - 1
70 goto 35
75 let a = -1
80 print a
85 end

Analisadores de precedência de operadores operam sobre a classe das gramáticas de operadores, ou seja, gramáticas que os não-terminais aparecem sempre separados por símbolos terminais e que as produções não derivam a palavra vazia. A análise de precedência de operadores é bastante eficiente e é aplicada, principalmente, no reconhecimento de expressões, como expressões aritméticas e lógicas. Considerando a tabela de precedência de operadores apresentada a seguir, apresente a sequência de movimentos para o reconhecimento da entrada a + b * c * d + e.

G = ({A, B, C}, {+,  *, a, b, c, d, e}, P, A)
P = {A → A+B | B
     B → B*C | C
     C → a | b | c | d | e}

Erros na consulta a matriz:

erro 1 - insere + na entrada e emite a mensagem: operador esperado.

Erros na redução do handle:

erro 2 - se + ou * definem um handle, verificar se existem variáveis em ambos os lados do operador. Em caso negativo, executar a redução e emitir a mensagem: falta expressão.

(Poscomp, 2022) Dada a gramática G = (V, T, P, S), onde P = {S ::= (S) S, S ::= ε}, encontre o reconhecedor para a linguagem gerada por G.

a. Expressão Regular.

b. Autômato Finito Determinístico.

c. Autômato Finito Não Determinístico.

d. Autômato de Pilha.

e. Nenhuma das anteriores.

Comentários:

Conforme a Hierarquia de Chomsky, Autômatos de Pilha são reconhecedores de Gramáticas Livre do Contexto. Autômatos Finitos são reconhecedores de Gramáticas Lineares, enquanto Expressões Regulares são geradores, não reconhecedores de sentenças.

Os métodos de Análise Preditiva Tabular e de Precedência de Operadores utilizam Autômatos de Pilha para realizarem o reconhecimento das sentenças de entrada.

Analise as seguintes assertivas, em relação à análise sintática no contexto da construções de compiladores para linguagens de programação.

1. O funcionamento do algoritmo de análise sintática ascendente (bottom-up) corresponde ao percurso da árvore sintática do programa a partir das folhas (representando os símbolos terminais da gramática que define a linguagem), até chegar à raiz (que representa a variável ou símbolo não terminal inicial da gramática.
2. O funcionamento do algoritmo de análise sintática descendente (top-down) corresponde ao percurso da árvore sintática do programa a partir das folhas (representando as variáveis ou símbolos não terminais da gramática que define a linguagem), até chegar à raiz (que representa a sequência de símbolos terminais da gramática.
3. Na construção de tabelas de análise de precedência de operadores, podem aparecer dois tipos de conflitos: a) quando não existe relação de precedência entre o terminal mais ao topo da pilha e o símbolo da entrada, e b) quando o analisador supõe a existência de um handle no topo da pilha, mas não existe produção com o lado direito correspondente.
4. Dada uma gramática a ser processada por um algoritmo de análise preditiva tabular, deve-se verificar se os lados direitos de qualquer par de regras dela não contêm prefixos não vazios em comum. Por exemplo, uma gramática com regras X → abBc e Y → ab não pode ser processada por um algoritmo de análise preditiva tabular, pois o prefixo ab aparece nos lados direitos de ambas as regras.

Quais das assertivas apresentadas estão corretas?

a. apenas as assertivas I e II.

b. apenas as assertivas I e III.

c. apenas as assertivas II e III.

d. apenas as assertivas II e IV.

e. apenas as assertivas III e IV.

Comentários:

Os algoritmos de análise sintática descendente (top-down) constroem a árvore de derivação a partir do símbolo inicial da gramática (raiz da árvore), fazendo a árvore crescer até atingir suas folhas (símbolos terminais ou palavra vazia).

A fatoração à esquerda permite eliminar a indecisão sobre qual produção aplicar quando duas ou mais produções iniciam com a mesma forma sentencial na mesma variável em análise. O processo é realizado individualmente para cada variável da gramática.

(Poscomp, 2023) Seja o alfabeto A = {b, k, z}. Expressões regulares sobre A são definidas (da forma habitual) como cadeias (strings) contendo símbolos do alfabeto dado pela união de A com o conjunto {(, ), *, |}. Assim:

• () e e, as quais denotam respectivamente a linguagem vazia e a linguagem que contém apenas a cadeia vazia.
• Cada símbolo do alfabeto é uma expressão regular, denotando a linguagem formada pelo símbolo.
• Dadas expressões regulares R, R1 e R2, notamos com R*, (R1|R2) e R1R2 as expressões regulares, representando, respectivamente, as operações de Estrela de Kleene (repetição), Escolha e Concatenação.

A notação R? é usada como abreviatura para (R|e), marcando que R é opcional. Sejam os tokens de uma certa linguagem definidos pelas expressões regulares sobre A a seguir:

Seja um analisador léxico que reconhece os tokens acima, procurando sempre casar a maior parte possível da entrada (maior prefixo possível). Caso a cadeia kkbzkbbkkb seja dada como entrada ao analisador léxico, qual será a sequência de tokens devolvida por ele?

a. T1 T3 T2 T3.

b. T1 T1 T3.

c. T2 T3.

d. T3 T2 T3.

e. T3 T3 T3.

Comentários:

Escopo é um contexto delimitante aos quais valores e expressões estão associados em uma linguagem de programação. O tipo de escopo utilizado pela linguagem de programação vai determinar quais tipos de entidades este pode conter e como estas são afetadas, em outras palavras, a sua semântica. Normalmente, o escopo é utilizado para definir o grau de ocultação da informação, isto é, a visibilidade e acessibilidade às variáveis em diferentes partes do programa. Considere o programa apresentado a seguir, escrito na linguagem de programação C.

int a = 10;

void xpto()
{
  printf("%d ", a);
}

int main()
{
  {
    int a = 20;
    {
      int a = 30;
      xpto();
      printf("%d ", a);
    }
    printf("%d ", a);
  }
  printf("%d ", a);
  return 0;
}

Considerando a utilização do escopo estático, assinale a alternativa que corresponde a saída apresentada ao final da execução do programa apresentado.

a. 10 30 20 10.

b. 10 30 20 20.

c. 30 30 20 10.

d. 30 30 20 20.

e. 30 30 30 30.

Um analisador sintático preditivo sem recursão pode ser construído mantendo uma pilha explicitamente, em vez de implicitamente, via chamadas recursivas. O analisador é dirigido por um programa que considera X, o símbolo no topo da pilha, e a, o símbolo corrente da entrada. Se X é um não-terminal, o analisador escolhe uma produção-X consultando a entrada M[X, a] da tabela M de análise. Por outro lado, ele tenta fazer um casamento entre o terminal X no topo da pilha e o símbolo corrente a da entrada. Apresente a tabela da Análise Preditiva Tabular, com recuperação local de erros, da gramática a seguir.

G = ({A, B, C, D}, {a, ;, (, )}, P, A)
P = {A → (B) | a
     B → (B)D | aD
     C → ;AD
     D → C | ε}

Conjuntos FIRST(α) e FOLLOW(A)

FIRST(A) = {a, (}
FIRST(B) = {a, (}
FIRST(C) = {;}
FIRST(D) = {;, ε}

FOLLOW(A) = {;, ), $}
FOLLOW(B) = {)}
FOLLOW(C) = {)}
FOLLOW(D) = {)}

erro 1 - insere o token a na entrada e emite a mensagem: operando esperado.

erro 2 - insere o token ) na entrada e emite a mensagem: parêntese direito esperado.

erro 3 - retira o token da entrada e emite a mensagem: fim de arquivo encontrado.