Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
69 lines (35 sloc) 2.07 KB

3.8 节的练习

3.8.1

假设我们有两个词法单元:(1)关键字 if,(2)标识符,它表示除了 if 之外的所有由字母组成的串。请给出:

  1. 识别这些词法单元的 NFA
  2. 识别这些词法单元的 DFA

解答

  1. NFA

    3 8 1-nfa

    注意:该nfa也存在潜在冲突,根据课本讲述的两个原则来决定匹配的词素 1、匹配最长的前缀 2、按定义的先后顺序进行匹配

  2. DFA

    3 8 1-dfa

3.8.2

对如下的词法单元重复练习 3.8.1:

  1. 关键字 while
  2. 关键字 when
  3. 标识符,它代表以字母开头、由字母和数位组成的字符串

解答

  1. NFA

    3 8 2-nfa

  2. DFA

    太麻烦,不画了

3.8.3 !

假设我们修正 DFA 的定义,使得每个状态在每个输入符号上有零个或一个转换(而不是像标准的 DFA 定义中那样恰好有一个转换)。那么,有些正则表达式就可以具有相比按标准定义构造得到的 DFA 而言更小的 “DFA”。给出这种正则表达式的例子。

解答

以正则表达式 ab 定义的语言为例,假定该语言输入的字符集为 {a, b}

标准的 DFA

3 8 3-1

修正的 DFA

3 8 3-2

同标准的 DFA 相比,状态 0 上有 0 个 b 上的转换,状态 1 上有 0 个 a 上的装换,状态 2 上有 0 个 a 上的转换和 0 个 b 上的转换。显然,根据修正的定义得到的 DFA 更小。

3.8.4 !!

设计一个算法来识别形如 r1/r2 的 Lex 向前看模式,其中 r1 和 r2 都是正则表达式。说明该算法如何处理如下输入:

  1. (abcd|abc)/d
  2. (a|ab)/ba
  3. aa*/a*