Exercícios

3.1

Descreva em termos de diagramas de grafos sintáticos a seguinte gramática expressa em notação yacc:

  %token  T1, T2, T3, T4
  %%
  n1   :  n2 T1 n2 T2
       |  T2
       ;
  n2   :  n3
       |  n4
       ;
  n3   :  n4 T3 n4
       |  T3 n4
       ;
  n4   :  n4 T4
       |  T4
       ;

3.2

Dada a expressão regular $(xx)*(y\vert z)z*$

(a)

Construa, usando o método da construção de Thompson, o autômato finito não-determinístico que reconhece as seqüências de símbolos que formam sentenças na linguagem regular correspondente.

(b)

Converta o autômato do item (a) para um autômato finito determinístico usando o método da construção de subconjuntos.

(c)

Converta o autômato finito determinístico obtido para outro equivalente com o menor número possível de estados.

3.3

Desenvolva o autômato finito determinístico com mínimo número de estados para reconhecer sentenças da gramática regular $G_2 = \{ V_n, V_t, P, A \}$, com $V_n = \{ A, B, C \}$, $V_t = \{ x, y \}$ e produções $P = \{ A \rightarrow x B, \; A \rightarrow y B, \; B \rightarrow x C, \; C \rightarrow x C, C \rightarrow y \}$.

3.4

O seguinte arquivo em formato lex especifica tokens que serão aceitos em uma dada aplicação (a ação correspondente não é mostrada aqui):

    %%
    0[01]{2}0
    1(0{2}|1{2})[01]

Dada esta especificação, indique para cada um dos tokens a seguir se ele seria ou não aceito na aplicação, justificando sua resposta.

(a)

0000

(b)

00120

(c)

0001

(d)

0010

(e)

0120

(f)

1000

(g)

1010

(h)

1020

(i)

1111

(j)

100110

3.5

Dada a gramática $G_1 = \{ V_n, V_t, P, S \}$, com $V_n = \{A, S\}$, $V_t = \{a, b\}$ e as produções $P = \{ S \rightarrow A, \; A \rightarrow aAb, \; A \rightarrow ab\}$

(a)

Qual a classe de linguagem definida por essa gramática?

(b)

Mostre a árvore gramatical para a sentença $aabbb$. Esta pertence à linguagem definida por essa gramática? Justifique.

(c)

Dê dois exemplos de sentenças geradas por essa gramática, apresentando para cada um dos exemplos a árvore sintática e a derivação canônica mais à esquerda.

(d)

Monte a tabela de deslocamento e redução para esta gramática. Mostre como as sentenças dos itens (b) e (c) seriam processadas através do analisador de deslocamento e redução correspondente.

3.6

Considere a gramática $G$ com $V_{nt} = \{S, A, B, C\}$, $V_t = \{x,y,z\}$, símbolo sentencial $S$ e as seguintes produções ( $\varepsilon$ é a string vazia):

R1:

$S \rightarrow A x B y C$

R2:

$A \rightarrow x A x$

R3:

$A \rightarrow \varepsilon$

R4:

$B \rightarrow B y$

R5:

$B \rightarrow \varepsilon$

R6:

$C \rightarrow z A z$

Para a sentença $x\,x\,x\,y\,y\,z\,x\,x\,z$, apresente

(a)

a derivação canônica mais à direita;

(b)

a derivação canônica mais à esquerda; e

(c)

a árvore gramatical, incluindo as ocorrências da string vazia como folhas da árvore.

3.7

Considere a gramática $G=(\{E,T,F\},\{x,y,+,\times,(,)\}, P, E)$ onde $P$ é o conjunto com as seguintes produções:

1. $E \rightarrow E + T$
2. $E \rightarrow T$
3. $T \rightarrow T \times F$
4. $T \rightarrow F$
5. $F \rightarrow ( E )$
6. $F \rightarrow x$
7. $F \rightarrow y$

(a)

Classifique a gramática pela hierarquia de Chomsky, justificando sua resposta.

(b)

A sentença $x+x\times y + y$ é descrita por esta gramática? Justifique sua resposta mostrando se existe ou não uma árvore sintática para a sentença e uma derivação canônica.