3.1 词法分析器的作用

3.1.1          float     limitedSquare     (      x     )     {     float     x     ;

     return     (     x     <=     -10.0     ||     x     >=     10.0     )     ?     100     :     x     *     x     ;

     }

除了标点符号/运算符号/赋值符号，其他都有属性值（词法值？）

3.1.2 Here     is     a     photo     of     <B>     my      hourse     </B>

     <P>     <IMG     SRC     =     "HOUSE.GIF"     >     <BR>

     See     <A     HREF     =     "morePix.html"     >     More Pictures     </A>     if you liked that one.     <P>

3.3 词法单元的归约

3.3.2

1）a(a|b)*a a后面0个或多个a或b，最后加个a

2）0个或多个b或者前面加个a，这个表达式重复0次或多次

3）0个或多个a或b，后面接个a，再接个a或b，再接个a或b

4）3个b，然后随意插入a

5）语言描述起来比较困难：aa或bb重复0次或多次，后面接0次或多次（ab或ba，接0次或多次aa或bb，接ab或ba，接0次或多次aa或bb）

3.3.3长度为n的字符串

1）前缀：n+1个

2）后缀：n+1个

3）真前缀 n-1个

4）子串

子串数 = 非空子串数+1

非空子串数计算如下：

删除前缀长度可能是                  0，   1，  2  ...，n-1

对应的删除后缀的可能长度为n-1  n-2   n-3 ...，0           - 0

因此总数为n+n-1+...+1+1=(n+1)*n/2+1

5）子序列数

c(n,0)+c(n,1)+...+c(n,n) = 2^n

3.3.4[sS][eE][lL][eE][cC][tT]

3.3.5 2)以后的题太难了，靠自己想搞不定，从网上搜的

1)uv=[b-df-hj-np-tv-z]

uv*auv*euv*iuv*ouv*uuv*

2)a*b*c*....y*z*

!!3)开始是/*，结尾是*/，中间可以有/*,但不能有*/,除非"*/"。

other -> [^/*//]

notend ->[other*

///*(notend"*/"notend)*/*//

!!4) ^(?![0-9]*([0-9])[0-9]*\1[0-9]*)[0-9]*$

!!5)^(?![0-9]*([0-9])[0-9]*\1[0-9]*\1[0-9]*)[0-9]*$

!!6)^(?!(b*ab*ab*)*ab*$|(a*ba*ba*)*$)(a|b)*$

!!7) b*(ab?)*

!!8)b*a*b?a*

3.3.6

1) [a-jA-J]

2) [辅音字母表]

3)[0-9a-fA-F]

!!4[.?!,:;...]

3.3.7 \""\" 或 \"\\

3.3.8 补集可以全部列出来

3.3.9 m个a和n个a?连起来

3.3.10 1)[ ]中的第一个^表示补，开头^表示行首

2)^可以用在前面加一个"\n"匹配，$在最后加个"\n"匹配

3.3.11 不确定这样是否正确：

character -> 所有可以用来做文件名的字符

[character\*?\??]+.[character\*?\??]+

3.3.12 假设e为专义字符，将ee->\e，其它情况的e->\，_前面如果没有\，则表示为character，%前面如果没有\，则表示为character*

3.4 词法单元的识别

3.4.1 看完这节马上做这个会觉得比较难，等看完3.6节以后回头再看会感觉比较容易，包括3.4.2

1) a(a|b)*a

                                       2 a则不变         ->其他->4最终状态

                            a  /

start-> 0 ->a-> 1      b↓↑a
3中*清空

                           b  \

                                        3 b则不变，加一个*

2)((ε|a)b*)*

KPM

3.4.3 

1) a b a b a b a a b

    0 0 1 2 1 2 1 1 2

2) 3)类似

3.4.4 提示用归纳法，其实主要用了归纳法的思想。

程序中最重要的是t，表示匹配到当前失效函数的值，求下一个失效函数值要用到。

初值设置应该没啥问题，只有一个字符串的真子串长度肯定是0

假设当前已经算出f(s) = t，下一步计算f(s+1)

如果b(s+1)==b(t+1)，则容易得到f(s+1)=t+1，以t+1作为新的t进行下一步计算

如果b(s+1)!=b(t+1)，说明继续匹配失败，需要减小t为一个合适的值（程序第3行的做法），直到满足两个条件之一：

1.t=0，说明前面的算出的值失效，从0开始重新算

2.新的t计算得出b(s+1)==b(t+1)，这样找到一个前面有效的值，加1即可继续计算

说出来可能比较难理解，实际调试一下比较容易理解。

3.4.5 参见《算法导论》中文版570页

3.5 词法分析器生成工具

图3-23 的LEX程序没法运行，首先是开头声明部分LT等常量需要定义，其次，因为没有定义

所以编译的时候要加上ll：gcc lex.yy.c -ll

3.6 有穷自动机

3.7 从正则表达式到自动机

3.7.1 1) 图3-26   开始状态为 A = {0,1,3}

A输入a以后为 B = {2}

A输入b以后为 C = {4}

2) 图2-29   开始状态A={0} A

A输入a以后为 B = {0,1}     B

A输入b以后为 A = {0}         B

B -> a -> C = {0,1,2}           C

B -> b -> {0,1}                      C

C -> a -> {0,1,2}                  C

C -> b -> D = {0,1,2,3}        D

D -> a -> {0,1,2}                  D

D -> b -> {0,1,2,3}

3)略

3.7.2 1）aabb 图3-29

a   0,1

a   0,1,2

b   0,2,3   匹配成功，但要接着匹配下一个

b   0,2,3   输入结束，匹配成功。

3.8 词法分析器生成工具的设计

3.8.1 

i -> f

character+

3.8.2略

3.8.3

3.8.4

a -> b -> c -> ->d

3.9 基于DFA的模式匹配器的优化

3.9.1

结点n	nullable(n)	firstpos(n)
1)?	true	firstpos(c1)
2)+	nullable(c1)	firstpos(c1)

3.9.2 1) (a|b)*

a:1 b:2

A = {1,2}

只有1个状态