CN113741869B - 一种高性能的可变语法编程语言的构造方法 - Google Patents
一种高性能的可变语法编程语言的构造方法 Download PDFInfo
- Publication number
- CN113741869B CN113741869B CN202110879501.1A CN202110879501A CN113741869B CN 113741869 B CN113741869 B CN 113741869B CN 202110879501 A CN202110879501 A CN 202110879501A CN 113741869 B CN113741869 B CN 113741869B
- Authority
- CN
- China
- Prior art keywords
- grammar
- stack
- generator
- parser
- context
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Active
Links
Images
Classifications
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F8/00—Arrangements for software engineering
- G06F8/30—Creation or generation of source code
- G06F8/37—Compiler construction; Parser generation
-
- Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y02—TECHNOLOGIES OR APPLICATIONS FOR MITIGATION OR ADAPTATION AGAINST CLIMATE CHANGE
- Y02D—CLIMATE CHANGE MITIGATION TECHNOLOGIES IN INFORMATION AND COMMUNICATION TECHNOLOGIES [ICT], I.E. INFORMATION AND COMMUNICATION TECHNOLOGIES AIMING AT THE REDUCTION OF THEIR OWN ENERGY USE
- Y02D10/00—Energy efficient computing, e.g. low power processors, power management or thermal management
Landscapes
- Engineering & Computer Science (AREA)
- Software Systems (AREA)
- General Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Devices For Executing Special Programs (AREA)
Abstract
本发明提出了一种高性能的可变语法编程语言的构造方法，本发明通过设置解析器生成器包括嵌套堆栈自动机生成器以及解析表达式文法生成器，其中嵌套堆栈自动机生成器用于生成嵌套堆栈自动机，能够在上下文切换时，比如入栈和出栈操作时，可插入相应的下一层级的代码，而且能够随时对代码进行更改；通过设置嵌套堆栈自动机能够独立运行，不需要语法分析器的反馈作用，相比传统词法分析‑语法分析器的组合，本发明的词法分析器能够独立对上下文无关文法完成词法分析，提高开发调试效率，具备工程上的优势。
Description
技术领域
本发明涉及计算机领域，特别是涉及一种高性能的可变语法编程语言的构造方法。
背景技术
2003，微软研究院提出了第一种可变语法的语言Nemerle，该种语言中能够嵌入部分其他语言的语法，能够面向对象或者面向函数式进行程序设计，故而又被称作动态语法。可变语法相比一般的语言中的宏功能要更进一步，使编程人员能够选择最合适的语法来实现程序的功能，编译器同时还能够嵌入代码的语法检查以及语义检查，减少程序的编写错误。可变语法经过编译，相比通过字符串调用外部程序的执行效率显著提高，另一方面，通过嵌入语法，也使得代码跨语言移植的操作得到简化(参考文献：Seaton,C.:Aprogramming language where the syntax and semantics are mutable atruntime.Technical Report CSTR-07-005,University of Bristol(June 2007))。
但是现有的可变语法语言，比如Nemerle，Raku和Katadin等，都存在如下几点问题：其一，普遍采用PEG解析，虽然PEG对语法解析的空间复杂度仅为O(n)，但是实际操作时，输入的长度n还需要与一个极大的常数相乘，因此占用的内存较高，导致解析效率低下；其二，在传统的集成开发环境(integrated development environment，IDE)中，难以做到语法高亮显示，提高了语法的检查、校正等方面的难度。因此需要一种解析效率高并且便于校验的语言的构造方法。
发明内容
本发明的目的是解决现有技术的不足，提供一种高性能的可变语法编程语言的构造方法，结构简单，使用方便。
一种高性能的可变语法编程语言的构造方法，包括如下步骤：
步骤1：构建解析器生成器，其中解析器生成器包括嵌套堆栈自动机生成器以及解析表达式文法生成器；
步骤2：解析器生成器接收输入的语法规则，嵌套堆栈自动机生成器生成VPD，VPD表示嵌套堆栈自动机，解析表达式文法生成器生成PEG，PEG表示解析表达式文法解析器；由VPD和PEG构成解析器；
步骤3：步骤2中生成的解析器进入一个指定的上下文环境，创建与上下文相对应的有限状态机；
步骤4：解析器接收字符流并转换当前的有限状态机的状态，直到当前的状态成为有限状态机的终结状态之一；其中若当前栈空，则进入步骤6；若终结状态进入新的上下文，新建一个有限状态机放入有限状态机栈中，重复执行步骤4；若终结状态返回上一级上下文，进入步骤5；
步骤5：新建一个解析表达式文法解析器实例，将当前上下文中的所有符号交给此实例，并生成抽象语法树；返回上下文，返回步骤4；
步骤6:返回默认上下文的抽象语法树，进入步骤7；
步骤7：将运行状态返回到上一级栈的有限状态机中；
步骤8：解析器生成可执行文件，结束步骤。
进一步的，所述步骤1中的解析器生成器支持动态修改语法，动态修改语法的实现方法包括如下步骤：
步骤11：解析器生成器构建运行的过程中，生成并维护一张词法规则表和一张语法规则表；
步骤12：通过应用程序编程接口完成两表的增删改查操作；
步骤13：通过调用应用程序编程接口或者使用特定的语法构造，修改语法规则表；
步骤14：解析器生成器重新分析修改后的语法规则表中的语法规则的引用关系，通过嵌套堆栈自动机生成器以及解析表达式文法生成器生成新的词法规则、语法规则以及对应的状态机，结束步骤。
进一步的，所述步骤2中嵌套堆栈自动机生成器生成嵌套堆栈自动机的过程包括如下步骤：
步骤211：根据粗粒度划分语法环境，语法环境包括普通代码上下文环境以及字符串内上下文环境；
步骤212：嵌套堆栈自动机生成器接收并分析不同粗粒度的上下文对应的语法规则正则表达式；
步骤213：嵌套堆栈自动机生成器将每种上下文对应的正则表达式，生成相应的有限状态机定义；并通过union操作符，生成并联的有限状态机定义；并联的有限状态机定义表示将有限状态机进行并联操作；
步骤214：对特定的内容进行匹配，特定的内容包括字符串字面量边界、括号边界、模块定义边界，并生成状态栈压栈代码以及状态栈出栈代码；
步骤215：将步骤214中获得的符号生成代码、压栈代码和出栈代码放入有限状态机中，合并为VPD，结束步骤；符号生成代码、压栈代码和出栈代码分别对应有限状态机的符号生成、压栈和出栈的终结状态。
进一步的，所述步骤2中解析表达式文法生成器生成解析表达式文法解析器的步骤包括：
步骤221：解析表达式文法生成器接收操作人员输入的PEG语法规则或者直接传递的词法VPD的解析结果；
步骤222：解析表达式文法生成器对上下文中的每个PEG规则生成一段匹配子程序；
步骤223：解析表达式文法生成器根据PEG规则中的终结规则生成与符号流相匹配的代码，根据PEG规则中的非终结规则生成匹配子程序的调用；生成解析表达式文法解析器，结束步骤；
所述步骤223中的符号流表示通过符号生成代码获得的符号集。
进一步的，所述步骤2中生成的解析表达式文法解析器输出为解析树的构建指令流，在构建指令流完成后，按照编写顺序依次执行，并调用PEG规则中的回调函数产生解析结果；该解析结果可以为抽象语法树输出，或者直接的解释求值，或者其他程序的分析结果。
进一步的，所述步骤4中若解析器解析字符流的终结符得到的动作为生成符号，则重置当前有限状态机的状态，并继续解析字符流；若解析得到的动作为压栈，则创建一个新的有限状态机实例，并将运行状态转至新的有限状态机中；若解析得到的动作为出栈，则销毁当前的有限状态机实例，并将运行状态转至上一级栈的有限状态机中。
进一步的，所述步骤1构成的解析器生成器还能够运用于生成IDE，IDE表示集成开发环境，其中解析器生成器生成二阶段解析器IDE工具的方法包括如下步骤：
步骤S1：解析器生成器接收设置的文本源代码，并且每一段设定长度的文本就缓存一个解析状态，解析状态包括VPD的执行栈的信息；
步骤S2：解析器生成器对上下文中距离编辑点最近的解析状态开始执行VPD，并且同步更新从缓存点到编辑点的符号流状态，但所属上下文的状态不即时更新；
步骤S3：符号流更新后，异步触发重新处理当前栈帧中的上下文的PEG解析；若解析后的状态和编辑前的存在区别，则返回上一级栈帧，并且更新上一级栈帧的PEG解析；否则保持本栈帧，结束步骤；
步骤S4：在步骤S3返回上一级栈帧后，判断返回的栈帧解析后的状态是否发生变化，若发生变化则继续向上一级栈帧更新，直至与缓存状态相匹配，或者达到最外层的栈帧；否则保持返回的栈帧，结束步骤。
进一步的，所述步骤S1中一个VPD的执行栈为一个或多个栈帧，每个栈帧包含有限状态机的状态以及PEG的解析状态。
进一步的，所述步骤S3和S4运行时，仅刷新部分PEG的解析状态。
本发明的有益效果为：
通过设置解析器生成器包括嵌套堆栈自动机生成器以及解析表达式文法生成器，其中嵌套堆栈自动机生成器用于生成嵌套堆栈自动机，能够在上下文切换时，比如入栈和出栈操作时，可插入相应的下一层级的代码，而且能够随时对代码进行更改；
通过设置嵌套堆栈自动机能够独立运行，不需要语法分析器的反馈作用，相比传统词法分析和语法分析器的组合，本发明的词法分析器能够独立对上下文无关文法完成词法分析，提高开发调试效率，具备工程上的优势，包括方便团队任务分拆，简化开发调试，使代码更容易理解等；
通过对每个上下文分别编写语法，减少记忆表的占用空间，进一步提高了表达式的解析效率；
通过设置目标语言和IDE能够通过同一套定义生成，提高了操作人员的开发效率。
附图说明
图1为本发明实施例一的操作人员修改语法的示意框图；
图2为本发明实施例一的动态修改语法的实现方法；
图3为本发明实施例一的嵌套堆栈自动机生成器的工作流程示意图；
图4为本发明实施例一的解析表达式文法生成器的工作流程示意图；
图5为本发明实施例一的解析器生成器生成集成开发环境示意图。
具体实施方式
以下通过特定的具体实例说明本发明的实施方式，本领域技术人员可由本说明书所揭露的内容轻易地了解本发明的其他优点与功效。本发明还可以通过另外不同的具体实施方式加以实施或应用，本说明书中的各项细节也可以基于不同观点与应用，在没有背离本发明的精神下进行各种修饰或改变。需说明的是，在不冲突的情况下，以下实施例及实施例中的特征可以相互组合。
需要说明的是，以下实施例中所提供的图示仅以示意方式说明本发明的基本构想，遂图式中仅显示与本发明中有关的组件而非按照实际实施时的组件数目、形状及尺寸绘制，其实际实施时各组件的型态、数量及比例可为一种随意的改变，且其组件布局型态也可能更为复杂。
名词解释：
嵌套堆栈自动机：嵌套堆栈自动机(Visibly pushdown，简称为VPD)是由Alur和Madhusudan提出的一种状态机(Alur,R.；Madhusudan,P.(2004)."Visibly pushdownlanguages".Proceedings of the thirty-sixth annual ACM symposium on Theory ofcomputing-STOC'04.)，相当于在有限的自动机上增加一个栈结构。基于VPD的分析器，其能力相比基于有限自动机的分析器的能力更强，包括如下特性：
1、任何上下文无关的文法可以通过合并规则转换称为一个VPD文法；
2、VPD文法组合后依旧是VPD文法；
3、其状态变化具备确定性，不会产生语法二义性的问题。
解析表达式文法：解析表达式文法(Parsing Expression Grammar，简称为PEG)，是一种不同于上下文无关文法的解析式文法。PEG的最常用解析方法是Pakrat解析器，Pakrat解析器把语法定义编译成递归下降的函数调用，通过记忆表(memoize table)来消除回溯。记忆表一般通过二维数组来实现，其中二维数组的行对应输入字符的索引，列对应规则的编号，数组元素为解析的结果(AST或求值)。当一个语法的规则匹配时，Pakrat解析器在记忆表的对应位置写下缓存结果。如果解析出现了回溯，解析器会先查询记忆表的对应位置，若缓存命中，则可避免对同一段文本反复应用相同的解析规则。
实施例一：
一种高性能的可变语法编程语言的构造方法，包括如下步骤：
步骤1：构建解析器生成器，其中解析器生成器包括嵌套堆栈自动机生成器(VPDG)以及解析表达式文法生成器(PEGG)；
步骤2：解析器生成器接收输入的语法规则，嵌套堆栈自动机生成器生成嵌套堆栈自动机(VPD)，解析表达式文法生成器生成解析表达式文法解析器(PEG)，由VPD和PEG构成解析器；
步骤3：步骤2中生成的解析器进入一个指定的上下文环境，创建与上下文相对应的有限状态机；
步骤4：解析器接收字符流并转换当前的有限状态机的状态，直到当前的状态成为有限状态机的终结状态之一；其中若当前栈空，则进入步骤6；若终结状态进入新的上下文，新建一个有限状态机放入有限状态机栈中，重复执行步骤4；若终结状态返回上一级上下文，进入步骤5；
步骤5：新建一个解析表达式文法解析器实例，将当前上下文中的所有符号交给此实例，并生成抽象语法树；返回上下文，返回步骤4；
步骤6:返回指定上下文的抽象语法树，进入步骤7；
步骤7：将运行状态返回到上一级栈的有限状态机中；
步骤8：解析器生成可执行文件，结束步骤。
如图1、2所示，所述步骤1中的解析器生成器支持动态修改语法以及无歧义的语法重用，其中动态修改语法表示操作人员能够在多种语法中选择一种最合适或者擅长的语法来实现程序的功能。如图1所示，其中操作人员包括语言的设计者和使用者，不论是那种操作人员均可对语法进行修改以满足其使用需求。如图2所示，其中动态修改语法的实现方法包括如下步骤：
步骤11：解析器生成器构建运行的过程中，生成并维护一张词法规则表和一张语法规则表；
步骤12：通过应用程序编程接口(API)完成步骤11生成的两表的增删改查操作；
步骤13：操作人员通过调用API或者使用设定的语法构造，修改语法规则表；
步骤14：解析器生成器重新分析经过步骤13修改后的语法规则表中的语法规则的引用关系，通过VPDG以及PEGG生成新的词法规则、语法规则以及对应的状态机，结束步骤。
所述步骤14中解析器生成器生成新的词法规则、语法规则以及对应的状态机，即修改了语法，并运用修改后的状态机对操作人员后续输入的代码进行解析和编译。需要说明的是在一些其他实施方式中，还能够通过实时编译技术完成动态修改语法的操作。
如图3所示，所述步骤2中嵌套堆栈自动机生成器生成嵌套堆栈自动机的过程包括如下步骤：
步骤211：根据粗粒度划分语法环境，语法环境包括普通代码上下文环境以及字符串内上下文环境等；
步骤212：嵌套堆栈自动机生成器接收并分析不同粗粒度的上下文对应的语法规则正则表达式；
步骤213：嵌套堆栈自动机生成器将每种上下文对应的正则表达式，生成相应的有限状态机定义；并通过union操作符，生成并联的有限状态机定义；其中并联的有限状态机定义表示将由正则表达式生成的有限状态机定义通过union操作符并联获得；
步骤214：对特定的内容进行匹配，特定的内容包括字符串字面量边界、括号边界、模块定义边界等，并生成状态栈压栈代码以及状态栈出栈代码；
步骤215：将步骤214中获得的符号生成代码、压栈代码和出栈代码放入有限状态机中，合并为VPD，结束步骤；符号生成代码、压栈代码和出栈代码分别对应有限状态机的符号生成、压栈和出栈的终结状态。
所述步骤211中普通代码上下文环境中不需要考虑转义字符等问题，而在字符串内上下文环境中则不需要考虑关键字等语法元素。其中通过粗粒度划分语法环境能够实现模块化分解工作。
所述步骤212中的语法规则的正则表达式表示对语法中字符串操作的一种逻辑公式，用事先定义好的一些特定字符、及这些特定字符的组合，组成一个“规则字符串”，这个“规则字符串”用来表达对字符串的一种过滤逻辑。
如图4所示，步骤2中解析表达式文法生成器生成解析表达式文法解析器的步骤包括：
步骤221：解析表达式文法生成器接收操作人员输入的PEG语法规则或者直接传递的词法VPD的解析结果；
步骤222：解析表达式文法生成器对上下文中的每个PEG规则生成一段匹配子程序；
步骤223：解析表达式文法生成器根据PEG规则中的终结规则生成与符号流相匹配的代码，根据PEG规则中的非终结规则生成匹配子程序的调用；生成解析表达式文法解析器，结束步骤。
所述步骤223中的符号流表示通过步骤215中的符号生成代码获得的符号集
其中步骤2中生成的解析表达式文法解析器用于解析符号流，输出为解析树的构建指令流，在构建指令流完成后，按照编写顺序依次执行，并调用PEG规则中的回调函数产生解析结果，需要说明的是该解析结果可以为抽象语法树输出，或者直接的解释求值，或者其他程序的分析结果，具体的解析结果形式由操作人员输入的回调函数决定。在本实施例中解析表达式文法解析器先构建指令流，再执行指令流，因为在解析表达式文法解析器解析结束之前，构建指令流时能够进行回溯重写的，因此上述的构建和执行顺序能够保证回调函数对于最终产生的语法的每个节点都执行且仅执行一遍。在一些其他实施方式中解析表达式文法解析器也可以同时构建指令流和执行指令流，并且直接调用回调函数，能够加快执行效率。
所述步骤3中的上下文表示操作人员输入的源代码环境，上下文环境包括字符串环境。
所述步骤4中若解析器解析字符流的终结符得到的动作为生成符号(token)，则重置当前有限状态机的状态，并继续解析字符流；若解析得到的动作为压栈，则创建一个新的有限状态机实例，并将运行状态转至新的有限状态机中；若解析得到的动作为出栈，则销毁当前的有限状态机实例，并将运行状态转至上一级栈的有限状态机中。
如图5所示，需要说明的是在一些其他实施方式中步骤1构成的解析器生成器还能够运用于生成集成开发环境(IDE)，其中编程语言的IDE的最核心的功能，就是在操作人员编辑文本时，能够即时更新已经输入的文本的符号分类和所属上下文，有了符号分类和上下文分析，就能够实现IDE的语法高亮、错误检查、文档提示、参考信息、快速重构等功能。其中解析器生成器生成二阶段解析器IDE工具的方法包括如下步骤：
步骤S1：解析器生成器接收用户编辑的文本源代码，并且每一段设定长度的文本就缓存一个解析状态，解析状态包括VPD的执行栈等信息；
步骤S2：解析器生成器对上下文中距离编辑点最近的解析状态开始执行VPD，并且同步更新从缓存点到编辑点的符号流状态，但所属上下文的状态不即时更新；
步骤S3：符号流更新后，异步触发重新处理当前栈帧中的上下文的PEG解析；若解析后的状态和编辑前的存在区别，则返回上一级栈帧，并且更新上一级栈帧的PEG解析；否则保持本栈帧，结束步骤；
步骤S4：在步骤S3返回上一级栈帧后，判断返回的栈帧解析后的状态是否发生变化，若发生变化则继续向上一级栈帧更新，直至与缓存状态相匹配，或者达到最外层的栈帧；否则保持返回的栈帧，结束步骤。
所述步骤S1中一个VPD的执行栈可以为一个或多个栈帧，每个栈帧包含有限状态机的状态以及PEG的解析状态。执行栈的构造与解析器的构造相同，执行栈只针对IDE进行缓存。
所述步骤S3和S4中，在实际运行时，可以通过仅刷新部分PEG的解析状态，而非重新解析整个代码文件，相比传统的基于PEG的解析器，能够提高IDE的响应速度。
在实施的过程中，通过设置解析器生成器包括嵌套堆栈自动机生成器以及解析表达式文法生成器，其中嵌套堆栈自动机生成器用于生成嵌套堆栈自动机，能够在上下文切换时，比如入栈和出栈操作时，可插入相应的下一层级的代码，而且能够随时对代码进行更改；通过设置嵌套堆栈自动机能够独立运行，不需要语法分析器的反馈作用，相比传统词法分析-语法分析器的组合，本发明能够在词法分析阶段就能够完成分析工作，无需语法分析器的反馈作用，提高效率，具备工程运行上的优势；通过对每个上下文分别编写语法，减少记忆表的占用空间，进一步提高了表达式的解析效率；通过设置目标语言和IDE能够通过同一套定义生成，提高了操作人员的开发效率。
以上描述仅是本发明的一个具体实例，不构成对本发明的任何限制。显然对于本领域的专业人员来说，在了解了本发明内容和原理后，都可能在不背离本发明原理、结构的情况下，进行形式和细节上的各种修改和改变，但是这些基于本发明思想的修正和改变仍在本发明的权利要求保护范围之内。
Claims (8)
1.一种高性能的可变语法编程语言的构造方法，其特征在于，包括如下步骤：
步骤1：构建解析器生成器，其中解析器生成器包括嵌套堆栈自动机生成器以及解析表达式文法生成器；
步骤2：解析器生成器接收输入的语法规则，嵌套堆栈自动机生成器生成VPD，VPD表示嵌套堆栈自动机，解析表达式文法生成器生成PEG，PEG表示解析表达式文法解析器；由VPD和PEG构成解析器；
所述步骤2中嵌套堆栈自动机生成器生成嵌套堆栈自动机的过程包括如下步骤：
步骤211：根据粗粒度划分语法环境，语法环境包括普通代码上下文环境以及字符串内上下文环境；
步骤212：嵌套堆栈自动机生成器接收并分析不同粗粒度的上下文对应的语法规则正则表达式；
步骤213：嵌套堆栈自动机生成器将每种上下文对应的正则表达式，生成相应的有限状态机定义；并通过union操作符，生成并联的有限状态机定义；并联的有限状态机定义表示将有限状态机进行并联操作；
步骤214：对特定的内容进行匹配，特定的内容包括字符串字面量边界、括号边界、模块定义边界，并生成状态栈压栈代码以及状态栈出栈代码；
步骤215：将步骤214中获得的符号生成代码、压栈代码和出栈代码放入有限状态机中，合并为VPD，结束步骤；符号生成代码、压栈代码和出栈代码分别对应有限状态机的符号生成、压栈和出栈的终结状态；
步骤3：步骤2中由VPD和PEG构成的解析器进入一个指定的上下文环境，创建与上下文相对应的有限状态机；
步骤4：解析器接收字符流并转换当前的有限状态机的状态，直到当前的状态成为有限状态机的终结状态之一；其中若当前栈空，则进入步骤6；若终结状态进入新的上下文，新建一个有限状态机放入有限状态机栈中，重复执行步骤4；若终结状态返回上一级上下文，进入步骤5；
步骤5：新建一个解析表达式文法解析器实例，将当前上下文中的所有符号交给此实例，并生成抽象语法树；返回上下文，返回步骤4；
步骤6: 返回指定上下文的抽象语法树，进入步骤7；
步骤7：将运行状态返回到上一级栈的有限状态机中；
步骤8：解析器生成可执行文件，结束步骤。
2.根据权利要求1所述的一种高性能的可变语法编程语言的构造方法，其特征在于，所述步骤1中的解析器生成器支持动态修改语法，动态修改语法的实现方法包括如下步骤：
步骤11：解析器生成器构建运行的过程中，生成并维护一张词法规则表和一张语法规则表；
步骤12：通过应用程序编程接口完成两表的增删改查操作；
步骤13：通过调用应用程序编程接口或者使用设定的语法构造，修改语法规则表；
步骤14：解析器生成器重新分析修改后的语法规则表中的语法规则的引用关系，通过嵌套堆栈自动机生成器以及解析表达式文法生成器生成新的词法规则、语法规则以及对应的状态机，结束步骤。
3.根据权利要求1所述的一种高性能的可变语法编程语言的构造方法，其特征在于，所述步骤2中解析表达式文法生成器生成解析表达式文法解析器的步骤包括：
步骤221：解析表达式文法生成器接收操作人员输入的PEG语法规则或者直接传递的词法VPD的解析结果；
步骤222：解析表达式文法生成器对上下文中的每个PEG规则生成一段匹配子程序；
步骤223：解析表达式文法生成器根据PEG规则中的终结规则生成与符号流相匹配的代码，根据PEG规则中的非终结规则生成匹配子程序的调用；生成解析表达式文法解析器，结束步骤；
所述步骤223中的符号流表示通过符号生成代码获得的符号集。
4.根据权利要求3所述的一种高性能的可变语法编程语言的构造方法，其特征在于，所述步骤2中生成的解析表达式文法解析器输出为解析树的构建指令流，在构建指令流完成后，按照编写顺序依次执行，并调用PEG规则中的回调函数产生解析结果；该解析结果可以为抽象语法树输出，或者直接的解释求值，或者其他程序的分析结果。
5.根据权利要求1所述的一种高性能的可变语法编程语言的构造方法，其特征在于，所述步骤4中若解析器解析字符流的终结符得到的动作为生成符号，则重置当前有限状态机的状态，并继续解析字符流；若解析得到的动作为压栈，则创建一个新的有限状态机实例，并将运行状态转至新的有限状态机中；若解析得到的动作为出栈，则销毁当前的有限状态机实例，并将运行状态转至上一级栈的有限状态机中。
6.根据权利要求1所述的一种高性能的可变语法编程语言的构造方法，其特征在于，所述步骤1构成的解析器生成器还能够运用于生成IDE， IDE表示集成开发环境，其中解析器生成器生成二阶段解析器IDE工具的方法包括如下步骤：
步骤S1：解析器生成器接收设置的文本源代码，并且每一段设定长度的文本就缓存一个解析状态，解析状态包括VPD的执行栈的信息；
步骤S2：解析器生成器对上下文中距离编辑点最近的解析状态开始执行VPD，并且同步更新从缓存点到编辑点的符号流状态，但所属上下文的状态不即时更新；
步骤S3：符号流更新后，异步触发重新处理当前栈帧中的上下文的PEG解析；若解析后的状态和编辑前的存在区别，则返回上一级栈帧，并且更新上一级栈帧的PEG解析；否则保持本栈帧，结束步骤；
步骤S4：在步骤S3返回上一级栈帧后，判断返回的栈帧解析后的状态是否发生变化，若发生变化则继续向上一级栈帧更新，直至与缓存状态相匹配，或者达到最外层的栈帧；否则保持返回的栈帧，结束步骤。
7.根据权利要求6所述的一种高性能的可变语法编程语言的构造方法，其特征在于，所述步骤S1中一个VPD的执行栈为一个或多个栈帧，每个栈帧包含有限状态机的状态以及PEG的解析状态。
8.根据权利要求6所述的一种高性能的可变语法编程语言的构造方法，其特征在于，所述步骤S3和S4运行时，仅刷新部分PEG的解析状态。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN2020109479892 | 2020-09-10 | ||
| CN202010947989 | 2020-09-10 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN113741869A CN113741869A (zh) | 2021-12-03 |
| CN113741869B true CN113741869B (zh) | 2023-05-26 |
Family
ID=78729887
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN202110879501.1A Active CN113741869B (zh) | 2020-09-10 | 2021-07-30 | 一种高性能的可变语法编程语言的构造方法 |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN113741869B (zh) |
Families Citing this family (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN114090017B (zh) * | 2022-01-20 | 2022-06-24 | 北京大学 | 编程语言的解析方法及装置、非易失性存储介质 |
| CN115982059B (zh) * | 2023-03-21 | 2023-07-04 | 麒麟软件有限公司 | Shell脚本检查工具的实现方法 |
| CN117217214A (zh) * | 2023-09-05 | 2023-12-12 | 广州正是网络科技有限公司 | C#语法树生成方法、应用、系统、存储介质及电子设备 |
Citations (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| WO2001014959A2 (en) * | 1999-08-16 | 2001-03-01 | Z-Force Corporation | System of reusable software parts and methods of use |
| EP1380939A1 (en) * | 2002-07-08 | 2004-01-14 | Abb Research Ltd. | Version management for software object associations |
| CN105830025A (zh) * | 2013-12-20 | 2016-08-03 | 微软技术许可有限责任公司 | 动态类型化的编程语言中的属性访问 |
| CN107766045A (zh) * | 2016-08-19 | 2018-03-06 | 康耐视公司 | 为机器视觉系统提供可视化程序的装置、系统和方法 |
Family Cites Families (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US7127704B2 (en) * | 2000-06-02 | 2006-10-24 | Sun Microsystems, Inc. | Interactive software engineering tool with support for embedded lexical contexts |
| WO2003010766A1 (en) * | 2001-07-23 | 2003-02-06 | Matsushita Electric Industrial Co., Ltd. | Information recording medium, and apparatus and method for recording information on information recording medium |
| US7869074B2 (en) * | 2005-09-20 | 2011-01-11 | Brother Kogyo Kabushiki Kaisha | Communication system, information processing device, peripheral device and communication method |
| US8863101B2 (en) * | 2008-12-10 | 2014-10-14 | International Business Machines Corporation | Compiler generator |
| US8881141B2 (en) * | 2010-12-08 | 2014-11-04 | Intenational Business Machines Corporation | Virtualization of hardware queues in self-virtualizing input/output devices |
-
2021
- 2021-07-30 CN CN202110879501.1A patent/CN113741869B/zh active Active
Patent Citations (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| WO2001014959A2 (en) * | 1999-08-16 | 2001-03-01 | Z-Force Corporation | System of reusable software parts and methods of use |
| EP1380939A1 (en) * | 2002-07-08 | 2004-01-14 | Abb Research Ltd. | Version management for software object associations |
| CN105830025A (zh) * | 2013-12-20 | 2016-08-03 | 微软技术许可有限责任公司 | 动态类型化的编程语言中的属性访问 |
| CN107766045A (zh) * | 2016-08-19 | 2018-03-06 | 康耐视公司 | 为机器视觉系统提供可视化程序的装置、系统和方法 |
Also Published As
| Publication number | Publication date |
|---|---|
| CN113741869A (zh) | 2021-12-03 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN113741869B (zh) | 一种高性能的可变语法编程语言的构造方法 | |
| US10664655B2 (en) | Method and system for linear generalized LL recognition and context-aware parsing | |
| EP0204942A2 (en) | Compiler for a source program, a method of making the same and its use | |
| KR20060069364A (ko) | 다중 예외 처리 모델에 대한 중간 표현 | |
| JPS6375835A (ja) | 目的コ−ド、プログラム・リスト及び設計文書を生成する装置 | |
| JP2012063868A (ja) | 言語処理パーサーを組み合わせて、組み合わせパーサーを生成する方法、並びにそのコンピュータ及びコンピュータ・プログラム | |
| JPH06501583A (ja) | 多言語最適化コンパイラ内のフォールディングメカニズムを構成する方法 | |
| Verano Merino et al. | Getting grammars into shape for block-based editors | |
| US20080141230A1 (en) | Scope-Constrained Specification Of Features In A Programming Language | |
| US20030196195A1 (en) | Parsing technique to respect textual language syntax and dialects dynamically | |
| JP7391983B2 (ja) | プログラム論理の表現を生成する方法、逆コンパイル装置、再コンパイルシステムおよびコンピュータプログラム製品 | |
| JP2879099B1 (ja) | 抽象構文木処理方法、抽象構文木処理プログラムを記録したコンピュータ読み取り可能な記録媒体、抽象構文木データを記録したコンピュータ読み取り可能な記録媒体、及び、抽象構文木処理装置 | |
| Matsumura et al. | A declarative extension of parsing expression grammars for recognizing most programming languages | |
| KR102614967B1 (ko) | 자바스크립트의 중간 언어 기반 의미론 추출 자동화 시스템 및 방법 | |
| Dejanović | Parglare: a LR/GLR parser for python | |
| Grigorev et al. | String-embedded language support in integrated development environment | |
| Griswold et al. | Variant Translators for Version 8 of Icon | |
| Wu et al. | Component-based LR parsing | |
| Pahade et al. | Introduction to Compiler and its Phases | |
| Jeffery | Build Your Own Programming Language: A programmer's guide to designing compilers, interpreters, and DSLs for solving modern computing problems | |
| Handzhiyski et al. | Tunnel Parsing with Ambiguous Grammars | |
| Pappalardo | μComp language implementation | |
| Pierce et al. | A transformation-directed compiling system | |
| KR0168929B1 (ko) | 칠 전위처리기의 전위처리 방법 | |
| Drumm | Readtable-Macro Transducer-Chain Parsing |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant |