Schedule

Hiroya Fujinami
Hiroya Fujinami
  • @makenowjust

Ph.D. student at SOKENDAI (NII, National Institute of Informatics). Researcher for information security and formal language. Ruby committer. I am the author of Regexp optimization to prevent ReDoS in Ruby 3.2.0.

Make Parsers Compatible Using Automata Learning

CRuby currently has two parsers, Prism and parse.y, and starting with Ruby 3.4, Prism has become the default parser. Prism is a new Ruby parser that claims to be highly compatible with the traditional parser, parse.y. But, how can we guarantee this compatibility? One formal (academic) solution to this problem is automata learning, an algorithm to infer an automata from a black-box system. Automata has some benefits, e.g., we can verify two automata are the same. Therefore, we can ensure that Prism and parse.y are the same if their automata obtained by automata learning are the same. In this talk, we provide an overview the automata theory and introduce an algorithm of automata learning called L*. We will also introduce the case study of how a compatibility issue in Prism was found using automata learning (ruby/prism#3035). We believe it will be an interesting talk as an application of the latest academic topics.