V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
black11black
V2EX  ›  问与答

各位大大,编译中 parser 如何能够构建出自己的 抽象语法?

  •  
  •   black11black · 2020-02-17 15:13:49 +08:00 · 1456 次点击
    这是一个创建于 1739 天前的主题,其中的信息可能已经有所发展或是发生改变。

    大家好,最近想做一个可编程化的类似 cicd 那种流程控制项目

    我个人比较菜,想先做个简单的 demo,想要实现如下这样的效果:

    def task1(file):
        ffmpeg -i file -o file.mp4 # etc. 
    
    def task2(file):
        # do something else
    
    def workflow(folder):
        foreach file in folder:
            task1(file)
            task2(file)
    

    ↑ 想要实现的是比如往程序里输入这样一个配置文件( python 语法抽象比较简洁,姑且先用类似的语法了)然后程序就会按照我设定好的这一套工作流程,按顺序执行所有设定好的工作。

    要让程序理解输入的工作流程描述文件,需要进行简单的词法和文法分析,然后抽象成 ast,因为只是个简单的 demo,里面没有什么复杂的东西,只要能实现定义与循环执行就可以了,甚至不需要表达式计算的功能

    按我理解,我的算法流程应该是这样的 1、先是词法分析(这个已经搞定了), 2、然后把代码分成一段一段的(比如类似 python 这种按照缩进分段,或者用{}表示,还没想好) 3、然后我需要抽象出一种当前语言的元语法

    #比如
    stmt : stmt expr
    expr : (expr)
    expr : NODE
    

    这种感觉的,(就是编译原理课上教的那种) 4、再然后实现一个 LL1 算法,对每段分别处理,就能 parse 出抽象语法树了。

    现在的一个犯难是并不知道怎么抽象出这种元语法(甚至在这种只有定义和调用、以及循环的简单情况下) 当初编译原理上的课都还给老师了,唉 现在还记得比如如果单纯要写一个描述运算表达式的元语法是很简单的,大概类似这样:

    expr : (expr)
    expr : expr + expr
    expr : expr * expr
    expr : expr - expr
    expr : expr / expr
    expr : NODE
    expr : -NODE
    

    这种感觉,然后实际操作的时候类似一个简单的栈虚拟机就能搞定表达式运算,这个很简单。 但是这种有定义有调用的元语法该怎么写啊,老师当初也没讲过例子啊,啊啊啊啊啊啊啊啊啊啊啊啊

    10 条回复    2020-12-06 03:38:56 +08:00
    scalaer
        1
    scalaer  
       2020-02-17 15:20:58 +08:00
    先定个小目标, 实现个能跑的 dsl,dsl 多了, 再进一步抽象呗
    black11black
        2
    black11black  
    OP
       2020-02-17 15:24:33 +08:00
    @scalaer

    我现在在做的就算 dsl 吧...我觉得我这个目标定的也不大啊

    关于 parse,如果不抽象语法树的话,最土的做法是写很多条件判断,比如在 def 后面找一个 name token,然后再找括号,再找......找不到就报错之类的

    这么写的话感觉就很 low 啊。。
    scalaer
        3
    scalaer  
       2020-02-17 15:44:14 +08:00   ❤️ 1
    你看看 antlr, 没必要自己写 parser
    crella
        4
    crella  
       2020-02-17 16:17:54 +08:00 via Android
    ……隔壁 ruby 做这个感觉还算简单啊,不清楚 python 技术链

    反正我在代码里动态 eval 新的函数是没什么问题
    secondwtq
        5
    secondwtq  
       2020-02-17 17:04:26 +08:00
    随便找个栗子就行: https://www.lua.org/manual/5.3/manual.html
    翻到最底下
    black11black
        6
    black11black  
    OP
       2020-02-17 17:30:32 +08:00
    @secondwtq

    ORZ 好长,翻跪了

    program -> { [ def | statement ] EOL }
    def -> "def" IDENTIFIER "(" IDENTIFIER ")" : block
    block -> "{" statement { EOL statement } "}"
    statement -> "foreach" STRING "in" IDENTIFIER ":" block | simple
    simple -> { IDENTIFIER } | IDENTIFIER '(' IDENTIFIER ')' | IDENTIFIER '=' STRING

    ↑ 所以现在我感觉我设计的语法应该可以抽象成这样
    只有 define,循环 , 执行三个功能,没有 expr 计算。

    然后问题是,这东西咋搞成 LL1parser 啊,看了看感觉全是左循环左因子

    网上看了个例子,简单的 expr 运算拆成 LL1 就要写这么长了:

    s->e
    e->te'
    e'->+te'
    e'->-te'
    e'->空
    t->ft'
    t'->*ft'
    t'->/ft'
    t'->空
    f->NUMBER
    f->'('e')'

    感觉上面的要改的话要写死自己啊。。
    ai277014717
        7
    ai277014717  
       2020-02-17 17:37:01 +08:00
    lex/yacc 或者 antlr 然后直接处理回调就好了。
    momocraft
        8
    momocraft  
       2020-02-17 17:38:44 +08:00
    自己撸一整套本来就是是不小的工程

    如果你面向实用,要用户学你发明的语言也有成本

    要不要考虑用已有的语言+已有的 parser/interpreter
    secondwtq
        9
    secondwtq  
       2020-02-17 17:50:53 +08:00
    @black11black 你为啥非要死抠 LL(1) 呢
    thautwarm
        10
    thautwarm  
       2020-12-06 03:38:56 +08:00 via Android
    还需要帮忙吗?在下可以带给你新世界
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   982 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 22ms · UTC 20:32 · PVG 04:32 · LAX 12:32 · JFK 15:32
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.