1
winterbells 2019-10-27 00:49:38 +08:00 via Android
要不照着编译器原理写?。。
|
2
secondwtq 2019-10-27 00:50:13 +08:00
关键字:解释器( Interpreter )
一定要学 fq 我见过最好用的计算器是 Jupyter Notebook 另外我非常好奇你为什么会用 perl6/raku ... "执行一万次运算时 ruby 太慢所以改为 c++写计算文件,ruby 调用 g++编译、执行" G++ 有时候可以比 Ruby 还慢 ... 虽然这里应该不会有太大问题 |
3
Sanko 2019-10-27 00:51:26 +08:00 via Android
编译原理
|
4
crella OP 在 ghub 上找到了一个 c#的,一个 ruby 的,都应该是可以直接借鉴的。
|
5
verrickt 2019-10-27 01:46:02 +08:00 via Android
po 所描述的计算器和编译器有明显的类似之处:根据用户提供的**字符串**产生某个确定性的结果。
简易提几个点,你需要一个组件把用户输入的字符串转化为树状结构,一个组件实现树状结构的计算,一个组件实现输出。 正好对应编译原理的前端,中端,后端。 不这么搞光是个运算符优先级就能搞死个人。 ninputer 有系列博客讲怎么写编译器的,po 可以参考下。里面提到的很多问题都有共性。 |
6
xiadong1994 2019-10-27 02:00:08 +08:00 via iPhone
你要支持复杂表达式就得走编译器 /解释器那一套
|
7
secondwtq 2019-10-27 03:22:45 +08:00 4
@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 ...) |
8
thedrwu 2019-10-27 03:52:45 +08:00 via Android
关于计算器:
1、手写个简单的 LL 前端就能解析这类语法了。 2、可以考虑拓展上矩阵,加减乘除(逆)、行列式、LU 分解、对称正定矩阵的解、QR 分解、求特征值、SVD 分解。当然只是简单的玩玩,毕竟复杂的问题不会人肉填矩阵。 对于最后一段:楼主既然是工科,可以写写行业软件,写的过程中顺便能打好扎实的专业基础。 |
9
Mohanson 2019-10-27 07:27:08 +08:00 via Android
|
10
Mohanson 2019-10-27 07:31:45 +08:00 via Android
如果不想搞符号优先级的话可以直接逆波兰表达式走起,比特币脚本也用的逆波兰
|
11
cmdOptionKana 2019-10-27 07:57:59 +08:00
楼主你初学玩到这个程度,非常优秀了,建议这个项目先玩到这里不要深入了。可以直接进入下一个阶段,选一个方向,比如想做安卓 app 就学 java,想做苹果 app 就学 swift,想做网站就学前端和选一个后端框架,学了这些之后可以玩的就丰富了,等遇到瓶颈再补基础知识。
|
12
crella OP @thedrwu 矩阵这个有想过,用户层命令新建矩阵的时候,在类里面设定好应该就容易操作了。主要是用了 octave 美滋滋,暂时不想折腾矩阵。
|
13
crella OP |
14
crella OP @cmdOptionKana 说实话只对嵌入式和模拟电路有兴趣……要不然也不会试过逼自己用 c++写过计算的部分
|
15
secondwtq 2019-10-27 14:58:39 +08:00 1
@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 最后我觉得你可以额外讲一下这个项目之后的前景,比如现在是完全没有动态内存分配的 ... 当然作为一个入门教程这些倒没什么必要,不过如果我在现场的话我会提这个问题的 |
16
Mohanson 2019-10-27 16:24:07 +08:00 via Android
@secondwtq 感谢指正!我目前也是个初心者,没想到在 v 站炸出个大佬!
前后端分类那段已纠正! 增量分析那段是有点问题,写的时候确实纠结了很久,改一下。 clang 不做优化和对应硬件平台代码生成,这里我想表达的是复用 clang 这个命令行工具,因为优化,编译 c 代码都是用这个命令行工具实现的 |
17
crella OP 稍微更新一下:首先搞上了 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 (:) 已删除函数 |