词法与语法分析器介绍

news/2024/7/14 19:23:56/文章来源:https://blog.csdn.net/weixin_40398522/article/details/139250743

概述

词法和语法可以使用正则表达式和BNF范式表达,而最终描述文法含义的事状态转换图

Lex与YACC

词法分析器Lex

词法分析词Lex,是一种生成词法分析的工具,描述器是识别文本中词汇模式的程序,这些词汇模式是在特殊的句子结构中定义的

Lex 接收到文件或文本形式的输入时,会将文本与常规表达式进行匹配:一次读入一个输入字符,直到找到一个匹配的模式

如果能够找到一个匹配的模式,Lex就执行相关的动作(比如返回一个标记Token)。另外,如果没有可以匹配的常规表达式,将会停止停止进一步的处理,Lex将显示一个错误信息

Lex 和 C语言是强耦合的,一个.lex文件通过Lex解析并生成C的输出文件,这些文件被编译为词法分析器的可执行版本

lex 或 .l 文件在格式上分为以下3段

    1. 全局变量声明部分
    1. 词法规则部分
    1. 函数定义部分

Lex 变量表

变量名详细解释
yyinFILE* 类型。它指向lexer 正在解析的当前文件
yyoutFILE* 类型。它指向记录lexer输出的位置。默认情况下,yyin 和 yyout 都指向标准输入和输出
yytext匹配模式的文本存储在这一变量中(char*)
yyleng给出匹配模式的长度
yylineno提供当前的行数信息(lexer不一定支持)

Lex 函数表

函数名详细解释
yylex()这一函数开始分析。它由Lex自动生成
yywrap()这一函数在文件(或输入)的末尾调用。如果函数的返回值是1,就停止解析。它可以用来解析多个文件
yyless(int)这一函数可以用来输出除来前n个字符外的所有读出标记
yymore()这一函数告诉Lexer将下一个标记附加到当前标记后

代码

文件 a.l

%{
#include <stdio.h>
extern char *yytext;
extern FILE *yyin;
int count = 0;
%}%%// 两个百分号标记指出了 Lex 程序中这一段的结束和第二段的开始
\$[a-zA-Z][a-zA-Z0-9]*  {count++; printf("  变量%s", yytext);}
[0-9\/.-]+  printf("数字%s", yytext);
=           printf("被赋值为");
\n          printf("\n");
[ \t]+      /* 忽略空格 */;
%%// 函数定义部分
int main(int avgs, char *avgr[]) {yyin = fopen(avgr[1], "r");if (!yyin) {return 0;}yylex();printf("变量总数为:%d\n", count);fclose(yyin);return 1;
}

对于以上代码,解释如下

  • 全局变量声明部分: 声明了一个int型全局变量count,用来记录变量的个数
  • 规则部分: 第1个规则是找 符号开头、第 2 个符号为字母且后面为字符或数字的变量,类似于 符号开头、第2个符号为字母且后面为字符或数字的变量,类似于 符号开头、第2个符号为字母且后面为字符或数字的变量,类似于a,并计数加1. 同时,将满足条件的yytext输出;第2个规则是找数字;第3个规则是找"=" 号;第4个规则是输出"\n"; 第5个规则是忽略空格
  • 函数定义部分: 打开一个文件,然后调用yylex 函数进行词法解析,输出变量的技术,最后调用fclose关闭文件

lex 代码编译

lex a.l
gcc lex.yy.c -o test -ll

测试文件 file

$a = 1
$b = 2

执行如下命令

./test file
变量$a被赋值为数字1
变量$b被赋值为数字2
变量总数为:2

语法分析词YACC

YACC(Yet Another Compiler-Compiler) 是 UNIX/Linux 上一个用来生成编译器的编译器(编译器代码生成器). YACC使用BNF范式定义语法,能处理上下文无关文法

YACC 语法规则

YACC 语法包括3部分,即定义段、规则段和用户代码段

… 定义段 …
%%
… 规则段 …
%%
… 用户代码段 …

代码

词法分析文件: cal.l

%{
#include "y.tab.h"
#include <math.h>
%}%%
([0-9]+|([0-9]*\.[0-9]+)([eE][-+]?[0-9]+)?) {yylval.dval = atof(yytext);return NUMBER;
}
[ \t]   ;
\n |
. return yytext[0];
%%

语法分析文件: calc.y

%{
#include <stdio.h>
#include <string.h>
#include <math.h>
int yylex(void);
void yyerror(char *);
%}%union {double dval;
}
%token <dval> NUMBER
%left '-' '+'
%left '*' '/'
%nonassoc UMINUS
%type <dval> expression
%%
statement_list: statement '\n'| statement_list statement '\n';statement: expression { printf("= %g\n", $1); };expression: expression '+' expression {$$ = $1 + $3;}|   expression '-' expression { $$ = $1 - $3; }|   expression '*' expression { $$ = $1 * $3; }|   expression '/' expression{if ($3 == 0.0)yyerror("divide by zero");else$$ = $1 / $3;}|   '-' expression %prec UMINUS { $$ = -$2; }|   '(' expression ')' { $$ = $2; }|   NUMBER { $$ = $1; }
%%void yyerror(char *str) {fprintf(stderr, "error:%s\n", str);
}int yywrap() { return 1;
}int main() {yyparse();
}

从代码中可以看出,规则部分使用BNF范式

  • expression 最终是NUMBER,以及使用+、-、* 、/ 和 ()的组合,对加、减、乘、除、括号、负号进行表达
  • statement 是由expression 组合而成的,可以输出计算结果
  • statement 是由expression 组合而成的,可以输出计算结果
  • statement_list 是statement的组合

lex 编译

lex cal.l
  • 通过这个命令会生成lex.yy.c,里面维护了NUMBER这个Token的有穷自动机

使用 YACC对 calc.y

yacc -d calc.y
  • 会生成y.tab.c、y.tab.h

最终执行结果

gcc -o calc y.tab.c lex.yy.c
./calc1+2= 33+6= 9

Re2C 与 Bison

词法分析器 Re2c

Re2c 是一个词法编译器,可以将符合Re2c规范的生成高效的C/C++代码,Re2c会将正则表达式生成对应的有穷状态机

代码

num.l

#include <stdio.h>
enum num_t {ERR, DEC};static num_t lex(const char *YYCURSOR)
{const char *YYMARKER;/*!re2cre2c:define:YYCTYPE = char;re2c:yyfill:enable = 0;end = "\x00";dec = [1-9][0-9]*;*   {return ERR;}dec end {return DEC;}*/
}int main(int argc, char **argv)
{for (int i = 1; i < argc; ++i) {switch (lex(argv[i])) {case ERR: printf("error\n"); break;case DEC: printf("十进制表示\n"); break;}}return 0;
}

执行以下命令,转换成c代码

re2c num.l -o num.c

num.c

/* Generated by re2c 3.0 on Sun May 26 21:58:19 2024 */
#line 1 "num.l"
#include <stdio.h>
enum num_t {ERR, DEC};static num_t lex(const char *YYCURSOR)
{const char *YYMARKER;#line 11 "num.c"
{char yych;yych = *YYCURSOR;switch (yych) {case '1':case '2':case '3':case '4':case '5':case '6':case '7':case '8':case '9': goto yy3;default: goto yy1;}
yy1:++YYCURSOR;
yy2:
#line 14 "num.l"{return ERR;}
#line 32 "num.c"
yy3:yych = *(YYMARKER = ++YYCURSOR);switch (yych) {case 0x00: goto yy4;case '0':case '1':case '2':case '3':case '4':case '5':case '6':case '7':case '8':case '9': goto yy5;default: goto yy2;}
yy4:++YYCURSOR;
#line 15 "num.l"{return DEC;}
#line 53 "num.c"
yy5:yych = *++YYCURSOR;switch (yych) {case 0x00: goto yy4;case '0':case '1':case '2':case '3':case '4':case '5':case '6':case '7':case '8':case '9': goto yy5;default: goto yy6;}
yy6:YYCURSOR = YYMARKER;goto yy2;
}
#line 16 "num.l"}int main(int argc, char **argv)
{for (int i = 1; i < argc; ++i) {switch (lex(argv[i])) {case ERR: printf("error\n"); break;case DEC: printf("十进制表示\n"); break;}}return 0;
}

从上面代码中可以看出,这个状态机一共有8种状态,分别是开始状态、yy3至yy9状态,其中yy3状态是错误输出,返回ERR

yy5 状态是对应的正则匹配状态,返回DEC

在这里插入图片描述

YYCURSOR 是指向输入的指针,根据状态的流转,指针加1

语法编译器Bison

对于一条BNF文法规则,其左边是一个非终结符(symbol 或者 non-terminal),其右边则定义该非终结符是如何构成的,也称为产生式(production)

产生式可能包含非终结符,也可能包含终结符(terminal),还可能二者都有

利用BNF文来分析目标文本,比较流行的算法有LL分析(自顶向下的分析,top-down parsing),LR分析(自底向上的分析,bottom-up parsing;或者叫移进-归约分析, shift-down parsing)

其中LR算法有很多不同的变种,按照复杂度和能力递增的顺序依次是LR(0)、SLR、SLR、LALR和LR(1)

Bison是基于LALR分析法实现的,适合上下文无关文法

当Bison读入一个终结符TOKEN时,会将该终结符及其语意值一起压榨,其中这个栈叫做分析器栈(parse stack)

把一个TOKEN压入栈叫作移进。举个例子,对于计算1+2 * 3, 假设现已经读入来1 + 2 * ,那么下一个准备读入的是3,这个栈当前就有4个元素,即1、+、2和*

当已经移进的后n个终结符和组(grouping)与一个文法规则相匹配时,它们会根据该规则结合起来,这叫归约(reduction)

栈中哪些终结符和组会被单个的组(grouping)替换。同样,以1 + 2 * 3;为例,最后一个输入的字符为分号,表示结束,那么按照下面的规则进行归约:

expression '*' expression { $$ = $1 * $3 }

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_1052405.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

欧科云链:Web3.0时代 具备链上数据分析能力的公司愈发凸显其价值

在当今激烈的市场竞争中&#xff0c;新兴互联网领域迅速崛起&#xff0c;Web2.0已相对成熟&#xff0c;用户创造数据&#xff0c;但不拥有数据。被视为新的价值互联网的Web3.0&#xff0c;赋予用户真正的数据自主权&#xff0c;它的到来被认为是打破Web2.0垄断的机遇。 在Web3…

【区块链】Postman功能接口测试

需要将完整的合约部署到fisco上以及启动后端的工程项目 启动WeBASE python3 deploy.py startAll 然后通过127.0.0.1&#xff1a;5002/WeBASE-Front启动webase 在工程日录下启动项目,检查配置文件conf.properties中的合约和用户信息足否与webase-front一致 运行trace的jar包项…

Qt 5前后调色板差异变化

Qt 5之前&#xff1a; QPalette palette;//调色板 设置背景颜色 palette.setColor(QPalette::Backgound, color...);Qt 5之后&#xff1a; 由原有的 Background 模式 更新为 Window 模式 QPalette palette;//调色板 设置背景颜色 palette.setColor(QPalette::Window, color..…

AI智能体研发之路-模型篇(四):一文入门pytorch开发

博客导读&#xff1a; 《AI—工程篇》 AI智能体研发之路-工程篇&#xff08;一&#xff09;&#xff1a;Docker助力AI智能体开发提效 AI智能体研发之路-工程篇&#xff08;二&#xff09;&#xff1a;Dify智能体开发平台一键部署 AI智能体研发之路-工程篇&#xff08;三&am…

python web自动化(Pytest实战)

1.UnitTest框架与Pytest框架对⽐ 1&#xff09; unittest框架介绍 Unittest则是Python语⾔的标准单元测试框架。 Unittest⽀持⾃动化测试&#xff0c;测试⽤例的初 始化、关闭和测试⽤例的聚合等功能&#xff0c;它有⼀个很重要的特性&#xff…

嵌入式UI开发-lvgl+wsl2+vscode系列:2、label(标签)+button(按钮)+slider(滑块)控件熟悉及其示例demo运行

文章目录 一、前言二、常见控件示例demo模拟环境运行及接口熟悉&#xff08;重要&#xff09;如何修改示例main函数测试各种示例1、label示例1.1、label示例1&#xff08;标签基础示例&#xff09;1.2、label示例2&#xff08;标签带阴影效果&#xff09;1.3、label示例3&#…

ComfyUI简单介绍

&#x1f353;什么是ComfyUI ComfyUI是一个为Stable Diffusion专门设计的基于节点的图形用户界面&#xff0c;可以通过各种不同的节点快速搭建自己的绘图工作流程。 软件打开之后是长这个样子&#xff1a; 同时软件本身是github上的一个开源项目&#xff0c;开源地址为&#…

编译原理 期末复习笔记整理(上)

资料借鉴&#xff1a; 【编译原理】期末复习 零基础自学_哔哩哔哩_bilibili 编译原理笔记 第一章 引论 1.编译原理逻辑过程&#xff1a; 词法分析 语法分析 语义分析 中间代码生成 编译代码生成 2.词法分析 任务: 输入源程序&#xff0c;对…

通用代码生成器应用场景三,遗留项目反向工程

通用代码生成器应用场景三&#xff0c;遗留项目反向工程 如果您有一个遗留项目&#xff0c;要重新开发&#xff0c;或者源代码遗失&#xff0c;或者需要重新开发&#xff0c;但是希望复用原来的数据&#xff0c;并加快开发。 如果您的项目是通用代码生成器生成的&#xff0c;…

Java应用中文件上传安全性分析与安全实践

✨✨谢谢大家捧场&#xff0c;祝屏幕前的小伙伴们每天都有好运相伴左右&#xff0c;一定要天天开心哦&#xff01;✨✨ &#x1f388;&#x1f388;作者主页&#xff1a; 喔的嘛呀&#x1f388;&#x1f388; 目录 引言 一. 文件上传的风险 二. 使用合适的框架和库 1. Spr…

NLP(17)--大模型发展(1)

前言 仅记录学习过程&#xff0c;有问题欢迎讨论 大模型的演化&#xff1a; ElMO : 类似双向lstm 结果和词向量拼接 预训练鼻祖 GPT :使用了Transformer 模型 开始使用Token &#xff08;发现预训练的作用&#xff09; Bert&#xff1a;认为双向比单向好 MLM(双向) 优于 LT…

App Inventor 2 Encrypt.Security 安全性扩展:MD5哈希,SHA/AES/RSA/BASE64

这是关于App Inventor和Thunkable安全性的扩展&#xff0c;它提供MD5哈希&#xff0c;SHA1和SHA256哈希&#xff0c;AES加密/解密&#xff0c;RSA加密/解密&#xff0c;BASE64编码/解码方法。 权限 此扩展程序不需要任何权限。 事件 OnErrorOccured 抛出任何异常时将触发此事件…

四川景源畅信:抖音小店新手如何做?

随着短视频平台的兴起&#xff0c;抖音小店成为了许多创业者的新选择。但是&#xff0c;对于新手来说&#xff0c;如何在抖音上开设并经营好自己的小店呢?本文将围绕这一问题展开讨论。 一、明确目标和定位作为抖音小店的新手&#xff0c;首先要明确自己的经营目标和定位。是想…

二叉树尾部分

1.二叉树的销毁 2.二叉树的层序遍历 3.判断二叉树是否为完全二叉树 4.二叉树的性质 1.二叉树的销毁 以后序的方式遍历销毁左右子数&#xff0c;因为前序和中序销毁的话根会被销毁而找不到左右子树的位置&#xff0c;后序的根访问在最后&#xff0c;可以找到左右的子树位置。…

YOLOv10介绍与推理--图片和视频演示(附源码)

导 读 本文主要对YOLOv10做简单介绍并给出推理图片和视频的步骤演示。 YOLOv10简介 YOLOv10是清华大学的研究人员在Ultralytics Python包的基础上&#xff0c;引入了一种新的实时目标检测方法&#xff0c;解决了YOLO 以前版本在后处理和模型架构方面的不足。通过消除非最大抑…

从零开始打造教育APP:在线教育系统源码与开发流程

很多人疑问&#xff0c;应该如何从零开始打造一个在线教育APP&#xff1f;今天&#xff0c;小编将详细为大家讲解在线教育系统的源码与开发流程。 一、需求分析 对于在线教育APP&#xff0c;需要要明确以下几点&#xff1a; 1.目标用户&#xff1a;明确APP的用户群体&#xf…

类 和 对象(二)

构造方法 接上篇&#xff0c;若每次都想下面的setDate方法给对象初始化&#xff0c;未免比较麻烦&#xff0c;那有什么方法可以让初始化更加简便呢&#xff1f; public void setDate(int year, int month, int day){this.year year;this.month month;this.day day;}答&#…

2024.5.27 作业 xyt

定义自己的命名空间my_sapce&#xff0c;在my_sapce中定义string类型的变量s1&#xff0c;再定义一个函数完成对字符串的逆置 #include <iostream>using namespace std; namespace my_space {string s1"hello world";void my_strreverse(string str); } using…

C++笔试强训day34

目录 1.ISBN号码 2.kotori和迷宫 3.矩阵最长递增路径 1.ISBN号码 链接https://www.nowcoder.com/practice/95712f695f27434b9703394c98b78ee5?tpId290&tqId39864&ru/exam/oj 提取题意&#xff0c;模拟一下即可。 #include <iostream> using namespace std; …

《我的阿勒泰》读后感

暂没时间写&#xff0c;记录在此&#xff0c;防止忘记&#xff0c;后面补上!!! 【经典语录】 01、如果天气好的话&#xff0c;阳光广阔地照耀着世界&#xff0c;暖洋洋又懒洋洋。这样的阳光下&#xff0c;似乎脚下的每一株草都和我一样&#xff0c;也把身子完全舒展开了。 02、…