词法分析和解析概述
Perl程序员花很多时间处理数据：读取数据、转换数据，然后输出结果。Perl在这方面非常擅长，拥有各种字符串操作工具，包括正则表达式。
正则表达式能走多远：看到多次建议说，不能仅用正则表达式本身解析HTML或XML。当Perl内置的文本处理工具不够用时，你必须转向更强大的工具。
那就是解析。
词法分析和解析概述
要更正式地讨论词法分析和解析到底是什么，可以从维基百科的定义开始：[词法分析](http://en.wikipedia.org/wiki/Lexing)和[解析](http://en.wikipedia.org/wiki/Parsing)。
不幸的是，当人们使用“解析”这个词时，他们有时包括词法分析的概念。有时他们不包括。这可能会导致混淆，但我将尽量保持它们清晰。其他词语也存在类似的情况，我们的思维通常会通过分析词语使用的上下文来理解其特定含义。所以，请记住这一点。
词法阶段和解析阶段可以合并为一个单一过程，但我主张始终将它们分开。请相信我，我会很快解释。如果你在保持这两个概念分开时遇到困难，请注意，这些阶段很方便地按字母顺序运行：首先我们进行词法分析，然后进行解析。
历史课 - 缺席
在这个时候，这篇文章通常会提供这个领域的历史发展总结，解释世界是如何走到今天的。我不会那样做，特别是因为我第一次接触解析很多年前，当时（lex、bison、yacc）这些工具操作起来非常复杂，我发过誓要戒除。尽管如此，了解这些工具仍然可用是好事，所以这里有几点参考
Flex是lex的后继者，而Bison是yacc的后继者。这些都是成熟的（旧的）工具，可以让你不必手工构建词法分析器或解析器。这篇文章解释了为什么（我仍然）不使用这些工具。
但为什么研究词法分析和解析呢？
有许多情况，唯一的解决方案需要词法分析和解析
运行程序
这很容易理解，但很难实现。为了运行程序，我们需要设置一系列前置条件
- 定义语言，可能称为Perl
- 为该语言的语法编写编译器（结合词法分析和解析）
- 用该语言编写程序
词法和解析源代码
毕竟，在运行之前它必须是语法正确的。如果不是，我们将显示语法错误。这一步真正重要的是确定程序员的意图，即编写代码的原因。在这一步，我们不会运行代码，但我们会得到输出。我们如何做到这一点？
运行代码
然后我们可以查看输出，希望它是正确的。如果不是，也许我们必须找到并修复逻辑错误。
渲染HTML + 内容的网页
步骤与第一个例子相同，只是用HTML替换Perl，尽管我无法将编写HTML称为编写程序。
这一次，我们要问：网页设计师的意图是什么。他们想渲染什么，如何渲染？当然，与编程语言相比，语法检查要宽松得多，但仍需进行。例如，这里有一个可以通过Marpa解析的明显损坏的HTML示例。
<title>Short</title><p>Text</head><head>有关更多详细信息，请参阅Marpa::HTML。到目前为止，我在所有工作中都使用了Marpa::R2，这并不涉及HTML。
渲染图像，可能是SVG格式
以下文件是用DOT语言编写的，由Graphviz图形可视化工具（teamwork.dot）使用
digraph Perl { graph [ rankdir="LR" ] node [ fontsize="12pt" shape="rectangle" style="filled, solid" ] edge [ color="grey" ] "Teamwork" [ fillcolor="yellow" ] "Victory" [ fillcolor="red" ] "Teamwork" -> "Victory" [ label="is the key to" ] }给定这个“程序”，渲染器通过渲染图像来实现作者的意图
要实现这一点需要什么？如上所述，词法分析、解析、渲染。使用Graphviz的
dot命令执行这些任务，我们会运行shell> dot -Tsvg teamwork.dot > teamwork.svg注意：这些示例中使用的文件可以从http://savage.net.au/Ron/html/graphviz2.marpa/teamwork.tgz下载。
链接到DOT语言指向DOT语法的定义，它以某种随意的BNF版本编写：Backus-Naur Form。这很重要，因为通常很容易将语言的BNF描述转换为词法分析和解析器中的代码。
使用输入文件中的不同语言渲染相同的图像
假设你决定Graphviz语言太复杂，因此你围绕它编写了一个包装器，以便最终用户可以编写该语言的简化版本。这实际上发生了，原始努力现在可以在已弃用的Perl模块Graph::Easy中找到。Tels，作者，设计了自己的非常巧妙的小语言，他称之为
Graph::Easy。当我接管
Graph::Easy的维护时，我发现代码过于复杂，难以阅读，更不用说工作了，所以我编写了另一个词法分析和解析器的实现，以Graph::Easy::Marpa的形式发布。我将在另一篇文章中详细讨论这一点。现在，让我们讨论之前用Graph::Easy（teamwork.easy）重写的图形。graph {rankdir: LR} node {fontsize: 12pt; shape: rectangle; style: filled, solid} edge {color: grey} [Teamwork]{fillcolor: yellow} -> {label: is the key to} [Victory]{fillcolor: red}这当然更简单，但
Graph::Easy::Marpa是如何工作的呢？简单：词法分析、解析、渲染。更多Graph::Easy::Marpa的示例可以在我的Graph::Easy::Marpa示例中找到。
现在应该很清楚，词法分析和解析实际上非常普遍，尽管它们通常在幕后操作，只有它们的渲染输出对普通程序员、用户或网络冲浪者可见。
所有这些问题都有一个共同点，即源文本格式复杂但结构良好，对于HTML文档的作者来说，一些细节略显笨拙。在每种情况下，编写词法分析和解析器的程序员的职责是尊重原始文本作者的意图。我们只能通过将输入中的每个标记识别为具有独立意义的单元（例如，单词print表示输出作者选择的内容）来实现这一点，并通过实现这种意义（对于print，使输出在设备上可见）。
有了所有这些，我可以安全地声称，词法分析和解析的普遍性和成功证明它们是软件工程领域的至关重要组成部分。那么为什么要研究它们呢！
好的解决方案和自制的解决方案
讨论词法分析和解析的另一个更重要原因是：训练程序员，在没有这些领域的专业知识的情况下，抵制使用他们已经熟悉的工具的诱惑，正则表达式显然是首选。
当然，正则表达式适用于许多简单情况，flex和bison等老牌工具也始终可用，但现在又有一个新成员加入：[Marpa](http://www.jeffreykegler.com/marpa)。Marpa从过去几十年中进行的理论研究中汲取了大量精华，并提供了多种形式。
libmarpa：用C手工编写的。
Marpa::XS：libmarpa上一个版本的Perl和C接口。
Marpa::R2：libmarpa最新版本的Perl和C接口。这是我使用的版本。
Marpa::R2::Advanced::Thin：libmarpa的最新和最薄的接口，该接口说明了如何使Marpa对非Perl语言可用。
当然，问题在于这些工具是否是好的选择，甚至是卓越的选择。好消息是，Marpa的优势非常明显。它经过充分测试，这本身就是一个巨大的优势。它有一个Perl接口，这样我就可以用Perl指定我的任务，然后让Marpa处理细节。它有自己的[Marpa Google Group](http://groups.google.com/group/marpa-parser?hl=en)。它已经被CPAN上的各种模块使用（参见[在CPAN上搜索Marpa](https://metacpan.org/search?q=Marpa)）；开源意味着你可以看到其他人如何使用它。
更好的一点是，Marpa有一个非常简单的语法，一旦你习惯了，当然！如果你遇到麻烦，只需在Google Group上发帖。 （如果你曾经使用过flex和bison，你会对驱动Marpa有多简单感到惊讶。）Marpa也非常快，因为libmarpa是用C编写的。它的速度有些令人惊讶，因为新技术通常需要一些时间才能超越现有技术，同时提供所有重要的稳定性。
最后，Marpa正在不断改进。例如，最近作者消除了对Glib的依赖，以提高可移植性。他的工作仍在继续，因此用户可以期待在一段时间内看到一系列渐进式改进。
我自己在[Graph::Easy::Marpa](https://metacpan.org/pod/Graph::Easy::Marpa)和[GraphViz2::Marpa](https://metacpan.org/pod/GraphViz2::Marpa)中使用Marpa，但这不是一篇专门关于Marpa的文章。
词法分析器的职责描述
如我之前提到的，这些阶段按英文字母顺序排列。首先进行词法分析，然后进行解析。
在这里，我用“词法分析”来表示与解析相比相对简单的（比较简单）过程，即对文本流进行标记化，这意味着将输入流切割成离散的标记并识别每个标记的类型。输出是一个新的流，这次是独立的标记流。（词法分析比解析简单。）
词法分析只做识别标记的工作。关于这些标记的含义、它们可接受的顺序或任何其他问题都是解析器的事。词法分析器会说：我找到了另一个标记，并将其识别为类型T。因此，对于每个识别的标记，词法分析器将产生两个项目
- 标记的类型
- 标记的值
由于词法分析过程是反复进行的，词法分析器将产生一个由标记元素组成的数组，每个元素至少需要这两个组件：类型和值。
在实践中，我更喜欢将这些元素表示为hashref
{
count => $integer, # 1 .. N.
name => '', # Unused.
type => $string, # The type of the token.
value => $value, # The value from the input stream.
}
……由一个类型为Set::Tiny的对象管理。后者模块有很多很好的方法，非常适合这项工作。直到最近，我使用的是Set::Array，这是我未曾编写但现在已经维护的模块。然而，我最近的一份报告《Set-handling modules》从Set-handling modules中获得了见解，该报告比较了一系列类似的模块，这让我确信应该切换到Set::Tiny。对于可能最好以树的形式存储其输出的应用程序，Perl模块Tree::DAG_Node非常出色。
《count》字段看似冗余，但在词法分析器的清理阶段有时很有用，因为此时可能需要将正则表达式分割的标记合并。此外，如果需要的话，它也对解析器可用，所以我总是将其包含在哈希引用中。
《name》字段实际上并未使用，但为那些分叉或子类化我代码的人提供了一个可以工作的地方，他们可以按照自己的需求进行操作，而不必担心他们的编辑会影响基本代码。
解析器的职责描述
解析器关注的是每个标记出现的上下文，这意味着它关心所检测到的标记序列和组合是否真的符合预期的语法。
理想情况下，语法以BNF形式提供。这使得将其转换为Marpa可接受的格式变得容易。如果您有其他形式的语法，您的任务可能会更加困难，这仅仅是因为其他人没有完成形式化语法的艰难工作。
那就是解析器。什么是语法？
语法和子语法
我之前已经展示了一个示例语法，用于DOT格式。普通人如何理解用BNF编写的文本块？培训有助于。除此之外，我还从实践经验中汲取了一些东西。最终，对于我们这些初学者来说，会意识到无论语法如何正式定义，其中都包含两个子语法
子语法 #1
一个子语法指定了标记的外观，意味着它在输入流中可以采取的形式范围。如果词法分析器检测到一个无法理解的候选者，它可以生成一个错误，或者激活一个名为Ruby Slippers（与Ruby编程语言无关）的策略。这种技术是由Marpa的作者Jeffrey Kegler命名的。
简单来说，Ruby Slippers策略通过修改当前标记（或更大的输入流部分）以满足语法，并在新的综合标记处重新启动处理。Marpa可以说是唯一能够做到这一点的方法。
子语法 #2
另一个子语法指定了这些标记可以组合的允许方式，这意味着如果它们不符合语法，代码将生成某种类型的语法错误。
容易吗？
我将语法分为两个子语法，因为这对我说很有帮助，帮助我表达我的词法分析和解析的金科玉律：将第一个子语法编码到词法分析器中，第二个子语法编码到解析器中。
如果您知道标记的外观，您可以使用词法分析器通过将其分割成单独的标记来标记输入流。然后您将这些标记交给解析器进行（更多）语法检查，并对用户可能使用该特定输入流（标记组合）的意图进行解释。
这种词法分析和解析之间的分离为任何新项目提供了一个清晰的攻击计划。
如果您认为这会变得复杂，实际上它只是听起来很复杂。是的，我引入了一些新概念（并且还将引入一些），但不要绝望。这并不真的那么困难。
对于任何给定的语法，您必须以某种方式在某处管理“这是否是一个有效的文档？”这一问题的复杂性。使用正则表达式识别标记很容易。（这可能是为什么这么多人停留在使用正则表达式挑选文档而不是转向解析的阶段。）跟踪该标记出现的上下文以及语法允许该标记的上下文是困难的。
设置和管理正式语法及其实现似乎很复杂，但这是一个指定且被广泛理解的机制，你不必每次都重新发明。词法分析和语法分析的方法将你需要编写的代码限制为两件事：一组规则，说明如何在语法中构造标记，以及一组规则，说明当构建一组有效的标记组合时会发生什么。这种限制使你能够专注于应用程序的重要部分——确定符合语法的文档的含义（作者的意图）——而不是过多地关注验证文档是否符合语法的机制。
换句话说，你可以更多地关注你想要用文档做什么，而不是如何用它做某事。
编写词法分析器
词法分析器的任务是识别标记。子语法#1指定了这些标记的外观。任何词法分析器都必须检查输入流，可能是一个字符一个字符地，以查看当前输入附加到立即前面的输入是否符合标记的定义。
程序员可以以多种方式编写词法分析器。我通过结合正则表达式和DFA（确定有限自动机模块）模块来实现。博客条目More Marpa Madness讨论了在词法分析器（以及在解析器中，我在那里使用它）中使用Marpa。
什么是DFA？滥用任何合理的定义，让我这样描述它们。确定部分意味着给定相同的输入和相同的阶段，你将始终得到相同的结果。《有限》部分意味着输入流只包含有限数量的不同标记，这简化了代码。《自动机》本质上是一种软件机器——一个程序。DFA也常被称为STT（状态转换表）。
你如何在Perl中使这一切都发挥作用？MetaCPAN是你的朋友！特别是，我喜欢使用Set::FA::Element来驱动这个过程。对于候选替代方案，我汇编了一个与该领域相关的Perl模块列表，同时清理了Set::FA的文档。见Set::FA的替代方案。我没有编写Set::FA，也没有编写Set::FA::Element，但现在我维护它们。
将语法从BNF（或你使用的任何形式）转换为DFA提供
对问题的洞察
将BNF转换为正则表达式意味着你必须完全理解语法定义在说什么。
公式的清晰性
你最终会得到一个电子表格，它简单而清晰地编码了你对手册的理解。
电子表格？是的，我将导出的正则表达式以及其他信息存储在电子表格中。我甚至将这个电子表格纳入源代码。
回到有限自动机
在实践中，构建词法分析器是一个重复阅读BNF定义（这里是指DOT语言）的过程，以构建相应的一组正则表达式以处理每个情况。这无疑是一项繁重的工作。
例如，通过使用正则表达式/[a-zA-Z_][a-zA-Z_0-9]*/，你可以使Perl的正则表达式引擎智能地吞噬字符，只要它们符合定义。用通俗的话说，这个正则表达式说：以字母开头，大写或小写，或下划线，后面跟0个或多个字母、数字或下划线。看起来熟悉吗？它与Perl的\w定义非常相似，但它不允许以数字开头。实际上，DOT在某些情况下禁止它们（但在某些情况下允许纯数字）。
所有这些手工编写的正则表达式的结果是什么？它们被输入到DFA中，与输入流一起。DFA的输出是一个标志，表示是或否，输入流与指定的正则表达式定义的标记匹配或不匹配。在这个过程中，每当DFA识别到一个标记时，它会调用回调函数，并将它们存储起来。运行结束后，你可以将它们输出为一个标记流，每个标记都有一个标识类型，正如我之前描述的词法分析器的任务描述。
关于回调的注意事项：有时设计一个捕获比看起来更合适的内容的正则表达式更容易，然后使用回调中的代码将其分割成多个捕获，从而输出多个标记元素。
因为开发状态转换表是一个迭代过程，我建议创建各种测试文件，包括各种示例程序，以及具有非常简短名称的脚本来运行测试（名称简短，因为你将无数次地运行这些脚本……）。
状态
什么是状态？为什么你应该关心它们？
在任何时刻，STT（自动化，软件机器）都处于一个精确的开启状态。也许它还没有接收到任何一个标记（因此它处于起始状态），或者也许它刚刚处理完前一个标记。无论如何，代码保持信息以便知道它确切处于什么状态，这有助于知道现在可以接受哪些标记集合。也就是说，它有一个标记集合，其中任何一个在当前状态下都是合法的。
这意味着：你必须将每个正则表达式与一个特定的状态相关联，反之亦然。此外，只要每个新的输入字符匹配属于当前状态的正则表达式，机器将保持其当前状态。当该字符不匹配时，它会跳转（进行转换）到新状态。
示例词法分析器代码
考虑以下来自Set::FA::Element摘要的简单代码
my($dfa) = Set::FA::Element -> new
(
accepting => ['baz'],
start => 'foo',
transitions =>
[
['foo', 'b', 'bar'],
['foo', '.', 'foo'],
['bar', 'a', 'foo'],
['bar', 'b', 'bar'],
['bar', 'c', 'baz'],
['baz', '.', 'baz'],
],
);
在transitions参数中，第一行说：“foo”是一个状态名称，“b”是一个正则表达式。如果下一个输入字符匹配该正则表达式，则跳转到状态“bar”。其他行类似。
要使用Set::FA::Element，你必须准备一个与此格式匹配的转换参数。现在你看到了状态和正则表达式的需求。
这是我从GraphViz2::Marpa::Lexer::DFA直接使用的代码
Set::FA::Element -> new
(
accepting => \@accept,
actions => \%actions,
die_on_loop => 1,
logger => $self -> logger,
start => $self -> start,
transitions => \@transitions,
verbose => $self -> verbose,
);
让我们讨论这些参数。
accepting 这是一个状态名称的数组引用。在处理整个输入流后，如果机器最终处于这些状态之一，则它已接受该输入流。这意味着每个输入标记都与适当的正则表达式匹配，其中“适当”意味着每个字符都匹配当前状态的正则表达式，无论该字符输入时状态如何。
actions 这是一个函数名称的散列引用，以便机器可以在进入或离开任何状态时调用函数（可选）。这就是识别标记的堆栈是如何工作的。
因为我自己编写了这些函数，并编写了将每个函数附加到特定状态和正则表达式组合的规则，所以我在每个函数中编码了DFA已匹配的标记类型的知识。这就是为什么堆栈最终会以（标记，类型）对的形式输出，在运行结束后。
die_on_loop 如果此标志为真，则告诉DFA如果当前状态的所有正则表达式都不匹配当前输入字符，则停止。而不是无限循环，停止并抛出异常。
你可能想知道为什么自动停止不是默认的，甚至不是强制的。默认行为允许你在程序崩溃之前尝试从这种不良状态中恢复，或者至少显示一个合理的错误信息。
logger 这是一个（可选的）记录对象。
start 这是STT开始时的状态名称，因此代码知道在接收到第一个输入字符时尝试哪个正则表达式。
transitions 这是一个可能很大的数组引用，它分别列出所有状态可能匹配的当前输入字符的所有正则表达式。
verbose 如果未定义记录对象，指定要报告多少信息。
在配置了所有这些之后，下一个问题是如何将语法准备成适合这个参数列表的形式。
编码词法分析器 - 再访
因此，编码者需要开发可以直接输入所选DFA（例如 Set::FA::Element）或以某种方式转换成该模块可接受的格式的正则表达式等。到目前为止，我还没有实际说明我是如何做到这一点的，但现在该明确说明了。
我使用一个有九列的电子表格
Start 这包含一个单词，“Yes”，对应于起始状态的状态名称。
Accept 这包含单词“Yes”，对应于任何将成为接受状态（机器已匹配输入流）的状态名称。
State 这是状态名称。
Event 这是一个正则表达式。如果当前输入字符匹配此正则表达式，则事件将触发。
因为正则表达式属于给定的状态，我们知道DFA只会处理与当前状态关联的正则表达式，通常只有一个或最多几个。
当每个状态有多个正则表达式时，我留下所有其他列都是空的。
Next 如果当前字符匹配同一行电子表格（当然是在当前状态下）的正则表达式，STT将跳转到“下一个”状态的名称。
Entry 可选的函数名称，DFA在进入（新）状态之前将调用它。
Exit 可选的函数名称，DFA在离开当前状态时将调用它。
Regexp 这是一个工作列，我在其中放置公式，以便在事件列的各个地方引用它们。它不传递给DFA的转换参数。
Interpretation 对自己的注释。
我已经将STT for GraphViz2::Marpa的STT放在线上了。
这个电子表格有各种优点
可读性。 它非常易于阅读和处理。别忘了，一开始你基本上会在语法定义文档（希望是BNF）和这个电子表格之间切换。在这个阶段，我实际上没有进行多少（任何）编码。
可导出性。 因为我还没有代码，有几个可能性。我可以直接读取电子表格。这种方法有两个问题：外部模块（读取代码）的复杂性，以及加载和运行此代码的缓慢。
因为我使用LibreOffice，我可以强制最终用户安装OpenOffice::OODoc，或者将电子表格导出为Excel文件，以便他们可以利用这个选项。我选择不支持在模块（Graph::Easy::Marpa 和 GraphViz2::Marpa）中直接读取.ods文件。
我可以选择先导出电子表格到一个CSV文件。这样我们就可以相当快速地将CSV文件读入DFA中，而不需要加载读取电子表格的模块。在这里要注意LibreOffice，因为它强制你使用Unicode来存储电子表格，但导出时会出现一些奇特的字符序列，比如双引号会被导出为三个字节的序列0xe2, 0x80, 0x9c。当在正则表达式中使用时，这个序列永远不会匹配输入流中的真实双引号。唉。勿作恶。如果可能的话。
我还可以直接将电子表格集成到我的代码中。这是我最喜欢的方法。我分两个阶段做这件事。首先将我的数据导出到一个CSV文件中，然后将该文件附加到模块源代码的末尾，在__DATA__标记之后。
这种内联数据可以轻松地被非常 neat 和非常快速的模块 Data::Section::Simple 访问。因为Perl已经加载了这个模块，并且正在执行它，所以在其中读取数据时几乎没有开销。难道你不爱Perl！还有MetaCPAN当然。还有贡献这样神奇代码的社区。
这种替代方案的优点是它允许最终用户在修改了内置的.csv或.ods文件后，可以使用脚本的命令行选项来读取自己的文件，覆盖内置的STT。
经过这一切之后，剩下的就是代码来读取和验证STT数据结构，然后将其重新格式化为Set::FA::Element所要求的格式。
编写解析器
到这个阶段，你已经知道如何将第一个子语法集成到词法分析器的设计和代码中。你也知道第二个子语法必须编码到解析器中，因为解析器就是这样执行语法检查的。
你如何做这取决于你选择哪个预存的模块来帮助解析器的开发。因为选择了Marpa（目前是Marpa::R2），所以这篇文章将针对这个模块进行说明。然而，只有在下一篇文章中，我才会深入探讨Marpa。
无论你选择哪个工具，都要将解析过程想象成这样：你的输入流是一组预定义的标记（可能是词法分析器的输出）。现在你必须指定所有可能的合法标记组合。这是语言的语法（或者更准确地说，剩余的语法，因为第一个子语法已经处理了所有合法标记的定义）。在这个阶段，假设所有传入的标记都是合法的。换句话说，解析器不会尝试解析和运行包含基于标记的语法错误的程序，尽管它可能包含逻辑错误（即使是用Perl编写的 :-））。
任何不匹配给定合法组合的标记组合都可以立即被拒绝为语法错误。记住，最友好的编译器会尽可能在每次解析中找到尽可能多的语法错误。
因为这个检查是在标记一级进行的，所以你（应该）确切地知道哪个标记触发了错误，这意味着你可以发出一个很好的错误信息，指出元凶及其上下文。
示例解析器代码
这里是一个Marpa::R2语法的示例（从其简介中改编）
my($grammar) = Marpa::R2::Grammar -> new
({
actions => 'My_Actions',
start => 'Expression',
rules =>
[
{ lhs => 'Expression', rhs => [qw/Term/] },
{ lhs => 'Term', rhs => [qw/Factor/] },
{ lhs => 'Factor', rhs => [qw/Number/] },
{ lhs => 'Term', rhs => [qw/Term Add Term/],
action => 'do_add'
},
{ lhs => 'Factor', rhs => [qw/Factor Multiply Factor/],
action => 'do_multiply'
},
],
default_action => 'do_something',
});
尽管这与词法分析器示例中的Set::FA::Element -> new()调用之间存在差异，但这两个片段基本上是相同的
actions 这是Marpa将查找的动作所在的Perl包的名称，例如do_add()和do_multiply()。（好吧，词法分析器没有这样的选项，因为它默认为当前包。）
start 这是要开始的规则的lhs名称，就像在词法分析器中一样。
规则 这是一个语法规则的数组引用，它定义了语法的语法。这是词法分析器的 转换 参数。
默认行为 使用这个（可选）回调作为任何未明确指定其自己行为的规则元素的执行行为。
真正的问题是，如何将BNF或其他形式的语法转换成一组 规则描述符。你怎么看待这个问题？我建议将实际代码与语法描述进行对比。
这是之前解释过的 teamwork.dot 文件。
digraph Perl
{
graph [ rankdir="LR" ]
node [ fontsize="12pt" shape="rectangle" style="filled, solid" ]
edge [ color="grey" ]
"Teamwork" [ fillcolor="yellow" ]
"Victory" [ fillcolor="red" ]
"Teamwork" -> "Victory" [ label="is the key to" ]
}
一般来说，一个有效的 Graphviz (DOT) 图必须以以下之一开始
strict digraph $id {...} # Case 1. $id is a variable.
strict digraph {...}
strict graph $id {...} # Case 3
strict graph {...}
digraph $id {...} # Case 5
digraph {...}
graph $id {...} # Case 7
graph {...}
… 正如实际代码所示。图的ID是 Perl，这是第5种情况。如果你曾经注意到你可以将BNF写成一棵树（对吧？），那么你可以猜到接下来会发生什么。我喜欢从根向下编写我的 规则描述符。
将这个图作为树绘制给出
DOT's Grammar
|
V
---------------------
| |
strict |
| |
---------------------
|
V
---------------------
| |
digraph or graph
| |
---------------------
|
V
---------------------
| |
$id |
| |
---------------------
|
V
{...}
将解析器连接回词法分析器
等等，这是什么？我没有说过 strict 是可选的吗。在解析器中，它不是可选的。在DOT语言中它是可选的，但我设计了词法分析器，并确保在图的作者省略了 strict 时，它必须输出 strict => no。
到解析器运行时，strict 就不再是可选的了。我这样做是为了让词法分析器输出流的消费者（例如解析器作者）的生活更轻松。（让解析器工作更少通常是件好事。）
同样，对于 digraph 'v' graph，我设计了词法分析器在一种情况下输出 digraph => 'yes'，在另一种情况下输出 digraph => 'no'。这意味着什么？对于 teamwork.dot，词法分析器将以（某种方便的格式）输出等效于
strict => no
digraph => yes
graph_id => Perl
...
我选择 graph_id 是因为DOT语言允许其他类型的ID，如节点、边、端口和方向。
所有这些产生前六个Marpa友好的规则
[
{ # Root-level stuff.
lhs => 'graph_grammar',
rhs => [qw/prolog_and_graph/],
},
{
lhs => 'prolog_and_graph',
rhs => [qw/prolog_definition graph_sequence_definition/],
},
{ # Prolog stuff.
lhs => 'prolog_definition',
rhs => [qw/strict_definition digraph_definition graph_id_definition/],
},
{
lhs => 'strict_definition',
rhs => [qw/strict/],
action => 'strict', # <== Callback.
},
{
lhs => 'digraph_definition',
rhs => [qw/digraph/],
action => 'digraph', # <== Callback.
},
{
lhs => 'graph_id_definition',
rhs => [qw/graph_id/],
action => 'graph_id', # <== Callback.
},
...
]
用英语来说，所有这些断言整个图由一个序言部分和一个图序列部分组成。（记住，我创造了prolog_and_graph等名称。)
接下来，序言由一个strict部分组成，现在不再是可选的，然后是一个digraph部分，它将匹配词法分析器的输入/^(di|)graph$/，以及词法分析器的输出digraph => /^(yes|no)$/，然后是一个可选的graph_id，然后是其他一些东西，这将精确地定义真实存在的图，在序言的八种可能格式列表中以{...}表示。
哇。
关于规则描述符的有趣之处
再看看那些规则描述符。它们对标记的值什么也没说！例如，在graph_id => Perl中，对于像Perl这样的ID会发生什么。什么也没有。它们被忽略。这就是这些语法的运作方式。
回想一下：词法分析器的任务是根据第一个子语法来识别有效的图ID。当数据到达解析器时，我们知道我们有一个有效的图ID，只要它正确地插入到语法的结构中，我们就准备好接受任何有效的图ID。因此，Marpa::R2甚至不会查看图ID，这意味着这个语法可以与每个有效的图ID一起工作。
这一点也引发了关于特定的lexer/parser代码实现是否可以或必须将两个阶段分开，或者实际上是否可以将它们合并在一起而不陷入过早优化的陷阱的棘手讨论。我将对此讨论只字不提，因为我已经宣布了我的立场：我的实现使用两个独立的模块。
链和树
如果这些规则必须链接到一个树中，您如何处理根？考虑对Marpa::R2的new()方法的这个调用。
my($grammar) = Marpa::R2::Grammar -> new(... start => 'graph_grammar', ...);
graph_grammar正好是第一个规则描述符中的lhs。
之后，每个规则的rhs，包括根的，必须在规则描述符列表的后面定义。这些定义形成了链中的链接。如果您画出这个，您会看到最终结果是树。
这是DOT的完整Marpa::R2语法（如GraphViz2::Marpa模块中使用）的图像：[http://savage.net.au/Ron/html/graphviz2.marpa/Marpa.Grammar.svg](http://savage.net.au/Ron/html/graphviz2.marpa/Marpa.Grammar.svg)。我使用Graphviz和GraphViz2创建了此图像。我在树中的节点名称中添加了数字，否则Graphviz会将任何两个无数字的相同名称视为同一个节点。
少写代码，多设计
在这里，我将停止构建语法的树（见下一篇文章），并转向一些设计问题。
我编写词法分析器/解析器的经验法则
本文件的其余部分旨在帮助初学者在面对他们还不熟悉的难题时调整自己的思维。当然，如果您是词法分析和解析的专家，您可以自由忽略我说的一切，如果您认为我在这里误用了词法分析/解析术语，请告诉我。
避免过早优化
是的，又是这个老问题。它有多种含义。
词法分析和解析器
不要试图将词法分析器和解析器结合在一起，即使它们最终可能会这样做。请在尝试将它们压缩到单个模块（或程序）中之前，等待每个设计都清晰并最终确定。
词法分析和标记
让词法分析器识别标记的存在，但不要识别它们的最终角色或含义。
词法分析和上下文
不要让词法分析器进行上下文分析。通过使用上下文让解析器通过上下文消除具有多种含义的标记的歧义。让词法分析器做识别标记的艰难工作。
例如，对于商业上下文分析，可能也不是您想要的。
词法分析和语法
不要让词法分析器进行语法检查。这实际上与上一个论点相同。
词法分析和其输出
不要最小化词法分析器的输出流。例如，不要迫使读取词法分析器输出代码猜测一个变长标记集是否结束。输出一个特定的标记作为集合终止符。这个标记的目的就是告诉解析器发生了什么。没有这样的标记，下一个标记必须承担双重任务：首先告诉解析器变长部分已结束，其次，它代表自己。这种过度加载是不必要的。
状态转换表
在STT中，不要试图最小化状态的数量，至少在代码稳定（即，不再处于[快速]开发中）之前不要这样做。
我在电子表格程序中开发我的STT，这意味着一个单元格中存储的公式（正则表达式）可以被任意数量的其他单元格引用。这非常方便。
分而治之
嗯，另一个古老的格言。当然，这些格言之所以持久，正是因为它们告诉我们一些重要的东西。在这里，这意味着仔细研究问题，并分别处理其每个部分（词法分析器，解析器）。就这么多。
不要重复造轮子
是的，我知道您绝不会这样做。
CPAN上有许多Perl模块可以帮助处理STT等事情，例如Set::FA::Element。检查其“参见”（实际上在Set::FA中）以获取其他STT辅助工具。
对STT要有耐心
开发STT需要许多迭代
测试用例
每次迭代，准备一个单独的测试用例。
小型脚本
有一个运行单个测试的小型脚本。给它一个简短——可能暂时——的名字，使得每个测试都更容易运行。你可以在将其包含到发行版中时给它一个有意义的名字。
包装脚本
有一个运行所有测试的脚本。
我把测试数据文件放在data/目录下，脚本放在scripts/目录下。然后，在t/目录下创建测试可能可以使用这两组助手。
因为我只使用了Marpa::R2进行图形工作，所以包装脚本的输出是一个网页，这使得查看结果变得简单。我喜欢在网页上包含（简短）输入或输出文本文件，旁边是SVG图像。这样我就可以一目了然地看到输入是什么，因此我可以在不切换到编辑器窗口的情况下告诉输出应该是什么。
最初需要一点努力，但之后检查最新测试的输出就非常容易了。
我已经提供了包装脚本示例输出
对语法要有耐心
与STT一样，创建语法至少对我来说是一个非常试错的过程。我提供一些建议
建议
纸张，而非代码
一个好主意是不要从编辑器开始编码，而是将语法作为树状图在纸上绘制。
注意备选方案
这指的是当输入流中可以出现几个标记中的一个时。学会如何绘制它，而不要试图最小化树中的分支数量。
当然，你仍然需要学习如何编写这样的结构。以下是从Graph::Easy::Marpa中获取的一小段代码，用于处理这个问题（注意：从现在开始我们将回到
Graph::Easy语言！）{ # Graph stuff. lhs => 'graph_definition', rhs => [qw/graph_statement/], }, { lhs => 'graph_statement', # 1 of 3. rhs => [qw/group_definition/], }, { lhs => 'graph_statement', # 2 of 3. rhs => [qw/node_definition/], }, { lhs => 'graph_statement', # 3 of 3. rhs => [qw/edge_definition/], },这告诉您，一个图形元素可以是组、节点或边中的任何一个。这是Marpa::R2的任务，尝试这些备选方案，以查看哪些（如果有的话）与输入流匹配。这个规则集表示输入流中的一个点，在该点可能出现几个备选方案。
树看起来像
graph_definition | V graph_statement | V --------------------------------------- | | | V V V group_definition node_definition edge_definition我的注释
3 of 3表示边可以独立存在。注意序列
…但考虑节点定义
{ # Node stuff. lhs => 'node_definition', rhs => [qw/node_sequence/], min => 0, }, { lhs => 'node_sequence', # 1 of 4. rhs => [qw/node_statement/], }, { lhs => 'node_sequence', # 2 of 4. rhs => [qw/node_statement daisy_chain_node/], }, { lhs => 'node_sequence', # 3 of 4. rhs => [qw/node_statement edge_definition/], }, { lhs => 'node_sequence', # 4 of 4. rhs => [qw/node_statement group_definition/], },在这里
3 of 4告诉您节点可以后面跟着边。一个现实的例子是：
[node_1] -> [node_2]，其中[x]是一个节点，->是一个边，因为边可以后面跟着一个节点（应用3 of 4）。这个完整的例子代表输入流中的一个点，在该点允许/期望出现几个特定的序列标记。以下是边定义
{ # Edge stuff. lhs => 'edge_definition', rhs => [qw/edge_sequence/], min => 0, }, { lhs => 'edge_sequence', # 1 of 4. rhs => [qw/edge_statement/], }, { lhs => 'edge_sequence', # 2 of 4. rhs => [qw/edge_statement daisy_chain_edge/], }, { lhs => 'edge_sequence', # 3 of 4. rhs => [qw/edge_statement node_definition/], }, { lhs => 'edge_sequence', # 4 of 4. rhs => [qw/edge_statement group_definition/], }, { lhs => 'edge_statement', rhs => [qw/edge_name attribute_definition/], }, { lhs => 'edge_name', rhs => [qw/edge_id/], action => 'edge_id', },
但我必须停下来，所以…
总结和收尾
我希望我已经阐明了编程中可能复杂和令人望而生畏的部分，并且我也希望我已经说服你，使用电子表格辅助的Perl是现代（或“唯一”）达到词法分析和解析幸福的途径。
Ron Savage是一位长期从事Perl编程并大量贡献CPAN的贡献者。
标签
反馈
这篇文章有什么问题吗？请通过在GitHub上打开一个问题或拉取请求来帮助我们。
