1 个不稳定版本
| 0.1.0 | 2023年3月25日 |
|---|
#2827 在 解析器实现
20KB
226 行
Blarse 是一个在 Rust 中构建的更轻量级的解析框架。实际上，它甚至很难被称为一个传统意义上的解析框架：它只是一个具有一些基本功能的标记树实现。
Blarse 中的解析树结构看起来像这样
int y = applyFunction ( ( double ) x ) ;
^^^ ^ ^ ^^^^^^^^^^^^^ ^ ^ ^^^^^^ ^ ^ ^ ^
Name Name Eq Name Open Open Name Close Name Close Semicolon
paren paren Paren Paren
^^^ ^ ^ ^^^^^^^^^^^^^ ^ ^^^^^^^^^^^^^^ ^ ^ ^
Name Name Eq Name Open Expr Name Close Semicolon
paren Paren
^^^ ^ ^ ^^^^^^^^^^^^^ ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ ^
Name Name Eq Name Expr Semicolon
^^^ ^ ^ ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ ^
Name Name Eq Expr Semicolon
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Statement
表面上看起来很难理解，最终结果看起来也相当晦涩。然而，在编写解析器时，我们可以反向查看这个过程。我们不是将两个名称、一个等号、一个表达式和分号组合成一个语句，而是简单地理解一个语句需要这些组件，然后看看这些规则是否适用。
和 Blex 一样，Blarse 通过在保持其类型不变的同时缓慢地转换数据来处理数据。Blex 将标记转换为从单个字符的薄包装开始，到更复杂的标记，这次作为词素的复杂和数据丰富的表示。同样，Blarse 将解析标记从简单的标记的薄层转换为更复杂的解析标记，构建成自上而下的树结构，以便清晰理解。
和Blex 一样，Blarse 的处理是通过一个特质的规则完成的。相关的边界是 Fn(Vec<ParseToken>) -> Vec<ParseToken>。和Blex 一样，可以修改这些解析标记，事实上，这是一种处理它们的惯用方法。
让我们来点 Lispy！
让我们创建一个名为 eval 的规则，它解析 Lisps 中看到的 S 表达式。我们将尝试解析 Quick Racket 介绍中的这个示例代码
(define (rgb-series mk)
(vc-append
(series (lambda (sz) (colorize (mk sz) "red")))
(series (lambda (sz) (colorize (mk sz) "green")))
(series (lambda (sz) (colorize (mk sz) "blue")))))
首先，我们需要一些词法分析代码来识别括号和单词。为此，我们将有四个简单的规则。
- 将任何空白标记为 "ws"。
- 将 "(" 和 ")" 标记为 "paren"。
- 将任何由括号或空白分隔的字符序列标记为 "word"。
- 删除任何空白。
这些可以将类似于 A (space) 的东西转换成
A: word;
(: (; paren;
space: word;
): ); paren;
接下来，我们需要创建一个解析规则。解析器应将所有S表达式（括号内的单词和S表达式）转换为它们自己的解析标记，将表达式的元素作为子节点。例如，A (space) 应转换为包含一个叶子标记和一个分支标记的解析标记，其中分支标记本身包含叶子标记 space。因此
A ("word")
("expr"):
space ("word")
实现此功能的最简单方法是迭代和递归的组合。函数应扫描解析标记中的左括号，然后是右括号。当这两个都找到时，函数应在括号之间的解析标记上递归调用自己，并将该结果包装在一个父解析标记中。
我们从典型的函数签名开始，给我们的函数一个简单的名字 eval
fn eval(mut pts: Vec<ParseToken>) -> Vec<ParseToken> {
...
}
我们将修改 pts 输入参数，而不是复制它。因此，我们可以在最后返回 pts。
fn eval(mut pts: Vec<ParseToken>) -> Vec<ParseToken> {
pts
}
在此之前，我们需要迭代我们的解析标记，如之前所述。我们可以使用状态机来跟踪是否找到了括号。这看起来可能像
A (deeply (nested) expression)
^ ^ ^
Left paren found! |
Left paren found!
Right paren found! (Execution complete)
这表明我们需要两个状态：未找到括号或找到一个左括号。我们可以使用布尔值来跟踪此状态，但更优雅的选项是存储最后一个找到的左括号的索引作为 Option<usize>。然后我们可以迭代 pts 中的索引，并在找到左括号时更新此值。
fn eval(mut pts: Vec<ParseToken>) -> Vec<ParseToken> {
let mut l_index: Option<usize> = None;
for i in 0..pts.len() {
if pts[i].has_tag("(") {
l_index = Some(i);
}
}
pts
}
现在我们只需要添加一个分支，当找到一个右括号且 l_index 是 Some 时触发。
fn eval(mut pts: Vec<ParseToken>) -> Vec<ParseToken> {
let mut l_index: Option<usize> = None;
for i in 0..pts.len() {
if pts[i].has_tag("(") {
l_index = Some(i);
} else if let Some(l) = l_index {
if pts[i].has_tag(")") {
...
}
}
}
pts
}
此分支应在 pts 的子集上递归调用 eval，从 l_index 到 i，不包括 i。然后它应该创建一个新的解析标记，将此调用的结果作为其子节点，然后将其插入到替换 pts 从 l_index 到 i 的子集的位置中。幸运的是，Rust 有一个内置函数可以帮助我们完成最后的部分，即 Vec::splice。
fn eval(mut pts: Vec<ParseToken>) -> Vec<ParseToken> {
let mut l_index: Option<usize> = None;
for i in 0..pts.len() {
if pts[i].has_tag("(") {
l_index = Some(i);
} else if let Some(l) = l_index {
if pts[i].has_tag(")") {
let pts_slice = pts[(l + 1)..i].to_vec();
let new_expr = ParseToken::new_branch_from_first(
eval(pts_slice),
vec!["expr"]);
pts.splice(l..=i, vec![new_expr]);
}
}
}
pts
}
第一行（以 let pts_slice 开头）定义了要评估的区域。然后我们在 new_expr 的初始化器中将它传递给 eval，确保将 expr 作为标签添加到新的解析标记中。然后我们调用这个有用的 splice 函数。
然而，这种行为并没有考虑到在相同嵌套级别上可能有多个S表达式的可能性。请记住，我们原始的状态机在找到一个右括号后终止。我们可以通过递归调用 eval 来实现相同的功能，并提前返回结果。
fn eval(mut pts: Vec<ParseToken>) -> Vec<ParseToken> {
let mut l_index: Option<usize> = None;
for i in 0..pts.len() {
if pts[i].has_tag("(") {
l_index = Some(i);
} else if let Some(l) = l_index {
if pts[i].has_tag(")") {
let pts_slice = pts[(l + 1)..i].to_vec();
let new_expr = ParseToken::new_branch_from_first(
eval(pts_slice),
vec!["expr"]);
pts.splice(l..=i, vec![new_expr]);
return eval(pts);
}
}
}
pts
}
由于括号不再包含在新表达式中，因此新表达式将被忽略，下一个对 eval 的调用将前进到下一个S表达式。让我们看看我们原始语料库（[[#Let's get Lispy!]])）上的结果。
("expr"):
define ("word")
("expr"):
rgb-series ("word")
mk ("word")
("expr"):
vc-append ("word")
("expr"):
series ("word")
("expr"):
lambda ("word")
("expr"):
sz ("word")
("expr"):
colorize ("word")
("expr"):
mk ("word")
sz ("word")
"red" ("word")
("expr"):
series ("word")
("expr"):
lambda ("word")
("expr"):
sz ("word")
("expr"):
colorize ("word")
("expr"):
mk ("word")
sz ("word")
"green" ("word")
("expr"):
series ("word")
("expr"):
lambda ("word")
("expr"):
sz ("word")
("expr"):
colorize ("word")
("expr"):
mk ("word")
sz ("word")
"blue" ("word")
()
虽然有点冗长，但没错！我们成功解析了一些Lisp代码。...只是结尾那个讨厌的空标记有点问题。我们可以使用另一个函数remove_last来处理这个问题。
fn remove_last(mut pts: Vec<ParseToken>) -> Vec<ParseToken> {
if pts.len() > 0 {
pts.remove(pts.len() - 1);
}
pts
}
我不会重复输出，但请相信那个令人烦恼的标记已经消失了。
依赖项
~22KB