Primeira Lista de Exercícios

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

1. Um pré-processador C
2. Um pretty-printer
3. Um colorizador de programas de um editor de texto
4. Um montador
5. 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 não sinalizados
• Números reais não sinalizados (simples, sem uso de potências de 10 ou “notação de engenharia”)
• Operadores aritméticos: +, -, /, *, (, )
• Operador de atribução: =
• Identificadores, onde são válidas apenas letras

Escreva expressões regulares (usando as extensões do JFlex) e desenhe um autômato finito para reconhecer os tokens acima.

5. Adicione constantes inteiras hexadecimais aos analisadores léxicos de TINY (escrito à mão e JFlex).

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

7. Dada a gramática:

  A -> AA | (A) | <vazio>

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

8. Dada a gramática:

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

Escreva derivações à direita e árvores sintáticas para as expressões a seguir:

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

9. A gramática a seguir gera todas as expressões regulares para o alfabeto de letras (usei aspas simples as marcas dos operadores):

  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 e corrija as precedências dos operadores
• Que associatividade é imposta aos operadores binários pela resposta anterior? Por quê?

10. 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.

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

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

12. 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 de acordo com cada uma das especificações abaixo:

• 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).
• No máximo um sinal unário permitiod antes de qualquer termo, assim -2--3 é legal (e igual a -1) mas --2 e -2---3 são ilegais.
• 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.

13. Em algumas linguagens uma declaração de procedimento deve terminar com uma sintaxe que inclua o nome do procedimento. Por exemplo, em Modula-2, um procedimento é declarado assim:

  PROCEDURE FOO;
  BEGIN
    ...
  END FOO;

Observe o uso do nome FOO após o END. Isso pode ser verificado por um analisador sintático livre de contexto? Como você implementaria isso em um analisador sintático recursivo?

14. Dada a gramática A -> (A)A | <vazio>, escreva pseudocódigo para analisá-la de forma recursiva.

15. Dada a gramática:

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

Escreva o pseudocódigo para analisar essa gramática de forma recursiva.

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

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

18. Dadas as 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 construa os conjuntos de lookahead para as produções da gramática. Elas são LL(1)? Esboce um analisador recursivo para elas.

19. 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() {
  if(lookAhead.type == 'a') {
    match('a');
    A();
    match('a');
  } else if(lookAhead.type != Token.EOF) {
    error("erro de sintaxe!");
  }
}

20. Reescreva a gramática de TINY para permitir que somente expressões booleanas sejam permitidas como condições em if e repeat, e que somente expressões aritméticas sejam permitidas do lado direito de atribuições e em comandos write.