-
编译原理复习——词法分析
词法分析程序的主要功能1.输入源程序，输出单词符号2. 从左至右 ， 从上至下 逐个字符地对源程序进行扫描3.把构成源程序的 字符串 转换成 单词符号的 序列4.输出单词序列用于语法分析其他功能滤掉空格、跳过注释、换行符行、列计数发现并 定位 词法错误词法分析程序的输出形式单词符号分为以下5类：关键字（保留字，基本字）标识符：变量名，过程名常数： 整形，实型运算符：+, -, *, /,…界符： ; , ( ) …状态转换图 是词法分析器的重要组件之一有限方向图， 结点 表示状态，状态间用 箭弧 连 接，箭弧上的 标记 （符号）代表射出结点状态下有可能出现的输入字符一张状态转换图有：（ 1 ）有限个状态 （ 2 ）一个初态 （ 3 ）一个或多个终态 , 用 双圈表示确定的有穷自动机 (DFA)确定的有穷自动机 DFA 定义： DFA 是一个五元组， M=(K, Σ, f , S, Z)
状态转换图 : DFA M 含有 m 个状态， n 个输入字符，则状态转换图有 m 个结点，每个结点至多有 n 条箭弧射出，每条箭弧用 Σ 中一个不同的输入字符做标记
DFA的特点：(1) 初态唯一(2) 输入字符不包括 ε(3) 有向边上只有一个字符(4) 一个状态对于某个字符，最多只有一条出边所以上图中所示的状态转换图不是一个DFA可被 DFA 识别的单词符号对 ∑ * 中任意符号串 t ，若存在从初态到某一终态的 通路，且通路上所有弧标记符连接成的字等于 t ，则称 t 可为 DFA 所识别 ( 读出或接受 ) 。 即对于任意字符串 t ∈ Σ, f (S ， t)=P, P ∈ Z可识别空串若 M的 初态结点同时也是终态结点，则空字 ε 可为 M所识别 f (k i ， ε)= k i不确定的有穷自动机 NFANFA是一个五元组， M=(K, Σ, f , S, Z)
只有f和S是和DFA是不同的
NFA的特点：(1) 初态不 唯一(2)输入字符包括 ε(3)有向边上可以为 字符串(4)一个状态对于某个字符，可能有 多条输 出边 ，即状态的后继不唯一可被NFA识别的单词符号对∑ * 中任意字α，若存在从初态到某一终态的通 路，且通路上所有弧标记符连接成的字等于α，则称α可为NFA所识别(读出或接受)。可识别空串若M的初态结点同时也是终态结点，或存在某初 态到某终态的ε通路，则空字ε可为M所识别。DFA是NFA的特例有穷自动机的等价性对于每个NFA M，存在一个DFA M’使得 L(M)=L(M’)对于任何两个有穷自动机，如果L(M)=L(M’)， 则称M不M‘是等价的NFA转换成DFA采用的方法是子集法具体参考 NFA转换成DFA的方法——子集法_用编程写诗的博客-CSDN博客_nfa转dfa子集法以及DFA的最小化转化参考 -
相关阅读:
Web Vue VI
python3.11教程1：python基础语法、程序控制、函数
java-net-php-python-jsp员工时间管理系统查重PPT计算机毕业设计程序
flutter 随机数的生成 四舍五入
Contos7中Mysql忘记密码或者初始登录时密码错误解决方法
【Python人工智能】Python全栈体系（二十一）
润和软件HopeStage与华宇信息TAS应用中间件完成产品兼容性互认证
GitHub：黑客盗用 OAuth 令牌，导致数十个组织数据泄露
心理测评测试h5公众号字节微信小程序app开源版开发
面向对象之设计原则与设计模式
- 原文地址：https://blog.csdn.net/m0_53345417/article/details/127602807