在可信编译器设计中实践CompCert编译器的语法分析器形式化验证过程  

Experiment on Formal Verification Process of Parser of CompCert Compiler in Trusted Compiler Design

作　　者：李凌[1] 李璜华 王生原[1] LI Ling;LI Huang-hua;WANG Sheng-yuan(Department of Computer Science and Technology,Tsinghua University,Beijing 100084,China)

机构地区：[1]清华大学计算机科学与技术系,北京100084

出　　处：《计算机科学》2020年第6期8-15,共8页Computer Science

基　　金：核高基重大专项(2017ZX01030-301-003)。

摘　　要：Jourdan等在其2012年发表的论文“Validating LR(1)Parsers”中提出了一种形式化验证语法分析器的方法,并将其成功地应用于CompCert编译器(2.3以上版本)的语法分析器验证中。借助这种方法,文中完成了L2C项目中的Lustre*语言语法分析器的形式化验证,实现了开源L2C编译器前端语法分析器的两个选项之一。首先对这一语法分析器的实现进行了论述,其中包括有参考价值的技术细节;随后分析了该语法分析器的运行性能及正确性;最后对如何将这一方法推广至更一般的应用场景进行了总结。Jourdan and others presented a method to formally verify a parser in their paper Validating LR(1)Parsers published in 2012,and successfully applied it to the parser verification of CompCert compiler(version 2.3 and above).With this method,formal validation of the Lustre*parser is completed,which is a part of the Open L2C project,and one of the two options of the front-end parser of the Open L2C compiler is implemented.Firstly,this paper discussesthe implementation of the parser,inclu-ding some valuable technical details.Thenit analyzes the running performance and correctness of the parser.And finally,how to apply this method tomore general parsersis summarized.

关 键 词：语法分析 LR(1)分析器 形式化验证 Lustre*语言 CompCert COQ 

分 类 号：TP314[自动化与计算机技术—计算机软件与理论]