学海网

中国科学技术大学2004－2005学年第二学期考试试卷编译原理和技术
1．（15分）
(a) 字母表 = { ( , ) }上的语言{ ( ), (( )( )), ((( ))), ( )( )( )( )( )}是不是正规语言？为什么？
(b) 正规式 (0 | 1)* 和( ( | 0) 1* )*是否等价，说明理由。

2．（15分）接受文法
S  A a | b A c | d c | b d a
A  d
3．（10分）现有字母表={ a }，写一个和正规式a*等价的上下文无关文法，要求所写的文法既不是LR文法，也不是二义文法。

4．（20分）
(a) 下面的文法定义语言L = { anbncm | m, n  1}。写一个语法制导定义，其语义规则的作用是：对不属于语言L的子集L1= { anbncn | n  1}的句子，打印出错信息。
S  D C D  a D b | a b C  C c | c
......