词法分析原理

学习课程- 华南理工大学- 刘欣欣

参考教程

参考学习的课程

js 版本的课程

计算机编译的过程
  1. 词法分析
  2. 语法分析
  3. 中间代码生成
  4. 优化
  5. 目标代码产生

词法分析单元

=> <token-name, attr-value>

词法分析课程

  • 词法分析器的设计
  • 正规表达式与有限自动机
  • 词法分析器的自动生成 –LEX

单词符号的识别

  1. 超前搜索

    1. 基本字识别
    2. 标识符识别：
      1. 字母开头的字母数字串，后跟界符或算符

  2. 几点限制 – 不必使用超前搜索

    1. 所有基本字都是保留字，用户不能用它们作为自己的标识符
    2. 基本字作为特殊的标识符来处理，使用保留表

  3. 状态转化图

    • 状态转化图是个有限方向图
    • 用于识别或者接受一定的字符串

参考的项目 antlr

image-20210914115530623

image-20210914120153403

词法分析器的设计

  • 语言单词的规范 – 单词表
  • 状态转化图

基本概念：

  1. 确定有限自动机(Deterministic Finite Automaton) 简称DFA。dfa是匹配速度，是确定的。

  2. 非确定有限自动机(Nondeterministic Finite Automaton) 简称NFA,nfa是匹配结果，是不确定的。

  3. DFA比较快，但不提供Backtrack（回溯）功能，NFA比较慢，但提供了Backtrack功能。

  4. NFA是基于表达式的（Regex-Directed），而DFA是基于文本的（Text-Directed）。

  5. DFA引擎在任意时刻必定处于某个确定的状态，而NFA引擎可能处于一组状态之中的任何一个，所以，NFA引擎必须记录所有的可能路径（trace multiple possible routes through the NFA），NFA之所以能够提供Backtrack的功能，原因就在这里。

NFA 和 DFA 是等价的， NFA 可以转化为 DFA

参考的开源项目

开源项目参考 

  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
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107


import (
	"fmt"
 
)
// 定义状态变量
const (
	Initial = iota // 初始状态
	ID             // 原始状态
	Num
	GT
	GE
)

func isNum(c rune) bool {
	if c >= '0' && c <= '9' {
		return true
	}
	return false
}

func isAlpha(c rune) bool {
	if (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') {
		return true
	}
	return false
}



func main() {
	// 读取输入的文本
	_srcRawLine := "age12>=45" + "\n"
	var _state = Initial
	var _outToken = ""

	for _, _char := range _srcRawLine {
		var _doTwice = false
		for {
			switch _state {
			case Initial:
				_doTwice = true
				_outToken = ""
				if isNum(_char) {
					_state = Num
				} else if isAlpha(_char) {
					_state = ID
				} else if _char == '>' {
					_state = GT
				}
				_outToken += string(_char)
				//break
			case ID:
				if isAlpha(_char) || isNum(_char) || _char == '_' {
					_outToken += string(_char)
				} else {
					fmt.Println("ID", _outToken)
					_state = Initial
				}
				//break
			case Num:
				if isNum(_char) {
					_outToken += string(_char)
				} else {
					fmt.Println("Num", _outToken)
					_state = Initial
				}
				//break
			case GT:
				if _char == '=' {
					_outToken += string(_char)
					_state = GE
				} else {
					fmt.Println("OP", _outToken)
					_state = Initial
				}
				//break
			case GE:
				fmt.Println("OP", _outToken)
				_state = Initial
				//break
			}

			if _state != Initial || _doTwice {
				break
			}
		}
	}

	//结束时输出

	// switch _state {
	// case ID:
	// 	fmt.Println("ID", _outToken)
	// 	break
	// case Num:
	// 	fmt.Println("Num", _outToken)
	// 	break
	// case GT:
	// 	fmt.Println("OP", _outToken)
	// 	break
	// case GE:
	// 	fmt.Println("OP", _outToken)
	// 	break
	// }

}

NFA 是不确定的， DFA 是确定的，因此 要将不确定的 NFA 转化为 DFA 这种才好。

学习教程

参考b站教程