extend racket syntax for backus-naur-forms

Question

I have a set of derivation rules implemented in racket. We can assume that there aren't any optional , which means there are no rules containing pipes (in BNF): ::= |

In racket, I have got something like this:

(define *rules*
  '((S . ("b" "a"))
    (B . ("a"))
    (C . (S B))))

Please note that terminal symbols are implemented in the form of racket strings, nonterminal symbols in the form of racket symbols. Now, I'd like to import this rules from another racket file containing rules in backus naur syntax:

S ::= ba
B ::= a
C ::= SB

(capital letter = nonterminal)

Therefore, I need to extend the racket syntax. I have no idea how to handle that. Can you help me? It shouldn't be that much code ...

Answer 1

I think you're looking to parse a file that's written using the BNF syntax, and produce an s-expression version; is that right?

If so, it shouldn't be hard. In particular, the format implied by your question is that every line is of the form

<NT> :: = [<NT>|<T>]*

... which you could take apart like this:

#lang racket

;; COPYRIGHT 2012 John B. Clements (clements@brinckerhoff.org)
;; Licensed under the Apache License, version 2.
;; (You're free to use it, but your source code has to include
;; my authorship.)

(require rackunit)

(define example
  (list "S ::= ba"
        "B ::= a"
        "C ::= SB"))

;; parse a single line:
;; string -> (list/c symbol? (listof (or/c string? symbol?)))
(define (parse-line l)
  (match (regexp-match #px"^([A-Z]) ::= ([A-Za-z]*)$")
    [(list _ lhs rhses)
     (list lhs (map parse-char (string->list rhses)))]))

;; parse a single char:
;; char -> (or/c symbol? string?)
(define (parse-char ch)
  .. oops! out of time. You'll have to write this part yourself... )

(check-expect (map parse-line example)
              '((S ("b" "a"))
                (B ("a"))
                (C (S B))))

Oops! I see a bug in there. No problem, you'll figure it out. Gotta run....