Proceedings of ISP RAS

Certified Grammar Transformation to Chomsky Normal Form in F*

M.I. Polubelova (SPbU, Saint Petersburg, Russia)
S.N. Bozhko (SPbU, Saint Petersburg, Russia)
S.V. Grigorev (SPbU, Saint Petersburg, Russia)


Certified programming allows to prove that the program meets its specification. The check of correctness of a program is performed at compile time, which guarantees that the program always runs as specified. Hence, there is no need to test certified programs to ensure they work correctly. There are numerous toolchains designed for certified programming, but F* is the only language that support both general-purpose programming and semi-automated proving. The latter means that F* infers proofs when it is possible and a user can specify more complex proofs if necessary. We work on the application of this technique to a grammarware research and development project YaccConstructor. We present a work in progress verified implementation of transformation of Context-free grammar to Chomsky normal form, that is making progress toward the certification of the entire project. Among other features, F* system allows to extract code in F# or OCaml languages from a program written in F*. YaccConstructor project is mostly written in F#, so this feature of F* is of particular importance because it allows to maintain compatibility between certified modules and those existing in the project which are not certified yet. We also discuss advantages and disadvantages of such approach and formulate topics for further research.


certified programming; F*; program verification; context-free grammar; Chomsky normal form; grammar transformation; dependent type; refinement type


Proceedings of the Institute for System Programming, vol. 28, issue 2, 2016, pp. 127-138.

ISSN 2220-6426 (Online), ISSN 2079-8156 (Print).

DOI: 10.15514/ISPRAS-2016-28(2)-8

Full text of the paper in pdf Back to the contents of the volume