// 两个宏用来集中管理safe和unsafe模式下的下标访问和不可达
// 如果使用了use_unsafe的话，它们分别会调用get_unchecked和unreachable_unchecked
macro_rules! index { ($arr: expr, $idx: expr) => { $arr[$idx as usize] }; }
macro_rules! impossible { () => { unreachable!() }; }
// 非终结符的编号
// 终结符和非终结符都有编号，并且保证终结符的编号都小于非终结符的编号
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub enum TokenKind { _Eps = 2, _Eof, _Err, Add, Sub, Mul, Div, Mod, UMinus, RPar, LPar, IntLit }
// lr分析的value stack的元素，这个例子里只能是lexer解析出来的token或者表示Expr的i32
pub enum StackItem<'p> { _Token(Token<'p>), _0(i32) }
// lexer解析出来的token的类型，包含了终结符种类，对应的字符串片段，行列号信息
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub struct Token<'l> {
pub ty: TokenKind,
pub piece: &'l [u8],
pub line: u32,
pub col: u32,
}
pub struct Lexer<'l> {
pub string: &'l [u8],
pub line: u32,
pub col: u32,
}
impl<'l> Lexer<'l> {
pub fn new(string: &[u8]) -> Lexer {
Lexer { string, line: 1, col: 1 }
}
// 新解析一个Token
// 如果解析结果是_Eps就不会返回给parser，如果是_Eof可能会导致parser完成最终的Acc或者出错
// 如果是_Err会导致parser出错
pub fn next(&mut self) -> Token<'l> {
// ACC表示每个dfa节点对应于哪个终结符，如果一个都不对应就是_Err
static ACC: [TokenKind; 10] = [一张巨大的表，这里不列了];
// EC表示equivalent char，有些字符对dfa处理起来可能是一样的，用EC先减小字符集的大小，从而减小dfa转移表的大小
static EC: [u8; 256] = [一张巨大的表，这里不列了];
// DFA_EDGE表示dfa的状态转移表，逻辑上DFA_EDGE[state][char]表示在state处遇到char时的下一个state编号
// 规定编号0必须代表出错状态
// 下面的所有u8(不包括上面那个EC的u8)，都是可以变化的，是可以容纳状态数的最小无符号整数
static DFA_EDGE: [[u8; 10]; 10] = [一张巨大的表，这里不列了];
// 这个循环不断把字符喂给dfa，直到：
// 识别出一个非_Eps的token后出错或文件结尾 => 返回这个token
// 没有识别出非_Eps的token时出错 => 返回_Err
// 没有识别出非_Eps的token时文件结尾 => 返回_Eof
loop {
let (mut line, mut col) = (self.line, self.col);
let mut last_acc = TokenKind::_Err;
let mut state = 0;
let mut i = 0;
while i < self.string.len() {
let ch = index!(self.string, i);
let ec = index!(EC, ch);
let nxt = index!(index!(DFA_EDGE, state), ec);
let acc = index!(ACC, nxt);
if acc != TokenKind::_Err { last_acc = acc };
state = nxt;
if nxt == 0 { // 出错，不能消耗掉当前字符，它属于下一个token
let piece = &self.string[..i];
self.string = &self.string[i..];
if last_acc != TokenKind::_Eps {
return Token { ty: last_acc, piece, line, col };
} else {
line = self.line;
col = self.col;
last_acc = TokenKind::_Err;
state = 0;
i = 0;
}
} else {
// 维护行号列号
// 有些字符其实宽度不一定是1(如tab)，但是简单起见这里统一用1表示了
if ch == b'\n' {
self.line += 1;
self.col = 1;
} else {
self.col += 1;
}
i += 1;
}
}
// 文件结尾
let piece = &self.string[..i];
self.string = b"";
return if last_acc != TokenKind::_Eps && i != 0 {
Token { ty: last_acc, piece, line, col }
} else {
Token { ty: TokenKind::_Eof, piece: b"", line: self.line, col: self.col }
};
}
}
}
// lr分析中对于一个lookahead字符的几种动作
#[derive(Copy, Clone, Debug, Eq, PartialEq)]
pub enum Act { Shift(u8), Reduce(u8), Acc, Err }
impl<'p> Parser {
pub fn parse<'l: 'p>(&mut self, lexer: &mut Lexer<'l>) -> Result<i32, Token<'l>> {
// PROD表示产生式的(左端项编号，右端项数目)
static PROD: [(u8, u8); 9] = [一张巨大的表，这里不列了];
// lr分析的动作表
static ACTION: [[Act; 12]; 18] = [一张巨大的表，这里不列了];
// lr分析的goto表
static GOTO: [[Option<u8>; 2]; 18] = [一张巨大的表，这里不列了];
let mut value_stk: Vec<StackItem<'p>> = vec![];
let mut state_stk: Vec<u8> = vec![0];
let mut state = 0; // state永远与栈顶相等，只是为了减少一些访存
let mut token = lexer.next(); // lookahead符号
println!("{:?}", token); // log_token的作用，输出一个刚解析出的token
// 标准的lr分析循环
loop {
let act = index!(index!(ACTION, state), token.ty as u32 - 2); // - 2是因为非终结符的编号都>= 2
match act {
Act::Shift(s) => {
// 移进，把token压入value stack，把shift的目标状态压入state stack
value_stk.push(StackItem::_Token(token));
state_stk.push(s);
state = s;
// 获取新的lookahead符号
token = lexer.next();
println!("{:?}", token); // 还是log_token的作用，输出一个刚解析出的token
}
Act::Reduce(r) => {
// 规约，先从state stack上弹出产生式右端项那么多个的state
let prod = index!(PROD, r);
for _ in 0..prod.1 { match state_stk.pop() { Some(_) => {} None => impossible!() }; }
// 然后从value stack上弹出产生式右端项那么多个的value用于执行语法动作
let value = match r {
0 => {
println!("Expr -> Expr Add Expr"); // log_reduce的作用，输出产生式
let r = match value_stk.pop() { Some(StackItem::_0(x)) => x, _ => impossible!() };
let _op = match value_stk.pop() { Some(StackItem::_Token(x)) => x, _ => impossible!() };
let l = match value_stk.pop() { Some(StackItem::_0(x)) => x, _ => impossible!() };
// 这个 l + r 就是用户编写的语法动作，嵌到这里来了
StackItem::_0({ { l + r } })
}
// 这里省略类似的Sub Mul Div Mod...
// 最后的一次规约，把用户定义的目标非终结符规约到增广语法中新定义的非终结符
8 => {
println!("_Expr -> Expr");
let _1 = match value_stk.pop() { Some(StackItem::_0(x)) => x, _ => impossible!() };
StackItem::_0({ _1 })
}
_ => impossible!(),
};
// 然后在value stack上压入新生成的value，并且通过访问goto表得知state stack上需要压入的新state
value_stk.push(value);
let cur = index!(state_stk, state_stk.len() - 1);
let nxt = match index!(index!(GOTO, cur), prod.0) { Some(nxt) => nxt, None => impossible!() };
state_stk.push(nxt);
state = nxt;
}
Act::Acc => {
// 接受，将栈顶作为最终结果返回
match state_stk.pop() { None => impossible!(), Some(_) => {} };
let res = match value_stk.pop() { Some(StackItem::_0(r)) => r, _ => impossible!() };
return Ok(res);
}
// 出错，返回导致出错的token
Act::Err => return Err(token),
}
}
}
}
