进行语法分析后得到了 token 流，对 token 流进行分析以得到语法树的过程是语法分析。 语法分析分为两种： 自顶向下的语法分析 自低向上的语法分析 这个方向的定义是来源于树的产生方式。 Context-free Grammar 使用上下文无关语法进行语法定义。 1 S -> a | b | c 非终结符产生（推导到）终结符。 二义性 一个文法可以产生多棵分析树，则为二义性文法。 例如 悬空 else 问题: 有语法: 1 2 3 4 5 S -> if C then S | if C then S else S | id := E C -> E = E | E < E | E > E E -> E + E | E - E | id 1 2 3 4 if x<3 then if x>0 then x:=5 else x:=-5 // 这个 `else` 是哪个 if 的 else ?...
前言 编译原理是很有趣的一门学科，但是相对晦涩难懂。 本文的首要目的是为我自己梳理编译原理的学习笔记，也是为了能为后人有一个参考的资料。 本系列文章将会有若干篇，每篇文章的基本结构将会是： 术语表：用于解释本文中的各种术语 主要内容，将分为不同的几个标题 技巧性的知识 术语表 本系列文章将在每篇的开头先把本文的术语解释一下。 在编译原理的学习过程中，各种奇怪的术语总是令人困扰。 Lexical Analysis 将字符串转换为 Token 串的过程 Token 词法单元, 通过词法分析得到的词法单元 Regular Expression 正则表达式、正规式：用来描述词法的工具 NFA: Non-determined Finite Automaton，非确定有限状态自动机(详细解释见下文) DFA: Determined Finite Automaton, 确定有限状态自动机 词法分析的过程 词法分析的目的就是将一串字符串转化为计算机可以使用的串（也即 Token 串）。 执行这一过程的程序是一种 “扫描器”。按照一定方向（一般是从左到右）扫描字符串，并将得到的 Token 通过一定的方式表达出来 （例如 XML ) 1 2 flowchart LR 字符串 --> id[(扫描器)] --> Token串 那么如何定义某个串为一个 Token 呢？ 这就需要用到正则表达式。 正则表达式是给人类使用的，用于定义 Token 串的工具，而计算机对于正则表达式也是束手无策。 实际上扫描器是基于有限状态自动机的。 正则表达式 本文不详细解释正则表达式，正则表达式理论上对于能够学习编译原理的同学并不陌生。 需要注意的是正则表达式有三种最重要的符号： 联合，通常使用+ 或 | 表示 连接，通常不使用符号表示（或者使用 $\cdot$ 表示） 闭包，通常使用* 表示 上述符号的优先级顺序为从上到下，优先级递增。 当然除此之外还需要括号来表示运算的优先级。...