Primeira Lista de Exercícios

1. Descreva as tarefas efetuadas pelos seguintes programas, e explique como eles se assemelham ou se relacionam a compiladores:

• Um pré-processador C
• Um pretty-printer (formatador de programas)
• Um colorizador de programas de um editor de texto
• Um montador
• Um linkeditor do sistema operacional

2. Explique qual a relação e para que servem expressões regulares, autômatos finitos, tokens e lexemas.

3. Construa um autômato finito para aceitar as palavras reservadas case, char, const e continue.

4. Considere os tokens:

• Números inteiros sem sinal
• Números reais sem sinal
• Operadores aritméticos: +, -, /, *, (, )
• Operador de atribução: =
• Identificadores, onde são válidas apenas letras

Escreva regras usando expressões regulares e desenhe um autômato finito para reconhecer os tokens acima.

5. Numerais hexadecimais são usados em muitas linguagens de programação, e são escritos com o prefixo 0x ou 0X seguido de dígitos hexadecimais, 0-9 e a-f ou A-F. Ex: 0x80, 0xDEADBEEF, 0X42acB, 0xF.

• Escreva a(s) regra(s) léxica(s) para numerais hexadecimais, usando expressões regulares.
• Escreva um autômato finito determinístico para numerais hexadecimais.

6. Qual o problema causado por aninhamento de comentários em um analisador léxico gerado a partir de expressões regulares?

7. O seguinte trecho de código Java é responsável por ler e ignorar comentários em um analisador léxico de Pascal escrito à mão:

      case '{':
        nextChar();
        while((char)lookAhead != '}' &&
              lookAhead != EOF)
          nextChar();
        if((char)lookAhead != '}')
          error("comentário não terminado");
        nextChar();
        continue;

Como você reescreveria esse trecho para permitir comentários aninhados? Você pode definir métodos auxiliares. Dica: pense em um analisador sintático recursivo.

8. Escreva uma gramática sem ambiguidades que gere o conjunto de cadeias de caracteres {s;, s;s;, s;s;s;, …}.

      A -> A A | ( A ) | *vazio*

Descreva a linguagem que ela gera, e mostre que ela é ambígua.

10. Dada a gramática:

      E -> E + T | E - T | T
      T -> T * F | F
      F -> ( E ) | num

Escreva derivações e árvores sintáticas para as expressões a seguir (assuma que os numerais são instâncias do terminal num):

• 3 + 4 * 5 - 6
• 3 * ( 4 - 5 + 6 )
• 3 - ( 4 + 5 * 6 )

11. Escreva uma gramática para expressões boolenas contendo as constantes true e false e os operadores &&, || e !, além de parênteses. O operador || tem precedência menor que &&, e este menor que !. A gramática não pode ser ambígua.

12. Desafio! Mostre que a seguinte tentativa de resolução da ambiguidade do else ainda é ambígua:

      CMD -> if ( exp ) CMD | CASAM-CMD
      CASAM-CMD -> if ( exp ) CASAM-CMD else CMD | outro

13. Sinais de subtração unários podem ser acrescentados de diferentes maneiras a uma gramática de expressões aritméticas. Modifique a gramática da questão 10 de acordo com cada uma das especificações abaixo:

• No máximo um sinal unário permitido antes de qualquer termo, assim -2–3 é legal (e igual a -1) mas –2 e -2—3 são ilegais.
• Desafio: no máximo um sinal unário de subtração permitido em cada expressão, e deve aparecer no início (-2-3 é legal e igual a -5, -2-(-3) é legal, mas -2–3 é ilegal).
• Uma quantidade arbitrária de sinais unários de subtração é permitida antes de qualquer termo, portanto todas as expressões acima são legais.

14. Na gramática a seguir os não-terminais estão em maiúsculas e os terminais em minúsculas, todos separados por espaços (estilo BNF):

    PROGRAMA -> begin LISTACMD end
    LISTACMD -> LISTACMD CMD 
               | CMD
    CMD      -> do id := num to num begin LISTACMD end
               | read id
               | write EXP
               | id := EXP
    EXP      -> EXP + EXP | EXP - EXP | num | id | ( EXP )

Mostre a árvore sintática para o programa a seguir (pode abreviar os não-terminais assim: P, L, C, E, T):

    begin
      read x
      do i := 1 to 100 begin
        x := x + i
      end
      write x
    end

• Qual a principal razão para essa gramática não ser LL(1)?
• Mostre que essa gramática é ambígua.
• Remova a ambiguidade dessa gramática.
• Reescreva a gramática para remover recursão à esquerda e fatorar prefixos comuns

15. A gramática a seguir descreve um subconjunto das expressões regulares (o | do lado direito da primeira regra é o token do operador |):

    RE -> RE | RE
    RE -> RE RE
    RE -> RE *
    RE -> ( RE )
    RE -> letra

• Use essa gramática para apresentar uma derivação da expressão regular (ab|b)*.
• Mostre que essa gramática é ambígua.

• Reescreva essa gramática para não ser mais ambígua, corrigindo as precedências dos operadores. Lembre-se que a concatenação tem precedência sobre o

  , e a repetição (*) tem precedência sobre esses dois. Faça a operação de concatenação ser associativa à direita.

16. Dada a gramática A -> ( A ) A | *vazio*, escreva pseudocódigo para analisá-la de forma recursiva com retrocesso local e sem retrocesso (LL(1)).

17. Uma gramática LL(1) pode ser ambígua? Justifique.

18. Uma gramática não ambígua precisa ser LL(1)? Justifique.

19. Dadas as duas gramáticas a seguir:

      LEXP -> ATOMO | LISTA
      ATOMO -> num | id
      LISTA -> ( LEXP-SEQ )
      LEXP-SEQ -> LEXP-SEQ LEXP | LEXP

      DECL -> TIPO VAR-LISTA
      TIPO -> int | float
      VAR-LISTA -> id , VAR-LISTA | id

Remova a recursão esquerda, caso seja necessário, e escreva pseudo-código para um analisador recursivo para elas.

20. Dada a gramática:

    CMD -> ATRIB
    CMD -> CHAMADA
    CMD -> outro
    ATRIB -> id := exp
    CHAMADA -> id ( exp )

• Essa gramática é LL(1)? Justifique.
• Escreva o pseudocódigo para analisar essa gramática de forma recursiva sem retrocesso. Lembre-se de construir a árvore corretamente.

21. Da a gramática A -> aAa | *vazio*, demostre que essa gramática não é LL(1), e mostre que o código a seguir não implementa corretamente um analisador recursivo para essa gramática:

    void A() {
      Tree res = new Tree("A");
      if(la().equals("a")) {
        res.child(match("a"));
        res.child(A());
        res.child(match("a"));
      } else if(!la().equals("<<EOF>>")) {
        error("erro de sintaxe!");
      }
      return res;
    }

22. Considere a gramática a seguir, para um fragmento de Pascal:

    LISTA -> LISTA ; CMD | CMD
    CMD -> id := EXP
    EXP -> id | id ( ) | num

Reescreva essa gramática para eliminar recursão à esquerda e prefixos comuns.

Última Atualização: 2016-05-18 10:58