Segunda Lista de Exercícios

1. Considere a gramática a seguir:

E -> ( L )
E -> a
L -> L , E
L -> E

Construa o DFA de itens LR(0) para essa gramática. Ela é LR(0)? Se não for, indentifique o conflito. Construa a tabela de análise sintática shift-reduce LR(0) (se possível) ou SLR(1).

2. Considere a gramática a seguir:

S -> S ( S )
S ->

Construa o DFA de itens LR(0) para essa gramática. Ela é LR(0)? Se não for, indentifique o conflito. Construa a tabela de análise sintática shift-reduce LR(0) (se possível) ou SLR(1).

3. Considere a gramática a seguir, para um fragmento de TINY:

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

a) Dê a sequência de ações (shift, reduce, accept) do analisador LR para o termo id := num ; id := id ().

b) Construa o DFA de itens LR(0) dessa gramática.

4. Considere a gramática a seguir:

S -> E
E -> E + E | E - E | E * E | ( E ) | id | num

a) Dê duas sequência de ações (shift, reduce, accept) do analisador LR para o termo num + num * num. Não é preciso dar o número dos estados nas ações de shift. Mostre como essas duas sequências de ações provam que a gramática é ambígua.

b) Dê o estado inicial do autômato LR(0) dessa gramática, as transições que saem desse estado, e os estados alvo dessas transições.

c) Escreva a implementação em Kotlin de uma AST e a função de verificação de tipos para termos dessa gramática. Os nós da AST devem implementar a interface abaixo:

interface Exp

Para a verificação de tipos a função é tipo(tabsimb: Map<String, String>): String, que retorna o tipo do termo sendo analisado. Um numeral literal tem tipo int, as operações aritméticas têm tipo int se suas partes tiverem tipo int, caso contrário temos um erro. O tipo dos identificadores é dado pela tabela de símbolos.

5. Um analisador LR(0) pode efetuar mais ou menos reduções que um analisador SLR(1) antes de declarar um erro? Justifique sua resposta.

6. Suponha que sejam removidas as especificações de associatividade e precedência dos operadores na especificação Jacc da gramática a seguir (tornando, portanto, a gramática ambígua). Quais seriam a associatividade e precedência dos operadores usando as regras de eliminação de ambiguidade de Jacc (shift em caso de conflito shift-reduce, reduce pela regra que vem primeiro em caso de conflito reduce-reduce)?

exp  : '(' exp ')'
     | NUM
     | ID
     | exp '<' exp
     | exp '=' exp
     | exp '+' exp
     | exp '-' exp
     | exp '*' exp
     | exp '/' exp
     ;

7. Acrescente os operadores ^ (exponenciação) e - (menos unário) à especificação de TINY. A precedência da exponenciação é maior do que a dos outros operadores binários, e ela é associativa à direita. A precedência do menos unário é maior que a dos operadores binários.

8. Considere a gramática a seguir para declarações simples em Pascal:

DECL -> VAR-LISTA : TIPO
VAR-LISTA -> VAR-LISTA , id
VAR-LISTA -> id
TIPO -> integer
TIPO -> real

Escreva a especificação de uma AST Kotlin para termos dessa gramática, e implememente a verificação de tipos como uma função tipo(tabsimb: Map<String, String>): Map<String, String>, que retorna uma nova tabela de símbolos com os tipos dos símbolos definidos pelo termo analisado. Declarar a mesma variável duas vezes é um erro.

9. Vetores são um tipo de dado bastante comum em linguagems de programação. Eles são um tipo composto: se t é um tipo qualquer da linguagem, t[] é um vetor em que cada elemento tem tipo t. A operação principal em um vetor é a indexação, que pode ser para leitura ou escrita.

Na indexação de leitura, uma expressão que deve ter o tipo t[] é indexada por uma expressão de tipo inteiro, e o resultado é um valor do tipo t (assumindo que o índice está dentro dos limites do vetor), o elemento correspondente ao índice.

data class IndexaLe(val vetor: Exp, val indice: Exp): Exp

Na indexação de escrita, uma expressão que deve ter tipo t[] e indexada por uma expressão de tipo inteiro está do lado esquerdo de uma atribuição, e uma expressão do tipo t deve estar do lado direito. O resultado é substituir o elemento na posição dada pelo índice pelo resultado do lado direito da atribuição.

data class IndexaEscreve(val vetor: Exp, val indice: Exp, val ldir: Exp): Cmd

a) Implemente a verificação de tipos para as operações de indexação de vetores, dados os fragmentos da AST acima. Assuma que a função de verificação de tipos é tipo(tabsimb: Map<String, String>): String; para um comando a verificação de tipos simplesmente retorna void. Se tipo é uma string, tipo.endsWith("[]") testa se é ele é um tipo vetor, e tipo.substring(0, tipo.size()-2) extrai o tipo base de um tipo vetor.

10. Acrescente um comando for ao compilador TINY. A sintaxe é

CMD -> for ID := exp TO exp BEGIN cmds END

O comportamento de um comando for é executar o bloco até que a variável de controle ultrapasse o valor da segunda expressão dada. O valor inicial é dado pela primeira expressão, e a cada iteração o valor é incrementado em 1. Se o valor inicial for maior que o final o for não executa nenhuma vez. A variável de controle é local ao for, estando no escopo do bloco de comandos dele. As duas expressões devem ter tipo inteiro, e esse é o tipo da variável de controle também. Faça todo o trabalho: modificação do analisador léxico para incluir as palavras chave for e to, modificação do analisador sintático para gerar o nó apropriado, e implementação da classe Java que representa esse nó, com sua análise de escopos e tipo.


Última Atualização: 2017-11-27 13:15