NLP|自然语言处理-语法解析指南：算法和技术（第5部分）-控件新闻-慧都网

NLP|自然语言处理-语法解析指南：算法和技术（第5部分）

原创|使用教程|编辑：郑恭琳|2018-01-04 13:14:28.000|阅读 955 次

概述：语法有两种主要格式：BNF（及其变体）和PEG。本章节旨在让大家了解这些不同的格式以及何时应该使用它们。

# 慧都年终大促·界面/图表报表/文档/IDE等千款热门软控件火热促销中 >>

格式

语法有两种主要格式：BNF（及其变体）和PEG。许多工具都实现了这些理想格式的变体。一些工具完全使用自定义格式。频繁的自定义格式由三部分语法组成：结合自定义代码的选项，其次是词法分析部分，最后是解析器部分。

鉴于类似BNF的格式通常是上下文无关语法的基础，您还可以看到它以CFG格式标识。

Backus-Naur Form及其变体

Backus-Naur Form（BNF）是最成功的格式，甚至是PEG的基础。但是，这个过程很简单，因此它的基本形式并不常用。我们通常使用更强大的变体。

为了说明为什么这些变体是必要的，我们来展示一个BNF的例子：一个字符的描述。

< letter >    ::= "a" | "b" | "c" | "d" | "e" | "f" | "g" | "h" | "i" | "j" | "k" | "l" | "m" | "n" | "o" | "p" | "q" | "r" | "s" | "t" | "u" | "v" | "w" | "x" | "y" | "z"
< digit >     ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
< character > ::= < letter > | < digit >

符号< letter >可以在英文字母的任何字母中转换，尽管在我们的例子中只有小写字母是有效的。类似的过程发生在< digit >，它可以指示任何替代数字。第一个问题是你必须单独列出所有的选择；像使用正则表达式一样，不能使用字符类。这很烦人，但通常是可以管理的，除非你必须列出所有的Unicode字符。

一个更难的问题是，没有简单的方法来表示可选的元素或重复。所以，如果你想这样做，你必须依靠布尔逻辑（boolean logic）和替代(|)符号。

< text >      ::= < character > | < text > < character >

该规则规定< text >可以由一个字符或一个短的< text >和一个< character >组成。这将是dog的分析树：

BNF还有许多其他限制：在语法中使用空字符串或格式使用的符号（即:: =）使得复杂，它有一个详细的语法（即你必须在< and >之间包含终端）等等。

Extended Backus-Naur Form

为了解决这些限制，Niklaus Wirth创建了Extended Backus-Naur Form(EBNF)，其中包含了他自己的Wirth语法表示法的一些概念。

EBNF是最常用的当代解析工具，尽管工具可能偏离标准符号。EBNF有一个更清洁的符号，并采用更多的运算符来处理连接或可选的元素。

我们来看看如何在EBNF中编写前面的例子。

letter    = "a" | "b" | "c" | "d" | "e" | "f" | "g" | "h" | "i" | "j" | "k" | "l" | "m" | "n" | "o" | "p" | "q" | "r" | "s" | "t" | "u" | "v" | "w" | "x" | "y" | "z" ;
digit     = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;
character = letter | digit ;
text      = character , { character } ;

文字符号在连接运算符（，）和可选符号（{..}）的帮助下更容易描述。得到的分析树也会更简单。标准的EBNF仍然存在一些问题，如不熟悉的语法。为了克服这个问题，大多数解析工具都采用了受正则表达式启发的语法，并且还支持像字符类这样的附加元素。

ABNF

Augmented BNF (ABNF)是BNF的另一种变体，主要用于描述双向通信协议，并由IETF和几个文档（参见和更新）进行形式化。

ABNF可以和EBNF一样有效，但是有一些怪癖限制了它在互联网协议之外的采用。例如，直到最近，标准规定字符串以不区分大小写的方式进行匹配，这在许多编程语言中匹配标识符是个问题。

ABNF与EBNF有不同的语法；例如，替代运算符是斜杠（/），有时它更好。例如，不需要连接运算符。它还比标准的EBNF有更多的东西。例如，它允许您定义数字范围，如％x30-39，相当于[0-9]。这也被设计师自己用来包含标准的字符类，比如最终用户可以使用的基本规则。这种规则的一个例子是ALPHA，相当于[a-zA-Z]。

PEG

解析表达语法（PEG）是。从技术上讲，它来源于一种称为自顶向下解析语言（Top-Down Parsing Language，TDPL）的旧式正式语法。然而，描述它的一个简单的方法是在现实世界中的EBNF。

实际上，它看起来和EBNF相似，但也直接支持广泛使用的东西，比如字符范围（字符类）——虽然它也有一些实际上并不那么实际的差异，比如使用更正式的箭头符号（←）更常见的等号（=）。前面的例子可以用PEG来写。

letter    ← [a-z]
digit     ← [0-9]
character ← letter / digit
text      ← character+

正如你所看到的，这是程序员写的最明显的方式：用字符类和正则表达式运算符。唯一的异常是替代运算符（/）和箭头字符，事实上，PEG的许多实现使用“equals”字符。

实用的方法是PEG形式化的基础：创建它是为了描述更自然的编程语言。这是因为上下文无关文法起源于描述自然语言的工作。从理论上讲，CFG是一个生成语法，而PEG是一个分析语法。

第一个应该是用语法描述的语言只生成有效句子的一种配方。它不必与解析算法相关。相反，第二种类型直接定义了该语言的解析器的结构和语义。

PEG与CFG

这种理论差异的实际意义是有限的：PEG与packrat算法更密切相关，但基本上这是它。例如，一般来说，PEG（packrat）不允许左递归。虽然可以修改算法本身来支持它，但是这消除了线性时间解析属性。另外，PEG解析器通常是无扫描器的解析器。

PEG和CFG之间最重要的区别可能是PEG的选择顺序是有意义的，而CFG则不是。如果有许多可能的有效方法来解析输入，则CFG将不明确，因此将返回错误。通常错误的意思是，一些采用CFG的解析器可以处理模糊的语法；例如，向开发者提供所有可能的有效结果，并让他们把它整理出来。相反，由于第一个适用的选择将被选择，PEG完全消除了歧义。因此，PEG永远不会含糊不清。

这种方法的缺点是，在列出可能的备选方案时必须更加小心，否则可能会产生意想不到的后果。也就是说，有些选择永远无法匹配。

在下面的例子中，doge永远不会被匹配。由于dog先来，它每次都会被挑选。