parsing解析入门


备注

在通常的用法中,解析是指分析一种语言,例如句子,并使用该语言的语法规则来识别组件片段,从而学习其含义。在计算机科学中,它指的是将符号序列识别为有效符号的特定算法过程,并且允许通常在计算机语言编译器或解释器中确定语言构造的含义(或语义 )。

一个简单的解析器

编写解析器的最简单方法是使用递归下降技术。这将创建一个自上而下的解析器(可能正式描述为LL(1))。为了开始这个例子,我们首先要为我们的语言建立语法规则。在这个例子中,我们将对只能使用plus运算符的表达式使用简单的算术表达式赋值:

 Assignment --> Identifier := Expression
 Expression --> Expression + Term | Term
 Term --> Identifier | (Expression)
 Identifier --> x | y | z 
 

对于语法的每个规则,我们可以编写一个过程来识别规则的传入令牌。出于本示例的目的,我们可以假设一个名为NextToken 的例程,它调用一个词法分析器来提供令牌,以及一个名为error 的例程,用于输出错误消息。使用的语言基于Pascal。

 var token:char;  (* Updated by NextToken *) 

 procedure identifier;
 begin
    if token in ['x','y','z']
    then
        NextToken
    else
        error('Identifier expected')
 end; 
 

您可以看到此代码实现了识别Identifier 的规则。然后我们可以类似地实现Term 的规则:

 procedure expression forward; 

 procedure term;
 begin
     if token = '('
     then
         begin
         nextToken;
         expression;
         if token <> ')'
         then
             error(') expected')
         else NextToken
         end
     else
         identifier
 end; 
 

当我们来实现Expression 规则时,我们遇到了问题; Expression 规则的第一个元素本身就是一个Expression 。这将导致我们写下以下内容:

procedure expression;
begin
expression;
...
end;
 

这是直接自我递归的,因此会永远循环。由于这个原因,由自上而下算法解析的语法不能是左递归的。解决此问题的一个简单方法是以下列方式将递归重新设置为迭代:

Expression --> Term { + Term}* 
 

我们现在可以将语法规则编码为:

 procedure expression;
 begin
     term;
     while token = '+'
         do
         begin
             NextTerm;
             term
         end
 end; 
 

我们现在可以使用剩余的赋值规则来完成解析器:

procedure assignment;
begin 
    identifier;
    if token <> '='
    then
        error('= expected')
    else
        begin
        NextToken;
        expression;
        end
 end; 
 

解析英语句子的例子

例如,在句子中:

那蛋糕非常好吃。

英语语言的规则将做蛋糕名词非常 副词修饰形容词 不错 ,并通过这种分析的含义可以理解。

然而,这种分析依赖于我们认识到所使用的符号序列是单词。如果我们不熟悉使用的字符,我们就无法做到这一点。如果我们使用不熟悉的符号(例如中文)遇到句子,则以这种方式解析可能会很困难。这是一个中文句子的例子:

我可以写一点儿中文。

对于没有阅读中文字符的人来说,不清楚哪些符号组合形成单词。处理英语或中文时计算机算法也是如此。

因此,必须通过称为词法分析扫描的过程来进行解析,其中将各个字符组合在一起形成识别的符号,我们通常可以将其称为单词,但在解析算法中称为标记

解析所需的内容

在执行解析时,在开始之前,需要指定语言的语法 。解析器还需要令牌源。

解析器可以是手写代码,也可以使用解析器生成器工具 。如果使用了解析器生成器工具,那么如果您的平台中尚未包含该工具,则需要下载并安装该工具。

语法定义

解析器的语法通常需要以上下文自由形式编写。通常使用诸如BNF(Backus-Naur形式)EBNF(扩展后Naur形式)之类的符号。通常用于描述编程语言的其他符号可能是铁路图

词汇分析

通常由词法分析器(或扫描仪)为解析器提供令牌。更多细节可以在词法分析器(TBC)的文档中找到。

解析技术

手工编写一个解析器,一个合适的算法将需要选择适合双方语言被解析和执行手段。解析算法分为自上而下解析自下而上 解析两种类型。在开始编写解析器时,初学者更容易学习(递归)自顶向下解析器。

分析器生成器工具

创建解析器的最常用方法是使用解析器生成器工具。有很多这样的工具,但最常用的一些是: