前言 准备努努力啃一啃编译原理，目标就是能啃多少，啃多少，加油！
开始 词法分析的工作就是将一个个长长的字符串识别出一个个的单词，这些单词被称为Token, 并且词法分析的工作是一边读取，一边识别字符串的，不是把字符串都读到内存再识别，这跟我们在人类世界听别人说话很类似，一边听，一边提取信息。
问题来了，如何把一长串的字符，断成一个个的Token呢？如何分割呢？
解决问题 首先拿一个简单的例子来实现，比如：
这是一个简单的关系表达式，我们可以用自己熟悉的语言来解析这个表达式，我使用的是swift。大概这样：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 /// 有限自动机 enum NJDFAState { /// 初始化 case initial /// 字母 case alpha /// 大于 case greaterThan /// 大于等于 case graterEqual /// 数字 case digit } struct NJToken { var type: NJTokenType? var text: String? } var tokenList:[NJToken] = [] var currentTokenText:[Character] = [] var currentToken:NJToken = NJToken() func initToken(ch:Character) -> NJDFAState { var state = NJDFAState.initial if isAlpha(ch: ch) { state = NJDFAState.alpha } else if ch == ">" { state = NJDFAState.greaterThan } else if isDigit(ch: ch) { state = NJDFAState.digit } return state }
词法分析的过程被就是构造好的有限自动机，在不同的状态中迁移，从而解析出Token
所以，上面的的例子age >= 45可以这样解析：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 let script = "age >= 45" let scriptList:[Character] = Array(script) var i = 0 var state = NJDFAState.initial while i < scriptList.count { let ch = scriptList[i] switch state { case .initial: state = initToken(ch: ch) if !isBlank(ch: ch) { currentTokenText.append(ch) } case .alpha: if isAlpha(ch: ch) { currentTokenText.append(ch) } else { state = initToken(ch: ch) currentToken.text = String(currentTokenText) currentToken.type = .alpha tokenList.append(currentToken) currentTokenText = [] currentToken = NJToken() } case .graterEqual: break case .greaterThan: if ch == "=" { currentTokenText.append(ch) state = initToken(ch: ch) currentToken.text = String(currentTokenText) currentToken.type = .graterEqual tokenList.append(currentToken) currentTokenText = [] currentToken = NJToken() } case .digit: if isDigit(ch: ch) { currentTokenText.append(ch) } else { state = initToken(ch: ch) currentToken.text = String(currentTokenText) currentToken.type = .digit tokenList.append(currentToken) currentTokenText = [] currentToken = NJToken() } } i += 1 if i == scriptList.count { state = initToken(ch: ch) currentToken.text = String(currentTokenText) currentToken.type = .digit tokenList.append(currentToken) currentTokenText = [] currentToken = NJToken() } } print(tokenList)
结果：
1 2 3 4 5 6 7 8 9 [ComTest.NJToken( type: Optional(ComTest.NJTokenType.alpha), text: Optional("age")), ComTest.NJToken( type: Optional(ComTest.NJTokenType.graterEqual), text: Optional(">=")), ComTest.NJToken( type: Optional(ComTest.NJTokenType.digit), text: Optional("45"))]
当然，这段代码还有很多值得优化的地方，为了实现思路，很多地方写的相当硬核。
不过，这还没完成，接下来才是重头戏。
正则表达式 大家可能发现了，上面的swift代码其实很不严谨，相当硬核，而想要更严谨，正则表达式 可以用来解决这个问题。
正则表达式
我们来解析int age = 40（此处不是按照swift语法来做的，只是一个简单的例子而已），这个语句中能解析出来的词法是：
1 2 3 Int: 'int' id: [a-zA-Z_]([a-zA-Z_]|[0-9]*) Assignment: '='
这里，又出现了一个问题，int 这个关键字，和id标识符很容易冲突，都是字母开头，后面跟着其他字母。
当然，关键字的优先级肯定是要高于标识符的，一般的语言也不允许用关键字做标识符。
所以，在词法分析器中，我们应该区分关键字和标识符。
具体思路就是：
当第一个字符是 i 的时候，我们让它进入一个特殊的状态。接下来，如果它遇到 n 和 t，就进入状态 4。但这还没有结束，如果后续的字符还有其他的字母和数字，它又变成了普通的标识符。比如，我们可以声明一个 intA（int 和 A 是连着的）这样的变量，而不会跟 int 关键字冲突。
了解了思路，接下来就是用自己熟悉的语言来实现了，这里就不贴代码了。
顺便说一下swift中的正则表达式用NSRegularExpression来处理。
总结 手写一个词法分析器，我写的这个，其实就是个简单的展示demo，还有很多问题，优化什么，我真是能力有限，以后再说。
词法分析器的过程大概就是这样：
要实现一个词法分析器，首先需要写出每个词法的正则表达式，并画出有限自动机，之后，用代码表示这种状态迁移过程
