词法分析器

文档状态：编辑中....

Table of Contents

首选要熟知编译的整个过程的几个阶段,第一步词法分析器,本blog讲述词法分析的构造原理以及基本技术

  1. 熟知词法分析器的任务[逐行扫描]
  2. 对于词法分析器的要求[功能,单词符号种类]
  3. 词法分析器的设计
  4. 正规表达式和有限自动机[*]
  5. 词法分析器的自动产生--LEX

误区订正

功能

输入字符串------[___]---->输出tok
输出的单词符号的 表示形式 (单词种别,单词自身的值)

设计

拆分结构:程序文件 |输入缓冲区|预处理子程序|扫描器|扫描缓冲区

扫描缓冲区使用的半区互补策略解决一些 问题

超前搜索问题

辣鸡语言需要的超前搜索问题,所以所有语言都是辣鸡?其实是一些没必要的语法糖增加了扫描器的难度
超前搜索问题分布在

解决方案[加上几点限制,但是限制不完]

怎样写

工具需要:
状态转换图
- 可用来识别(或接受)一定的字符串,比如:常数状态转换图,标识符状态转换图,
像基本字这种东西不像标识符一样存在无数种,既然是有限的且数量比较少,就使用保留字表就行了.

有了状态转换图再将其转化为程序

正规表达式和有限自动机

FAQ

  1. 正规式与正规集是什么?
    我们要研究的程序语言的所有单词词汇构成的集合就是字的集合叫正规集,但这句话并非定义
    [1] 正规集可以用正规表达式表达
    [2] 正规表达式是表示正规集的一种方法
    [3] 一个字集合是正规集当且仅当它能用正规式表示

2.正规式和正规集的递归定义
1. $({ \varepsilon})$和 $({ \varnothing })$上的正规式,他们所表示的正规集为 $({ \{\varepsilon\} })$ 和 $({ \varnothing })$
2. 任何a $({ \in \sum })$,a是 $({ \sum })$上的正规式,他所表示的正规集为{a},其中a表示字母,a表示正规式,a表示字,即字符串

  1. 正规式满足的规律
    1. 或交换e1|e2=e2|e1
    2. 或的左结合=或的右结合e1|(e2|e3)=(e1|e2)|e3
    3. 乘法的左结合=或的右结合
    4. 乘对或的左分配e1(e2|e3)=e1e2|e1e3
    5. 乘对或的右分配(e2|e3)e1=e2e1|e3e1
    6. 乘与空的交换$({ e \varepsilon })$=$({ \varepsilon e=e ----e_1 e_2\neq e_2 e_1})$

类似冯诺依曼构造自然数的方案[左侧是集合,右侧是表达式]
$({ \varnothing })$---->0
$({ \{ \varnothing \}})$---->1
$({ \{\varnothing \{ \varnothing \}\} })$---->2

DFA[确定有限自动机]

就是状态转换图的高度形式化,便于后继做数学上的加工
易于程序实现

使用五元式定义($({ S, \sum,f,S_0,F })$)
$({ S为有穷状态机, \sum为有穷输入字母表,f为状态转换函数,S_0为唯一的初态 ,F为可空终态集 })$

DFA与NFA定义区别
1. 状态转换函数的不同,DFA的状态转换函数是单值映射,可以没有下一状态,但是一旦有必须唯一,但是NFA不唯一
2. 初态不一样,DFA的初态是唯一的,而NFA的初态可以是一个集合(多个)

DFA与NFA状态图区别
1.弧上的标记的标记可以是 $({ \sum^‘ 中的一个字,甚至可以是一个正规式,而不一定是单个字符 })$
2. 可以有多个初态
3. 同一个字可能出现在同状态射出的多条弧上
4. [caution]DFA弧上不允许出现 $({ \varepsilon })$,因为它是字

DFA是NFA的特例

NFA[非确定有限自动机]

NFA具有更强的直观性,易于人们设计和理解

使用五元式定义($({ S, \sum,f,S_0,F })$)
$({ S为有穷状态机, \sum为有穷输入字母表,f为状态转换函数,S_0为初态集合 ,F为可空终态集 })$

NFA<=>DFA

基于上面提出的定义上或者是状态图上的差异进行改造消除差异
两者进行转换具有很大的意义,因为基于NFA设计十分简单,基于DFA应用于程序实现比较方便,这样就可以先根据NFA设计,再通过转化为DFA之后进行程序实现

  1. 消除多个初态问题[easy]
  2. 消除弧上的正规式[拆开]
  3. 消除 $({ \varepsilon })$ [子集法, $({ \varepsilon-closure(I) 即 \varepsilon-闭包 })$ ]
    要熟练了解epsilon闭包的定义

$({ \varepsilon-closure(I) 其实就是单独的状态们重新根据某种规则视状态集为基本单位,这种规则即为针对 \varepsilon 的扩展})$,说来说去就是 $({ \varepsilon^*a\varepsilon^* 这种包含多个状态节点的状态们看成一个状态以达到消除 \varepsilon的目的 })$

正规式与有限自动机的等价性

  1. 对任何FA M,都存在一个正规式r,使得L(r)=L(M)
  2. 对于任何正规式r,都存在一个FA M,使得L(M)=L(r)

[1]好证[2]使用运算符数量归纳法

确定有限自动机的化简

引入略微绕口的概念,不太方便使用，想要熟练化简，就要了解到底是化简什么，如果状态A，B等价,那么两者可以化为一个状态,除此之外多余状态也要删除

什么是等价和多余状态

$({ 设DFA M=(Q,\sum ,f,S_0,F),s,t \in Q,})$, 对于任何$({ a \in \sum^*[字], f(s,\alpha) \in F 当且仅当 f(t,\alpha)\in F})$,称s和t是等价的

输入字母表中的所有字符之后仍然回到{A，B}这个集合或者都是跳转到C状态，那么A，B就可以看作是一个状态，那么这就是化简了!

把S划分为终态和非终态两个子集形成基本划分 $({ \prod [说什么以 \varepsilon 为划分原理....] })$

将终态和非终态分开划分的原理是，$({ 终态有一条到达自身的 \varepsilon 道路,而非终态没有到达终态的 \varepsilon 道路})$

实现简化划分的算法
有些东西就是这样,通过数学语言的描述因为高度抽象, (ノ▼Д▼)ノ 总是不愿再看第二遍,但是用自然语言又描述不够清楚和严谨,这个算法也是这样.对了,这个算法有一个理论基础 $({ \zeta })$ ,先说明一下,对了这种定义方式是递归性质的

算法这样看起来就明朗多了 ⧸⎩⎠⎞͏(・∀・)⎛͏⎝⎭⧹,不断从集合 $({ D^n })$ 中取出状态A,B...,输入字符,一旦两者的输出状态落入到现有划分的不同集合中,那么就将当前集合按照A,B,...割裂,最终形成最简自动机.