Skip to content

Latest commit

 

History

History
83 lines (56 loc) · 5.73 KB

2.2 词法分析和语法分析.md

File metadata and controls

83 lines (56 loc) · 5.73 KB

词法分析和语法分析

原文

词法分析

lex

lex 是用于生成词法分析器的工具，lex 生成的代码能够将一个文件中的字符分解成 Token 序列，很多语言在设计早期都会使用它快速设计出原型。我们将 lex 理解为正则匹配的生成器，它会使用正则匹配扫描输入的字符流。

Go

Go 语言的词法解析是通过 src/cmd/compile/internal/syntax/scanner.go文件中的 cmd/compile/internal/syntax.scanner 结构体实现的，这个结构体会持有当前扫描的数据源文件、启用的模式和当前被扫描到的 Token。

src/cmd/compile/internal/syntax/tokens.go 文件中定义了 Go 语言中支持的全部 Token 类型，所有的 token 类型都是正整数。

从 Go 语言中定义的 Token 类型，我们可以将语言中的元素分成几个不同的类别，分别是名称和字面量、操作符、分隔符和关键字。词法分析主要是由 cmd/compile/internal/syntax.scanner 这个结构体中的 cmd/compile/internal/syntax.scanner.next 方法驱动，这个 250 行函数的主体是一个 switch/case 结构：

func (s *scanner) next() {
	...
	s.stop()
	startLine, startCol := s.pos()
	for s.ch == ' ' || s.ch == '\t' || s.ch == '\n' && !nlsemi || s.ch == '\r' {
		s.nextch()
	}

	s.line, s.col = s.pos()
	s.blank = s.line > startLine || startCol == colbase
	s.start()
	if isLetter(s.ch) || s.ch >= utf8.RuneSelf && s.atIdentChar(true) {
		s.nextch()
		s.ident()
		return
	}

	switch s.ch {
	case -1:
		s.tok = _EOF

	case '0', '1', '2', '3', '4', '5', '6', '7', '8', '9':
		s.number(false)
	...
	}
}

我们只是简单看一下词法分析匹配整数的逻辑：在 for 循环中不断获取最新的字符，将字符通过 cmd/compile/internal/syntax.source.nextch 方法追加到 cmd/compile/internal/syntax.scanner 持有的缓冲区中；

当前包中的词法分析器 cmd/compile/internal/syntax.scanner 也只是为上层提供了 cmd/compile/internal/syntax.scanner.next 方法，词法解析的过程都是惰性的，只有在上层的解析器需要时才会调用 cmd/compile/internal/syntax.scanner.next 获取最新的 Token。

Go 语言的词法元素相对来说还是比较简单，使用这种巨大的 switch/case 进行词法解析也比较方便和顺手，早期的 Go 语言虽然使用 lex 这种工具来生成词法解析器，但是最后还是使用 Go 来实现词法分析器，用自己写的词法分析器来解析自己。

语法分析

语法分析是根据某种特定的形式文法（Grammar）对 Token 序列构成的输入文本进行分析并确定其语法结构的过程。从上面的定义来看，词法分析器输出的结果 — Token 序列是语法分析器的输入。

语法分析的过程会使用自顶向下或者自底向上的方式进行推导。

分析方法

语法分析的分析方法一般分为自顶向下和自底向上两种，这两种方式会使用不同的方式对输入的 Token 序列进行推导：

  • 自顶向下分析：可以被看作找到当前输入流最左推导的过程，对于任意一个输入流，根据当前的输入符号，确定一个生产规则，使用生产规则右侧的符号替代相应的非终结符向下推导；
  • 自底向上分析：语法分析器从输入流开始，每次都尝试重写最右侧的多个符号，这其实是说解析器会从最简单的符号进行推导，在解析的最后合并成开始符号
自底向上

常见的四种文法 LR(0)、SLR、LR(1) 和 LALR(1) 使用了自底向上的处理方式，我们可以简单写一个与上一节中效果相同的 LR(0) 文法： $$

  1. S \rightarrow S_1 \
  2. S_1 \rightarrow S_1b \
  3. S_1 \rightarrow a $$ 自底向上的分析过程会维护一个栈用于存储未被归约的符号，在整个过程中会执行两种不同的操作，一种叫做入栈（Shift），也就是将下一个符号入栈，另一种叫做归约（Reduce），也就是对最右侧的字符串按照生产规则进行合并。
Lookahead

在语法分析中除了 LL 和 LR 这两种不同类型的语法分析方法之外，还存在另一个非常重要的概念，就是向前查看（Lookahead），在不同生产规则发生冲突时，当前解析器需要通过预读一些 Token 判断当前应该用什么生产规则对输入流进行展开或者归约，例如在 LALR(1) 文法中，需要预读一个 Token 保证出现冲突的生产规则能够被正确处理。

Go

Go 语言的解析器使用了 LALR(1) 的文法来解析词法分析过程中输出的 Token 序列，最右推导加向前查看构成了 Go 语言解析器的最基本原理，也是大多数编程语言的选择。