LR(k)文法任意文法位置的断点调试方法

摘要

本发明涉及LR(k)文法任意文法位置的断点调试方法，其步骤是：定义语言的LR(k)文法或LR(k)文法的子类文法G；在相应的文法位置插入断点；检查每一断点，若该断点设置在产生式右部中间的某个文法位置，则添加无用非终结符号，从而得到新的文法G’；为文法G’生成分析表；计算每个断点的类型；分析输入串，直至遇到一个归约动作，检查该归约动作处是否对应一个断点，如是则采取如下动作：对有效断点，暂停分析过程，显示当前的分析状态信息；对无效断点，忽略该断点，继续分析过程；对不确定断点，则忽略或结合当前的输入串和断点设置位置，进一步判断该位置是否有效，如果对于当前的输入串，该位置是有效的，则按有效断点位置处理，如果该位置是无效的，则忽略该位置，继续分析过程。本发明显著增加可跟踪和调试的断点数目，可以跟踪到更细粒度的语法成分，帮助用户更好地进行文法调试，降低分析器的开发难度。

说明书

技术领域

本发明涉及文法的断点调试技术，提出了一种LR(k)文法任意文法位置的断点调试方法，它可显著增加可跟踪和调试的断点数目，帮助用户更好地进行文法调试。

背景技术

分析器生成器(parser generator)在分析器(parser)和编译前端(compiler front end)构造中得到了广泛应用，越来越多的开发者使用分析器自动生成工具来生成分析器或编译前端。

与编译领域的专家不同，这些普通开发者往往对分析理论并不熟悉，而且他们也不是经常开发此类分析工具。对于这类开发者而言，良好的文法调试支持是不可或缺的，可以有效降低分析器开发的复杂性，提高开发效率。即使对编译领域的专家而言，良好的文法调试支持也可以帮助他们更快更好地开发分析器。对于LL(k)文法，一些经典的源码调试工具，比如GNU的gbd调试器、微软的Visual C++调试器等，可以用来展示LL分析方法采用的递归下降分析器(recursive descent parser)的分析过程，这是因为LL文法和它对应的递归下降分析器之间有很明显的结构对应关系，借助这些经典的源码调试工具，开发者就可以对分析过程有较好的理解。然而，LR(k)文法却无法利用这些经典的源码调试工具，主要原因在于LR(k)采用的是自底向上的分析方法，LR(k)文法和其对应的分析器之间并无结构上的对应关系。为流行的程序设计语言，如C++、Ada等开发LR(k)分析器，需要非常专业的知识和技能，只有很少的开发者可以开发此类分析器。LR(k)文法是支持确定性分析的最大文法类，LR(k)文法及其子类在各类分析器生成器(parser generator)中有广泛应用。相比于LL(k)文法，LR(k)文法所能描述的文法范围要宽泛得多，可以表示当今大多数编程语言的文法，可以处理左递归，应用非常广泛，因此，迫切需要良好的LR(k)文法调试技术支持。

软件可视化(Software visualization，简称SV)，是一种利用图形手段增强用户对程序理解的技术。目前已出现了一些基于SV、采用自底向上分析方法的分析器生成器，如Ytracc，YT，Visual Parse++，Llun，AnaGram等。这些工具可以展示LR(k)分析器使用的确定性下推自动机(deterministic pushdown automaton)的分析过程，如符号栈(symbol stack)，语法树(syntax tree)，当前使用的产生式(production)及向前看符号(lookahead)等，可以帮助用户较好地理解分析过程。

断点是一种经典直观的调试支持手段，广泛应用于各类基于SV技术的调试器(debugger)中。或许断点调试是目前最为人们熟悉的调试方式了。目前采用的LR(k)文法的断点调试技术存在一个不足，即只允许在产生式右部末尾设置断点，不允许在产生式右部的中间位置设置断点。比如，对于图1所示文法，传统的断点调试方法只允许在图中粗黑点标注的位置设置断点，不允许在其它位置设置断点。这是LR(k)分析方法的一个固有属性，因为标准的LR(k)分析方法不支持产生式内部的语义动作调用，无法暂停分析过程以查看分析状态信息。

只允许在产生式右部末尾而不允许在产生式右部的其它位置设置断点，给用户的调试带来了不便。比如，对于图1中的Rule 1，如果想在分析器识别了“+”后查看分析器的分析状态，目前的LR(k)文法调试技术却并不支持，因为不允许在“+”之后设置一个断点，除非用户手工在“+”之后添加了一个新的无用非终结符号(null nonterminal)X，如图2所示，并且在新增加的产生式的末尾设置一个断点(Rule3)。

由用户手工添加无用非终结符会带来一系列的弊端。首先，这种方式修改了原始文法，损害了文法的可读性；其次，给用户增加了额外的处理负担；第三，这些无用非终结符本质上并不是原始文法的一部分，因此在调试完毕后，它们必须从文法中删除，这样，用户每次设置一个断点，都要手工添加一个无用非终结符，当调试完毕又不得不删除，这给用户的调试带来了很大的不便；最后，在LR(k)文法中添加无用非终结符可能会引入新的分析冲突，造成更改后的文法不再是LR(k)文法，从而导致分析过程失败。比如，图1所示文法是一个LR(k)文法，如果在Rule 1的右边开始位置添加一个无用非终结符，将导致更改后的文法不再是LR(k)文法(图3)，

发明内容

有鉴于此，本发明的目的是提出一种新的断点调试方法，该方法可显著增加可跟踪和调试的断点数目，从而可以跟踪到更细粒度的语法成分。

为此，本发明采用以下技术方案：

一种LR(k)文法任意文法位置的断点调试方法，它包括如下步骤：

定义语言的LR(k)文法或者LR(k)文法的子类文法G；

用户在相应的文法位置插入断点；

检查用户设置的每一个断点，如果该断点设置在某个产生式右部末尾，则什么都不做，如果该断点设置在产生式右部中间的某个文法位置，则自动添加相应的无用非终结符号，从而得到一个新的文法G’；

为新的文法G’生成分析表；

计算每个断点的类型，从而得到每个断点是有效断点、无效断点，还是不确定断点；

利用LR(k)分析方法或者其子类分析方法分析输入串，直到遇到一个归约动作，检查该归约动作处是否对应一个断点，如果对应一个断点，则根据不同的断点类型采取如下动作：如果是一个有效断点，则暂停分析过程，显示当前的分析状态信息；如果是一个无效断点，则忽略该断点，继续分析过程；如果是一个不确定断点，则采用以下两种方法之一：一种方法是简单忽略这些不确定断点，继续分析过程；另一种方法是结合当前的输入串和断点设置位置，进一步判断该位置是否有效，如果对于当前的输入串，该位置是有效的，则按照有效断点位置处理，如果对于当前输入串，该位置是无效的，则忽略该位置，继续分析过程。

本发明方法的优点在于：支持在产生式右部任意文法位置插入断点，可显著增加可跟踪和调试的断点数目，从而可以跟踪到更细粒度的语法成分；本发明方法对用户完全透明，不会给用户增加任何处理负担，用户用起来简单直观；本方法很容易集成到现有的分析器生成框架中；本发明可帮助用户更好地进行文法调试，可在一定程度上降低分析器的开发难度。其中的断点类型分类算法可以区分不同的断点类型，可以更好的指导分析过程，同时又不会引入任何新的分析冲突。

附图说明

图1表示一个LR(1)文法；

图2表示添加一个无用非终结符到图1所示文法；

图3表示增加无用非终结符给文法引入了新的冲突；

图4表示在产生式右部的中间位置中间插入一个断点；

图5表示一个文法的文法位置；

图6表示一个支持加法和乘法的算术表达式文法；

图7表示图6所示文法的初始结点的一个部分状态位置图；

图8表示一个示例文法G；

图9表示图8所示文法的初始状态对应的两个PSPG；

图10表示合并图9中的两个PSPG中的相同结点得到的SPG；

图11表示一个状态数随n增大呈指数规模增长的LR(k)文法。

具体实施方式

本发明提出了一种新颖的LR(k)文法断点调试方法，它支持在产生式右部任意文法位置(grammar position)插入断点。比如，对于上面讨论的问题，如果用户想要在识别“+”后查看分析状态信息，我们的调试方法支持在“+”之后直接设置一个断点(图4)。本发明还提出了一种方法来区分有效、无效和不确定断点位置。本发明可以显著增加可利用的断点数量，用户可以跟踪到更细粒度的文法片断，可以帮助用户更好的理解分析过程。

1相关定义

为了后文论述方便，此处给出本发明用到的一些相关术语的定义。对于在本发明中涉及的文法、语言和分析技术方面的基础知识，请参考编译原理教科书中的相应内容。上下文无关文法(context-free grammar)

一个上下文无关文法是一个四元式G＝(N，T，P，S)，其中N代表文法的非终结符集合，T代表终结符号集合，P是文法的产生式集合，S是文法的开始符号。

LR(k)文法

LR(k)文法是上下文无关文法的子类，它是能够被一个最多预读k个向前看符号就可以识别的确定性的移进-归约(shift-reduce)分析器(亦称递归上升分析器(recursive ascentparser))所能识别的最大文法类。

文法位置(grammar position)，主要位置(main position)和导出位置(derived position)

一个文法位置是一个形如[i，j]的二元组，这里i代某个产生式p的编号，j代表p右部的某个位置，  0≤j≤产生式p右部的符号数目。编号为0的产生式的左部符号是文法的开始符号。位置[i，j]表示产生式i的右部第j个符号之后的位置。位置[0，0]和[i，j](j≥1)称为主要位置，位置[i，0](i≥1)称为导出位置。图5列出了图1所示文法的文法位置。

项目(item)，初始项目(initial item)，主要项目(main item)和导出项目(derived item)

文法G的一个项目是一个三元组[i，j，γ]，此处[i，j]表示一个文法位置，γ是向前看符号(对于某些简单的分析器，如LR(0)分析器，向前看符号可省略)。项目[i，j，γ]也可用形如A→α·β{γ}的形式表示，其中A→α·β表示文法位置[i，j]，γ是向前看符号。[0，0，$]是文法的初始项目，此处$是文法的结束符。项目[i，j，γ]是一个主要项目当且仅当[i，j]是一个主要位置。项目[i，j，γ]是一个导出项目当且仅当[i，j]是一个导出位置。分析器的一个状态(state)可以由它的主要项目集合(main items set)唯一地确定。

为了区分不同的断点，我们引入了以下几个新的概念：

有效断点位置(valid breakpoint position)，无效断点位置(invalid breakpoint position)和不确定断点位置(indeterminate breakpoint position)。

对一个LR(k)文法G，假定￡’是不包含位置[i，j]的任意文法位置的集合，令￡”＝￡’U[i，j]，即￡”是￡’和[i，j]的并集，在文法G的文法位置集合￡’处插入无效非终结符后得到的文法为G’，在文法G的文法位置集合￡”处插入无效非终结符后得到的文法为G”。则文法位置[i，j]是一个有效断点位置，当且仅当对于所有的￡’，G’和G”要么都是LR(k)文法，要么都不是LR(k)文法；文法位置[i，j]是一个无效断点位置，当且仅当对于每一个￡’，G”都不是LR(k)文法；文法位置[i，j]是一个不确定断点位置，当且仅当对于某些￡’的集合但不是所有的￡’集合，G”不是LR(k)文法。

部分状态(partial state)，部分状态位置图(partial state position graph，后文简称PSPG)，状态位置图(state position graph，后文简称SPG)

部分状态(partial state)是由Purdom和Brown等提出的一个概念，一个状态的部分状态包括：(1)任何可以移入个终结符或者用产生式归约的项目，记这样的项目为d；(2)任何可以推导出d的主要项目，记这些主要项目为M；(3)任何包含在M的闭包closure(M)中并且可以推导出d的项目(关于闭包的概念，请参考编译原理教科书)。对每一个部分状态，都对应一个部分状态位置图(PSPG)。每一个PSPG都包含一个初始结点(记为I)，一个终止结点(记为E)，部分状态中和每个项目相关联的每个文法位置[i，j]都对应PSPG中的一个中间结点。PSPG是一个有向图，图中的弧表示项目间的ε转换关系(ε-transition)。从I到M中的每一个项目都有一条弧，从每一个d到E也有一条弧。对于每条形如a→b弧，此处a和b既不是初始结点，也不是终止结点，表示a可以经过一次ε转换到b。

除了初始结点和终止结点外的每个结点都表示一个文法位置。

图6是一个算术表达式文法，表1列出了初始状态及初始状态的状态转换关系。图7是给出了初始结点的一个PSPG示例。

 StateItem  ACTION  GOTO  Looka-  head   Action Stack Top  Next  State    1S→·E    {$}E→·E+T  {+，$}E→·T    {+，$}T→·P^*T  {+，$}T→·P    {+，$}P→·〔E〕{+，^*，$}P→·i    {+，^*，$}     〔，i     shift E E T P P 〔  i  2  2  3  4  4  5   6

表1

Purdom等的方法中存在一个不足，即对于同一个分析状态可能会构造多个PSPG。欧阳士庭等提出了一种改进的方法，该方法通过合并同一个状态中所有PSPG中的相同结点，从而得到一个新的图，欧阳等称该图为SPG(state position graph)。这样，对于一个状态，只需要构造一个SPG即可。

对于图8所示文法中的始态，图9中(为了简单起见，向前看符号图中没有标出)给出了它对应的两个PSPG。在图9中，结点1和6，结点2和7都是相同的结点，合并这些相同的结点以后得到的SPG如图10所示。

决定结点(dominator)，前驱决定结点(predominator)，直接前驱决定结点(immediatepredominator)

对于有向图G＝(V，A，r)，其中V表示顶点的集合，A表示弧的集合。r表示开始结点，V中除了开始结点r外的其它结点都可以从r经过一步或多步转换到达。如果从结点r到结点v的每一条路径都经过结点w，则称结点w为结点v的决定结点。如果p和q是G中的结点，p是q的前驱决定结点(predominator)当且仅当从r到q的每一条路径都经过p。结点p是结点q的直接前驱决定结点(immediate predominator)当且仅当p是q的前驱决定结点，并且q除了p以外的其他任何前驱决定结点也是p的前驱决定结点。

2断点类型分类算法

下面介绍本发明用到的算法

算法1：LR(k)分析器分析状态的SPG构造算法

算法输入：一个LR(k)文法G＝(N，T，P，S)和它对应的LR(k)分析表M.

算法输出：每一个分析状态对应的SPG

算法步骤：

对M中的每一个状态m

{

  为状态m生成一个初始结点I_m

  对状态m中的每一个主要项目m

  {

    生成一个结点N_mi，并且从结点I_m添加一条弧到N_mi

    如果mi的形式为：A→α·Xβ，{γ}，这里α，β∈(NUT)^*，X∈T

    {

      生成一个新的终止结点N_shift X，并且从结点N_mi添加一条弧到N_shift X

    }

    否则，如果mi的形式为：A→α·，{γ}，这里α∈(NUT)^*

    {

      生成一个新的终止结点N_{reducet(A→α)}，从结点N_mi添加一条弧到N_{reducet(A→α)}

    }

    否则，如果mi的形式为：A→α·Xβ，{γ}，这里α，β∈(NUT)^*，X∈N)

    {

      为形如：X→·η，{∏}(这里η∈(NUT)^*)的每一个项目生成一个新的结点

      从结点N_mi添加一条弧到新生成的每一个结点

      把所有新生成的结点添加到集合Q中

      当Q不为空

      {

        从集合Q中删除一个结点，记该结点为N_current

        如果N_current是跟一个形如：Y→·ε，{Γ}的项目关联，这里ε表示空串

        {

          生成一个新的终止结点N_{reduce(Y→ε)}，从结点N_current添加一条弧到N_{reduce(Y→ε)}

        }

        否则，如果N_current是跟一个形如：Y→·Bη，{Γ}的项目关联，这里B∈T，η∈(NUT)^*

        {

          生成一个新的终止结点N_shift B，从结点N_current添加一条弧到N_shift B

        }

        否则，如果N_current是跟一个形如：Y→·Bη，{Γ}的项目关联，这里B∈N，η∈(NUT)^*

        {

          对每一个形如：B→·θ，{Л}(这里θ∈(NUT)^*)的项目生成一个新的结点

          从结点N_current添加一条弧到新生成的每个结点

          如果Y≠B

          {

            把所有新生成的结点添加到集合Q中

          }

        }

      }

    }

  }

}

算法2：断点位置类型分类算法

算法输入：一个LR(k)文法G＝(N，T，P，S).

算法输出：文法G的每一个断点位置的类型：有效断点，无效断点或者不确定断点

算法步骤：

(1)使用算法1为分析器的每一个状态构造一个SPG；

(2)对于每一个SPG，计算直接前驱决定结点，为该SPG构造决定结点树(dominator tree)T，前驱决定结点的计算及决定结点树的构造可以采用既有的决定结点和决定结点树构造算法，如2004年Georgiadis等的算法；

(3)检查得到的每一个SPG中的每一个结点，对于每一个形如[i，0]并且能推导出自身的断点位置标记为无效断点位置；

(4)检查得到的每一个SPG中的每一个结点，如果文法位置[i，j]尚未做标记，并且存在一个部分状态(x，γ)包含文法位置[i，j]对应的项目，并且结点(x，γ)，[i，j)不是(x，γ)对应的终止结点的前驱决定结点(此处(x，γ)表示一个部分状态(partial state)，x表示项目集，γ表示向前看符号集。((x，γ)，[i，j])表示SPG中对应部分状态(x，γ)的一个结点，[i，j]表示文法G中的一个文法位置)，则把[i，j]标记为不确定断点位置。结点q是结点p的前驱决定结点当且仅当在步骤(2)中构造的决定结点树T中q是p的祖先(ancestor)；

(5)把所有未做标记的其它文法位置都标记为有效断点位置。

3本发明提出的断点调试方法

标准的LR(k)分析方法不支持在产生式中间调用语义动作，因此如果想在产生式的中问插入断点，就必须在相应位置添加无用非终结符符号。本发明的文法断点调试方法中，调试器会根据用户设置的断点，自动添加相应的无用非终结符号，这一过程对用户是透明的，用户不必手工添加任何的无用非终结符号。

添加无用非终结符号后可能会引入新的分析冲突，造成更改后的文法不再是LR(k)文法，从而导致分析过程失败。因此，调试器还需要利用上面给出的算法2米计算各个断点的类型。

本发明提出的断点调试方法的具体实施步骤如下：

(1)用BNF等定义语言的LR(k)文法或者LR(k)文法的子类文法G；

(2)用户在相应的文法位置插入断点；

(3)检查用户设置的每一个断点，如果该断点设置在某个产生式右部末尾，则什么都不做。如果设置在产生式右部中间的某个文法位置，则自动添加相应的无用非终结符号。这样会得到一个新的文法G’；

(4)为文法G’生成分析表。根据不同的设计需求，分析表可以是LR(k)的，或者LR(k)的子类，如SLR(1)，LR(0)，LALR(1)等；

(5)利用上面给出的算法2来计算每个断点的类型，从而可以得到每个断点是有效断点，无效断点，还是不确定断点；

(6)利用LR(k)分析方法(或者其子类分析方法)分析输入串，直到遇到一个归约(reduce)动作。检查该归约动作处是否对应一个断点，如果有断点，则根据不同的断点类型采取如下动作：

(6.1).如果是一个有效断点，则暂停分析过程，以图形化或其它手段等报告显示当前的分析状态信息；

(6.2).如果是一个无效断点，则忽略该断点，继续分析过程；

(6.3).如果是一个不确定断点，可以采用两种不同的处理策略，一种方法是简单忽略这些不确定断点，继续分析过程。另一种方法是结合当前的输入串和断点设置位置，进一步判断该位置是否有效，如果对于当前的输入串，该位置是有效的，则按照有效断点位置处理，如果对于当前输入串，该位置是无效的，则忽略该位置，继续分析过程。

4实验效果评价

实用的文法调试器必须有较快的响应速度，从第3节所述步骤可看出，每次更改了断点设置，在启动调试器前，都必须重新生成分析表，重新构造每个状态的SPG(算法1)，并且重新计算每个断点的类型(算法2)。为了验证本发明提出的调试方法的有效性，我们进行了三组实验，实验4.1使用了一个指数规模的文法以及一个实用的编程语言文法Java，用于验证LR(k)分析表的生成性能；实验4.2给出了一个指数规模文法和Java文法的SPG构造时间，用于验证SPG的构造性能；实验4.3给出了Java文法的断点分类时间，用于验证断点分类算法的性能。

4.1 LR(k)分析表的生成性能

LR(k)分析方法的子类——LALR(1)，由于分析表规模较小，分析速度较快，且与LR(k)分析能力接近，在实际中应用最广。因此，本实验中我们也生成LALR(1)分析表。Earley证明了图1 1所示文法，它的状态数目随着n的增大呈指数规模增长。Earley指出该文法很适合验证LR(k)分析表的构造性能。表2给出了n＝2，3，4，5，6，7，8时的LALR(1)分析表的构造时间，表3给出了一个实用的编程语言文法Java(采用的是Java1.4的文法)的LALR(1)分析表生成时间。

               表2                                   表3

通常，对于一个典型的编程语言文法，它的LALR(1)分析表一般只有几百个状态，即使对于文法异常复杂的C++文法，它的LALR(1)分析表规模也只有1200个状态左右。因为LALR(1)是一个线性时间的分析方法，从表2和表3可以看出，对于一个实际的编程语言文法，LALR(1)分析表的生成速度是相当快的，可以满足文法调试的时间响应需求。

4.2 SPG构造性能

表4给出了图11所示文法的SPG构造时间，表5给出了Java 1.4文法的SPG构造时间。

                   表4                                 表5

需要指出的是，我们的SPG构造实现并未做很多的优化，如果对程序实现做进一步的优化，构造时间还可以进一步缩短。从表4和表5可看出，对于一个和Java 1.4文法规模相似的编程语言文法，SPG的构造时间是相当快的。由于SPG构造算法是线性的，实用的编程语言文法的分析器状态数目一般不会比Java 1.4文法高出太多，因此，可以推断出，SPG的构造时间可以满足文法调试的时间响应需求。

4.3断点位置分类算法的性能

在断点位置分类算法中，有两个问题比较关键，一个是，该算法的执行速度有多快；另一个是，对于一个典型的文法，有多少文法位置是有效的，有多少是无效的，有多少是不确定的。

对于第一个问题，我们使用了Java 1.4文法米检验算法的执行时间，表6给出了实验结果。

 States  Rules   Total  Valid  In-  valid  Un-  deter-  minate  CPU  clocks   Seconds 448  278   2690  2326   131   233  4,836,  431   0.0032

表6

断点分类算法是一个线性算法，从表6可看出，对于一个规模和Java类似的文法，断点分类算法的运行时间大约为0.003秒，这个执行速度是相当快的，可以满足文法调试器的需求。

对于第二个问题，从表6可以看出，在Java 1.4文法中，有效断点位置的比例为86.47％，无效断点的比例为4.87％，不确定断点的比例为8.66％。典型地，在一个产生式的右部一般至少有两个符号，换句话说，对于一个产生式，一般至少有3个文法位置，使用传统的文法断点调试方法，仅能在产生式右部末尾插入断点，因此，最多有1/3的位置可插入断点，考虑到平均情况下产生式右部的符号数目一般远多于两个，因此，传统方法可以利用的断点位置一般远低于1/3，而采用我们的方法，可以显著增加可利用的断点数目。以表6所示Java文法为例，使用传统断点调试方法，最多只有278个断点可以利用，而使用我们的断点调试方法，可以利用的断点数目有2326个，是传统方法可利用断点数目的8倍多。考虑到Java文法在编程语言文法中具有相当的代表性，据此，我们可以推断出，本发明的断点调试方法，在提高可利用断点数目方面是卓有成效的。

5结论

本发明提出的LR(k)文法断点调试方法，支持在产生式右部的任意文法位置设置断点，该方法可以显著增加可以利用的断点位置，可以跟踪到更细粒度的文法单元。本发明的方法对用户完全透明，不会给用户增加任何处理负担，用户用起来简单直观。而且，本发明很容易集成到现有的分析器生成框架中。断点类型分类算法可以区分不同的断点类型，可以更好的指导分析过程，同时又不会引入任何新的分析冲突。我们的调试方法，可以帮助用户更好地调试文法，可在一定程度上降低分析器的开发难度。