3个版本
0.1.2 | 2023年1月2日 |
---|---|
0.1.1 | 2023年1月2日 |
0.1.0 | 2023年1月2日 |
#94 in 解析工具
4MB
11K SLoC
lang-pt
一种用于生成递归下降自顶向下解析器的语言解析器工具。
概述
为如JavaScript这样的语言编写的解析器通常由于语言的复杂性而手写定制。然而,编写定制的解析器代码通常会增加解析器开发和维护的成本。为了减少开发工作量,已创建了用于构建高级语言(HLL)解析器的库。此库的目标是开发一个灵活的库,以支持广泛的语法,同时与手写的解析器相比保持良好的性能。
设计
语言解析器通常是通过手动编写定制代码或使用解析器生成器工具开发的。当使用解析器生成器构建解析器时,语言的语法是在由生成器工具指定的领域特定语言(DSL)中实现的。然后,生成器将编译语法并生成目标运行时语言的解析器代码。然而,此解析器库使用一组生产工具来在Rust编程语言中实现语法。因此,而不是在生成器指定的语言中编写语法,可以使用诸如Concat、Union等工具来实现符号的连接和替代生产。
此解析工具还配备了Lookahead、Validator和非结构化等实用工具,以支持自定义验证、基于优先级的解析等。此解析库可用于解析需要将自定义功能注入语法的广泛语言。此外,库还包括如SeparatedList和Suffixes等生产工具,以简化语言的语法编写。
用法
我们将通过一个JavaScript表达式实现的示例来说明生成解析器的步骤。
标记化
标记类型
首先,我们将创建一个标记类型,它将表示标记流数据中每个元素的值。标记类型应实现TokenImpl特质,以便Tokenizer可以访问所需的默认文件结束(EOF)标记。默认EOF标记将被添加到标记流的末尾。我们将定义枚举类型,包含JavaScript表达式的各个部分,并实现TokenImpl特质。
use lang_pt::TokenImpl;
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
enum Token {
ID,
Number,
Add,
Sub,
Mul,
Div,
LT,
LTE,
GT,
GTE,
EQ,
Space,
Semicolon,
LineBreak,
EOF,
Assign,
OpenBrace,
CloseBrace,
OpenParen,
CloseParen,
OpenBracket,
CloseBracket,
}
impl TokenImpl for Token {
fn eof() -> Self { Self::EOF }
fn is_structural(&self) -> bool { todo!() }
}
构建标记化器
分词是一个预处理过程,其中输入文本文档被分割成一系列的标记。然后,解析程序将使用标记流输入并解析它们成一个有意义的抽象语法树(AST)。这个库可以被用来创建一个无词法分析器的LexerlessParser程序,从而不需要单独分配一个分词器。然而,词法分析器通常会使得解析程序比没有词法分析器的解析更快。在这个例子中,我们将创建一个DefaultParser程序,它从分词器获取分词后的输入。
在构建完整的JavaScript表达式分词器之前,我们首先将实现一个由数字、标识符和算术运算符组成的简单算术表达式的分词器。分词器由负责在输入的增量位置处创建标记的词素工具组成。查看词素API文档,以了解可用的词素工具及其功能概述。
use lang_pt::lexeme::{Pattern, Punctuations};
use lang_pt::Code;
use lang_pt::Lex;
use lang_pt::{ITokenization, Tokenizer};
use std::rc::Rc;
let identifier: Pattern<Token> = Pattern::new(Token::ID, r#"^[_$a-zA-Z][_$\w]*"#).unwrap();
let number_literal =
Pattern::new(Token::Number, r"^(0|[\d--0]\d*)(\.\d+)?([eE][+-]?\d+)?").unwrap();
let non_break_space = Pattern::new(Token::Space, r"^[^\S\r\n]+").unwrap();
let line_break = Pattern::new(Token::LineBreak, r"^[\r\n]+").unwrap();
let expression_punctuations = Punctuations::new(vec![
("+", Token::Add),
("-", Token::Sub),
("*", Token::Mul),
("/", Token::Div),
("<", Token::LT),
("<=", Token::LTE),
(">", Token::GT),
(">=", Token::GTE),
("==", Token::EQ),
("=", Token::Assign),
("{", Token::OpenBrace),
("}", Token::CloseBrace),
("(", Token::OpenParen),
(")", Token::CloseParen),
("[", Token::OpenBracket),
("]", Token::CloseBracket),
(";", Token::Semicolon),
])
.unwrap();
let tokenizer = Tokenizer::new(vec![
Rc::new(non_break_space),
Rc::new(identifier),
Rc::new(number_literal),
Rc::new(expression_punctuations),
Rc::new(line_break),
]);
let tokens1 = tokenizer.tokenize(&Code::from("a+b+c=d")).unwrap();
debug_assert_eq!(
tokens1,
vec![
Lex { token: Token::ID, start: 0, end: 1 },
Lex { token: Token::Add, start: 1, end: 2 },
Lex { token: Token::ID, start: 2, end: 3 },
Lex { token: Token::Add, start: 3, end: 4 },
Lex { token: Token::ID, start: 4, end: 5 },
Lex { token: Token::Assign, start: 5, end: 6 },
Lex { token: Token::ID, start: 6, end: 7 },
Lex { token: Token::EOF, start: 7, end: 7},
]
);
let tokens2 = tokenizer.tokenize(&Code::from("if(true){}")).unwrap();
debug_assert_eq!(
tokens2,
vec![
Lex { token: Token::ID, start: 0, end: 2 },
Lex { token: Token::OpenParen, start: 2, end: 3 },
Lex { token: Token::ID, start: 3, end: 7 },
Lex { token: Token::CloseParen, start: 7, end: 8 },
Lex { token: Token::OpenBrace, start: 8, end: 9 },
Lex { token: Token::CloseBrace, start: 9, end: 10 },
Lex { token: Token::EOF, start: 10, end: 10 }
]
);
关键字 & 常量
在第二个分词示例中,“if”和“true”是关键字,分别代表常量值。然而,我们当前的分词器将关键字和值分词为ID。因此,分词器应该更新,以便关键字和值产生适当的标记。让我们在标记类型中添加关键字和常量字段。
enum Token {
...
If,
Else,
While,
For,
True,
False,
Null,
Undefined,
}
现在,我们将映射分词后的ID到相应的关键字。因此,我们将用映射器包装标识符模式,以便它将关键字和值映射到相关的标记。
let identifier: Pattern<Token> = Pattern::new(Token::ID, r#"^[_$a-zA-Z][_$\w]*"#).unwrap();
let mapping_identifier = Mapper::new(
identifier,
vec![
("if", Token::If),
("else", Token::Else),
("while", Token::While),
("for", Token::For),
("true", Token::True),
("false", Token::False),
("null", Token::Null),
("undefined", Token::Undefined),
],
)
.unwrap();
...
let tokenizer = Tokenizer::new(vec![
Rc::new(non_break_space),
Rc::new(mapping_identifier),
Rc::new(number_literal),
Rc::new(expression_punctuations),
]);
...
let tokens2 = tokenizer.tokenize(&Code::from("if(true){}")).unwrap();
debug_assert_eq!(
tokens2,
vec![
Lex { token: Token::If, start: 0, end: 2 },
Lex { token: Token::OpenParen, start: 2, end: 3 },
Lex { token: Token::True, start: 3, end: 7 },
Lex { token: Token::CloseParen, start: 7, end: 8 },
Lex { token: Token::OpenBrace, start: 8, end: 9 },
Lex { token: Token::CloseBrace, start: 9, end: 10 },
Lex { token: Token::EOF, start: 10, end: 10 }
]
);
正则表达式文字
JavaScript语言的正则表达式文字由 /pattern/[g][m][i] 定义。以下词素工具可以用来解析JavaScript正则表达式文字。
let regex_literal = Pattern::new(
Token::RegexLiteral,
r"^/([^\\/\r\n\[]|\\.|\[[^]]+\])+/[gmi]*",
)
.unwrap();
然而,/pattern/可能是两个除法表达式序列的一部分。因此,我们将查看前一个标记以确定正则表达式文字是否在当前位置有效。
let validated_regex_literal = Middleware::new(regex_literal, |_, lex_stream| {
// Validate that latest position is not part of expression continuation.
lex_stream.last().map_or(false, |d| match d.token {
Token::ID | Token::Number | Token::CloseParen /* Parenthesis expr end.*/ => false,
_ => true,
})
});
// Adding Regex literal before punctuation.
let mut combined_tokenizer = CombinedTokenizer::new(
MAIN,
vec![
...
Rc::new(validated_regex_literal),
Rc::new(expression_punctuations_mixin),
],
);
状态
可能需要多个基于状态的分词器来解析像JavaScript模板文字这样的许多语言语法。因此,可以形成多个基于状态的CombinedTokenizer词法分析器来分词像JavaScript模板文字这样的语法。每个状态提供了一组词素工具,它们匹配特定状态的有关值或模式。
use lang_pt::lexeme::{Action, Mapper, Pattern, Punctuations, StateMixin};
use lang_pt::Code;
use lang_pt::Lex;
use lang_pt::TokenImpl;
use lang_pt::{CombinedTokenizer, ITokenization};
use std::rc::Rc;
const MAIN: u8 = 0;
const TEMPLATE: u8 = 1;
let expression_punctuations = Punctuations::new(vec![
...
("`", Token::TemplateTick),
])
.unwrap();
let expression_punctuations_mixin = StateMixin::new(
expression_punctuations,
vec![
(
Token::TemplateTick,
Action::Append { state: TEMPLATE, discard: false, `},
),
(
Token::OpenBrace,
Action::Append { state: MAIN, discard: false, `},
),
(Token::CloseBrace, Action::Pop { discard: false }),
],
);
let template_string: Pattern<Token> = Pattern::new(
Token::TemplateString,
r"^([^`\\$]|\$[^{^`\\$]|\\[${`bfnrtv])+",
)
.unwrap();
let template_punctuations = Punctuations::new(vec![
("`", Token::TemplateTick),
("${", Token::TemplateExprStart),
])
.unwrap();
let template_punctuation_mixin = StateMixin::new(
template_punctuations,
vec![
(Token::TemplateTick, Action::Pop { discard: false }),
(
Token::TemplateExprStart,
Action::Append { state: MAIN, discard: false },
),
],
);
let mut combined_tokenizer = CombinedTokenizer::new(
MAIN,
vec![
Rc::new(non_break_space),
Rc::new(mapped_id),
Rc::new(number_literal),
Rc::new(expression_punctuations_mixin),
],
);
combined_tokenizer.add_state(
TEMPLATE,
vec![
Rc::new(template_string),
Rc::new(template_punctuation_mixin),
],
);
let token_stream = combined_tokenizer
.tokenize(&Code::from("`Sum is ${a+b-c}`"))
.unwrap();
debug_assert_eq!(
token_stream,
vec![
Lex::new(Token::TemplateTick, 0, 1),
Lex::new(Token::TemplateString, 1, 8),
Lex::new(Token::TemplateExprStart, 8, 10),
Lex::new(Token::ID, 10, 11),
Lex::new(Token::Add, 11, 12),
Lex::new(Token::ID, 12, 13),
Lex::new(Token::Sub, 13, 14),
Lex::new(Token::ID, 14, 15),
Lex::new(Token::CloseBrace, 15, 16),
Lex::new(Token::TemplateTick, 16, 17),
Lex::new(Token::EOF, 17, 17),
]
);
解析器
在本节中,我们将实现一个JavaScript表达式的解析器。我们将使用分词器提供的分词数据,并按照语言的语法将其解析成AST。一旦我们从分词器收到标记,我们希望从标记列表中过滤掉非语法标记,如“Space”,以简化并加快解析速度。因此,我们将更新is_structural实现以过滤非结构化标记。
impl TokenImpl for Token {
...
fn is_structural(&self) -> bool {
match self {
Token::Space | Token::LineBreak => false,
_ => true,
}
}
}
我们还将创建节点值并实现NodeImpl特质来表示AST中的每个节点。
#[derive(Debug, Clone, Copy)]
enum NodeValue {
NULL,
ID,
Number,
Add,
Sub,
Mul,
Div,
}
impl NodeImpl for NodeValue {
fn null() -> Self {
Self::NULL
}
}
现在,我们将实现解析JavaScript表达式的语法。在编写完整的表达式之前,我们首先将实现一个解析简单算术表达式的解析器。
let identifier = Rc::new(TokenField::new(Token::ID, Some(NodeValue::ID)));
let number = Rc::new(TokenField::new(Token::Number, Some(NodeValue::Number)));
let end_of_file = Rc::new(EOFProd::new(None));
let add_ops = Rc::new(TokenFieldSet::new(vec![
(Token::Add, Some(NodeValue::Add)),
(Token::Sub, Some(NodeValue::Sub)),
]));
let mul_ops = Rc::new(TokenFieldSet::new(vec![
(Token::Mul, Some(NodeValue::Mul)),
(Token::Div, Some(NodeValue::Div)),
]));
//We are going to implement following grammar for parsing an javascript expression.
/*
Value ← [0-9]+ / '(' Expr ')'
Product ← Value (('*' / '/') Value)*
Sum ← Product (('+' / '-') Product)*
Expr ← Sum
*/
// The expression in the parenthesis is required before defining expression.
// Let's initialize an parenthesis expression. We will set productions after defining expression.
let paren_expr = Rc::new(Concat::init("paren_expr"));
let value = Rc::new(Union::new(
"value",
vec![number, identifier, paren_expr.clone()],
));
let product = Rc::new(SeparatedList::new(&value, &mul_ops, true)); // The separator should be inclusive i.e. operators should not be at the end of production.
let sum = Rc::new(SeparatedList::new(&product, &add_ops, true));
let semicolon = Rc::new(TokenField::new(Token::Semicolon, None));
let expression = Rc::new(Concat::new("expression", vec![sum.clone(), semicolon]));
let root = Rc::new(Concat::new("root", vec![expression.clone(), end_of_file]));
// Setting the production for parenthesis_expr.
let open_paren = Rc::new(TokenField::new(Token::OpenParen, None));
let close_paren = Rc::new(TokenField::new(Token::CloseParen, None));
paren_expr
.set_symbols(vec![open_paren, expression, close_paren])
.unwrap();
let parser = DefaultParser::new(Rc::new(combined_tokenizer), root).unwrap();
let parsed_addition_tree = parser.parse(b"a+b-10;").unwrap();
println!("{:?}", parsed_addition_tree);
/*
[
ASTNode { token: ID, start: 0, end: 1 },
ASTNode { token: Add, start: 1, end: 2 },
ASTNode { token: ID, start: 2, end: 3 },
ASTNode { token: Sub, start: 3, end: 4 },
ASTNode { token: Number, start: 4, end: 6 },
]
*/
let parsed_tree = parser.parse(b"a+b*c;").unwrap();
println!("{:?}", parsed_tree);
/*
[
ASTNode { token: ID, start: 0, end: 1 },
ASTNode { token: Add, start: 1, end: 2 },
ASTNode { token: ID, start: 2, end: 3 },
ASTNode { token: Mul, start: 3, end: 4 },
ASTNode { token: ID, start: 4, end: 5 },
]
*/
默认情况下,生产工具Concat、List或SeparatedList不会在解析树中创建任何节点。相反,它们将解析树扁平化,并将其追加到一个Vec中。需要用Node包装一个工具来在AST中创建节点。让我们将乘法项、加法和表达式用Node包装。
#[derive(Debug, Clone, Copy)]
enum NodeValue {
...
Product,
Sum,
Expr,
Root,
}
...
let product = Rc::new(SeparatedList::new(&value, &mul_ops, true)); // The separated should be inclusive i.e. operators should not be at the end of production.
let product_node = Rc::new(Node::new(&product, NodeValue::Product));
let sum = Rc::new(SeparatedList::new(&product_node, &add_ops, true));
let sum_node = Rc::new(Node::new(&sum, NodeValue::Sum));
let semicolon = Rc::new(TokenField::new(Token::Semicolon, None));
let expression = Rc::new(Concat::new("expression", vec![sum_node.clone(), semicolon]));
let expr_node = Rc::new(Node::new(&expression, NodeValue::Expr));
let root = Rc::new(Concat::new("root", vec![expr_node.clone(), end_of_file]));
let root_node = Rc::new(Node::new(&root, NodeValue::Root));
...
let parser = DefaultParser::new(Rc::new(combined_tokenizer), root_node).unwrap();
let parsed_addition_tree = parser.parse(b"a+b-10;").unwrap();
assert_eq!(parsed_addition_tree.len(), 1);
parsed_addition_tree[0].print().unwrap();
/*
Root # 0-7
└─ Expr # 0-7
└─ Sum # 0-6
├─ Product # 0-1
│ └─ ID # 0-1
├─ Add # 1-2
├─ Product # 2-3
│ └─ ID # 2-3
├─ Sub # 3-4
└─ Product # 4-6
└─ Number # 4-6*/
let parsed_tree = parser.parse(b"a+b*c;").unwrap();
assert_eq!(parsed_tree.len(), 1);
parsed_tree[0].print().unwrap();
/*
Root # 0-6
└─ Expr # 0-6
└─ Sum # 0-5
├─ Product # 0-1
│ └─ ID # 0-1
├─ Add # 1-2
└─ Product # 2-5
├─ ID # 2-3
├─ Mul # 3-4
└─ ID # 4-5
*/
高阶表达式
我们当前的解析器不是设计来解析像真值、instance-of表达式这样的高阶表达式。让我们更新我们的解析器以解析高阶表达式。
// Extending summation expression to compare arithmetic values.
let cmp_ops = Rc::new(TokenFieldSet::new(vec![
(Token::GT, Some(NodeValue::GT)),
(Token::GTE, Some(NodeValue::GTE)),
(Token::LT, Some(NodeValue::LT)),
(Token::LTE, Some(NodeValue::LTE)),
(Token::EQ, Some(NodeValue::EQ)),
]));
// Implementing comparison expression.
let cmp_expr = Rc::new(SeparatedList::new(&sum_node, &cmp_ops, true));
let cmp_expr_node = Rc::new(Node::new(&cmp_expr, NodeValue::Comparative));
let semicolon = Rc::new(TokenField::new(Token::Semicolon, None));
let ternary_op = Rc::new(TokenField::new(Token::Ternary, None));
let colon = Rc::new(TokenField::new(Token::Colon, None));
// The production comparison expression(cmp_expr) could be an expression or beginning part of true-false, instanceOf or typeof expression.
// We will be implementing rest of the higher order expressions as suffixes to the comparison expression.
let truthy_expr_part = Rc::new(Concat::new(
"truthy_expr_part",
vec![
ternary_op,
cmp_expr_node.clone(),
colon,
cmp_expr_node.clone(),
],
));
let instance_of = Rc::new(TokenField::new(Token::InstanceOf, None));
let instance_of_expr_part = Rc::new(Concat::new(
"instance_of_expr_part",
vec![instance_of, cmp_expr_node.clone()],
));
// Suffixes will return left production match with first match from the suffixes productions.
let expr_part = Rc::new(Suffixes::new(
"expr_part",
&cmp_expr_node,
true,
vec![
(truthy_expr_part.clone(), NodeValue::Truthy),
(instance_of_expr_part, NodeValue::InstanceOfExpr),
],
));
let expression = Rc::new(Concat::new(
"expression",
vec![expr_part.clone(), semicolon],
));
/*
Root # 0-17
└─ Expr # 0-17
└─ Truthy # 0-16
├─ Comparative # 0-9
│ ├─ Sum # 0-6
│ │ ├─ Product # 0-1
│ │ │ └─ ID # 0-1
│ │ ├─ Add # 1-2
│ │ ├─ Product # 2-3
│ │ │ └─ ID # 2-3
│ │ ├─ Sub # 3-4
│ │ └─ Product # 4-6
│ │ └─ Number # 4-6
│ ├─ GT # 6-7
│ └─ Sum # 7-9
│ └─ Product # 7-9
│ └─ Number # 7-9
├─ Comparative # 10-12
│ └─ Sum # 10-12
│ └─ Product # 10-12
│ └─ Number # 10-12
└─ Comparative # 13-16
└─ Sum # 13-16
├─ Product # 13-14
│ └─ ID # 13-14
├─ Add # 14-15
└─ Product # 15-16
└─ Number # 15-16
*/
表达式终止
我们当前的实施要求分号(';')来终止JavaScript表达式。然而,JavaScript表达式也可以由eof、闭括号('}')或换行符终止。我们不希望使用行终止生成消耗eof或闭括号字符,因为它们是另一个生成的部分。因此,我们将实现Lookahead工具来检查eof或'}'是否紧接在表达式之后。
此外,换行符也可以表示JavaScript语言的语句结束语法。然而,is_structural实现从标记流中过滤掉了LineBreak标记。因此,我们将使用NonStructural实用工具来强制子生成器消费未过滤的标记流。完整的表达式结束生成如下。
let lookahead_eof = Rc::new(Lookahead::new(
&end_of_file,
Some(NodeValue::ExprTermination),
));
let close_brace = Rc::new(TokenField::new(Token::CloseBrace, None));
let lookahead_close_brace = Rc::new(Lookahead::new(
&close_brace,
Some(NodeValue::ExprTermination),
));
let hidden_null_white_space = Rc::new(TokenField::new(Token::Space, None).into_nullable());
let line_break = Rc::new(TokenField::new(Token::LineBreak, None));
let line_break_seq = Rc::new(
Concat::new("line_break_seq", vec![hidden_null_white_space, line_break])
.into_node(NodeValue::ExprTermination),
);
let expression_termination = Rc::new(Union::new(
"line_termination",
vec![
semicolon,
lookahead_eof,
lookahead_close_brace,
line_break_seq,
],
));
let expression = Rc::new(Concat::new(
"expression",
vec![expr_part.clone(), expression_termination],
));
测试
使用此库构建的标记化和解析器由词素实用工具和生成实用工具组成。我们可以为每个词素和生成实用工具分配日志级别,以便每个实用工具可以单独监控。
记录标记化
...
template_string.set_log(Log::Result("template-string")).unwrap();
...
combined_tokenizer.set_log(Log::Default("combined-tokenizer")).unwrap();
...
let token_stream = combined_tokenized.tokenize(b"`Sum is ${a+b-c}`").unwrap();
// Logs
/*
combined-tokenizer : Switching state 0 -> 1 at { line: 1, column: 2 }
Entering template-string
Lexeme Success for template-string : token: TemplateString from { line: 1, column: 2 } to { line: 1, column: 9 }.
Entering template-string
Lexeme error for template-string : at { line: 1, column: 9 }
combined-tokenizer : Switching state 1 -> 0 at { line: 1, column: 11 }
combined-tokenizer : Switching state 0 -> 1 at { line: 1, column: 17 }
Entering template-string
Lexeme error for template-string : at { line: 1, column: 17 }
*/
...
记录生成
truthy_expr_part.set_log(Log::Result("truthy-expr-part")).unwrap();
parser.parse(b"b instanceOf A;").unwrap();;
// Logs
/*
Unparsed production 'truthy-expr-part': at { line: 1, column: 2 }.
*/
parser.tokenize_n_parse(b"a+b-10>90?80:f+8;").unwrap();
// Log
/*
Parsing Success for 'truthy-expr-part': from { line: 1, column: 9 } to { line: 1, column: 16 }.
*/
调试解析器
此外,可以通过如下添加它们以进行调试来单独测试每个生成。
let mut parser = DefaultParser::new(Rc::new(combined_tokenizer), root_node).unwrap();
parser.add_debug_production("mul-expr", &product_node);
parser.add_debug_production("sum-expr", &sum_node);
let product_tree = parser.debug_production_at("mul-expr", b"a+b*4", 2).unwrap();
product_tree[0].print().unwrap();
/*
Product # 2-5
├─ ID # 2-3
├─ Mul # 3-4
└─ Number # 4-5
*/
let sum_tree = parser.debug_production_at("sum-expr", b"a+b*4", 0).unwrap();
sum_tree[0].print().unwrap();
/*
Sum # 0-5
├─ Product # 0-1
│ └─ ID # 0-1
├─ Add # 1-2
└─ Product # 2-5
├─ ID # 2-3
├─ Mul # 3-4
└─ Number # 4-5
*/
许可证
语言解析工具(lang_pt)在MIT许可证下提供。请参阅LICENSE。
依赖项
~4.5–6.5MB
~107K SLoC