Turmas - 1º Semestre de 2022
Turmas
1º Semestre de 2022

(vale 1,0 ponto) Desenvolva um programa na linguagem de programação SIMPLE, que apresente o máximo divisor comum (MDC) entre dois números. Por exemplo, caso os valores fornecidos pelo usuário sejam 18 e 60, o programa deverá apresentar como resposta o valor 6. Caso o usuário forneça valores inválidos, o programa deverá apresentar como resposta o valor -1.

10 input a
15 if a <= 0 goto 55
20 input b
25 if b <= 0 goto 55
30 if b == 0 goto 60
35 let r = a % b
40 let a = b
45 let b = r
50 goto 30
55 let a = -1
60 print a
65 end

(vale 1,0 ponto) A construção de analisadores descendentes é auxiliada por duas funções, denominadas FIRST e FOLLOW, associadas a uma gramática G. Durante a análise descendente, as funções FIRST e FOLLOW permitem escolher qual produção deverá ser aplicada, com base no próximo símbolo de entrada. Considerando a gramática livre de contexto G, analise as assertivas a seguir:

G = ({S, A, B, C}, {a, b, c, d}, P, S)
P = {S → AC | CdB | Ba
     A → aA | BC
     B → bB | CB | ε
     C → cC | ε}

1. O conjunto FIRST(S) é {a, b, c, d, ε} e o conjunto FOLLOW(C) é {a, b, c, d, $}.
2. O conjunto FIRST(A) é {a, b, c} e o conjunto FOLLOW(B) é {a, c, $}.
3. O conjunto FIRST(B) é {b, c, ε} e o conjunto FOLLOW(A) é {c, $}.
4. O conjunto FIRST(A) é {a, b, c, ε} e o conjunto FOLLOW(C) é {a, c, d, $}.

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.

(vale 1,0 ponto) Uma gramática possui recursão à esquerda se ela tiver um não-terminal A tal que exista uma derivação A →⁺ Aα para alguma cadeia α. Os métodos de análise descendentes não podem tratar gramáticas com recursão à esquerda, de modo que uma transformação é necessária para eliminar essa recursão. A fatoração à esquerda é uma transformação da gramática útil na produção de gramáticas adequadas para um reconhecedor sintático preditivo, ou descendente. Quando a escolha entre duas ou mais alternativas das produções-A não é clara, ou seja, elas começam com a mesma forma sentencial, podemos reescrever essas produções para adiar a decisão até que tenhamos lido uma cadeia da entrada longa o suficiente para tomarmos a decisão correta. Analise as assertivas a seguir sobre as transformações de gramáticas livre de contexto.

1. A fatoração à esquerda das produções

   B → xAB | CA | xB

   gera as produções

   B  → xB₁ | CA
   B₁ → AB | B

2. A fatoração à esquerda das produções

   C → xy | xDB

   gera as produções

   C  → xC₁
   C₁ → y | DB | ε

3. A eliminação da recursão à esquerda das produções

   B → a | BC | DC

   gera as produções

   B  → a | DC | aB₁ | DCB₁
   B₁ → C | CB₁

4. A eliminação da recursão à esquerda das produções

   A → BA | BAA | b | bA
   B → b | AA | a

   gera as produções

   A → b | BA | bA | BAA
   B → b | bA | bAA | BAA | BAAA | a

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.

(vale 1,0 ponto) Considere o pseudoprograma apresentado a seguir, escrito na linguagem de programação Java.

public class Test {
  public void sub1() { int a, y, z, w; }
  public void sub2() { int a, b, z, w; }
  public void sub3() { int a, b, c, w; }
  public void sub4() { int a, b, c, d; }
  public static void main(String[] args) { int x, y, z, w; }
}

Supondo que o pseudoprograma apresentado utilize o escopo dinâmico, considere as assertivas a seguir:

1. Caso a sequência de chamada seja main chama sub3; sub3 chama sub4 e sub4 chama sub2, as variáveis visíveis durante a execução da última função chamada são x e y de main, a, b, z e w de sub2 e c e d de sub4.
2. Caso a sequência de chamada seja main chama sub4; sub4 chama sub1 e sub1 chama sub3, as variáveis visíveis durante a execução da última função chamada são x de main, y e z de sub1 e a, b, c e w de sub3.
3. Caso a sequência de chamada seja main chama sub2; sub2 chama sub1 e sub1 chama sub4, as variáveis visíveis durante a execução da última função chamada são x de main, y e z de sub1, w de sub2 e a, b, c e d de sub4.
4. Caso a sequência de chamada seja main chama sub1; sub1 chama sub4 e sub4 chama sub2, as variáveis visíveis durante a execução da última função chamada são x de main, y de sub1, a, b, z e w de sub2 e c e d de sub4.

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 I e IV.

d. apenas as assertivas II e III.

e. apenas as assertivas II e IV.

(vale 1,0 ponto) 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 ⊕ d) e.

G = ({A, B, C, D, E, F}, {∨, ⊕, &, (, ), a, b, c, d, e}, P, A)
P = {A → B ∨ A | B
     B → C ⊕ B | C
     C → D & C | D
     D → ( A ) | E
     E → a | b | c | d | e}

Erros na consulta a matriz:

erro 1 - empilha ) e emite a mensagem: falta de parêntese à direita.

erro 2 - insere ∨ na entrada e emite a mensagem: operador esperado.

erro 3 - descarta ) da entrada e emite a mensagem: parêntese direito ilegal.

Erros na redução do handle:

erro 4 - 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.

erro 5 - se o par ( ) deve ser reduzido, verificar se existe uma variável entre os parênteses. Em caso negativo, executar a redução e emitir a mensagem: expressão nula entre parênteses.

(vale 1,0 ponto) 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 sequência de movimentos, com recuperação de erros em modo pânico, da entrada x y z + x z / * - y +, considerando a tabela M apresentada a seguir.

(vale 1,0 ponto) Os analisadores sintáticos preditivos, ou seja, os analisadores de descida recursiva que não precisam de retrocesso, podem ser construídos para uma classe de gramáticas chamada LL(1). O primeiro L em LL(1) significa que a cadeia de entrada é lida da esquerda para a direita, o segundo L representa uma derivação mais à esquerda e o 1 pelo uso de um símbolo à frente na entrada utilizado em cada passo para tomar as decisões quanto à ação de análise. Apresente a tabela M de análise preditiva tabular, com recuperação de erros em modo pânico, para a gramática livre de contexto G, apresentada a seguir:

G = ({A, B, C, D, E, F, G}, {x, y, z}, P, A)
P = {A → xB
     B → DC
     C → xC | yC | zC | ε
     D → yE
     E → GF
     F → xF | yF | zF | ε
     G → z}

Eliminação de Recursividade à Esquerda

G = ({A, B, C, D, E, F, G}, {x, y, z}, P, A)
P = {A → xB
     B → DC
     C → xC | yC | zC | ε
     D → yE
     E → GF
     F → xF | yF | zF | ε
     G → z}

Fatoração à Esquerda

G = ({A, B, C, D, E, F, G}, {x, y, z}, P, A)
P = {A → xB
     B → DC
     C → xC | yC | zC | ε
     D → yE
     E → GF
     F → xF | yF | zF | ε
     G → z}

Conjuntos FIRST(α) e FOLLOW(A)

FIRST(A) = {x}
FIRST(B) = {y}
FIRST(C) = {x, y, z, ε}
FIRST(D) = {y}
FIRST(E) = {z}
FIRST(F) = {x, y, z, ε}
FIRST(G) = {z}

FOLLOW(A) = {$}
FOLLOW(B) = {$}
FOLLOW(C) = {$}
FOLLOW(D) = {x, y, z, $}
FOLLOW(E) = {x, y, z, $}
FOLLOW(F) = {x, y, z, $}
FOLLOW(G) = {x, y, z, $}