记忆化也花了我一番功夫,现在用了一个比较土的办法,在每个结点上记录了当前遇到过的所有可能,这个是逐渐构造的,意味着如果只需要第一种解析树,不需要额外的空间。然后逐渐扩张,如果有可以重用的结构就重用,把涉及的所有的结构都放在一个 Vec 中,用完之后一起 drop 掉。
当然了,这个时候,各种东西都变成了引用:
//! This example is taken from MashPlant/lalr1usegll_pg_core::*;usegll_pg_macros::gll;uselogos::Logos;#[derive(Logos, Debug, Eq, PartialEq, Clone)]enumToken{#[end]End,#[error]Error,#[token = " "]_Eps,#[token = "+"]Add,#[token = "-"]Sub,#[token = "*"]Mul,#[token = "/"]Div,#[token = "%"]Mod,#[token = "("]LPar,#[token = ")"]RPar,#[regex = "[0-9]+"]IntLit,}#[derive(Default)]structParser{literals:Vec<i32>,}#[gll(Expr, Token)]implParser{// you can omit self#[rule(Expr -> Expr Add Expr)]fnexpr_add(l:&i32,_op:&LogosToken<Token>,r:&i32)->i32{*l+*r}// you can use &self#[rule(Expr -> Expr Sub Expr)]fnexpr_sub(&self,l:&i32,_op:&LogosToken<Token>,r:&i32)->i32{*l-*r}// you can use &mut self as well// but all of these have &mut self in fact#[rule(Expr -> Expr Mul Expr)]fnexpr_mul(&mutself,l:&i32,_op:&LogosToken<Token>,r:&i32)->i32{*l**r}#[rule(Expr -> Expr Div Expr)]fnexpr_div(l:&i32,_op:&LogosToken<Token>,r:&i32)->i32{*l/*r}#[rule(Expr -> Expr Mod Expr)]fnexpr_mod(l:&i32,_op:&LogosToken<Token>,r:&i32)->i32{*l%*r}#[rule(Expr -> Sub Expr)]fnexpr_neg(_op:&LogosToken<Token>,r:&i32)->i32{-*r}#[rule(Expr -> LPar Expr RPar)]fnexpr_paren(_l:&LogosToken<Token>,i:&i32,_r:&LogosToken<Token>)->i32{*i}// so you can make your IDE happy with &mut self here#[rule(Expr -> IntLit)]fnexpr_int(&mutself,i:&LogosToken<Token>)->i32{letlit=i.slice.parse().unwrap();self.literals.push(lit);lit}}#[test]fnambiguous(){letmutlexer=Token::lexer("1 + 2 + 3");letmutparser=Parser{literals:vec![]};letres=parser.parse(&mutlexer).unwrap();// two ways to parseletres:Vec<_>=res.cloned().collect();assert_eq!(res,vec![6,6]);}