CODEWITHSUNDEEP
lispracketgrammarbnf
user1680944
user1680944

Reputation: 567

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?

Upvotes: 1

Views: 1803

Answers (2)

soegaard
soegaard

Reputation: 31145

I recommend taking a look at this classic, recursive descent parser:

http://www.cs.indiana.edu/eip/compile/scan-numlist.ss

The example consists of a lexer for a small Scheme subset. It was used for he the Scheme compiler workshop in 1996.

http://www.cs.indiana.edu/eip/compile/

Upvotes: 1

John Clements
John Clements

Reputation: 17233

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))))

Upvotes: 1

Related Questions