lelwel

目录

• 介绍
• 语法示例
• 快速入门
• 语法规范
• 许可证

介绍

Lelwel (Language for Extended LL(1) parsing With Error resilience and Lossless syntax trees) 使用 LL(1) 语法 生成带有扩展（直接左递归、运算符优先级、语义谓词（这还使任意前瞻成为可能）和语义动作（这允许处理语义上下文敏感性，例如 C 中的类型/变量名歧义）的 Rust 递归下降解析器。

解析器创建了一个同构、无损的具体系语法树（CST），可用于构建抽象语法树（AST）。某些模式被检测到，以避免为仅转发到其他规则的规则创建 CST 节点。可以使用正则表达式定义绑定来重命名某些解析的 CST 节点。

错误恢复和树构建灵感来源于 Alex Kladov（matklad）的 鲁棒 LL 解析教程。Lelwel 使用一个（据我所知）新颖的启发式方法，通过使用由语法诱导的有向图中的支配集的 follow 集自动计算恢复集。

Lelwel 以库的形式编写。它被 CLI 工具 llw、语言服务器 lelwel-ls 使用，并可以作为构建依赖项包含，以便从 build.rs 文件中调用。有一个用于 Neovim 的插件，该插件使用语言服务器。

默认情况下，生成的解析器使用 Logos 进行词法分析，使用 Codespan 进行诊断，但这不是强制的。

为什么还需要另一个解析器生成器？

• 错误恢复： 生成的解析器可能提供类似于手写解析器的错误恢复能力。
• 无损语法树： 语言工具（如语言服务器或格式化工具）需要有关源代码的所有信息，包括空白和注释。
• 语言服务器： 当您的语法包含冲突或错误时，立即获得反馈。
• 易于调试：生成的解析器易于理解，可以使用标准工具进行调试。

为什么选择LL(1)而不是更通用的CFL或PEG解析器？

• 错误恢复能力：似乎LL解析器比LR解析器更适合从不完全的源代码生成有意义的语法树。
• 运行时复杂度：更通用的解析器，如GLR/GLL或ALL(*)，对于某些语法，其运行时复杂度可能为$O(n^3)$或$O(n^4)$。只要你的语义动作和谓词具有常数运行时复杂度，LL(1)解析器可以保证具有线性运行时复杂度。
• 歧义性：任意上下文无关文法是否具有歧义性的决策问题是不可判定的。因此，通用解析器生成器发出的警告可能包含误报。在最坏的情况下，歧义性可能在运行时被发现。PEG形式主义只是定义了如何消除歧义，这可能会导致解析器解析与你期望不同的语言。

语法示例

lelwel语法文件解析器 (*.llw) 本身也是由lelwel生成的。还有C语言（无预处理器的示例）（实际上使用语义上下文信息解决歧义，与ANTLR4和Tree-sitter的示例不同）、Lua、算术表达式、JSON和Oberon-0的示例。

您可以在Lelwel沙盒中尝试示例。

以下示例展示了由Resilient LL Parsing教程介绍的玩具语言"L"的语法。

token Fn='fn' Let='let' Return='return' True='true' False='false';
token Arrow='->' LPar='(' RPar=')' Comma=',' Colon=':' LBrace='{' RBrace='}'
      Semi=';' Asn='=' Plus='+' Minus='-' Star='*' Slash='/';
token Name='<name>' Int='<int>';
token Whitespace;

skip Whitespace;

start file;

file: fn*;
fn: 'fn' Name param_list ['->' type_expr] block;
param_list: '(' [param (?1 ',' param)* [',']] ')';
param: Name ':' type_expr;
type_expr: Name;
block: '{' stmt* '}';
stmt:
  stmt_expr
| stmt_let
| block
| stmt_return
;
stmt_expr: expr ';';
stmt_let: 'let' Name '=' expr ';';
stmt_return: 'return' [expr] ';';
expr: expr_bin;
expr_bin:
  expr_bin ('*' | '/') expr_bin
| expr_bin ('+' | '-') expr_bin
| expr_call
;
expr_call:
  expr_call arg_list
| expr_literal
| expr_name
| expr_paren
;
arg_list: '(' [expr (?1 ',' expr)* [',']] ')';
expr_literal: Int | 'true' | 'false';
expr_name: Name;
expr_paren: '(' expr ')';

快速入门

1. 将语法文件写入您crate的src目录。您可以选择安装CLI或语言服务器以验证您的语法文件：cargo install --features=cli,lsp lelwel。
2. 将以下内容添加到您的Cargo.toml和build.rs文件中。

   [dependencies]
   logos = "0.14.0"
   codespan-reporting = "0.11.1"
   
   [build-dependencies]
   lelwel = "0.6.2"
   

   fn main() {
      lelwel::build("src/your_grammar.llw");
   }
   

3. 开始构建。这将创建一个与您的语法文件相邻的parser.rs文件。parser.rs文件需要手动编辑以实现词法分析器，它包括实际解析器generated.rs，该解析器写入Cargo的OUT_DIR。如果在parser.rs文件生成后更改了语法，可能需要手动更新Token枚举或Parser实现以用于语义谓词和动作。
4. 使用以下最小的main.rs文件使用解析器模块来打印CST和诊断信息。

   mod parser;
   
   use codespan_reporting::files::SimpleFile;
   use codespan_reporting::term::termcolor::{ColorChoice, StandardStream};
   use codespan_reporting::term::{self, Config};
   use logos::Logos;
   use parser::*;
   
   fn main() -> std::io::Result<()> {
       let args: Vec<String> = std::env::args().collect();
       if args.len() != 2 {
           std::process::exit(1);
       }
       let source = std::fs::read_to_string(&args[1])?;
       let mut diags = vec![];
       let (tokens, ranges) = tokenize(Token::lexer(&source), &mut diags);
       let cst = Parser::parse(&source, tokens, ranges, &mut diags);
       println!("{cst}");
       let writer = StandardStream::stderr(ColorChoice::Auto);
       let config = Config::default();
       let file = SimpleFile::new(&args[1], &source);
       for diag in diags.iter() {
           term::emit(&mut writer.lock(), &config, &file, diag).unwrap();
       }
       Ok(())
   }
   

语法规范

Lelwel语法基于上下文无关文法（CFG）的正式主义，特别是LL(1)语法。对经典语法语法有所扩展，例如类似EBNF的结构。

语法文件由顶层定义组成，它们独立于它们的顺序。

令牌列表

令牌列表定义将一系列令牌（终端）引入语法。它以token关键字开始，以;结束，并包含一系列令牌名称和相应的令牌符号。

令牌名称必须以大写字母开头。令牌符号是可选的，并用单引号括起来。它在错误信息和parser.rs文件的生成器中使用。在正则表达式中，可以通过名称或符号引用令牌。

[!提示]如果令牌符号字符串以<开始并以>结束，则令牌被视为一组令牌，其符号仅作为描述。这会影响在parser.rs中默认生成的错误信息和词法规则。

示例

token MyKeyword='my_keyword' Int='<integer literal>' True='true' False='false';

规则

语法规则必须以小写字母开头。正则表达式用于指定规则的右侧。

以下特殊正则表达式模式被识别为规则。

• 左递归

  具有直接左递归的规则。规则必须由顶级选择组成。可能有多个递归和非递归分支。如果选择由单个规则引用组成的非递归分支，则不会在语法树中创建节点。

  示例

  call_expr:
    call_expr arg_list
  | primary_expr
  ;
  

• 运算符优先级

  解析二进制表达式的规则。规则必须由顶级选择组成。恰好有一个分支引用了不同的规则。所有其他分支必须包含3个元素的左递归和右递归连接。连接的中间元素必须是引用一个令牌或令牌交替。顶级选择的分支顺序决定了运算符优先级。只有在选择递归分支时，语法树中才会创建节点。

  示例

  bin_expr:
    bin_expr ('*' | '/') bin_expr
  | bin_expr ('+' | '-') bin_expr
  | primary_expr
  ;
  

• 无条件转发

  仅转发到其他规则的规则。规则可能由另一个规则的单一引用组成或由每个分支引用单个规则组成的顶级选择。对于此类规则，语法树中不会创建任何节点。

  示例

  stmt:
    for_stmt
  | while_stmt
  | expr_stmt
  | return_stmt
  ;
  

• 条件转发

  由第一个元素是规则引用且后续元素可能为空的连接组成的规则。如果使用可能为空的部分，则语法树中仅创建节点。

  示例

  expr_list:
    expr (',' expr)*
  ;
  

• 右递归转发

  规则必须由至少一个右递归分支和一个引用规则的分支组成的顶级选择组成。如果选择由单个规则引用组成的非递归分支，则不会在语法树中创建节点。

  示例

  unary_expr:
    ('+' | '-') unary_expr
  | primary_expr
  ;
  

• 可能为空

  可能推导出空字符串的规则。如果推导不是空的，则创建节点。

  示例

  generic_args:
    ['<' type_list '>']
  ;
  

正则表达式

正则表达式由以下语法构造组成。

• 分组： (...)
• 标识符： rule_name或TokenName
• 符号： 'token symbol'
• 连接： A B，即A后跟B
• 交替： A | B，即A或B
• 可选： [A]，即A或无
• 星重复: A*，表示0个或多个A的重复
• 加号重复: A+，表示1个或多个A的重复
• 语义谓词: ?1，表示语义谓词编号1
• 语义动作: #1，表示语义动作编号1
• 绑定: @new_node_name用于重命名语法树节点
• 节点标记: <1标记索引为1以创建新节点
• 节点创建: 1>new_node_name在标记索引为1的位置插入节点

start translation_unit;

skip Whitespace Comment;

right '^' '=';