编译原理之美
宫文学
北京原点代码 CEO
46197 人已学习
新⼈⾸单¥59
登录后,你可以任选4讲全文学习
课程目录
已完结/共 45 讲
开篇词 (1讲)
编译原理 · 期中考试周 (1讲)
编译原理之美
15
15
1.0x
00:00/00:00
登录|注册

05 | 语法分析(三):实现一门简单的脚本语言

'(' additiveExpression ')'
IntLiteral
Identifier
assignmentStatement : Identifier '=' additiveExpression ';'
expressionStatement : additiveExpression ';'
intDeclaration : 'int' Id ( '=' additiveExpression)? ';'
assignmentStatement
expressionStatement
intDeclaration
statement+
递归下降算法的回溯,会导致多少计算时间的浪费?跟代码长度是线性关系还是指数关系?
计算机语言中,有哪些语法在运用递归下降算法的时候,也是会导致回溯的?
设计可能导致递归下降算法中回溯的情景
学完这讲以后,你也能找到了一点感觉:Shell脚本也好,PHP也好,JavaScript也好,Python也好,其实都可以这样写出来
通过对三种语句的支持,实现了一个简单的脚本语言
实现REPL(Read-Eval-Print Loop)
实现一个交互式的界面来输入程序,并执行程序
理解递归下降算法中的回溯
实现赋值语句的解析
实现变量声明、给变量赋值、在表达式中引用变量
使用HashMap作为变量存储区
primaryExpression
赋值语句
表达式语句
变量声明语句
statement
programm
一课一思
课程小结
实现一个简单的REPL
解析赋值语句
让脚本语言支持变量
增加所需要的语法规则
本节课将实现更多功能,使解释器更像一门脚本语言
前两节课掌握了表达式的解析
语法分析(三):实现一门简单的脚本语言

该思维导图由 AI 生成,仅供参考

前两节课结束后,我们已经掌握了表达式的解析,并通过一个简单的解释器实现了公式的计算。但这个解释器还是比较简单的,看上去还不大像一门语言。那么如何让它支持更多的功能,更像一门脚本语言呢?本节课,我会带你寻找答案。
我将继续带你实现一些功能,比如:
支持变量声明和初始化语句,就像“int age” “int age = 45”和“int age = 17+8+20”;
支持赋值语句“age = 45”;
在表达式中可以使用变量,例如“age + 10 *2”;
实现一个命令行终端,能够读取输入的语句并输出结果。
实现这些功能之后,我们的成果会更像一个脚本解释器。而且在这个过程中,我还会带你巩固语法分析中的递归下降算法,和你一起讨论“回溯”这个特征,让你对递归下降算法的特征理解得更加全面。
不过,为了实现这些新的语法,我们首先要把它们用语法规则描述出来。

增加所需要的语法规则

首先,一门脚本语言是要支持语句的,比如变量声明语句、赋值语句等等。单独一个表达式,也可以视为语句,叫做“表达式语句”。你在终端里输入 2+3;,就能回显出 5 来,这就是表达式作为一个语句在执行。按照我们的语法,无非是在表达式后面多了个分号而已。C 语言和 Java 都会采用分号作为语句结尾的标识,我们也可以这样写。
确认放弃笔记?
放弃后所记笔记将不保留。
新功能上线,你的历史笔记已初始化为私密笔记,是否一键批量公开?
批量公开的笔记不会为你同步至部落
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线
笔记
复制
AI
  • 深入了解
  • 翻译
    • 英语
    • 中文简体
    • 中文繁体
    • 法语
    • 德语
    • 日语
    • 韩语
    • 俄语
    • 西班牙语
    • 阿拉伯语
  • 解释
  • 总结

本文深入介绍了如何实现一门简单的脚本语言,通过语法分析和递归下降算法来支持更多的功能,使解释器更像一门语言。作者首先介绍了需要增加的语法规则,包括变量声明、赋值语句和表达式语句等。然后详细讲解了如何让脚本语言支持变量,并通过简单的存储机制实现了变量的支持。接着,作者解析了赋值语句的实现逻辑,包括预读、回溯和消化Token等步骤。最后,作者提到了对变量初始化部分的改造,使其在初始化时支持表达式。此外,文章还介绍了递归下降算法中的回溯特点,以及实现一个简单的REPL的过程。通过具体的代码和解释,读者可以深入了解如何实现一门简单的脚本语言,对读者进行了技术上的引导和指导。整篇文章内容丰富,涵盖了语法规则、变量支持、赋值语句实现、递归下降算法特点和REPL实现等方面,适合对编译技术感兴趣的读者深入学习。

仅可试看部分内容,如需阅读全部内容,请付费购买文章所属专栏
《编译原理之美》
新⼈⾸单¥59
立即购买
登录 后留言

全部留言(34)

  • 最新
  • 精选
  • janey
    像这里用java实现了一种脚本语言,但是这些java语句又是怎么被计算机识别的呢?

    作者回复: java语句当然是由java的编译器来识别了。 不过你提了一个重要的事情。 在编译领域,有一个事情,叫做自举(bootstraping),也就是这门语言的编译器可以用自己这门语言编写。这是语言迈向成熟的标志。一般前面的版本,是要借助别的语言编写编译器,但后面就应该用自己的语言来编译了。 著名的语言都实现了自举。比如,go语言的编译器是用go编写的(早期版本不是。能实现自举,还是go发展历程上的一个历程碑),jdk里面自带了java语言的编译器,本身也是用java写的。

    2019-08-27
    5
    27
  • C语言实现: https://github.com/KiLuYa/simpleScript C语言,没有现成的数据结构,没有 try catch throw 处理错误的机制,没有虚拟机的垃圾回收机制,感觉实现起来比Java要麻烦很多,尤其是繁琐的错误码判断,以及程序流程在多分支下的内存的手动申请和释放。 遇到过一个国外公司的产品,它提供了脚本语言,但用户写程序,如果某一行有个语法bug,编译报错时,它会报连续十几行的错。学完这节内容就知道,应该是它的parser没有在检测到语法错误时停下来,还傻傻地带着错误继续parse,直到所有token都被处理掉。

    作者回复: 看你用C语言做了很多实践,非常好! 针对你的问题,也跟你探讨一下: 1.每门语言都有它的优势。很多编译器都是用C/C++编写的,比如可以更灵活的对内存管理,就是优势呀。JVM的实现,也没法用Java,还是要用比较底层的语言。 2.错误处理这个问题比较复杂。最好的情况,是我们知道哪一个小范围是有错的,对这个部分报错,但其他部分继续处理。比如,你调用一个函数时,监测出参数的数量错了,但其他部分仍然可以继续去解析和处理。如果碰到一个错误,就完全停下,那也不行。这样做IDE的时候,就不够友好和智能。

    2019-09-29
    2
    11
  • 缺个豆饼吗
    https://github.com/yuguomin/my-compiler 老师,作业来啦~

    作者回复: 棒!TypeScript版本的!

    2019-10-08
    6
  • ct
    根据老师讲解,实现了一个 golang 的版本 https://repl.it/@catplanet007/simple-interpreter

    作者回复: 你用的这个在线工具很酷。可以提供一个运行环境直接跑!很棒! 我玩了好一会 :-D

    2019-08-24
    6
  • Fan
    😂,又看了一次。建议老师可以把这两个专栏的内容集结后出书。

    作者回复: 你看第二遍了?为你点赞!看来你对编译是真有兴趣,可以考虑把这个方向变成自己的技术专长,去干一点有深度的事情。 书的话,已经在整理,进度有点慢:-( 因为我又给自己挖了坑,想达到两个目标: 1.要求更加浅显易懂,再复杂的问题,也要简单说明白; 2.里面的例子用自己设计的语言。 所以... 我后面加快进度:-)

    2020-12-10
    3
    4
  • LDxy
    正则表达式匹配文本的时候也会导致回溯吧?好像还有可能因此导致严重的性能问题

    作者回复: 对。如果正则表达式的内部实现是基于NFA的,就会有这个问题。 NFA和DFA这个知识点不适合在前期讲,会把初学者搞晕。我准备在后面找个机会放入这个知识点。

    2019-08-24
    4
  • wj
    老师, 还有个问题, 借此文问一下, 词法分析\语法分析等和机器学习有什么交集吗? 我有个场景想比较两个java文件的匹配度, 或者两段代码的匹配度, 不知道机器学习在这个场景是否可以应用, 以及如何应用呢?谢谢~

    作者回复: 你提了一个好问题。 其实,人工智能的发展史经历了两个不同的路径。 早期,更多的是演绎逻辑。就是人为制定规则,比如自然语言翻译的规则,并不断执行这些规则。 第二条路径,是最近复兴的机器学习的方法。它更多的是归纳逻辑。机器学习是通过数据的训练,把规则归纳出来。这些归纳出来的规则目前还是比较黑盒的,人比较难以解读,但却很有用,更加准确。 你的需求场景用这两种方法应该都能解决,只不过落地时还要考虑很多细节和限制因素。

    2019-08-24
    4
  • 中年男子
    有了前几讲的基础,这一讲很轻松搞定,根据宫老师的java代码我实现了C++版本,其中一些不太清晰的概念通过代码也理解了,老师真的很棒!

    作者回复: 谢谢肯定! 编译原理这门课,是学原理可能学不懂。但真正动手,其实都能写出来。早期写编译器的先驱并没有编译原理课。 并且,很多具体实现过程,是可以偏离死搬教条的原理的。比如,理想情况下要设计无二义性文法。实际应用中,只要针对某个具体算法是无二义的就行了。能实际有用才是硬道理。

    2019-08-25
    3
  • Sudouble
    跟着课程做,一下就明白了。打卡第五节课 https://github.com/potterhere/TheBeautyOfCompiling/tree/master/w5_ReadEvalPrintLoop

    作者回复: 看到你的github空间里有好几个项目,学习力很强! 另外,能否把你的项目整个cmake文件,便于我编译运行?:)

    2019-10-18
    2
    2
  • 曾经瘦过
    学完了这部分之后 感觉 其实编译没有想的那么复杂,通过递归下降,对所有的可能做了处理.不符合的可能回溯 去匹配其他的. 有点感觉了,希望可以一步一步啃下编译原理

    作者回复: 这个“感觉”很重要。保持好。遇到挫折也不要在意!

    2019-09-17
    2
收起评论
显示
设置
留言
34
收藏
沉浸
阅读
分享
手机端
快捷键
回顶部