Search code examples
lispracketgrammarbnf

How to express BNF using Lisp?


I want to express a grammar rule that is written in BNF using Lisp. here is the rule. It is important to note that non-terminals are represented in capital letters and the terminals are represented in small letters:

A -> a A b

I tried to use the define function of lisp to define that grammar. However when I use a define function Lisp obliges me to specify the body of the function that I defined.

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

However if I fill the body with whatever like:

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

I don't get any error.

My question here is whether I should specify something in the body that will help me define other rules of the grammar, for example should I specify in the body of A the rule for the non terminal B? If that define () function is not the right one to use, what other function(s) would help me represent that BNF grammar using Lisp?


Solution

  • Perhaps I'm misunderstanding something here, but it seems to me that you want to represent an EBNF as a piece of data. If this is the case, you could simply use an s-expression.

    Something like this, perhaps?

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