编译原理-词法分析(Lexical Analysis)

概念

概览表

名词	解释	示例
lexical analysis，scanning	词法分析	-
Token	词法单元	(if,-), (id,x)
Lexeme	词素，词法单元的实例

语言的定义

• 文法(G, Grammar): 四元组$G = (V_N,V_T, S, P )$G=(VN​,VT​,S,P)，
• 其中 $V_N$VN​：一个非空有限的非终结符号集合，它的每个元素称为非终结符，一般用大写 字母表示，它是可以被取代的符号；
• $V_T$VT​：一个非空有限的终结符号集合，它的每个元素称为终结符，一般用小写字母 表示, 是一个语言不可再分的基本符号；
• S：一个特殊的非终结符号，称为文法的开始符号或识别符号，S ∈ VN。开始符号 S必须至少在某个产生式的左部出现一次； 设V是文法G的符号集，则有：$V = V_N ∪ V_T ， V_N ∩ V_T= ∅$V=VN​∪VT​，VN​∩VT​=∅
• P：产生式的有限集合。所谓的产生式，也称为产生规则或简称为规则，是按照一 定格式书写的定义语法范畴的文法规则。
  例：
  

BNF

• BNF的基本语法： <符号> ::= <使用符号的表达式>
• 双引号（" "）中的字符串（“word”）代表这些字符本身，而double_quote代表双引号。
• 双引号外的字符串（有可能带下划线）代表语法部分。
• 尖括号（< >）中的内容为必选项。
• 方括号（[ ]）中的内容为可选项。
• 大括号（{ }）中的内容为可重复0至无限次的项。
• 竖线（|）表示其左右两侧任选一项，相当于 OR 的意思

例：java中for语句的BNF：

FOR_STATEMENT ::=
　　"for" "(" ( variable_declaration |
　　( expression ";" ) | ";" )
　　[ expression ] ";"
　　[ expression ] ";"
　　")" statement

正则表达式

下面是Lex 的正则表达式符号定义，更多语言可参考：http://www.greenend.org.uk/rjk/tech/regexp.html

表达式	匹配	例子
r1r2	连接
r1|r2	或
®	不改变r表示，主要是用于确定运算优先关系
r*	零个或多个实例
r+	一个或多个实例
r?	零个或多个实例
[a-c]	等价于a|b|c，或 [abc]
.	除了换行符以外的任意字符
^	一行的开始
$	行的结尾
[^abc]	除了abc以外的任何字符
r{m,n}	重复出现次数m-n
r1/r2	后面有r2时的r1	abc/123
\c	运算类字符的字面值	\*,\$,\|

正则文法 （Chomsky 3型文法）

• 定义

• P中产生式具有形式$A\longrightarrow \alpha B$A⟶αB，$A\longrightarrow B$A⟶B (右线性)，或者$A\longrightarrow B\alpha$A⟶Bα，$A\longrightarrow B$A⟶B(左 线性)， 其中$AB \in V_N，\alpha \in V_T*$AB∈VN​，α∈VT​∗。
• 也称为正规文法RG、线性文法：若所有产生式均是左线性，则称为左线 性文法；若所有产生式均是右线性，则称为右线性文法。
• 产生式要么均是右线性产生式，要么是左线性产生式，不能既有左线性 产生式，又有右线性产生式

• 正则表达式(regular expressions, RE) 是 定义正则语言(regular languages, RL)的标准工具 ，正则表达式和正则文法等价，可以互相转化

• 其定义的集合叫做正则集合(regular set) ， 是词法单元的规约

• 识别3型语言的自动机称为有限状态自动机(FA)。

例：

• L(a(a|b)*) = {a,aa,ab,aaa, aab,aba,abb,aaaa, aaab,…}

DNF 确定有限状态自动机

确定有限自动机DFA是一个五元组 $M =(SS,\Sigma ,\delta,S_0,TS)$M=(SS,Σ,δ,S0​,TS)，

• SS ：有限的状态集合 {S0，S1，S2，…}
• $\Sigma$Σ ：有限的输入字符表
• $\delta$δ ：状态转换函数, 是单值全映射函数；
• S0 ：初始状态， S0 $\in$∈SS
• TS ：终止状态集，TS$\subseteq$⊆SS

两种表示方式：

• 状态转换图 ：用有向图表示自动机，比较直观，易于理解；
• 状态转换矩阵(转换表)：用二维数组描述自动机，易于程序的自动实现；

• 有限状态自动机实际指的是一个驱动程序，读取字符串，并根据转换图或转换表分析输入，自动给出结果.

NFA(非确定的有限状态自动机)

• 和DFA的主要区别在于：不要求转换函数是单值的。

子问题

NFA -> DFA

RE -> NFA

Thompson算法

RE ->DFA

DFA的最小化

合并等价状态; (状态合并法)
分离不等价状态 ;(状态分离法)

• 状态分离法：

工作流