用c语言手搓一个600行的类c语言解释器: 给编程初学者的解释器教程(4)- 语法分析1:EBNF和递归下降文法 用c语言手搓一个600行的类c语言解释器: 给编程初学者的解释器教程(1)- 目标和前言...这一章开始进入解释器的核心部分: 语法分析器; 我们来看看两个概念,EBNF和递归下降文法,以及如何用这两个方法来计算tryC中的表达式。...BNF与上下文无关文法 Backus-Naur符号(就是众所周知的BNF或Backus-Naur Form)是描述语言的形式化的数学方法,由John Backus (也许是Peter Naur)开发,最早用于描述...EBNF EBNF是基本巴科斯范式(BNF)元语法符号表示法的一种扩展,主要对BNF中常见的两种情况,即重复项和可选项添加了相应的语法规则,如用方括号"[ … ]" 表示可选部分,用花括号"{ … }...tryC中算术表达式具体的代码实现(就是上述文法直接转换过来的啦): (在下一篇文章中还会提及表达式中对变量的处理过程) double term() { double temp = factor
项目github地址及源码: https://github.com/yunwei37/tryC 这一章开始进入解释器的核心部分: 语法分析器; 我们来看看两个概念,EBNF和递归下降文法,以及如何用这两个方法来计算...BNF与上下文无关文法 Backus-Naur符号(就是众所周知的BNF或Backus-Naur Form)是描述语言的形式化的数学方法,由John Backus (也许是Peter Naur)开发,最早用于描述...EBNF EBNF是基本巴科斯范式(BNF)元语法符号表示法的一种扩展,主要对BNF中常见的两种情况,即重复项和可选项添加了相应的语法规则,如用方括号" .... " 表示可选部分,用花括号"{ ......,它就能从起始非终结符开始,不断地调用非终结符的分解函数,不断地对非终结符进行分解,直到匹配输入的终结符。...tryC中算术表达式具体的代码实现(就是上述文法直接转换过来的啦): (在下一篇文章中还会提及表达式中对变量的处理过程) double term() { double temp = factor
像正则表达式的表达能力等价于正则文法一样,BNF范式的表达能力等价于上下文无关文法。BNF是“Backus Naur Form”的缩写。...John Backus和Peter Naur首次引入一种形式化符号来描述给定语言的语法。 BNF的元符号: ::=表示“定义为”,有的书上用–>|表示“或者”尖括号用于括起非终结符。...BNF的扩展EBNF: 可选项被括在元符号“[”和“]”中 重复项(零个或者多个)被括在元符号“{”和“}”中 仅一个字符的终结符用引号(“)引起来,以和元符号区别开来 上述操作符不是严格限定的,有的人喜欢直接使用扩展正则表达式的操作符描述...BNF的扩展EBNF: 可选项被括在元符号“[”和“]”中 重复项(零个或者多个)被括在元符号“{”和“}”中 仅一个字符的终结符用引号(“)引起来,以和元符号区别开来 上述操作符不是严格限定的,有的人喜欢直接使用扩展正则表达式的操作符描述...事实上,一个上下文无关文法是严格的,既不可能由正则文法产生,当且仅当该语言的一切文法都是自嵌套的。 如上所述,上下文无关文法的递归性,对其分析方法也有很大影响。
(BNF) 产生式:在计算机中指 Tiger 编译器将源程序经过词法分析(Lexical Analysis)和语法分析(Syntax Analysis)后得到的一系列符合文法规则(Backus-Naur...Form,BNF)的语句 巴科斯诺尔范式:即巴科斯范式(英语:Backus Normal Form,缩写为 BNF)是一种用于表示上下文无关文法的语言,上下文无关文法描述了一类形式语言。...基础结构称终结符 复合结构称非终结符 引号和中间的字符表示终结符 可以有括号 * 表示重复多次 | 表示 “或” + 表示至少一次 案例: 我们来用 BNF 来表述一下大家比较熟悉的四则运算。...在无限制文法当中是可以产生多个非终结符 所以在无限制文法里面是可以随便写 1-型:上下文相关文法 产生式:??::=?? 对产生的书写做出了一定的限制 可以在左边右边的?...对每一个层级来说我们是以语法作为线索,但是实际上除了语法,重点讲的是语义和进行时。 所谓 “语义” 就是在实行上在用户使用的时候是什么样子的。
BNF范式与上下文无关文法 巴科斯范式 以美国人巴科斯(Backus)和丹麦人诺尔(Naur)的名字命名的一种形式化的语法表示方法,用来描述语法的一种形式体系,是一种典型的元语言。...BNF表示语法规则的方式为:非终结符用尖括号括起。每条规则的左部是一个非终结符,右部是由非终结符和终结符组成的一个符号串,中间一般以“::=”分开。...相信到这里小伙伴应该明白BNF范式的一些基本概念和使用方式了。 我们再来插入一个题外话,既然这里提到BNF范式是一种上下文无关文法,那什么是上下文、什么是上下文无关。...::=人|狗|猫|天 人::=人(吃|抓) 吃::=吃(饭|肉|鱼) 这样我们对这个产生式进行了一些限定,当主语是人的时候,谓语只能产生吃和抓这样的宾语。...代码编写 上面的定义只是开胃菜,希望通过上面的描述,小伙伴能够理解BNF范式的应用,至于上下文无关和上下文有关。这些暂时不用考虑,毕竟我们目前还是在做上下文无关文法相关的内容。
通过使用 Jison,开发人员可以定义自己的模版语法规则,然后将其转换为解析器,从而实现对自定义模版语法的支持。...通过使用 Jison,开发人员可以定义自己的 DSL 语法规则,然后将其转换为解析器,从而实现对自定义 DSL 的支持。...语法定义通常使用BNF或EBNF表示。2.实现DSL的解析器:DSL解析器是将DSL代码解析为计算机可执行的指令的程序。解析器通常使用词法分析器和语法分析器来实现。...OK,立即这些,就看看其中的一些概念,对于新手可能需要科普一下:BNF或EBNF简单的描述BNF(巴克斯-诺尔范式)和 EBNF(扩展巴克斯-诺尔范式)是一种用于描述编程语言结构的形式语法。...上下文无关文法是自然语言处理、编译原理和计算机语言设计等领域中广泛使用的一种形式化表示方法。要轻松写一个上下文无关文法,可以按照以下步骤进行:1. 确定终结符号集和非终结符号集。
BNF 范式通过 Left ::= Right 表示产生式。...一般用大写的 S 表示文法的开头,称为开始符号。 终结符与非终结符 下面为了方便书写,使用 BNF 范式表示文法。...附上一个 mysql 上下文无关文法集合。 左推导与右推导 上面提到的推导符号 => 在实际运行过程中,显然有两种方向左和右: E + E => ?...从最左边的 E 开始分析,称为左推导,对语法解析来说是自顶向下的方式,常用方法是递归下降。 从最右边的 E 开始分析,称为右推导,对语法解析来说是自底向上的方式,常用方法是移进、规约。...结合优先级 对 SQL 的文法来说不存在优先级的概念,所以从某种程度来说,SQL 的语法复杂度还不如基本的加减乘除。
BNF 是一种 上下文无关文法,举个例子就是,人类的语言就是一种 上下文有关文法,我随时都可以讲一句 “以上说的都是废话”,戏弄一下读者阅读本文所花的时间(每当回忆起来,我都会坐在轮椅上大呼过瘾)。...这些其实都是在 静态层面 上对语言的描述,为了实际执行这些语言,就需要对其进行解析,还原出语言本身所描述的信息结构。...对工程师来说,解决问题的第一步就是先知道你面对的是什么问题:使用编译原理的知识来解析开头的表达式,相当于定义一个简陋的 DSL 语言,并编写词法解析器和语法解析器(lexer & parser)来将其转换成...首先是前面提到的终结符和非终结符,重复一下上面解释 BNF 时举的抽象表达式: ::= 。可以这样来理解: 由词法解析器生成的符号,也叫 token,是终结符。...词法分析器(lexer)生成终结符,而语法分析器(parser)则利用自顶向下或自底向上的方法,利用文法中定义的终结符和非终结符,将输入信息转换为 AST(抽象语法树)。
前言 本文将会从上下文无关文法开始介绍,从使用 BNF 描述语法到理解递归下降分析思想,最后实现一个简单的 html 解析器收尾。...本文的亮点是使用 typescript 编写组合子编译器,对于前端开发某些特定领域会有重要意义和价值。同时本文注重实用价值,配合简短 js 代码示例来帮助理解。 2....巴科斯范式 - 语法描述语言 巴科斯范式 Backus Normal Form,缩写为 BNF, 是一种用于表示上下文无关文法的语言。...在含有递归的语法中,不能出现左递归(包括间接左递归),也不能有二义性,没有左递归且没有二义性的语法符合 LL(1)文法,就可以使用递归下降分析法解析。...左递归无法使用递归下降分析的原因是会让程序死循环,具体可以参考编译原理龙书 2.4.5 Left Recursion 章节。 3. 递归下降分析 符合 LL(1)文法的语法可以使用递归下降分析法解析。
这两天团队要做项目总结,所以个人就浅薄的作了几点总结,当然,是从团队研发人员的角度去出发,因为团队的研发人员是基石,是铸造项目和产品的核心,产品的质量完全由研发人员来决定的,而市场唯一认可的是产品。...规范权限管理 一个权限不规范的团队暴雷是早晚的事,即使不暴雷,那么途中一定会遇到大大小小的问题,权限包括服务器权限,数据库权限,各种文档权限和各种中间件的访问权限等等。...,不仅让代码整理比较健康,另一方面也培养了成员,对后续的开发打下基础,另外,一个团队的技术氛围会在很在程度上决定这个团队的稳定性。...上面就列举了几个部分来说,也是在团队中总结出来的,当然,还有很多影响团队的发展和项目的交付的因素,后续再进行一些总结,当然,因为我的经验不是很足,在团队里面只是一颗螺丝钉,但是我觉得无论是谁,在团队中都是十分重要的...今天的分享就到这里,感谢你的观看,我们下期见,如果你有什么想法和点子,我真切的希望你能和我分享,我们一起学习,一起成长!
HTML和CSS规范中规定了浏览器解释html文档的方式,由W3C组织对这些规范进行维护,W3C是负责制定web标准的组织。 ...HTML文法定义(The HTML grammar definition) W3C组织制定规范定义了HTML的词汇表和语法。...非上下文无关文法(Not a context free grammar) 正如在解析简介中提到的,上下文无关文法的语法可以用类似BNF的格式来定义。...HTML DTD Html适用DTD格式进行定义,这一格式是用于定义SGML家族的语言,包括了对所有允许元素及它们的属性和层次关系的定义。...正如前面提到的,html DTD并没有生成一种上下文无关文法。 DTD有一些变种,标准模式只遵守规范,而其他模式则包含了对浏览器过去所使用标签的支持,这么做是为了兼容以前内容。
(★★) 文法的分类 有限自动机(★) 后缀表达式(★★★) 传值与传址(★★★★) 多种程序语特点(★★★) ---- 编译与解释(★★★) 编译过程 词法错误:非法字符,关键字或标识符拼写错误...语法错误:语法结构出错,if endif不匹配, 缺分号 语义错误:死循环,零除数,其它逻辑错误 文法(★★) 一个形式文法是一个有序四元组G=(V ,T,S, P),其中: 1)V :非终结符...是语言的组成部分,是最终结果。VnT=0 3)S :起始符。是语言的开始符号。 4)P :产生式。用终结符替代非终结符的规则。...例如a*=fa,a,a.a..s},而(ab)*={ab,abab,ababab...c} 文法的分类 有限自动机(★) 注意终态与起始初态,S就是初态,Z是终态。 终态是加强圈。...Prolog语言(逻辑推理,简洁性,表达能力,数据库和专家系统 9. Python语言(解释型,面向对象,胶水语言)
在上一篇我们添加了对乘除法的支持,也介绍了BNF范式,并且针对当前的算术表达式写出了对应的范式,同时根据范式给出相应的代码实现。这篇我们将继续为算数表达式添加对括号的支持。...对应的BNF 范式 在上一篇我们给出了乘除法对应的范式 ::={(PLUS|MINUS)} ::={(DIV|MUL)}...例如下面的算数表达式 ((1+2)*3+4) - (5 - 6 / 3) 这里我们直接给出对应的文法,然后再来分析一下该如何由这个文法得到对应的表达式 ::={(PLUS|MINUS...break; default: return false; } } return true; } 这里我对这个函数进行了一些改写...另外需要特别注意的是,我们将反括号的判断放到了 get_factor 函数中,所以在 get_term 和 expr 中,遇到反括号应该考虑对位置索引进行递减,并且遇到反括号应该认为到达末尾并推出。
https://blog.csdn.net/huyuyang6688/article/details/44752153 编译原理在软考中的考点大体上分为以下几点:文法、语法推倒树和算符优先...文法 基本元素 首先要了解文法中最基本的两个元素:非终结符和终结符。 ...“→”左边的符号必须是非终结符。 3型文法(正规文法),3型文法在2型文法的基础上多加了一个条件,β中如果包含终结符和非终结符时,非终结符要么都在左侧,要么都在右侧。...优先关系 三种优先关系的运算为: ≑关系:直接看产生式的右部,如果有A→…ab…或者A→…aBb… ,则有a≑b; ⋖关系:当A→…aB…时,对每一b∈FIRSTVT...以上仅是对在视频中所学知识的总结,理解还不够具体,希望在后面看书和做题的过程中能够把知识吃透。 软考路上,你最棒!
消除左递归,提取左公因子,First集follow集,构造分析表,对一个句子分析。LL(1)三种基本动作:生成(最左推导),匹配,接受。 自底向上? 语义分析:什么是属性?什么是属性文法?什么是联编?...LL(1)三种基本动作:生成(最左推导),匹配,接受 将BNF写为LL(1)分析算法 消除左递归: 提取左公因子: FIRST集 定义: 令 X 为一个文法符号(一个终结符或非终结符)或 ε ,...LL(1)文法: 一个上下文无关文法是LL(1)文法的充分必要条件是:对每个非终结符A的两个不同产生式,A→α, A→β,满足SELECT(A→α)∩SELECT(A→β)=空集 其中α,β不同时能推导出...构造LL(1)预测分析表 对于文法G的每一个产生式A→α执行第2,3步 对每个终结符a∈FIRST(α),把A→α加到M[A,a]中 若ε∈FIRST(α),则对任何b∈FOLLOW(A)把A→α加入[...•数的有效位数。 什么是属性文法 确定语言实体的属性或特性,它们必须进行计算并写成属性等式或语义规则,并描述这些属性的计算如何与语言的文法规则相关。这样的一组属性和等式称作属性文法。
它能接受一个用BNF(巴科斯范式)描述的LALR(1)文法并构造LALR(1)语法分析器。...Lemon与YACC没有本质上的不同,都是LALR(1)文法编译器。但lemon有一些改进,主要有: (1)语法更易读和理解,变量不易弄错。...Lua1.1版本生成的是y.tab.c。 3.指令和程序 虚拟机中执行的程序体,程序由指令串构成。指令常会变化比较大,以适应各种不同的需求或性能改进等。SQLite和Lua的指令都经历过比较大变化。...这样的指令系统对于效率有很大的帮助。不过,在编译器设计上,就要在代码生成阶段对寄存器进行分配,增加了实现的复杂度。并且每条指令的复杂度增加。...对比Lua早前版本和现在的版本,可以看到Lua在性能优化方面做了很多努力。
引言 前面已经介绍了编译器的预处理,词法分析,词法分析器的实现,也在其中说到了语法分析的任务和过程。...语法分析的输入是词法单元序列,然后根据语言的文法表示(展开式),利用有限状态机理论,生成抽象语法树,然后遍历得到中间代码,即,三地址码。本节就以一个实验的方式,来看一下,语法分析器的内在实现机制。...5.1实验描述 编制一个递归下降分析程序,实现对词法分析程序所提供的单词序列的语法检查和结构分析。 利用C语言编制递归下降分析程序,并对简单语言进行语法分析。...5.1.1 待分析的简单语言的语法 用扩充的BNF表示如下: ⑴::=beginend ⑵::={ ;} ⑶::= ⑷::=...:从开始状态开始,利用有限状态机理论,根据语言的文法展开式,进行状态分析,得到语法树。
函数参数中,一维数组和多维数组的第一维将会被视为指针(即使给定维数),其余将会照常编码。...不过这个仅仅是简单的总结,所以这一小节让我们再进一步深究下去,来从C语言的BNF文法中理解类型声明的语法。 BNF范式 如果你对BNF范式有一定了解,请跳过这一段直接去看“分析”节。...是一种用于表示上下文无关文法的语言,上下文无关文法描述了一类形式语言。...优先级 从BNF范式中,我们可以看出指针声明和其他声明的优先级。其中,括号对优先级最高。其次,数组和函数指针的优先级相同,而指针的优先级最低。...int (*arr)[3]; 由于括号对优先级更高,考虑*,所以arr是个指针,数组声明的优先级较括号对低,所以指针指向的是一个数组。于是,这是一个数组指针。 总结 回到我们总结的规律。
下面这些观点都是程序员在教科书上、在编码规范里、在正统的软件工程流程里流传开来的,帮助了许多人在程序员启蒙期间养成了良好的习惯、原则。对许多人(包括曾经的我)来说,似乎是理所当然的。...如果你恰好对当前需要用到的业务和技术特别熟悉,领先团队里其他人一大截怎么办?...关于第 2 点,要代码“ 看得懂”,是设计出来的,而不是注释加出来的。这和产品质量一样,产品质量是设计出来的,而不是测试测出来的。注释的意义在于对当前代码自解释做不到的地方进行补充。...另外,有许多代码本身就没有多大被 UT 测试的价值,这也是不容忽视的。 优秀的程序员,应该难以容忍自己产出糟糕的代码,也许对代码有一点洁癖,对代码之美有不懈的追求。...对这样的软件的使用动机,也应该来源于程序员,而相关数据的采集,最终一定要为程序员服务。 今天只是把上面这些观点做了个整理,在和别人谈起这些的时候,其实我觉得我只是说了实话而已,我的观点一点都不偏激。
php_execute.png 第1步:词法分析将PHP代码转换为有意义的标识Token。该步骤的词法分析器使用Re2c实现的。 第2步:语法分析将Token和符合文法规则的代码生成抽象语法树。...语法分析使用了巴科斯范式(BNF)来表达文法规则,Bison借助状态机、状态转移表和压栈、出栈等一系列操作,生成抽象语法树。 第3步:上步的抽象语法树生成对应的opcode,被虚拟机执行。...可见,Token就是一个个的“词块”,但是单独存在的词块不能表达完整的语义,还需要借助规则进行组织串联。语法分析器就是这个组织者。它会检查语法、匹配Token,对Token进行关联。...PHP7对抽象语法树的支持,实现了PHP编译器和解释器解耦,有效提升了可维护性。 顾名思义,抽象语法树具有树状结构。AST的节点分为多种类型,对应着不同的PHP语法。...在当前章节,我们可以认为节点类型是对语法规则的抽象,例如赋值语句,生成的抽象语法树节点为ZEND_AST_ASSIGN。而赋值语句的左右操作数,又将作为ZEND_AST_ASSIGN类型节点的孩子。
领取专属 10元无门槛券
手把手带您无忧上云