带回溯的自上而下语法分析的困难和缺点_青藤(7)de博客_百度空间

首先是文法的左递归性问题。一个文法是含有左递归的,如果存在非终结符P
含有左递归的文法将使上述的自上而下的分析过程陷入无限循环。即,当试图用P去匹配输入串时,我们会发现,在没有识别任何输入符号的情况下,又得重新要求P去进行新的匹配。因此,使用自上而下分析法必须xx文法的左递归性。

其次,由于回溯,就碰到一xxx烦事情。如果我们走了一大段错路,{zh1}必须回头,那么,就应把已经做的一大堆语义工作(指中间代码产生工作和各种表格的簿记工作)推倒重来。这些事情既麻烦又费时间,所以,{zh0}应设法xx回溯。

第三,在上述的自上而下分析过程中,当一个非终结符用某一候选匹配成功时,这种成功可能仅是暂时的。例如,就文法(4.1)而言,考虑输入串x**y。若对A首先使用第二个候选式,A将成功地把它的{wy}子结*匹配于输入串的第二个符号。但S的第三个子结y与第三个输入符号*不匹配。因而,导致了无法识别输入串x**y是一个句子的事实。然而,若A首先使用它的{dy}个候选**,则整个输入串即可获得成功分析。这意味着,A首先使用第二个候选所得的成功匹配是虚假的。由于这种虚假现象,我们需要更复杂的回溯技术。一般说,要xx虚假匹配是很困难的。但若从最长的候选开始匹配,虚假匹配的现象就会减少一些。

第四,当最终报告分析不成功时,我们难于知道输入串中出错的确切位置。

{zh1},由于带回溯的自上而下分析实际上采用了一种穷尽一切可能的试探法,因此,效率很低,代价极高。严重的低效使得这种分析法只有理论意义,而在实践上价值不大。

注:带回溯的自上而下语法分析
这是自顶向下分析的一般方法,即对任一输入符号串,试图用一切可能的方法,从识别符号出发,根据文法自上而下地为输入串建立一棵语法树。

  下面用一个简单例子来说明这种过程:

  假定有文法G[S]:

  S→cAd         
  A→ab|a 以及输入串w=cad

  为了自上而下地构造w的语法树, 我们首先按文法的识别符号产生根结点S,并让指示器IP指 向输入串的{dy}符号c。然后,用S的规则(此处左部为S的规则仅有一条)把这棵树发展为图3-1-1(a)。 我们希望用S的子结从左至右匹配整个输入串w。首先,此树的最左子结是终结符c为标志的子结,它和输入串的{dy}个符号相匹配。 于是,我们就把IP调整为指向下一输入符号a,并让第二个子结A去进行匹配,非终结符A有二个选择, 我们试着用它的{dy}个选择去匹配输入串, 于是把语法树发展为图3-1-1(b)。子树A的最左子结和IP所指的符号相符,然后我们再把IP调为指向下一符号d并让A的第二个子结进入工作。但A的第二个子结为终结符号b,与IP当前指的符号d不一致。因此,A宣告失败。 这意味着A的{dy}个选择此刻不适用于构造w的语法树。这时,我们应该回头(回溯)看A是否还有别的选择。
    
           图3-1-1 语法树

  为了实现回溯, 我们一方面应把A的{dy}个选择所生长的子树注销掉;另一方面,应把IP恢复为进入A时的原值, 也就是让它重新指向第二输入符号a。现在我们试探用A的第二个选择,即考虑生成图3-1-1(c)的语法树。由于子树A只有一个子结a,而且,它和IP所指的符号相一致,于是,A完成了匹配任务。在A获得匹配后,指示器指向下一个未被触及的符号d。

  在S的第二子结A完成匹配后,接着就轮到第三个子结d进行工作。由于这个子结和{zh1}一个输入符号相符,于是,我们完成了构造语法树的任务,证明了w是文法G[s]的一个句子。

  上述自顶向下地为输入符号w建立语法树的过程, 实际上也是设法建立一个最左推导序列,以便通过一步步推导将输入串推导出来。很明显,对于输入串w可以通过如下的推导过程将其推导出来:SCAdcad

  所以用最左推导,是因为我们对输入串是自左向右扫描的,只有使用最左推导,才能保证按扫描顺序去匹配输入串。在上述推出符号串w的过程中, 由于出现在符号串中的非终结符号只有一个,因此,未明显地表现出最左推导的性质。

  根据以上分析,不难编出程序来实现这种分析的算法。但是,上述这种自顶向下的分析算法存在着一定的困难和缺点。困难表现在不能为左递归文法构造自顶向下的语法分析器 (上述所举例子的文法G[s]是不具有在递归性的)。缺点主要表现在存在着回溯问题。当然,应用带回溯的自顶向下的分析算法还必须将文法规则存放于内存。下面将具体介绍这种分析算法所存在的问题及其解决办法。



郑重声明:资讯 【带回溯的自上而下语法分析的困难和缺点_青藤(7)de博客_百度空间】由 发布,版权归原作者及其所在单位,其原创性以及文中陈述文字和内容未经(企业库qiyeku.com)证实,请读者仅作参考,并请自行核实相关内容。若本文有侵犯到您的版权, 请你提供相关证明及申请并与我们联系(qiyeku # qq.com)或【在线投诉】,我们审核后将会尽快处理。
—— 相关资讯 ——