PParser
3.82/5 (10投票s)
定义超越乔姆斯基限制的创新。
引言
本文介绍了我过去开发的一个程序，今天完成它是因为我能够更新乔姆斯基的理论。我发布这篇文章是为了展示我的解决方案。也许其他地方也有类似的解决方案，但我不知道。我是一名拥有30年经验的开发人员，毕业于高级计算机专业，并在法国的公司工作过。
我发布这篇文章是因为我接触了 Loyc LL(K) 项目，这是一个非常棒的项目，拥有高度发达且可能不为人知的强大功能。在我的文章中，我将提出一个程序，用于定义编程语言的各种语法规则，以及更广泛意义上的文本和数字数据。
为什么这有用？
我一直认为，要指定一种用于分析词汇和语法的编程语言，必须详细说明一切。乔姆斯基迫使我们指定一种编程语言，其中包含数百条或多或少复杂的视角范式规则。
我的解决方案实际上非常实用，因为有更复杂的语法规则需要指定：例如，数学表达式的语法是用 BNF（巴科斯-瑙尔范式）编写的。
E -> E + E
E -> E - E
E -> E / E
E -> E * E
E -> (E)
E -> T
E -> N
T -> [a-zA-Z _] [a-aA-Z_0-9] *
N -> [0-9] +
但是它缺少信息，即运算符 + 和 * 是左结合运算符，而 - 和 / 是右结合运算符。显然，数学表达式的定义会变得非常复杂，尤其是在添加诸如三角函数或带多个参数的函数时。
巴科斯-瑙尔范式不适合表示我制定的规则，因为这些信息直接基于我开发的算法。
问题如下：
- “如果有大量的移入和归约操作，如何提高分析速度？”
- “如何通过关注内容而非形式来快速编写语法规则？”
- “如何解决指令块的层次结构问题，这些指令块遵循一个上下文，而所有这些块构成一个不完整的集合？”
从技术上讲，如果规则很多，那么处理时间就更长；同时，规则的存在是为了使本质上非确定性的东西变得确定。事实上，语法规则定义了目标编程语言如何组织，并增加了为满足特定算法而指定的每个程序组件的不确定性，但又无限地复制单一格式。
背景
我的培训非常全面，我非常擅长创建和开发编程语言，编译器能够最大限度地响应语言提供的所有可能性。这是我最擅长的编程技能之一，即词法和语法分析软件。此外，软件始终需要这类媒介：包含各种形式信息和逻辑答案的文本媒介，沿着软件的目标路径进行，这条路径必须遵循，但不应该用“原始”形式写成高级语言。
这些是小型文件或配置文件，XML、INI 或其他形式，其中包含特定信息以及它们之间的关系。有时，开发一个优秀的程序来查找和创建这些文本文件会更好，因为它们非常复杂，需要密切关注一切都能正常运行（包括处理数据的目标和风险的 bug 或错误）。
在我的培训之后，我想创建一个最符合语法和语法分析的软件。通用是因为该软件旨在进行制图，并且它允许忽略编写语法规则的困难。这种困难非常大，代表形式也难以理解：需要几天时间才能完全确定特定语言的所有规则：有时使用 lex 和 yacc 等工具无法分析该语言。这尤其适用于上下文无关文法和书面语言。如果 lex 程序分析术语并可以“吃掉”空格，那么在某些语言中它们仍然是必需的。
需要几十年的项目和编程语言才能看到哪些算法的卓越表现，因为软件公司希望获得巨大的声誉和高技术领先地位，为此他们会在绝对保密的情况下进行这方面的研究。结果有时是令人振奋的，包括他们投入其中的资源。
Microsoft 等大公司的情况就是如此。但知识的积累被保密起来，只有少数人能够进行真正的创新：Microsoft 在 15 年内创建的编程语言可能是：Visual Basic。
诚然，处理 VB 文件的源代码仍然得到很好的保护。事实上，它与其他文件非常不同，因为它们没有能力轻松编译该语言。这展示了语法
Function Call (param1, param2, _
下划线字符暴露了特定的算法。如果 lex 程序应该编译 VB，那么它应该考虑到上下文和回车符通过以下划线字符分隔的解析，在该上下文中，下划线字符用于在下一行继续指令，因为 VB 不允许多行！
新的 C# .NET 系统比 Java 明显更先进，我们必须承认，它也有巨大的变化。最壮观的是，源文件编译的处理速度远远超过了基本编译算法的速度。这不是因为代码只是转换为 IL，而是因为解析在乔姆斯基技术方面要先进得多。
让我们面对现实吧：乔姆斯基是自动机理论（如句法分析）的代表，但这些理论早已被世界上的私人公司淘汰，甚至新的算法也可能与乔姆斯基的限制时间相矛盾，而计算机仍然被当作二进制文件处理，而不是在 1/10 秒内处理数千页文本。
在 2010 年，XML-FO 能够将所有格式的大文件转换为 PDF 格式（例如），这比由简单有限规则定义的简单迭代 PLC 简单得多。我们越来越远离二进制，从字节转向直接处理和用 Unicode 编写的文本（这使文本文件的大小翻倍甚至翻四倍），而无需用一些小的附加项来使文件变成二进制序列！
在 2015 年，所有网站都显示格式化和分析的反馈，并对所有指令执行语法高亮显示，自动缩进源程序，甚至自动审核所说内容，同时不忽略国家和国际法律，有时还会进行手动审核来替换或补充。
所有这些都不是一个人能做到的，而是由一群有能力为每家公司提供有针对性和可靠的专业知识的人共同完成的，并且不被人们忽略。社交网络就是一个例子，开源社区扩展到了各种能力，吸引了许多人对知识技艺的关注。
有人可能会说，计算机和编程代表了非常高水平人群的宇宙……甚至是世界的国王。但这并不是说要忘记错误的决定：就像其他领域，特别是在知识领域一样，很容易从经济角度考虑问题，而许多人宁愿选择经济利益而非知识的利益。
请记住，计算领域仍然有些难以传播知识，原因并非其封闭性，而是有时它并非任何智力都能企及。事实上，这是一个需要不易获得的认知能力的领域。让我们让那些希望在几天内教授新编程的人，他们像周日的江湖骗子一样。
Using the Code
Application
我首先描述了软件的使用。该软件名为 precedence（优先级），因为我使用了一个原始的优先级定义概念，只有一个参数：优先级数。最低优先级数字是 1。这是所有项（数字和名称）的优先级。较高的数字定义了运算符的优先级，已知以下运算符按优先级升序排序：+ - * /。括号可以附加，在这种情况下，优先级会发生变化。
该应用程序显示一个单一窗口。有 4 个选项卡和一个菜单：帮助、语法和测试结果。菜单和文件页面：文件菜单允许加载/保存扩展名为 * .f 的文件，其中包含语法规则示例。第二个菜单显示选项卡。
语法选项卡对应于一组独立规则的配置。下面的示例显示了用于识别整数的加法、乘法、减法和除法以及变量名的规则。括号用于更改优先级。
第三个选项卡允许您选择一个测试样本。下拉列表用于选择一个测试。要分析的文本在输入区域；该区域是可编辑的；一个按钮用于添加新测试或保留对文本的更改。单击“验证”按钮将根据“语法”选项卡中定义的语法规则执行文本的解析。
第四个选项卡显示分析结果。结果是解析树层次结构的 XML 表示。
定义语法规则
- 规则首先由一个目标标识，即其类型
- 无操作：如果什么都不发生：此规则用于“吃掉”某些单词
- 表达式列表：此操作创建一个新表达式并将其存储在列表中；它创建一系列连续的表达式。
- 开括号：此操作在表达式中打开一个括号
- 闭括号：此操作结束一个括号；如果闭括号后面没有开括号，则会发生解析器错误。
- 开子表达式：此操作在树中开始一个子分支
- 闭子表达式：此操作进入树的子分支
- 一元运算符：表示一元运算符；您必须指定一个优先级数字
- 二元运算符：二元；您必须指定一个优先级数字
- 语句：表示这是一个指令
- 项：表示它是一个项
- 一元或二元运算符的优先级数字必须等于或大于 1。
指令或项始终具有最低优先级，即 1。优先级数字越高，运算符越次要：因此，每当遇到具有较高优先级的运算符时，它就低于具有较低优先级的运算符：例如，加法运算符 + 的优先级低于乘法运算符 *，因为乘法相对于加法；因此，乘法会自动放置在 + 运算符下方（如果存在）。同样，如果乘法后面跟着加法，那么加法会自动放置在乘法之上的轴上。因此，优先级数字是运算符和项在树中存储方式的唯一指示符。项和指令具有最低优先级级别，因为它们将始终是语法树的叶子。 - 用于在树中构建的对象由正则表达式唯一标识。
- 可以指定属性
属性按名称命名并包含一个值。name = value [, ...] 形式构成属性集。属性将添加到生成的语法树的 XML 表示中。
开发
FIFO 类实现了一个生产者/消费者算法。该类提供 FifoWriter，随后识别标记。词法单元仅读取一次；没有其他读取或仅读取产品；树的构建是最佳的，因为子分支是连续添加的，而不会被重放。
FifoReader 类实现了一个线程，该线程处理接收到的词法数据，形式为表达式对象，其类指示要插入树的对象类型。数据的读取会立即搜索解析树中的位置。例如，当出现两个连续的二元运算符时，可能会发生错误。在这种情况下，产生的处理可能会变得混乱。Expression 类包含所有发送到 FifoWriter 类的操作。此类的方法应用于发送的每种类型的项：开括号或闭括号、短语、表达式列表、一元或二元运算符、项或指令。
Terminate 方法表示处理已结束，必须完成线程的执行。树中对象的插入系统由三个主要类实现：Movement、nodule 和 NoeudNAire。nodule 类及其派生类 NoduleOperateurBinaire、NoduleOperateurUnaire、NoduleTerme 和 NoduleInstruction 是存储在树中的项。每个类都实现虚拟函数 Print()，该函数将表示写入 XML 文档。NoeudNAire 类是执行图形中插入位置搜索的类，它考虑了要插入的对象类型及其相对于图中已存在对象的优先级：可以将节点插入树的顶部，或者插入到现有节点的位置，而该节点会移动到子图中。根据优先级，如果它大于轴上对象，则要插入的对象出现在下方。树可以有两个分支；有两个分支以上，表明定义的语法规则应进行审查。
Movement 类执行实际的插入功能到生成的语法树中。它对应于要插入树的节点处理的结束。
如果实现方式是这样的，通过使用后台线程，这是因为处理非常详细且耗时，超过了词法单元的读取处理。此外，底层系统还可以处理其他情况，例如错误检测、处理和指示（行、列、错误描述），以帮助开发人员更正其语法规则或修复其程序的来源。
关注点
这是解析领域一项非常先进的技术。乔姆斯基一直认为文本分析和编译是最难掌握和最耗时的技术。
通过这个程序，并富有创造性地使用优先级数字，递归形式消失，取而代之的是由正则表达式标识的简单词法单元列表；要分析的文本从头到尾读取，无需校对，也无需状态即可跟踪语法规则的进度。
有了这个程序，语法定义变得简单、快速、直观且易于理解。
历史
在未来的文章中，我将介绍该软件的演进，例如
- 背景
- 类型推断（整数、实数、带反馈数据的运算符）
- n 元运算符的定义（三个或更多子节点）
- 语法高亮
- 为直接编译（或代码转换）做准备
- 逆向工程
- 带表达式和计算函数的属性