1、 1 对于下列语言分别写出它们的正规表达式。 (1) 英文字母组成的所有符号串，要求符号串中顺序包含五个元音。 答： 令 Letter 表示除这五个元音外的其它字母。 (letter)*A(letter)*E(letter)*I(letter)*O(letter)*U(letter)* (2) 英文字母组成的所有符号串，要求符号串中的字母依照词典顺序排列。 答： A*B*.Z* (3) =0,1上的含偶数个 1 的所有串。 答： (0|10*1)* (4) =0,1上的含奇数个 1 的所 有串。 答： (0|10*1)*1 (5) 具有偶数个 0 和奇数个 1 的有 0 和 1 组成的符号串的
2、全体。 答： 设 S 是符合要求的串， |S|=2k+1 (k0）。 则 SS 10|S21， |S1|=2k (k0）， |S2|=2k (k0）。 且 S1 是 0,1上的串，含有奇数个 0 和奇数个 1。 S2 是 0,1上的串，含有偶数个 0 和偶数个 1。 考虑有一个自动机 M1 接受 S1，那么自动机 M1 如下： 和 L(M1)等价的正规表达式，即 S1 为： (00|11)|(01|10)(00|11)*(01|10)*(01|10)(00|11)* 类似的考虑有一个自动机 M2 接受 S2，那么自动机 M2 如下： 和 L(M2)等价的正规表达式，即 S2 为： (00|11
3、)|(01|10)(00|11)*(01|10)* 因此， S 为： (00|11)|(01|10)(00|11)*(01|10)*(01|10)(00|11)*0| (00|11)|(01|10)(00|11)*(01|10)*1 (6) 不包含子串 011 的由 0 和 1 组成的符号串的全体。 答： 1*|1*0(0|10)*(1|) (7) 由 0 和 1 组成的符号串 ,把它看成二进制数，能被 3 整除的符号串的全体。 答： 假 设 w 的自动机如下： 对应的正规表达式： (1(01*0)1|0)* 2 给出接受下列在字母表 0,1上的语言的 DFA。 (1) 所有以 00 结束的符
4、号串的集合。 (2) 所有具有 3 个 0 的符号串的集合。 答： (1) DFA M=(0， 1， q0， q1， q2， q0， q2， ) 其中 定义如下 : （ q0， 0） =q1 （ q0， 1） =q0 （ q1， 0） =q2 （ q1， 1） =q0 （ q2， 0） =q2 （ q2， 1） =q0 (2)正则表达式 : 1*01*01*01* DFA M=(0， 1， q0， q1， q2， q3， q0， q3， ) 其中 定义如下 : （ q0， 0） =q1 （ q0， 1） =q0 （ q1， 0） =q2 （ q1， 1） =q1 （ q2， 0） =q3 （
5、q2， 1） =q2 （ q3， 1） =q3 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
6、 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 the
7、n 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 分析表。 EE+T|T TTF|F FF*| a|b 答： 该文法的拓广文法 G为 (0) E E (1) E E+T (2) E T (3) T TF (4) T F (5) F F* (6) F a (7) F b 其 L
8、R(0)项目集规范族和 goto 函数 (识别活前缀的 DFA)如下 : I0 = EE, EE+T, ET, TTF, TF, FF*, Fa, Fb I1 = EE, EE+TI2 = ET, TTF, FF* , Fa, Fb I3 = TF, FF* I4 = Fa I5 = Fb I6 = EE+T, TTF, TF, FF*, Fa, Fb I7 = TTF, FF* I8 = FF* I9 = EE+T, TTF, FF*, Fa, Fb 求 FOLLOW 集： FOLLOW(E)= , FOLLOW(T)= , , a, b FOLLOW(F)= , , a, b, * 构造的
9、 SLR 分析表如下： 显然，此分析表无多重定义入口，所以此文法是 SLR 文法。 6 为下面的文法构造 LALR(1)分析表 SE EE+T|T T(E)|a 答： 其拓广文法 G： (0) S S (1) S E (2) E E+T (3) E T (4) T (E) (5) T a 构造其 LR(1)项目集规范族和 goto 函数 (识别活前缀的 DFA)如下 : I0 = SS, $, SE, $, EE+T, $/+, ET, $/+, T(E), $/ +, Ta, $/+ I1 = SS, $ I2 = SE, $, EE+T, $/+ I3 = ET, $/+ I4 = T(E
10、), $/+, EE+T, )/+, ET, )/+, T(E), )/+, Ta, )/+ I5 = Ta, $/+ I6 = EE+T, $/+, T(E), $/+, Ta, $/+ I7 = T(E ), $/+, EE+T, )/+ I8 = ET, )/+ I9 = T(E), )/+, EE+T, )/+, ET, )/+, T(E), )/+, Ta, )/+ I10 = Ta, )/+ I11 = EE+T, $/+ I12 = T(E), $/+ I13 = EE+T, )/+, T(E), )/+, Ta, )/+ I14 = T(E), )/+, EE+T, )/+ I
11、15 = EE+T, )/+ I16 = T(E), )/+ 合并同心的 LR(1)项目集，得到 LALR 的项目集和转移函数如下： I0 = SS, $, SE, $, E E+T, $/+, ET, $/+, T(E), $/+, Ta, $/+ I1 = SS, $ I2 = SE, $, EE+T, $/+ I3,8 = ET, $/+/) I4,9 = T(E), $/+/), EE+T, )/+, ET, )/+, T(E), )/+, Ta, )/+ I5,10 = Ta, $/+/) I6,13 = EE+T , $/+/), T(E), $/+/), Ta, $/+/) I7
12、,14 = T(E), $/+/), EE+T, )/+ I11,15 = EE+T, $/+/) I12,16 = T(E) , $/+/) LALR 分析表如下： 7 （ 1）通过构造识别活前缀的 DFA 和构造分析表，来证明文法 E E + id | id 是 SLR(1)文法。 答： 先给出接受该文法活前缀的 DFA 如下： 再构造 SLR 分析表如下： 动作 转移 id + $ E 0 s2 1 1 s3 acc 2 r2 r2 3 s4 4 r1 r1 表中没有多重定义的条目，因此该文法是 SLR(1)的。 （ 2）下面左右两个文法都和（ 1）的文法等价 E E + M id |
13、id E M E + id | id M M 请指出其中有几个文法不是 LR(1)文法，并给出它们不是 LR(1)文法的理由。 答： 只有文法 E M E + id | id M E E E E + id E id I0 E E E E + id I1 E id I2 E id + E E + id I3 E E + id I4 id 状态 不是 LR(1)文法。因为对于句子 id+id+ +id 来说，分析器在面临第一个 id 时需要做的空归约次数和句子中 +id 的个数一样多，而此时句子中 +id 的个数是未知的。 8 根据自上而下的语法分析方法，构造下面文法的 LL（ 1）分析表。 D
14、TL T int | real L id R R , id R | 答： 先计算 FIRST 和 FOLLOW FIRST(D) = FIRST(T) = int,real FIRST(L) = id FIRST(R) = , FOLLOW(D) = FOLLOW(L) = $ FOLLOW(T) = id FOLLOW(R) = $ LL(1)分析表如下： int real id , $ D D - TL D - TL T T - int T - real L L - idR R R - ,idR R - 9 下面的文法产生的表达式是对整型和实型常数应用算符 +形成的。当两个整数相加时，结果
15、仍为整数，否则就是实数。 EE+T|T T num.num|num （ a）给出一个语法制导定义以确定每个子表达式的类型。 （ b）扩充（ a）中的语法制导定义把表达式翻译成前缀形式，并且决定类型。使用一元算符 inttoreal把整型值转换成相等的实型值，以使得前缀形式中的 +的两个操作对象是同类型的。 答： (a): 产生式 语义规则 EE1+T IF (E1.type=integer) and (T.type=integer) THEN E.type:=integer ELSE E.type:=real ET E.type:=T.type Tnum.num T.type:=real Tn
16、um T.type:=integer (b): 产生式 语义规则 EE1+T IF (E1.type=integer) and (T.type=integer) THEN BEGIN E.type:=integer Print(+,E1.val,T.val) END ELSE BEGIN E.type:=real IF E1.type=integer THEN Begin E1.type:=real E1.val:=inttoreal(E1.val) End IF T.type:=integer THEN Begin T.type:=real T.val:=inttoreal(T.val) E
17、nd Print(+,E1.val,T.val) END ET E.type:=T.type E.val:=T.val Tnum.num T.type:=real T.val:=num.num.lexval Tnum T.type:=integer T.val:=num.lexval 10 假设说明是由下列文法产生的： Did L L,id L|:T T integer |real （ a）建立一个翻译模式，把每一个标识符的类型加入到符号表中。 （ b）从（ a）中的翻译模式构造一个预翻译程序。 答： (a)： 产生式 翻译模式 Did L D.Type:=L.Type addtype(id.
18、entry, D.type) L,id L1 L.Type:=L1.Type addtype(id.entry, L.type) L:T L.type:=T.type Tinteger T.type:=integer Treal T.type:=real (b)： Procedure D; begin If lookahead=id then Begin Match(id); D.type=L; addtype(id.entry,D.type) end else error end Function L: DataType; Begin If lookahead=, then Begin Ma
19、tch(,); If lookahead=id then begin match(id); L.Type=L; addtype(id.entry,L.type); return(L.type) end Else error End Else if lookahead=: then Begin Match(:); L.Type=T; return(L.Type) end else error End Function T: DataType; Begin If lookahead=integer then Begin Match(integer); return(integer) end els
20、e If lookahead=real then Begin Match(real); return(real) end else error end 11 为下面的算术表达式文法写一个语法制导的翻译方案，它将每个子表达式 E 的符号（即值大于零还是小于零）记录在属性 E.sign 中 （属性值分别用 POS 或 NEG 表示 ） 。你可以假定所有的整数都不为零，这样就不用担心零的符号。 E E *E | +E | E | unsigned_integer 答： E E1 *E2if E1.sign= E2.sign then E.sign := POS else E.sign := NEG
21、E +E1 E.sign := E1.sign E E1 if E1.sign= POS then E.sign := NEG else E.sign := POS E unsigned_integer E.sign := POS 12 为下面文法写一个语法制导的定义，用 S 的综合属性 val 给出下面文法中 S 产生的二进制数的值。例如，输入 101.101 时， S. val := 5.625。（不得修改文法。） S L . R | L L L B | B R B R | B B 0 | 1 答： S L . R S. val := L. val + R. val S L S. val
22、:= L. val L L1 B L. val := L1. val 2 + B. val L B L. val := B. val R B R1 R. val := (R1. val + B. val)/2 R B R. val := B. val/2 B 0 B. val := 0 B 1 B. val := 1 13 试问下面的程序将有怎样 的输出 ？ 分别假定 ： （ a） 传值调用 （ call-by-value）； （ b） 引用调用 （ call-by-reference）； （ c） 复制恢复 （ copy-restore）； （ d） 传名调用 （ call-by-name） 。 program main(input,output）；
