Functional programming languages are a neat tool to write parsers, especially when equipped with a pattern matching mechanism.<\/p>\n\n\n\n\n\n\n\n
Here’s the beginning of our SQL parser in memdb:<\/p>\n\n\n\n
(define<\/font> parse_sql (lambda<\/font> (s) (begin<\/font>\n \n (define<\/font> identifier (lambda<\/font> (s) (match s\n (regex "(?is)^`(.*)`(.*)"<\/font> _ id rest) '(<\/font>id <\/font>rest)<\/font>\n (regex "(?is)^([a-zA-Z_][a-zA-Z_0-9]*)(.*)"<\/font> _ id rest) '(<\/font>id <\/font>rest)<\/font>\n (error<\/b><\/font> (concat "expected identifier, found "<\/font> s))\n ))) \n \n (match s \n (regex "(?s)^\\\\s*(?m:--.*?$)(.*)"<\/font> _ rest) \/* comment *\/ (parse_sql rest)\n (concat "\\n"<\/font> rest) (parse_sql rest)\n (regex "(?is)^\\\\s+(.*)"<\/font> _ rest) (parse_sql rest)\n (regex "(?is)^CREATE(?:\\\\s|\\\\n)+TABLE(?:\\\\s|\\\\n)+(.*)"<\/font> _ rest) (match (identifier rest) '(<\/font>id <\/font>rest)<\/font> (concat "tablecreate "<\/font> id ", decl: "<\/font> rest) (error<\/b><\/font> "expected identifier"<\/font>))\n (error<\/b><\/font> (concat "unknown SQL syntax: "<\/font> s))\n ) \n))) <\/pre>\n\n\n\nAs you can see, you can nearly write EBNF syntax in scheme despite the exception that you are bound to left linearity.<\/p>\n\n\n\n
I extended scheme with the
match<\/code> instruction which takes the following parameters:<\/p>\n\n\n\n
(match value [pattern result] ... [default])<\/code><\/p>\n\n\n\nWhere
pattern<\/code> can be one of:<\/p>\n\n\n\n\n
\"string\"<\/code> matches string equality<\/li>\n\n\n\nvariable<\/code> matches any value and stores the value into the variable<\/li>\n\n\n\n(concat \"string\" variable)<\/code> splits away a fixed prefix<\/li>\n\n\n\n(concat variable \"string\" variable)<\/code> splits away a fixed infix<\/li>\n\n\n\n(concat variable \"string\")<\/code> splits away a fixed postfix<\/li>\n\n\n\n'(pattern pattern pattern ...)<\/code> matches only a list with the same amount of items and matching patterns<\/li>\n\n\n\n(regex \"pattern\" variable variable variable)<\/code> will parse the value as a regex and store all captured groups into variables<\/li>\n<\/ul>\n\n\n\nWhen a value matches the pattern, the result is evaluated. Matched variables can be used in the
result<\/code> expression. If no match has been found,default<\/code> is evaluated.<\/p>\n\n\n\nThis way, we can write parsers very intuitively, but also optimizers that traverse tree structure patterns become very easy to implement.<\/p>\n\n\n\n
<\/p>\n","protected":false},"excerpt":{"rendered":"
Functional programming languages are a neat tool to write parsers, especially when equipped with a pattern matching mechanism.<\/p>","protected":false},"author":2,"featured_media":4870,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_editorskit_title_hidden":false,"_editorskit_reading_time":0,"_editorskit_is_block_options_detached":false,"_editorskit_block_options_position":"{}","_uag_custom_page_level_css":"","footnotes":""},"categories":[129,128],"tags":[],"class_list":["post-4869","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-memcp","category-programming","single-item"],"featured_image_urls_v2":{"full":["https:\/\/launix.de\/launix\/wp-content\/uploads\/2023\/02\/data-5933101_1920.jpg",1920,1440,false],"thumbnail":["https:\/\/launix.de\/launix\/wp-content\/uploads\/2023\/02\/data-5933101_1920-150x150.jpg",150,150,true],"medium":["https:\/\/launix.de\/launix\/wp-content\/uploads\/2023\/02\/data-5933101_1920-300x225.jpg",300,225,true],"medium_large":["https:\/\/launix.de\/launix\/wp-content\/uploads\/2023\/02\/data-5933101_1920-768x576.jpg",751,563,true],"large":["https:\/\/launix.de\/launix\/wp-content\/uploads\/2023\/02\/data-5933101_1920-1024x768.jpg",751,563,true],"1536x1536":["https:\/\/launix.de\/launix\/wp-content\/uploads\/2023\/02\/data-5933101_1920-1536x1152.jpg",1536,1152,true],"2048x2048":["https:\/\/launix.de\/launix\/wp-content\/uploads\/2023\/02\/data-5933101_1920.jpg",1920,1440,false],"trp-custom-language-flag":["https:\/\/launix.de\/launix\/wp-content\/uploads\/2023\/02\/data-5933101_1920.jpg",16,12,false],"xs-thumb":["https:\/\/launix.de\/launix\/wp-content\/uploads\/2023\/02\/data-5933101_1920-64x64.jpg",64,64,true],"appku-shop-single":["https:\/\/launix.de\/launix\/wp-content\/uploads\/2023\/02\/data-5933101_1920.jpg",620,465,false]},"post_excerpt_stackable_v2":"
Functional programming languages are a neat tool to write parsers, especially when equipped with a pattern matching mechanism. Here’s the beginning of our SQL parser in memdb: (define parse_sql (lambda (s) (begin (define identifier (lambda (s) (match s (regex "(?is)^`(.*)`(.*)" _ id rest) '(id rest) (regex "(?is)^([a-zA-Z_][a-zA-Z_0-9]*)(.*)" _ id rest) '(id rest) (error (concat "expected identifier, found " s)) ))) (match s (regex "(?s)^\\\\s*(?m:–.*?$)(.*)" _ rest) \/* comment *\/ (parse_sql rest) (concat "\\n" rest) (parse_sql rest) (regex "(?is)^\\\\s+(.*)" _ rest) (parse_sql rest) (regex "(?is)^CREATE(?:\\\\s|\\\\n)+TABLE(?:\\\\s|\\\\n)+(.*)" _ rest) (match (identifier rest) '(id rest) (concat "tablecreate " id ", decl: " rest) (error…<\/p>\n","category_list_v2":"MemCP<\/a>, Programming<\/a>","author_info_v2":{"name":"Carl-Philip H\u00e4nsch","url":"https:\/\/launix.de\/launix\/en\/author\/carli\/"},"comments_num_v2":"0 comments","uagb_featured_image_src":{"full":["https:\/\/launix.de\/launix\/wp-content\/uploads\/2023\/02\/data-5933101_1920.jpg",1920,1440,false],"thumbnail":["https:\/\/launix.de\/launix\/wp-content\/uploads\/2023\/02\/data-5933101_1920-150x150.jpg",150,150,true],"medium":["https:\/\/launix.de\/launix\/wp-content\/uploads\/2023\/02\/data-5933101_1920-300x225.jpg",300,225,true],"medium_large":["https:\/\/launix.de\/launix\/wp-content\/uploads\/2023\/02\/data-5933101_1920-768x576.jpg",751,563,true],"large":["https:\/\/launix.de\/launix\/wp-content\/uploads\/2023\/02\/data-5933101_1920-1024x768.jpg",751,563,true],"1536x1536":["https:\/\/launix.de\/launix\/wp-content\/uploads\/2023\/02\/data-5933101_1920-1536x1152.jpg",1536,1152,true],"2048x2048":["https:\/\/launix.de\/launix\/wp-content\/uploads\/2023\/02\/data-5933101_1920.jpg",1920,1440,false],"trp-custom-language-flag":["https:\/\/launix.de\/launix\/wp-content\/uploads\/2023\/02\/data-5933101_1920.jpg",16,12,false],"xs-thumb":["https:\/\/launix.de\/launix\/wp-content\/uploads\/2023\/02\/data-5933101_1920-64x64.jpg",64,64,true],"appku-shop-single":["https:\/\/launix.de\/launix\/wp-content\/uploads\/2023\/02\/data-5933101_1920.jpg",620,465,false]},"uagb_author_info":{"display_name":"Carl-Philip H\u00e4nsch","author_link":"https:\/\/launix.de\/launix\/en\/author\/carli\/"},"uagb_comment_info":0,"uagb_excerpt":"Functional programming languages are a neat tool to write parsers, especially when equipped with a pattern matching mechanism.","_links":{"self":[{"href":"https:\/\/launix.de\/launix\/en\/wp-json\/wp\/v2\/posts\/4869","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/launix.de\/launix\/en\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/launix.de\/launix\/en\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/launix.de\/launix\/en\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/launix.de\/launix\/en\/wp-json\/wp\/v2\/comments?post=4869"}],"version-history":[{"count":1,"href":"https:\/\/launix.de\/launix\/en\/wp-json\/wp\/v2\/posts\/4869\/revisions"}],"predecessor-version":[{"id":4871,"href":"https:\/\/launix.de\/launix\/en\/wp-json\/wp\/v2\/posts\/4869\/revisions\/4871"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/launix.de\/launix\/en\/wp-json\/wp\/v2\/media\/4870"}],"wp:attachment":[{"href":"https:\/\/launix.de\/launix\/en\/wp-json\/wp\/v2\/media?parent=4869"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/launix.de\/launix\/en\/wp-json\/wp\/v2\/categories?post=4869"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/launix.de\/launix\/en\/wp-json\/wp\/v2\/tags?post=4869"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}