Projeto Compilador Java - Análise Sintática e Recuperação de Erros

Universidade Federal de Juiz de Fora Disciplina Teoria dos Compiladores Instituto de Ciências Exatas Professor Marcelo Bernardes Vieira Departamento de Ciência da Computação PROJETO E IMPLEMENTAÇÃO DE UM COMPILADOR 2ª PARTE Projete e implemente um analisador sintático para a linguagem Java definida pela gramática livre de contexto listada no fim deste documento 1 Use a solução da parte I do projeto como ponto inicial para a implementação 2 Converta a gramática Java em uma gramática LL1 ou LR1 Construa um parser para a linguagem Java 3 Durante o parsing crie toda a árvore de sintaxe abstrata em memória 4 Adicione um esquema de recuperação de erros com sincronização Implemente no mínimo a recuperação do tipo phraselevel 5 Atenda a todas as especificações mínimas a seguir Lembrese que este trabalho faz parte de um projeto muito maior Documentação mínima A documentação a ser entregue em papel deve ser como um pequeno artigo objetivo impessoal e completo que explica os detalhes do quê o programa faz como faz e ainda apresenta conclusões obtidas pelo trabalho É um documento a parte que deve conter pelo menos as seguintes estruturas seções 1 Título Apresente o título do trabalho eou nome do compilador Nome dos integrantes do grupo seguidos dos pesos de cada um A soma dos pesos deve ser 1 2 Visão geral Dê uma visão geral do funcionamento do programa Descrição dos módulos e suas interdependências Apresente uma breve descrição de cada módulo bem como um diagrama por exemplo mostrando suas interrelações i Analisador sintático 1 Descreva e justifique a forma com a qual vocês implementaram o analisador sintático 2 Apresente a Gramática LL1 ou LR1 resultante 3 Apresente as estruturas de dados os métodos e os algoritmos utilizados ii Gerenciador de erros sintáticos 1 Apresente claramente o método de gerenciamento de erros escolhido 2 Apresente as estruturas de dados os métodos e os algoritmos utilizados iii Árvore de sintaxe abstrata 1 Mostre em detalhes como a árvore de sintaxe abstrata é construída 3 Resultados experimentais Listagem dos testes executados deve conter os arquivos de entrada compilados pelo programa arquivos texto jmm com código Java com os respectivos resultados de saída Comente os testes executados ATENÇÃO procure fazer testes relevantes levando em conta as diferentes construções da linguagem Prove que seu compilador é capaz de realizar as tarefas especificadas abaixo 4 Conclusão Esse é o lugar em que vocês podem me comunicar tudo o que vocês acham que é importante de ser dito Descreva todas as características especiais do seu compilador nessa seção Indique extensões e funcionalidades extras 5 Referências bibliográficas Mostre quais as fontes que vocês consultaram para realizar cada etapa do trabalho Inclua quaisquer artigos livros citações etc consultados No caso dos livros do curso indique quais as seções lidasusadas para cada tarefa 6 Listagem do programa fonte O código deve ser claro comentado indentado e sem linhas quebradas Use uma fonte isométrica todos os caracteres têm a mesma largura e altura Ex Courier Forneçam uma listagem organizada e compacta Evite longos trechos de código dentro de um mesmo bloco Os programas fonte devem ser entregues prontos para compilar sem erros nem avisos com makefile projeto CodeBlocks projeto CodeLite e descompactados Na apresentação leve um backup em pendrive Não conte com o uso da rede ATENÇÃO o código deve rodar em ambiente Linux e Windows MinGW Especificações mínimas para o analisador sintático Esse trabalho é realizável somente através da leitura dos livros Não reinvente a roda Seja objetivo e desenvolva como está na literatura observando rigorosamente as especificações a seguir Abuse ostensivamente de comentários esclarecedores sobre e em todo o código do compilador A saída do programa deve ser enviada exclusivamente para stdout Não crie nenhum arquivo de saída As mensagens de erro devem ser enviadas exclusivamente para stderr Não crie nenhum arquivo de mensagens de erro A precedência dos operadores Java da menor para a maior e que deve ser resolvida na gramática LL1 é 1 Atribuição 2 Or booleano 3 And booleano 4 Igual e diferente 5 Outros relacionais 6 Adição subtração e Or bit a bit 7 Multiplicação divisão e And bit a bit 8 Unários 9 Parênteses Ao converter a GLC Java para LL1 ou LR1 estejam certos de que vocês não estão mudando a linguagem que é aceita pela gramática Não se preocupem com nenhuma regra sensível ao contexto Outras restrições à linguagem serão impostas na próxima parte do projeto De fato há uma parte da GLC Java que não pode ser convertida para LL1 nem LR1 O problema ocorre em algumas formas de expressões envolvendo o operador de atribuição A dificuldade está em determinar se a expressão no lado esquerdo é um L value no momento da derivação Por exemplo as seguintes expressões são válidas em Java ai ai não é um Lvalue aqui ai x ai é um Lvalue aqui x 8 y 6 x e y são Lvalue aqui e y 6 é uma expressão que resulta no Rvalue 6 mas as seguintes não são válidas em Java ai bi x ai bi não é um Lvalue válido x 8 y 6 8 y não é um Lvalue tem precedência sobre A manipulação correta desses casos requer mais do que um token de lookahead ou um ou mais tokens do tipo lookbehind Por agora a solução é desprezar o problema e traduzir a gramática Java em uma gramática LL1 quase equivalente Ou seja a gramática LL1 será equivalente a Java com exceção de que aceitará strings do tipo ai bi expr Portanto a árvore de sintaxe abstrata aceita a atribuição de uma expressão a outra expressão Na próxima parte do projeto ao realizar a análise semântica e a geração de código o compilador deverá verificar se a expressão no lado esquerdo de uma atribuição é um Lvalue A conversão da gramática Java para LL1 ou LR1 será a tarefa mais importante dessa parte do projeto Mesmo calculando os conjuntos FIRST e FOLLOW é recomendável testar a sua gramática manualmente para verificar se suas produções derivam corretamente alguns programas Java bem simples Por exemplo class execclass public int calculaint k int h Systemoutprintlnk foram calculados class mainclass public static void main int a float b x y u7 dummysomaexecclasscalculak75a Uma vez verificado que a sua gramática é LL1 ou LR1 e deriva a mesma linguagem da GLC Java então implemente o parser Se sua escolha é por um parser recursivo descendente gereo a partir de uma gramática LL1 Se você escolher uma estratégia bottomup com uma gramática LR1 será necessário utilizar um gerador de parsers Neste caso as decisões de implementação terão restrições impostas pelo gerador Tenha certeza de que o grupo consegue realizar todas as tarefas neste contexto Especificações mínimas para o gerenciador de erros sintáticos É preciso garantir que o parser pode derivar todas as construções da linguagem Java e suas combinações antes de adicionar o código de recuperação de erros Após ter certeza de que o parser funciona você deve implementar uma recuperação de erros com um esquema de phraselevel simplificado para um único token faltante ou incorreto Não é necessário apresentar esquemas mais complexos de recuperação de erros Encontre casos simples de recuperação a partir de um único token esperado mas não encontrado Use o conjunto FOLLOW para sincronizar o parser Quando o parser encontrar um erro ele deve imprimir uma mensagem em stderr tentar se recuperar e continuar o parsing Por exemplo após detectar o seguinte erro ID LPARENT ID SEMICOLON o parser deve imprimir uma mensagem como Linha 34 erro sintático Falta fecha parênteses na chamada do procedimento e continuar o parsing como se o parênteses estivesse no local esperado Emita mensagens com significado para stderr contendo o número da linha na qual ocorreu o erro Erros léxicos devem gerar mensagens de erro mas não devem terminar o parsing Busque o próximo token válido e o retorne Especificações mínimas para o gerador de código intermediário Somente adicione o código para a construção da árvore de sintaxe abstrata após 1 implementar todo o parser no caso de construir um parser recursivo descendente 2 ou gerar e entender como funciona a interface do gerador de parsers para inserção de ações A função para o primeiro nãoterminal da gramática Program deverá retornar um ponteiro para o nodo raiz da árvore de sintaxe abstrata PROGRAM indicado na tabela a seguir Essa é a única interface do analisador sintático com o compilador Implemente as estruturas e a construção da árvore de sintaxe abstrata de forma independente do parser Esse apenas deve conter o código necessário para montar a árvore ATENÇÃO apenas construa a árvore NÃO verifique nada da linguagem Isso é tarefa para o analisador semântico Insira ações no parser para criar uma árvore com uma estrutura equivalente à dos nodos a seguir Nodo Formas possíveis 1 PROGRAM CLASSLIST 2 CLASSLIST ID VARLIST METHODLIST ID CLASSLIST NULL 3 VARLIST TYPE ARRAY IDLIST VARLIST NULL 4 METHODLIST TYPE ARRAY ID VARLIST VARLIST STATEMENTLIST METHODLIST NULL 5 IDLIST ID ARRAY IDLIST NULL 6 TYPE ID PRIMITIVE 7 ARRAY ARRAY NULL 8 STATEMENTLIST STATEMENT STATEMENTLIST NULL 9 STATEMENT IF WHILE SWITCH BREAK PRINT READ RETURN ASSIGN CALL STATEMENTLIST EXP 10 IF EXP STATEMENT STATEMENT 11 WHILE EXP STATEMENT 13 SWITCH EXP CASEBLOCK 14 CASEBLOCK NUM STATEMENTLIST CASEBLOCK NULL 15 READ EXP 16 PRINT EXPLIST 17 RETURN EXP 18 ASSIGN NAME EXP 19 CALL NAME EXPLIST 20 EXPLIST EXP EXPLIST NULL 21 EXP NAME NUMBER LITERAL LITERALCHAR CALL RELATIONALOP ADDITIONOP MULTIPLICATIONOP BOOLEANOP BITWISEOP NOT SIGN NEW LENGTH TRUE FALSE THIS 22 NEW TYPE ARRAYLIST TYPE EXPLIST 23 ARRAYLIST EXP ARRAYLIST NULL 24 NAME ID NAME ID NAME ARRAYLIST 25 RELATIONALOP OPREL EXP EXP 26 ADDITIONOP OPADD EXP EXP 27 MULTIPLICATIONOP OPMUL EXP EXP 28 BOOLEANOP OPBOOL EXP EXP 29 BITWISEOP OPBIT EXP EXP 30 NOT EXP 31 SIGN EXP 32 NEW ID PRIMITIVE EXP 33 LENGTH NAME Procure adicionar ao parser um código claro e simples para a construção e encadeamento dos nodos acima Escolha qualquer estrutura de dados para implementar a árvore Mas lembrese que a análise semântica deverá percorrêla eficientemente encontrando padrões sintáticos Esse módulo poderá ser desenvolvido em C de forma orientada a objetos use somente construções permitidas em Java Os construtores a seguir exemplificam uma implementação em Java package ArvoreSintaxe ProgramClassList ClassListIdentifier Id VarList att MethodList m Identifier parent ClassList next Typeint primitive Identifier id VarListType t Array a IdList l VarList next IdListIdentifier id Array a IdList next MethodListint type Identifier id VarList formal VarList localvar StmtList sl MethodList next StmtListStatement s StmtList next ExpListExp e Explist next abstract class Statement extends Statement IfExp e Statement s1 Statement s2 whileExp e Statement s1 abstract class Exp extends Exp AssignName v Exp e CallName id ExpList el IdentifierString s NameName base Identifier id Exp index Numberfloat n Numberint n Literal String literal AdditionOpint op Exp e1 Exp e2 RelationalOpint op Exp e1 Exp e2 NotExp e EXEMPLO o código Java para montar a árvore da sentença if a b m else cg k 1 seria algo como Exp l new RelationalOp LESSTHAN new Identifiera new Identifierb Exp a new AdditionOpPLUS new Identifierk new Number1 Exp m new NameNULL new Identifierm Exp g new Namenew NameNULL Identifierc NULL new Identifierg NULL Statement s1 new Callm NULL Statement s2 new Assigng a Statement s new Ifl s1 s2 Entrada e saída do compilador Você deve imprimir TODO nãoterminal de sua gramática LL1 que estiver sendo processado e TODO terminal que for casado com o token de entrada Por exemplo dado o seguinte programa class mainclass public static void main int i x 5 h O parser deve mostrar como saída algo como o seguinte usando a GLC Java Program ClassDecl MATCH CLASS MATCH IDmainclass MATCH OPENBRA LocalDecl MethodDecl MATCH PUBLIC MATCH STATIC MATCH VOID MATCH IDmain Array MATCH OPENPAR FormalList MATCH CLOSEPAR MATCH OPENBRA VarDecl Type MATCH INT Array IdList MATCH ID Array MATCH SEMICOLON VarDecl StmtList Stmt Expr Primary MATCH IDx MATCH ASSIGN Expr Expr Primary MATCH NUMBER5 BinOp MATCH MINUS Expr Primary MATCH IDh MATCH SEMICOLON MATCH CLOSEBRA LocalDecl MATCH CLOSEBRA MATCH EOF Crie uma interface com o padrão de programação Visitante Visitor para gerar uma impressão hierárquica dos nodos da árvore Por exemplo a sentença if a b m else cg k 1 poderia resultar em IF LESSTHAN IDa IDb CALL NAME IDm ASSIGN NAME NAME IDc IDg ADDOP IDk NUMBER1 Prazo e avaliação Lembrese que este projeto é o principal elemento de avaliação do curso Uma documentação de alta qualidade técnica formal e de escrita é importante O código fonte deve estar correto muito bem documentado mas muito mesmo e deve ser eficiente Todos os grupos não têm permissão de possuir ou manter consigo o código ou os resultados de outro grupo É aconselhável que os grupos mantenham sigilo sobre suas soluções Qualquer indício de cópia será considerado fato grave contra todos os grupos envolvidos e a pena será a anulação de TODAS AS NOTAS DE TRABALHO no semestre A avaliação do grupo depende de Atendimento ao que foi solicitado Resultados práticos Qualidade da documentação Qualidade do código Pontualidade na entrega Apresentação de no mínimo 30 minutos demonstrando as funcionalidades do compilador Criatividade na resolução dos problemas Criatividade em ir além do mínimo mas somente após alcançar o mínimo A avaliação individual depende de Peso dado a cada um dos participantes como consenso do próprio grupo A soma dos pesos deve ser um Presença e participação em todas as aulas e durante toda a aula Destaque no grupo Ter peso maior do que os outros participantes Destaque na apresentação do compilador A avaliação da classe depende de Diferença entre a maior e a menor nota dos grupos Diferença entre a maior e a menor nota individual Apresentações dos grupos A apresentação deverá ser feita no momento da entrega da documentação PRAZOS O prazo máximo para a entrega e a apresentação é dia 21 de novembro de 2023 após o horário da aula se houver Penalidade por dia de atraso corridos 3 pontos Funcionalidades opcionais Não adicione funcionalidades opcionais antes que a solução básica esteja completa e correta Uma implementação incompleta das funcionalidades obrigatórias mais adicionais resultará em uma nota menor do que uma implementação completa sem nenhuma característica extra A seguir há alguns exemplos de adicionais que vocês podem considerar Laços do tipo for Gramática JAVA Program ClassDecl Program ClassDecl ClassDecl class ID LocalDecl class ID extends ID LocalDecl LocalDecl MethodDecl LocalDecl VarDecl LocalDecl epsilon VarDecl Type Array IdList VarDecl epsilon IdList ID Array IdList ID Array Array Array epsilon MethodDecl public Type ID Array FormalList VarDecl StmtList public static void ID Array FormalList VarDecl StmtList FormalList Type Array ID Array FormalRest epsilon FormalRest Type Array ID Array FormalList epsilon Type int float boolean double char ID StmtList Stmt Stmt StmtList Stmt if Expr Stmt else Stmt if Expr Stmt while Expr Stmt Systemoutprintln ExprList Systeminread Expr Expr Expr return Expr StmtList break switch Expr CaseBlock Expr ExprList CaseBlock case NUM StmtList CaseBlock case NUM CaseBlock ExprList epsilon ExprListTail ExprListTail Expr Expr ExprListTail Expr Primary UnaryOp Expr Expr BinOp Expr Expr Expr Primary ID NUM LITERAL LITERALCHAR Expr Expr ID Expr ExprList Expr ArrayList Exprlength new Type ArrayList new Type ExprList true false this ArrayList Expr ArrayList epsilon UnaryOp BinOp Correção da Gramática e Explicação dos Erros 1 ExprList e CaseBlock Erro A regra ExprList tinha um loop infinito pois ExprListTail poderia gerar Expr ou ExprListTail e ExprList poderia gerar ExprListTail ou ϵ Isso cria um loop onde ExprList pode continuar gerando indefinidamente Correção ExprList Expr ExprListTail ϵ ExprListTail Expr ExprListTail ϵ Erro A regra CaseBlock também tinha um problema semelhante CaseBlock1 poderia gerar StmtList CaseBlock ou CaseBlock o que poderia levar a um loop infinito Correção CaseBlock case NUM StmtList CaseBlock ϵ 2 Regras de Operadores Erro Existiam regras redundantes como Op0 Op11 Op22 etc que tornavam a gramática mais complexa do que o necessário Correção Simplificamos as regras combinandoas em uma única regra para cada operador Por exemplo Expr Op Expr Expr Op Expr ϵ Op Op1 Op Op Op1 Op ϵ 3 Recursão à Esquerda Erro A gramática original tinha recursão à esquerda o que não é adequado para análise descendente Correção Removemos a recursão à esquerda reescrevendo as regras Por exemplo Expr Op Expr Expr Op Expr ϵ 4 Regra Expr1 Erro A regra Expr1 tinha uma produção que gerava Primary1 Expr1 o que poderia levar a um loop infinito Correção Expr1 ID Expr1 ExprList Expr1 ArrayList Expr1 length Expr1 ϵ Resumo dos Erros 1 Loops Infinitos Algumas regras como ExprList e CaseBlock tinham loops infinitos devido à forma como foram escritas 2 Redundância As regras de operadores eram redundantes e podiam ser simplificadas 3 Recursão à Esquerda A gramática tinha recursão à esquerda que foi removida para tornála adequada para análise descendente Na próxima página irei adicionar sua gramática com todas as correções acima citadas Gramática Corrigida Program ClassDecl Program1 Program1 Program ϵ ClassDecl class ID ClassDecl1 ClassDecl1 LocalDecl extends ID LocalDecl LocalDecl MethodDecl LocalDecl VarDecl LocalDecl ϵ VarDecl Type Array IdList VarDecl ϵ IdList ID Array Idlist1 Idlist1 ID Array ϵ Array Array ϵ MethodDecl public MethodDecl1 MethodDecl1 Type ID Array FormalList VarDecl StmtList static void ID Array FormalList VarDecl StmtList FormalList Type Array ID Array FormalRest ϵ FormalRest Type Array ID Array FormalRest ϵ Type int float boolean double char ID StmtList Stmt StmtList1 StmtList1 StmtList ϵ Stmt if Expr Stmt1 while Expr Stmt Systemoutprintln ExprList Systeminread Expr Expr return Expr StmtList break switch Expr CaseBlock Stmt1 else Stmt ϵ CaseBlock case NUM StmtList CaseBlock ϵ ExprList Expr ExprListTail ϵ ExprListTail Expr ExprListTail ϵ Expr Op Expr Expr Op ϵ Op Op1 Op Op Op1 ϵ Op1 Op2 Op1 Op1 Op2 ϵ Op2 Op3 Op2 Op2 Op3 Op3 ϵ Op3 Op4 Op3 Op3 Op4 Op4 Op4 Op4 ϵ Op4 Op5 Op4 Op4 Op5 Op5 Op5 ϵ Op5 Op6 Op5 Op5 Op6 Op6 Op6 Op6 ϵ Op6 Primary Primary Primary Primary Primary ID Expr1 NUM LITERAL LITERALCHAR Expr new Type Primary2 true false this Expr1 Primary1 ϵ Primary1 ID ExprList ArrayList length Primary2 ArrayList ExprList ArrayList Expr ArrayList ϵ Esta gramática corrigida aborda os problemas de loop infinito redundância e recursão à esquerda que foram identificados anteriormente Conjuntos FIRST e FOLLOW para a Gramática Corrigida Vamos calcular os conjuntos FIRST e FOLLOW para a gramática corrigida Conjuntos FIRST O conjunto FIRST de um símbolo é o conjunto de terminais que podem aparecer no início de uma string derivada desse símbolo 1 Program class 2 Program1 class ϵ 3 ClassDecl class 4 ClassDecl1 extends 5 LocalDecl public Type ϵ 6 VarDecl Type ϵ 7 IdList ID 8 Idlist1 ϵ 9 Array ϵ 10 MethodDecl public 11 MethodDecl1 Type static 12 FormalList Type ϵ 13 FormalRest ϵ 14 Type int float boolean double char ID 15 StmtList if while Systemoutprintln Systeminread ID return break switch ϵ 16 StmtList1 if while Systemoutprintln Systeminread ID return break switch ϵ 17 Stmt if while Systemoutprintln Systeminread ID return break switch 18 Stmt1 else ϵ 19 CaseBlock case ϵ 20 ExprList Op ϵ 21 ExprListTail ϵ 22 Expr Op 23 Expr ϵ 24 Op Op1 25 Op ϵ 26 Op1 Op2 27 Op1 ϵ 28 Op2 Op3 29 Op2 ϵ 30 Op3 Op4 31 Op3 ϵ 32 Op4 Op5 33 Op4 ϵ 34 Op5 Op6 35 Op5 ϵ 36 Op6 Primary 37 Primary ID NUM LITERAL LITERALCHAR new true false this 38 Expr1 ArrayList length ϵ 39 Primary1 ArrayList length 40 Primary2 ArrayList 41 ArrayList ϵ Conjuntos FOLLOW O conjunto FOLLOW de um símbolo é o conjunto de terminais que podem aparecer imediatamente após esse símbolo em uma string derivada 1 Program 2 Program1 3 ClassDecl class 4 ClassDecl1 class 5 LocalDecl 6 VarDecl public Type 7 IdList 8 Idlist1 9 Array ID 10 MethodDecl public Type 11 MethodDecl1 public Type 12 FormalList 13 FormalRest 14 Type ID 15 StmtList case 16 StmtList1 case 17 Stmt if while Systemoutprintln Systeminread ID return break switch case 18 Stmt1 if while Systemoutprintln Systeminread ID return break switch case 19 CaseBlock case 20 ExprList 21 ExprListTail 22 Expr 23 Expr 24 Op 25 Op 26 Op1 27 Op1 28 Op2 29 Op2 30 Op3 31 Op3 32 Op4 33 Op4 34 Op5 35 Op5 36 Op6 37 Primary ArrayList length 38 Expr1 39 Primary1 40 Primary2 41 ArrayList ArrayList length Estes são os conjuntos FIRST e FOLLOW para a gramática corrigida Se você tiver mais perguntas ou precisar de mais detalhes sobre uma parte específica por favor me avise Lembrese que mesmo com a correção de seus exercícios solicito que revise os itens e efetue a formatação de seu texto de acordo com a sua necessidade