Skip to content

Instantly share code, notes, and snippets.

@danking
Created July 6, 2011 19:55
Show Gist options
  • Save danking/1068185 to your computer and use it in GitHub Desktop.
Save danking/1068185 to your computer and use it in GitHub Desktop.
A very simple example showing how to use Racket's lexing and parsing utilities
#lang racket
(require parser-tools/lex
(prefix-in re- parser-tools/lex-sre)
parser-tools/yacc)
(provide (all-defined-out))
(define-tokens a (NUM VAR))
(define-empty-tokens b (+ - EOF LET IN))
(define-lex-trans number
(syntax-rules ()
((_ digit)
(re-: (re-? (re-or "-" "+")) (uinteger digit)
(re-? (re-: "." (re-? (uinteger digit))))))))
(define-lex-trans uinteger
(syntax-rules ()
((_ digit) (re-+ digit))))
(define-lex-abbrevs
(digit10 (char-range "0" "9"))
(number10 (number digit10))
(identifier-characters (re-or (char-range "A" "z")
"?" "!" ":" "$" "%" "^" "&"))
(identifier (re-+ identifier-characters)))
(define simple-math-lexer
(lexer
("-" (token--))
("+" (token-+))
("let" (token-LET))
("in" (token-IN))
((re-+ number10) (token-NUM (string->number lexeme)))
(identifier (token-VAR lexeme))
;; recursively calls the lexer which effectively skips whitespace
(whitespace (simple-math-lexer input-port))
((eof) (token-EOF))))
(define-struct let-exp (var num exp))
(define-struct arith-exp (op e1 e2))
(define-struct num-exp (n))
(define-struct var-exp (i))
(define simple-math-parser
(parser
(start exp)
(end EOF)
(error void)
(tokens a b)
(precs (left - +))
(grammar
(exp ((LET VAR NUM IN exp)
(make-let-exp $2 (num-exp $3) $5))
((NUM) (num-exp $1))
((VAR) (var-exp $1))
((exp + exp) (make-arith-exp + $1 $3))
((exp - exp) (make-arith-exp - $1 $3))))))
(define (eval parsed-exp)
(match parsed-exp
((let-exp var num exp)
(eval (subst var num exp)))
((arith-exp op e1 e2)
(op (eval e1)
(eval e2)))
((num-exp n) n)
((var-exp i) (error 'eval "undefined identifier ~a" i))))
(define (subst var num exp)
(match exp
((let-exp var2 num2 exp2)
(if (eq? var var2)
exp
(let-exp var2 num2
(subst var num exp2))))
((arith-exp op e1 e2)
(arith-exp op
(subst var num e1)
(subst var num e2)))
((var-exp id)
(if (equal? id var)
num
exp))
((num-exp n) exp)))
(define (lex-this lexer input) (lambda () (lexer input)))
(let ((input (open-input-string "3 - 3.3 + 6")))
(eval (simple-math-parser (lex-this simple-math-lexer input))))
(let ((input (open-input-string "let foo 6 in 3 - 3.3 + foo")))
(eval (simple-math-parser (lex-this simple-math-lexer input))))
@wedesoft
Copy link

Hi! Thanks for your work. Very concise example :)

@kmicinski
Copy link

Thanks for the example here, Dan!

@danking
Copy link
Author

danking commented May 20, 2020

I just rediscovered this and realized it has thirty stars! This might be my highest impact piece of code 😉

@ali-bahjati
Copy link

ali-bahjati commented Jul 2, 2020

Hi,

Thank you for your great and informative code. However, there's a simple mistake in line 70 of the code, you should change eq to equal in order to make string comparison work. (Example showing this mistake: let foo 5 in let foo 7 in 3 - 3.3 + foo)

@Terkwood
Copy link

Still helping out newbies after so many years. Thanks for submitting this!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment