Please use this identifier to cite or link to this item:
http://repositorio.ufc.br/handle/riufc/82085| Type: | TCC |
| Title: | Gramática livre de contexto para tipagem de grafos em linguagem de programação |
| Authors: | Pinheiro, Alysson Lucas Braga |
| Advisor: | Rezende, Cenez Araújo de |
| Keywords in Brazilian Portuguese : | gramática livre de contexto;tipagem de grafos;sistemas de tipos;antlr4;verificação semântica |
| Keywords in English : | context-free grammar;graph typing;type systems;antlr4;semantic validation |
| Knowledge Areas - CNPq: | CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO |
| Issue Date: | 2025 |
| Citation: | PINHEIRO, Alysson Lucas Braga. Gramática livre de contexto para tipagem de grafos em linguagem de programação. 2025. Trabalho de Conclusão de Curso (Graduação em Ciência da Computação) - Campus de Russas, Universidade Federal do Ceará, Russas, 2025. |
| Abstract in Brazilian Portuguese: | Este Trabalho de Conclusão de Curso investiga, formaliza e valida uma Gramática Livre de Contexto (GLC) dedicada à tipagem estática de grafos, com vistas a suprir lacunas metodológicas em linguagens formais e compiladores orientados a grafos. A gramática foi especificada em Extended Backus–Naur Form (EBNF), convertida para Another Tool for Language Recognition (ANTLR 4) e acompanhada de uma semântica executável em Python, implementada via visitor pattern. Essa infraestrutura permite, em tempo de compilação, detectar usos de vértices e arestas sem declaração prévia, violação de cardinalidade, incompatibilidades típicas de multigrafos direcionados e ausência de atributos obrigatórios, além de identificar ciclos ou identificadores duplicados quando tais restrições são impostas. Do ponto de vista acadêmico, o trabalho contribui ao oferecer uma base teórica rigorosa que pode ser empregada tanto no ensino de Teoria de Grafos quanto em disciplinas de Compiladores e Linguagens Formais, servindo como caso de estudo completo — da definição lexical e sintática ao ciclo de análise semântica — para estudantes e pesquisadores. Ademais, a proposta estabelece um framework extensível que pode ser reutilizado em futuras linhas de pesquisa sobre sistemas de tipos para grafos, transformação de grafos baseada em regras, integração de grafos a DSLs e geração automática de código. A validação com um conjunto de onze casos de teste sintéticos evidenciou cobertura integral das regras gramaticais, reforçando a robustez do método e seu potencial como artefato de pesquisa replicável. |
| Abstract: | This work proposes the development of a context-free grammar for graph typing, aiming to formalize the characteristics of these structures in computational systems. The increasing complexity of graph-based systems, used in domains such as social networks, logistics systems, and data science, demands tools that ensure consistency and safety in handling these structures. The proposed grammar defines types for vertices and edges, as well as establishes composition rules and semantic validation. The project focuses on planning the grammar and modeling an interpreter capable of validating and inferring properties of graphs. It is expected that the future implementation of this proposal (in a subsequent thesis) will result in a formal and efficient approach to graph typing, contributing to the reliability of computational systems that rely on these structures. |
| URI: | http://repositorio.ufc.br/handle/riufc/82085 |
| Access Rights: | Acesso Aberto |
| Appears in Collections: | CIÊNCIA DA COMPUTAÇÃO - RUSSAS - Monografias |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| 2025_tcc_albpinheiro.pdf | 610,85 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.