Trabalhos Práticos - PLI 2002
Trabalho Prático 1
Trabalho Prático 2
Este trabalho irá ser composto por 3 ou 4 fases distintas. O aluno deverá ir
desenvolvendo o trabalho à medida que os enunciados começarem a ser publicados
nesta página. Há uma data limite para a conclusão de cada uma das etapas. No
fim de cada etapa será feita a entrega dum "deliverable" específico
que será solicitado no enunciado de cada fase.
Após uma data limite, poderá ser-te solicitada pelo docente uma
demonstração do estado actual do protótipo, durante uma aula prática, pelo
que deverás fazer-te sempre acompanhar por uma diskette com a versão actual do
trabalho.
Descrição geral do trabalho
O trabalho, no seu todo, consistirá num gerador de parsers para gramáticas
LL(1).
Durante as várias etapas o aluno terá que:
- desenvolver e especificar uma linguagem para descrição de gramáticas
- implementar um analisador léxico e um analisador sintático que façam o
reconhecimento dessa linguagem e construam uma representação abstracta das
frases introduzidas.
- implementar um analisador semântico que irá verificar se a gramática é
LL(1). Caso não seja deverá indicar quais as situações de conflito.
- implementar um gerador de código que realizará uma travessia à
representação abstracta e gerará o respectivo código, lex+C e lex+yacc,
que não é mais do que uma implementação específica dum parser para a
linguagem que especificada na entrada.
- ...?
Etapa 1 (Data limite - 5 de Abril)
Visualização dos
realatórios submetidos
Nesta etapa, terás que definir uma linguagem para a especificação de
gramáticas independentes de contexto.
Uma gramática independente de contexto é um quádruplo:
- símbolos terminais
- símbolos não terminais
- axioma
- produções
Usa a tua imaginação e criatividade e discute com os docentes e os colegas
as tuas ideias.
Assim que tiveres uma definição estável da linguagem implementa um
reconhecedor para essa linguagem usando a tecnologia leccionada na disciplina
até agora: lex para o analisador léxico e C+recursivo descendente para o
analisador sintático.
Deliverables
Pequeno relatório em LaTeX contendo:
- pequeno enunciado
- gramática da linguagem inventada por ti
- especificação do analisador léxico
- especificação do analisador sintático
Etapa 2 (Data limite - 19 de Abril)
Tendo o reconhecedor terminado há que acrescentar-lhe as acções
semânticas para a construção da representação abstracta. Para isso, vais
extrair a sintaxe abstracta da linguagem concreta que definiste na etapa1 e vais
usar as regras introduzidas nas aulas teóricas para derivar os tipos de dados
em C e as respectivas funções de construção em C.
Uma vez construída a representação abstracta deverás implementar em C os
algoritmos que permitam verificar se a gramática que foi especificada na tua
linguagem é LL(1): first, follow, firstN, lookahead.
No fim desta fase, o teu compilador deverá aceitar a especificação duma
gramática e indicar ao utilizador se a gramática é LL(1) ou não. No caso de
não ser, deverá indicar quais as situações de conflito.
Extra: sugerir as transformações a aplicar nas situações de conflito.
Em alternativa, para quem não conseguir implementar os algoritmos
referidos no ponto anterior, poderás fazer as seguintes validações/tarefas:
- Não há produções com identificadores idênticos, ou seja, o identificador
da produção é único.
- Todos os Símbolos terminais e não terminais estão devidamente declarados.
- O axioma é um símbolo não terminal devidamente declarado e que aparece
pelo menos uma vez do lado esquerdo duma produção.
- Quem não conseguiu implementar o cálculo de lookaheads deve fazer um
acrescento à linguagem: para cada produção deverá ser possível especificar a
lista de símbolos terminais pertencentes ao lookahead da produção.
Deliverables
Pequeno relatório em LaTeX contendo:
- pequeno enunciado
- gramática abstracta da linguagem inventada por ti
- tipos de dados em C derivados
- apresentação dos algoritmos que testam a condição LL(1)
- apresentação dos algoritmos que realizam as pequenas validações
- implementação em C dos algoritmos
Etapa 3 (Data limite - 3 de Maio)
Nesta etapa, vais fazer a geração de código.
Terás que gerar código para os seguintes módulos:
- Analisador léxico: especificação em lex, como vem sendo hábito poderás
gerar também o ficheiro tokens.h
- Analisador sintáctico: utilizando o método recursivo descendente
- Tratamento de erros: deverão ser detectados erros léxicos e sintácticos
Deliverables
Pequeno relatório em LaTeX contendo:
- relatório anterior +
- pequeno enunciado da etapa
- estratégia montada para a geração de código: número de travessias, tipo de
travessias, estruturas de dados auxiliares, ...
- apresentação de 2 exemplos (1 simples e outro mais complexo)
Etapa 4 (Data limite - 17 de Maio) - entrega final
Nesta etapa, apenas terás de substituir o parser recursivo descendente pelo
parser LALR gerado pelo yacc. Para isso, terás que especificar a gramática da
tua linguagem no yacc e transpor as acções semânticas do recursivo descendente
(é provável que a gramática sofra alterações tornando-se mais simples).
Deliverables
- Relatório final do projecto (20% da nota prática final)
- Demonstração e defesa do trabalho em data a combinar (80% da nota prática
final)
16-04-2002 16:13
by jcr