• 编译原理复习——词法分析

    词法分析程序的主要功能
    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
    不确定的有穷自动机 NFA
    NFA是一个五元组， 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‘是等价的
    以及DFA的最小化转化参考

     

  • 相关阅读:
    大数据挖掘决策树计算过程
    FP独立站该怎么运营？斗篷黑科技教您找对方法引流获客
    垃圾回收只知道标记清除？一文帮你打通V8垃圾回收
    Activiti回退与跳转节点
    proxmox pve /dev/mapper/pve-root扩容
    【目标检测算法】YOLO-V1~V3原理梳理
    赛码系统——根据文件生成时间先后顺序对文件进行排序
    [附源码]java毕业设计病历管理系统设计
    vuex的安装和使用
    如何快速掌握B站数据分析，发现更多精彩内容？
  • 原文地址：https://blog.csdn.net/m0_53345417/article/details/127602807