duangsuse::Echo

#PL https://github.com/qnnnnez/rs

曾经在百度贴吧看到的邮电二进制序列化大佬... 现在居然也写 Sexp 语言解释器了...

二进制处理的算法我之前也写过，没有这位的那么高级那么实用，是解包一游戏的数据的。
而且也不如这个 C++ 的... 跨平台、内建序列化框架、C++ template 使用、各种图像纹理和波形、字体字形 glyph 解包打包什么的...

不过，我看（Sexp 解析器）的时候居然估计错了一个，真是该打... 太菜了...

https://github.com/qnnnnez/rs/blob/master/src/sexpr.rs#L53

我居然蠢到以为 self 里不保存扩号开闭堆叠状态的话肯定是不行的，然后一厢情愿地认为肯定是分配了新对象然后递归...
其实是单纯递归就可以了... 这次是我突然脑抽了一下，其实我还是知道的，之前我设计的 SubsequenceParser 就是属于上面那种脑残做法，而后来我设计的 HeapParser 其实就是递归下降解析，不过不把递归信息保存在栈上而是保存在堆上

伪代码（顺便教可能不了解解析器的你们如何手写解析器，当然是 parser combinator style 的『广义』解析器）：

Peekable<char> input; // 可以理解为字符流 Stream<Character>，标准输入
char current_char; // 当前字符，方便在函数直接传递

/* 常量 */
char PAREN_OPEN = '(';
char PAREN_CLOS = ')';
char BLANK = ' '; // 要跳过的空格

/* 辅助函数 auxilary */
fn nextChar() { current_char = input.peek(); }
fn getChar() -> char { return current_char; }

nextChar(); // seek 到第一个 char（虽然此操作不真正是 seek）

/* 解析：无解析状态 */
fn lexToplevel() -> Vec<Sexp> {
  let mut result_vec = vec![];

  loop {
    match getChar() {
      PAREN_OPEN => result_vec.push(lexList()), // 如果是列表，则进入列表分词状态
      /* 不应该出现不对称的闭扩号，对应（有开有闭）的闭扩号应该在解析列表时已经跳过了，不应该在顶层出现 */
      PAREN_CLOS => panic!("Unmatched parenthesis: Shold NOT seen closing paren lexing toplevel"),
      BLANK => next, // skip blanks
      EOS => break,
      _ => result_vec.push(lexAtom())
    }
    nextChar();
  }
  return result_vec;
}

fn lexList() -> Vec<Sexp> {
  assert!(getChar() == PAREN_OPEN);
  nextChar(); // 跳过开始的 '(' 字符
  let mut ret = vec![];
  while (getChar() != PAREN_CLOS && getChar() != EOS) {
    ret.push(lexToplevel()); // 直到最后看到列表结束符 ')'，我们知道列表嵌套的问题已经在 lexToplevel() 里处理好了，所以不去管这个递归定义
    nextChar();
  }
  if (getChar() == EOS) panic!("Unclosed parnthesis till EOS");
  nextChar(); // 之前的状态应该是 getChar() == PAREN_CLOS，nextChar() 跳过这个闭扩号
  return ret
}
fn lexAtom() -> Atom { /* implementation omitted */ }

~~所以这里啊我们可以看到现在流行的一个解析组合子的逻辑结构，多么优美，一切状态可以通过递归组合传递，语言层面的支持，不像那些循环 state based lexer，一大堆 yystat、pushState 很难看~~

那么我们来看看它如何解析一些简单的小程序（虽然都是简单的东西，感到羞愧。）

()

首先 seek 到输入 (，lexToplevel 分派到 lexList，
while 循环直接没进（因为 ( 后面已经是 ) 了
nextChar 到 eos，返回 toplevel 后结束分词

()()

[()()]lexToplevel => [()()]lexList{[]}[()] |> {[]}[()]lexToplevel => lexList{[][]}() |> {[][]}lexToplevel

(()) 这个比较有意思，因为开始使用调用栈记录嵌套了
首先 ( 分派 lexList，lexList 再 lexToplevel，lexToplevel 看见第二个 ( 又调用 lexList
此时调用栈是这样的：

lexList $j = [ $k ]
lexToplevel $i = $j
lexList [ $i ]
lexToplevel (())

递归到这里（栈顶）实际上已经结束了，因为中间第二个 ( 后面直接就是 )，没有别的，然后递归回溯得到结果

$k = (none)
$j = []
$i = []
lexToplevel (()) = [[]]

(1 ())

lexToplevel (1 ()) =
lexList 1 () : [] =
lexAtom 1 : lexList () : [] =
1 : [] : [] = [1 []]

((1) 2222 hhhhh ())

lexToplevel ((1) 2222 hhhhh ()) =
 (in lexList) {(1) 2222 hhhhh ()} : [] =
  (in lexList) {{1 : []} 2222 hhhhh ()} : [] =
   (in lexAtom) {{#1 : []} 2222 hhhhh ()} : [] =
  (in lexAtom) {{#1 : []} #2222 hhhhh ()} : [] =
  (in lexAtom) {{#1 : []} #2222 #hhhhh ()} : [] =
  (in lexList) {{#1 : []} #2222 #hhhhh {[]}} : [] =

— 开始回溯归约 —
{{#1 : []} #2222 #hhhhh []} : []
{{#1 : []} #2222 hhhhh []} : []
{{#1 : []} 2222 hhhhh []} : []
{{1 : []} 2222 hhhhh []} : []
{[1] 2222 hhhhh []} : []
[[1] 2222 hhhhh []]

((()) 这个有意思的地方在于它会失败，因为没有闭扩号就 EOS 了，猜猜在哪里 EOS，那时调用栈是啥样（

比起 HeapParser 手动维护的数据结构，系统调用栈记录的可能更多，一个调用（call）没有返回（return）的时候，调用者（caller）处于尚没有完成执行的状态，等待被调用者（callee）求值完成
我比较奇怪就是单靠记录一个 level 和一个 heap 上的 list 可不可以就直接像 recursive descent method （递归下降解析法）一样直接能解析了，奇怪的是好像无法做到区分 () 和 ()()、() (1)、((1)) 这种嵌套一样
递归的确是比较好玩的，因为实际上，类似现在 Coroutines 和各种 CPS 一样，调用帧记录了返回地址，也即函数的 continuation，所以被挂起没有完成执行的函数实际上有足够的信息在恢复执行时规约到完整的 AST（因为我们实际上的确记录了要把项目插入在哪里（通过记录返回地址的函数调用完成））

递归之美。

看看 Rust 的 enum ADT（代数数据~~结构~~ 类型）多么优雅（

#[derive(Debug)]
pub enum SExpr {
    Atom(SAtom),
    List(Vec<SExpr>),
    Quote(Box<SExpr>),
}

#[derive(Debug)]
pub enum SAtom {
    Symbol(String),
    Integer(i64),
    Bool(bool),
    Char(char),
}

GitHub

qnnnnez/rs

Contribute to qnnnnez/rs development by creating an account on GitHub.

29 viewsduangsuse ¯\_(ツ)_/¯ |学渣|母上千古, edited 12:34