1、软件设计师-程序设计语言基础及答案解析(总分：42.00，做题时间：90 分钟)1.编译的优化工作对于下面程序段构造的控制流程图有_个基本块。（分数：1.00）A.1B.2C.3D.4已知文法 GS：SA0B1，AS11，BS00，该文法属于乔姆斯基定义的 (18) 文法，它不能产生串 (19) 。语言 L=ambnm0，n1)的正规表达式是 (20) 。一个文法 G=(N，T，P，S)，其中 N 是非终结符号的集合，T 是终结符号的集合，P 是产生式集合，S 是开始符号，令集合 V=NT，那么 G 所描述的语言是 (21) 的集合。程序设计语言引入“类”的概念是为了解决数据保护问题。C+语言
2、将类的成员封装在类体之中，使之具有一定的存取规则，这些规则规定了存取类的成员的权利，其中对于用 Private 说明的成员，它 (22) 。（分数：5.00）A.0 型B.1 型C.2 型D.3 型A.0011B.1010C.1001D.0101A.a*bb*B.aa*bb*C.aa*b*D.a*bA.由 S 推导出的所有符号串B.由 S 推导出的所有终结符号串C.V 中所有符号组成的符号串D.V 的闭包中的所有符号串A.既能被该类的成员函数访问，又能被外界直接访问B.只能被该类的成员函数访问，外界不能直接访问C.不能被该类的成员函数访问，只能被外界直接访问D.既不能被该类的成员函数访问，也不
3、能被外界直接访问某一确定性有限自动机(DFA)的状态转换图如图 2-2 所示，令 d=01219，则以下字符串中，不能被该 DFA 接受的是 (9) ，与该 DFA 等价的正规式是 (10) 。(其中， 表示空字符。)（分数：2.00）A.B.C.D.A.(-dd)d*E(-dd)d*(-dd)d*.d*E(-dd)d*B.(-dd)dd*(.)d*E(-dd)d*C.(-d)dd*E(-d)d*(-dd)dd*.d*E-E(-d)d*D.(-dd)dd*E(-dd)d*(-dd)dd*.d*E(-dd*dd*)假设某程序语言的文法如下：Sab(T)TTdSS其中：V T=a，b，d，(，)，
4、V NS，T，S 是开始符号。考查该文法，称句型(Sd(T)db)是 S 的一个 (33) ，其中， (34) 是句柄： (35) 是素短语； (36) 是该句型的直接短语； (37) 是短语。（分数：5.00）A.最左推导B.最右推导C.规范推导D.推导A.SB.bC.(T)D.sd(T)A.SB.bC.(T)D.sd(T)A.SB.S，(T)，bC.S，(T)，TdS，bD.Sd(T)dbA.Sd(T)dbB.d(T)C.TdD.Sd(T)d考查下列文法：G(V T,VN,E，P)其中：V T=+，*，(，)，i)VN=E，T，FE 是开始符号P： EE+TTTT*FFF(E)IF*F+T
5、 是该文法的一个句型，其中， (28) 是句柄， (29) 是素短语 (30) 是该句型的直接推导， (31) 是该句型的最左推导， (32) 是该文法的一个句子。（分数：5.00）A.FB.F*FC.F+TD.F*F+，TA.FB.F*FC.F+TD.F*F+TA.F*F+IB.F*F+T*FC.F*F+F*FD.i* i+TA.F*F+T*FB.F*F+TC.F*(E)+TD.(E)*F+TA.T+(i+i)B.i+(i+F)C.iD.(E)某一非确定性有限自动机(NFA)的状态转换图如图 2-6 所示，与该 NFA 等价的正规式是 (12) ，与该 NFA等价的 DFA 是 (13) 。
6、（分数：2.00）A.0*(01)0B.(010)*C.0*(01)0*D.0*(10)*A.B.C.D.2.程序设计语言提供了基本类型及其相关的操作，而_ 则允许开发者自定义一种新的类型及其相关的操作。（分数：1.00）A.对象B.实例C.类D.引用已知一不确定的有限自动机(NFA)如图 2-8 所示，采用子集法将其确定化为 DFA 的过程如表 2-1 所示。表 2-1 状态集表（分数：4.00）A.2B.4C.3D.5A.1，3，4，5，ZB.2，3C.6D.4，5，ZA.ZB.6C.4，5，Z)D.A.(01)*B.(0*1*)*001C.(0*1*)*0(01)*D.(0*1*)0(0
7、1)*某一确定有限自动机(DFA)的状态转换图如图 2-1 所示，该 DFA 接受的字符串集是 (7) ，与之等价的正规式是 (8) 。（分数：2.00）A.以 1 开头的二进制代码串组成的集合B.以 1 结尾的二进制代码串组成的集合C.包含偶数个 0 的二进制代码串组成的集合D.包含奇数个 0 的二进制代码串组成的集合A.1*0(01)*B.(01*0)*1*C.1*(01)0*D.1*(01*0)*3.编译程序进行词法分析时不能_。（分数：1.00）A.过滤源程序中的注释B.扫描源程序并识别记号C.指出出错行号D.查出拼错的保留字(关键字)4.文法 GS：SxSxy 所描述的语言是_ (n
8、0)。（分数：1.00）A.(xux)nB.xyxnC.xynxD.xnyxn5.下面的 C 程序代码段在运行中会出现_ 错误。int i=0；while(i10)；i=i+1；（分数：1.00）A.语法B.类型不匹配C.变量定义D.动态语义6.对于以下编号为、的正规式，正确的说法是_。(aa*ab)*b (ab)*b (ab)*aa*b（分数：1.00）A.正规式等价B.正规式等价C.正规式等价D.正规式互不等价7.与逆波兰式 ab+-c*d-对应的中缀表达式是_。（分数：1.00）A.a-b-c*dB.-(a+b)*c-dC.-a+b*c-dD.(a+b)*(-c-d)图 2-7 为一确定
9、有限自动机(DFA)的状态转换图，与该自动机等价的正规表达式是 (14) ，图中的 (15) 是可以合并的状态。（分数：2.00）A.a(ba)*bb(a*b*)*B.(ab)*bba*b*C.(a*b*)bb(ab)*D.(ab)*bb(a*b*)*A.0 和 1B.2 和 3C.1 和 2D.0 和 38.高级程序设计语言中用于描述程序中的运算步骤、控制结构及数据传输的是_。（分数：1.00）A.语句B.语义C.语用D.语法9.与正规式(ab)*等价的正规式为_。（分数：1.00）A.a*b*B.a*b*C.(a*b*)*D.(ab)*假设某程序语言的文法如下：SSaTTTTbRRTPdR
10、P PfSge其中：V T=a，b，d，e，f，g，V NS，T，R，P，S 是开始符号。那么，此方法是 (38) 方法。这种文法的语法分析通常采用优先矩阵，优先矩阵给出了该文法中各个终结符之间的优先关系 (大于，小于，等于，无关系)。在上述文法中，某些终结符之间的优先关系如下：b (39) a：f (40) g；a (41) a；d (42) d。（分数：5.00）A.正规文法B.算符文法C.二义文法D.属性文法A.大于B.小于C.等于D.无关系A.大于B.小于C.等于D.无关系A.大于B.小于C.等于D.无关系A.大于B.小于C.等于D.无关系10.对于下面的文法 GS，_ 是其句子(从
11、S 出发开始推导)。GS: SM(S，M) MPMP Pabc. xxz（分数：1.00）A.(a，f)B.(fac,bb)，gC.(abc)D.c,(da)软件设计师-程序设计语言基础答案解析(总分：42.00，做题时间：90 分钟)1.编译的优化工作对于下面程序段构造的控制流程图有_个基本块。（分数：1.00）A.1B.2C.3D.4 解析：分析 基本块的划分有以下 3 个步骤。第 1 步：满足下列条件之一的任意语句可以充当入口。程序的第一个语句；能由条件转移语句或无条件转移语句转移到的语句：紧跟在条件转移语句后面的语句。第 2 步：根据第 1 步求出的每一入口语句，构成其所属的基本块。由
12、该入口语句到另一入口语句(不包括该入口语句)之间的语句序列：由该入口语句到一转移语句(包括该转移语句)之间的语句序列：由该入口语句到一停止转移语句(包括该转移语句)之间的语句序列。第 3 步：凡是未被纳入某一基本块中的语句，都是程序中控制流程无法到达的语句，也是不会被执行到的语句，可以从程序中删除。根据上述步骤，我们知道所给程序段的第 1，4，8，10 句为入口，第 11 句是停止语句，没有要删除的语句。于是该程序段可分为 4 个基本块。已知文法 GS：SA0B1，AS11，BS00，该文法属于乔姆斯基定义的 (18) 文法，它不能产生串 (19) 。语言 L=ambnm0，n1)的正规表达式
13、是 (20) 。一个文法 G=(N，T，P，S)，其中 N 是非终结符号的集合，T 是终结符号的集合，P 是产生式集合，S 是开始符号，令集合 V=NT，那么 G 所描述的语言是 (21) 的集合。程序设计语言引入“类”的概念是为了解决数据保护问题。C+语言将类的成员封装在类体之中，使之具有一定的存取规则，这些规则规定了存取类的成员的权利，其中对于用 Private 说明的成员，它 (22) 。（分数：5.00）A.0 型B.1 型C.2 型D.3 型 解析：A.0011 B.1010C.1001D.0101解析：A.a*bb* B.aa*bb*C.aa*b*D.a*b解析：A.由 S 推导出
14、的所有符号串B.由 S 推导出的所有终结符号串 C.V 中所有符号组成的符号串D.V 的闭包中的所有符号串解析：A.既能被该类的成员函数访问，又能被外界直接访问B.只能被该类的成员函数访问，外界不能直接访问 C.不能被该类的成员函数访问，只能被外界直接访问D.既不能被该类的成员函数访问，也不能被外界直接访问解析：分析 对于空(1)，文法 GS的产生式集合中的产生式均符合左线性文法的产生式规则，因此 GS为左线性文法，即 3 型文法(正规文法)。对于空(2)，与正规文法 GS对应的正规表达式为(0110) +，该表达式无法产生字符串 0011。对于空(3)，根据语言 L 的定义，其包含的符号串为
15、 0 个或以上的 a 后面紧跟 1 个或以上的 b 组成的符号串，在各个答案中，只有 A 表示的含义与语言 L 相符。对于空(4)，由文法的定义直接得出答案。在 C+语言中，共有三个存取规则规定存取类的成员的权利，分别为 Public，Protected 和 Privateo 其中 Public 表示既能被该类的成员函数访问，也能被派生类的成员函数访问，且能被外界直接访问；Protected 表示既能被该类的成员函数访问，也能被派生类的成员函数访问，但不能被外界直接访问；Private 则表示只能被该类的成员函数访问，不能被派生类的成员函数访问，也不能被外界直接访问。故空(5)的答案选 B。某
16、一确定性有限自动机(DFA)的状态转换图如图 2-2 所示，令 d=01219，则以下字符串中，不能被该 DFA 接受的是 (9) ，与该 DFA 等价的正规式是 (10) 。(其中， 表示空字符。)（分数：2.00）A.B. C.D.解析：A.(-dd)d*E(-dd)d*(-dd)d*.d*E(-dd)d* B.(-dd)dd*(.)d*E(-dd)d*C.(-d)dd*E(-d)d*(-dd)dd*.d*E-E(-d)d*D.(-dd)dd*E(-dd)d*(-dd)dd*.d*E(-dd*dd*)解析：分析 DFA 能识别的字符串是指一条从初态节点到终态节点的路径上所有弧上的标记符所连
17、接龙的字符串。我们依次检查备选项看哪些字符串不能被 DFA 接受。首先看“3875”，这个字符扫中的元素全是数字，从初态 0 出发输入一个数字进入状态 1：在状态 1 输入一个数字还是回到状态 1，无法前进。所以不能被 DFA 接受。接着看“1.2E+5”，这个不用判断都可以知道不行，因为“+”在 DFA 中不能识别。再看“-123.”，该串能从初态 0 到达终态 5，所以能被只别。最后一个备选项中首字符“.”在初始状态无法被识别，所以不能被 DFA 识别。然后我们把 DFA 转化为正规式。首先可以排除 B 和 D，很显然(-dd)dd*所表达的串比所描述的多一个d。再看 Cs 选项中(-d)
18、dd*E(-d)d*表示不经过状态 5 的路径，而后面的 -dd)dd*.d*E-E(-d)d*)是指经过状态 5 的路径，所以 C 也被排除。这样答案只能选择 A 了。假设某程序语言的文法如下：Sab(T)TTdSS其中：V T=a，b，d，(，)，V NS，T，S 是开始符号。考查该文法，称句型(Sd(T)db)是 S 的一个 (33) ，其中， (34) 是句柄： (35) 是素短语； (36) 是该句型的直接短语； (37) 是短语。（分数：5.00）A.最左推导B.最右推导C.规范推导D.推导 解析：A.S B.bC.(T)D.sd(T)解析：A.SB.b C.(T) D.sd(T)
19、解析：A.SB.S，(T)，b C.S，(T)，TdS，bD.Sd(T)db解析：A.Sd(T)db B.d(T)C.TdD.Sd(T)d解析：分析 要正确解答本题需要清楚基本概念。最左(右)推导：任何一步推导过程 (， 都是句型)都是对 中的最左(最右)非终结符进行替换，这种推导为最左 (最右)推导。在形式语言中，最右推导常被称为规范推导。按照最左推导和最右推导的规则，最终都不可能推出原来的句型。最后可以看出句型Sd(T)db是由一般推导推出的，步骤如下。S(T)(TdS)(Tdb)Td(T)dbSd(T)db本题文法的推导树如图 2-10 所示。*所以，S 是句型相对于规则 TS 占的直接
20、短语，也是最左直接短语(句柄)。(T)尽句型相对于规则 S(T)的直接短语，对于问题 B，答案是正确的。素短语是一个短语，它至少包含一个终结符，并除自身外不包含其他的素短语。在问题 C 的备选答案中都满足条件，所以对于问题 C，答案都正确。b 是句型 Sd(T)db 相对于 Sb 的直接短语，S 是句型 Sd(T)db 相对于 TS 的直接短语， (T)是句型 Sd(T)db 相对于 S(T)的直接短语，所以问题 D 的答案为。由推导树可知，无论如何无法从 S 推导出 d(T)，Td 或 Sd(T)d，所以问题 E 的答案是。考查下列文法：G(V T,VN,E，P)其中：V T=+，*，(，)
21、，i)VN=E，T，FE 是开始符号P： EE+TTTT*FFF(E)IF*F+T 是该文法的一个句型，其中， (28) 是句柄， (29) 是素短语 (30) 是该句型的直接推导， (31) 是该句型的最左推导， (32) 是该文法的一个句子。（分数：5.00）A.F B.F*FC.F+TD.F*F+，T解析：A.FB.F*F C.F+TD.F*F+T解析：A.F*F+IB.F*F+T*F C.F*F+F*FD.i* i+T解析：A.F*F+T*FB.F*F+TC.F*(E)+TD.(E)*F+T 解析：A.T+(i+i)B.i+(i+F)C.i D.(E)解析：分析 根据形式文法的定义可直
22、接获得本题的答案。句型 F*F+T 的推导过程如下：EE+TT+ TT*F+TF*F+T，所以 F 是句型 F*F+T 相对于产生式 TF 的直接短语，又因为它是该句型的最左直接短语，所以 F 是该句型的句柄。同理，可分析出句型 F*F+T 的短语有 F，F*F，F*F+T。由于素短语中至少应含有一个终结符，所以 F 不是素短语：由于 F*F+T 中包含了短语 F*F，所以它也不是素短语。因此该句型的素短语是 F*F。因为句型 F*F+TF*F+T*F，所以 F*F+T*F 是该句型的直接推导。而 F*F+T，F*F+T*F 和 i*i+T 都不能由句型 F*F+T 直接推导出来。由于最左推导
23、是对句型右部的最左非终结符进行推导，所以在空(4)的选择答案中只有(E)*F+T 满足此条件。因为句子是仅含终结符的句型，而在空(5)的供选择答案中只有 i 有可能是句子，所以应该选择答案 C。某一非确定性有限自动机(NFA)的状态转换图如图 2-6 所示，与该 NFA 等价的正规式是 (12) ，与该 NFA等价的 DFA 是 (13) 。（分数：2.00）A.0*(01)0B.(010)* C.0*(01)0*D.0*(10)*解析：A. B.C.D.解析：分析 从 q0状态可以经过 q1状态回到 q0状态，同时也可以输入 0 回到 q0状态，或输入若干个 0后经过 q1状态再回到 q0状
24、态。所以该自动机识别的串等价于正规式(010)*。再利用子集法求出与该NFA 等价的 DFA。2.程序设计语言提供了基本类型及其相关的操作，而_ 则允许开发者自定义一种新的类型及其相关的操作。（分数：1.00）A.对象B.实例C.类 D.引用解析：分析 类是面向对象语言必须提供的、由用户定义的数据类型，它将具有相同状态、操作和访问机制的多个对象抽象成一个对象类。在定义了类以后，属于这种类的一个对象称为类实例或类对象。已知一不确定的有限自动机(NFA)如图 2-8 所示，采用子集法将其确定化为 DFA 的过程如表 2-1 所示。表 2-1 状态集表（分数：4.00）A.2 B.4C.3D.5解析
25、：A.1，3，4，5，ZB.2，3C.6D.4，5，Z 解析：A.ZB.6C.4，5，Z)D. 解析：A.(01)*B.(0*1*)*001C.(0*1*)*0(01)*D.(0*1*)0(01)* 解析：分析 将 NFA 转换为 DFA 一般用于集法。下面用子集法来进行转换。首先，K 0=_closure(0)=(S，1，2，3)，这是初始集，也就是初始状态。这里值得注意的一点是图中 表示空，从 S 到 1 是 箭头线，所以如果能到达 S，也就能到达 1。所以如果图 2-2 的初态实际上包含S，1，2，3 四个。因此在表 2-1 中，第一行第一列是S1，2，3。接下来对初态集S，1，2，3)
26、输入 0，即 K1=_closuremove(K 0，0)=1，3，4，5，Z，所以第一行 I0列对应的数据为1，3，4，5，Z。接着 K2=_closure(move(K 0，1)=2，3，所以第一行 I1列对应的数据为2，3。依次类推：令 K3=_closure(move(K 1，0)=1，3，4，5，6，Z，令 K4=_closure(move(K 1，1)=。最终求得 T1=1，3，4，5，6，Z，T 24，5，Z，T 3=，据此可以得出答案。某一确定有限自动机(DFA)的状态转换图如图 2-1 所示，该 DFA 接受的字符串集是 (7) ，与之等价的正规式是 (8) 。（分数：2.0
27、0）A.以 1 开头的二进制代码串组成的集合B.以 1 结尾的二进制代码串组成的集合C.包含偶数个 0 的二进制代码串组成的集合 D.包含奇数个 0 的二进制代码串组成的集合解析：A.1*0(01)*B.(01*0)*1*C.1*(01)0*D.1*(01*0)* 解析：分析 DFA 能接受的字符串是指一条从初态节点到终态节点的路径上所有弧上的标记符所连接成的字符串。本题初态、终态节点均为 q0，若字符串中遇到 0，则状态由 q0变为 q1，这样只有再次遇到 0，状态 q1才能回到终态 q0，因此该 DFA 接受的字符串是包含偶数个 0 的二进制代码串。所以正规式中也应该含有偶数个 0。3.编
28、译程序进行词法分析时不能_。（分数：1.00）A.过滤源程序中的注释B.扫描源程序并识别记号 C.指出出错行号D.查出拼错的保留字(关键字)解析：分析 词法分析的任务是对源程序从前到后(从左到右)逐个字符进行扫描，从中识别出一个个“单词”符号，所以不能识别记号。4.文法 GS：SxSxy 所描述的语言是_ (n0)。（分数：1.00）A.(xux)nB.xyxnC.xynxD.xnyxn 解析：分析 根据文法所描述的推导规则，推导过程是这样的：SxSxx 2Sx2x 3Sx3.x nSxnx nyxn同时又有xSxxyx；x 2Sx2x 2yx2，.因此从两个式子得出规律：字符串中间只有一个
29、y，两边有相同数目的 x。5.下面的 C 程序代码段在运行中会出现_ 错误。int i=0；while(i10)；i=i+1；（分数：1.00）A.语法B.类型不匹配C.变量定义D.动态语义 解析：分析 语义错误分为动态语义错误和静态语义错误，静态语义错误发生在编译阶段，动态语义错误发生在运行阶段。6.对于以下编号为、的正规式，正确的说法是_。(aa*ab)*b (ab)*b (ab)*aa*b（分数：1.00）A.正规式等价B.正规式等价C.正规式等价 D.正规式互不等价解析：分析 由于正规式产生的字符串为 a*b 或 ab*b，产生的字符串为 a*b 或 b*b，产生的字符串为 a*b 或
30、 b*b，故等价。7.与逆波兰式 ab+-c*d-对应的中缀表达式是_。（分数：1.00）A.a-b-c*dB.-(a+b)*c-d C.-a+b*c-dD.(a+b)*(-c-d)解析：分析 逆波兰式把运算符写在运算对象的后面，所以也称为后缀式。这种表示法的优点是根据运算对象和运算符的出现次序进行计算，不需要使用括号。用栈结构实现后缀式的计算是很方便的，一般的方法是：自左至右扫描后缀式，遇到运算对象时就将其压入栈中，遇到 k 元运算符时就从栈中弹出 k 项进行运算，并将结果压入栈中，当表达式被扫描完时，栈顶元素就是表达式的运算结果。图 2-7 为一确定有限自动机(DFA)的状态转换图，与该自
31、动机等价的正规表达式是 (14) ，图中的 (15) 是可以合并的状态。（分数：2.00）A.a(ba)*bb(a*b*)* B.(ab)*bba*b*C.(a*b*)bb(ab)*D.(ab)*bb(a*b*)*解析：A.0 和 1B.2 和 3 C.1 和 2D.0 和 3解析：分析 首先将途中状态分为终态和非终态两个子集，即(0，1，2，3)，再进行子集划分。观察第一个子集，输入 b 后，状态 0 转换为状态 1，而状态 1 转换为状态 2，因此1和2是可区别的。由于状态 2，3 输入字符 a 得到结果 3，输入字符 b 得到相同结果 2，所以子集2， 3是不可区别的。从而得到新的划分：
32、(0，1，2，3)，即 2 和 3 是可以合并的状态。因此第二空的答案选 B。重复子集划分步骤，发现新的状态无法再次划分。删除节点 3 得到新的状态转换图，根据正规式和有限自动机之间的转换规则可以得到与该自动机等价的正规表达式为a(ba)*bb(a*b*)*，从而第一空的答案选 A。8.高级程序设计语言中用于描述程序中的运算步骤、控制结构及数据传输的是_。（分数：1.00）A.语句 B.语义C.语用D.语法解析：分析 语法：由程序设计语言的基本符号组成程序中的各个语法成分(包括程序)的一组规则，其中由基本符号构成的符号(单词)书写规则称为词法规则，由符号(单词)构成语法成分的规则称为语法规则。
33、程序语言的语法可通过形式语言进行描述。语义：程序语言中按语法规则构成的各个语法成分的含义，可分为静态语义和动态语义。语用：表示构成语言的各个记号和使用者的关系，涉及符号的来源、使用和影响。9.与正规式(ab)*等价的正规式为_。（分数：1.00）A.a*b*B.a*b*C.(a*b*)* D.(ab)*解析：分析 正规式(ab)*表示字符 a 和 b 组成的任何长度的字符串(a 和 b 的位置任意)。a*b*表示由若干个 a 组成的字符串，或者是由若干个 b 组成的任何长度的字符串。a*b*萨表示由若干个 a 后跟若干个 b 所组成的任何长度的字符串(a 在 b 前面)。(ab)*表示每个 a
34、b 所组成的任何长度的字符串(ab 不能分离)。(a*b*)*表示由字符 a 和 b 组成的任何长度的字符串(若干个 a 后面跟若干个 b，b 后面再跟若干个 a)。只有(a*b*)*与(ab)*含义相同，因此正规式(ab)*与(a*b*)*是等价的。假设某程序语言的文法如下：SSaTTTTbRRTPdRP PfSge其中：V T=a，b，d，e，f，g，V NS，T，R，P，S 是开始符号。那么，此方法是 (38) 方法。这种文法的语法分析通常采用优先矩阵，优先矩阵给出了该文法中各个终结符之间的优先关系 (大于，小于，等于，无关系)。在上述文法中，某些终结符之间的优先关系如下：b (39)
35、a：f (40) g；a (41) a；d (42) d。（分数：5.00）A.正规文法B.算符文法 C.二义文法D.属性文法解析：A.大于 B.小于C.等于D.无关系解析：A.大于B.小于C.等于 D.无关系解析：A.大于 B.小于C.等于D.无关系解析：A.大于B.小于 C.等于D.无关系解析：分析 所谓算符文法，可以描述如下：如果在一个文法 G 中，不含有形如“UAB”的产生式，其中 A，BV n，则 G 为算符文法。也就是说，如果 G 是算符文法，那么 G 的任何产生式的右部都不会出现两个非终结符号相邻的情况，而且，对算符文法而言，也不会产生两个非终结符号相邻出现的句型。这种性质意味着
36、，如果把终结符号看做广义运算符，而把非终结符号看做广义运算的对象，则在算符文法的任何句型中，两相邻运算符之间的运算对象至多只有一个，而不会出现其间运算对象个数不确定的情况。这样就使得广义运算总是按照中缀形式出现的，对语法分析工作非常有益。对于给定的文法 G，可以逐个检查 G 的各产生式，查看它们的右部是否含有相邻出现的非终结符号，以确定 G 是否为算符文法，然后再构造相应的优先矩阵。若此矩阵中无多重定义的元素，同理则可确认一算符优先文法。在算符文法中，一般按照如下规则判断终结符之间的优先关系。当且仅当 G 中有形如“Uab”或者“UaBb”的产生式，a=b；当且仅当 G 中有形如“UaA”的产
37、生式，且有或者“A=+=b”或者“A= +=aB”时，ab；当且仅当 G 中有形如“UAb”的产生式，且有或者“A=+=a”或者“A= +=aB”时，ab。如果算符文法 G 的任何一对终结符号之间，至多只有 3 种算符优先关系等于、大于或者小于成立，则称 G 为算符优先文法。10.对于下面的文法 GS，_ 是其句子(从 S 出发开始推导)。GS: SM(S，M) MPMP Pabc. xxz（分数：1.00）A.(a，f)B.(fac,bb)，g C.(abc)D.c,(da)解析：分析 若文法 G 的开始符号为 S，那么从开始符号 S 能推导出的符号串称为文法的一个句型，即 是文法 G 的一个句型，当且仅当有如下推导*。若 X 是文法 G 的一个句型，且 *，则称 X 是文法 G的一个句子。
