Implementation of Lexical Analysis

发表于

Implementation of Lexical Analysis

Regular languages

  • Epsilon: a simple string namely the empty string
  • Union: A+B == {a|a属于A} U {b|b属于B}
  • Concatenation: AB = {ab|a属于A ^ b属于B}
  • Iteration: A* = A...A(0次或多次)

正则表达式可能有多个表示方式

Formal languages

alphabet 表示一系列的字符，adcii码

meaning function L : maps syntax to semantics，将表达式映射到字符串的集合。比如：

L(epison) = {""} L('c') = {"c"} L(A+B) = L(A) U L(B)

Reason for meaning function：有时候一个semantics可以用多个syntax表示，可能是多对一的映射关系。用于不会有一对多的关系。

lexical specification

  • letter = [a-zA-Z]
  • keyword = 'if'+'else'+..
  • digit = '0'+'1'+'2'+'3'+'4'+'5'+'6'+'7'+'8'+'9'
  • Integer = digit digit* = digit+
  • Identifier = letter(letter+digit)*
  • whitespace(blanks/newlines/tabs) = (' '+''+')+

考虑如何匹配一个邮箱地址：anyone@cs.stanford.edu(考虑前面只由字母组成)

  • 得到这样的正则表达式：letter+ '@' letter+ '.' letter+ '.' letter+

注意:

  • union = A|B = A+B
  • option: A+ ε = A?
  • range: 'a'+'b'+...+'z' = [a-z]
  • Excluded range: complement of [a-z] = [^a-z]

正则表达式可以描述很多语言，是一种语言的说明。

如何进行正则表达式的匹配

  1. Write a rexp for the lexemes of each token
  • number = digit*
  • keyword = 'if'+'else'+..
  • Identifier = letter(letter+digit)*
  • OpenPar = '('
  1. Construct R

R = keyword + Identifier + Number + ...

  1. Let input be X1..Xn

For i<=i<=n check x1..xi 属于L(R)

  1. if success, x1..xi属于L(Ri)

  2. remove x1...xi

Question:

  • How much input is used?

最长匹配原则，如果有两个字符串都符合正则表达式的话。

  • which token is used?

x1..xi 属于L(R); R = R1+R2...Rn。

如果有x1...xi属于L(Ri),也有x1...xi属于L(Rj),那么采用priority choose。例如if应该是keyword，不是identifier。

Finite Automa

  • Regular expressions = specification
  • Finite automata = implementation

consists of:

  • input alphabet

  • a set of states

  • a start state

  • a set of accepting states

  • a set of transitions:

from state1, inpute a, go to state2;

如果输入完之后还处于接收状态，就接收；

否则，就拒绝：处于结束状态（terminate states，no transitions）；遇到错误匹配

Regular Expressions to NFAS

Lexical Specification-> Regular expressions-> NFA-> DFA-> Table-driven Implementation of DFA

对于NFA，每个notation的图表示与正则表达式相对应，比如正则表达式的epsilon就与开始状态，接收一个epsilon，到达的结束状态的图表示相对应。比如AB，就是状态A接收一个epsilon到达状态B。

我觉得在这种情况下，AB中的A或者B用状态机来表示比较恰当。假如A是一个组合状态，就递归进去解析，直到得到最终的单元的notation。

NFA to DFA

假如在NFA中，由B分别经过epsilon可以到达B和C，那么可以说：

epsilon-closure(B) = {B, C, D}，就是仅仅经过epsilon，迭代可以到达的状态

对于NFA来说，在不同的时间NFA可能处于多个状态，a(X) = {y|x属于X and x->(a)y}表示a应用于X后到达Y

  • 定义DFA

states: subset of S(all states in NFA)

start: epsilon-closure(s)

final: {X|x与NFA中final states的交集不等于空集的集合},也就是到达的状态中包含了NFA中的final states，就意味着这是DFA中的final states

transitions: X->(a)Y, if y == epsilon-closure(a(X))

implementing finite automata

由DFA组织一个表，有多少种状态就多少行，有多少种输入就多少列，表示出每种状态在不同输入的情况下到达的状态。

所以，匹配流程如下：

1
2
3
4
5
i = 0
state = 0
while(input[i]) {
    state = A[state, input[i++]]
}

DFA: faster, less compact

NFA: slower, more compact

提醒

本章内容仅本人所理解，不供参考