Step1: String -> Scanning (DFA) -> Tokens Scanner又叫Lexical analyzer或Lexer.

其目的在于, 将需要compile的源代码逐字读入compiler, 并将每一个符合"词汇命名规则(Lexical Syntax)"的字段转换成token存储.
换句话说, 就是一遍读, 一遍看每一个单词的拼写对不对. 对的就转成token, 拼错了就输出error.

作业中对应: A6 P4
(某些语言的compiler在Scanning之后还包含Preprocessing, 因为不在241讨论范围内, 不做解释)

Step2: Tokens -> Parsing(LL/LR) -> Intermediate Format (WLI)

Parsing又叫Syntactic Analysis.
其目的在于, 将token与token联系在一起, 并将他们的转换成符合一定规范的"中间格式", 一般是某种树状结构, 例如241中定义的WLI.

在Parsing过程中, 如果遇到不符合某种语言的"语法规则(Grammar)"时, 则输出error. 如果语法正确, 则输出对应格式.
简单说, 就是看的说的话是不是人话, 有没有缺个标点少个括号.
如果不是人话那就说明你该重新学语法去了.

作业中对应: A8 P4

Read more...

Terminal Symbols: 6个

BOF, EOF, id, -, (, )

S, expr, term

S

0	S BOF expr EOF
1	expr term
2	expr expr - term
3	term id
4	term ( expr )

Read more...

概念就不说了, 啥压缩比啊, logical/Physical compression, Lossy/Lossless的.

Run-Length Encoding (RLE)

• 第一位表示由0或者1开头
• 之后用prefix-free integer encoding表示每一个Run的长度
  • 后x位表示这个run的binary长度
  • 前x-1位填零, 为unary表示后x位的长度减一

Huffman Coding

• 用binary trie表示字典中的所有字符
• 将文本依照trie转成binary

• 将每个字符存入独立的trie中
• 确定每个字符的出现次数(频率), 一个trie的比重(weight)即为trie中字符的频率和
• 将weight最小的两个trie合并成一个新trie
• 重复上一步直到只剩下一个trie

Read more...

Tries

单词查找树 Tries (Radix Tree):

• 
• 左0右1
• item只存在leaf上
• Prefix-free: 任意一个key不能有其他key是他的前缀(比如: 1101和11011不能共存)
• Search: 逐位执行BS
• Insert: 逐位执行BS
• 如果找到某leaf与insert的item不等, insert fail. (现存item是新item的prefix)
• 如果在某个node搜索结束, insert fail. (新item是其他key的prefix)

• 如果无路可走了, 开路出来.

• Delete: Search到对应item以后, 删除这个leaf以及其他无用的node.

Compressed Tries (Patricia Tries):

• 
• 相比普通Tries, compressed tries去除了额外的node(只有一个child的node). 其他基本相同.

• 每个node中增加了下一层Search中, 需要检测的位数

Multiway Tries:

• 
• 以特定alphabet集合为基础, 建立的Tries
• 通过$ sigh以允许prefix存在
• 不是Binary Tree
• 同样可以compress, 与Compressed Tries方法相同

String Matching 要match的string为T, pattern为P

Brute-force Algorithm

1. 从前往后依次比对P的首字母
2. 如发现与首字母匹配, 则继续比对剩下的字符直到P结尾
3. 如P未结尾时出现不匹配, 则回到与首字母匹配位置的下一个, 继续比对首字母

4. 如T结尾, 则无匹配

Boyer-Moore Algorithm

1. 将T和P右对齐
2. 从P的结尾开始, 依次向前与T比对
3. 如遇到不匹配, 检查T该位置的字符是否在P中出现过
   
   
   • 如出现过, 则将该字符在P中最后出现的位置, 与T对齐
   • 如没出现过, 则讲P向后shift一个P的长度
   • 重复第二步

4. 如T结尾, 则无匹配

KMP Algorithm

1. 建立KMP Failure Array 位于j点的F(j)值等于P[1..j]的结尾与P的开头所重叠的字符位数
2. 将T和P左对齐
3. 从P的开头开始, 依次向后与T比对
4. 如遇到P[i]不匹配, P向后shift[i - F(i-1)]位, 且 i 值assign为F(i-1)

5. 如T结尾, 则无匹配

Suffix Tree (Trie) 与前几个Algorithm相反, 此Algorithm是为了在同一个T中寻找不同P而建立的.

Post-condition: T长度为n, i值为从0到n-1
1. 将所有T[i..n]依次insert进Compressed trie
2. 因为Compressed trie的性质 (prefix-free), 如果某一个T[i..n]是已有node的prefix, 则不会被insert
3. 每个node和leaf中, 保存对应的i和n值
4. 在Compressed trie中搜索, 将P与每个node进行比对. (长度以P为准)
5. 如果遇到node长度小于P长度, 则无匹配.

= =`最后一个Module后天再说...每天都看Algorithm会死人的`明天收拾251

更多CS 240总结请看: http://blog.gregwym.info/tag/cs240/

Fedex, 明明昨天还没到北美大陆呢, 今天早上就到家门口了...

Read more...