解析

解析语法分析句法分析是分析自然语言计算机语言数据结构一串符号的过程,符合正式语法的规则。解析一词来自拉丁语parsOrationis ),意思是(语音)的一部分

该术语在语言学计算机科学的不同分支中具有略有不同的含义。传统的句子解析通常是一种理解句子或单词确切含义的方法,有时是借助句子图等设备。它通常强调语法分裂的重要性,例如主题谓语

计算语言学中,该术语用于指代句子或其他单词字符串的计算机中的形式分析,从而导致一棵解析树显示它们的句法关系相互关系,这也可能包含语义信息。某些解析算法可能会产生分析森林句法含糊的解析树列表。

在描述语言理解时,该术语也用于心理语言学。在这种情况下,解析是指人类分析句子或短语(用语言或文本)“用语法成分来识别言语,句法关系等的各个部分”的方式。当讨论哪些语言提示有助于说话者解释花园路径句子时,这个术语尤其普遍。

在计算机科学中,该术语用于计算机语言的分析中,将输入代码的句法分析用于其组件部分,以便促进编译器口译员的撰写。该术语也可用于描述分裂或分离。

人类语言

传统方法

传统的解析语法练习,有时称为子句分析,涉及将文本分解为其语音的组成部分,并说明每个部分的形式,功能和句法关系。这在很大程度上取决于对语言的偶联脱落的研究,这对于易于发音的语言可能非常复杂。要解析诸如“咬人狗”之类的短语涉及指出,奇异名词“男人”是句子主题,动词“ bites”是动词“咬人”和单数名词“狗”是句子的对象句子图之类的技术有时用于指示句子中元素之间的关系。

解析以前是整个英语世界中语法教学的核心,并且被广泛认为是对书面语言的使用和理解的基础。但是,这种技术的一般教学不再是当前的。

计算方法

在某些机器翻译自然语言处理系统中,人类语言的书面文本由计算机程序解析。人类的句子不容易被程序解析,因为人类语言的结构存在很大的歧义,其用法是在潜在的无限可能性范围内传达含义(或语义),但其中只有一些对特定情况是严密的。因此,话语“男人叮咬狗”与“狗咬人”是一个细节,但在另一种语言中可能是“男人狗叮咬”,依赖更大的环境以区分这两种可能性,如果确实如此的差异是令人担忧。即使显然正在遵守某些规则,也很难准备形式规则来描述非正式行为。

为了解析自然语言数据,研究人员必须首先就要使用的语法达成共识。语法的选择受语言和计算问题的影响;例如,某些解析系统使用词汇功能语法,但是通常,已知这种类型的语法解析是NP完整的头部驱动的短语结构语法是另一种语言形式主义,在解析社区中很受欢迎,但是其他研究工作则集中在诸如宾夕法尼亚州立大学(Penn Treebank)中使用的较少复杂形式主义上。浅解析旨在仅找到主要成分的边界,例如名词短语。避免语言争议的另一个流行策略是依赖语法解析。

大多数现代解析器至少部分是统计的。也就是说,他们依靠已经被注释的培训数据语料库(手工解析)。这种方法允许系统收集有关在特定情况下发生各种构造的频率的信息。 (请参阅机器学习。)已使用的方法包括直接的PCFG (概率无上下文语法),最大熵神经网。大多数更成功的系统都使用词汇统计数据(也就是说,他们考虑了所涉及的单词的身份,以及它们的演讲部分)。但是,这样的系统容易受到过度拟合的影响,并且需要某种平滑才能有效。

自然语言的解析算法不能像手动设计的编程语言语法一样依赖具有“良好”属性的语法。如前所述,一些语法形式主义很难在计算上解析。通常,即使所需的结构不是不含上下文的,对语法的某种无上下文近似也用于执行第一张通过。使用无上下文语法的算法通常依赖于CYK算法的某些变体,通常具有一些启发式方法来修剪不太可能分析以节省时间。 (请参阅图表解析。)但是,某些系统贸易速度的精度,例如,换档算法的线性时间版本。一个最近的发展是解析的,解析器提出了大量分析,而更复杂的系统选择了最佳选择。在自然语言理解应用中,语义解析器将文本转换为其含义的表示。

心理语言学

心理语言学中,解析不仅涉及单词分配给类别(形成本体论的见解),而且还涉及根据句子从句子中的每个单词(称为内涵)提出的句子规则来评估句子的含义的评估。 。通常会在听到或阅读单词时发生这种情况。

神经语言学通常理解解析是工作记忆的函数,这意味着解析用于使一个句子的几个部分一次发挥作用,所有这些句子都可以易于访问,可以根据需要进行分析。因为人的工作记忆有局限性,句子解析的功能也是如此。几种不同类型的句法句子可以证明这一点,这些句子提出了句子的心理解析问题。

挑战解析能力的第一个,也许是最著名的句子类型是花园路径句子。这些句子的设计是使对句子的最常见解释在语法上似乎有缺陷,但是经过进一步检查,这些句子在语法上是正确的。花园路径句子很难解析,因为它们包含一个以上含义的短语或单词,通常是最典型的含义是演讲的不同部分。例如,在句子中,“马过了谷仓倒下”,最初被解释为过去时动词,但在这句话中,它是形容词短语的一部分。由于解析用于识别语音的一部分,因此这些句子挑战了读者的解析能力。

难以解析的另一种句子类型是依恋歧义,其中包括一个可能会修改句子不同部分的短语,因此在识别句法关系方面提出了挑战(即“男孩看到瞭望远镜的女士”,在其中,用望远镜的含糊不清可以修改男孩或女士。

挑战解析能力的第三种类型的句子是中心嵌入,其中短语被放置在其他类似形成的短语的中心(即“男人的老鼠猫撞到陷阱中的老鼠,猫的老鼠cain the陷阱”。大多数极端情况3中心嵌入对于精神解析方面的挑战,再次是由于句法关系的歧义。

在神经语言学中,有多种理论旨在描述大脑中解析的方式。一种这样的模型是一种更传统的句子处理模型,它认为大脑内有一个独特的模块设计用于句子解析,在访问词汇识别和检索之前,然后进行了句法处理,以考虑单个处理解析的句法结果,只有在检测到潜在问题的情况下才能返回修订该句法解释。相反的,更现代的模型认为,在思维中,句子的处理不是模块化的,也不是严格的顺序发生。相反,它认为可以同时考虑几种不同的句法可能性,因为词汇访问,句法处理和意义的确定在大脑中并行发生。通过这种方式,这些过程被整合在一起。

尽管关于解析的神经学仍然有很多要学习的知识,但研究表明,大脑的几个区域可能在解析中起作用。这些包括左前颞极,左下额回,左颞回,左上额回,右后扣带回皮层和左角回。尽管尚未得到绝对的证明,但有人建议这些不同的结构可能有利于短语结构解析或依赖性结构解析,这意味着可以以不同的方式处理不同类型的解析,但尚待理解。

话语分析

话语分析研究了分析语言使用和符号事件的方法。有说服力的语言可以称为修辞

计算机语言

解析器

解析器是一种软件组件,可获取输入数据(经常文本)并构建数据结构- 通常是某种解析树抽象的语法树或其他层次结构,在检查正确的语法时提供了输入的结构表示。解析可以在其他步骤之前或之后进行其他步骤,也可以将这些步骤合并为一个步骤。解析器通常之前是单独的词汇分析仪,该分析仪从输入字符的顺序创建令牌。另外,这些可以结合在无扫描仪解析中。解析器可以手工编程,也可以由解析器生成器自动或半自动生成。解析与模板互补,这会产生格式化的输出。这些可以应用于不同的域,但通常会出现在一起,例如SCANF / PRINTF对,或编译器的输入(前端解析)和输出(后端代码生成)阶段。

解析器的输入通常是某些计算机语言的文本,但也可能是文本的自然语言或结构化的文本数据,在这种情况下,通常只提取文本的某些部分,而不是构造的解析树。解析器的范围从非常简单的功能,例如SCANF到复杂的程序,例如C ++编译器的前端或Web浏览器HTML解析器。重要的一类简单解析是使用正则表达式完成的,其中一组正则表达式定义了常规语言和正则表达式引擎会自动生成该语言的解析器,从而允许文本的模式匹配和提取文本。在其他情况下,在解析之前使用正则表达式,作为解析器的输出的Lexing步骤。

解析器的使用因输入而异。对于数据语言,通常会发现解析器作为程序的文件阅读设施,例如在HTML或XML文本中读取;这些示例是标记语言。在编程语言的情况下,解析器是编译器解释器的组成部分,该编译器或解释器解析了计算机编程语言源代码以创建某种形式的内部表示形式;解析器是编译器前端的关键步骤。编程语言往往是根据确定性的无上下文语法来指定的,因为可以为其编写快速有效的解析器。对于编译器,解析本身可以在一次或多个通过中完成 - 请参阅一通编译器多通编译器

一通编译器的隐含缺点可以通过添加固定措施来基本克服,即在向前传球期间为代码搬迁提供准备,并且在当前程序段被认为已被视为已被视为已被确认为已被确认为已被确认为已被确认为已被确认为已被确认为已被确认为已验证完全的。这样的修复机制将是有用的一个示例,将是一个正向goto语句,在该语句中,在程序段完成之前,goto的目标是未知的。在这种情况下,固定的应用将延迟,直到确认GOTO的目标为止。相反,向后的goto不需要修复,因为该位置已经知道。

无上下文的语法在表达语言的所有要求的程度上受到限制。非正式的原因是,这种语言的记忆是有限的。语法不记得在任意长的输入中存在构造的存在。这对于例如必须在引用名称之前声明名称的语言是必要的。但是,可以表达这种约束的更强大的语法不能有效地解析。因此,为无上下文的语法创建一个放松的解析器是一种普遍的策略,该语法接受所需的语言构造的超集(即接受某些无效的构造)。后来,可以在语义分析(上下文分析)步骤中过滤不需要的构造。

例如,在Python中,以下是句法有效的代码:

x = 1;
print(x);

但是,以下代码在句法上是根据无上下文的语法有效的,产生了与以前相同结构的语法树,但违反了使用之前必须在使用前初始初始化变量的语义规则:

x = 1
print(y)

过程概述

Flow of data in a typical parser
典型解析器中的数据流

以下示例演示了用两个语法级别解析计算机语言的常见情况:词汇和句法。

第一阶段是令牌生成或词汇分析,通过其将输入字符流分为有意义的符号,该符号由正则表达式的语法定义。例如,计算程序将查看诸如“12 * (3 + 4)^2“然后将其分成代币12,*,(,3,+,4,),^,2,在算术表达的上下文中,每个都是有意义的符号。 Lexer将包含规则来告诉它字符*,+,^,()标记新令牌的开始,如此毫无意义的令牌”12*“ 或者 ”(3“不会生成。

下一个阶段是解析或句法分析,该分析检查令牌是否形成了允许的表达式。这通常是指无上下文的语法来完成的,该语法递归定义了可以构成表达式和必须出现的顺序的组件。但是,并非所有定义编程语言的规则都可以通过无上下文的语法来表达,例如类型有效性和标识符的正确声明。这些规则可以用属性语法正式表达。

最后阶段是语义解析或分析,它正在阐明刚刚验证并采取适当动作的表达的含义。对于计算器或解释器,该动作是评估表达式或程序;另一方面,编译器将生成某种代码。属性语法也可以用来定义这些动作。

解析器类型

解析器的任务本质上是确定输入是否以及如何从语法的开始符号得出的。这可以从本质上进行两种方式完成:

自上而下的解析
自上而下的解析可以看作是通过使用给定正式语法规则的自上而下的扩展来搜索解析,从而试图找到输入流的最左边推导。令牌从左到右消耗。包容性选择用于通过扩大语法规则的所有替代右侧右侧的右手来适应歧义。这被称为原始汤方法。与句子图的非常相似,原始汤破坏了句子的选区。
自下而上的解析
解析器可以从输入开始,并尝试将其重写为开始符号。凭直觉,解析器试图找到最基本的元素,然后是包含这些元素的元素,依此类推。 LR解析器是自下而上解析器的示例。这种类型的解析器使用的另一个术语是Shift-Reduce解析。

LL解析器递归的解析器是无法适应左递归生产规则的自上而下解析器的例子。尽管人们认为自上而下的解析的简单实现无法容纳直接和间接的左回归,并且可能需要指数级的时间和空间复杂性,同时解析含糊不清的无上下文的语法,但由霜冻创建了更复杂的自上而下的解析算法,Hafiz和Callaghan在多项式时间内适应歧义左递归,并产生可能指数级的解析树数的多项式大小表示。他们的算法能够就给定的无上下文语法产生输入的最左侧和最右推导。

关于解析器的一个重要区别是解析器是生成最左边的推导还是最右边的推导(请参阅无上下文的语法)。 LL解析器将产生最左边的推导,而LR解析器将产生最右边的推导(尽管通常是反向)。

一些图形解析算法是为视觉编程语言设计的。视觉语言的解析器有时基于图形语法

自适应解析算法已用于构建“自我扩展”的自然语言用户界面

执行

最简单的解析器API读取整个输入文件,进行一些中间计算,然后写入整个输出文件。 (例如内存中多通编译器)。

当没有足够的内存存储整个输入文件或整个输出文件时,这些简单的解析器将无法正常工作。它们也不适用于现实世界中永无止境的数据流。

一些用于解析此类数据的替代API方法:

  • 一旦解析器检测到输入流中的相关令牌(例如Expat
  • 拉解析器
  • 增量解析器(例如增量图表解析器),由于文件的文本由用户编辑,因此不需要完全重新放置整个文件。
  • 活跃与被动解析器

解析器开发软件

一些知名的解析器开发工具包括以下内容:

展望

C程序不能用少于2个令牌lookahead进行解析。顶部: C语法摘录。底部:解析器消化了令牌”int v;main(){“并且即将选择一个规则来得出STMT 。只查看第一个lookahead代币”v“它不能决定选择哪种替代方案;后者需要窥视第二个令牌。

LookAhead建立了解析器可以使用哪种规则使用的最大传入令牌。 LookAhead与LLLRLALR Parsers特别相关,通常通过将LookAhead固定到括号中的算法名称(例如LALR(1))来明确指示。

大多数编程语言,即解析器的主要目标,都是通过有限的lookahead(通常是一种)可以解析的解析器的仔细定义的,因为lookahead有限的解析器通常更有效。这一趋势的一个重要变化是在1990年特伦斯·帕尔(Terence Parr)为他的博士学位创建Antlr的一个重要变化。论文,有效LL( k )解析器的解析器,其中k是任何固定值。

LR解析器看到每个令牌后通常只有几个动作。它们正在移动(将此令牌添加到堆栈中以进行以后减少),减少(从堆栈中弹出令牌并形成句法结构),结束,错误(无知的规则应用)或冲突(不知道是移动还是减少) 。

LookAhead有两个优势。

  • 在发生冲突的情况下,它可以帮助解析器采取正确的措施。例如,在其他条款的情况下解析if语句。
  • 它消除了许多重复的状态,并减轻了额外堆栈的负担。 AC语言非远见解析器将拥有约10,000个州。 Lookahead解析器将拥有大约300个州。

示例:解析表达式1 + 2 * 3

表达式解析规则集(称为语法)如下,
规则1:E→E + E表达是两个表达式的总和。
规则2:E→E * E表达是两个表达式的产物。
规则3:E→数字表达是一个简单的数字
规则4:+比 *的优先级要少。

大多数编程语言(除了一些诸如APL和SmallTalk之类的少数)和代数公式对乘法的优先次数高于添加,在这种情况下,对上述示例的正确解释是1 +(2 * 3) 。请注意,上面的规则4是语义规则。可以重写语法以将其纳入语法。但是,并非所有此类规则都可以翻译成语法。

简单的非外观解析器动作

最初输入= [1, +,2, *,3]

  1. 将“ 1”转移到输入(预期规则3)上。输入= [+,2, *,3] stack = [1]
  2. 根据规则3将“ 1”降低到表达“ e”。 stack = [e]
  3. 将“+”转移到输入(预期规则1)上。输入= [2, *,3] stack = [E, +]
  4. 将“ 2”转移到输入(预期规则3)上。输入= [*,3] stack = [E, +,2]
  5. 根据规则3将堆栈元素“ 2”简化为“ e”。 stack = [E, +,E]
  6. 根据规则1将堆栈项目[E, +,E]和新输入“ E”减少为“ E”。 stack = [e]
  7. 从输入(预期规则2)将“*”转移到堆栈中。输入= [3] stack = [E,*]
  8. 将“ 3”转移到输入(预期规则3)上。输入= [](空)stack = [E, *,3]
  9. 根据规则3将堆栈元素“ 3”简化为“ e”。 stack = [e, *,e]
  10. 根据规则2将堆栈项目[E, *,E]和新输入“ E”减少为“ E”。 stack = [e]

根据语言语义,解析树和由此产生的代码是不正确的。

为了正确解析,没有LookAhead,有三个解决方案:

  • 用户必须将表达式包装在括号内。这通常不是可行的解决方案。
  • 每当规则违反或不完整时,解析器都需要具有更多的逻辑来回溯和重试。 LL解析器也遵循类似的方法。
  • 另外,解析器或语法需要具有额外的逻辑才能延迟减少并仅在绝对确定要首先减少的规则时减少。该方法用于LR解析器。这正确解析了表达,但具有更多状态并增加了堆栈深度。
lookahead解析器
  1. 在预期规则3中将1转到输入1的堆栈。它不会立即减少。
  2. 根据规则3将堆栈项目1减少到输入 +上的简单表达式。 LookAhead是 +,因此我们正在通往E +的路径,因此我们可以将堆栈减少到E。
  3. 在预期规则1中将输入 +上的堆栈移动到堆栈中。
  4. 在预期规则3中将2移至输入2的堆栈。
  5. 根据规则3将堆栈项目2减少到输入 *上的表达。 LookAhead *只期望E之前。
  6. 现在,堆栈具有E + E,并且输入仍然是 *。它现在有两个选择,可以根据规则2进行移动或基于规则1的减少。由于 *基于规则4的优先级高于 + +,因此我们在预期规则2中将 *转移到堆栈上。
  7. 在预期规则3中将3移至输入3上的堆栈。
  8. 根据规则3查看输入结束后,将堆栈项目3减少到表达。
  9. 根据规则2将堆栈项目e * e减少到e。
  10. 根据规则1将堆栈项目E + E减少到E。

生成的解析树是正确的,并且比非面目的解析器更有效。这是LALR解析器所遵循的策略。

也可以看看