使用BNF的编译器编译器

Question

为什么没有直接使用BNF的解析器生成器？

我熟悉JavaCC和Antlr，最近还接触到了Parse2。似乎每一个都有它自己的符号。BNF非常容易阅读，而其他符号则不容易。是不是有什么内在的原因导致我不能将BNF提供给编译器编译器并得到解析树呢？

Answer 1

为什么没有直接使用BNF的解析器生成器？

不，但大多数解析器生成器都是从尝试做所有事情开始的。社区花了很长时间才明白有时少即是多。

使用BNF (一些变体)的工具已经存在很长时间了。

早在1963年，一篇描述MetaII的论文就发表了。MetaII的基线BNF是你所期望的(左侧加上右侧)，加上一些现在相对标准的EBNF扩展(Kleene Star和Plus，Groupting，alternatives)和非标准的嵌入式操作(用于生成字面上的语法制导的翻译输出)。它采用内置的令牌词法分析器。MetaII可以对自己的语法进行元编译，以准确地复制自己的语法。这篇论文展示了这一点，当你摸索为什么它有效时，这是一个令人兴奋的时刻，从而使引导到更复杂的版本。并编译其他简单的语言。一个常见的简单扩展是为词法标记定义语法规则。早在20世纪70年代，我就构建了各种实现，以及使用它的工具，因为它太酷了，太有用了。

Tree Meta添加了用于构建树的操作，以及用于模式匹配树生成输出的辅助语法。

当您添加所有额外的EBNF和生成内容时，MetaII和Tree Meta的结果"BNF“对于外行来说可能相当难阅读，主要是因为它很密集，并且您必须熟悉上下文。否则，它看起来就像一个链式打印机的输出(对于那些知道这是什么的人来说)是坏的。

大多数现代编译器-编译器并没有太大的不同。YACC使用嵌入式(您最喜欢的语言)代码扩展了BNF来执行操作，通常用于构建树。JavaCC使用扩展的BNF；使用JJTree，您可以构建AST。ANTLR 1/2/3还具有扩展的BNF，具有用于构建树的嵌入式操作。这使得他们和MetaII一样，呃，丑陋...40年来没有任何进展。

我们的DMS软件再工程工具包(参见我的简历)使用了你能想象到的最简单的BNF，用于真正复杂的语法，如IBM Enterprise COBOL、Fortran 2005和C++14。

  LHS = RHS1 RHS2 ...  RHSn ;

对于各种令牌，LHS，RHS1 ...RHSn。列表很简单:您使用两个规则，一个用于基本情况，另一个用于列表扩展。替代方案很简单:编写另一个规则。从技术上讲，简单地将令牌的语法规则编码为其终端是实际字符的语法规则是很简单的。(由于解析速度的原因，DMS提供了一个真正的词法分析器，我们通常使用它)。

这是一个DMS BNF，适用于高中代数(还有一点微积分；一些符号方面的自由)：

equation = sum ;
sum = product ;
sum = sum '+' product ;
sum = sum '-' product ;
product = term ;
product = product '*' term ;
product = product '/' term ;
term = primary ;
term = primary '^' term ;
primary = NUMBER ;
primary = NAME ;
primary = '(' sum ')' ;
primary = '-' primary ;
primary = NAME '(' sum ')' ;
primary = 'D' NAME ':' primary ; -- differentiate primary
primary = 'I' sum 'D' NAME ; -- indefinite integral
primary = 'I' sum ',' sum ':' sum 'D' NAME ; -- definite integral

一个真正的DMS语法文件有其他的东西可以用来描述漂亮的打印等等。在这里你可以看到a bigger example of a DMS grammar for M6809 assembly code。

有趣的是，DMS只使用语法作为指导来构建as；没有额外的树构建操作。通过避免指定边解析边操作(构建树节点)的需要，生成的语法非常容易阅读。

DMS大约从1998年就开始这样做了；据我所知，它是第一个采用这种方法的工具。ANTLR的人最终发现这是一个好主意，现在ANTLR4从2013年开始将构建一个没有任何显式嵌入式操作的树，尽管它仍然有用于其他目的的操作。DMS的树可以是concrete (following the grammar directly) or "abstract" (许多树节点被丢弃，因为它们可以由DMS按需重建，具有抽象树和语法)。抽象的树实际上是相当不错的。我不知道ANTLR4在这里做什么。

这种方法真正的好处是，人们可以通过简单地修改规则来编写和修改非常复杂的、大型的语法；ASTs的构造是“自由的”，并且在语法方面总是“正确的”。这使得DMS可以提供各种其他相关的工具(漂亮的打印，源码到源码级别的转换)，并将其作为基准。(从技术上讲，DMS是一种“元”编译器，因为它可以使用自己的语法来解析自己的语法；我们使用DMS的这一功能来生成那些语法所隐含的语法分析器)。

你可以在“代数作为dms领域”上看到一个完整的例子，也可以通过我的简历。( BNF是从那里取来的)。我会提供链接，但很多人不喜欢这样。

Answer 2

Marpa::R2是Marpa的Perl接口，是一个通用的BNF解析器，它接受直接的BNF作为语法描述，并用Perl语言生成一个解析器。这是一个几乎从字面上取自BNF grammar tutorial的例子。

<tree>  ::= '(' <list> ')'
<list>  ::= <thing> | <list> ',' <thing>
<thing> ::= <tree> | <name>             
<name>  ::= 'ant' | 'bat' | 'cow' | 'dog' | 'cat'

The full code example.

Answer 3

看看这个：https://bnfc.digitalgrammars.com/

什么是BNF转换器？

BNF转换器是一个编译器构造工具，从标记的BNF语法生成编译器前端。它目前能够生成C、C++、C#、Haskell、Java和OCaml，以及XML表示。

给定标记的BNF语法，该工具生成：·抽象语法实现·同一语言中抽象语法的用例框架·Alex、JLex或Flex lexer生成器文件·Happy、CUP或Bison解析器生成器文件·作为Haskell/Java/C++/C模块的漂亮打印机·包含语言的可读规范的Latex文件

这个开源软件看起来也很有前途：https://github.com/navstev0/nodebnf

BNF既是一个解释器、编译器的框架，也是一个语言解析器。它可以使用BNF、ABNF或两者的混合。之前的版本使用了一个自定义的JavaScript标记，它是在BNF之后成型的来解释脚本文件，为了支持内联编译，这个功能被删除了。

Ant这里是一个开源的C++：https://github.com/chsu16/BNF-Compiler#bnf-compiler

flex编译器一个上下文无关的文法编译器，用

编写，带有C++ /bison。实现了词法分析器、LALR解析器、抽象语法树、符号表的类型检查和代码生成。这个项目是在加州大学洛杉矶分校的编译器设计类上构建的。