brag: a better Racket AST generator

raco pkg install brag-lib

1 Quick start

Backus-Naur Form (BNF)

展示了一个小例子:

#lang brag

nested-word-list: WORD
| LEFT-PAREN nested-word-list* RIGHT-PAREN

2 Introduction

brag是一个解析器生成器

  • 为BNF语法提供#lang。也就是说#lang brag自动生成一个解析器
  • 一些约定:第一个生成式会被作为初始生成式,全大写的标识符被当作端子记号,其他标识符被当作非端子记号
  • 不对记号划定做约束,记号可以携带字符串、符号名,或者其他通过token建构的实例。如果记号提供源位置,则解析出的语句对象也会带有相同源位置。
  • 通常情况下可以处理模糊的语法
  • 可以和racket的语言工具栏整合

2.1 Example: a small DSL for ASCII diagrams

例子是这样的:

3 9 X;

6 3 b 3 X 3 b;

3 9 X;

2.2 Parsing the concrete syntax

BNF表达式是这样的:

#lang brag

drawing: rows*
rows: repeat chunk+ ";"
repeat: INTEGER
chunk: INTEGER STRING

使用br-parser-tools/lex来生成记号划分器。RAGG使用的是parser-tools/lex。

  • 生成的parse函数可以接受一个记号序列,或者一个能生成记号的函数
  • 记号可以是position-token结构,会保留位置信息
  • parse在遇到void或者’eof记号时终止
  • parse会跳过#:skip?属性为#t的记号

2.3 From parsing to interpretation

有趣,竟然使用syntax-parse来解析语法树。

2.4 From interpretation to compilation

编译和解释的差别是,编译会生成语法对象用于稍后执行,而解释则是立马执行的。

3 The language

3.1 Syntax and terminology

#lang brag由规则合集,以及单行注释还有多行注释组成。

  • 规则由规则标识符、分隔符(":“或者”::=")、以及一个模式构成
  • 规则标识符是非全大写标识符
  • 符号型记号标识符是全大写的标识符
  • 行注释以#或者;开头直到行尾
  • 多行注释以(*或者)*
  • 标识符是由字母、数字、以及"-.!$%&/<=>?^_~@“构成的序列。不能包含*, +, {, },这些被用来定量用的。
  • 单个模式由是以下之一
    • 隐式的以空白或者逗号分隔的模式序列
    • 单个端子:要么是个明面上的字符串,或者是一个符号型记号标识符
      • 明面字符串可以匹配字符串自己,或者一个类型子域包含那个字符串的记号结构。举例,“FOO”可以匹配“FOO”,或者(token "FOO" "bar")或者(token 'FOO "bar")
      • 符号型记号标识符可以匹配字符串的版本的标识符,或者类型子域包含标识符的记号。举例,FOO可以匹配“FOO”,(token "FOO" "bar")或者(token 'FOO "bar")
      • “error"是brag留用的
    • 单个规则标识符
    • 单个选择模式:通过|分隔的模式序列
    • 单个数目化的模式:一个模式后面跟着*(零或者多个),?(零或者一个),+(一或者多个)。也可以使用花括号表示具体的数目,如{2}{2,5}{2,}{,5}等等。
    • 一个可选模式,以方括号表示(上一条中的?具有相同含义)
    • 一个显示序列:以括弧()环绕的表达式
    • 空集,一个特殊的模式用来匹配零记号的连对。

本节有两三个例子可读。

3.2 Cuts & splices

可以剪除一些对解析无用的记号(如下面例子中的/'+'以及/'*'以及/factor

#lang brag
expr : term (/'+' term)*
term : factor (/'*' factor)*
/factor : ("0" | "1" | "2" | "3"
       |  "4" | "5" | "6" | "7"
       | "8"  | "9")+

拼接意味着可以将当前节点拼接到其环绕节点中,如下面例子中的@term以及@factor

#lang brag
expr : term (/'+' term)*
@term : factor (/'*' @factor)*
factor : ("0" | "1" | "2" | "3"
       |  "4" | "5" | "6" | "7"
       | "8"  | "9")+

剪除或者拼接的记号会作为语法辖属出现在相应的语法对象中。

3.3 Syntax errors

处于指定的语法不对以外,下列情况中brag也会抛出语句错误:

  • 不具有任何规则
  • 一个规则的左侧或者右侧和其他规则相同
  • 引用了未定义的规则
  • 使用了留用的记号名EOF
  • 一条规则不具有可解性,如:infinite-a: "a" infinite-a

3.4 Semantics

#lang brag会生成一个提供若干绑定过的模块:

  • parse
  • parse-to-datum
  • make-rule-parser
  • all-token-types

4 Support API

(require brag/support)

brag/support还提供br-parser-tools/lex模块的全部符号

  • token,创建一个token结构
  • token-struct
  • exn:fail:parsing
  • apply-port-proc
  • apply-lexer
  • apply-tokenizer-maker
  • trim-ends
  • (:* re ...)
  • (:+ re ...)
  • (:? re ...)
  • (:= n re ...)
  • (:>= n re ...)
  • (:** n m re ...)
  • (:or re ...)
  • (:: re ...)
  • (:: seq re ...)
  • (:& re ...)
  • (:- re ...)
  • (:~ re ...)
  • (:/ char-or-string ...)
  • (from/to open close)
  • (from/stop-before open close)

4.1 Differences with ragg

此包从ragg的分叉,最显著的差异:

  • 增加了剪除和拼接
  • 增加了新的描述语法的语句,比如注释以及分量化的模式
  • 支持REPL交互
  • 提供额外的便利,比如parse-to-datum, apply-lexer, trim-ends, from/to以及from/stop-before等等