词法分析思维导图
词法分析介绍
树图思维导图提供 词法分析 在线思维导图免费制作，点击“编辑”按钮，可对 词法分析 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：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,...}
优先级
() > * > · > |
正规文法和正规表达式是等价的，可以相互转换
相关思维导图模板
树图思维导图提供 解决自卑问题思维导图 在线思维导图免费制作，点击“编辑”按钮，可对 解决自卑问题思维导图 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：f24b9de40cec41d332a3b50565b4f6e4
树图思维导图提供 系统需求分析与设计文档描述实践（作业名称） 在线思维导图免费制作，点击“编辑”按钮，可对 系统需求分析与设计文档描述实践（作业名称） 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：53431533c8b70140e2fb252631ff8c4b
沪公网安备 31011502019485号
上海工商