编译试题——程序员部分.doc

有限状态自动机可用五元组（VT，Q，δ，q0，Qr）来描述，它可对应于__A__。设有一有限状态自动机 M 的定义如下： VT ={0，1} Q={ q0，q1，q2} δ定义为： δ(q0，0)= q1 δ(q1，0)= q2 δ(q2，1)= q2 δ(q2，1)= q2 Qr={ q2}。 M 是一个__B__有限状态自动机，它所对应的状态转换图为__C__，它所能接受的语言可以用正则表达式表示为__D__，其含义为__E__。供选择的答案： A：① 0型文法　　　　 ② 1型文法　　　　 ③ 2型文法 　　　④ 3型文法 B：①歧义的 　　　　　②非歧义的 　　　　③确定的 　　　　④非确定的 注：图中-表示开始状态，+表示终止状态。 D：① (0|1)* ② 00 (0|1)* ③ (0|1)*00 ④ 0 (0|1)*0 E：①由 0 和 1 所组成的符号串的集合 ②以 0 为头符号和尾符号、由 0 和 1 所组成的符号串的集合 　 ③以两个 0 为结束的，由 0 和 1 所组成的符号串的集合 ④以两个 0 为开始的，由 0 和 1 所组成的符号串的集合 4 3 2 2 4 语法分析方法大体上可分成自上而下和自下而上两种。自下而上分析法，是从输入符号串开始逐步进行_A_，直至_A_成文法的起始符号。自上而下分析法，则是从文法的起始符号开始反复使用产生式进行_B_直至_B_出输入符号串。 　　算符优先文法是一种自下而上分析方法，其文法的特点是文法的产生式中_C_。自上而下的分析方法，通常要求文法的产生式_D_ ，如_E_文法就是一种可以自上而下分析的文法。 供选择的答案 　　A、B：①递归　　　　　②综合　　　　　③回归　　　　　④推导 　　　　　⑤分解　　　　　⑥归约 　　　 C：①不含两个相邻的非终结符　　　　②不含两个相邻的终结符 　　　　　③不含ε产生式　　　　　　　　　 ④不含长度为l的产生式 　　　 D：①不以非终结符开头　　　　　　　②不以终结符开头 　　　　　③不含左递归　　　　　　　　　　④不含右递归 　　　 E：① LR(I)　　　　② LL(I)　　　　③ SLR(I)　　　　④LALR(I) 6 4 1 3 2 假设某程序语言的文法如下： Ｓ→ＳａＴ∣Ｔ T → T b R∣Ｒ Ｒ→ Ｐd Ｒ∣Ｐ Ｐ→ fＳｇ∣e 　　其中：VT＝｛a, b, d, e, f, g｝；VN＝｛S,T,R,P｝；S是开始符号。那么，此方法是＿A＿方法。这种文法的语法分析通常采用优先距阵，优先矩阵给出了该文法中各个终结符之间的优先关系系〔大于，小于，等于，无关系）。在上述文法中，某些终结符之间的优先关系如下： b＿B＿a; f＿C＿g; a＿D＿a; d＿E＿d。 供选择的答案 A：①正则文法　　　　　 ②算符文法　　　　　 ③二义文法　　　　　 ④属性文法 B：①大于 　　　　　　　②小于　　　　　　　 ③等于 　　　　　　　④无关系 C：①大于 　　　　　　　②小于 　　　　　　　③等于 　　　　　　　④无关系 D：①大于 　　　　　　　②小于 　　　　　　　③等于　　　　　　　 ④无关系 E：①大于 　　　　　　　②小于 　　　　　　　③等于　　　　　　　 ④无关系 2 1 3 1 2 假设某程序语言的文法如下： S → a | b | (T) T → T d S | S 其中：VT = {a，b，d，(，)}，VN= {S，T}，S是开始符号。 考察该文法，称句型 (S d (T) d b )是S的一个_A_，其中：_B_是句柄；_C_是素短语；_D_是该句型的直接短语；_E_是短语。 供选择的答案： A：①最左推导 　　　　　②最右推导 　　　③规范推导 　　　　　　　④推导 B、C：① S　　　　　　　② b 　　　　　　③ (T) 　　　　　　　　　④S d (T) D：①S　　　　　　　　　②S，(T)，b　　　③S，(T)，T d S，b 　　　④ ( S d ( T ) d b ) E：① ( S d ( T ) d b)　② d ( T ) 　　　③ T d 　　　　　　　　　④ S d ( T ) d 4 1 3 2 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是该文法的一个句型,其中 ,__(16)__是句柄 ,__(17)__是素短语。__(18)__是该句型的直接推导,__(19)__是该句型的最左推导。__(20)