编译原理 | 乐趣区

关于编译原理:手写编程语言如何为-GScript-编写标准库

版本更新最近 GScript 更新了 v0.0.11 版本，重点更新了： Docker 运行环境新增了 byte 原始类型新增了一些字符串规范库 Strings/StringBuilder数组切片语法：int[] b = a[1: len(a)];具体更新内容请看下文。前言前段时间公布了 GScript 的在线 playground，这是一个能够在线运行 GScript 脚本的网站，其本质原理是接管用户的输出源码从而在服务器上运行的服务；这几乎就是后门大开的 XSS 攻打，为保住服务器我设置了运行 API 的后端服务的用户权限，这样能够防止执行一些歹意的申请。但也防止不了一些用户执行了一些耗时操作，比方一个死循环、或者是我提供 demo 里的打印杨辉三角。这实质上是一个递归函数，当打印的三角层数过高时便会十分耗时，同时也十分耗费 CPU。有几次我去查看服务器时发现了几个 CPU 过高的过程，基本上都是这样的耗时操作，不可避免的会影响到服务器的性能。应用 Docker为了解决这类问题，很天然的就能想到能够应用 Docker，所有的资源都和宿主机是隔离开的，无论怎么瞎折腾也不会影响到宿主机。说干就干，最初批改了 API 执行脚本的中央： string fileName = d.unix("Asia/Shanghai") + "temp.gs" ; s.writeFile(fileName, body, 438); string pwd = s.getwd(); // string res = s.command("gscript", fileName); string res = s.command("docker","run","--rm","-v", pwd+":/usr/src/gscript","-w","/usr/src/gscript", "crossoverjie/gscript","gscript", fileName); s.remove(fileName); r.body = res; r.ast = dumpAST(body); r.symbol=dumpSymbol(body); ctx.JSON(200, r);次要批改的就是将间接执行的 GScript 命令批改为了调用 docker 执行。 ...

关于编译原理:手写编程语言递归函数是如何实现的

前言本篇文章次要是记录一下在 GScript 中实现递归调用时所遇到的坑，相似的问题在中文互联网上我简直没有找到相干的内容，所以还是很有必要记录一下。在开始之前还是简略介绍下本次更新的 GScript v0.0.9 所蕴含的内容：反对可变参数优化 append 函数语义优化编译错误信息最初一个就是反对递归调用先看第一个可变参数： //formats according to a format specifier and writes to standard output.printf(string format, any ...a){}//formats according to a format specifier and returns the resulting string.string sprintf(string format, any ...a){}以上是随着本次更新新增的两个规范函数，均反对可变参数，其中应用 ... 示意可变参数，调用时如下： printf("hello %s ","123");printf("hello-%s-%s ","123","abc");printf("hello-%s-%d ","123",123);string format = "this is %s ";printf(format, "gscript");string s = sprintf("nice to meet %s", "you");assertEqual(s,"nice to meet you");与大部分语言相似，可变参数实质上就是一个数组，所以能够拿来循环遍历： int add(string s, int ...num){ println(s); int sum = 0; for(int i=0;i<len(num);i++){ int v = num[i]; sum = sum+v; } return sum;}int x = add("abc", 1,2,3,4);println(x);assertEqual(x, 10);// appends "v" to the end of a array "a"append(any[] a, any v){}之后是优化了内置函数 append() 的语义，本次优化来自于 issue12 的倡议：https://github.com/crossoverJie/gscript/issues/12 ...

关于编译原理:里程碑用自己的编程语言实现了一个网站

前言在上一篇《终于实现了一门属于本人的编程语言》介绍了本人写的编程语言 GScript ，在文中提到心愿最终能够应用 GScript 开发一个网站。到目前为止的确是做到了，首页地址： https://gscript.crossoverjie.top/index 要称为一个网站的确有点勉强，不过也是一个动静网页，因为返回的是 HTML，所以在以后阶段只有不嫌麻烦其实也能写一个“合格”的网站，有点像以前咱们学习 Java 时的 servlet。该页面的源码地址在这里：https://github.com/crossoverjie/gscript-homepage 其实总共也就40来行代码： class GScript{ string author; string[] features; string since; GScript(string a, string[] f, string s){ author = a; features = f; since = s; }}func (HttpContext) index(HttpContext ctx){ string[] features = {"statically", "strongly"}; GScript gs = GScript("crossoverJie",features, "2022"); string j = JSON(gs); println(j); string local = getCurrentTime("Asia/Shanghai","2006-01-02 15:04:05"); println("local=" + local); string html = ^ <html> <title>GScript</title> <pre> _ _ ___ ___ ___ ___|_|___| |_ | . |_ -| _| _| | . | _||_ |___|___|_| |_| _|_| |___| |_| v0.0.7 ^+ j +^ </pre> <h1>current ^+ local +^</h1> <p><a href="https://github.com/crossoverjie/gscript-homepage">GScript-homepace source code</a></p> </html> ^; ctx.HTML(200, html);}httpHandle("GET", "/index", index);string[] args = getOSArgs();if (len(args) ==3){ httpRun(":" + args[2]);}else { httpRun(":8000");}全是利用 GScript 所提供的规范库实现的，后文会具体聊聊内置 HTTP 包。 ...

关于编译原理:终于实现了一门属于自己的编程语言

前言都说程序员的三大浪漫是：操作系统、编译原理、图形学；最初的图形学的确是特定的业余畛域，咱们简直接触不到，所以对我来说换成网络更适合一些，最初再加上一个数据库。这四项技术如果都能把握的话那岂不是在 IT 行业横着走了，加上这几年互联网行业越来越不景气，越底层的技术就越不可能被代替；所以为了给本人的 30+ 危机留点前途，从往年上半年开始我就逐步开始从头学习编译原理。功夫不负有心人，通过近一个月的挑灯夜战，每晚都在老婆的督促下才劳动，克服了中途好几次想放弃的激动，终于当初实现了 GScript 一个预览版。预览版的意思是语法结构与整体设计根本实现，后续更新也不太会改变这部分内容、但还短少一些易用性能。个性首先来看看保留环节， GScript 是如何编写 hello world 的。 hello_world.gs: println("hello world");❯ gscript hello_world.gshello world废话说完了接下来重点聊聊 GScript 所反对的个性了。后文会重点阐明每一个个性。例子除了方才提到的 hello world，再来看一个也是示例代码常常演示的打印斐波那契数列。 void fib(){ int a = 0; int b = 1; int fibonacci(){ int c = a; a = b; b = a+c; return c; } return fibonacci;}func int() f = fib();for (int i = 0; i < 5; i++){ println(f());}输入后果如下： 01123整体写法与 Go 官网举荐的相似：https://go.dev/play/p/NeGuDahW2yP ...

关于编译原理:几百行代码实现一个脚本解释器

前言最近又在重新学习编译原理了，其实两年前也温习过，当初是为了能实现通过 MySQL 的 DDL 生成 Python 中 sqlalchemy 的 model。相干文章在这里：手写一个词法分析器尽管实现了相干性能，但当初看来其实实现的比拟糙的，而且也只使用到了词法剖析；所以这次我的目标是能够通过词法剖析->语法分析->语义剖析最终能实现一个功能完善的脚本"语言"。成果当初也有了一些阶段性的成绩，如下图所示：目前具备以下基本功能：变量申明与赋值（只反对 int)二次运算（优先级反对）语法查看debug 模式，能够打印 AST感兴趣的敌人能够在这里查看源码：https://github.com/crossoverJie/gscript 本地有 go 环境的话也能够装置运行。 go get github.com/crossoverJie/gscriptgscript -h或者间接下载二进制文件运行：https://github.com/crossoverJie/gscript/releases 实现以后版本是应用 go 编写的，的确也如题目所说，外围代码还不到 1k 行代码，当然这也和目前性能简陋无关。不过麻雀虽小五脏俱全，从以后版本还是使用到了编译原理中的局部常识：词法、语法分析。根本实现流程如上图：通过词法分析器将源码中解析出 token再通过对 token 推导生成出形象语法树（AST）如果语法语法呈现谬误，这一步骤便会抛出编译失败，比方 2*(1+ 少了一个括号。因为没有应用相似于 ANTLR 这样工具来辅助生成代码（不然性能也不会只有这么点），所以其中的词法、语法分析都是手写的，代码量并不大，对于想要调试的敌人能够间接查看源码。词法分析器：token/token.go:39语法分析器：syntax/syntax.go 其中会波及到一些概念，比方无限状态机、递归降落算法等知识点就没在本文探讨了，后续这个我的项目性能更加欠缺后也会重头整顿。布局最初是画饼阶段了，不出意外后续会持续新增如下性能：更多的根底类型，string/long 之类的。变量作用域、函数。甚至是闭包。OOP 必定也少不了。这些个性都实现后那也算是一个"古代"的脚本语言了，后续我也会持续更新学习和实现过程中的乏味内容。源码地址：https://github.com/crossoverJie/gscript

关于编译原理:编译原理与设计-41-自上而下分析法

自上而下分析法语法树的从左到右叶结点=#，则 #∈L(G)。 1. 文法的逐级优化打消左递归含有A→Aa模式产生式的文法：间接左递归两步或两步以上：间接左递归打消形式：写正规式→转化为右递归间接：先代入提取左公因子通过改写产生式来推延决定预测分析法的工作过程：从文法开始符号登程，在每一步推导过程中依据以后句型的最左非终结符A和以后输出符号a，抉择正确的A-产生式。为保障剖析的确定性，选出的候选式必须是惟一的。S_文法（简略的确定性文法）每个产生式的右部都以终结符开始同一非终结符的各个候选式的首终结符都不同留神：S_文法不含$ \varepsilon $产生式为了退出$ \varepsilon $产生式，须要看非终结符前面能跟什么终结符：FOLLOW集新定义：非终结符A的后继符号集可能在某个句型中紧跟在A后边的终结符a的汇合，记为FOLLOW(A)产生式的可全集产生式A→B的可全集是指能够选用该产生式进行推导时，对应的输出符号的汇合，记为SELECT(A→B) SELECT(A→aB) = {a}SELECT(A→$ \varepsilon $) = FOLLOW(A)q_文法每个产生式的右部或为$ \varepsilon $，或以终结符开始具备雷同左部的产生式有不相交的可全集q_文法不含右部以非终结符打头的产生式新定义：串首终结符集给定一个文法符号串a，a的串首终结符集FIRST(a)被定义为，能够从a推导出的所有串首终结符形成的汇合，包含$ \varepsilon $新 · 产生式的可全集产生式A→B的可全集是指能够选用该产生式进行推导时，对应的输出符号的汇合，记为SELECT(A→B) 如果$ \varepsilon \notin FIRST(a) $，那么SELECT(A→a) = FIRST(a)如果$ \varepsilon \in FIRST(a) $，那么$ SELECT(A→a) = (FIRST(a)-\varepsilon) \cup FOLLOW(A) $LL(1)文法名称含意第一个“L”示意从左向右扫描输出第二个“L”示意产生最左推导“1”示意在每一步中只须要向前看一个输出符号来决定语法分析动作2. FIRST集和FOLLOW集的计算每一个都是循环应用，直到不再增大 FIRST集 a. 找右侧第一个为终结符或空串 b. 找右侧，从左至右，非终结符的FIRST集FOLLOW集

关于编译原理:BITMiniCC-从跑通到跑路

须要java版本大于15 1. 下载从GitHub下载BITMiniCC压缩包，解压 2. 关上右击文件夹，抉择用IDEA关上抉择Trust Project 3. 更改编码抉择GBK点击convert抉择UTF-8点击convert 4. 设置我的项目构造工具栏File中抉择Project Structure，抉择Modules点击图中的×，删除默认的我的项目构造点击减少根目录抉择BITMiniCC文件夹，显示应与下图雷同 5. 设置我的项目库抉择Libraies，点击+号抉择lib文件夹，点击确定点击确定，后果如图所示 6. 设置main函数配置参数点击run中的edit configuration将框中内容改为你要剖析的C文件门路（图中为scanner的test文件） 7. 剖析config.xml配置文件 skip= 示意是否跳过，true为不运行该步，图中仅运行词法剖析scanpath= 剖析代码的门路，空字符串为默认门路，前面本人写词法剖析后这里要改批改后功败垂成，间接run就能够后果：词法剖析后果：

关于编译原理:编译原理-正规式运算四个特例理解

1. 先验常识设∑为无限字母表，在∑上的正规式与正规集可递归定义如下：和是∑上的正规式，它们示意的正规集别离为{}和；对任何a∈∑, a是∑上的正规式,它的正规集为{a}；若 r,s 都是正规式 , 它们的正规集别离为R和S , 则(r|s)、(r·s)、(r)*也是正规式，它们别离示意的正规集是：R∪S,RS,R*。此处重点为正规式示意的正规集为{}正规式示意的正规集为正规式(r|s)示意的正规集为R∪S正规式(r·s)示意的正规集为RS正规式(r)*示意的正规集为R*其中正规集RS应用的是汇合的乘积运算,定义如下：因而, 下文特例中正规式运算将用正规集运算, 形象化解释 2. 注释·A汇合运算为{}A=A因而·A=AØ·A汇合运算为ØA=Ø因而Ø·A=Ø|A汇合运算为{}∪A设A={a1,a2,a3...} 若a1,a2,a3...≠, {}∪A={,a1,a2,a3...}若a1=, {}∪A={a1,a2,a3...}因而|A后果为正规式A', 正规式A'的正规集为{}∪A Ø|A汇合运算为Ø∪A=A因而Ø|A=A

关于编译原理:编译原理与设计-2-词法分析

预处理：转换为字符串或字符词法剖析1. 基本功能1.1 词法规定语言因素：语法（语言的形容规定）、语义（语言的含意）巴科斯-诺尔范式BNF[元语言符号] <>:→(::=):示意“定义为”或“由……组合成”|: “或”字符与字符串字母表符号串: *中的元素符号串长度||前缀、真前缀后缀、真后缀子符号串（子串）1.2 定义：正规式递归定义: 构造方法设∑为无限字母表，在∑上的正规式与正规集可递归定义如下和是∑上的正规式，它们示意的正规集别离为{}和对任何a∈∑, a是∑上的正规式,它的正规集为{a} 若r,s都是正规式 , 它们的正规集别离为R和S , 则(r|s)、(r·s)、(r)也是正规式，它们别离示意的正规集是：R∪S,RS,R 无限次应用上述三条规定形成的表达式，称为∑上的正规式，仅由这些正规式示意的汇合为正规集正规式：汇合符号，正规集：汇合正规式的运算字母表→根本正则式→递归正则式根本正则式: 字母自身正规式：词法的示意办法确定无限状态机：词法的识别方法

关于编译原理:编译原理与设计-12-编译器介绍

编译器1. 编译程序的示意须要体现编译程序的三要素: 目标语言 T宿主语言 C源语言 S函数示意T = C(S)T型图示意梯形图只有单梯形图和三梯形图符号示意 $$C_{宿}^{源目}$$

关于编译原理:编译原理与设计-11-编程语言

1. 动静类型与动态类型参考: https://zhuanlan.zhihu.com/p/... 动态类型变量的类型必须先申明，即在创立的那一刻就曾经确定好变量的类型，而后的应用中，你只能将这一指定类型的数据赋值给变量。如果强行将其余不相干类型的数据赋值给它，就会引发谬误。在编译阶段实现数据类型的相容性查看动静类型将什么类型的数据赋值给变量，这个变量就是什么类型在运行阶段实现数据类型的相容性查看动静类型语言举例： PHPRubyPython动态类型语言举例： CC++JAVAC#2. 强类型与弱类型参考：https://zhuanlan.zhihu.com/p/... 强类型语言(类型不平安语言)强类型语言是一种强制类型定义的语言，即一旦某一个变量被定义类型，如果不经强制转换，那么它永远就是该数据类型。弱类型语言(类型平安语言)弱类型语言是一种弱类型定义的语言，某一个变量被定义类型，该变量能够依据环境变动主动进行转换，不须要通过现行强制转换。强类型语言举例： JavaC++Python弱类型语言举例： VBPHPJavaScript补充：隐式类型转换两种模式的隐式类型转换：相干类型之间隐式转换如：一个int类型的数据与一个float类型的数据相加不相干类型之隐式间转换如：一个int类型数据与一个字符串类型数据相加

关于编译原理:elixir-0084-关于-DFA确定性有限自动机的那些事儿

最近在看编译原理这本书，感觉是很棒的入门书（指难度由浅入深深深深）。前两章次要是一些概念性的货色，第三章就开始动真格的，上代码上公式了。不本人实现一下，根本就是看得云里雾里的。所以接下来一段时间可能会不定期地更新一些对于我在编译原理这本书里看到的货色的实现的文章。书本的第三章介绍了 DFA 是如何对字符串进行匹配的，例如，正则表达式 (a|b)*abb 能够转换为以下的 DFA 代码。通过状态机的机制在读取字符时切换以后状态，并依据最初的状态来确定匹配是否胜利。 defmodule DFA do def init(string) do %{ s: 0, chars: String.to_charlist(string) } end def run(%{s: s, chars: [h | t]}) do s = move(s, h) run(%{s: s, chars: t}) end def run(%{s: s, chars: []}) do if s in f() do :yes else :no end end defp move(0, ?a), do: 1 defp move(0, ?b), do: 0 defp move(1, ?a), do: 1 defp move(1, ?b), do: 2 defp move(2, ?a), do: 1 defp move(2, ?b), do: 3 defp move(3, ?a), do: 1 defp move(3, ?b), do: 0 defp f(), do: [3]end这个 DFA 只会匹配到以 "abb" 结尾的字符串： ...

关于编译原理:编译原理之美1-前端技术

一、参考编译原理学习系列目录——更新ing 了解代码：编译器的前端技术二、编译器的前后端前端 —— 编译器对程序代码的剖析和了解过程，通常只和语言的语法无关，跟指标机器没有关系后端 —— 生成指标代码的过程，和指标机器无关三、词法剖析

关于编译原理:编译原理之美1-概览

一、参考编译原理学习系列目录——更新ing 了解代码：编译器的前端技术二、

关于编译原理:编译原理-学习系列目录更新ing

一、编译原理之美学习一、参考操作系统学习系列目录——更新ing 设置工作模式与环境（上）：建设计算机

关于编译原理:编译原理之前端

前端：编译器对程序代码的剖析和了解过程。词法剖析: lexical analysis，分词实现原理：无限状态机，如lex GNUlex 语法分析: 依据语法规定生成程序的语法结构(形象语法数AST) 递归降落办法，Yacc、 JavaCC 、GNU Bison 、Antlr 语义剖析: 上下文剖析打消歧义 * 变量援用消解、作用域\~\~\~\~ * 合法性检查 * 数据类型标识 * 语义剖析的某些后果，会作为属性标注在AST上后端：生成指标代码的过程，和指标机器相干。

关于编译原理:编译原理AST

AST：形象语法树（abstract syntax code，AST）是源代码的形象语法结构的树状示意，树上的每个节点都示意源代码中的一种构造，这所以说是形象的，是因为形象语法树并不会示意出实在语法呈现的每一个细节，比如说，嵌套括号被隐含在树的构造中，并没有以节点的模式出现。咱们将源代码转化为AST后，能够对AST做很多的操作，包含一些你想不到的操作，这些操作实现了各种各样不拘一格的性能，给你带进一个不一样的世界。懂编译原理的确能够随心所欲。 Most compilers break down into three primary stages: Parsing, Transformation, and Code GenerationParsing is taking raw code and turning it into a more abstract representation of the code.Transformation takes this abstract representation and manipulates to do whatever the compiler wants it to.Code Generation takes the transformed representation of the code and turns it into new code.ParsingParsing typically gets broken down into two phases: Lexical Analysis and Syntactic Analysis. ...