发布时间 : 星期四 文章编译原理小题答案更新完毕开始阅读dc0302b0a26925c52dc5bf8f
四、简答题
1、什么是句子？ 什么是语言? 答：
设G是一个给定的文法，S是文法的开始符号，如果S=>*x（其中x∈Vt*），则称x是文法的一个句子。
设G[S]是给定文法，则由文法G所定义的语言L(G)可描述为 L(G)＝{x│S=>*x,x∈VT*}
2、已知文法G[E]为：
E→T|E+T|E-T T→F|T*F|T/F F→（E）|i
① 该文法的开始符号（识别符号）是什么？
②请给出该文法的终结符号集合VT和非终结符号集合VN。 ③ 找出句型T+T*F+i的所有短语、简单短语和句柄。
答：① 该文法的开始符号（识别符号）是E。 ②该文法的终结符号集合VT={+、-、*、/、（、）、i}。 非终结符号集合VN={E、T、F}。 ③句型T+T*F+I的句柄为第一个T。
3、已知文法G[S]为：
S→dAB A→aA|a B→Bb|ε
① G[S]产生的语言是什么？
② G[S]能否改写为等价的正规文法？
答：① G[S]产生的语言是L(G[S])={da^nb^m│n≥1,m≥0}。 ② G[S]能改写为等价的正规文法,其改写后的等价的 正规文法G[Sˊ]为：
Sˊ→dA
A →aA|aB|a B →bB|b
5、证明下面文法G[N]是二义性文法。
G[N]： N →SE∣E S →SD∣D E →0∣2∣10
D →0∣1∣2
7、简述DFA与NFA有何区别 ? 答：
主要区别在于，1.DFA没有ε转换；2.DFA的状态转换函数是单值映射，即当前状态输入一个字符后转换到下一个状态，而NFA的状态转换函数是非单值映射，也就是说当前状态输入一个字符后可以转换到下面N个状态。
8、试给出非确定自动机的定义。 答：
一个非确定的有穷自动机（NFA）M是一个五元组：M=（S，Σ，move，s0 ，F）。 其中:
1. 一个有限的状态集合S；
2. Σ是一个输入符号集合，ε不在Σ中； 3. move是状态转换函数，是在S×Σ*→S的子集的映射，即，move: S×Σ*→2S ；表明在某状态下对于某输入符号可能有多个后继状态；
4. s0是唯一的开始状态；
5. F是接受（或终止）状态集合，且F属于S一个子集。
9、为正规式（a|b）*a(a|b) 构造一个等价的确定的有限自动机。
答：
10、构造正规式相应的 NFA : 1(0|1)*101
12、已知文法 G[S] 为： S→dAB A→aA|a B→Bb|ε
G[S] 产生的语言是什么？
13、编译过程一般分为几个阶段？各阶段的输入输出分别为什么？
15、在LL(1)分析法中，LL分别代表什么含义? 答：
第一个L代表从左到右的扫描，第二个L代表每次进行最左推导。
16、文法G为： S→aAB A→a B→ α|β|γ
则判断G为LL（1）文法的条件是： 17、文法G=({A, B, S}, {a, b, c}, P, S) 其中P为： S→Ac|aB A→ab B→bc
该文法是二义的吗？说明理由。 18、文法G=({E}, {+, *, i, (, )}, P, E)其中P为： E→i E→E+E E→E*E E→(E)
该文法是二义的吗？说明理由。
19、自顶向下分析思想是什么？ 答：
从开始符出发导出句型并一个符号一个符号地与给定终结符串进行匹配。如果全部匹配成功，则表示开始符号可推导出给定的终结符串。因此判定给定终结符号串是正确句子。
25、简单优先方法基本思想是什么？
28、语法制导翻译方法的基本思想是什么?
33、给定下列中缀式，分别写出等价的后缀式和四元式(运算符优先级按常规理解)。
(1)(a＋b*c)/(a＋b)－d