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

非码农想学点 C 然后写 Interpreter/Virtual Machine/Compiler 玩儿,求问数据结构和算法这块需要多少知识?

  •  
  •   levelworm · 2019-10-09 09:32:13 +08:00 · 3092 次点击
    这是一个创建于 1870 天前的主题,其中的信息可能已经有所发展或是发生改变。
    目前工作是 BA,主要是写 SQL 查询。之前自学过 C++,不过写的很烂。现在在看 C,想要以后自己写解释器编译器之类的玩儿。求问下看编译原理之前,数据结构和算法这块需要懂得点啥?类似的项目我没做过,可能有点相关的就是一个简单的 JSON parser,但其实是看着 VB 代码搬过来的。

    我学 C++的时候能够写堆栈、链表和二叉搜索树。但是高级一点的,比如平衡二叉树和图我都没学会。

    要求不高,能够手撸一个短小精悍的脚本语言就成了。查了下似乎前端已经比较自动化了,但是我还是想手撸 Parser。我已经三十多岁了,不指望转码农,就是当初玩无冬之夜的时候特别着迷它的脚本语言,写了不少脚本,自那之后就一直想自己弄一个。
    24 条回复    2019-10-09 17:32:42 +08:00
    zjsxwc
        1
    zjsxwc  
       2019-10-09 09:37:39 +08:00   ❤️ 1
    龙书
    salamanderMH
        2
    salamanderMH  
       2019-10-09 09:42:38 +08:00   ❤️ 1
    编译原理及实践这本书简单点。
    itenyh
        3
    itenyh  
       2019-10-09 09:46:59 +08:00 via iPhone   ❤️ 1
    喜欢写代码,不用当码农,码农是青春饭
    levelworm
        4
    levelworm  
    OP
       2019-10-09 09:47:26 +08:00
    @zjsxwc
    多谢啊,这本书我听好几个人说起来了,看来是经典。
    Context free grammar 我是不是也要搞一下?不过那本书里头有了。
    levelworm
        5
    levelworm  
    OP
       2019-10-09 09:50:34 +08:00
    @salamanderMH 多谢!看了一下目录的确也不错,步子似乎小一些
    stormhouse
        6
    stormhouse  
       2019-10-09 09:53:24 +08:00 via Android   ❤️ 1
    推荐这个 http://craftinginterpreters.com 第二部分
    感觉对初学者很友好
    结合郑刚的《自制编程语言》
    我目前能写个简单的表达式解析了
    zhuangzhuang1988
        7
    zhuangzhuang1988  
       2019-10-09 09:55:44 +08:00   ❤️ 2
    先看 antlr 的两本书 <Language Implementation Patterns> <The Definitive ANTLR 4 Reference>好用,工具齐全,知道工业级的代码有啥.
    parsec 相关的少花时间, 语法糖, 对写算法没啥提高
    然后再看理论书.
    GeruzoniAnsasu
        8
    GeruzoniAnsasu  
       2019-10-09 09:59:34 +08:00 via Android   ❤️ 1
    以及推荐一下 llvm 的 tutorio


    写出一个 parser 其实相当于数据结构刚学会了链表,虽然能用来做不少事了但也刚入门而已( interpreter 只要能撸出来 parser 就已经完成大部分了)
    jimrok
        9
    jimrok  
       2019-10-09 10:10:59 +08:00   ❤️ 1
    python 不是很好了,也可以嵌入到应用里,你用 c++做个桥,接上去,就能用脚本控制你的代码了。
    fcten
        10
    fcten  
       2019-10-09 10:21:42 +08:00   ❤️ 1
    有理论基础的话,看着 lua 的代码照着撸就是了。没有就先学一下编译原理。
    favourstreet
        11
    favourstreet  
       2019-10-09 10:29:41 +08:00 via Android   ❤️ 1
    写 c 的解释器不需要多少编译原理的东西,但是强烈建议看一看 c 的标准 ISO9899 (草案),这个标准会为你实现 c 的编译器 /解释器提供极大的帮助;另外建议以实现自举为目标(解释器自己能嵌套运行),这个不难,很重要,而且据我的经验,很有成就感
    levelworm
        12
    levelworm  
    OP
       2019-10-09 11:10:59 +08:00
    @favourstreet 多谢,不过这要求离我很远,我慢慢来,先写个简单的解释器。。。不过能想象出来会很有成就感。
    kele1997
        14
    kele1997  
       2019-10-09 11:22:02 +08:00   ❤️ 1
    github 上的 c4 很短,可以看一看, 然后下面的那个是教程版
    c4 实现了自举哦
    nianyu
        15
    nianyu  
       2019-10-09 11:33:56 +08:00   ❤️ 1
    我想知道推荐龙书的自己看没看完 况且 lz 说了非码农, 写点编译器用得到看龙书? 简单的网上一大把的博客百行代码的简易实现. 可以先看看王垠的文章 如何写一个解释器
    hmzt
        16
    hmzt  
       2019-10-09 11:35:20 +08:00   ❤️ 1
    解释器很好写的,不需要太多知识,会字符串处理就差不多了,编译器的汇编部分就比较麻烦了
    levelworm
        17
    levelworm  
    OP
       2019-10-09 12:11:37 +08:00
    @kele1997 多谢,没想到炸出来这么多牛人。。。
    levelworm
        18
    levelworm  
    OP
       2019-10-09 12:14:32 +08:00
    @hmzt 这块我看过一点东西,印象最深刻的就是怎么用 two passes 来读入函数信息,比如说 parameter 和 local variable。觉得的确是聪明啊。。。
    wangyzj
        19
    wangyzj  
       2019-10-09 12:24:44 +08:00   ❤️ 1
    老哥,勇气可嘉
    但能有你这种心态才能永远保持年轻和竞争力啊
    jon
        20
    jon  
       2019-10-09 14:08:47 +08:00
    收藏一下
    YourLord
        21
    YourLord  
       2019-10-09 14:10:01 +08:00 via Android   ❤️ 1
    BA 为啥要学 C/C++?

    Python 用处更大。
    seraphv3
        22
    seraphv3  
       2019-10-09 17:17:25 +08:00
    我看过虎书 C 语言版前半部分,照着做了学校的课程大作业。做解释器应该容易点,要做汇编代码生成,寄存器分配真是难,不管 x86 还是 MIPS。印象中数据结构和算法有一些,像符号表(里面有 hash 运算,类似于实现了一个 java 的 HashMap )、语法树、中间代码树,不过没有什么需要预先学习的,用到的时候看看就行了
    tankren
        23
    tankren  
       2019-10-09 17:23:01 +08:00   ❤️ 1
    是我就不会自学这种 怎么学都比不上专业的 对自己工作 /职业发展无用的 技能
    lazydog
        24
    lazydog  
       2019-10-09 17:32:42 +08:00 via Android   ❤️ 1
    github 上的 build your own x 项目可以帮到你!
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1144 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 23:02 · PVG 07:02 · LAX 15:02 · JFK 18:02
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.