|
3 jaren geleden | |
---|---|---|
.. | ||
static | 3 jaren geleden | |
词法分析科学计算器.代码 | 3 jaren geleden | |
readme.md | 3 jaren geleden | |
词法分析科学计算器.e | 3 jaren geleden |
本节的目标是实现包含一些初等函数的计算器, 允许输入的例子如下:
# 允许以#开始写注释, #到行尾的将被忽略
1 + sin(degree(30)) # 角度制的30度
2 - cos(pi) / 10 # 默认为弧度制, 支持定义常量
3 * log(10, 100) # 以10为底, 取100的对数
4 / (2^3 / 4^2) # 当然仍然还有括号可以用
上一节中实现功能时边读入边解析和计算, 如果按照这样的逻辑完成本节的目标, 代码将会冗长又固执, 难以阅读和修改. 本节的代码清晰地分为了两个部分:
此处的「词」是一个泛指, 意为某些同类字的集合, 如「12334.235」是「数字和小数点」的集合是词, 「sin」是「字母」的集合是词, 「# 注释文本」也是词.
这里定义了一些词类型
.版本 2
.常量 词类型枚举
.常量 词类_数字, "1"
.常量 词类_整数部分, "2"
.常量 词类_小数部分, "3"
.常量 词类_标识符, "4"
.常量 词类_算符, "5"
.常量 词类_括号, "6"
.常量 词类_注释, "7"
.常量 词类_逗号, "8"
.常量 词类_空格, "9"
.常量 词类型枚举数量, "9"
词类_整数部分和词类_小数部分是为了迁就小数匹配, 词法分析的时候是跳过这两个的. 词法分析的时候逻辑很简单, 伪代码大约是:
对于每一个词类
如果 是整数部分 或 小数部分
到循环尾
end
如果 正则匹配对当前剩余文本匹配成功
记录匹配结果和类型
文本游标往右走匹配结果那么长
跳出循环
end
end
这样一趟后就得到了这样的结果
> 词法分析 sin(x) + cos(pi * y) - ln(x) * 123.456 # 注释
用时 0ms
当前类型: 4, 内容: sin
当前类型: 6, 内容: (
当前类型: 4, 内容: x
当前类型: 6, 内容: )
当前类型: 5, 内容: +
当前类型: 4, 内容: cos
当前类型: 6, 内容: (
当前类型: 4, 内容: pi
当前类型: 5, 内容: *
当前类型: 4, 内容: y
当前类型: 6, 内容: )
当前类型: 5, 内容: -
当前类型: 4, 内容: ln
当前类型: 6, 内容: (
当前类型: 4, 内容: x
当前类型: 6, 内容: )
当前类型: 5, 内容: *
当前类型: 1, 内容: 123.456
当前类型: 7, 内容: # 注释
----
>
语法树通常没有定型, 需因地制宜设计. 数学表达式通常可以视为一个纯的无求值顺序问题的语言. 可以做如下规约:
0 ± x -> ±(0, x)
x ± 0 -> ±(x, 0)
a + b -> +(a, b)
12345 -> +(12345, 0)
这样的话所有的计算表达式都可以写作 函(函甲, 函乙, 函丙, 函丁...)
函: 指函数
那么语法树的每一个节点应当包含如下信息
但是很遗憾, 这样的代码会报递归定义错误, 我又没找到怎么把一个指针重新解释成某个自定义类型等我开始扩展易语言语法的时候首先要处理这个事情, 那只能自己申请内存管理数据了, 按C的写法数据结构定义如下:
{
char 函数名[16], // 定长16, 再长不支持了
int32_t 参数量, //
int32_t 参数数组容量, // 参数数组指针后有多大容量, 按照每次*2扩充
uint64_t *参数数组指针, // 按长整数, 未来迁移到x64时兼容
}
// 此结构单个长度为 16+8+8 = 32 字节
终于可以开始写递归下降器了.
我不觉得我谈论递归下降能比网上的其他教程更好, 随便找了两个参考链接.
额外阅读:
接下来将假设你有基础的相关知识了. 考虑合规的表达式要么是 f(args)
x + y
, 要么是二者在括号内外通过算符连接, 因此给出如下定义
# 尖括号内是词类型, 大括号内是语法
# * 与正则表达式内星号含义相同, 指匹配0或任意次 ((女装)*)
# + 与正则表达式内星号含义相同, 指匹配至少1次
# | 表 或.
表达式 := 加后表达式 (("+" | "-") 加后表达式)*
加后表达式 := 因子 (("*" | "/") 因子)*
因子 := 左括号 表达式 右括号 | 函数 | 数字
函数 := 标识符 左括号 (表达式 (逗号 表达式)*){0,1} 右括号
光写出来构造还是蛮简洁的, 匹配表达式时可以沿着表达式->加后表达式->因子->函数->表达式
走, 这就是递归下降里的递归含义, 而下降则是指自顶向下慢慢解析. 如果你足够敏锐, 一定能意识到这个流程可能出现无限循环, 这就是左递归问题, 好在上面所提到的数学表达式是LL(1)文法(从左往右每次多看1个词就可以确定究竟是什么), 脑子不糊涂一般不会写出来无限循环. 对于更复杂的情况, 可以上LL(k)解析器, 尽量多看几个. 不过还有一些其他处理方法, 后面再提.
细微之处的东西在代码的注释里.
本节代码使用 git 组织, 每一个里程碑我都会创建一个 commit, 你可以通过 git 回溯来分步查看我的编码过程. 如果你不会 git, 可以下载一个 github desktop, 可以直接在 GUI 上看到各个 commit 的内容.
本节代码仍然使用纯的易语言做文本分析, 但是如果你详细读了这份代码, 会发现大量的重复, 之后我将使用 JavaScript 的 peggyjs 库来重新做这件事, 同时, 如果你认真读了本节代码, 你也可以轻松读懂 peggyjs 的大部分东西.
不过严格来说, 正则表达式也是 DSL, 因此用了正则表达式就不算是纯易语言了.