Beau­tiful Racket / racket school 2019

• 1 intro
• 2 taco compiler
• 3 the tacopoca­lypse
• 4 tacogram
• 5 taco victory

1. 

   A grammar describes the struc­ture of every syntac­ti­cally correct program in a language. It does not describe every seman­ti­cally correct program.

   

   Ques­tion (hard): is it possible to do that?

2. 

   A grammar is a sequence of produc­tion rules consisting of names (on the left) and patterns (on the right). By default, the parse starts with the first rule.

3. 

   The patterns are made of tokens (aka termi­nals) or names of produc­tion rules (aka nonter­mi­nals). These pattern elements can be further modi­fied with quan­ti­fiers, groups, or choice patterns.

4. 

   Possible gram­mars for US zip codes:

   zip-code : digit{5} ["-" digit{4}]
   digit : "0" | "1" | "2" | "3" | "4"
         | "5" | "6" | "7" | "8" | "9"

   1 2 3

   zip-code : digit{5} ["-" digit{4}] digit : "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"

   
   zip-code : beginning [middle] end
   beginning : digit digit
   middle : end "-" digit
   end : beginning digit
   digit : number | zero
   number : odd | even
   odd : "1" | "3" | "5" | "7" | "9"
   even : "2" | "4" | "6" | "8"
   zero : "0"

   1 2 3 4 5 6 7 8 9

   zip-code : beginning [middle] end beginning : digit digit middle : end "-" digit end : beginning digit digit : number | zero number : odd | even odd : "1" | "3" | "5" | "7" | "9" even : "2" | "4" | "6" | "8" zero : "0"

   
   

   Ques­tion: which is better? Why?

   

   Ques­tions (of no import): what is this grammar nota­tion called? Who is cred­ited with inventing the idea of a grammar?

5. 

   A grammar can be used as source code for #lang brag to generate a parser.

   #lang brag
   zip-code : digit{5} ["-" digit{4}]
   digit : "0" | "1" | "2" | "3" | "4"
         | "5" | "6" | "7" | "8" | "9"

   1 2 3 4

   #lang brag zip-code : digit{5} ["-" digit{4}] digit : "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"

   
   (parse-to-datum "01234-5678")

   1	(parse-to-datum "01234-5678")

   
6. 

   The result of a parse is a parse tree. Each leaf corre­sponds to the result of a produc­tion rule: it contains the name of the rule followed by the terminal elements matched to its pattern.

   '(zip-code (digit "0") (digit "1") (digit "2") (digit "3") (digit "4") "-" (digit "5") (digit "6") (digit "7") (digit "8"))

   1	'(zip-code (digit "0") (digit "1") (digit "2") (digit "3") (digit "4") "-" (digit "5") (digit "6") (digit "7") (digit "8"))

   
   

   Ques­tion: how do we know the parse tree only contains termi­nals?

   

   Ques­tion: what makes this output format excep­tion­ally conve­nient for makers of languages?

7. 

   A grammar in brag can be further anno­tated with cuts and splices to remove or merge elements.

   #lang brag
   zip-code : @digit{5} [/"-" digit{4}] ; splice and cut
   digit : "0" | "1" | "2" | "3" | "4"
         | "5" | "6" | "7" | "8" | "9"

   1 2 3 4

   #lang brag zip-code : @digit{5} [/"-" digit{4}] ; splice and cut digit : "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"

   
   (parse-to-datum "01234-5678")

   1	(parse-to-datum "01234-5678")

   
   '(zip-code "0" "1" "2" "3" "4" (digit "5") (digit "6") (digit "7") (digit "8"))

   1	'(zip-code "0" "1" "2" "3" "4" (digit "5") (digit "6") (digit "7") (digit "8"))

   
8. 

   A brag module exports two func­tions. parse applies the grammar to a list of tokens (or a token-producing thunk) and produces a syntax object. parse-to-datum does the same, but returns the parse tree as a raw datum rather than syntax object.

9. 

   Ques­tion: why is this grammar faulty?

   #lang brag
   foo : "x" bar
   bar : foo

   1 2 3

   #lang brag foo : "x" bar bar : foo

   
10. 

    Warning: brag won’t complain about ambiguous gram­mars.

    #lang brag
    top : foo | bar
    foo : "x"
    bar : "x"

    1 2 3 4

    #lang brag top : foo | bar foo : "x" bar : "x"

    
    

    Ques­tion: is this a bug or a feature?

11. 

    It’s possible to start a parse with some­thing other than the first rule. This is a tech­nique we can use to adjust how the REPL works for our language.

1. 

   16-bit binary numbers, like 0100101101101101

2. 

   US phone numbers, like (213) 555-6890

3. 

   CSS hex strings repre­senting grays, like "#ccc" and "#999999"

4. 

   CSS hex strings repre­senting any color, like "#f9c" and "#036a7e"

5. 

   Binary numbers that are palin­dromes, like 11 and 10010100100101001

6. 

   Binary numbers with an equal number of 0 and 1 digits, like 01101010000111

7. 

   Math expres­sions involving addi­tion and multi­pli­ca­tion (don’t forget about oper­ator prece­dence), like 1 + 2 * 3 + 4

tacogram/test.rkt

#lang tacogram
##$%#$%#$#$#$$##$%#$%#$#$#$$##$%#$#$#$%#$$##$#$#$%#$%%$#%#$%#$#$%%$##$#$%%#$%%$##$#$%%#$%%$#%%%%#$%%$##$#$#$#$#$%#$$#%%%#$%%%$#%%%%#$%%$##$%#$#$%%%$##$#$%%#$%%$##$#$%#$#$%%$##$%#$#$#$%#$$##$%#$%#$#$#$$##$#$#$%#$%#$$#%%#$%#$%#$$##$#$#$#$#$%#$$#%#$#$#$%%#$$##$#$#$#$#$%#$$##$#$#$%#$%#$$##$%#$%#$%#$$##$#$#$#$#$%#$$##$%#$#$%%#$$##$#$#$#$#$%#$$##$#$#$%#$%#$$#%#$%%#$%#$$##$#$#$#$#$%#$$##$#$#$%%%%$#%#$#$%#$%#$$#%#$#$%#$%#$$#%#$#$%#$%#$$

1 2

#lang tacogram ##$%#$%#$#$#$$##$%#$%#$#$#$$##$%#$#$#$%#$$##$#$#$%#$%%$#%#$%#$#$%%$##$#$%%#$%%$##$#$%%#$%%$#%%%%#$%%$##$#$#$#$#$%#$$#%%%#$%%%$#%%%%#$%%$##$%#$#$%%%$##$#$%%#$%%$##$#$%#$#$%%$##$%#$#$#$%#$$##$%#$%#$#$#$$##$#$#$%#$%#$$#%%#$%#$%#$$##$#$#$#$#$%#$$#%#$#$#$%%#$$##$#$#$#$#$%#$$##$#$#$%#$%#$$##$%#$%#$%#$$##$#$#$#$#$%#$$##$%#$#$%%#$$##$#$#$#$#$%#$$##$#$#$%#$%#$$#%#$%%#$%#$$##$#$#$#$#$%#$$##$#$#$%%%%$#%#$#$%#$%#$$#%#$#$%#$%#$$#%#$#$%#$%#$$



 
 
"hello world"
(+ 1 (* 2 (- x)))

1 2 3 4

"hello world" (+ 1 (* 2 (- x)))

tacogram/main.rkt

#lang br/quicklang
(require "grammar.rkt")

(module+ reader
  (provide read-syntax))

(define (tokenize ip)
  (for/list ([tok (in-port read-char ip)])
    tok))

(define (parse src toks)
  (define parse-tree-datum (parse-to-datum toks))
  (for/list ([leaf (in-list (cdr parse-tree-datum))])
    (integer->char
     (for/sum ([val (in-list (cdr leaf))]
               [power (in-naturals)]
               #:when (equal? val '(taco)))
       (expt 2 power)))))

(define (read-syntax src ip)
  (define toks (tokenize ip))
  (define parse-tree (parse src toks))
  (strip-context
   (with-syntax ([PT parse-tree])
     #'(module tacogram-mod tacogram
         PT))))

(define-macro (mb PT)
  #'(#%module-begin
     (display (list->string 'PT))))
(provide (rename-out [mb #%module-begin]))

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

#lang br/quicklang (require "grammar.rkt") (module+ reader (provide read-syntax)) (define (tokenize ip) (for/list ([tok (in-port read-char ip)]) tok)) (define (parse src toks) (define parse-tree-datum (parse-to-datum toks)) (for/list ([leaf (in-list (cdr parse-tree-datum))]) (integer->char (for/sum ([val (in-list (cdr leaf))] [power (in-naturals)] #:when (equal? val '(taco))) (expt 2 power))))) (define (read-syntax src ip) (define toks (tokenize ip)) (define parse-tree (parse src toks)) (strip-context (with-syntax ([PT parse-tree]) #'(module tacogram-mod tacogram PT)))) (define-macro (mb PT) #'(#%module-begin (display (list->string 'PT)))) (provide (rename-out [mb #%module-begin]))

tacogram/grammar.rkt

#lang brag

;; ···

1 2 3

#lang brag ;; ···



(parse-to-datum "\n##$%#$%#$#$#$$\n")

1	(parse-to-datum "\n##$%#$%#$#$#$$\n")



'(taco-program (taco-leaf (not-a-taco) (taco) (not-a-taco) (taco) (not-a-taco) (not-a-taco) (not-a-taco)))

1	'(taco-program (taco-leaf (not-a-taco) (taco) (not-a-taco) (taco) (not-a-taco) (not-a-taco) (not-a-taco)))

• 1 intro
• 2 taco compiler
• 3 the tacopoca­lypse
• 4 tacogram
• 5 taco victory