如何使用 Lisp 表达 BNF？

Question

我想用 Lisp 表达一个用 BNF 写的语法规则。这是规则。需要注意的是，non-terminals用大写字母表示，终端用小写字母表示：

A -> a A b

我尝试使用 lisp 的 define 函数来定义该语法。但是，当我使用定义函数时，Lisp 要求我指定我定义的函数的 body。

   #lang racket
   (define (A a A b B)())

但是，如果我用以下内容填充 body：

   #lang racket
   (define (A a A b B)("Hello World"))

我没有收到任何错误。

我的问题是我是否应该在 body 中指定一些有助于我定义其他语法规则的内容，例如我是否应该在 A 的 body 中指定非终结符 B 的规则？如果 define () 函数不适合使用，还有哪些其他函数可以帮助我使用 Lisp 表示 BNF 语法？

Answer 1

也许我在这里误解了什么，但在我看来，您想将 EBNF 表示为一段数据。如果是这种情况，您可以简单地使用 s 表达式。

也许是这样的？

#lang racket

(define my-ebnf
  `((A (a A b))
    (Q (z z Q z))
    (T (A p Q))))

Answer 2

我建议看一下这个经典的递归下降解析器：

该示例包含一个用于小型 Scheme 子集的词法分析器。它在 1996 年被用于他的 Scheme 编译器研讨会。

How to express BNF using Lisp?