Tags:ABNF, ACL2, grammar, parsing and verification

Abstract:

Augmented Backus-Naur Form (ABNF) is a standardized formal grammar notation used in several Internet syntax specifications. This paper describes (i) a formalization of the syntax and semantics of the ABNF notation and (ii) a verified parser that turns ABNF grammar text into a formal representation usable in declarative specifications of correct parsing of ABNF-specified languages. This work has been developed in the ACL2 theorem prover.

A Formalization of the ABNF Notation and a Verified Parser of ABNF Grammars