习题课 编译原理与技术 计算机科学与技术学院 李诚

Assignment 1&2--2.3c 题目：叙述由下列正规式描述的语言 （0|1） * 0（0|1）（0|1） 答案： 表示倒数第三位为0的01串 注意：用自然语言描述，描述字符串性质

Assignment 1&2--2.3d 题目：叙述由下列正规式描述的语言 0 *10 * 10 * 10 * 答案： 含且仅含3个1的01串 注意：用自然语言描述，描述字符串性质

Assignment 1&2-- 2.4c 题目：为下列语言写出正规式定义：某语言的注释，它是以/*开始并以*/结束的任意字符，但它的任何前缀（除本身）不以*/结尾

Assignment 1&2-- 2.4c 题目：为下列语言写出正规式定义：某语言的注释，它是以/*开始并以*/结束的任意字符，但它的任何前缀（除本身）不以*/结尾(为便于区分，字符*用★表示) 分析：除了/与★，其他字符均可一视同仁，则 定义： charWA: a|b|…|/ char without asterisk charWSA: a|b|… char without asterisk and slash 在/★之后，可能存在非★字符，然后若干个★，则其后一定不能跟/，即只能跟charWSA，隔开之后，又可以是任意字符，直到遇到★，若其不是结束的或最后一个★，则重复此过程

Assignment 1&2-- 2.4c 题目：为下列语言写出正规式定义：某语言的注释，它是以/*开始并以*/结束的任意字符，但它的任何前缀（除本身）不以*/结尾 charWA: a|b|…|/ char without asterisk charWSA: a|b|… char without asterisk and slash Comment: / ★ charWA*(★ ★*otherWSA charWA*)* ★ *★ /

Assignment 1&2-- 2.4 g 题目：为下列语言写出正规式定义：由偶数个0和奇数个1构成的所有01串 分析：偶数个0，奇数个1构成的01串可以看作由偶数个0、1构成的串再加上一个额外的1，而我们在课上已经讲过偶数个0、1串的正规式，那么可以将其利用 even01: (00|11)*((01|10)(00|11)*(01|10)(00|11)*)*

Assignment 1&2-- 2.4 g 题目：为下列语言写出正规式定义：由偶数个0和奇数个1构成的所有01串 定义出01皆是偶数个的字串： even01: (00|11)*((01|10)(00|11)*(01|10)(00|11)*)* 分情况讨论， 1打头：直接跟even01即可 0打头：一定需要有01或10，在0与此之间可以有任意个00或11，在此之后接even01即可 所以可得结果： 1 even01|0(00|11)*(01|10)even01

Assignment 1&2--2.8.a 题目：用算法2.2将 (a|b)* 的NFA变换成DFA， 给出处理 ababbab 的状态转换序列

Assignment 1&2--2.8.a： (a|b)*的NFA ε ε 开始 a | b的NFA： i f ε b ε ε a ε ε 开始 (a|b)*的NFA： ε ε i f ε b ε ε

Assignment 1&2--2.8.a： (a|b)*的NFA ε a 2 3 ε ε 开始 ε ε 标上号： 1 6 7 ε b 4 5 ε ε

Assignment 1&2--2.8.a： (a|b)*的子集构造 4 3 5 6 7 ε a b 开始 A={0,1,2,4,7} B={1,2,3,4,6,7} C={1,2,4,5,6,7}

Assignment 1&2--2.8.a： (a|b)*的转换表 C={1,2,4,5,6,7} a b A B C

Assignment 1&2--2.8.a： (a|b)*的DFA C a B a 开始 A a b b C b ababbab的状态转换序列：ABCBCCBC

Assignment 1&2--2.8.b 题目：用算法2.2将(a*|b*)*的NFA变换成DFA， 给出处理ababbab的状态转换序列

Assignment 1&2--2.8.b: (a*|b*)*的NFA ε a ε ε ε 开始 ε i f b ε ε ε ε ε (a*|b*)*的NFA： ε ε a ε ε ε 开始 ε ε ε i f ε b ε ε ε ε ε

Assignment 1&2--2.8.b: (a*|b*)*的子集构造 NFA： ε ε ε a ε 2 3 4 5 ε ε 开始 ε ε 1 ε ε 10 11 b ε ε ε ε 6 7 8 9 ε ε A={0,1,2,3,5,6,7,9,10,11} B={1,2,3,4,5,6,7,9,10,11} C={1,2,3,5,6,7,8,9,10,11}

Assignment 1&2--2.8.b： (a*|b*)*的DFA C a B a 开始 A a b b C b ababbab的状态转换序列：ABCBCCBC

Assignment 1&2--2.8.c 题目：用算法2.2将((ε|a)|b*)*的NFA变换成DFA， 给出处理ababbab的状态转换序列

Assignment 1&2--2.8.c: ((ε|a) |b*)*的NFA 3 ε ε ε ε 开始 ε b ε ε 1 6 7 8 9 10 ε a ε ε 4 5 ε A={0,1,2,3,4,6,7,9,10} B={1,2,3,4,5,6,7,9,10} C={1,2,3,4,6,7,8,9,10}

Assignment 1&2--2.8.c： ((ε|a)|b*)*的DFA 开始 A a b b C b ababbab的状态转换序列：ABCBCCBC

Assignment 1&2--2.8.d 题目：用算法2.2将(a|b)*abb(a|b)*的NFA变换成DFA， 给出处理ababbab的状态转换序列

Assignment 1&2--2.8.d: (a|b)*abb(a|b)*的NFA ε a 2 3 ε ε 开始 ε ε a 1 6 7 8 ε b ε b 4 5 9 ε ε b a 12 13 ε ε ε ε 10 11 16 17 ε b ε 14 15 ε

Assignment 1&2-- 2.8.d: (a|b)*abb(a|b)*的转换表 C D E F G H I A={0,1,2,4,7} B={1,2,3,4,6,7,8} C={1,2,4,5,6,7} D={1,2,4,5,6,7,9} E={1,2,4,5,6,7,10,11,12,13,17} F={1,2,3,4,6,7,8,11,12,13,14,16,17} G={1,2,4,5,6,7,11,12,14,15,16,17} H={1,2,4,5,6,7,9,10,11,12,14,15,16,17} I={1,2,4,5,6,7,10,11,12,14,15,16,17} 容易出错的地方：再最后几步构造时忘记检查状态7-10的变化，导致转换表不全

Assignment 1&2-- 2.8.d: (a|b)*abb(a|b)*的DFA C D E F G H I a a b a F H b a b B D E a a a b a a b A G b b I C b b ababbab的状态转换序列：ABDBDEFH

（a）为句子abab构造2个不同的最左推导，以此说明该文法是二义的。 （b）为abab构造对应的最右推导。 Assignment 3&4--3.2 3.2 考虑文法 （a）为句子abab构造2个不同的最左推导，以此说明该文法是二义的。 （b）为abab构造对应的最右推导。 （c）为abab构造对应的分析树。 （d）这个文法产生的语言是什么？

Assignment 3&4--3.2

Assignment 3&4--3.2

Assignment 3&4--3.2 a和b数量相同的串

3.3 下面的二义文法描述命题演算公式，为它写一个等价的非二义文法。 Assignment 3&4--3.3 3.3 下面的二义文法描述命题演算公式，为它写一个等价的非二义文法。 Answer:

Assignment 3&4--3.8a 3.8a 消除下面文法的左递归。 Answer:

Assignment 5--3.11 题目：构造下面文法的LL(1)分析表 S-> aBS | bAS |ε A-> bAA | a B-> aBB|b

Assignment 5--3.11: 构造First集和Fellow集 文法： S-> aBS | bAS |ε A-> bAA | a B-> aBB|b First Fellow S a, b, ε $ A a, b a, b, $ B a b $ S S-> aBS S-> bAS S->ε A A-> a A-> bAA B B-> aBB B-> b First集和Fellow集 LL(1)分析表

Assignment 5--3.12 题目：下列文法是否为LL(1)文法 S-> AB | PQx A-> xy B-> bc P->dP |ε Q->aQ|ε

Assignment 5--3.12 如何证明？ P56：对任意两个产生式A->α|β都有： 1） First(α)∩ First(β)=Φ 2）若β=>* ε, 则First(A)∩ Fellow(A)=Φ 如果要证明不是LL(1)文法， 那么只要能找到反例即可

Assignment 5--3.12 S-> AB | PQx; A-> xy; B-> bc P->dP |ε; Q->aQ|ε 由于只有S，P，Q三种非终结符有两种推导选择，逐一分析 P的右部：dP、 ε，开始符号肯定不相交 Q的右部：aQ、ε，开始符号肯定不相交 S的右部：AB、PQx 由于PQx的First集含有x（当P、Q均推出ε ） AB的First含有x First(AB)∩ First(PQx)!=Φ 得证该文法不是LLQ

Assignment 5--3.16a 题目：用文法 S-> (L) | a L-> L, S | S 构造(a, (a, a))的最右推导，写出每个右句型的句柄

Assignment 5--3.16a S-> (L) | a; L-> L, S | S (a, (a, a)) S =>rm (L) =>rm (L, S) =>rm (L, (L)) =>rm (L, (L, S)) =>rm (L, (L, a)) =>rm (L, (S, a)) =>rm (L, (a, a)) =>rm (S, (a, a)) =>rm (a, (a, a))

S-> (L) | a; L-> L, S | S (a, (a, a)) Assignment 5--3.16a S-> (L) | a; L-> L, S | S (a, (a, a)) S =>rm (L) =>rm (L, S) =>rm (L, (L)) =>rm (L, (L, S)) =>rm (L, (L, a)) =>rm (L, (S, a)) =>rm (L, (a, a)) =>rm (S, (a, a)) =>rm (a, (a, a)) 容易出错的地方：忘记L不能直接推导出a

Q&A Q&A