Desenvolva um programa na linguagem de programação SIMPLE, que apresente a sequência de Tribonacci, definida recursivamente pela fórmula Fn = Fn-1 + Fn-2 + Fn-3, sendo F0 = 0, F1 = 1 e F2 = 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}
+ | * | a..e | $ | |
---|---|---|---|---|
+ | < | < | < | > |
* | > | > | < | > |
a..e | > | > | erro 1 | > |
$ | < | < | < | aceita |
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.
Pilha | Relação | Entrada | Ação | Handle |
---|---|---|---|---|
$ | < | a + b * c * d + e $ | empilha a | |
$ a | > | + b * c * d + e $ | reduz | C → a |
$ A | < | + b * c * d + e $ | empilha + | |
$ A + | < | b * c * d + e $ | empilha b | |
$ A + b | > | * c * d + e $ | reduz | C → b |
$ A + A | < | * c * d + e $ | empilha * | |
$ A + A * | < | c * d + e $ | empilha c | |
$ A + A * c | > | * d + e $ | reduz | C → c |
$ A + A * A | > | * d + e $ | reduz | B → B*C |
$ A + A | < | * d + e $ | empilha * | |
$ A + A * | < | d + e $ | empilha d | |
$ A + A * d | > | + e $ | reduz | C → d |
$ A + A * A | > | + e $ | reduz | B → B*C |
$ A + A | < | + e $ | empilha + | |
$ A + A + | < | e $ | empilha e | |
$ A + A + e | > | $ | reduz | C → e |
$ A + A + A | > | $ | reduz | A → A+B |
$ A + A | > | $ | reduz | A → A+B |
$ A | aceita | $ |
(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.
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:
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:
Token | Expressão regular |
---|---|
T1 | k?b?zz*k |
T2 | z?k?bb*z |
T3 | b?z?kk*b |
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:
Entrada | Token | Expressão regular | Reconhecido |
---|---|---|---|
kkbzkbbkkb | T1 | k?b?zz*k | e |
kkbzkbbkkb | T2 | z?k?bb*z | e |
kkbzkbbkkb | T3 | b?z?kk*b | kkb |
Entrada | Token | Expressão regular | Reconhecido |
---|---|---|---|
zkbbkkb | T1 | k?b?zz*k | zk |
zkbbkkb | T2 | z?k?bb*z | e |
zkbbkkb | T3 | b?z?kk*b | zkb |
Entrada | Token | Expressão regular | Reconhecido |
---|---|---|---|
bkkb | T1 | k?b?zz*k | zk |
bkkb | T2 | z?k?bb*z | e |
bkkb | T3 | b?z?kk*b | bkkb |
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) = {)}
a | ; | ( | ) | $ | |
---|---|---|---|---|---|
A | A → a | erro 1 | A → (B) | erro 1 | erro 1 |
B | B → aD | erro 1 | B → (B)D | erro 1 | erro 1 |
C | C → ;AD | erro 1 | erro 1 | ||
D | D → ε | D → C | D → ε | D → ε | D → ε |
a | desempilha | ||||
; | desempilha | ||||
( | desempilha | ||||
) | erro 2 | erro 2 | erro 2 | desempilha | erro 2 |
$ | erro 3 | erro 3 | erro 3 | erro 3 | sucesso |
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.