1.语法分析

语法分析的任务是根据语言的语法规则，分析单词串是否构成短语和句子，即表达式、语 句和程序等基本语言结构，同时检查和处理程序中的语法错误。程序设计语言的绝大多数语法 规则可以采用上下文无关文法进行描述。语法分析方法有多种，根据产生语法树的方向，可分为自底向上和自顶向下两类。

1）上下文无关文法

上下文无关文法属于乔姆斯基定义的2型文法，被广泛地用于表示各种程序设计语言的语 法规则。对于上下文无关文法GT5]= iVN, VT' P, S），其产生式的形式都是其中de VN,

若不加特别说明，下面用大写英文字母J、B、C等表示非终结符，？小写英文字母a、b, c 等表示终结符号，《，v,w等表示终结符号串，小写希腊字母《、p' y、3等表示终结符和非终 结符混合的文法符号串。由于一个上下文无关文法的核心部分是其产生式集合，所以文法可以 简写为其产生式集合的描述形式。dSMHmi

（1）规范推导（最右推导）。如果在推导的任何一步（其中《、#是句型），都是对ct 中的最右（最左）非终结符进行替换，则称这种推导为最右（最左）推导。最右推导常称为规 范推导。

（2）短语、直接短语和句柄。设a职是文法G的一个句型，即^二^部，且满足

和4:^5,则称<5是句型a砂相对于非终结符J的短语。特别地，如果有则称3是句 型cc8p相对于产生式3的直接短语。一个句型的最左直接短语称为该句型的句柄。

【例2.4】对于简单算术表达式，可以用下面的文法G[幻进行描述。

G[?]= i{EyTyF}, {+, *, （，）， id）， P, E）

P={E-*T]E+T, T-*F\T*F, F-（E）\id}

可以证明，W+iW*以是该文法的句子。下面用最右推导的方式从文法的开始符号出发推导 出该句子。为了表示推导过程中相同符号的不同出现，给符号加一个下标。

E=> +7] => +7^ *Fy => E' +T2 *id3 ^ E] +F2 *id3 => E' +id2 *id3

=>T3+ id2 * id3 => F2 + id2 * id3 => id{ + id2 * id3 该推导过程可以用树型结构进行描述。

由于五=>^+r2*^,且72=;>以2,所以站是句型五rHW2*站的相对于非终结符r的短语。

由于？；F3+id2*id3, KF3 => id,,所以姊是句型/w2+城相对于非终结符尸的短语， 也是相对于产生式F-id的直接短语。

由于五乌+7],且7;^>吨*岣，所以吣*吣是句型私+站*吣的相对于非终结符r的 短语。

由于E^id' *id2 + id3,所以idfidrHds是句型idfidz+ieh的相对于非终结符E的短语。 实际上城，i<h, idz,和姑*都是句型姑*以2+城的短语，而且袖、id2、id3 均是直接短语，其中是最左直接短语，即句柄。

返回目录：软件设计师程序语言基础知识汇总

编辑推荐：软件设计师教程之计算机系统知识