-
编译原理复习——词法分析
词法分析程序的主要功能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的最小化转化参考 -
相关阅读:
DDR3笔记 频率配置
【HDFS】ResponseProcessor线程详解以及客户端backoff反压
北大肖臻老师《区块链技术与应用》系列课程学习笔记[25]以太坊-智能合约-5
nodejs微信小程序-实验室上机管理系统的设计与实现-安卓-python-PHP-计算机毕业设计
zephyr 单链表
流媒体传输 - RTSP Over HTTP
8款好用的电脑监控软件分享
离子液体[EMIm][PF6],[HMIm][PF6],[C14MIm][PF6]修饰纳米Fe3O4，TiO2和SiO2（离子液体修饰物）
智慧火灾应急救援：无人机、直升机航拍视角下的火灾应急救援检测数据集&代码
【PHP漏洞-弱类型】基础知识、php弱相等、报错绕过
- 原文地址：https://blog.csdn.net/m0_53345417/article/details/127602807