编译原理各章习题.pdf

编译原理各章习题第⼆章⾼级语⾔及其语法描述1、设有⽂法G[S]：S→NN→D|NDD→0|1|2|…|9试写出028和4321的最左推导和最右推导过程。2、证明⽂法G[S]是⼆义性⽂法：S→ifEthenSelseS|ifEthenS|sE→0|13、设有⽂法G[E]：E→E-T|TT→T/F|FF→i|(E)（1）试写出i/(i-i-i)的推导树。（2）试写出（F-i）/F的短语、简单短语和句柄。4、设∑={0,1}，请给出∑上下列语⾔的⽂法（1）所有以0开头的串（2）所有以0开头，以1结尾的串5、证明⽂法G1和G2等价G1：S→0S1，S→01G2：A→0R，A→01，R→A1第三章有限状态⾃动机和词法分析1、请⽤中⽂描述下列正规式表⽰的正规集（1）0(0|1)*0（2）0*10*10*10*2、试写出∑＝{0，1}上下列集合的正则表达式：（1）所有以1开始和结束的符号串。（2）恰含有3个1的所有符号所组成的集合。（3）集合{01，1}。（4）所有以111结束的符号串。3、试写出∑＝{0，1}上下述集合的正则表达式：（1）试写出⾮负整数集的正则表达式。（2）试写出以⾮5数字为头的所有⾮负整数集的正则表达式。4、试将图3.1中所⽰的有限状态⾃动机M最⼩化。图3.1M的状态转换图5、设∑＝{a,b}，试构造下述正则表达式的确定性有限状态⾃动机：（1）a(a|b)*baa（2）(a|b)*bbb*6、对于下列的状态转换矩阵：（1）分别画出相应的状态转换图。（2）⽤⾃然语⾔分别描述它们所识别的输⼊串的特征7、将图3.2所⽰的⾮确定的有限状态⾃动机确定化和最⼩化。图3.2⾮确定的有限状态⾃动机M第四章⾃顶向下语法分析1、从下列⽂法中消去左递归。（1）S→Aa|bA→Ac|Sd（2）A→A∨B|BB→B∧C|CC→?D|DD→(A)|i2、请消去下⾯⽂法G[S]中的回溯G[S]：S→aBc|aB→bB|ε3、有⽂法G[S]：S→ABA→a|εB→b|ε（1）验证该⽂法是LL(1)⽂法；（2）请构造预测分析表4、考虑⽂法G[A]：A→aABc|d|εB→Bb|b（1）改写为LL(1)⽂法；（2）请构造预测分析表（3）给出句⼦adbc的分析过程第五章⾃底向上语法分析1、请对下列⽂法G[S]构造算符优先分析表S→bAbA→(B|aB→Aa)2、⽂法G[S]：S→S(SaS→b该⽂法是LR(0)还是SLR(1)⽂法？3、⽂法G[A]：A→(A)|a构造该⽂法的LR(0)分析表，并请描述((a))的分析过程。4、⽂法G[S]:S→(S)S→（1）这个⽂法是例如LR(0)⽂法吗？若是，请构造该⽂法的LR(0)分析表。（2）这个⽂法是例如SLR(1)⽂法吗？若是，请构造该⽂法的SLR分析表。（3）构造该⽂法识别活前缀的DFA