正则表达式之外:解析上下文无关语法的简介

2020年12月13日15:52:12 发表评论 144 次浏览

克里斯托弗·迪金斯(Christopher Diggins)

正则表达式之外:解析上下文无关语法的简介1

摄影者

约翰尼斯·普莱尼奥

on

不飞溅

可信赖的工具已经成为大多数程序员的一部分, 它是一种重要而有用的工具正则表达式.但是除此之外, 还没有上下文无关的语法。这是一个简单的概念, 名字很漂亮。

正则表达式是一种验证和查找文本模式的方法。可以使用正则表达式描述和检测的模式类型(又名语法)称为常规语言。常规语言是形式语言中最简单的形式语言乔姆斯基阶层.

正则表达式非常适合查找或验证许多类型的简单模式, 例如电话号码, 电子邮件地址和URL。但是, 当将它们应用于可以具有递归结构的模式时, 它们就不够用了, 例如:

  • HTML / XML打开/关闭标签
  • 用编程语言打开/关闭大括号{/}
  • 在算术表达式中打开/关闭括号

要解析这些类型的模式, 我们需要更强大的功能。我们可以进入下一个形式的正式语法上下文无关文法(CFG)。

解析数学表达式

解析所有数学表达式的集合超出了真正正则表达式的能力。原因是它们可以包含任意深的嵌套括号对。

例如, 考虑以下表达式:(2 +(3 *(7–4)))

请注意, 算术表达式的结构实际上是一棵树:

+ / \ 2   *   / \  3   -     / \     7 4

运行CFG解析器而生成的树结构称为a解析树.

描述无上下文语法

表达CFG语法有两种流行的方法:

  1. 扩展的Bachus-Naur形式(EBNF)-从以下方面描述CFG:生产规则。这些规则在应用时可以生成该语言中所有可能的合法短语。
  2. 解析表达语法(PEG)-用以下术语描述CFG:识别规则。这些规则可用于匹配语言中的有效短语。

与EBNF相比, PEG形式主义具有一个优势, 即到解析器的映射是明确的, 并且可以轻松实现自动化。

以下是一个简单的PEG

从其维基百科解除

此页面描述了将基本四个运算应用于非负数的数学公式

整数。

Expr ← SumSum ← Product ((‘+’ / ‘-’) Product)*Product ← Value ((‘*’ / ‘/’) Value)*Value ← [0–9]+ / ‘(‘ Expr ‘)’

用简单的英语来说, 我们可以这样读:

  • Expr是一个和
  • 和是一个产品随后是零个或多个由" +"或"-"组成的子模式, 后跟一个产品
  • 产品是一个值后跟零个或多个由" *"或" /"组成的子模式, 后跟一个值
  • 值是字符集{0, .. 9}的一个或多个成员, 或者是一个开放的括号"(", 后跟一个Expr和右括号")"。

解析器生成器与解析库

假设你不是那种喜欢重新发明轮子的人(并不是说这有什么问题), 通常有两种创建解析器的选择:

1.使用解析器生成器—从解析器的抽象定义生成解析器源代码的工具。 JavaScript中的一些流行示例包括吉森, 聚乙二醇, Nearley和ANTLR.

2.使用解析库—一个库, 它允许将解析规则表达为API。 JavaScript中的一些示例包括八哥, 柿子和雪佛兰.

我更喜欢使用解析库, 因为它们更易于理解, 调试, 维护和自定义。

使用TypeScript / JavaScript编写解析器八哥解析库

正则表达式之外:解析上下文无关语法的简介2

八哥

来自Wikimedia Commons的y Mahesh Iyer

最近, 我正在从事的一个项目(苍鹭语言)需要可以在浏览器中运行的解析库。我发现现有库的复杂性和开销太大。考虑到我以前在C ++和C#中编写解析库的经验, 我决定编写一个解析器库称为八哥使用TypeScript.

八哥用途流利的语法(方法链接)轻松将解析器定义为类似于PEG语法的一组规则(子解析器)。

下面的例子是来自Myna GitHub存储库:

从具体语法树(CST)到抽象语法树(AST)

当解析器处理输入时, 每个成功匹配的规则(即语法产生)都可以映射到解析树中的一个节点。生产规则到树中节点的字面映射是具体语法树(CST)。

在某些情况下, CST用途有限, 因为它包含许多语法混乱, 例如源代码中的注释, 或者字符串文字是带双引号还是单引号。它可能包含规则创建的结果, 这些规则的创建是为了使语法更易于使用, 但并不表示要进行分析的预期树结构。

最简单的操作是仅在输出树中为特定规则创建节点, 并跳过其他规则。解析树的简化版本称为抽象语法树(AST)。可能会对AST执行多次处理, 以将其转换为其他AST表示形式, 以简化后续处理步骤。

在Myna中, 通过根据标记为AST属性。从技术上讲, 此属性返回一个新规则, 该规则具有一个内部属性集, 该属性集告诉解析器在解析树中生成一个解析节点。

使用生成的Myna抽象语法树

这是在" Node.JS"中使用Myna定义的解析器来评估算术表达式的示例:

最后的话

如果你想了解有关创建和使用解析器的更多信息, 无论Myna库是否满足你的特定需求, 我建议你花一些时间通读Myna解析库的源代码.

Myna用TypeScript编写(对于大多数程序员来说, 语法都很熟悉), 包含在没有依赖性的单个文件中, 并且少于1200行, 包括详细的文档。

如果你有兴趣了解Myna应用于更复杂的场景, 请查看山雀编程语言。这完全在TypeScript中实现, 并且仅取决于八哥解析库。 Chickadee是一种微小的编程语言, 专门用于帮助人们学习实现编程语言的技术。

如果你喜欢这篇文章, 请告诉我, 并考虑与你的朋友和同事分享。

一盏木

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: