PParser - 第二部分

• 下载演示 - 119.2 KB
• 下载源码 - 94.3 KB

引言

第二部分涉及上下文。上下文是在解析文本时应用的策略字段。文本的构成规则并非总是相同的。例如，文字字符串由其结束的引号来监督。在这两个引号之间，所有的字符和所有的单词，其解析方式与整个文本的解析方式不同。

同样，所有编程语言都提供添加注释，这些注释在编译时永远不会被考虑。然而，这些注释用于“注释”甚至文档化程序过程（键入，定义过程是什么，等等），甚至管理计算机程序在注释中维护期间的变更可追溯性。

另一个更难的例子是动态网页和脚本语言，如JavaScript或VB（用于Windows），直接嵌入网页以显示。HTML标签 <script> 的language属性必须包含；通常，此属性是JavaScript，但也可以选择VB作为语言。在Windows上，脚本将被识别为Visual Basic脚本。类似地，带有前缀“asp”（用于ASP.NET）或前缀<?php 用于PHP脚本的标签会影响通用解析系统，而每种技术倾向于被封装在一个不支持所有格式的系统中。

为什么这有用？

从这些不同的观点来看，定义解析上下文对于逆向工程至关重要，而不是对于每个系统操作程序的案例。此外，解析具有不同语法的文本片段表明，无需分析整个文本，只需分析片段。然而，一个能够通过简单的分隔符处理片段的端到端自由分区的文本并延迟处理的混合解析系统，似乎在逆向工程和通用编程语言的演进方面具有意义。因此，了解如何定义上下文以分析编程语言的片段而不丢失这些片段的动态潜在影响非常重要。

问题如下

1. “总的来说，如何以不同的方式解析由两侧定界符标识的片段？”
2. “我们应该开发什么样的算法才能在不单独处理片段的情况下从一个上下文切换到另一个上下文？”
3. “如何确保所使用的算法不局限于某些‘原始’语言？”

背景

在上一篇文章中，我谈到了VB语言和用于将多行指令视为一条指令的通配符。使用上下文并将语法规则关联到文本片段，就可以正确处理VB语法。

               Function Call (param1, param2, _
                              param3, param4, _
                              param5)

您可以在以下网址下载VB .NET规范：https://www.microsoft.com/en-us/download/confirmation.aspx?id=22306。该文档指出，Visual Basic支持以空格后跟下划线字符和0个或多个空格后跟回车符来继续一行。如果本文档使用的VB规范BNF，这意味着，前提是该语言是使用LEX或FLEX等程序开发的。我们注意到，Microsoft从未提供过词法和语法分析程序，并且在.NET之前，Windows没有这类库。而在Linux上，FLEX和BISON通常是默认安装的。

通常，编写“编译器”（或仅解析）需要5个步骤

1. 对于任何编程语言，即使是尚不存在的语言，似乎都没有困难创建FLEX文件，然后（之后）创建BISON文件。
2. 当你开始创建FLEX文件时，在正确解析文本和所有测试方面就已经存在一些小困难。总会有一个或多个测试不能立即起作用。
3. 一旦越过这个阶段，我们就必须继续完成整个编程语言的源代码，而不引起对先前测试的回归。真正的问题开始出现，我们意识到FLEX并非如此之好，实际上，这使得任务非常困难，甚至不可能用FLEX完成实际解析。
4. 然后你必须专注于BISON，因为FLEX永远不够。然后你必须创建BISON文件，最后生成读取编译器所需的语法树。
5. 最后，我们必须：

• 处理所有可能的错误：逐个处理每个错误，并提供正确的错误指示描述，尽可能接近“真实”原因。
• 不要在第一个错误处停止“编译”，并提供可能的选项。

这将是完成编译任何编程语言的程序。这需要几个月的时间来确保稳定性和高可靠性，并通过定期使用它。学习和巨大的工作等待着，最终可以进行调整，头脑中充满了开发，甚至是对你自己的分析工具进行彻底的重新设计，而无需FLEX或BISON！

这些程序对于小型扫描器来说还可以，但对于专业项目或“真正的”编译器来说完全不适合。此外，语法和句法分析器比比皆是，不是因为它们令人兴奋和困难，而是因为现有工具的灵活性不足。

使用代码

用户手册

首先，我将描述软件的使用。该软件名为Precedence，因为我使用一个原始的优先级定义概念，只有一个参数：一个优先级数字。最低优先级数字是1。这是所有项（数字和名称）的优先级。更高的数字定义运算符的优先级，并且以下运算符按优先级升序排序：+ - * /。可以添加括号，在这种情况下，优先级会发生变化。

该应用程序显示一个窗口。

有5个选项卡和一个菜单：帮助、用法、语法、测试和结果。文件和页面菜单：文件菜单用于加载/保存扩展名为*.f的文件，其中包含语法规则示例；第二个菜单显示每个选项卡。

上下文选项卡是一个列表，其中每一行包含一个复选框、一个名称和一个标题。以数据形式存储的信息对应于此选项卡列表中任何上下文的所有上下文。每个上下文定义一组有限的语法规则，这些规则特定于该上下文；上下文有一个名称用于唯一标识它和标题；它就是显示在语法选项卡中的标题。

语法选项卡匹配一系列语法规则的配置，用于选择下拉列表上方列表中的一个上下文。下面的示例显示了用于识别赋值和=运算符的规则，并且可以表示XML树。括号用于更改操作的优先级。

第四个选项卡用于通过下拉列表选择一个测试样本。要解析的文本在输入区域中；该区域是可编辑的；一个按钮用于添加新测试或保留对文本所做的更改。单击“解析”按钮将根据“语法”选项卡中定义的语法规则解析文本。

最后一个选项卡显示分析结果。结果是解析树的XML表示。

定义语法规则

1. 规则首先由一个目标标识，即它的类型。
   • 无操作：不执行任何操作：此规则对于“吃掉”某些单词很有用。
   • 表达式列表：此操作创建一个新表达式并将其存储在列表中；它创建一系列连续的表达式。
   • 开括号：此操作在表达式中打开一个括号。
   • 闭括号：此操作结束一个括号；闭括号后跟开括号，否则会发生解析器错误。
   • 交换上下文：此操作执行即时上下文的更改；当上下文更改时，将应用该上下文选定的语法规则。您可以创建上下文的新实例或恢复之前的实例。之前的上下文已被缓存。
   • 关闭上下文：此操作结束一个上下文；将恢复并应用之前缓存的上下文及其语法规则；已关闭环境的语法不再适用。
   • 打开子表达式：此操作开始树的一个子分支。
   • 关闭子表达式：此操作进入树的子分支。
   • 一元运算符：表示一元运算符；您必须指定一个优先级数字。
   • 二元运算符：二元；您必须指定一个优先级数字。
   • 语句：表示这是一个语句。
   • 项：表示这是一个项。
2. 一元或二元运算符的优先级数字必须大于或等于1。语句或项的优先级始终最低，即1。优先级数字越高，运算符越次要：因此，每当遇到优先级更高的运算符时，它就低于优先级较低的运算符。例如，加法运算符+的优先级低于乘法运算符*，因为乘法相对于加法；因此，乘法会自动放置在+运算符下方（如果存在）。同样，如果乘法后面跟着加法，那么加法会自动放置在乘法上方的轴上。因此，优先级数字是运算符和项如何存储在树中的唯一指示符。项和语句具有最低的优先级级别，因为它们始终是语法树的叶子。
    
3. 用于构建树的对象由正则表达式唯一标识。
4. 在上下文更改的情况下，上下文字段用于指示要应用的上下文名称（而非标题）（运行上下文实例）。下一个字段的值被选中，如果应该使用之前上下文的实例。未选中的复选框表示需要使用新实例继续分析文本。
5. 可以指定属性：属性通过名称命名并包含一个值。suite name = value [, ...] 构成属性集。这些属性将被添加到生成的语法树的XML表示中。

Application

最常见的测试是识别文字：数字和字符串。还可以进行其他测试，例如XML和/或HTML或动态网页。以下是BNF示例。

start
ident := [a-zA-Z][a-zA-Z0-9_]*
literal := entier | decimal | scientific | any-string | quoted-char

entier := non-zero-chiffre chiffres
non-zero-chiffre := [1-9]
chiffre := [0-9]
chiffres := chiffre*
decimal := entier "," chiffre+
scientific := entier "." chiffre+ "E" ("+"|"-") entier
dchar :=  "\\\\" | "\\\"" | "\\" | "\"" | .*
dstring := dchar*
dquoted-string := "\"" dstring 
char :=  "\\\\" | "\\'" | "\\" | "'" | .*
string := char*
quoted-string := "'" string 
quoted-char := "'" char
any-string := quoted-string | dquoted-string
name := [a-zA-Z][a-zA-Z0-9_-]*
attribute := name "=" quoted-string
attributes := attribute* | ">"
xmlOpenNode := "<" name attributes
xmlCloseNode := "</" name attributes
xml := (xmlOpenNode | xmlCloseNode | ident)*
start := ident "=" literal | "xml" xml | "html" xml

注意两种特殊情况：上下文被缓存并更改为另一个上下文，然后返回缓存的上下文：字符串字符和XML，在<和>之间。我们可以确定从一个上下文到另一个上下文的转换对应于FLEX可重入的项。然而，交换两个现有上下文的事实必须实例化多个FLEX语法。

以下是PParser应用程序的结果

上表显示了每个上下文要应用的各种规则。
同样，测试如下

a = 1
b = 349095
c = 34.44
d = 344E+14
e = 34.000011E-10

e = ''
a = '1234.555'
b = 'reieopioiprerze \ jklfjdflkds \\ fjdljfdls \r\n \b \' kfdmlkfdkfdms'

e = ""
a = "aakfdfdjs fsdjklfj kfldsj fkljslks"
a = "1234.555"
b = "reieopioiprerze \ jklfjdflkds \\ fjdljfdls \r\n \b \" kfdmlkfdkfdms"

xml (<a>ttt</a>)
xml (<a>tt<b></b></a>)
xml (<a m='1' g='zzzzzz'>tt<b m='2' g="kfjsdlkjklfjs \ \r\n \"">rrr</b></a>)

请注意，对于某些语法，动态添加/删除规则会很有趣

•  动态添加/删除规则
•  评估内容知识“不吞噬”
•  如果识别出任何术语，则触发特定操作

开发

Fifo类实现了一个提供者/消费者算法。该类随后提供FifoWriter识别的令牌。词法单元只读取一次；没有其他读取或只读产品；树的构建是最佳的，因为子分支是连续添加的，而无需重播。

FifoReader类实现了一个线程，该线程处理接收到的词法数据，将其形式为表达式对象，其类指示要插入树的对象类型。读取数据会导致立即搜索解析树中的位置。例如，当两个连续的二元运算符出现时，可能会发生错误。在这种情况下，结果处理可能会变得混乱。Expression类包含发送到FifoWriter类的所有操作。该类的函数应用于发送的每种类型的项：开括号或闭括号，作为短语，表达式列表，一元或二元运算符，项或语句。

Terminate()函数指示处理已结束，必须完成线程的执行。树中对象的插入系统由三个主要类实现：Mouvement、Nodule和NoeudNAire。Nodule类及其派生类NoduleOperateurBinaire、NoduleOperateurUnaire、NoduleTerme和NoduleInstruction是存储在树中的项。每个类实现虚拟函数Print()，该函数以XML文档的形式写入表示。NoeudNAire类是执行图中插入位置搜索的类，它考虑了要插入对象的类型及其相对于图中已有的其他节点的优先级：可以将节点插入到树的顶部，或者插入到现有节点的位置，然后该节点移动到子图中。根据优先级，如果它大于轴上某个对象，则要插入的对象位于下方。树可以有两个分支；超过两个分支，则表示应审查定义的语法规则。

GrammarContext和WorkingContext类处理上下文：GrammarContext类定义了上下文的名称以及与上下文语法规则关联的列表。当开始读取文件时，起始上下文是“Start”框被勾选的第一个上下文。要分析文本，我们使用一个正则表达式；此正则表达式是每个上下文规则的词典列表。运算符|（或）将添加到两个词典之间。

例如，对于“tagxml”上下文，规则是

那么下面的正则表达式将是

                (?<r1> [a-zA-Z -]+) | (?<r2>=) | (?<r3>\") | (?<r4>') | (?<r5>\>)|(?<r6>[ \t]+ | (\r\n)+)

在这个正则表达式中，单词的顺序非常重要：如果两个单词以相同的对应关系开始，则前面的单词必须是对应关系更长的那个。例如，如果A:=“\\\\”和B=“\\”，则应先声明A后声明B。对于给定的上下文，正则表达式将按列出的顺序定义上下文的所有规则。

            string regexStr = String.Empty;
            int index = 0;
            foreach (GrammarItem g in c.ContextRules)
            {
                if (!String.IsNullOrEmpty(g.LexicWord))
                {
                    if (index > 0) regexStr += "|";
                    ++index;
                    regexStr += "(?<r" + index.ToString() + ">" + g.LexicWord + ")";
                }
            }

然后，输入文本中从头到尾识别出的每个连接都需要搜索相应的规则，并检测规则的类型（在可能的规则类型中），如上列表所示。

                    Regex r = new Regex(regexStr, RegexOptions.Multiline);
                    Match m = r.Match(this.txtSample.Text, previous.MatchPosition);
                    for (int indexGroup = 1; indexGroup <= countRules; ++indexGroup)
                    {
                        Group g = m.Groups["r" + indexGroup.ToString()];
                        if (g.Success)
                        {
                            if (String.IsNullOrEmpty(g.Value))
                            {
                                ++previous.MatchPosition;
                                goto redo2;
                            }
                            GrammarItem gi = c.ContextRules[indexGroup - 1];
                            lexic = new LexicItem(c, gi, g.Value);
                            lexic.MatchPosition = g.Index + g.Length;
                            break;
                        }
                    }

变量previous是之前的匹配：MatchPosition属性确保搜索对应关系在任何上下文下都能在之前停止的地方继续进行。

注意：对Group类（.NET正则表达式类）的Value属性进行空字符串测试，可以确保当没有任何内容被读取时，位置将继续前进（以防止无限循环）。

当上下文发生更改时，当前上下文将被缓存，正则表达式是新上下文的正则表达式；当当前上下文的处理完成时，将恢复之前缓存的上下文，并重新构建正则表达式。

只有在形成解析树的XML表示时，我们才需要从一个上下文移动到另一个上下文，将XML片段组合到一个文件中。此外，两个对象类Nodule（继承自该类）用于控制整个XML文件的构建：NoduleContextChange和NoduleContextStop。NoduleContextChange类保留要应用的已工作上下文的名称（运行上下文实例），NoduleContextStop类保留先前已工作上下文的名称。

为了表示语法树的所有元素，树的每个节点都实现了Nodules属性。此属性构建了树节点及其所有子节点序列。此外，还添加了两个附加节点：XmlStartElement和XmlEndElement。XmlWriter类.NET通过映射函数（如WriteStartElement()和WriteEndElement()）来构建语法树。整个算法按顺序构建语法树，最终得到一个包含在每个上下文中构建的所有片段的单个XML文件。

Mouvement类在生成的语法树中执行实际的插入函数。它对应于要插入树中的节点处理的结束。

如果实现方式是这样，通过在后台使用线程，是因为处理如此详细，以至于花费了读取词法单元的时间。此外，底层系统可以允许研究其他情况，例如错误检测、处理及其指示（行、列、错误描述），以帮助开发人员纠正其语法规则或修复其程序的源。

关注点

这是解析领域的一项伟大先进技术。乔姆斯基一直认为文本分析和编译是最难掌握、最耗时开发的技术。通过这个程序，以及对优先级数字的创造性使用，递归形式消失了，取而代之的是一个简单的由正则表达式标识的词法单元列表；对要分析的文本的读取是从头到尾进行的，无需校对，也无需状态来跟踪语法规则的进度。

重入是通过上下文实现的。每个上下文的规则集都是特定于上下文的。可以维护上下文的状态以便以后恢复；程序可以适应多文件。通过此程序，语法规则的定义是一个列表，而不是解析树。

语法的构建变得简单、快捷、直观且不复杂。

继续这个项目将非常令人兴奋。该过程可以带来更多有趣的技术，并且可以解析极其特定甚至新的编程语言。在编写此代码时，一些错误需要花费时间来纠正；幸运的是，VS有一个很棒的调试器。

这篇文章讲的是一个软件。一个可以交谈的软件。

历史

在未来的文章中，我将介绍该软件的演进，例如：

• 类型推断（整数、实数、带反馈数据的运算符）
• 具有表达式和计算函数的属性
• 在解析期间存储数据计算
• n元运算符（三个或更多子节点）的定义
• 语法高亮
• 准备直接编译（或代码转换）
• 逆向工程