Turmas - 2º Semestre de 2016
Turmas
2º Semestre de 2016

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 a
15 if a <= 0 goto 55
20 input b
25 let a = a - 1
30 if a == 0 goto 60
35 input c
40 if b <= c goto 25
45 let b = c
50 goto 25
55 let b = -1
60 print b
65 end

Caso os números de entrada fornecidos pelo usuário sejam 4, 5, 3, 1 e 2, o programa apresentará como resposta:

a. 1

b. 2

c. 3

d. 4

e. 5

(Price, 2005) Em geral, os tradutores de linguagens de programação (compiladores e interpretadores) são programas bastante complexos. Porém, devido à experiência acumulada ao longo dos anos e, principalmente, ao desenvolvimento de teorias relacionadas às tarefas de análise e síntese de programas, existe um consenso sobre a estrutura básica desses processadores. A figura a seguir apresenta a estrutura básica de um compilador.

Qual das seguintes opções apresenta corretamento o nome das tarefas desempenhadas pela estrutura básica do compilador apresentado.

a. 1) gerador de código intermediário; 2) analisador léxico; 3) analisador sintático; 4) analisador semântico; 5) otimizador de código; 6) gerador de código objeto; 7) tabelas auxiliares e 8) atendimento a erros.

b. 1) analisador léxico; 2) analisador sintático; 3) analisador semântico; 4) otimizador de código; 5) gerador de código intermediário; 6) gerador de código objeto; 7) atendimento a erros e 8) tabelas auxiliares.

c. 1) analisador léxico; 2) analisador sintático; 3) analisador semântico; 4) gerador de código intermediário; 5) gerador de código objeto; 6) otimizador de código; 7) tabelas auxiliares e 8) atendimento a erros.

d. 1) analisador léxico; 2) analisador sintático; 3) analisador semântico; 4) gerador de código intermediário; 5) otimizador de código; 6) gerador de código objeto; 7) atendimento a erros e 8) tabelas auxiliares.

e. 1) analisador léxico; 2) analisador sintático; 3) analisador semântico; 4) gerador de código intermediário; 5) otimizador de código; 6) gerador de código objeto; 7) tabelas auxiliares e 8) atendimento a erros.

Considere o pseudoprograma apresentado a seguir, escrito na linguagem de programação Java.

public class Test {
  private int x, y, z, w;
  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) { }
}

Supondo que o pseudoprograma apresentado utilize o escopo dinâmico, considere as afirmativas 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 x de main, y de sub1, c de sub3 e a, b, z e w de sub2.
2. Caso a sequência de chamada seja main chama sub3; sub3 chama sub2 e sub2 chama sub4, as variáveis visíveis durante a execução da última função chamada são x, y e z de main, w de sub2 e a, b, c e d de sub4.
3. 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, d de sub4, y, z e w de sub1 e a, b e c de sub3.
4. Caso a sequência de chamada seja main chama sub2; sub2 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.

Assinale a alternativa correta:

a. somente as afirmativas I e II são corretas.

b. somente as afirmativas I e III são corretas.

c. somente as afirmativas I e IV são corretas.

d. somente as afirmativas II e III são corretas.

e. somente as afirmativas II e IV são corretas.

A gramática a seguir define expressões regulares sob os símbolos a e b, usando o operador + no lugar do operador | para a união, a fim de evitar conflito com a barra vertical usada como um meta-símbolo nas gramáticas.

G = ({E, T, F}, {a, b, +, *}, P, E)
P = {E → E+T | T
     T → TF | F
     F → F* | a | b}

a) 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. Elimine a recursão à esquerda da gramática original.

G = ({E, E₁, T, T₁, F, F₁}, {a, b, +, *}, P, E)
P = {E  → TE₁
     E₁ → +TE₁ | ε
     T  → FT₁
     T₁ → FT₁ | ε
     F  → aF₁ | bF₁
     F₁ → *F₁ | ε}

b) A construção de analisadores descendentes é auxiliada por duas funções, FIRST e FOLLOW, associadas a uma gramática G. Durante a análise descendente, FIRST e FOLLOW nos permitem escolher qual produção aplicar, com base no próximo símbolo da entrada. Apresente os conjuntos FIRST e FOLLOW da gramática resultante do item a.

FIRST(E)  = {a, b}
FIRST(E₁) = {+, ε}
FIRST(T)  = {a, b}
FIRST(T₁) = {a, b, ε}
FIRST(F)  = {a, b}
FIRST(F₁) = {*, ε}

FOLLOW(E)  = {$}
FOLLOW(E₁) = {$}
FOLLOW(T)  = {+, $}
FOLLOW(T₁) = {+, $}
FOLLOW(F)  = {a, b, +, $}
FOLLOW(F₁) = {a, b, +, $}

c) 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 resultante da solução do item a, considerando os conjuntos FIRST e FOLLOW obtidos no item b.

d) 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 da entrada a + ba* + b, considerando a tabela M do item c.

Analisador Preditivo Tabular:

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. Considere a gramática livre do contexto apresentada a seguir.

G = ({S, T, P, F}, {x, +, *, ^}, P, S)
P = {S → S+T | T
     T → T*P | P
     P → P^F | F
     F → x}

Qual linha da tabela de precedência de operadores da gramática apresentada está correta.