Download presentation
Presentation is loading. Please wait.
1
习题课 编译原理与技术 计算机科学与技术学院 李诚
2
Assignment 1&2--2.3c 题目：叙述由下列正规式描述的语言 （0|1） * 0（0|1）（0|1） 答案：
表示倒数第三位为0的01串 注意：用自然语言描述，描述字符串性质
3
Assignment 1&2--2.3d 题目：叙述由下列正规式描述的语言 0 *10 * 10 * 10 * 答案：
含且仅含3个1的01串 注意：用自然语言描述，描述字符串性质
4
Assignment 1& c 题目：为下列语言写出正规式定义：某语言的注释，它是以/*开始并以*/结束的任意字符，但它的任何前缀（除本身）不以*/结尾
5
Assignment 1& c 题目：为下列语言写出正规式定义：某语言的注释，它是以/*开始并以*/结束的任意字符，但它的任何前缀（除本身）不以*/结尾(为便于区分，字符*用★表示) 分析：除了/与★，其他字符均可一视同仁，则 定义： charWA: a|b|…|/ char without asterisk charWSA: a|b|… char without asterisk and slash 在/★之后，可能存在非★字符，然后若干个★，则其后一定不能跟/，即只能跟charWSA，隔开之后，又可以是任意字符，直到遇到★，若其不是结束的或最后一个★，则重复此过程
6
Assignment 1& c 题目：为下列语言写出正规式定义：某语言的注释，它是以/*开始并以*/结束的任意字符，但它的任何前缀（除本身）不以*/结尾 charWA: a|b|…|/ char without asterisk charWSA: a|b|… char without asterisk and slash Comment: / ★ charWA*(★ ★*otherWSA charWA*)* ★ *★ /
7
Assignment 1& g 题目：为下列语言写出正规式定义：由偶数个0和奇数个1构成的所有01串 分析：偶数个0，奇数个1构成的01串可以看作由偶数个0、1构成的串再加上一个额外的1，而我们在课上已经讲过偶数个0、1串的正规式，那么可以将其利用 even01: (00|11)*((01|10)(00|11)*(01|10)(00|11)*)*
8
Assignment 1& 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
9
Assignment 1& a 题目：用算法2.2将 (a|b)* 的NFA变换成DFA， 给出处理 ababbab 的状态转换序列
10
Assignment 1&2--2.8.a： (a|b)*的NFA
ε ε 开始 a | b的NFA： i f ε b ε ε a ε ε 开始 (a|b)*的NFA： ε ε i f ε b ε ε
11
Assignment 1&2--2.8.a： (a|b)*的NFA
ε a 2 3 ε ε 开始 ε ε 标上号： 1 6 7 ε b 4 5 ε ε
12
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}
13
Assignment 1&2--2.8.a： (a|b)*的转换表
C={1,2,4,5,6,7} a b A B C
14
Assignment 1&2--2.8.a： (a|b)*的DFA
C a B a 开始 A a b b C b ababbab的状态转换序列：ABCBCCBC
15
Assignment 1& b 题目：用算法2.2将(a*|b*)*的NFA变换成DFA， 给出处理ababbab的状态转换序列
16
Assignment 1&2--2.8.b: (a*|b*)*的NFA
ε a ε ε ε 开始 ε i f b ε ε ε ε ε (a*|b*)*的NFA： ε ε a ε ε ε 开始 ε ε ε i f ε b ε ε ε ε ε
17
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}
18
Assignment 1&2--2.8.b： (a*|b*)*的DFA
C a B a 开始 A a b b C b ababbab的状态转换序列：ABCBCCBC
19
Assignment 1& c 题目：用算法2.2将((ε|a)|b*)*的NFA变换成DFA， 给出处理ababbab的状态转换序列
20
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}
21
Assignment 1&2--2.8.c： ((ε|a)|b*)*的DFA
开始 A a b b C b ababbab的状态转换序列：ABCBCCBC
22
Assignment 1& d 题目：用算法2.2将(a|b)*abb(a|b)*的NFA变换成DFA， 给出处理ababbab的状态转换序列
23
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 ε
24
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的变化，导致转换表不全
25
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
26
（a）为句子abab构造2个不同的最左推导，以此说明该文法是二义的。 （b）为abab构造对应的最右推导。
Assignment 3&4--3.2 3.2 考虑文法 （a）为句子abab构造2个不同的最左推导，以此说明该文法是二义的。 （b）为abab构造对应的最右推导。 （c）为abab构造对应的分析树。 （d）这个文法产生的语言是什么？
27
Assignment 3&4--3.2
28
Assignment 3&4--3.2
29
Assignment 3&4--3.2 a和b数量相同的串
30
3.3 下面的二义文法描述命题演算公式，为它写一个等价的非二义文法。
Assignment 3&4--3.3 3.3 下面的二义文法描述命题演算公式，为它写一个等价的非二义文法。 Answer:
31
Assignment 3&4--3.8a 3.8a 消除下面文法的左递归。 Answer:
32
Assignment 题目：构造下面文法的LL(1)分析表 S-> aBS | bAS |ε A-> bAA | a B-> aBB|b
33
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)分析表
34
Assignment 题目：下列文法是否为LL(1)文法 S-> AB | PQx A-> xy B-> bc P->dP |ε Q->aQ|ε
35
Assignment 如何证明？ P56：对任意两个产生式A->α|β都有： 1） First(α)∩ First(β)=Φ 2）若β=>* ε, 则First(A)∩ Fellow(A)=Φ 如果要证明不是LL(1)文法， 那么只要能找到反例即可
36
Assignment 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
37
Assignment a 题目：用文法 S-> (L) | a L-> L, S | S 构造(a, (a, a))的最右推导，写出每个右句型的句柄
38
Assignment a 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))
39
S-> (L) | a; L-> L, S | S (a, (a, a))
Assignment a 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
40
Q&A Q&A
Similar presentations
