Turmas - 1º Semestre de 2023
Turmas
1º Semestre de 2023

Quando se consideram linguagens especificadas através de gramáticas livres de contexto, deve-se também considerar de que forma é feita a aceitação sintática de suas sentenças para fins de compilação e/ou interpretação. Quando se trata de efetuar o reconhecimento de sentenças, o que se busca, na verdade, é localizar uma sequência de produções que, quando aplicada à raiz da gramática, forneça como resultado, através da série correspondente de derivações, a sentença fornecida para análise. Sendo possível completar a derivação, diz-se que a sentença pertence à linguagem; caso contrário, que ela não pertence à linguagem.

Por exemplo, a derivação da sentença a + a sobre a gramática livre de contexto G₁ pode produzir a sequência de derivação E ⇒ T + E ⇒ F + E ⇒ F + T ⇒ a + T ⇒ a + F ⇒ a + a, no qual foram aplicadas seis produções, sendo elas (1), (4), (2), (6), (4), (6).

G1 = ({E, T, F}, {a, +, *, (, )}, P1, E)
P1 = {E → T + E  (1)
      E → T      (2)
      T → F * T  (3)
      T → F      (4)
      F → ( E )  (5)
      F → A }    (6)

Conforme exposto, para o reconhecimento da sentença [[a];[a;[a]]] sobre a gramática livre de contexto G₂ é necessário a aplicação de quantas produções?

G2 = ({S, L}, {;, [, ], a}, P2, S)
P2 = {S → a | [L]
      L → S;L | S}

a. 10 produções.

b. 11 produções.

c. 12 produções.

d. 13 produções.

e. 14 produções.

Uma característica de projeto de expressões menos comumente discutida é a ordem de avaliação de operandos. As variáveis, nas expressões, são avaliadas buscando seus valores na memória. As constantes, às vezes, são avaliadas da mesma maneira. Em outros casos, uma constante pode fazer parte da instrução de linguagem de máquina e não exigir uma busca na memória. Se um operando for uma expressão colocada entre parênteses, todos os operandos que ela contém devem ser avaliados antes que seu valor possa ser usado como um operando. Se nenhum dos operandos de um operador tiver efeitos colaterais, a sua ordem de avaliação é irrelevante. Um efeito colateral de uma função, chamado efeito colateral funcional, ocorre quando ele modifica um de seus parâmetros ou uma variável global (ela é declarada fora da função, mas acessível na função).

Admitindo que a função C fun seja definida como

int fun(int *i, int *j) {
  *i += 3;
  *j += 5;
  return *j - *i;
}

void main() {
  int x = 3;
  int y = 2;
  int z = x + fun(&x, &y) + y;
}

Avalie as seguintes assertivas:

1. O valor de z será 14 caso os operandos sejam avaliados da esquerda para a direita.
2. O valor de z será 11 caso os operandos sejam avaliados da esquerda para a direita.
3. O valor de z será 9 caso os operandos sejam avaliados da direita para a esquerda.
4. O valor de z será 6 caso os operandos sejam avaliados da direita para a esquerda.

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.

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.

void sub1() { int x, y, z; }
void sub2() { int x, b, c; }
void sub3() { int a, b, z; }
void sub4() { int a, y, z; }
int main() { 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 e a e z de sub3.
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 z de sub1, b de sub3 e a e c de main.
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 sub1, b e c de sub2 e a, y e z de sub4.
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 x e y de sub1, c de sub2 e 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.

(Price, 2005) Considere o seguinte programa escrito na sintaxe Pascal:

program main;
  var a, b : integer;

procedure p(x, y, z : integer);
begin
  y := y + 1;
  z := z + x;
end;

begin
  a := 2;
  b := 3;
  p(a + b, a, b);
  write(b);
end.

Com base no programa apresentado, avalie as asserções a seguir.

1. Caso os parâmetros sejam passados por valor, o valor impresso será 5.
2. Caso os parâmetros sejam passados por valor-resultado, o valor impresso será 8.
3. Caso os parâmetros sejam passados por nome, o valor impresso será 9.
4. Caso os parâmetros sejam passados por referência, o valor impresso será 9.

A respeito dessas asserções, assinale a alternativa correta.

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.

Os critérios de avaliação das linguagens de programação fornecem uma estrutura para o projeto. Infelizmente, essa estrutura é contraditória. Em seu documento sobre projeto de linguagens, Hoare (1973) afirma que “existem tantos critérios importantes, mas conflitantes, que a reconciliação e a satisfação dos mesmos é uma grande tarefa de engenharia”. Por exemplo, dois critérios conflitantes no projeto de linguagens de programação são a confiabilidade e o custo de execução. Por que esses dois critérios são conflitantes? Justifique sua resposta com a apresentação de algoritmos, na linguagem de programação de sua preferência.

A definição da linguagem de programação Ada exige que todas as referências aos elementos do array sejam verificados para assegurar que o índice ou os índices estejam em suas faixas legais. Isso aumenta o custo de execução de programas Ada que contenham um grande número de referências aos elementos do array. A linguagem de programação C não exige verificação da faixa de índice, de modo que os programas em C executam mais rapidamente do que programas em Ada semanticamente equivalentes, não obstante os programas em Ada sejam mais confiáveis. Os projetistas da Ada trocaram a eficiência de execução pela confiabilidade, o oposto dos projetistas do C.

Código na linguagem de programação Ada:

procedure ArrayInit is
  a : array (1..2000000) of integer;
begin
  for i in 1..2000000 loop
    a(i) := i;
  end loop;
end ArrayInit;

Código na linguagem de programação C:

void arrayInit()
{
  int a[2000000];
  for (int i = 0; i < 2000000; i++)
  {
    a[i] = i;
  }
}

Em Ada, cada acesso aos elementos do array a serão verificados, garantindo que o elemento desejado realmente exista no array. Em contrapartida, o C não realiza tais verificações, permitindo que elementos inexistentes ao array sejam acessados e modificados, caso o programador se descuide nos índices.

No exemplo apresentado, a execução do subprograma Ada é cerca de 3 milissegundos mais lento do que o subprograma equivalente em C, justamente porque o C não gasta tempo de processamento verificando a existência dos elementos no array a.

A ideia existente por trás da semântica operacional é descrever o significado de um programa ao executar suas instruções em uma máquina, seja ela real ou simulada. As alterações que ocorrem no estado de uma máquina, quando ela executa determinada instrução, definem o significado desta. Usando as instruções da máquina virtual definida a seguir, apresente uma definição semântica operacional da instrução switch em C apresentada a seguir.

ident := var
ident := var op_bin var
ident := op_un var
goto label
if var relop var goto label

ident é um identificador.

var é um identificador ou uma constante.

op_bin pode ser um dos operadores aritméticos do conjunto {+, -, *, /}.

op_un pode ser um dos operadores unários do conjunto {+, -}.

relop pode ser um dos operadores relacionais do conjunto {=, <>, >, <, >=, <=}.

switch (var) {
  case c1: expr1;
  case c2: expr2;
  case c3: expr3;
  default: expr4;
}

if var = c1 goto label1;
if var = c2 goto label2;
if var = c3 goto label3;
goto label4;
label1:
  expr1;
label2:
  expr2;
label3:
  expr3;
label4:
  expr4;

Arrays multidimensionais podem ser armazenados em ordem de linha maior, como no Pascal, ou em ordem de coluna maior, como no FORTRAN. Por exemplo, o arranjo

pode ser armazenado, em memória, de duas maneiras possíveis:

No caso dos elementos serem armazenados em ordem de linha maior, a função responsável por retornar o endereço do elemento desejado é dado por posição A(i, j) = (j - 1) + J * (i - 1), sendo

i a posição da linha desejada,

j a posição da coluna desejada,

I a quantidade de linhas, e

J a quantidade de colunas.

Por exemplo, a posição do elemento a₂₁ será posição A(2, 1) = (1 - 1) + 3 * (2 - 1) = 3

Apresente a função responsável por retornar o endereço do elemento desejado, caso o arranjo seja armazenado em ordem de coluna maior.

posição A(i, j) = (i - 1) + I * (j - 1)