• KnowNothing
    2019-08-16
    老师,在关键字和保留字的识别上,我认为有不需要加入中间状态的更简单的方式:
    完成词法分析后,遍历所有ID token,如果其text在关键字和保留字集合内,将该token类型改成对应的关键字/保留字类型。
    或者,
    每当识别出一个ID token,都检查其text,如果是在关键字和保留字集合内,纠正type。

    作者回复: 没错,可以的。
    但是构造成有限自动机的话,程序就可以标准化处理。不需要再手写其他代码。比如正则表达式工具。

    当然,如果纯手写词法分析器,不受任何标准算法的限制的话,那发挥空间就会大很多。

    爱动脑的好同学!

     5
     29
  • kirogiyi
    2019-08-17
    宫老师,例子里面的词法分析大多是靠条件判断来实现,如果对一门完整的语言来进行分析的话,工作量会不会很大。我在想,是否有其他方式可以实现?

    作者回复: 课程的示例代码的主要目的是把意思讲明白,我甚至把状态都用枚举表示,就是为了易读。性能不是第一考虑。
    从性能的角度,词法分析可以用查表的方法实现状态迁移。在每个状态,接收什么字符,切换到另外的状态。那样更快,这是常用的方法。
    不光词法分析可以这么做,语法分析也可以。基于表驱动。这时候,最重要的是构造那张表。代码的话,就不大看明白是啥意思。

    
     22
  • 傲娇的小宝
    2019-08-18
    感觉有限状态机有点类似图灵机的工作方式。我一般只用正则匹配一下文件名或者某个字符串是否符合我的预期。

    作者回复: 有限自动机是比较简单的一种自动机,对应于正则文法,也叫做3型文法。
    比它强大的是下推自动机,对应于上下文无关文法,也叫做2型文法。
    比它更强大的是线性有界自动机,对应于上下文相关文法,也叫1型文法。
    图灵机的范围比它们都大,它对应0型文法。你任何能用产生式写出来的文法规则,都属于0型文法。

    希望对你有帮助,了解有限自动机和图灵机的关系:)

     1
     17
  • Fan
    2019-08-16
    宫老师,有没有一些词法分析的demo可以推荐看看呢?

    作者回复: 最好的demo,就是现有语言的词法分析器,比如Java的、GNU c的,都能拿到源代码。比如Java的编译器在JDK的源代码里就有。

    此外,我们在后端时会讲到LLVM工具。LLVM的文档里有一个小的教程,做了一个完整的前端。你也可以参考一下。http://llvm.org/docs/tutorial/MyFirstLanguageFrontend/LangImpl01.html

    回头我整理一份清单放到github上,告诉大家去哪里下载。你的需求估计其他同学也有。

    谢谢你!

     1
     17
  • 逗逼师父
    2019-08-17
    老师您好,我的疑问是,age>=45的有限状态机图中,为什么比较操作符不像标识符那样停留在同一个状态?我觉得>和>=都是属于比较操作符呀

    作者回复: 很好的问题。
    是这样的。从Token分类的角度,我们确实可以把这两个归为一类。
    但如果把它们看做同一个状态,就会有一些问题。比如,接收到=号应该怎么处理呢?接收第一个=号,仍然处于比较操作符状态。那么接收第二个呢?问题是,有限状态机接收字符的时候,是没法数个数的。如果你要记个数,也就相当于在内部新增加了一个状态,还是等价于两个状态。我这么说你理解吗?

     3
     9
  • devna
    2019-08-16
    之前做的一个项目中有大量的历史遗留脚本是用Perl写的,于是主动去学了下Perl,不得不说,Perl是我见过所有语言里对正则表达式支持最强的,效率也是最高的(我想可能是因为Perl在语言核心内置了正则表达式引擎,不像其他语言,是通过各种模块支持的)。
    后来从Perl了解到《精通正则表达式》这本书,买来看了下,确实是很好的一本书。虽然读完很久很多东西都忘了,但是对正则表达式的理解深刻了很多。

    作者回复: great!
    基于你已有的积累,是否可以进一步想想,能否自己写一个支持正则的工具?比如像grep、sed这些超级命令一样。那几个命令被认为是神级的命令,就是因为支持正则表达式,让它们能适应各种情况。

     1
     9
  • 梓航(﹏)
    2019-08-17
    我是来提意见的,麻烦老师在讲示例的时候,把对应的github链接贴上,而不是在最后贴一个总的地址,我点进去一脸懵,哪个文件对应哪个例子啊?

    作者回复: 好的,谢谢您提意见!已通知后台调整一下。
    02课的文件是目录中的SimpleLexer.java文件。

    另,如果到github的https://github.com/RichardGong/PlayWithCompiler项目主页,里面有每堂课的课件的介绍,供您参考。

    
     8
  • 诺亚
    2019-08-25
    isAlpha 的 alpha 好像没有字母的意思吧?用 alphabet 会不会比较合适点?

    作者回复: 你很细心,所以我也仔细给你解答下:-)
    isAlpha是 is alphabetic 的缩写。isalpha()函数是好几个语言的标准库里都提供的,比如C、python等。
    alphabet指的是整个字母表,不是字母表里的单个字母。

     1
     6
  • xindoo
    2019-08-16
    正则表达式匹配3的任意倍数 https://www.zhihu.com/question/24824487

    作者回复: 哇,真好玩!
    点赞!

    
     5
  • (╯‵□′)╯︵┻━...
    2019-10-03
    有回随手发现Google搜索可以使用正则表达式……然后感觉星星都亮了

    作者回复: 嗯。等你学了算法篇第16讲,了解了正则表达式的机制后,可以设计点正则表达式测试一下谷歌的性能,看看能否把谷歌的服务器累趴下...

    
     4
  • 请叫我赓哥
    2019-08-28
    您好,老师,初步接触编译原理,您讲的手工打造词法分析,是用已知的java或c或其他语言实现,我想问一下,c语言的编译器是用什么实现的呢,或者其他语言的编译器?另外其他的词法分析器又是用什么语言编写的呢,谢谢

    作者回复: 在编译领域,有一个事情,叫做自举(bootstraping),也就是这门语言的编译器可以用自己这门语言编写。这是语言迈向成熟的标志。一般前面的版本,是要借助别的语言编写编译器,但后面就应该用自己的语言来编译了。
    著名的语言都实现了自举。比如,go语言的编译器是用go编写的(早期版本应该是用C语言写的编译器。能实现自举,还是go发展历程上的一个历程碑),jdk里面自带了java语言的编译器,本身也是用java写的。
    更早的语言,那当然是用汇编写编译器。比尔盖茨当年就是用汇编写。
    掌握编译原理之后,其实用什么语言都可以写。
    这门课程的示例语言是playscript。我有计划后面把playscript实现自举。

    
     3
  • 好吃的呆梨
    2019-08-16
    ts的实现,请老师和同学指正。https://github.com/sheeeeep/fundamentals-of-compiling/blob/Ch02/src/lexical-analyser.ts

    作者回复: 非常好!要号召大家跟你学习!
    太棒了!

    你有精力的话,还可以再精进一下,参考一下成熟编译器的词法分析工具,从课程示例的代码的基础上再提升一个等级:)

    比如说,另一个同学提到过,如何提升词法分析的性能什么的。

     2
     3
  • 冬瓜
    2019-08-16
    int 后面的 id 的正则是不是 [a-zA-Z_][0-9a-zA-Z_]*这样就行,为啥要将数字通过|连接呢?是不是有什么用意😳

    作者回复: 就是个习惯而已,把数字和字符分两组。

    我们在写正式的词法文件时,有时会这么写:
    Id: Charactor (Charactor | Digit)*
    Number: Digit+
    Charactor: [a-zA-Z_]
    Digit: [0-9]

    这时候,Digit在几个不同的规则中是复用的。

     2
     3
  • 鱼_XueTr
    2019-08-16
    正则表达式在做爬虫和文本处理中用过比较多。

    作者回复: 是滴。
    程序编译的第一阶段工作,本质也是文本处理。

    
     3
  • 哆啦B梦จุ๊บ
    2019-11-20
    听了老师的讲解,感觉没有想象的那么难,不管好坏,先敲一版出来总是没错的:
    https://github.com/zyfandtmx/compile/blob/master/src/main/java/mycompiler/lexical/LexicalAnalysis.java

    作者回复: 看到了,不错!
    破山中贼易,破心中贼难。
    任何高峰,都是能找到一条缓坡上去的。

    
     2
  • 恩佐
    2019-11-01
    https://github.com/shaojintian/learn_compiler
    老师能看看我的lexer么?用golang写的
    请老师和同学们指正,感谢

    作者回复: 看了你的代码,挺不错的。如果再补充一下README,让人可以迅速build和测试你的项目就更好了。

     1
     2
  • 阿尔伯特
    2019-08-31
    Mark.
    https://github.com/albertabc/compiler/blob/master/main.cpp

    作者回复: 下载,编译,并运行了。
    你提供的cmake配置很赞,让编译很顺畅!
    也看出你C++功底很扎实呀!
    再次点赞!

     1
     2
  • 乐毅
    2019-08-24
    老师,是否可以将关键字和保留字预先存储起来? 如果可以,那和文中描述的方式有什么区别吗?

    作者回复: 可以呀。
    算法可以是灵活的,可以有多种实现。课程里讲的理论往往更通用,比如可以根据正则表达式自动生成有限自动机。
    在具体领域中,比如如果只是给计算机语言做词法分析,当然可以针对关键字这种特殊情况做特殊处理。
    所以,在实际工程中,往往比纯原理更简单。因为允许变通。

    
     2
  • benben
    2019-08-16
    每当看到状态机图后就感觉明白怎么做了!老师的图真厉害😄

    作者回复: 谢谢肯定:)

    
     2
  • (口-口)🌟
    2019-08-16
    一般都是用来批量的处理数据的,比如把csv格式转换为json格式,方便程序操作,或者从日志冲筛选出指定的字段。

    作者回复: 谢谢分享!
    没错,这是词法分析的应用之一。
    再进一步,在处理一些复杂格式的日志时,仅仅用词法分析还不够,还要加上语法分析功能才行。

    
     2
我们在线,来聊聊吧