求导工具和语法分析
最近想用编译原理的思想和现代化类库来重构我大一写的函数求导器
仓库
思想&语法
在这里函数是真正的一等公民
- 变量的本质是数学函数
- 编程层面的函数需要引入多元函数,但是没必要
- 复杂的数据结构诸如链表，数组在这里是不存在的。如果需要存在，那么借鉴图灵机的做法，将用一个数字来显式表示数据结构的内存空间和类型，接着再用多元函数定义的读取方式。这个已经超出数学函数的范畴
约束
- 大小写敏感
- 行分隔符
核心词法
- 关键字
- x 定义函数的唯一关键字
- ln
- exp 和标识符e区分
- let 用于函数的组合
- fn 定义函数
- ' 数学求导符号,
- 内嵌函数
- print 打印函数的值或者结果
- dre 对函数进行求导
- 标识符 /\a+\w*/
- 行拆分
- 换行
核心语法
赋值语句
- 函数定义
let f = x^5 + 3;
- 变量定义
let b = f * x + 3;
- 嵌套调用
let c = b(x^2) + 1;
- 变量嵌套
let d = c(c(c));
- 函数求导
let e = d'';
- 嵌套求导
let f = e''(a');
开发感想
考虑到c内存管理困难和库比较少，一开始考虑的是rust。但是rust的yacc和lex实在有点不堪(没错只能写右递归无二义文法)，因此回到了c
数据结构
语法数的数据解构用的是二叉树，但实际是是glib的链树当成二叉树使用。由于该语言表达式是一等公民,因此语法树向上冒泡传的是表达式而非值，表达式一边冒泡一边做基本运算，最后算出右值
树上操作
求导
考虑如下求导文法:
\[a+b' \Rightarrow a'+b'\\
ab' \Rightarrow a'b+ab' \\
...
\]
(定义求导符号优先级最低)
可以看出这是一个一型文法，属于扩张性操作，因此使用mutable写法
格式化
一般是合并同类项和除0，除1
\[a \circ Zero \circ b \Rightarrow Zero \\
a+Zero+b \Rightarrow a+b \\
...
\]
可以看出这是一个零型文法，属于收缩操作。由于使用的是二叉树，每一次格式化和合并同类项必须要替换子树。使用immutable写法比较简单
图灵机和零型文法
众所周知，编译器的工作流程如下
- 将高级语言转化为IR
- 将IR转化为机器码
转化为IR的流程如下
- token分词(三型文法)
- 控制流转ast(二型文法)
- ast转IR(零型文法为主)
这里lex和yacc分别使用自动机和自底向上的栈规约实现了1和2, 3就需要我们自己手写代码来完成语义制导。而语义制导依靠的就是我们的计算机(即图灵机)来实现。这也是为何ast是一种递归数据结构。