CP-Homework1

:material-circle-edit-outline: 约 216 个字 :material-clock-time-two-outline: 预计阅读时间 1 分钟

[!ABSTRACT]

Modern Compiler Implementation in C.pdf P46~47 250225

2.1

a

c*a(a|c)*b(a|b|c)*

b

((b|c)*a(b|c)*a(b|c)*)*

c

(1|0)*00

d

穷举

1(0|1)*(0|1)(0|1)(0|1)(0|1)(0|1)(0|1) | 11(0|1)(0|1)(0|1)(0|1) | 10101(0|1) | 1011(0|1)(0|1)

e

不太确定

a|((ba)*b)*(ba)*c)*

f

(00|0[1-7][0-7]*) | (0|[1-9][0-9]*)

g

费马大定律

1|10

2.2

a

有限状态机没有记忆能力，数量关系的确认需要数量值的确定，而数量值无法被有限状态机存储

b

原因同上，回文的识别需要将字符串前半部分与后半部分比较，确切说是需要存储和比较已读取的字符，有限状态机无法实现

c

原因同上，举反例，一对花括号（{}）在 C 语言中很常见的，而有限状态机无法识别匹配两个配对的花括号

2.5

2.6

注意需要 repeat，直到无法再化简