Lista2.en.pt

Prévia do material em texto

Analisar e Top-Down análise (Compiladores 
Curso por Alex Aiken) 
QUESTÃO 1 
Quantas cordas faz o seguinte gramática gerar? UMA → BB B → CC C → 1 | 2 Quantas cordas faz o seguinte gramática gerar? UMA → BB B → CC C → 1 | 2 Quantas cordas faz o seguinte gramática gerar? UMA → BB B → CC C → 1 | 2 Quantas cordas faz o seguinte gramática gerar? UMA → BB B → CC C → 1 | 2 Quantas cordas faz o seguinte gramática gerar? UMA → BB B → CC C → 1 | 2 Quantas cordas faz o seguinte gramática gerar? UMA → BB B → CC C → 1 | 2 Quantas cordas faz o seguinte gramática gerar? UMA → BB B → CC C → 1 | 2 Quantas cordas faz o seguinte gramática gerar? UMA → BB B → CC C → 1 | 2 Quantas cordas faz o seguinte gramática gerar? UMA → BB B → CC C → 1 | 2 
2 4 7 8 15 16 
QUESTÃO 2 
Quantas cordas faz o seguinte gramática gerar? UMA → BB B → CC C → 1 | 2 Quantas cordas faz o seguinte gramática gerar? UMA → BB B → CC C → 1 | 2 Quantas cordas faz o seguinte gramática gerar? UMA → BB B → CC C → 1 | 2 Quantas cordas faz o seguinte gramática gerar? UMA → BB B → CC C → 1 | 2 Quantas cordas faz o seguinte gramática gerar? UMA → BB B → CC C → 1 | 2 Quantas cordas faz o seguinte gramática gerar? UMA → BB B → CC C → 1 | 2 Quantas cordas faz o seguinte gramática gerar? UMA → BB B → CC C → 1 | 2 Quantas cordas faz o seguinte gramática gerar? UMA → BB B → CC C → 1 | 2 Quantas cordas faz o seguinte gramática gerar? UMA → BB B → CC C → 1 | 2 
| ε| ε
11 12 15 16 31 32 63 64 
QUESTÃO 3 
Qual das seguintes gramática (s) produzir linguagens regulares? [Escolha todas que se 
aplicam]
UMA → ( A) | εUMA → ( A) | εUMA → ( A) | εUMA → ( A) | εUMA → ( A) | ε UMA → ( UMA( | εUMA → ( UMA( | εUMA → ( UMA( | εUMA → ( UMA( | εUMA → ( UMA( | ε UMA → ( B) | ( BB) B → UMA → ( B) | ( BB) B → UMA → ( B) | ( BB) B → UMA → ( B) | ( BB) B → UMA → ( B) | ( BB) B → UMA → ( B) | ( BB) B → 
( CC) | ( CCC) C → ( DDD) ( CC) | ( CCC) C → ( DDD) ( CC) | ( CCC) C → ( DDD) ( CC) | ( CCC) C → ( DDD) ( CC) | ( CCC) C → ( DDD) ( CC) | ( CCC) C → ( DDD) 
D → ()D → ()
UMA → aA | b UMA → aA | b UMA → aA | b UMA → aA | b UMA → aA | b UMA → Aa | b UMA → Aa | b UMA → Aa | b UMA → Aa | b UMA → Aa | b UMA → aaab | εUMA → aaab | εUMA → aaab | εUMA → aaab | εUMA → aaab | ε UMA → AAAAB | εUMA → AAAAB | εUMA → AAAAB | εUMA → AAAAB | εUMA → AAAAB | ε UMA → AAAAB | aab UMA → AAAAB | aab UMA → AAAAB | aab UMA → AAAAB | aab UMA → AAAAB | aab 
PERGUNTA 4 
Considerando-se o seguinte gramática: S → AA Considerando-se o seguinte gramática: S → AA Considerando-se o seguinte gramática: S → AA 
→ B | CB → ( C) C → B + C | DD → 1 | 0 → B | CB → ( C) C → B + C | DD → 1 | 0 → B | CB → ( C) C → B + C | DD → 1 | 0 → B | CB → ( C) C → B + C | DD → 1 | 0 → B | CB → ( C) C → B + C | DD → 1 | 0 → B | CB → ( C) C → B + C | DD → 1 | 0 → B | CB → ( C) C → B + C | DD → 1 | 0 → B | CB → ( C) C → B + C | DD → 1 | 0 → B | CB → ( C) C → B + C | DD → 1 | 0 → B | CB → ( C) C → B + C | DD → 1 | 0 → B | CB → ( C) C → B + C | DD → 1 | 0 → B | CB → ( C) C → B + C | DD → 1 | 0 → B | CB → ( C) C → B + C | DD → 1 | 0 → B | CB → ( C) C → B + C | DD → 1 | 0 
Adicionando qual das seguintes fará com que a gramática para ser deixado recursiva? [Escolha todas que se 
aplicam]
B → C B → C B → C D → B D → B D → B UMA → D UMA → D UMA → D D → UMA D → UMA D → UMA C → 1C C → 1C C → 1C C → C + B C → C + B C → C + B 
PERGUNTA 5 
Qual dos seguintes gramáticas remove corretamente esquerda recursão de: S → Aa | Um δ → Sβ Qual dos seguintes gramáticas remove corretamente esquerda recursão de: S → Aa | Um δ → Sβ Qual dos seguintes gramáticas remove corretamente esquerda recursão de: S → Aa | Um δ → Sβ Qual dos seguintes gramáticas remove corretamente esquerda recursão de: S → Aa | Um δ → Sβ Qual dos seguintes gramáticas remove corretamente esquerda recursão de: S → Aa | Um δ → Sβ Qual dos seguintes gramáticas remove corretamente esquerda recursão de: S → Aa | Um δ → Sβ Qual dos seguintes gramáticas remove corretamente esquerda recursão de: S → Aa | Um δ → Sβ 
[Escolha todas que se aplicam] 
S → Aa | Um δ → δβAS → Aa | Um δ → δβAS → Aa | Um δ → δβAS → Aa | Um δ → δβAS → Aa | Um δ → δβAS → Aa | Um δ → δβAS → Aa | Um δ → δβA
'
UMA ' → αβA ' | εUMA ' → αβA ' | εUMA ' → αβA ' | εUMA ' → αβA ' | εUMA ' → αβA ' | εUMA ' → αβA ' | εUMA ' → αβA ' | ε
S → Ds 'S → Ds 'S → Ds 'S → Ds '
S ' → COMO ' | εS ' → COMO ' | εS ' → COMO ' | εS ' → COMO ' | εS ' → COMO ' | εS ' → COMO ' | εS ' → COMO ' | ε
UMA → βα UMA → βα UMA → βα 
S → Aa | Um δ → δβ | Aαβ S → Aa | Um δ → δβ | Aαβ S → Aa | Um δ → δβ | Aαβ S → Aa | Um δ → δβ | Aαβ S → Aa | Um δ → δβ | Aαβ S → Aa | Um δ → δβ | Aαβ S → Aa | Um δ → δβ | Aαβ S → Aa | Um δ → δβ | Aαβ S → Aa | Um δ → δβ | Aαβ 
S → δAα | Um δ → UMAS → δAα | Um δ → UMAS → δAα | Um δ → UMAS → δAα | Um δ → UMAS → δAα | Um δ → UMAS → δAα | Um δ → UMAS → δAα | Um δ → UMA
' UMA | ε' UMA | ε' UMA | ε' UMA | ε
UMA ' → αβ UMA ' → αβ UMA ' → αβ UMA ' → αβ 
PERGUNTA 6 
Considere o seguinte gramática: E → E * E | E Considere o seguinte gramática: E → E * E | E Considere o seguinte gramática: E → E * E | E Considere o seguinte gramática: E → E * E | E Considere o seguinte gramática: E → E * E | E Considere o seguinte gramática: E → E * E | E Considere o seguinte gramática: E → E * E | E 
+ E | ( E) | int + E | ( E) | int + E | ( E) | int + E | ( E) | int + E | ( E) | int 
Quantas árvores de análise exclusivas estão lá para a cadeia 5 * 3+ (2 * 7) +4? Quantas árvores de análise exclusivas estão lá para a cadeia 5 * 3+ (2 * 7) +4? Quantas árvores de análise exclusivas estão lá para a cadeia 5 * 3+ (2 * 7) +4? Quantas árvores de análise exclusivas estão lá para a cadeia 5 * 3+ (2 * 7) +4? Quantas árvores de análise exclusivas estão lá para a cadeia 5 * 3+ (2 * 7) +4? 
1 2 4 5 7 8 
QUESTION 7
Using the grammar and string from the previous question (Question 6), which of the following rules are necessary to produce a 
unique parse tree for the string 5 ∗ 3+(2 ∗ 7)+4? [Choose all that apply] unique parse tree for the string 5 ∗ 3+(2 ∗ 7)+4? [Choose all that apply] unique parse tree for the string 5 ∗ 3+(2 ∗ 7)+4? [Choose all that apply] unique parse tree for the string 5 ∗ 3+(2 ∗ 7)+4? [Choose all that apply] unique parse tree for the string 5 ∗ 3+(2 ∗ 7)+4? [Choose all that apply] 
addition associates to the left multiplication associates to the 
left multiplication binds more tightly than addition parentheses 
bind more tightly than multiplication 
 
QUESTION 8
[Choose all that apply] 
The language "strings with an even number of 0's" is both regular and context-free. The language "0n1n, 
where n > 0 is an integer" is context-free but not regular. The language "0n1n2n, where n > 0 is an 
integer" is context-free but not regular. The language "0n2, where n > 0 is an integer" is regular. 
A linguagem "0n2, onde n> 0 é um inteiro" não é nem nem regular, livre de contexto. 
PERGUNTA 9 
Considere seguindo 4 gramáticas: G1. S →Considere seguindo 4 gramáticas: G1. S →
ASB | Sb | b G2. S → Sa | Sb | c G3. S → SaS | εASB | Sb | b G2. S → Sa | Sb | c G3. S → SaS | εASB | Sb | b G2. S → Sa | Sb | c G3. S → SaS | εASB | Sb | b G2. S → Sa | Sb | c G3. S → SaS | εASB | Sb | b G2. S → Sa | Sb | c G3. S → SaS | εASB | Sb | b G2. S → Sa | Sb | c G3. S → SaS | εASB | Sb | b G2. S → Sa | Sb | c G3. S → SaS | εASB | Sb | b G2. S → Sa | Sb | c G3. S → SaS | εASB | Sb | b G2. S → Sa | Sb | c G3. S → SaS | εASB | Sb | b G2. S → Sa | Sb | c G3. S → SaS | εASB | Sb | b G2. S → Sa | Sb | c G3. S → SaS | εASB | Sb | b G2. S → Sa | Sb | c G3. S → SaS | εASB | Sb | b G2. S → Sa | Sb | c G3. S → SaS | εASB | Sb | b G2. S → Sa | Sb | c G3. S → SaS | εASB | Sb | b G2. S → Sa | Sb | c G3. S → SaS | ε
G4. S → bT G4. S → bT G4. S → bT 
T → aT | εT → aT | εT → aT | εT → aT | εT → aT | ε
Seja n = o número de gramáticas onde existe uma cadeia quepossui pelo menos duas diferentes derivações mais à esquerda; 
m = número de gramáticas onde por qualquer string, só temos uma árvore de análise; K = o número de 
gramáticas que podem ser utilizados com um analisador de descida recursiva Escolha o valor correcto para n, 
m e k.
n = 1; m = 2; k = 1 n = 1; m = 1; k = 0 n = 2; m = 2; k = 1 n = 2; m = 2; k = 2 n = 
1; m = 1; k = 1 
PERGUNTA 10 
Quantas cordas distintos e analisar as árvores podem ser gerados pela seguinte gramática? S → A1 | 1B A → 10 |Quantas cordas distintos e analisar as árvores podem ser gerados pela seguinte gramática? S → A1 | 1B A → 10 |Quantas cordas distintos e analisar as árvores podem ser gerados pela seguinte gramática? S → A1 | 1B A → 10 |Quantas cordas distintos e analisar as árvores podem ser gerados pela seguinte gramática? S → A1 | 1B A → 10 |Quantas cordas distintos e analisar as árvores podem ser gerados pela seguinte gramática? S → A1 | 1B A → 10 |Quantas cordas distintos e analisar as árvores podem ser gerados pela seguinte gramática? S → A1 | 1B A → 10 |Quantas cordas distintos e analisar as árvores podem ser gerados pela seguinte gramática? S → A1 | 1B A → 10 |Quantas cordas distintos e analisar as árvores podem ser gerados pela seguinte gramática? S → A1 | 1B A → 10 |
C | εC | εC | ε
B → C1 | εB → C1 | εB → C1 | εB → C1 | εB → C1 | ε
C → 0 | 1 C → 0 | 1 C → 0 | 1 C → 0 | 1 C → 0 | 1 
5 cordas 7, árvores de análise 5, 6 cordas árvores de análise 6 cordas 7, árvores de análise 4, 6 cordas de análise 
árvores 
PERGUNTA 11 
Qual das seguintes gramática (s) não são ambíguos e reconhecem o mesmo gramática como: E → E + E | E - E | E * E Qual das seguintes gramática (s) não são ambíguos e reconhecem o mesmo gramática como: E → E + E | E - E | E * E Qual das seguintes gramática (s) não são ambíguos e reconhecem o mesmo gramática como: E → E + E | E - E | E * E Qual das seguintes gramática (s) não são ambíguos e reconhecem o mesmo gramática como: E → E + E | E - E | E * E Qual das seguintes gramática (s) não são ambíguos e reconhecem o mesmo gramática como: E → E + E | E - E | E * E Qual das seguintes gramática (s) não são ambíguos e reconhecem o mesmo gramática como: E → E + E | E - E | E * E Qual das seguintes gramática (s) não são ambíguos e reconhecem o mesmo gramática como: E → E + E | E - E | E * E Qual das seguintes gramática (s) não são ambíguos e reconhecem o mesmo gramática como: E → E + E | E - E | E * E Qual das seguintes gramática (s) não são ambíguos e reconhecem o mesmo gramática como: E → E + E | E - E | E * E 
 | E / E | int [Escolha todas que se aplicam] | E / E | int [Escolha todas que se aplicam] | E / E | int [Escolha todas que se aplicam] | E / E | int [Escolha todas que se aplicam] | E / E | int [Escolha todas que se aplicam] 
E → int + E | int - E | int * E | int / E | int E → E + int | E - int | E * E → int + E | int - E | int * E | int / E | int E → E + int | E - int | E * E → int + E | int - E | int * E | int / E | int E → E + int | E - int | E * E → int + E | int - E | int * E | int / E | int E → E + int | E - int | E * E → int + E | int - E | int * E | int / E | int E → E + int | E - int | E * E → int + E | int - E | int * E | int / E | int E → E + int | E - int | E * E → int + E | int - E | int * E | int / E | int E → E + int | E - int | E * E → int + E | int - E | int * E | int / E | int E → E + int | E - int | E * E → int + E | int - E | int * E | int / E | int E → E + int | E - int | E * E → int + E | int - E | int * E | int / E | int E → E + int | E - int | E * E → int + E | int - E | int * E | int / E | int E → E + int | E - int | E * E → int + E | int - E | int * E | int / E | int E → E + int | E - int | E * E → int + E | int - E | int * E | int / E | int E → E + int | E - int | E * E → int + E | int - E | int * E | int / E | int E → E + int | E - int | E * E → int + E | int - E | int * E | int / E | int E → E + int | E - int | E * E → int + E | int - E | int * E | int / E | int E → E + int | E - int | E * E → int + E | int - E | int * E | int / E | int E → E + int | E - int | E * E → int + E | int - E | int * E | int / E | int E → E + int | E - int | E * E → int + E | int - E | int * E | int / E | int E → E + int | E - int | E * E → int + E | int - E | int * E | int / E | int E → E + int | E - int | E * 
int | E / int | int E → int + E | E - int | int * E | E / int | int E → int + E ' | int int | E / int | int E → int + E | E - int | int * E | E / int | int E → int + E ' | int int | E / int | int E → int + E | E - int | int * E | E / int | int E → int + E ' | int int | E / int | int E → int + E | E - int | int * E | E / int | int E → int + E ' | int int | E / int | int E → int + E | E - int | int * E | E / int | int E → int + E ' | int int | E / int | int E → int + E | E - int | int * E | E / int | int E → int + E ' | int int | E / int | int E → int + E | E - int | int * E | E / int | int E → int + E ' | int int | E / int | int E → int + E | E - int | int * E | E / int | int E → int + E ' | int int | E / int | int E → int + E | E - int | int * E | E / int | int E → int + E ' | int int | E / int | int E → int + E | E - int | int * E | E / int | int E → int + E ' | int int | E / int | int E → int + E | E - int | int * E | E / int | int E → int + E ' | int int | E / int | int E → int + E | E - int | int * E | E / int | int E → int + E ' | int int | E / int | int E → int + E | E - int | int * E | E / int | int E → int + E ' | int int | E / int | int E → int + E | E - int | int * E | E / int | int E → int + E ' | int int | E / int | int E → int + E | E - int | int * E | E / int | int E → int + E ' | int int | E / int | int E → int + E | E - int | int * E | E / int | int E → int + E ' | int int | E / int | int E → int + E | E - int | int * E | E / int | int E → int + E ' | int int | E / int | int E → int + E | E - int | int * E | E / int | int E → int + E ' | int int | E / int | int E → int + E | E - int | int * E | E / int | int E → int + E ' | int int | E / int | int E → int + E | E - int | int * E | E / int | int E → int + E ' | int int | E / int | int E → int + E | E - int | int * E | E / int | int E → int + E ' | int int | E / int | int E → int + E | E - int | int * E | E / int | int E → int + E ' | int 
- E ' | int + E | int - EE '→ int * E ' | int / E ' | int E → E ' + E | E ' -E | E '- E ' | int + E | int - EE '→ int * E ' | int / E ' | int E → E ' + E | E ' -E | E '- E ' | int + E | int - EE '→ int * E ' | int / E ' | int E → E ' + E | E ' -E | E '- E ' | int + E | int - EE '→ int * E ' | int / E ' | int E → E ' + E | E ' -E | E '- E ' | int + E | int - EE '→ int * E ' | int / E ' | int E → E ' + E | E ' -E | E '- E ' | int + E | int - EE '→ int * E ' | int / E ' | int E → E ' + E | E ' -E | E '- E ' | int + E | int - EE '→ int * E ' | int / E ' | int E → E ' + E | E ' -E | E '- E ' | int + E | int - EE '→ int * E ' | int / E ' | int E → E ' + E | E ' -E | E '- E ' | int + E | int - EE '→ int * E ' | int / E ' | int E → E ' + E | E ' -E | E '- E ' | int + E | int - EE '→ int * E ' | int / E ' | int E → E ' + E | E ' -E | E '- E ' | int + E | int - EE '→ int * E ' | int / E ' | int E → E ' + E | E ' -E | E '- E ' | int + E | int - EE '→ int * E ' | int / E ' | int E → E ' + E | E ' -E | E '- E ' | int + E | int - EE '→ int * E ' | int / E ' | int E → E ' + E | E ' -E | E '- E ' | int + E | int - EE '→ int * E ' | int / E ' | int E → E ' + E | E ' -E | E '- E ' | int + E | int - EE '→ int * E ' | int / E ' | int E → E ' + E | E ' -E | E '- E ' | int + E | int - EE '→ int * E ' | int / E ' | int E → E ' + E | E ' -E | E '- E ' | int + E | int - EE '→ int * E ' | int / E ' | int E → E ' + E | E ' -E | E '- E ' | int + E | int - EE '→ int * E ' | int / E ' | int E → E ' + E | E ' -E | E '- E ' | int + E | int - EE '→ int * E ' | int / E ' | int E → E ' + E | E ' -E | E '- E ' | int + E | int - EE '→ int * E ' | int / E '| int E → E ' + E | E ' -E | E '- E ' | int + E | int - EE '→ int * E ' | int / E ' | int E → E ' + E | E ' -E | E '- E ' | int + E | int - EE '→ int * E ' | int / E ' | int E → E ' + E | E ' -E | E '- E ' | int + E | int - EE '→ int * E ' | int / E ' | int E → E ' + E | E ' -E | E '- E ' | int + E | int - EE '→ int * E ' | int / E ' | int E → E ' + E | E ' -E | E '- E ' | int + E | int - EE '→ int * E ' | int / E ' | int E → E ' + E | E ' -E | E '- E ' | int + E | int - EE '→ int * E ' | int / E ' | int E → E ' + E | E ' -E | E '- E ' | int + E | int - EE '→ int * E ' | int / E ' | int E → E ' + E | E ' -E | E '- E ' | int + E | int - EE '→ int * E ' | int / E ' | int E → E ' + E | E ' -E | E '
E ' → int * E ' | int / E ' | int E ' → int * E ' | int / E ' | int E ' → int * E ' | int / E ' | int E ' → int * E ' | int / E ' | int E ' → int * E ' | int / E ' | int E ' → int * E ' | int / E ' | int E ' → int * E ' | int / E ' | int E ' → int * E ' | int / E ' | int E ' → int * E ' | int / E ' | int E ' → int * E ' | int / E ' | int E ' → int * E ' | int / E ' | int E ' → int * E ' | int / E ' | int 
PERGUNTA 12 
Vamos Tn ser a string 0n1, para ser combinado com um analisador descendente recursivo usando a gramática a seguir: 
S -> A | B | 0S A -> 
0A | 0 B -> 1
É o número de comparações de tokens necessários para (com sucesso) jogo Tn: 
O (1) Em) O (n2) O (n3) O (2n) 
© Universidade de Stanford, Stanford, Califórnia 94305