• Flex and Bison 阅读与学习笔记

    本文的内容来源于本人阅读 flex & bison的笔记和项目工程学习中遇到的问题。如果你能从中获得一丝丝帮助，本人将不胜荣幸。

    文章目录

    Ⅰ、目录与批注

    前四章 引言和使用介绍

    页 码批注备注
    19各部分通过%% 分割，其分别为 声明；模式与动作 和 C代码
    24atoi ：ascii to integer yylval：这个变量用来储存记号值，定义为整型
    25yacc：yet another compiler compiler
    antlr：another tool for language recognition    		java 的一个自定义语法编译器 和 bison 前身的全称
    26上下文无关文法 CFG 巴克斯范式 31BNF
    31如果一种文法是有歧义的，bison会报告在冲突（conflicts），而且标示出针对给定的输入哪里会有两种不同的分析。优先级 和 分组会解决二义性 还有 GLR处理二义性和任意的向前看符号
    ChapterⅡflex 的 使用
    35正则表达式使用元语言？？与对象语言相对，指描写和分析某种语言所使用的一种语言或符号集合；《语言与语言学词典》对语言学的解释是：纯理语言，指用来分析和描写另一种语言的语言或一套符号
    36正则表达式字符
    38flex如何处理二义性尽可能多地匹配字符；匹配更早出现的模式
    40开头设定%option noyywarp 来要求其不使用yywarp
    yyrestart（f）读取输入输出文件 f；
    42flex有灵活的三层输入结构
    yyin 来读取所需文件
    输入缓冲区
    重定义yy_input
    其使用yy_buffer_state的数据结构来处理输入
    43unput（c）的调用可以把字符 c 退回输入流
    44所有没有被匹配的输出都将拷贝到yyout中
    设置%option nodefault，使其不添加默认的规则，这样当输入无法被给定的模式匹配时，词法分析器可以报告一个错误。
    起始状态：其运行在特定时刻哪些状态被匹配 %x %s
    47flex 提供一个叫yylineno的变量，其被用来记录行号。我们可以直接使用它。
    49case_insensitive 其要求flex生成一个大小写无关的词法分析器
    51符号表 名字的查找：线性探索的哈希法。每个字符用 9 承之前的哈希值，让后再异或这个值。
    52yytext中的字符串被在下一个词法记号被分析时替换掉。
    58fiFL的作用
    字符常量 单引号 开始 ，单引号结尾 ‘ ’    		问题
    Chapter Ⅲbison 的 使用
    63flex讲输入流分解成若干个片段，bison则分析这些记号并基于逻辑进行组合。
    左部：LHS
    右部：RHS
    64bison不会自动地为我们创建语法分析树，需要我们自己实现。
    65bison处理时，其创建一组状态，每个状态都反映出一个或多个分析过的规则在可能的位置
    移进：当语法分析器读取记号，无法结束一条规则时，将其压入一个堆栈，让后切换到一个新的状态，此状态反映了刚刚读取的记号。
    规约：如果压入的符号可以组成规则的右部，将其全部从堆栈弹出，让后左部符号压入堆栈。    		（例子）
    66LALR（1）：LALR（1）全称为lookahead-LR（1）,是由LR（1）语法分析器变来的，其中L（Left Scan）表示自左向右处理输入，R（Right Reduce）表示生成最右推导，而数字1表示使用先行1个符号。
    第三章 LALR（1）的构造_lalr(1)_Bash_linux的博客-CSDN博客
    而LALR（1）简化了LR(1)，采用合并同心集方法，大大缩小了LR（1）的自动机状态规模，功能介于SLR(1)与LR(1)之间，但应用于目前的语言，已经绰绰有余。YACC就是使用这种分析方法。
    67三部分组成：定义；语法分析器的规则；C代码
    bison定义的规则会被编译成数组的形式，其内容代表了可以匹配输入记号的状态机。
    69%union定义符号值的类型，定义完后要声明%type <>
    没有显示的语义动作时，规则默认语义$$ = $1;
    70文字字符记号：记号的ASCII 就是记号的编号。
    71yyval 现在是联合类型，双精度浮点数的值不不给yyval.d
    72eval（调用计算）和 free是都采用深度优先
    73flex 的 -o 参数
    76声明优先级：%left %right %noassoc
    负数规则%prec
    77一个高级计算器的flex bison 代码实现（错误恢复机制）
    79用户自定义的函数 ufcall 节点；
    控制流使用 flow节点。
    81list的 定义是右递归的，否则使用更麻烦。
    83简单的错误恢复：放弃错误后续的语法符号，直到达到一个记号为error为有效的点；接着开始忽略后续的输入，直到找到一个可以被移进的记号，让后从此处继续开始分析。
    Chapter Ⅳ分析 SQL
    96MySql的输入是bison分析的。
    100逆波兰式的优点
    105btwode 的切换（因为 and 有 &&的意思 还有 between and的意思）
    107问题：mysql中的 = 号除了比较
    109语法分析器
    匹配长度可变的项目列表
    113子代码是基于位编码的
    114函数
    116select 语句的 语法规则**（可选的）** 这个对我的项目很重要

    flex 规范参考

    页 码批注备注
    20flex 基础命名 在这里插入图片描述
    133结构规范在这里插入图片描述
    134BEGIN 宏 在这里插入图片描述
    135上下文相关性
    特殊的行首模式 ^ $ ；起始状态；显示代码；
    2.07 Flex如何处理上下文相关性_如何做上下文相关性处理_ronnie88597的博客-CSDN博客 在这里插入图片描述定义 替换 在这里插入图片描述
    137echo 在这里插入图片描述
    137标准输入文件链
    yyrestart（file）来使得词法分析器读取任意标准输入文件
    137输入缓冲区
    139使用c++编辑 input 改为 yy_input 避免冲突
    140交互 和 批处理模式下的 词法分析器
    141文字块 在这里插入图片描述
    142多重词法分析器
    143在这里插入图片描述144字符集
    EBCDIC
    146可重入词法分析器 嵌套文件 多重词法分析器 在这里插入图片描述
    150yylex 的返回值 在这里插入图片描述
    %s 共享模式 %x 独占模式
    yylex
    flex 的变量 与 函数在这里插入图片描述
    151unput（）返回字符给输入流；
    yyless 和 unput 效果一样，但yyless 通常更快
    152yyleng （） = strlen（yytext）
    153问题 yy_decl
    154/第四部分 函数 function/ int yywrap()
    { /此函数必须由用户提供,或者声明 %option noyywrap当词法分析程序遇到文件结尾时，它调用例程yywrap()来找出下一步要做什么如果返回0，扫描程序继续扫描，如果返回1，扫描程序就返回报告文件结尾/ return 1; }
    yywarp 的 作用在这里插入图片描述

    bison 参考规范

    页 码批注备注
    155三部分组成 定义 %% 规则 %% 用户子例程 在这里插入图片描述
    156 在这里插入图片描述在这里插入图片描述定义；动作
    157嵌入动作
    159移进 规约冲突 输入字符存在两种可能的语法分析器 一般bison选择移进
    归约 归约冲突 一个记号可以结束两条不同规则的时候 选择先出现的那条规则进行归约
    当GLR语法分析器遇到冲突时，理论上其会分裂出并行的两种可能的分析
    %expect
    161
    bison 列表中一个结束标记 伪符号 $end 在这里插入图片描述
    %code
    162bison从 错误分析中恢复，其从分析器堆栈中 抛弃符号 和 符号值在这里插入图片描述错误恢复
    163继承属性 ($0)
    164词法反馈 ：从语法分析器反馈上下文信息 给 词法分析器
    166位置 %location
    168优先级声明在这里插入图片描述在这里插入图片描述
    170bison 处理左递归 要比 右递归 （如果列表中的元素个数很少而且你需要把他们存到一个链表中时，右递归更有用）更有效率。
    规则堆栈大小 TTINITDEPTH
    173特殊字符
    $ 引入一个值引用
    @ 引入一个位置引用
    174%start 声明 在这里插入图片描述
    声明符号类型 %union
    176记号 编号 -d生成的文件内 查看
    tab.h包含了与语法分析器相关的声明、常量和数据结构。其他源文件（如Flex的源文件）需要包含此头文件，以便正确地使用语法分析器生成的标记（tokens）和语法规则。
    177%union %type
    178可变语法和多重语法；合并的语法分析器
    179%name-prefix 或者 -p标志 注意：在运行项目的时候，编译器对我进行警告，这个已经过时，最新的用法应该是 %define api.prefix { xxx }
    180y.output文件
    --report = all
    181bison 库文件
    yyabort
    yyaccept
    yybackup 移出当前符号并替换为 另一个记号
    yyclearin 放弃预读符号
    yydebug
    yyerrork 其用来让语法分析器回到正常
    yyerror
    yyparse

    其余内容

    页 码批注备注
    CHAPTER Ⅶ二义性冲突
    187指针模型：一个指针将会在每次读到一个记号时在bison语法中移动。
    188在这里插入图片描述
    189冲突类型
    191语法分析器状态 -v 生成 output文件（其内为所有状态机的）
    1926A 的归约问题（解决）
    193归约 归约冲突：在冲突发生时，未被选择的规则在方括号中，其总是选择更早出现的规则来解决 归约 归约冲突
    195移进 归约冲突：
    在这里插入图片描述bison 总是选择移进来解决 冲突
    198常见的三种 冲突情况 表达式语句（语法是递归的）；if/then/else；嵌套列表(嵌套循环) 移进归约 冲突；规则的重叠 （归约 归约 -> GLR语法）
    大多数的移进 归约冲突来源于 bison有限的向前查看
    CHAPTER Ⅷ错误报告 与 恢复
    213为语法分析器添加位置信息 使用了yyloc内的位置 信息 和一个新的 lyyerror
    215带有文件名的位置信息
    218错误恢复技巧：尝试在输入流中向前移进足够远，这样新的输入就不会被旧的输入所影响
    219%destructor 声明：让bison知道弹出一个具体语义值符号时应该做什么 在这里插入图片描述
    220交互式语法分析器 的 恢复；先用yyclearin 放弃预读的内容；再用yyerrok 重新开始正常的分析；
    CHAPTER Ⅸ两者的进阶
    223纯 词法 语法 分析器的概念： <> 把所有静态数据结构替换为参数传递给词法分析器和语法分析器中的例程
    224纯 flex 在这里插入图片描述
    225将原本的静态数据改为 指向我们的实例数据⭐
    228%option bison-bridge bison-location reentrant
    244GLR分析
    247设定GLR语法分析器
    249c版 的 flex 和 C++的bison联合

    Ⅱ、相关练习代码

    学习历程

    在学习过程中，根据龙书的前几个章节又重新了解了一下编译原理，这个方向还是比较难理解的。我是由于工程的原因需要去使用flex and bison。因此我的工作停留在应用层面应该是足够了的。想深度理解编译原理这个课题龙书应该是最专业的入门了，有需求的同学可以去看一下。这些教材的中文版github都是可以找到pdf版本的。

    我的学习历程是先阅读了两本书才接触的代码，虽然在阅读过程中也结合着例子进行代码编写，但理解程度远不如去看工作中的一整个项目理解的快和好。在接触工程代码前，推荐先认真去看一下flex and bison 第三章的那个两者结合的例子，代码包含在下方代码链接的bison文件夹下。

    代码实例

    这个算是flex 和 bison一起使用来进行一个计算机程序的编写，从中可以理解如何运用flex进行词法分析，使用bison进行语法分析并且两者结合起来后的一些规范，如重命名，flex的c代码在bion中进行使用。对于初学者建议注意bison -d 生成的 tab.h 文件，对理解会有所帮助。

    额外提一点，虽然编译器是先进行词法分析，在进行语法分析。但对于flex 和 bison的编译则是先进行bison -d 的选项，详细看上文行。因为bison文件内含有预先定义好的 token 等一些列关键字，而flex的作用就是去识别他们。具体也可去看下方flex-bison-code内的makefile文件。
    在这里插入图片描述
    参考文献的第三篇也可以好好读一下，可以更好地理解两者的工作原理和他们在工程中的应用。
    flex-bison-code

    参考文献

    1. flex & bison
    2. Compilers: Principles, Techniques, and Tools
    3. Flex(scanner)/Bison(parser)词法语法分析工作原理
    4. 第三章 LALR（1）的构造_lalr(1)_Bash_linux的博客-CSDN博客
  • 相关阅读:
    牛只识别 牛脸识别 个体识别 身份识别
    python 绘制3D图
    简单的咖啡文化静态HTML网页设计作品 DIV布局咖啡馆文化网页模板代码 DW咖啡网站制作成品
    [C语言数据结构]队列
    C/C++指针之提高篇详解（二）
    Docker 的基本概念和优势
    大数据毕业设计选题推荐-河长制大数据监测平台-Hadoop-Spark-Hive
    管道-有名管道
    热电厂蒸汽流量如何无线传输至无纸记录仪上显示？
    计算机毕业设计ssm社区基层党建管理信息系统s5738系统+程序+源码+lw+远程部署
  • 原文地址：https://blog.csdn.net/M1170780140/article/details/133915677