- 上一篇 信息系统监理师专题三：进度、投资控制 [2008-4-7 15:35:33]
| 微软认证MCSE2003:Security | 微软认证MCSE2003+MCDBA |
| 国家软考-网络工程师 | 华为认证网络工程师（HCNE） |
| Adobe平面设计师(ACCD) | Adobe网络设计师（ACCD） |
| 国家信息化网络安全工程师 | CEAC网络应用工程师 |
| CEAC微机装配与维护工程师 | 数据恢复职业技术培训 |
| 黑客系列：黑客攻防实战 | 瑞星病毒防范职业技能培训 |
主要内容： ① 词法分析、语法分析的基本理论和方法。
② 有限自动机的基本工作原理，NFA向DFA的转换。
软件设计师专题五：编译原理(20080402)在线专题授课音视频
（本课程正式学员可登录学习系统，进入对应课程，在窗口左边的“课程资料室”内进行在线浏览。）重点：后缀表示（逆波兰式）、正则式、句型推导、DNF与正则式。
07上半年 后缀表示 1分
●表达式“(a+b)*(c-d)”的后缀表示为（48）。
（48）A. ab+cd-* B. abcd+-* C. ab+*cd- D. abcd*+-
正解：A
07下半年 后缀表示 集合的正规式表示 2分
● 集合 （21） 。
（21）A. 可用正规式“ ”表示
B. 不能用正规式表示，但可用非确定的有限自动机识别
C. 可用正规式“ ”表示
D. 不能用正规式表示，但可用上下文无关文法表示
正解：D
● 表达式“X = A + B ? (C ? D)/E”的后缀表示形式可以为 （22） （运算符优先级相同时，遵循左结合的原则）。
（22）A. XAB + CDE/??= B. XA+BC?DE/?=
C. XABCD??E/+= D. XABCDE+??/=
正解：C
2006年上半年考题
●对于下面的文法G[S]，___(44)___是其句子(从S出发开始推导)。
G(S]：S→M1(S,M) M→*P|MP P→a|b|c|…|x|x|z
(44)A．((a,O)) B．((fac,bb),g) C．(abc) D．(c,(da))
正解：B
推导过程：S->(S,M)->((S,M),P)->((M,MP),g)->((MP,PP),g) ->((MPP,bb),g)->((PPP,bb),g)->((fac,bb),g)
通过First集就可以判断了
●与逆波兰式ab+-c*d-对应的中缀表达式是___(45)___。
(45)A．a-b-c*d B．-(a+b)*c-d C．a+b*c-d D．(a+b)*(-c-d)
正解：B
其它
1. 考察下列文法: G( VT ,VN ,E ,P )
其中: VT = { + , * ,( , ) , i }
VN = { E , T , F }
E 是开始符号
P:
E → E + T | T
T → T * F | F
F → (E)| i
F*F+T是该文法的一个句型,其中___(1)___是句柄 ,___(2)___是素短语。___(3)___是该句型的直接推导,___(4)___是该句型的最左推导。___(5)___是该文法的一个句子。
【供选择的答案】
（1） A. F B. F*F C. F+T D. F*F+,T
（2） A. F B. F*F C. F+T D. F*F+T
（3） A. F*F+i B. F*F+T*F C. F*F+F*F D. i*i+T
（4） A. F*F+T*F B. F*F+T C. F*(E)+T D. (E)*F+T
（5） A. T+(i+i) B. i+(i+F) C. i D. (E)
【参考答案】（1）A （2）B （3）B （4）D （5）C
由语法树图可知：
短语有：F、F*F、F*F＋T。
F为句柄，F*F为素短语、i为文法的一个句子。
直接推导：从一个句型一步就能推导出另一个句型：
F*F＋T→F*F＋T*F
最左推导：F*F＋T→E*F＋T
因此，正确答案为A、B、B、D、C。
2. 假设某程序语言的文法如下：
S→a | b | (T)
T→TdS | S
其中，VT={a,b,d,(,)}，VN={S,T}，S是开始符号。考查该文法，称句型(Sd(T)db)是S的一个___(1)___。其中___(2)___是句柄；___(3)___是素短语；___(4)___是该句型的直接短语；___(5)___是短语。
【供选择的答案】
（1） A. 最左推导 B. 最右推导 C. 规范推导 D. 推导
（2） A. S B. b C. (T) D. Sd(T)
（3） A. S B. b C. (T) D. Sd(T)
（4） A. S B. S,(T),b C. S,(T),TdS,b D. (Sd(T)db)
（5） A. (Sd(T)db) B. d(T) C. Td D. Sd(T)d
【参考答案】（1）D （2）A （3）C （4）B （5）A
每个句型对应一棵语法树
每棵语法树的叶子结点从左到右排列构成一个句型
每棵语法树的子树的叶子结点从左到右排列构成一个短语
每棵语法树的简单子树（只有父子两层结点的叶子结点从左到右排列构成一个简单(直接)短语
每棵语法树的最左简单子树的叶子结点从左到右排列构成句柄
素短语是至少包含一个终结符的短语，但它不能包含其它素短语
最左素短语是指处于句型最左边的那个素短语.
最左推导：在每个推导过程中，总是首先考虑对当前最左边的非终结符号进行推导
最右推导：在每个推导过程中，总是首先考虑对当前最右边的非终结符号进行推导
【解析】
S
/ | \
( T )
/ | \
T d S
/ | \ |
T d S b
| /|\
S ( T )
一个句型的语法树中任一子树叶结点所组成的符号串都是该句型的短语，当子树中不包含其他更小的子树时，该子数叶结点所组成的字符串就是该句型的直接短语。
因此本题的直接短语的为 S 、（T）、b，短语有S、（T）、b、Sd（T)、Sd（T）db 、（Sd（T）db）。d不是直接短语,因为d所在的树还有子树所以它不是!
一个句型的最左直接短语称为该句型的句柄 素语是一个短语，它至少含有一个终结符，而且除它自身以外不再含有更少的素短语，对于句型（Sd（T）db）的素短语是（T）、b.
解答本题要搞清楚基本概念，下面具体分析各个问题。
先来看问题A。最左(右)推导：任何一步推导过程σ→β(其中σ、β是句型)都是对σ中的最左(最右)非终结符进行替换，这种推导为最左(最右)推导。在形式语言中，最右推导常被称为规范推导。
题中的句型(Sd(T)db)的第一步肯定是由S→(T)→(TdS)得出的。按照最左推导的规则(Tds)→(TdSdS)→(SdSdS)，最终不可能推出原来的句型。
按照最右推导的规则(Tds)→(Tdb)→(Td(T)db)，最终不可能推出原先的句型。
最后可以看出句型(Sd(T)db)是由一般推导推出的，步骤如下：
S→(T)→(Tds)→(Tdb)→(Td(T)db)→(Sd(T)db)
所以正确答案是④。
再来看问题B～E。来文法，S是文法的开始符号，αβδ是文法G的一个句型。如果有S→αAδ，且A→β，则称β是句型αβδ相对于非终符A的短语。特别是如有Aβ，则称β是句型αβδ相对于规则A→β的直接短语。一个句型的最左直接短语称为该句型的句柄。
本文法推导树如下：
S
/ | \
( T )
/ | \
T d S
/ | \ |
T d S b
| /|\
S ( T )
所以，S是句型相对于规则T→S的直接短语，也是最左直接短语(句柄)。(T)是句型相对于规则S→(T)的直接短语，对于问题2，选择A是正确的。
素短语是一个短语，它至少包含一个终结符，并除自身外不包含其他的素短语。所以，问题3的答案C正确。
d是句型相对于规则S→d的直接短语，则问题4的答案B正确。
由推导树可知，无论如何，无法由S推导出d(T)、Td或Sd(T)d，所以问题5的答案A正确。
●若正规表达式r=(a|b|c)(0|1)*，则L(r)中有（1）个元素。
[供选择的答案]
（1）A．12 B．18 C．6 D．无穷
[参考答案]
（1）D
[试题分析]
在本题中要求的根据正规表达式，确定其正规集合的元素个数。这里关键是理解闭包的概念。因为式中有（0|1）*，因此可以表示任意长度的0串或者1串。选D。
站内检索： |
 |