Ybadoo - Soluções em Software Livre
Turmas
1º Semestre de 2019

Questão 01

(Deitel, 2003) A linguagem de programação SIMPLE é uma linguagem simples, mas ainda poderosa e de alto nível, semelhante às versões iniciais da conhecida linguagem de programação BASIC. Cada instrução da linguagem de programação SIMPLE consiste em um número de linha e um comando da linguagem. Os números de linha devem aparecer em ordem crescente. Cada comando inicia com uma das seguintes palavras reservadas da linguagem de programação SIMPLE: rem, input, let, print, goto, if/goto ou end. Considere o programa escrito na linguagem de programação SIMPLE a seguir.

10 input n
15 if n <= 0 goto 65
20 let y = 0
25 let k = 0
30 if k >= n goto 75
35 let a = 2 * k
40 let b = a + 1
45 let y = y + b
50 print y
55 let k = k + 1
60 goto 30
65 let y = -1
70 print y
75 end

Caso a entrada fornecida pelo usuário seja 5, o programa apresentará como resposta:

a. 1 2 3 4 5

b. 1 2 4 8 16

c. 1 3 5 7 9

d. 1 3 6 10 15

e. 1 4 9 16 25

Questão 02

(Price, 2005) 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, d, g, h}, P, S)
P = {SACB | Cbb | Ba
A → da | BC
B → g | ε
C → h | ε}
  1. O conjunto FIRST(S) é {d, g, h, ε} e o conjunto FOLLOW(A) é {g, h, $}.
  2. O conjunto FIRST(S) é {a, b, d, g, h, ε} e o conjunto FOLLOW(C) é {b, g, h, $}.
  3. O conjunto FIRST(A) é {d, g, h, ε} e o conjunto FOLLOW(B) é {a, g, h, $}.
  4. O conjunto FIRST(A) é {d, g, h, ε} e o conjunto FOLLOW(C) é {a, b, g, h, $}.

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.

Questão 03

(Sebesta, 2000) O escopo de uma variável é a faixa de comandos em que a mesma é visível, ou seja, onde a variável pode ser referenciada por aquele comando. No escopo estático (ou léxico) o escopo de uma variável é determinado através da estrutura textual do programa, enquanto que no escopo dinâmico, o escopo de uma variável é determinado através da linha de execução do programa, sendo dependente, portanto da ordem de execução das rotinas.

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

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 sub1; sub1 chama sub3 e sub3 chama sub2, as variáveis visíveis durante a execução da última função chamada são y de sub1, x, b e c de sub2, a de sub3 e z de Test.
  2. Caso a sequência de chamada seja main chama sub3; sub3 chama sub4 e sub4 chama sub1, as variáveis visíveis durante a execução da última função chamada são x, y e c de sub1, b de sub3 e a e z de sub4.
  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 e c de sub1, b de sub2, y e z de sub4 e a de main.
  4. Caso a sequência de chamada seja main chama sub1; sub1 chama sub2 e sub2 chama sub3, as variáveis visíveis durante a execução da última função chamada são y de sub1, x e c de sub2, a, b e z de sub3.

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.

Questão 04

(Ramos, 2009) Analise as assertivas apresentadas a seguir:

  1. Análise descendente, também conhecida como top-down, é aquela em que o reconhecedor inicia os seus movimentos na raiz da gramática e evolui até a cadeia de entrada (em termos de árvore, é aquela em que a árvore é montada de cima para baixo).
  2. Uma das tarefas do analisador sintático é reconhecer e descartar separadores (espaços em branco, tabulações, mudanças de linhas e comentários) que possam ocorrer entre os tokens.
  3. O analisador sintático descendente recursivo com retrocesso emprega uma análise não-determinística, operando por tentativa e erro. Erros na cadeia de entrada são apontados somente depois de esgotadas todas as possibilidades de movimentação.
  4. Linguagem de montagem e linguagem de máquina são ambas linguagens de baixo nível, e por isso compartilham praticamente as mesmas características. A única diferença é que a linguagem de máquina utiliza mnemônicos para melhorar um pouco a legibilidade dos programas, ao passo que a linguagem de montagem utiliza apenas os códigos numéricos que são interpretados pela máquina-alvo diretamente.

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.

Questão 05

(Ricarte, 2008) 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 para a gramática livre de contexto G, reapresentada a seguir:

G = ({D, T, L, X}, {a, b, c, int, real, char, ',', ;}, P, D)
P = {DTL; | TL;D
T → int | real | char
LX | X,L
X → a | b | c}

Eliminação de Recursividade à Esquerda e da Fatoração à Esquerda

G = ({A, B, C, D, E, F}, {a, b, c, int, real, char, ',', ;}, P, A)
P = {ACD;B
BA | ε
C → int | real | char
DFE
E → ,D | ε
F → a | b | c}

Conjuntos FIRST(α) e FOLLOW(A)

FIRST(A) = {int, real, char}
FIRST(B) = {int, real, char, ε}
FIRST(C) = {int, real, char}
FIRST(D) = {a, b, c}
FIRST(E) = {',', ε}
FIRST(F) = {a, b, c}
FOLLOW(A) = {$}
FOLLOW(B) = {$}
FOLLOW(C) = {a, b, c}
FOLLOW(D) = {;}
FOLLOW(E) = {;}
FOLLOW(F) = {',', ;}

Tabela de Análise Preditiva

Tabela de análise preditiva da gramática G
 abcintrealchar,;$
A   ACD;BACD;BACD;B   
B   BABABA  B → ε
C   C → intC → realC → char   
DDFEDFEDFE      
E      E → ,DE → ε 
FF → aF → bF → c      

Questão 06

(Ricarte, 2008) 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 para o reconhecimento da entrada int a, b; real c;, considerando a tabela M obtida na Questão 05.

Movimentos do analisador preditivo tabular para int a, b; real c;
PilhaEntradaDerivação
$ Aint a, b; real c; $ACD;B
$ B ; D Cint a, b; real c; $C → int
$ B ; D intint a, b; real c; $ 
$ B ; Da, b; real c; $DFE
$ B ; E Fa, b; real c; $F → a
$ B ; E aa, b; real c; $ 
$ B ; E, b; real c; $E → ,D
$ B ; D ,, b; real c; $ 
$ B ; Db; real c; $DFE
$ B ; E Fb; real c; $F → b
$ B ; E bb; real c; $ 
$ B ; E; real c; $E → ε
$ B ;; real c; $ 
$ Breal c; $BA
$ Areal c; $ACD;B
$ B ; D Creal c; $C → real
$ B ; D realreal c; $ 
$ B ; Dc; $DFE
$ B ; E Fc; $F → c
$ B ; E cc; $ 
$ B ; E; $E → ε
$ B ;; $ 
$ B$B → ε
$$aceita

Questão 07

(Price, 2005) 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 "x";"x".

G = ({A, B, C}, {x, ;, "}, P, A)
P = {AB | B;A
B → "C"
C → x}
Tabela de análise preditiva
 x;"$
x >>>
;<><>
"<><>
$<<<aceita
Movimentos do analisador de precedência de operadores para "x";"x"
PilhaRelaçãoEntradaAçãoHandle
$<"x";"x"$empilha " 
$ "<x";"x"$empilha x 
$ " x>";"x"$reduzC → x
$ " A<";"x"$empilha " 
$ " A ">;"x"$reduzB → "C"
$ A<;"x"$empilha ; 
$ A ;<"x"$empilha " 
$ A ; "<x"$empilha x 
$ A ; " x>"$reduzC → x
$ A ; " A<"$empilha " 
$ A ; " A ">$reduzB → "C"
$ A ; A>$reduzAB;A
$ Aaceita$  

Questão 08

Para o desenvolvimento do compilador para a linguagem de programação SIMPLE, é necessário a elaboração de sua gramática livre de contexto, que servirá de base para a implementação do analisador sintático (descendente ou ascendente). Apresente a gramática livre de contexto, empregada por você, no desenvolvimento do analisar sintático da linguagem de programação SIMPLE. Lembre-se de reconhecer todas as regras sintáticas requeridas pela linguagem.

G = ({PROGRAM, COMMAND, EXPRESSION, OPERATOR, CONDITIONAL, RELATIONAL, ITEM, INTEGER, LABEL, DIGIT, VARIABLE}, {lf, etf, +, -, /, *, =, !, <, >, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z}, P, PROGRAM)
P = { PROGRAM → PROGRAM LABEL COMMAND lf | LABEL COMMAND lf | lf | etf
COMMAND → input VARIABLE | print VARIABLE | rem | if CONDITIONAL goto LABEL | let VARIABLE = EXPRESSION | goto LABEL | end
EXPRESSION → ITEM OPERATOR ITEM | ITEM
OPERATOR → + | - | / | *
CONDITIONAL → ITEM RELATIONAL ITEM
RELATIONAL → == | != | > | < | >= | <=
ITEM → VARIABLE | INTEGER
INTEGER → - LABEL | LABEL
LABEL → LABEL DIGIT | DIGIT
DIGIT → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
VARIABLE → a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z }