brag: a better Racket AST generator
raco pkg install brag-lib
1 Quick start
展示了一个小例子:
#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留用的
- 明面字符串可以匹配字符串自己,或者一个类型子域包含那个字符串的记号结构。举例,“FOO”可以匹配“FOO”,或者
- 单个规则标识符
- 单个选择模式:通过
|
分隔的模式序列 - 单个数目化的模式:一个模式后面跟着*(零或者多个),?(零或者一个),+(一或者多个)。也可以使用花括号表示具体的数目,如
{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等等