Compiler作業參考(1) A班

101年度第2學期 期中考前

[HW1]
都基本概念，上課應該都有解試過，有空再寫。

[HW2]
1. (a) 0 | ( [1-9] [0-9]* ) ... 0 或者是出現一個1-9間的數字後，後面可以接0-9數字
(b) 0 | 4 | 8 | ( ( [1-9] [0-9]* )? (1|3|5|7|9)(2|6) ) | ( ( [1-9] [0-9]* )? (2|4|6|8)(0|4|8) )   ...觀察4的倍數可以找到規則

5. 參考lecture note

6. ( 0 | ( [1-9] [0-9]* ) ) ( . ( 0 | [0-9]* [1-9] ) )?   ...跟1.(a)差不多，只是多了小數

7.   '/' '*' ( [.]* ~( '*' '/' ) ) '*' '/'   ...不同的regular expression引擎可能有不同寫法

16. 參考lecture note

17. 參考lecture note

[HW3]

1. (a) a^n b^m, where n>=2 m>=2, ambiguous
(b) a^n b^m, where n>=2 m>=2, unambiguous (left-most derivation)
(c) {a,b}, where the 1st character is 'a', length >=4, ambiguous
(d) infinity a...ab...b, unambiguous (left-most derivation)

6. (a)
S -> A B
A -> 1 | 2 | 3 | 4 | 5 | 6 | 7
B -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | (lambda)
(b) 

S -> A B
A -> 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | a | A | b | B | c | C | d | D | e | E | f | F
B -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | a | A | b | B | c | C | d | D | e | E | f | F | (lambda)

(c)

S -> 1 A 
A -> 1 A | (lambda)

(d) 
把上面三種整合起來，用不同的prefix區分，比如說base-16常用0x開頭

7. (a) 空的
(b) 定義不完整
(c) b (a)*
(d) {a,b,c}的任意組合，長度為2

8.(a) 略
(b) 略
(c) 括號中的expression有最高優先權，其次是times，最後是plus，採用left-associations

10. 兩個都ambiguous，( num plus num plus num， num ( plus num ( plus num ，皆可以有兩種tree

[HW4]

參考first set與follow set
http://iaic.csie.tku.edu.tw/compiler/LN/compiler_first_follow.pdf