Thank you for your comment

Beau­tiful Racket / racket school 2019

Day 3

Powerful points

Fancier lexing for lexing fanciers.

(define-lex-abbrev regex-chars (char-set "()*+?.^$|<!=[]"))

(define lex
  (lexer
   [(:+ "\n") (token 'NEWLINE lexeme)]
   [(from/stop-before ";" "\n") (token 'COMMENT #:skip? #t)]
   [(:+ whitespace) (token 'SP lexeme #:skip? #t)]
   [regex-chars lexeme]
   [alphabetic (token 'LITERAL lexeme)]))
1
2
3
4
5
6
7
8
9
(define-lex-abbrev regex-chars (char-set "()*+?.^$|<!=[]"))

(define lex
  (lexer
   [(:+ "\n") (token 'NEWLINE lexeme)]
   [(from/stop-before ";" "\n") (token 'COMMENT #:skip? #t)]
   [(:+ whitespace) (token 'SP lexeme #:skip? #t)]
   [regex-chars lexeme]
   [alphabetic (token 'LITERAL lexeme)]))
copy to clipboard

  1. The token struc­ture type lets us create a token that coop­er­ates specially with a brag parser. The first field of the struc­ture is the value matched in the grammar. But the second field of the struc­ture is the value inserted in the parse tree.

  2. SYMBOLIC-NAMES (in all caps) are used to clas­sify a set of tokens (like iden­ti­fiers, numbers, or strings). When used in the grammar, these names can be refer­enced without surrounding quotes:

    #lang brag
    top : ("x" | FOO)+
    1
2
    #lang brag
top : ("x" | FOO)+
    copy to clipboard

    We make a token with a symbolic name by passing a symbol as the first argu­ment, and the token value as the second:

    (token 'FOO 42)
    1
    (token 'FOO 42)
    copy to clipboard

    So when we feed these tokens to our parser:

    (parse-to-datum (list "x" (token 'FOO 42)))
    1
    (parse-to-datum (list "x" (token 'FOO 42)))
    copy to clipboard

    We get this result:

    '(top "x" 42)
    1
    '(top "x" 42)
    copy to clipboard

  3. The lexer supports many useful matching oper­a­tors, e.g. :+, from/stop-before, char-set, and alphabetic.

  4. define-lex-abbrev lets us assign names to lexer patterns. This can be handy for defining a set of “reserved” char­ac­ters that are assigned special meaning in our language.

  5. token struc­tures with #:skip? #t are ignored by a brag parser.

Mission

Make a language called algebra that can eval­uate the following source. Imple­ment f and g as func­tions; imple­ment f(zz,zz) and g(10) and g(23) as func­tion appli­ca­tions. # denotes a line comment.

Don’t worry about gener­al­izing the grammar (we’ll do that in the next project). Just make it good enough to run the sample.

Example:

algebra/test.rkt
#lang algebra
fun f(x,y) = x + y
# fun f(x,y) = x * y
fun g(zz) = f(zz,zz)
g(10)
g(23)
1
2
3
4
5
6
#lang algebra
fun f(x,y) = x + y
# fun f(x,y) = x * y
fun g(zz) = f(zz,zz)
g(10)
g(23)
copy to clipboard

Result:

20
46
1
2
20
46
copy to clipboard

Hint: Starter files:

algebra/main.rkt
#lang br/quicklang
(require brag/support "grammar.rkt")
(provide top fun expr app)

(module+ reader
  (provide read-syntax))

(define-lex-abbrev reserved-toks
  (:or #;···))

(define tokenize-1
  (lexer
   [whitespace #;···]
   [(from/stop-before "#" "\n") #;···]
   [reserved-toks #;···]
   [(:+ alphabetic) #;···]
   [(:+ (char-set "0123456789")) #;···]))

(define-macro top #;···)

(define-macro-cases fun
  #;···)

(define-macro-cases expr
  #;···)

(define-macro app #;···)

(define (read-syntax src ip)
  (define parse-tree (parse src (λ () (tokenize-1 ip))))
  (strip-bindings
   (with-syntax ([PT parse-tree])
     #'(module algebra-mod algebra
         PT))))
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#lang br/quicklang
(require brag/support "grammar.rkt")
(provide top fun expr app)

(module+ reader
  (provide read-syntax))

(define-lex-abbrev reserved-toks
  (:or #;···))

(define tokenize-1
  (lexer
   [whitespace #;···]
   [(from/stop-before "#" "\n") #;···]
   [reserved-toks #;···]
   [(:+ alphabetic) #;···]
   [(:+ (char-set "0123456789")) #;···]))

(define-macro top #;···)

(define-macro-cases fun
  #;···)

(define-macro-cases expr
  #;···)

(define-macro app #;···)

(define (read-syntax src ip)
  (define parse-tree (parse src (λ () (tokenize-1 ip))))
  (strip-bindings
   (with-syntax ([PT parse-tree])
     #'(module algebra-mod algebra
         PT))))
copy to clipboard
algebra/grammar.rkt
#lang brag

top : # ···
fun : # ···
expr : # ···
app : # ···
1
2
3
4
5
6
#lang brag

top : # ···
fun : # ···
expr : # ···
app : # ···
copy to clipboard

Hint: In the lexer, assign symbolic token names to your iden­ti­fiers (like ID) and inte­gers (like INT).

Hint: In the lexer, make tokens with #:skip #true to ignore parts of the source that serve no purpose. (For instance, white­space and comments.) Then you don’t have to handle them in the grammar.

Hint: In the grammar, use cuts to remove tokens that serve no further purpose. (For instance, reserved tokens can often be discarded.) Then you don’t have to handle them in the expander.

Hint: You don’t need to imple­ment multi­pli­ca­tion to run the test file. (Do you see why?)

Hint: In the expander, you can leverage inter­po­si­tion points. For instance, if you need a macro called app that handles func­tion appli­ca­tions in your program, you could do:

(define-macro (app ARG ...) #'(#%app ARG ...))
1
(define-macro (app ARG ...) #'(#%app ARG ...))
copy to clipboard

Or equiv­a­lently:

(define-macro app #'#%app)
copy to clipboard

Hint: At the REPL, you can feed test cases to your tokenizer like so:

(apply-port-proc tokenize-1 "g(23)")
1
(apply-port-proc tokenize-1 "g(23)")
copy to clipboard

Result:

(list (token-struct 'ID 'g #f #f #f #f #f) "(" (token-struct 'INT 23 #f #f #f #f #f) ")")
1
(list (token-struct 'ID 'g #f #f #f #f #f) "(" (token-struct 'INT 23 #f #f #f #f #f) ")")
copy to clipboard

You can feed test cases to your parser like so:

(parse-to-datum (apply-port-proc tokenize-1 "g(23)"))
1
(parse-to-datum (apply-port-proc tokenize-1 "g(23)"))
copy to clipboard

Result:

'(top (app g 23))
1
'(top (app g 23))
copy to clipboard

Summary

A little knowl­edge is still dangerous.

← prev next →