现有的上下文无关语法分析算法可分成两类。一类是用于分析程序设计语言的。它的作用范围是上下文无关语法的一个很小的特定子集，足够为程序设计语言所用。属于这类算法的有LL分析算法、LR分析算法、优先级(Precedence)算法、论断(Predictive)算法等。这些算法在它们自己的作用范围内效率较高。另一类用于一般的上下文无关语法。这类算法包括Earley算法、Cocke_Younger_Kasami算法。由于作用范围是一般的上下文无关语法，这类算法必须处理许多困难复杂的语言现象，这是程序设计语言中没有的。所以和前一类算法相比，这类算法效率较低。上下文无关语法分析算法出现了两个极端。其一是高效率但不能进行自然语言语法分析。其二是虽然能分析自然语言但效率太低。
下面简要介绍一下LR语法分析器算法过程。
LR语法分析算法是一种移位-归约（Shift-Reduce）算法。根据LR语法分析表来决定下一步要做什么。以下是一个例子。
开始时，输出缓冲器中放的是句子“MY CAR HAS A RADIO.”
Inputbuffer=MY CAR HAS A RADIO.$（“$”是句子结束符）
系统所用的语法规则是：（带*的表示终结符）
(1）S →NP VP
(2) S→SPP
(3) NP → *det *n
(4) PP → *prep NP
(5）VP →*v NP
由系统语法规则产生的LR语法分析表见表1。
几点说明：
（1）语法分析表分为Action表和Goto表。在Action表中，入口“shn”表示的意思是：从输入中取出一个词放入栈，并转到状态n。入口“ren”表示的意思是：用规则n来对栈中元素进行归约。入口“acc”表示accept。即句子可被接受为正确句子。空表示错误。
（2）Goto表表示运用规则进行归约后分析器必须转向的新状态。新状态是由当前状态以及归约得到的非终结符决定的。
（3）栈顶的数字表示当前状态。输入缓冲区包含输入的句子的每个词并在句末加“$”为结束符。
现在来看句子：MY CAR HAS A RADIO.的分析过程。
首先分析器先看到“MY”这个词，其词性为*det。从Action表中查到sh3，于是从输入缓冲区中取走词“MY”，把“*det”推入栈，转到状态3，即把“3”推入栈。接着看到词“CAR”，是名词*n，查表得sh8，把*n和8推入栈。缓冲区此时变为HAS A RADIO $。下个词是HAS，其类别是*v，查表得re3。于是分析运用规则3，即NP一>*det *n，把*det和*弹出后，0成为栈顶，把规则左部的NP推入栈，查Goto表的状态0遇到NP就转向状态2，则把“2”推入栈，此时缓冲区仍为HAS A RADIO $.，因为我们并未对HAS作移入处理。经过几步分析后，分析器找到了Action“accept”，这即是分析器结束分析的信号。
责任编辑：admin
上一篇：双向图算法分析器
下一篇：语法分析词典
微信公众号搜索“译员”关注我们，每天为您推送翻译理论和技巧，外语学习及翻译招聘信息。