V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
Zeahoo
V2EX  ›  程序员

学完编译原理你有什么收获?

  •  1
     
  •   Zeahoo · 2016-01-09 17:19:09 +08:00 · 14290 次点击
    这是一个创建于 2321 天前的主题,其中的信息可能已经有所发展或是发生改变。

    这个学期选了编译原理这门课,但是我只有学会了几种语法分析的方法,比如 LR(0), LR(1), SLR(1) 等……想问大家学了这门课都了解了一些什么?这些语法分析的方法对我们实际写代码或者理解代码有什么用处?

    74 条回复    2021-09-19 17:49:46 +08:00
    SPACELAN
        1
    SPACELAN  
       2016-01-09 17:38:20 +08:00
    用来装逼,逼格还是挺高的
    fy
        2
    fy  
       2016-01-09 18:18:43 +08:00   ❤️ 1
    用来装逼: https://github.com/fy0/tinyre
    这门课赋予了你构建软件行业基石的能力。
    xiandao7997
        3
    xiandao7997  
       2016-01-09 18:23:37 +08:00   ❤️ 1
    上次看到在 v2 有人在写 markdown 解析器时用到了编译原理里的一点知识
    codesun
        4
    codesun  
       2016-01-09 18:28:43 +08:00
    如果只是讲解了文法分析,那还叫编译原理吗?至少有语义制导,三地址码翻译吧?就是没有学优化和 codegen 的内容,光用这些内容,也够你写个玩具语言了,难道这对你理解现存的语言没有任何帮助?
    Zeahoo
        5
    Zeahoo  
    OP
       2016-01-09 18:42:27 +08:00
    @codesun 好吧,你说的我都听不懂,文法分析这一部分也是很吃力的学下来了,至于你说的语义制导,三地址码翻译我刚才看了目录才发现有这些东西。这门课学的时候也是迷迷糊糊的ˊ_>ˋ,看来还是要继续往下看~
    fetich
        6
    fetich  
       2016-01-09 18:42:57 +08:00
    保研要用的……
    EchoChan
        7
    EchoChan  
       2016-01-09 18:57:11 +08:00 via Android   ❤️ 2
    我们老师在最后一节又苦口婆心地跟同学们说,你们丫,不要每次遇到一些需要学习的东西就问有什么用?你让我怎么说呢?一个东西的用途不仅仅因为它的性质,更多的是它应用的潜在价值。你了解了它的产生背景,你就知道人们当初发明、发现、研究它的原因了,但是我跟你说它的当初的作用你也不会感兴趣的 。
    他举了几个例子,想说明的无非就是我们这一代人的浮躁以及功用主义。
    holulu
        8
    holulu  
       2016-01-09 18:59:24 +08:00
    能玩的东西多了。
    EchoChan
        9
    EchoChan  
       2016-01-09 19:04:14 +08:00 via Android
    诚然我是认为教材的内容编得不好,提高了学生对课程的理解。

    很多地方如果有图表影音来降低学生对知识理解的门槛,然而都是干巴巴的文字。并不是每个人都智商超群,也并不是每个人都能做到时刻专注。对于很多学生来说,这门课确实就是艰涩难懂。

    你说到对于码代码有什么用,我觉得这门课主要让人认识到不一样的思维模式。具体而言就是使得在未来进行问题求解时能有不一样的思路。
    aisk
        10
    aisk  
       2016-01-09 19:11:14 +08:00   ❤️ 1
    @EchoChan 我觉得他要是能说清楚到底有啥用也就不用这么废话了。
    EchoChan
        11
    EchoChan  
       2016-01-09 19:28:12 +08:00 via Android
    @aisk TM 的要怎么说清楚,既然说不清楚那还不如引导那些有意愿学好的人去了解产生原因
    aisk
        12
    aisk  
       2016-01-09 19:31:02 +08:00   ❤️ 1
    @EchoChan 你他妈的你老师自己就说不清楚,然后只能装逼绕过来说,你他妈的懂了吗?
    ljcarsenal
        13
    ljcarsenal  
       2016-01-09 19:35:07 +08:00 via Android
    对于调调 api 填填框架来说的程序员确实没什么用。
    EchoChan
        14
    EchoChan  
       2016-01-09 19:38:10 +08:00 via Android
    @aisk 你确定你看懂我的话?
    aisk
        15
    aisk  
       2016-01-09 20:00:08 +08:00   ❤️ 2
    @EchoChan 你的大意就是“虽然 XXX 看上去没什么用,但是你在 XXX 的过程中一定有些什么收获,所以 XXX 还是值得的。”

    一句永远正确但却没有任何意义的废话罢了。

    不过你这人一上来说话就“他妈的”是什么意思,难道你他妈的没好好教你礼貌?
    SonicY
        16
    SonicY  
       2016-01-09 20:06:42 +08:00
    @aisk 别人说的是 ta 妈的,而你直接说 @EchoChan 的妈妈,不太好吧。
    虽说我感觉 TMD 这种口头禅算不了多大点事。
    还是不要歪楼了。。。
    woai110120130
        17
    woai110120130  
       2016-01-09 20:06:46 +08:00
    光一个状态机就受益无穷
    shyling
        18
    shyling  
       2016-01-09 20:32:47 +08:00
    前几天有人跟我说学了编译原理得能写出来个编译器才行。
    jsyangwenjie
        19
    jsyangwenjie  
       2016-01-09 20:49:03 +08:00   ❤️ 4
    编译原理前端那部分真的 P 用没有过。。事实上大部分学校也就讲了前端那点东西,有的老师甚至连 syntax analysis 都讲不清楚。。编译真正好玩有用的从语义分析才正式开始,语义分析中怎么去检查类型,这个类型系统该怎么搞。中间代码该怎么生成,生成以后怎么加 Pass 去优化,然后生成机器码又该怎么去分配指令和寄存器,又要涉及到结构方面的东西。
    然而这个论坛的人只会告诉你,有用的,也不管自己有没有用过,反正他们只知道递归下降 LL LR 。

    顺便贴个论文, http://arxiv.org/abs/1010.5023
    大学里教你的前端那部分,早就在 UNIX 里面用 YACC 和 lex 实现好了,现在又有新的方法出来了。
    大部分人学编译都是龙书吧?手写递归下降或者语法分析有什么意义呢?早就是老的技术了(注意是技术), 并且有人家实现好了工具。其实说白了就是 DP 能解决的问题,讲了那么多什么都学不通。
    Wonicon
        20
    Wonicon  
       2016-01-09 20:49:09 +08:00   ❤️ 2
    前端虽然有那么多强大的算法和工具,但最后还是人肉递归下降分析器更易控制……我觉得中间代码的优化要比语法分析有意思,然而学力有限,没能掌握静态单赋值……要说收获,应用的场景没有遇到,不过对这个领域倒是更加感兴趣了……
    aisk
        21
    aisk  
       2016-01-09 20:54:04 +08:00
    @SonicY 是的,对熟人说话带口头禅,爆粗口啥的,真不是多大点事儿。
    可你跟一陌生人张口就是 TMD ,这他妈的不是有病吗?
    lifanxi
        22
    lifanxi  
       2016-01-09 21:10:18 +08:00   ❤️ 2
    如果你只是记住了 LL(1)、 LR(0)这些名词,而没有理解它们的内在,那么短期内可能除了考试没有别的什么用。

    但是如果理解了内在,就能让它们在相关的领域发挥出作用了。比如,理解了 DFA ,你会发现有很多情况下程序的逻辑都可以建模成一个 DFA ,然后按 DFA 的方式去实现,既简洁又不容易出错。
    initialdp
        23
    initialdp  
       2016-01-09 21:18:22 +08:00
    我是非科班出身,倒是想学习一些这类基础知识,至少对 C 、 Python 等语言会有更深入的理解吧。
    aitaii
        24
    aitaii  
       2016-01-09 21:19:13 +08:00
    收获了一次补考 然后意识到我学的是编译原理。。。
    secondwtq
        25
    secondwtq  
       2016-01-09 21:39:04 +08:00
    刚看到标题,学完?编译原理能学完?给跪了


    @initialdp 貌似编译原理一开始习惯性的用 C , Pascal 之类的做背景,到后面要是点类型系统之类的技能的话就奇葩辈出了..
    Zeahoo
        26
    Zeahoo  
    OP
       2016-01-09 21:41:27 +08:00 via iPhone
    @lifanxi
    @Wonicon
    @jsyangwenjie
    感谢各位的回复!
    Zeahoo
        27
    Zeahoo  
    OP
       2016-01-09 21:41:57 +08:00 via iPhone
    @secondwtq 措辞不当,下次发帖会注意的^ _ ^
    codesun
        28
    codesun  
       2016-01-09 21:50:19 +08:00
    @Zeahoo 如果你对编译感兴趣,可以继续花时间自学,这一块内容实在太多太大,一般的老师也没精力或者说是能力,来上优化,形式化自动验证之类的更深层次的内容。相比之下,前端是编译中最成熟,也是相对简单的一部分,因此大部分课程都将重心偏向于这一部分。

    如果你纯粹是为了学分而选这门课,那我觉得你还是别在这块花时间了,无论是工作还是学术,这一块普通人很难有所成就,当然大牛除外。
    loryyang
        29
    loryyang  
       2016-01-09 22:18:18 +08:00
    大学的课程很多时候就是讲解理论,编译原理课上讲的东西就是比较老的,而且也是都有现成实现的东西了。而这些用编译原理实现的工具或者软件比如 yacc 和 lex 则有着非常强大的功能,使用很广泛。这些东西只能靠自己课外去学习了。
    其实这也是大学课程比较尴尬的地方,很多东西讲的太基础或者偏理论,学了也不知道有什么用,而且大部分情况确实没什么用。那种理论课加实验课组合的形式其实很不错。但是现在的实验课往往偏鸡肋,效果并不好。
    SonicY
        30
    SonicY  
       2016-01-09 22:43:26 +08:00
    @aisk 哈哈因人而异吧,别太放心上。
    ltrans
        31
    ltrans  
       2016-01-09 22:45:55 +08:00 via Android   ❤️ 1
    噗。。。编译原理的实验课用 php 实现了词法分析器 23333
    noli
        32
    noli  
       2016-01-09 22:47:41 +08:00   ❤️ 2
    觉得编译原理没有实际用处?

    来,我们来实现一个 Web url 路由,支持动态绑定资源处理方法,譬如模仿一下 flask restful ?

    什么?你不知道什么叫做 web url 路由?

    那跟你说这些有什么用……
    orafy
        33
    orafy  
       2016-01-09 23:07:26 +08:00   ❤️ 2
    游戏程序员,工作中撸了个自定义的 Shading Language ,和 3 个后端: GLSL , HLSL , PSSL 。

    不仅减少了重复,
    还扩展了预处理(可以选择某个 define 是生成新 shader 或 dynamic branching ),
    也实现了反射(不再需要在运行时 glGetUniformIndices 之类的)。

    编译原理就是这些很有趣的事情的基础。
    forrestchang
        34
    forrestchang  
       2016-01-09 23:44:59 +08:00
    还没学编译原理,不过倒是写了个 Scheme 的解释器: https://github.com/forrestchang/Charon
    strwei
        35
    strwei  
       2016-01-09 23:48:18 +08:00
    000000100000000100000011
    fashioncj
        36
    fashioncj  
       2016-01-10 00:03:57 +08:00
    这些东西都是以后不知道什么时候就会用到的知识,不过考试周学习能力就是爆表
    Khlieb
        37
    Khlieb  
       2016-01-10 00:08:45 +08:00
    @EchoChan @aisk 决定这些教学内容的,是一群官僚,官僚不但武断的要把这些内容安排到课堂上,而且这些内容还被安排和学业挂钩。同样的内容,有些觉得对自己有用,有些人学了却发现根本就派不上用场,然而他们全然不顾这些。
    congeec
        38
    congeec  
       2016-01-10 00:10:17 +08:00 via iPhone
    我没学过这个,但我感觉王银的博客你一定要看,学习也好撕逼也罢,看完肯定有收获。 Yinwang.org
    kaichen
        39
    kaichen  
       2016-01-10 00:33:30 +08:00   ❤️ 2
    你如果知道了一个语言从源代码到可执行程序的过程(当然也有可能是编译结果是另外的编程语言,比如 Babel 做的事情)后,会更容易理解现在市面上流行语言为什么会设计成这样,为什么会具有某些行为。在你选择一个编程语言去做某件事时会更加有理有据。

    并且当你了解各种流行的语法特性怎么实现,例如说闭包,那么在写程序用到的时候就能知道,为什么某种写法就会导致内存泄漏,以及如何才能避免。
    RitzoneX
        40
    RitzoneX  
       2016-01-10 01:23:29 +08:00
    恩,写个操作系统
    MiguelValentine
        41
    MiguelValentine  
       2016-01-10 02:46:55 +08:00
    @RitzoneX 那不是编译原理能做到的。你说的是汇编。
    编译原理的本体是让你学会写语言解释器或者理解它。
    总而言之,如果你用汇编举其他高级语言,除了优化部分其他毫无用处。

    国内的教学有坑。学紫龙书的基础应该是有汇编基础才可以。
    noli
        42
    noli  
       2016-01-10 02:54:03 +08:00
    @jsyangwenjie 尽管 LR Parser Generator 已经不是什么高深的技术,手写递归下降目前依然是多数商业编译器的主要实现方式,因为这样的错误提示比较容易做得友好,投人力就可以搞好了——然而前提是,做这些的人必须要理解 LL ,不然根本无法工作。
    budlion
        43
    budlion  
       2016-01-10 09:11:52 +08:00
    工作中就曾利用 antrl 写过一个代码翻译器,把几百个 java 接口转换成 js ,和也曾实现过一套 DSL 语法来实现邮件查询。有兴趣可以尝试读一下 The Definitive ANTLR 4 Reference , 或者 Language Implementation Patterns, 应该会有个不错的启发。
    madshaw
        44
    madshaw  
       2016-01-10 09:57:17 +08:00 via Android
    感觉用来解决模式相关的问题非常爽
    jsyangwenjie
        45
    jsyangwenjie  
       2016-01-10 10:29:38 +08:00
    @noli 告诉我做商用编译器开发的有多少人?再告诉我这么些人中有多少人做的是前端部分?
    Haku
        46
    Haku  
       2016-01-10 12:14:22 +08:00
    至今不会用变量,练就了一套手撕内存的好技巧
    pyufftj
        47
    pyufftj  
       2016-01-10 12:52:22 +08:00
    @congeec 这个人我一直关注他,是王垠不是银。他语文水平是 IT 界里我见过最高的
    WalkingEraser
        48
    WalkingEraser  
       2016-01-10 12:58:23 +08:00
    C++是世界上最牛逼的语言(゜o゜;
    LazarusX
        49
    LazarusX  
       2016-01-10 14:17:52 +08:00
    目前正在通过上 Coursera 上 Stanford 开的 Compilers 课程和阅读《 Engineering a Compiler 》这本书自学编译原理。楼主问的是「学完编译原理你有什么收获」,那我说说学习编译原理之前我希望得到的收获。我自学编译原理,主要是纯粹对编译的过程比较好奇,知其然也想知所以然,本科时候没有修过编译原理,趁最近有点时间,就捡起来看看。我对编译原理这门课最大的期待主要是前端的部分,因为我觉得之后的工作中可能会在一些场景用到这部分的知识,比如解析复杂文本,设计并解析一种 DSL 等等。现在差不多把 parser 的部分学完了,在做编程作业的过程中,发现自己已经开始会对一门语言的语法设计进行揣摩和思考,这恐怕是意外的收获。

    目前感觉前端部分还是比较理解的,后端的技术含量或许更高。虽然我现在对后端部分了解不多,但我觉得如果能学习到一些后端涉及到的算法也挺好的。

    ---

    顺便吐个槽: Stanford 以及其他一些学校开设的编译课程的 parser 的 lab 就是学会使用 bison 或者 CUP ( lexer 的 lab 同理就是学会使用 lex ),我在想为什么不让学生直接手写一个 parser ,用递归下降写一个简单语言的 parser 应该不难,而用 bison 的话,有些过于简单了,而且自己写的东西要被编译一次才能成为编译器源代码的一部分,感觉怪怪的……
    LazarusX
        50
    LazarusX  
       2016-01-10 14:26:59 +08:00
    @LazarusX 再补充一点学习编译原理的原因。

    之前一个项目涉及到了静态分析,过程中遇到一些瓶颈,同学就推荐我学习编译原理,其中的知识或许会对静态分析有帮助。
    jsyangwenjie
        51
    jsyangwenjie  
       2016-01-10 14:32:44 +08:00
    @LazarusX 静态分析的话对前端根本没要求了,好好研究下 LLVM
    xiaoshenke
        52
    xiaoshenke  
       2016-01-10 15:22:53 +08:00 via Android
    装逼用,还有就是学新语言的时候会不自觉思考这用编译器怎么实现
    chenai
        53
    chenai  
       2016-01-10 17:41:55 +08:00
    我们是大三上学期开《编译原理》这门课的,学之前为了预习写了一个编译器 https://github.com/chenai/mini-c ,学完以后为了复习,又写了一个编译器, https://github.com/chenai/lily 当然都是 toy 级别的。

    因为不是做编译器开发的,可能自己水平还没有体会到编译原理有什么好处吧。
    至于 DSL 什么的也想过,不过你觉得中国大多数软件公司有用到的么?
    我理解还不够深,但是我觉得如果你闲着没事,多写点程序,多看看书,多学点知识应该没坏处吧?
    noli
        54
    noli  
       2016-01-10 18:18:09 +08:00
    @jsyangwenjie 偷换概念?我问你一个问题,你认为递归下降分析出错误,然后实现给出错误信息的工作,这部分属于前端还是后端?
    jsyangwenjie
        55
    jsyangwenjie  
       2016-01-10 18:59:37 +08:00
    @noli https://en.wikipedia.org/wiki/Recursive_descent_parser 你告诉我,你连中间代码都没生成是怎么得到 IR 的信息?
    narrowei
        56
    narrowei  
       2016-01-10 19:05:55 +08:00
    。。。为啥我们学校软件工程专业没有编译原理,导致我现在还在纠结要不要买本龙书看看-。-
    noli
        57
    noli  
       2016-01-10 20:39:58 +08:00
    @jsyangwenjie

    1. 不是所有编译过程都需要中间代码,譬如你写一个 web url routing 就没有什么鬼中间代码。但是你依然可以在一遍 pass 的过程中就找出所有注册路由过程中可能发生的错误或者歧义。又譬如 v8 jit 一样也没有什么鬼中间代码,从体验上来说它就是一遍 parsing ,要么出错要么生成 binary 。

    2. “手写递归下降或者语法分析有什么意义呢” 我问的问题是关于你的这个观点的,手写递归下降是很多商业编译器的做法,这些编译器不是用任何什么 lexer generator parser generator 整出来的。你跟我扯什么前端后端,现在又扯什么 IR ,让我觉得你好像没有实在地使用过编译器的技术……

    事实就是,一个十几人的编译器 team (再大一点的我就真没见过了),确实很少时候需要把精力放在 parsing 的阶段(可能这是你说的所谓前端?),主要精力都是放在生成优化,可能就是你说的 IR 阶段……

    手写递归下降有什么意义?除非在 LR 分析技术有什么重大突破吧,不然 LL(*) , 例如 ANTLR 这样的工具所使用的 parsing 技术才是主流,因为这样的 parser 好写,用户友好度高。
    jsyangwenjie
        58
    jsyangwenjie  
       2016-01-10 21:23:38 +08:00
    @noli 你不了解什么是编译器的 front-end 和 back-end 吗?另外我有说把精力放在 IR 阶段吗?我从头到尾在强调的都是编译技术的前端早就成熟了,在这方面挖不出什么新的研究成果了。现在更多的研究在程序分析上,特别是指针分析这两年比较火热。做编译向来就是做优化,这不仅牵扯到 IR ,还有就是体系结构等各个方面的优化。从没听说过谁还在研究前端部分的。

    另外, JIT 是 JIT ,我也没说编译器一定要生成中间代码。

    并且, parser 手写的原因是因为效率更高,至少我跟 IBM 的编译组交流的时候他们是这么跟我说的。当然我同意错误提示更加友好。

    还有, web url routing 跟编译有什么关系?
    noli
        59
    noli  
       2016-01-10 22:17:39 +08:00
    @jsyangwenjie

    1. “手写递归下降或者语法分析有什么意义呢” 这是你自己说的,我只负责告诉你有什么意义。

    2. 在 54 楼我问你,给出错误信息是前端还是后端, 55 楼你反问我关于 IR 的东西。你这是喝多了吧?

    3. 处理 "/api/v1/item/<id:string>" 这样的与 URL 相关的 DSL , 并且绑定到对应的处理器,叫做 url routing 。

    如果你把 LL parsing LR parsing 这部分当作前端,那我可以告诉你, ANTLR 的作者 Terrence Parr 就是研究前端的,教授,他的研究成果就是通用的 LL(*) Parser Generator 。

    LL(*) 的意思是,向前看任意多个 Token ,如果你不明白这是什么意思,那你还是看看龙书再出来教育他人吧。
    jsyangwenjie
        60
    jsyangwenjie  
       2016-01-10 22:26:17 +08:00
    @noli

    我明白了。。。你不是研究 PLT & compiler 相关的,跟你不在讨论一个点上。

    为什么我说没人研究前端了,你查一下 2000 至今 POPL PLDI OOPLA 这些会议上有多少是研究 parser 的:)

    另外, Parr 的研究成果早在 90 年代就发出来了:)

    LL(k)是什么意思不需要您教育。

    讨论就此停止:)
    Winchey
        61
    Winchey  
       2016-01-11 06:12:37 +08:00
    @aitaii 下午要考编译原理,看到这里突然很慌,感觉自己也要挂的节奏。。
    hqs123
        62
    hqs123  
       2016-01-11 08:32:08 +08:00
    学完编译原理再看下计算机构造和解释这本书,感觉收获更多。。。
    shakoon
        63
    shakoon  
       2016-01-11 08:58:10 +08:00
    这门课当年我也学得比较痛苦,然而我现在随便接触一个新语言能很快就上手,与这门课和《形式语言和自动机》有很大关系
    wizardoz
        64
    wizardoz  
       2016-01-11 09:33:28 +08:00
    很多东西都是这样,学会了你才能发现它的作用。不会的人不知道有什么用。
    sun2920989
        65
    sun2920989  
       2016-01-11 09:42:41 +08:00
    能玩的很多,工作能用到的不多.
    Tankpt
        66
    Tankpt  
       2016-01-11 09:49:36 +08:00
    学完的时候。写了个简单的解析 sql 的解析器
    kelos
        67
    kelos  
       2016-01-11 09:50:28 +08:00
    留着以后讲给你的同事听。逼格高到极点,尤其你能考到 90 分,简直可以完爆所有周边人。
    taisenjay
        68
    taisenjay  
       2016-01-11 10:22:10 +08:00
    学完就会做那几个类型的题目
    FireCat
        69
    FireCat  
       2016-01-11 11:21:36 +08:00
    龙书的作者在前言已经说了,编译原理有啥用,我觉得每本书都得看看前言,很急很关键。
    visonme
        70
    visonme  
       2016-01-11 13:14:41 +08:00
    对于大多数人和大多数场景下基本无用。
    印象中第一次使用或者说关联应用是给予底层性能优化上,至于大家说的写编译器,解释器啥的对我们来说还是比较远和不太可能接触的东西
    yuchting
        71
    yuchting  
       2016-01-11 16:50:37 +08:00
    看到标题很冲动,想进来讲一番道理,后来看到大家如此踊跃,作罢。
    举个不恰当的例子:

    请问一下,学医对性生活改善是否有帮助呢?

    有,又没有。
    wizardforcel
        72
    wizardforcel  
       2018-03-08 13:53:04 +08:00
    编译原理(或者其中的形式语言)不仅仅能用于解析程序,也能用于解析数据文件。

    比如说哪天你碰到一个非主流格式的文件就有用了。

    再比如你研究 NLP 的话,肯定有用。
    Zeahoo
        73
    Zeahoo  
    OP
       2018-03-08 14:21:04 +08:00
    @wizardforcel 两年前的帖子被你挖出来了,当初问的时候还是一个学生,现在已经工作了,感谢回复!
    ygmyth
        74
    ygmyth  
       241 天前
    哈哈又三年过去了,请问楼主学了吗
    关于   ·   帮助文档   ·   API   ·   FAQ   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   1416 人在线   最高记录 5497   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 23:33 · PVG 07:33 · LAX 16:33 · JFK 19:33
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.