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

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

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

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

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


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

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