【摘要】:同样,推导过程也存在相应的逆过程,称为归约。对于合法的输入符号串而言,这种从输入符号串出发,经过n次替换最终得到文法开始符的操作就是归约。在形式语言中,通常将最左归约称为规范归约,而将最右推导称为规范推导。读者必须注意,这只是一个形式语言学中的专有名词而己,并不表示规范归约与规范推导就是语法分析器的核心方法。例3-7 使用最左归约的方法验证句子3*5+(1-i)。
许多数学运算都定义了相应的逆运算或者逆操作。例如,乘法的逆运算就是除法,导数的逆运算就是不定积分。同样,推导过程也存在相应的逆过程,称为归约(reduction)。归约思想主要源于一种自下而上的语法分析方法一一“移进一归约”法。这种方法的思想是借助于一个暂存符号的栈把输入符号一个个地移进到栈里,当栈顶符号串形成某个非终结符的一个候选式时,把栈顶这部分符号串替换为该产生式的左部非终结符。通常,将这种栈顶的可归约的符号串称为句柄(handle)。对于合法的输入符号串而言,这种从输入符号串出发,经过n次替换最终得到文法开始符的操作就是归约。当然,如果输入的符号串无法归约得到文法开始符,即说明该符号串是非法的。
归约与推导类似,同样也存在最左归约与最右归约之分。最左归约对应的逆过程就是最右推导,而最右归约对应的逆过程正是最左推导。在形式语言中,通常将最左归约称为规范归约,而将最右推导称为规范推导。读者必须注意,这只是一个形式语言学中的专有名词而己,并不表示规范归约与规范推导就是语法分析器的核心方法。本书所讨论的基于推导的语法分析器恰恰是使用最左推导方法实现的。下面,笔者通过一个实例讲解归约的过程。
例3-7 使用最左归约的方法验证句子3*5+(1-i)。归约步骤如下所示:(www.daowen.com)
归约是一种重要的语法分析思想,而基于归约的语法分析法主要有LR分析法、算符优先分析法等。由于Neo Pascal语法分析器是基于推导实现的,因此,本书只详细讨论基于推导的语法分析器的设计与实现。如果读者对基于归约的语法分析器感兴趣,可以参考“龙书”或其他相关资料。
免责声明:以上内容源自网络,版权归原作者所有,如有侵犯您的原创版权请告知,我们将尽快删除相关内容。
有关编译器设计之路的文章