NLP|自然语言处理-语法解析指南:算法和技术(第1部分)

使用教程 | 作者:Elyn | 2017-12-28 14:14:59| 阅读 0 有用 (0) 评论 (0) 收藏


概述:语法解析这个系列文章总共有9个部分,在第1部分中,我们将学习正则表达式的语法,解析器的结构以及什么是无扫描解析器。

当我们列出用于Java、C#、Python和JavaScript解析的主要工具和库时,我们已经介绍了一些解析术语(需要这些方面文章资源的同学可以联系Elyn获取哦)。在本文中,我们将更深入地介绍解析中使用的概念和算法,以便您更好地理解这个迷人的世界。

在这篇文章中我们试图做到实用。我们的目标是帮助从业者,而不是解释完整的理论。我们只解释你需要知道的知识来理解和构建解析器。

语法解析的定义

语法解析被定义为“根据语法规则组织数据的输入分析”。

有几种方法来定义解析。然而,要点仍然是一样的:解析意味着找到我们给出的数据的底层结构

解析的简单定义

从某种意义上说,解析可以被认为是模板的逆过程:识别结构并提取数据。在模板中,我们有一个结构,并填充数据。在解析的情况下,您必须从原始表达中确定模型,而对于模板,则必须将数据与模型结合以创建原始表达。原始表达通常是文本,但也可以是二进制数据。

从根本上讲,解析是必要的,因为不同的实体需要不同形式的数据。解析允许以特定软件可以理解的方式来转换数据。一个明显的例子就是程序——它们是由人类编写的,但是它们必须由计算机来执行。所以,人们用一种他们能理解的形式写出来,然后一个软件以一种可以被计算机使用的方式来转换它们。

但是,即使在两个具有不同需求的软件之间传递数据时,解析也是必要的。例如,当你需要序列化或反序列化一个类时,就需要它。

大蓝景

关于解析的文本的大蓝景

在本节中,我们将描述解析器的基本组件。我们不是要给你正式的解释,而是实际的解释。

常用表达

正则表达式是可以由模式定义的一系列字符

正则表达式经常被吹捧为你不应该用来解析的东西。这是不正确的,因为你可以使用正则表达式来解析简单的输入。问题是一些程序员只知道正则表达式,所以他们用它们来解析所有的东西——甚至是他们不应该解析的东西。其结果通常是一系列非常脆弱的正则表达式一起被入侵。

您可以使用正则表达式来解析一些更简单的语言,但是这排除了大多数编程语言——甚至是那些看起来很简单的编程语言,比如HTML。事实上,可以用正则表达式解析的语言称为常规语言。它有一个正式的数学定义,但超出了本文的范围。

该理论的一个重要结果是常规语言也可以被有限状态机(finite state machine)解析或表达。也就是说,正则表达式和有限状态机同样强大。这就是他们被用来实现词法分析器的原因,我们将在后面看到。

常规语言可以由一系列正则表达式来定义,而更复杂的语言则需要更多的东西。一个简单的经验法则是,如果语言的语法具有递归或嵌套的元素,那么它就不是一种常规的语言。例如,HTML可以在任何标签内包含任意数量的标签;因此,它不是一个普通的语言,不管它是多么的巧妙,都不能用正则表达式来解析。

正则表达式语法

典型程序员对正则表达式的熟悉使他们经常被用来定义语言的语法。更确切地说,它们的语法被用来定义词法分析器或分析器的规则。例如,在一个规则中使用Kleene星号(* Kleene star)来表示一个特定元素可以呈现为零或无限次数。

该规则的定义不应与实际的词法分析器或分析器如何实现相混淆。您可以使用您的语言提供的正则表达式引擎来实现词法分析器。但是通常,语法中定义的正则表达式被实际转换为有限状态机来获得更好的性能。

解析器的结构

澄清了正则表达式的作用之后,我们可以看一下解析器的一般结构。完整的解析器通常由两部分组成:词法分析器,也称为扫描器或标记器,以及正确的解析器。解析器需要词法分析器,因为它不直接在文本上工作,而是在词法分析器产生的输出上。并不是所有的解析器都采用这个两步模式。一些解析器不依赖于单独的词法分析器,而是将两个步骤结合起来。 他们被称为无扫描程序分析器。

词法分析器和解析器按顺序工作:词法分析器扫描输入并生成匹配的tokens;解析器然后扫描tokens并产生解析结果。

让我们看看下面的例子,想象我们正试图解析加法。

437 + 734

词法分析器扫描文本并找到4、3和7,然后找到一个空格( )。 词法分析器的工作是识别字符437构成NUM类型的一个token。然后词法分析器找到一个+符号,它对应于PLUS类型的第二个token,最后找到另一个类型为NUM的token。

输入流在Tokens中被转换,然后在解析器中被转换成AST

解析器通常会组合词法分析器生成的token并对它们进行分组。

词法分析器和解析器使用的定义称为规则或产品。在我们的例子中,词法分析器规则将指定一个数字序列对应于NUM类型的token,而解析器规则将指定类型NUMPLUSNUM的token序列对应于一个求和sum表达式。

现在通常找到可以生成词法分析器和解析器的套件。过去,结合两种不同的工具比较常见:一种是生成词法分析器,另一种是生成解析器。例如,这是一个古老的lex和yacc共同使用的情况:使用lex,可以生成一个词法分析器,而使用yacc时,可以生成一个解析器。

无扫描解析器

无扫描器解析器的操作方式不同,因为它们直接处理原始文本,而不处理由词法分析器生成的tokens列表。也就是说,一个无扫描解析器就像一个词法分析器和一个解析器结合在一起。

虽然知道调试的目的,如果一个特定的分析工具是一个无扫描程序的分析器是非常重要的,但在很多情况下,定义一个语法是没有意义的。这是因为你通常还是定义了组合字符序列的模式来创建(虚拟)tokens;然后,你将它们结合起来,以获得最终结果。只是因为这样做更方便。换句话说,无扫描程序的语法分析器的语法看起来与具有单独步骤的工具非常相似。再次,你不应该为了方便而混淆事物是如何定义的,以及它是如何在幕后工作的。

请继续关注第2部分——我们将详细讨论解析器和语法。

本文原作者:Gabriele Tomassetti
翻译:Elyn

推荐阅读:
展望2018年:基于AI人工智能的移动应用程序开发将如何发展
开发一个聊天机器人(Chatbot)应用程序需要花费多少钱?
PS: 更多人工智能大数据相关视频、培训、公开课,请关注【慧都学院】
关于人工智能技术的最新资讯和相关开发工具推荐,请<咨询在线客服>!

Apple加入百厂约惠

慧都控件|提供软件技术整体解决方案

云集全球三千余款优秀控件、软件产品,提供行业领先的咨询、培训与开发服务
企业QQ:800018081|电话:023-68661681

用户评论: 您的宝贵经验,能为更多人带来帮助,登录后才能评论。
评论加载中...



    联系我们


    官方微信
    官方微博