实现一个中文编程语言EBNF介绍

举报
码乐 发表于 2024/02/26 10:53:26 2024/02/26
【摘要】 每一种动物和鸟类都有自己的声音和特征,有时选择使用某些奇特的乐器,可以让声音听起来更接近他们。 __hans zimmer 著名当代音乐艺术家 接上: 写在前面的简介语法, 人们知道如何控制.前面我们已经将原始源代码作为一个字符串,并将其转换为稍微更高级别的表示:一系列Tokens。在这一章编写的解析器获取这些词令,并再次将它们转换为更丰富、更复杂的表示。每一个成功...
 每一种动物和鸟类都有自己的声音和特征,有时选择使用某些奇特的乐器,可以让声音听起来更接近他们。
	
            __hans zimmer 著名当代音乐艺术家

接上: 写在前面的简介

语法, 人们知道如何控制.

前面我们已经将原始源代码作为一个字符串,并将其转换为稍微更高级别的表示:一系列Tokens。在这一章编写的解析器获取这些词令,并再次将它们转换为更丰富、更复杂的表示。

每一个成功的通用语言,都由众多内置成功的“小语言”构成,它们无处不在,或许有一千个。但行话为了区别和不那么烂大街。有了“特定领域语言”的名称。这些是为特定任务量身定制的。 比如 应用程序脚本语言、模板引擎、标记格式和甚至是配置文件语言。

在这一章,我们进入第一个重要里程碑,我们将实现获取文本并将每个单词映射到语言的语法。我们在这里以同样的方式使用解析器,只是我们的语言比古法自然语言更现代一些。

3.1 面对问题 表示代码: 语句 从词令到代码语句

这里我们将要解决的问题是如何把 token 链转换为数据模型。

	Tokens -> Data model (AST)

让我们专注于主要目标——代码语句的表示。我们已经写过分词器,应该很简单。如果没有用过解释器,也没有关系。也许你的直觉会有所帮助。
我们在中学就已经知道旧的人类内容 关于运算顺序:

	+ - x ÷  
            当他们同时存在一个计算式中的时候,
            我们总是需要先计算 乘法和除法,如果有更高优先级的如 位和 () 则更优先他它们,
            这里我们先讨论基本的 逻辑运算和算术运算。

我们知道乘法在加法或减法前计算。当我们使用树时。叶节点是数字,内部节点是操作符,每个操作数都有分支,比如从叶子到根的一个后序遍历。

    A. 从完整的树开始,评估最底部的操作,2 * 3
    B. 现在我们可以执行+.
    C. 接下来,-.
    D. 最终答案。
    # 注释: 乔姆斯基层次结构

我们打算使用模型的方式来确定它们到底如何计算。就像前面的分词器的词法文法一样,围绕代码语句文法有大量的理论。我们将比在分词器的扫描时稍微更多了解它们,因为它是贯穿大部分解释器和语言的有用逻辑。

并且我们将讨论一种称为 Parsing Expression Grammar PEGs, 也就是解析表达式语法的方式,

	(PEG) 
	assignment <- NAME '=' expr ';'
	expr <- term { '+'/'-' term }
	term <- factor { '*'/'/' factor }
	factor <- NUMBER / NAME / '(' expr ')'	

因此,我们需要执行以下几步

	1 理解如何指定语法
	2 提炼一种如何解析计算任务的直觉
	3 写一个自己的解析器

3.2 解析器 语句 Representing_Code: 让它把摄入的词令转换为语句的一部分

我们需要支持 逻辑 与或 和 计算器 加减乘除,我们约定以下运算符

	Tokens -> Data model (AST)

首先规定语法规范

	start -> location -> = -> expression  -> end 

其表达式解析顺序 如: term + term * term

	expression:
		start ->  term -> -end->
                        |		 |
                        <-	   +   <-
                        |		 |
                        <-	   -   <-
                        |		 |
                        <-	  *    <-
                        |		 |
                        <-	  /    <-
词解析 如: 12
    term:
    	   start -> INTEGER -> -end->
                 |			|
                   <-   FLOAT     <-	
                  |			|
                   <-   NAME      <-	

代码如下:

	//表达式
	func ParseExpression(tokens *Tokens) *Node {
		return ParseAddTerm(tokens)
	}

至此,我们可以将Tokens处理为一个个符合人类计算顺序习惯的语句,并最终在计算机硬件中执行。
比如VM,LLVM等。

4 解析的控制 EBNF: 工具 把材料消费为token, 转换为一个一个的指令 token

现在我们需要实现对tokens链的消费,比如我们需要把如下表达式实现

	2 + 3 * 4 * 5 - 6 * 7 - 8; 

其计算顺序应该是

	(2) + (3 * 4 * 5) - (6 * 7) - (8)

其计算顺序为表达式 :

		start ->  term -> -end->
			|		 |
			    <-	+   <-
			|		 |
			    <-	-   <-

解析因子 :

    	start -> INTEGER -> -end->
    	  |			|
    	   <-    FLOAT      <-	
          |			|
    	    <-    NAME       <-	

解析词:

	term:
    	     start -> factor -> -end->
    		 |	       |
    		  <-    *      <-	
    		 |	 	|
    		  <-    /      <-	

如此每个层次的词令描述,低优先的运算以更高优先级链接。
符号扫描被称为一种 BNF(Backus Naur Form) 表单方式进行。
左部的任何符号都可以被右部的符号替换,等效的,

	x = y + 22
	z = x - 11

	替换 x 
	z = (y + 22) - 11

另有一种EBNF的类似方式,比BNF更复杂的计算表达式解析方式,更接近数学的计算解析,这里不再深入。

	expr = term { '+'|'-' term }
	term = factor { '*'|'/' factor }
	factor = INTEGER | FLOAT | NAME | '(' expr ')'

EBNF 是一种非常普遍的语法规范,有大量文档可查看,在通用语言中也有应用。

4 小结

快要进入现代了,下一节我们继续探讨,特别是ENBF与PEGs的区别和应用。

【版权声明】本文为华为云社区用户原创内容,未经允许不得转载,如需转载请自行联系原作者进行授权。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。