2012年软考系统分析师经典教程：重点与难点

　　2.5.3 语法分析

　　语法分析的任务是识别由词法分析给出的单词符号序列是否为给定文法的正确句子(程序)。语法分析常用的方法有两类：

　　◆自底向上分析方法(LR分析法和算符优先分析法)

　　也称为移进-归约分析法。对“可归约串”刻画的不同，形成两种不同的分析方法，即规范归约分析法和算符优先分析法。

　　◆自顶向下分析方法

　　也称为面向目标的分析方法。存在两种分析方法，递归子程序法和预测分析法，都使用LL(1)文法来进行语法分析。

　　例题：假设某程序语言的文法如下：

　　S→a | b | (T)

　　T→TdS | S

　　其中，VT={a,b,d,(，)}，VN={S,T}，S是开始符号。

　　考查该文法，称句型(Sd(T)db)是S的一个A 。其中B是句柄;C是素短语;D是该句型的直接短语;E是短语。

　　A： ①最左推导 ②最右推导 ③规范推导 ④推导

　　B： ①S ②b ③(T) ④Sd(T)

　　C： ①S ②b ③(T) ④Sd(T)

　　D： ①S ②S,(T)，b ③S,(T)，TdS,b ④(Sd(T)db)

　　E： ①(Sd(T)db) ②d(T) ③Td ④Sd(T)d

　　此句型的语法树如下所示：

　　S

　　(T)

　　(T d S)

　　(T d S b)

　　(S (T))

　　从语法树我们可以看出，短语就是位于同一个非终端结点的所有叶子结点，比如S、Sd(T)、Sd(T)db就是是相对于T的短语，b、(T)、(Sd(T)db)是相对于S的短语。而直接短语则进一步要求这些叶子结点的非终端结点是它们的直接父结点。因此可以S、(T)、b都是该句型的直接短语。语法树上最左的直接短语就是句柄，本题中是S。

　　所谓素短语是指这样一个短语，它至少含有一个终结符，并且除它自身之外不再含任何更小的素短语。最左素短语则指处于句型最左边的那个素短语。

　　最左推导是指任何一步推导过程σ→β，都是对σ中的最左非终结符进行替换。因此，在语法树中也很容易看出，如果语法树中的只有最左的非终结符结点(包括各级结点)具有其子树，则它就是最左推导。最右推导与之类似，最右推导也称规范推导。

　　相关推荐：

　　2012年软考系统分析师考试60天完美复习计划

　　2012年软件水平考试网络工程师章节笔记讲义汇总

　　2012年上半年软件水平考试成绩查询汇总