首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

如何在yacc中使用递归来打印AST?

在yacc中,要使用递归来打印AST(抽象语法树),可以通过以下步骤实现:

  1. 首先,在yacc文件中定义AST节点的数据结构,每个节点包含相应的属性和子节点。
  2. 在yacc文件中,为每个语法规则添加相应的动作(action)。在动作中,可以创建AST节点,并将属性和子节点与规则中的符号关联起来。
  3. 在动作中使用递归来处理每个子节点,直到达到AST的叶节点。对于每个子节点,可以调用相应的打印函数来打印节点的内容。

下面是一个示例,假设我们要解析的语言中有一个规则叫做"expression",其中包含两个子节点"term"和"expression":

代码语言:txt
复制
%token ID
%token NUM

%%

expression: term '+' expression
           | term
           ;

term: ID
    | NUM
    ;

%%

在动作中,可以创建一个"Expression"节点,并将其子节点与规则中的符号关联起来。然后,使用递归来处理每个子节点,直到达到AST的叶节点。

代码语言:txt
复制
expression: term '+' expression
           {
               $$ = new ExpressionNode("+");
               $$->addChild($1);  // 将term节点作为子节点添加到Expression节点中
               $$->addChild($3);  // 将expression节点作为子节点添加到Expression节点中
           }
           | term
           {
               $$ = $1;  // 如果只有term节点,直接将其作为Expression节点返回
           }
           ;

接下来,在程序中实现一个递归打印函数来打印AST的内容:

代码语言:txt
复制
void printAST(Node* node)
{
    if (node == nullptr) {
        return;
    }

    // 打印当前节点的内容
    cout << node->getValue() << endl;

    // 打印子节点的内容
    for (auto child : node->getChildren()) {
        printAST(child);
    }
}

在以上示例中,"Node"表示AST节点的数据结构,包含"value"属性和"children"子节点列表。

最后,将递归打印函数应用于AST的根节点,即可打印出完整的AST:

代码语言:txt
复制
int main()
{
    // 解析输入的字符串,生成AST的根节点
    Node* root = parseInput();

    // 打印AST的内容
    printAST(root);

    return 0;
}

以上是一个简单的示例,演示了如何在yacc中使用递归来打印AST。实际应用中,根据具体语言和AST的结构,可能需要进行适当的调整和扩展。同时,可以根据需要使用腾讯云提供的相关产品,例如腾讯云函数(云函数)来实现云计算方面的功能,具体推荐的产品和链接请参考腾讯云官方文档或咨询腾讯云官方支持。

页面内容是否对你有帮助?
有帮助
没帮助

相关·内容

TiDB SQL Parser 的实现

Spark的SQL解析就是使用了ANTLR。Lex & Yacc 相对显得有些古老,实现的不是那么优雅,不过我们也不需要非常深入的学习,只要能看懂语法定义文件,了解生成的解析器是如何工作的就够了。...我们可以从一个简单的例子开始: 上图描述了使用Lex & Yacc构建编译器的流程。Lex根据用户定义的patterns生成词法分析器。...Yacc 生成的语法分析器使用自底向上的归约(shift-reduce)方式进行语法解析,同时使用堆栈保存中间状态。...我们可以使用 position 的形式访问堆栈的项,1引用的是第一项,2引用的是第二项,以此类推。 上面例子语法规则关联的动作,在完成语法解析的同时,也完成了表达式求值。...statement ast.StmtNode } 在语法解析过程,非终结符会被构造成抽象语法树(AST)的节点 ast.ExprNode 或 ast.StmtNode。

51210

🛰️ 递归思想

无限递归(而不归、死递归),栈溢出(函数的调用有时间和空间的开销,一个程序同时调用的函数个数是有限的)。...图片递归函数分为两类:在去的过程解决问题在归来的过程解决问题举例说明:图片去过程解决问题:前面人手中的子弹总数加上自己手上的,告诉下一个人,最后把子弹总数回传给上一个人。...图片归来的过程解决问题:把消息传递下去,让最后的人把手中的子弹数告诉前一个人,前一个人加上后一个人告知的数量,继续向前传递。图片递归函数的参数在每次调用时应该是不同的!...如何在递归和循环之间选择?一般情况下,当循环方法比较容易实现时,应该避免使用递归。...当很难简历一个循环方法时,递归可能是一个很好的选择(某些情况下,递归方法总是显而易见的,而循环方法却是难以实现)某些数据结构(树)本身就是递归时,则使用递归也是最好的方法了。

795161
  • TiDB 源码阅读系列文章(五)TiDB SQL Parser 的实现

    我们可以从一个简单的例子开始: [1240] 上图描述了使用 Lex & Yacc 构建编译器的流程。Lex 根据用户定义的 patterns 生成词法分析器。...Yacc 生成的语法分析器使用自底向上的归约(shift-reduce)方式进行语法解析,同时使用堆栈保存中间状态。...我们可以使用 $position 的形式访问堆栈的项,$1 引用的是第一项,$2 引用的是第二项,以此类推。$$ 代表的是归约操作执行后的堆栈顶。...statement ast.StmtNode } 在语法解析过程,非终结符 会被构造成抽象语法树(AST)的节点 ast.ExprNode 或 ast.StmtNode。...这段代码的运行结果如下,依次输出遍历过程遇到的节点类型: *ast.SelectStmt *ast.TableOptimizerHint *ast.TableRefsClause *ast.Join

    4.6K100

    (1)PHP内核 - 玩转php的编译与执行

    反序列化0day,溯源使用imap_open到底是如何绕过disable_function限制的,在WP5.0 RCEmkdir的差异,到今年四月份在twitter看见的chdir 配合ini_set...PHP内词法分析和语法分析分别使用的是re2c和yacc来完成的。其实准确来说一个应该是re2c和bison。...其中 表示在使用token时候会进行类型的转换,所有的token类型定义在YYSTYPE,这个结构前面也说过了是一个联合体,在yacc自动的生成yyparse函数下,获取的token对应的内容会保留在...yylval,所以在使用的时候,会进行yylval.ast类似的操作。...,再加点东西,在输出debug过程,它不会自己输出相对于的token的值,因为前面说道过了token的值类型是zend_parser_stack_elem,是我们自定义的,同样如果我们想要打印token

    1.9K10

    编译原理初学者入门指南

    词法分析器(lexer)生成终结符,而语法分析器(parser)则利用自顶向下或自底向上的方法,利用文法定义的终结符和非终结符,将输入信息转换为 AST(抽象语法树)。...也就是我们在此次需求需要获得的东西。 三、工程实践 我们的案例是使用 golang 来编写 lexer 和 parser。 在工程上,不同语言的实践方式是不一样的。...3.2 使用 goyacc 的思路 yacc 类工具的共同特点就是,通过编写 .y 格式的说明文件定义语法,然后使用 yacc 命令行工具生成对应语言的源代码。...在 goyacc ,lexer 本身相对简单,自己编写 go 代码实现就够了,parser 部分所需的文法约定,需要我们编写 .y 文件,也就需要了解 yacc 的文法约定。...而 yacc 只包含定义文法的语法,不含各类编程语言的语法,所以聪明的你肯定能猜到,yacc 文件免不了会出现类似宏定义的东西,会直接嵌入各类编程语言的代码片段。

    2.4K21

    编译入门 - 从零实现中文计算器

    https://woopen.github.io/ccalc/ 前言 其实前端开发,大量使用的编译器相关的知识。比如 webpack 是怎么知道你的 JS 文件依赖哪些其他 JS 文件?...Lex 常常与 yacc 语法分析器产生程序一起使用yacc(Yet Another Compiler Compiler),是Unix/Linux上一个用来生成编译器的编译器(编译器代码生成器)。...yacc生成的编译器主要是用C语言写成的语法解析器,需要与词法解析器Lex一起使用,再把两部分产生出来的C程序一并编译。...GNU bison基本兼容Yacc,并做了一些改进。它一般与flex一起使用。 上面介绍了几个有名的工具,这些工具在其他语言中都有对应的类库,比如 JS 的 bison 叫 jison。...比如下图是字符串 1 + 2 * (3 + 4) 生成的 AST。 可以发现字符串的括号并没有与之对应的节点,而是使用树的层级来描述对应的优先级。

    76810

    eKuiper 源码解读:从一条 SQL 到流处理任务的旅程

    ,也有一些其他 well-known 的数据库实现使用yacc 的方案来直接生成 SQL Parser。...自己实现 SQL Parser 而非使用 yacc 这类的 Parser Generator 的技术,有助于控制和降低 eKuiper 编译后整体的 binary size 的大小。...信息绑定到 ast 对象。...从 AST 对象中将查询的 filed 与各个流、表进行绑定当我们处理好 AST 树对象的各个节点的信息绑定后,我们就可以根据 AST 树对象来构造一个最初的逻辑计划。...在后续的分享,我们将以具体 SQL 为例,深入到各个环节、算子的内部执行的代码逻辑,从而让大家更好地理解 eKuiper 是如何在边缘端接受数据、处理计算并最终写入下游的整体流程。敬请期待。

    37810

    递归和迭代

    一.递归(Recursion) 1.递归:以相似的方式重复自身的过程 2.递归在程序中表现为:在函数的定义中直接或间接调用函数自身 3.递归和循环: (1)递归是有去(去)有回(归来),因为存在终止条件...,比如你打开一扇门还有一扇门,不断打开,最终你会碰到一面墙,然后返回 (2)循环是有去无回,但可以设置终止条件,比如你打开一扇门还有一扇门,不断打开,还有门,没有终点 4.递归的去和归来: (1)递归的去...:原问题必须可以分解成若干个子问题,而且子问题须与原始问题为同样的事(相似),且规模更小 (2)递归的归来:子问题的演化必须有一个明确的终点,否则可能导致无限递归(无终止条件的循环),也就是说不能无限制地调用本身...迭代则使用计数器结束循环。...,但是迭代不一定有递归,大部分可以相互转换.能用迭代的不用递归, 5.迭代在程序的表示: (1)必须设置计数器,可以通过计数设置或条件设置,否则会一直迭代 (2)必须有返回值可以作为再次迭代的初值

    68530

    题型篇 | 数据结构与算法之链表系列

    2、栈实现 从头到尾遍历单链表,将数据存储按照顺序存储到栈。然后遍历整个栈,打印输出数据。...3、递归实现 可以通过递归的方式来实现单链表从尾到头依次输出,递归过程涉及到“”和“归”,反转链表输出数据,正式利用了循环“”的过程,所以数据先从头部输出,那么递归采用的是“归”的过程来输出内容,输出当前结点先要输出当前节点的下一节点...关于递归重复计算问题,我们通常使用自下而上的解决思路(动态规划)来解决递归重复计算的问题。 ▉ 注意事项 1、涉及到循环解决的问题,可以想一想能不能使用归来解决。...2、操作上 递归:链表的很多操作都是可以用递归来进行解决的,因为链表的每个结点都有着相同的结构,再加上解决的问题可以分解为子问题进行解决。所以在链表递归编程技巧还是非常常用的。...:从尾到头打印链表、合并两个有序链表、反转链表等。 双指针:链表中大部分都是进行指针操作,链表属于线性表结构(形如一条线的结构),很多问题可以使用双指针来解决,也是非常常用到的。

    60010

    微信安全下一代特征计算引擎的探索与实践

    在上述的架构,执行引擎执行用户编辑的计算逻辑, z = x + y, 对输入数据进行计算,输出需要的特征,是系统的核心组件。 特征计算引擎探索 执行引擎的实现有多种方案可选,如下图所示的6种方案。...DSL的编译报错提示不友好不准确,因为语法解析器Parser采用的是Yacc工具生成,Yacc使用的是LALR算法, 该算法缺陷之一是编译报错提示不够准确友好,实际使用过程也是如此,业务同学也是常咨询...Clang的语义检查与一般方法不同,常规方案方法是在生成抽象语法树AST之后,遍历AST进行检查。而Clang在AST节点生成过程即时检查语义。...使用的是BackendConusmer读取AST,同样如果自定义AST处理逻辑,可以重新它的如下等函数 示例clang-funcnames实现了自定义的MyASTConsumer。...节点的函数,访问表达式VisitDecl和访问声明VisitDecl,都是可重写的函数: 示例clang-funcnames实现了自定义的MyASTVisitor: 总结下一下,如果使用Clang进行静态代码分析

    23310

    【蓝桥杯Java_C组·从零开始卷】第七节、递归

    使用递归需要注意哪些问题? 递归思想解决了哪些经典的问题? 是什么递归? 定义    在数学与计算机科学,递归(Recursion)是指在函数的定义中使用函数自身的方法。...实际上,递归,顾名思义,其包含了两个意思: 和 归,这正是递归思想的精华所在。 递归的精髓(思想)是什么?    正如上面所描述的场景,递归就是有去(去)有回(归来),如下图所示。...总的来说,归纳法主要包含以下三个关键要素: 步进表达式:问题蜕变成子问题的表达式 结束条件:什么时候可以不再使用步进表达式 直接求解表达式:在结束条件下能够直接计算返回值的表达式 事实上,这也正是某些数学的数列问题在利用编程的方式去解决时可以使用递归的原因...明确递归终止条件    我们知道,递归就是有去有回,既然这样,那么必然应该有一个明确的临界点,程序一旦到达了这个临界点,就不用继续往下去而是开始实实在在的归来。...i--; // 去 return f(i);// 到最深处后,不断地归来 } } } 递归的应用场景 在我们实际学习工作,递归算法一般用于解决三类问题

    31710

    【Flink】第二十八篇:Flink SQL 与 Apache Calcite

    它的作用是进行语法检查,并构建由输入单词(Token)组成的数据结构(AST)。...常见解释器:Apache Antlr、SQLParser、Apache Calcite(JavaCC) Apache Antlr ---- 概念: 它的鼻祖级工具是lex、yacc。...实现这个需求,需要按照java规范,将源码的每个词法(public、class、package)、类名、包名等转换成对应的字节码。那么如何取得这些词、类名、包名、变量名呢?...、~、=、>等)、双字符(>=、<=)等 关键字,Java的class、package、import、public等 2....我们看config.fmpp, 至此,我们大致了解Flink是如何在工程角度与Calcite相遇的,更多细节限于笔者能力和时间有限就不过多展开了。

    2.3K32

    算法渣-递归算法

    前言 之前的排序算法 《快速排序》 与 《归并排序》 都使用了递归手法,如果不能理解递归,那分治思想类算法实现就难以理解 递归 To iterate is human,to recurse divine...因为是描述问题,归是解决问题。而我的大脑容易被占据,只往远方去了,连尽头都没走到,何谈回的来 递归就是有去(去)有回(归来) 为什么可以”有去“?...这要求这些问题不断从大到小,从近及远的过程,会有一个终点,一个临界点,一个baseline,一个你到了那个点就不用再往更小,更远的地方走下去的点,然后从那个点开始,原路返回到原点 递归三要素 用程序表达出来...{ //先将问题全部描述展开,再由尽头“返回”依次解决每步剩余部分的问题 recursion(小规模); //go; solve;...VS迭代 递归算法与迭代算法的设计思路区别在于:函数或算法是否具备收敛性,当且仅当一个算法存在预期的收敛效果时,采用递归算法才是可行的,否则,就不能使用递归算法 参考资料 怎么更好地终极理解递归算法

    73130

    借助yacc和lex自制计算器——《自制编程语言》一

    在mycalc可以使用四则运算,即+、-、*、\。       ○ 整数。1、2、3等。       ○ 实数。123.456等。       ○ 换行符。...一个算式输入后,接着输入换行符就会执行计算,因此这里的换行符也应设置为记号     在lex使用正则表达式定义记号。...这一部分是使用正则表达式*去描述记号。 在规则区块遵循如下的书写方式:一个正则表达式的后面紧跟若干个空格,后接C代码。如果输入的字符串匹配正则表达式,则执行后面的C代码。...yacc的规则区块由语法规则以及C语言编写的相应动作两部分构成。 语法规则     在yacc,会使用类似BNF(巴克斯范式)的规范来编写语法规则。...所谓冲突,就是遇到语法模糊不清的地方时,yacc报出呃错误。

    4.6K10

    Calcite系列(六):执行流程-语法解析

    的树状语法结构,可基于递归下降算法(自顶向下)构造,其中根节点(RootNode)可代表整个语法树 目前广泛使用的语法解析框架主要包括ANTLR、JavaCC和Yacc等。...然而,Calcite使用JavaCC编译器进行语法解析。 在Calcite,Parser.jj是最核心的词法&语法分析文件。...类似 抽象语法树 在Calcite,基于SqlNode表示AST抽象语法树,一个SqlNode可对应语法树的一个节点,即对应SQL语句中的一个元素。...从整体上看,SQL解析将SQL转为AST抽象语法树,该语法树是朴素的,无元数据绑定的,也无法直接进行查询优化。...但基于语法树遍历,也可以挖掘丰富的SQL执行信息,目标库表、数据血缘、防御SQL注入攻击、热度分析等。

    57873

    Yacc 与 Lex 快速入门(词法分析和语法分析)

    -n不打印 -v 的汇总。 高级 Lex Lex 有几个函数和变量提供了不同的信息,可以用来编译实现复杂函数的程序。 下表列出了一些变量和函数,以及它们的使用。...这可以使用 Lex 来完成。 编写一个函数,通过调用 yyparse() 来开始解析。 编写错误处理例程( yyerror())。 编译 Yacc 生成的代码以及其他相关的源文件。...(这一段是可选的,如果有人想要略过它的话:)一个函数 main() 调用 yyparse() 函数(Yacc Lex 的 yylex() 等效函数)。...对于由 Lex 生成的 lexer 来说,要和 Yacc 结合使用,每当 Lex 匹配一个模式时都必须返回一个标记。...如果 Lex 和 Yacc 一起使用的话,头文件必须在相应的 Lex 文件 .lex的 C 声明段包括。

    5.5K20

    什么是递归?

    我们使用的词典,本身就是递归,为了解释一个词,需要使用更多的词。...具体到计算机中去 [2]: 递归(英语:Recursion),又译为递回,在数学与计算机科学,是指在函数的定义中使用函数自身的方法。...而对应的中文翻译 ”递归“ 却表达了两个意思:”“+”归“。 这两个意思,正是递归思想的精华所在。从这层次上来看,中文翻译反而更达意。 2....递归思想 递归就是有去(去)有回(归来)。 具体来说,为什么可以”有去“?...用递归来解决这些问题,往往几行代码就搞定了一些看起来相当”吓人“的问题。 当然,递归的性能问题是另一回事,栈的分配,函数调用代价都是在具体工程实践要考虑的。

    1.5K00

    你真的懂递归吗?

    学会了用递归来解决问题的这种思维方式,再去学习其他的算法思想,无疑是事半功倍的。 递归的本质 「无可奈何花落去,似曾相识燕归来。」 递归,去的过程叫“” ,回来的过程叫“归”。...我们平时使用高级语言来写的 if..else.. 也好, for/while 也好,在实际的机器指令层面来看,就是一个简单的地址跳转,跳转到特定的指令位置,类似于 goto 语句。...我们再来看一个生活的例子,大家小的时候一定用新华字典查过字。如果要查的字的解释,也有不认识的字。那就要接着查第二个字,不幸第二个字的解释,也有不认识的字,就要接着查第三个字。...我们再从一段代码,体会一下递归。...回到递归,在学习递归的过程,最大的陷阱就是人肉递归。人脑是很难把整个“”“归”过程毫无差错的想清楚的。

    59020

    业界代码安全分析软件介绍

    Mobile AST对字节或二进制代码执行SAST,DAST,IAST和/或行为分析,以识别移动应用程序的漏洞。...对于OWASP Top 10的漏洞,通过预先梳理能造成危害的函数,并定位代码中所有出现该危害函数的地方,继而基于Lex(Lexical Analyzer Generator, 词法分析生成器)和Yacc...Synopsys在IoT AST领域处于优势地位,它支持各种协议,XMPP,MQTT,CoAP和AMQP(通过Defensics)。...在广泛的AST使用案例的客户名单,特别是在需要多种测试技术的情况下。 它以提供创新产品和服务而闻名。拥有最完整的SDLC集成之一 例如,为流行的IDE和CI / CD工具提供开箱即用的集成。...license法律问题; 如何在自动集成阶段建立安全质量gate?

    2.1K20
    领券