词法分析介绍
树图思维导图提供 词法分析 在线思维导图免费制作,点击“编辑”按钮,可对 词法分析 进行在线思维导图编辑,本思维导图属于思维导图模板主题,文件编号是:511ae4f542e9a7140769212afc816068
词法分析思维导图模板大纲
NFA(不确定)
带ε转移
输入字母a,可能有多个方向转移
初始状态至少为1个
DFA(确定的)
不带ε转移
输入字母a,转移方向确定
初始状态唯一
NFA转换为等价DFA
重要运算
ε闭包
ε-closure(I)集合为集合中任意状态通过任意条ε能够到达的状态的集合,是个递归操作
Ia子集
ε-closure(move(I,a)),其中move(I,a)为状态集合I中任意状态在输入字母a后能够到达的状态的集合
子集法
对NFA初始状态求ε闭包,并作为未标记的状态集合加入到DFA的状态集
在DFA中选一个未被标记的状态S标记,对字母表的每个字母,计算Sa子集。如果Sa为新状态,则作为未被标记的状态集合加入到DFA的状态集,并添加转换连线S->Sa
DFA的化简
状态等价条件
一致性条件
两个状态同时为可接受状态或不可接受状态
蔓延性条件
两个状态在输入相同下,转换换台等价
分割法
将所有DFA状态初始置于同一集合内
将大子集内的状态根据终态和非终态分为两个子集
递归分析每个子集的状态,若其中存在集合在输入相同的情况下,转换状态在不同的子集,则需对这些集合进行划分
当这些子集不能再划分时,已经为最简,这时每个子集为DFA的一个状态
正规文法
3型文法G=(VN, VT, S, P)
正则表达式
递归操作
正规式
正规集
有穷自动机
(a)
{a}
a|b
{a,b}
a·b
{ab}
a*
{ε.a.aa.aaa,...}
优先级
() > * > · > |
正规文法和正规表达式是等价的,可以相互转换
树图思维导图提供 分析传统文化进行创新设计的优秀作品 在线思维导图免费制作,点击“编辑”按钮,可对 分析传统文化进行创新设计的优秀作品 进行在线思维导图编辑,本思维导图属于思维导图模板主题,文件编号是:b10e0023950f5b8b1cd58ca2e19944cc
树图思维导图提供 鱼塘选择途径之媒体网络:案例分析 在线思维导图免费制作,点击“编辑”按钮,可对 鱼塘选择途径之媒体网络:案例分析 进行在线思维导图编辑,本思维导图属于思维导图模板主题,文件编号是:dce4835f9b67d75eaf2d0ec0b8906ca0