自写计算器的疑惑

[crella]

工科生，出于兴趣想写一个计算器。

目前支持功能：
1、多语句，比如命令行输入 3+cos(pi/3);;4+afx(4, sin(5))。以双分号分隔。
2、自定义变量(输入 n=6.6)和自定义函数(输入 afx(x,y)=x-cos(x))。其中单变量函数支持求极限、求导和定积分，都是用原始方法粗略模拟的。用到 ruby 的反射。这个单项不能保证数学上的正确。
3、支持逐行解析文本文件并保存结果到文件。
4、支持数列按多个循环的填充公式生成，和数列求和。支持通过遍历区间来暴力求二元方程的解。(注：这一分项的功能都可能出现不能计算的意外情况。)
5、按入门教程写了个超简易的 cgi，试过网页访问，计算速度还算及格……因为我一开始理解的 cgi 都是访问一次就运行用户层 ruby 一次，所以很怂地在每次退出用户层时都把用户自定义的变量和函数保存成 txt。json 还没学，也挺想学学的。



(功能陈述完毕)


我在 github 搜了一下 calculator，好像都是按键的四则运算，我没什么可以参考的，这和我的玩耍理念不一样啊。懒于 fq，obey the law 惯了学不会折腾……也不知道搜索什么关键字？或许利用什么技术？

实战过程：一开始用 perl6，类型转换跳了不少坑，转 ruby。遇到坑了，不用 eval ；于是用户层用 ruby 写，ruby 写执行计算的 ruby 新脚本，然后 system 过去，再从 txt 获取结果。

后来因为逻辑没考虑好，执行一万次运算时 ruby 太慢所以改为 c++写计算文件，ruby 调用 g++编译、执行。后来逻辑搞清楚了，继续 ruby+ruby，计算速度也还行，就弃用 c++了。

现在打算计算层改为：用户层 ruby 生产完含有两个方法的带编号的 ruby 新脚本之后，load ext_NN.rb ，调用 ext_cal_NN 方法(NN 是任务的数字编号)，返回计算结果的数组。可是这样会不会导致内存消耗异常？有次手贱写错逻辑，结果 ruby.exe 占用了 2G 内存，后面任务管理器就卡死了，差点关不了机。

求高人指路。1、计算器还应添加什么有用又容易实现的功能？我目前就只会百度和看 ruby 基本教程，也下了基本 ruby 系统管理的电子书，github 看 ruby 开源项目的一堆都在定义类，不知道从哪里看起。2、有哪些类似的开源项目可以参考？ java、php、c#的基本语法都懂一点，对 python 和 js 无感。3、这个玩具还有值得投入时间的意义吗？

因为编程的概念太宽泛，不是面向工资编程的我不知道选什么方向啊。我就只觉得随着功能增加，不可能选用 eval，要不然该怎样使用用户自定义的 afx(x, y)函数，还有怎样生成多个自变量循环的数列呢，这些东西都不知道怎么表达和搜索。

[winterbells]

要不照着编译器原理写？。。

[secondwtq]

关键字：解释器（ Interpreter ）
一定要学 fq

我见过最好用的计算器是 Jupyter Notebook
另外我非常好奇你为什么会用 perl6/raku ...

"执行一万次运算时 ruby 太慢所以改为 c++写计算文件，ruby 调用 g++编译、执行" G++ 有时候可以比 Ruby 还慢 ... 虽然这里应该不会有太大问题

[Sanko]

编译原理

[crella]

在 ghub 上找到了一个 c#的，一个 ruby 的，都应该是可以直接借鉴的。

[verrickt]

po 所描述的计算器和编译器有明显的类似之处：根据用户提供的**字符串**产生某个确定性的结果。
简易提几个点，你需要一个组件把用户输入的字符串转化为树状结构，一个组件实现树状结构的计算，一个组件实现输出。
正好对应编译原理的前端，中端，后端。
不这么搞光是个运算符优先级就能搞死个人。

ninputer 有系列博客讲怎么写编译器的，po 可以参考下。里面提到的很多问题都有共性。

[xiadong1994]

你要支持复杂表达式就得走编译器 /解释器那一套

[secondwtq]

@winterbells @Sanko
给楼主打个预防针

我发 #2 之前第一行写的是“编译原理”，但是发之前最后改成了“解释器”
因为之前看了 https://v2ex.com/t/607304 这个帖子，就有直接回复“编译原理”的话是非常 misleading 的直觉

首先，楼主“编程的概念太宽泛”这个观察是对的，有很多人（包括很多面向工资编程的人）认为世界上有 10 种人，一种是程序员，另一种是非程序员。我认为所谓“程序员”和“非程序员”之间并不存在明确的界限，非要说的话只有“面向工资编程”和不是面向工资编程的区别
具体来说，很多看上去和编程无关的东西，都是要涉及到编程的，比如 VFX 领域其实很先进，已经普及了 Dataflow Programming，Visual Programming 和以 Python+Qt 为基础的辅助工具。普通人可能用个 AE，虽然 AE 智商兼容性稍微高点，不过也是要写表达式的。
在所谓 “H5” 流行起来之前的桌面时代很长一段时间 Flash 有很高的地位，Flash 的编程内容就更直接了。
还有 Apple 买的 Workflow，虽然 Apple 自己说这东西做的是“task automations ... without requiring familiarity with programming”，但是这东西本质上就是个 Visual Script
那为什么 Apple 要说它不需要“programming”呢？就是因为大众对“programming”这个东西有一种本能的距离感，你只要提了，那我觉得你这东西门槛高，不是给我用的，我就不用了。（这其实也多亏了 Apple 等公司多年来对用户苦心孤诣的“教育”）所以 Apple 要让 Workflow 在大众中流行起来，就必须明确和“programming”划清界限，哪怕这纯属一个此地无垠三百两的行为。

而杀伤力最大的例子，其实是 Excel，你用 Excel/Google Sheets 等软件时用过 公式 么？用了，你就写过程序
（这不是我自己 claim 的，至少 Shriram Krishnamurthi 和 Simon Peyton Jones 都持类似观点）
甚至广义的说，所有的管理人员都是程序员，只不过他们编程的不是机器，而是人而已
（这也就是前两天那个帖子 https://v2ex.com/t/611574 的终极解决方案：扩大“程序员”一词的定义，解构“程序员”这个概念本身

而社会主流，甚至包括 V 站，对“程序员”的定义是如此之狭窄，就好象只有写 Java Web 才能叫写程序，前端怎么能叫程序员呢（那是切图的，跟我念 qie 切 tu 图 de 的）？做硬件怎么能叫程序员呢？美术怎么能叫程序员呢？音乐人怎么能叫程序员呢？测试怎么能叫程序员呢？运维怎么能叫程序员呢？会计怎么能叫程序员呢？做科研怎么能叫程序员呢？不是，程序员就是 ATMPB 里面，写 Java Web 的那群人，给我记住了不许反驳

那么这些不是“传统”程序员的人，用的很多不是 C/Java 一类的语言，而是针对于他们自己领域（如数据处理、特效制作）的专门语言，计算机里管这东西叫 DSL （ Domain Specific Langauge ）。要理解 DSL 这个词的话 ... 我好像给不出严格的定义，因为貌似并不存在。这么说吧，Excel 的公式是面向数据处理的 DSL，AE 的表达式是面向动画的 DSL，正则表达式是面向字符串匹配的 DSL，Markdown/LaTeX 等是面向文档写作排版的 DSL （ LaTeX 好像更像个数学公式 DSL ...），MATLAB 是面向数值计算的 DSL，Windows 常用的 INI 是做配置的 DSL，Shell/BAT 则是做命令行交互与自动化的 DSL，HTML 是用来描述超文本的 DSL，CSS 则是用来描述样式的 DSL。
DSL 的另一面是通用编程语言（ General Purpose Language，就简称 GPL 吧），就是大众认知中的 C，C++，Java 这一类。一个 GPL 在使用了特定的框架和库之后其实也可以变成 DSL，比如 C++ 的 Boost 里面有个叫 Spirit 的东西，这东西可以直接在 C++ 里面写 parser （至于 parser 是啥 ...）。而 DSL 也可以变成 GPL，比如 JavaScript 一开始就是 Web 前端的 DSL，看起来是逆袭成 GPL 了（还派生出了 JSON 这个新的 DSL ），PHP 则偏后端，虽然有点 GPL 的意思，不过好像差了 JavaScript 两步

啰嗦了这么多，主要就是楼主要明白你要做的这个东西不叫计算器，叫 DSL
这个思维的转型首先要到位。举个例子，我们专业有个什么课，有一个作业就是写个计算器，作业要求其实很简单，大多数人就写了个加减乘除，稍微好一点的加了图形界面，就是楼主说的“按键的四则运算”。但是吧我有一个学弟，他就肝了几个晚上，把楼主的“多语句”“自定义变量”“自定义函数” 之类的都做出来了。当然他是有编译方面基础的，所以其实是按照 DSL 来做的，而不是“计算器”

楼主需要实现的也并不是把用户的代码放在 perl/ruby 里面跑，而是 按照实现 DSL 的方法实现一个 DSL。楼主现在路走的有点偏，你生成个脚本运行，然后还暴露在 CGI 上，就不说各路脚本小子要拿你 shell，就是写个死循环你也没办法啊，你见过哪家计算器会死循环的 ...

至于这个“实现 DSL 的方法”到底是什么，很大程度上就取决于你搜的是“编译原理”，还是“解释器”了
“编译原理”其实是一个科班课程（并且是非常局限于计算机的那种 ...），原则上会讲一个编译器（也就是 GCC ）所涉及到的所有基础理论知识（之所以说是 GCC，因为 GCC 在这方面其实可以大概说是 Ruby/Perl 的超集，一般的课程安排也会更倾向于这个方向）
这是上交 ACM 班编译原理课程的课程设计： https://acm.sjtu.edu.cn/wiki/Compiler_2019，他们要实现的东西的文档： https://acm.sjtu.edu.cn/w/images/3/30/M_language_manual.pdf （该文档慎点，有减寿风险）
本质上和楼主要实现的东西是没有区别的，只是更 general 一点（比如楼主的“计算器”只支持计算数值，这个还能支持字符串操作和布尔逻辑）
真写起来的话，就这个课程设计的实现思路两只手数不过来，不过核心思路大差不差，只是选择的具体算法和工具选择不太一样。

但是不是说楼主要写计算器，就要去上这个课并且把讲的东西弄明白，划重点：人家要求的是生成“x86-64 Assembly”，并且学生做大作业是要评分的，你只要东西喂进去，算出结果来就行，写起来越短平快越好。
然后楼主去搜“编译原理”，搜出来的东西不仅可以写这个课程设计，甚至足够写 GCC——因为“编译原理”是对所有编译相关技术的（非常奇葩的）一个 umbrella term
但是楼主只是想要写个复杂一点的计算器 ...

具体来说吧，一个科班的编译原理课程，可能会教你什么呢，首先是编译器前端：什么 NFA，DFA，LL，LR，LALR，就是先把源码变成语法树，还有类型检查什么的，然后是中端，什么 IR，CFG，DFA，Alias Analysis, Dominator Tree, CSE, SROA, LICM, IPO，然后后端，Instruction Selection, Register Allocation, Instruction Scheduling
（大多数的课程一般都是大概按我上面写的顺序来的，为什么说是“一般”，因为后面有反例）
我就直说了吧，对于楼主的目的来说，我上面列的这些东西，有一个算一个，全都没用，看到了直接拉黑（我特意漏了 Symbol Table 和 Activation Record 之类，因为这些还是有用的 ...）
（哦对就算这些，一般本科也不会全都学，能学一半就不错了，SJTU 这个课貌似还是有基本的完成度的，也只是讲了基本的东西，我们专业 Compiler 课居然是选修 ...）

对于非编译器领域的人（这个“编译器领域”其实不算小 ... 做深度学习框架的其实有一半都能算，就连 Graphics 大佬，PBRT 的作者之一 Matt Pharr 也来插了一脚）来说，学“编译原理”很多时候只和前端部分沾一点边，至于后面的优化和代码生成部分，我说实话真觉得有点屠龙之计的意思 ...
并且很巧合的是，编译器领域所主要集火的中端和后端，与编译器领域之外的人主要集火的前端，虽然都是编译器里面的东西，但是是完全不同的两个东西。很多工业编译器不用 parser generator，而是直接用 Recursive Descent 堆前端，萌新不会玩，搜到啥就看啥（特别还是考虑到国内网络十分缺乏高质量的相关资源），上来就看龙书，从第一页一直看到第 302 页，然后说“编译原理”难（何况就算用 parser generator，也不需要你理解 parser generator 是怎么工作的啊）
我也很无奈啊 ...

相比而言，“解释器”的相关资料一般就友好很多，一般写“解释器教程”的，对读者的 assumption 是：熟悉某一门 GPL （没忘记 GPL 是什么意思吧 ...），但是对“编译原理”完全不了解，认为“编译原理”和编程语言的实现本身很神秘的萌新。这就很适合楼主。这类教程的最后作品一般也和楼主的“计算器”很类似。

像 https://v2ex.com/t/554319，https://v2ex.com/t/607304 这些帖子都出现了类似的现象

（当然严格来说，“解释器”也可以做得很复杂，不过一般意义上的“解释器”最多止于 bytecode 这一层，之后如果要做什么 JIT 之类的，这些内容就和传统意义上的“编译原理”直接重合了。）
（为什么搜“编译原理”或者“Compiler”不是正道，我再举个例子，你说你想写个 DSL，找个 Compiler 的课程看吧，结果好死不死选了 CMU 的 15-411，这就爽了，你还没理解第一个 Slides 说的“Focus on code generation and optimization”是什么意思的时候，第二节课就开始 Instruction Selection 了，然后 Register Allocation，然后第一个 Lab 就让你实现一个 Code Generator ...）

[thedrwu]

关于计算器：
1、手写个简单的 LL 前端就能解析这类语法了。
2、可以考虑拓展上矩阵，加减乘除（逆）、行列式、LU 分解、对称正定矩阵的解、QR 分解、求特征值、SVD 分解。当然只是简单的玩玩，毕竟复杂的问题不会人肉填矩阵。



对于最后一段：楼主既然是工科，可以写写行业软件，写的过程中顺便能打好扎实的专业基础。

[Mohanson]

编译原理走起…

在下周的中国开源年会上我要演讲的内容就是编译器，感兴趣可以看下我的演讲稿，适合初学者入门

http://accu.cc/content/speech/minits/

[Mohanson]

如果不想搞符号优先级的话可以直接逆波兰表达式走起，比特币脚本也用的逆波兰

[cmdOptionKana]

楼主你初学玩到这个程度，非常优秀了，建议这个项目先玩到这里不要深入了。可以直接进入下一个阶段，选一个方向，比如想做安卓 app 就学 java，想做苹果 app 就学 swift，想做网站就学前端和选一个后端框架，学了这些之后可以玩的就丰富了，等遇到瓶颈再补基础知识。

[crella]

@thedrwu 矩阵这个有想过，用户层命令新建矩阵的时候，在类里面设定好应该就容易操作了。主要是用了 octave 美滋滋，暂时不想折腾矩阵。

[crella]

@secondwtq 感谢。我是没想那么多，主要是不想折腾 matlab 语法就自己搞个方便用的工具，本身也没想让别人都能用上。还有弄 cgi 是因为不习惯用 tk 做界面，还有用了 tk 就不知道怎么操作后台线程(资料少……)。本来是想 vb.net 做界面的，通过 http 访问，也做了一个小界面，还能用。不过按 vb 的计算按钮时，ruby 的命令行会弹出临时的黑框，看起来非常不爽。搞到云服务器上应该就没问题了。

之前看过一个 c#例子，也是不使用 eval，通过编译执行新文件来算表达式的，可能是为了兼容性吧，非常长，还只是应付四则运算

[crella]

@cmdOptionKana 说实话只对嵌入式和模拟电路有兴趣……要不然也不会试过逼自己用 c++写过计算的部分

[secondwtq]

@Mohanson 这个有意思，我当初就是想写一个 TS 的静态版，没想到一入此坑深似海 ...

nit:
> 编译器是一种将源语言翻译为另一种等价语言的程序软件
编译器对语言的等价性没有要求，只是源代码和目标代码的语义是等价的（经过优化之后语义可能也不完全等价）

> minits 项目的主要工作就集中在中端
生成 IR 一般是算在前端里面的，比如 LLVM 有 Clang、Julia、F18、Rust 等多个“前端”，LLVM 自身算是“中端”+“后端”。LLVM 代码里面有个 CodeGen 文件夹和 Target 文件夹，这俩主要构成“后端”，也就是 LLVM IR->MC，但是 Clang 代码里面也有个 CodeGen 文件夹，这个算是“前端的后端”，也就是 AST->LLVM IR，和 LLVM 的 CodeGen 是有区别的。中端就是 IR->IR。

> 在做语法分析时常用的技术手段是 "Increamental parsing", 也就是增量分析.
我认为对于新人来讲应该重点讲 Recursive Descent，Incremental Parsing 是比较高级的东西
另外看了这一段我是没理解 Incremental Parsing 是怎么做的
最后我觉得 ... 用自然语言举例有点糟糕

> 这在 C 代码中是无法想象的, 因为 C 的基本规则是先声明后赋值. 在 TS 中却可以这么用, 因为 TS 里有一个专门的模块负责维护代码内所有变量的类型, 函数签名或类签名. 这个模块的名字是 TypeChecker
有点乱 ... 首先 C 和 TS 在这里不一样，原因就是 C 标准和 TS 标准的规定不一样，也就是说是个设计问题，不是实现问题。另外 C 编译器一般也有“一个专门的模块负责维护代码内所有变量的类型, 函数签名” ... 一般编译器都有这个东西，这个叫 Symbol Table，然后操作 Symbol Table 的模块可能叫 TypeChecker （ Clang 里面直接就叫 Sema ），TypeChecker 的作用首先是 check，其次才是 infer。

> LLVM 是一个模块化的编译器套件, 它同样遵循上面的几个原则, 但它最伟大的贡献在于提出了通用中间语言表示, 也就是 LLVM IR. 但其实在 LLVM 之前, 绝大部分编译器都有自己的中间表示, 但缺点是它们是不通用的--也就是只在自己的领域内使用. 大部分后端优化, 比如消除冗余代码, 它们的算法是相同的, 但在 LLVM 之前它们要在不同的语言上各自实现一遍. 像 GCC, 它为了支持不同硬件平台, 它内部的许多编译阶段必须做到硬件无关性, GCC 内部使用了一种硬件平台无关的语言, 这个中间语言的名字叫 RTL
据我了解 GCC 有不止一个 IR，除了 RTL 之外至少还有 GENERIC 和 GIMPLE （ LLVM 其实也不止一个，只不过就使用层面而言主要用 LLVM IR ），RTL 已经比较底层了。GENERIC 其实也是 language-independent IR。LLVM 做得好的一个是 License （在当前）占便宜，一个是历史包袱比 GCC 小，然后是把生态建设起来了。换句话说“通用中间语言表示”一直都有，只是在 LLVM 之前一直没人用。
GCC 社区现在已经开始想要解决人员不足的问题了。比如参加 LLVM 的 conference 就算学生也是要收你五十刀的，GCC 的 conference 是免费的，如果是学生甚至可以申请路费赞助，可见 ...

> 实现完全复用 Clang 的 IR 优化和对应硬件平台的代码生成
Clang 不做优化和 CodeGen，这是 LLVM 做的，只是用 Clang 做了 driver

最后我觉得你可以额外讲一下这个项目之后的前景，比如现在是完全没有动态内存分配的 ... 当然作为一个入门教程这些倒没什么必要，不过如果我在现场的话我会提这个问题的

[Mohanson]

@secondwtq 感谢指正！我目前也是个初心者，没想到在 v 站炸出个大佬！

前后端分类那段已纠正！

增量分析那段是有点问题，写的时候确实纠结了很久，改一下。

clang 不做优化和对应硬件平台代码生成，这里我想表达的是复用 clang 这个命令行工具，因为优化，编译 c 代码都是用这个命令行工具实现的

[crella]

稍微更新一下：首先搞上了 json 保存、读取配置。然后通过“写入、修改外部 ruby 脚本，然后 load”，实现 eval 的等效功能，就不需要再通过读写 txt 来传递结果值了。这种 load 方式速度快一点，但是对消耗内存的影响我估计不了。

自动测试结果：

PS D:\rubyhome\xl3\3.2.0> ruby .\start-cli.rb
(:) (12-55-58) : 版本:3.2.0b
:) autotest#
(:) 正在解析命令:3+2
5.0
(:) 正在解析命令:1+cos(pi/3)-ln(1)
1.5
(:) 正在解析命令:setn#k = 1
(:) 已新建变量

(:) 正在解析命令:k - 0.5
0.5
(:) 正在解析命令:shown#
pi = 3.1416;e = 2.71828;k = 1;

(:) 正在解析命令:setfx#f(x) = x * x - 1.5 * x
(:) 已新建函数

(:) 正在解析命令:showfx#
f (x) = x*x-1.5*x

(:) 正在解析命令:dlim('f', 3)
4.5
(:) 正在解析命令:dv('f', 3)
4.5
(:) 正在解析命令:ig('f', 2, 3)
2.583
(:) 正在解析命令:fill#{x+2:1->3}*{x/3:1->3}+{x*2:2->4}
5.0;;7.0;;9.0;;6.0;;8.0;;10.0;;7.0;;9.0;;11.0;;5.333;;7.333;;9.333;;6.667;;8.667;;10.667;;8.0;;10.0;;12.0;;5.667;;7.667;
;9.667;;7.333;;9.333;;11.333;;9.0;;11.0;;13.0;;

(:) 正在解析命令:walkx#f(x)
x = 0.0
x = -0.0
x = 0.01
x = -0.01
x = 1.49
x = 1.5
x = 1.51

(:) 正在解析命令:walkxy#'x+y-2;x*x+y*y=3'
x = 1.71, y = 0.28
x = 0.28, y = 1.71
x = 1.71, y = 0.29
x = 0.29, y = 1.71
x = 1.71, y = 0.3
x = 1.7, y = 0.31
x = 0.31, y = 1.7
x = 0.3, y = 1.71

(:) 正在解析命令:sn#x+f(x):1->3,4,6->0.5->7
142.5

(:) 正在解析命令:deln#k
(:) 已删除变量

(:) 正在解析命令:delfx#f
(:) 已删除函数