1 对于下列语言分别写出它们的正规表达式。
1)英文字母组成的所有符号串，要求符号串中顺序包含五个元音。
答：令letter表示除这五个元音外的其它字母。
(letter)*a(letter)*e(letter)*i(letter)*o(letter)*u(letter))*
2)英文字母组成的所有符号串，要求符号串中的字母依照词典顺序排列。
答： a*b*..z*
3)σ=上的含偶数个1的所有串。
答：(0|10*1)*
4)σ=上的含奇数个1的所有串。
答：(0|10*1)*1
5)具有偶数个0和奇数个1的有0和1组成的符号串的全体。
答：设s是符合要求的串，|s|=2k+1 (k≥0）。
则 s→s10|s21，|s1|=2k (k>0），|s2|=2k (k≥0）。
且s1是上的串，含有奇数个0和奇数个1。
s2是上的串，含有偶数个0和偶数个1。
考虑有一个自动机m1接受s1，那么自动机m1如下：
和l(m1)等价的正规表达式，即s1为：
类似的考虑有一个自动机m2接受s2，那么自动机m2如下：
和l(m2)等价的正规表达式，即s2为：
因此，s为：
6)不包含子串011的由0和1组成的符号串的全体。
答：1*|1*0(0|10)*(1|ε)
7)由0和1组成的符号串，把它看成二进制数，能被3整除的符号串的全体。
答： 假设w的自动机如下：
对应的正规表达式：(1(01*0)1|0)*
2 给出接受下列在字母表上的语言的dfa。
1)所有以00结束的符号串的集合。
2)所有具有3个0的符号串的集合。
答：3 下面是用正规式表示的变量声明：
int | float ) id (,id )*
请改用上下文无关文法表示，也就是写一个上下文无关文法，它和该正规式等价。
答：d t l ;
t int | float
l l, id | id
4 试分析下面给出的if-then-else语句的文法，它的提出原本是为了矫正dangling-else (悬而未决的-else)文法的二义性：
stmt → if expr then stmt
matched-stmt
matched-stmt→ if expr then matched-stmt else stmt
other
试说明此文法仍然是二义性的。
答：考虑句子if e then if e then other else if e then other else other 它具有如下所示的两种分析树 stmt expr then e if stmt if matched-stmt expr then matched-stmt e other if esle stmt matched-stmt expr then matched-stmt e other esle stmt matched-stmt other stmt matched-stmt if expr then matched-stmt e if esle stmt esle stmt matched-stmt expr then e stmt other expr then matched-stmt e other if matched-stmt other
则上面给出的if-then-else文法仍是二义性的。
5 证明下面文法是slr(1)文法，并构造其slr分析表。
e→e+t|t
t→tf|f
f→f*|a|b
答：该文法的拓广文法g'为
其lr(0)项目集规范族和goto函数(识别活前缀的dfa)如下：
i0 = i1 = i2 =
i3 = i4 = i5 =
i6 = i7 = i8 =
i9 = 求follow集：follow(e)=follow(t)=
follow(f)=
构造的slr分析表如下：
显然，此分析表无多重定义入口，所以此文法是slr文法。
6 为下面的文法构造lalr(1)分析表。
s→e e→e+t|t
t→(e)|a
答：其拓广文法g'：
构造其lr(1)项目集规范族和goto函数(识别活前缀的dfa)如下：
i0 = i1 =
i4 = i5 =
i7 = i9 =
i10 =
i13 =
i15 =
合并同心的lr(1)项目集，得到lalr的项目集和转移函数如下：
i0 = i1 = i2 =
i5,10 =
i7,14 =
first(l) =
first(r) =
follow(d) =follow(l) =
follow(t) =
follow(r) =
编译原理第5 7章作业 含答案
第5 7章课后作业 含答案 1 将文法g s 改写为等价的g s 使g s 不含左递归和左公共因子。g s s bsae ba a abd dc a 解 g s s bs s sae a a dc a a a bd a 2 有文法g s s abf a bbs e b dag 证明文法g是ll 1 ...
编译原理作业1答案
计算机科学系 2012春季学期。编译原理 第一次作业参 一 下列正则表达式定义了什么语言 用尽可能简短的自然语言描述 1.b ab ab 所有含有偶数个a的由a和b组成的字符串。2.c a a c b a b c c b b c a a b c 答案一 所有至少含有1个a和1个b的由a，b和c组成的...
编译原理作业7答案
软件学院 2012秋季学期。编译原理 第七次作业参 一 证明下列文法。s aa bac dc bdaa d是lalr 1 文法但不是slr 1 文法。构造lr 1 自动机 没有需要合并的状态 没有状态存在冲突，因而是lalr 1 文法。构造lr 0 自动机 在状态i6，由于 a follow a 因...