Defesa de doutorado de Elton Máximo Cardoso dia 21/02/2025 às 14h

Defesa de doutorado do discente Elton Máximo Cardoso

Título: A Typed Approach For Parsing Expression Grammar Termination

Resumo: Parsing Expressions Grammars (PEGs) are recognition formalism proposed by
Brian Ford to describe top-down recursive parsers. Unfortunately, to determine
whether an arbitrary PEG will terminate when parsing an input is an undecidable
problem. As termination is a desired property for parsing tools, Ford proposes a
well-formedness test that guarantees every PEG that satisfies it, terminates on any
input. The well-formedness test proposed by Ford is computed as a fixpoint to ensure
that every expression of a PEG is well-formed. However, in our view, this notion
could be more simple and predictable if it was expressed as a type system. The aim
of this work is to provide an alternative semantic formulation for PEGs which is
based on type theory. More specifically, we intend to show that the well-known type
soundness property for our type system for PEGs is essentially a well-formedness
property, since the type system is sound with respect to Ford's original formulation.

• Data: 21/02/2025
• Horário: 14:00h
• Link: meet.google.com/uku-dqcp-dxy
• Banca examinadora
• Prof. Rodrigo Geraldo Ribeiro (Orientador, DECOM-UFOP)
• Prof. Leonardo Vieira dos Santos Reis (Co-orientador, UFJF)
• Prof. Reinaldo Silva Fortes (DECOM-UFOP)
• Profa. Karina Girardi Roggia (UDESC)
• Prof. Cristiano Damianni Vasconcellos (UDESC)
• Prof. Samuel da Silva Feitosa (UFFS)