编译原理:语法分析

目录

  • 引言
  • 上下文无关文法 CFG: Context-Free Grammar
    • 定义
    • 推导方法
      • 最左推导和最右推导
    • 分析树
    • 分析树->抽象语法树
    • 常见的上下文无关文法
    • 文法设计
      • 二义性文法
      • 扩展巴科斯范式:EBNF extended Backus Normal Form
    • 文法和语言分类
    • 相关术语
      • 直接推导
      • +推导
      • *推导
      • 句型、句子、语言
      • 短语、简单短语、句柄
    • 正则文法
      • DFA->正则文法
      • 正则文法->DFA
      • DFA->正则表达式
      • 正则文法->正则表达式
      • 正则表达式->正则文法
  • 自顶向下分析方法(LL分析算法) top-down parsing
    • 回溯分析方法backtracking parser
    • 预测分析方法 predictive paeser
      • 递归下降分析 recursive-descent parsing
      • LL(1)分析法 ll(1) parsing (重点)
      • First集合,Follow集合 (重点)
  • 自底向上分析方法(LR分析算法)bottom-up parsing

引言

语法分析器的作用:token序列->分析树、抽象语法树

语法错误可能有:

  1. 关键字、标识符拼写错误,如intege
  2. 语法结构出错,少分号,begin/end不匹配
  3. 静态语义错误:类型不一致、参数不匹配,如需要传入double却传入了char
  4. 动态语义错误:无穷递归(这就是为什么有的编译器会报错whille(t){}里没有t–,即使你在块里写了它也找不到,因为它只看一开始有没有,很傻)、0作除数

处理目标:

  1. 正确报告错误以及地点(有一些明明是x行错误,却报y行错误)
  2. 迅速恢复(要么一直找,直到找到想要的记号,这样比较愚蠢;要么替换纠正,容易改不对,引发更多报错)
  3. 不影响源程序的分析速度

词法分析可以合并到文法当中

上下文无关文法 CFG: Context-Free Grammar

文法是对语言结构的定义和描述。即从形式上用于表述和规定语言的结构称为“文法”。如:“草吃羊”在文法上正确,但语义不正确。

定义

G=(T,N,P,S)
T 是终极符号集合,可以理解为token,一般用小写、黑体表示
N是非终结符号集合,一般用大写、小写斜体表示
P是产生式或文法规则A->a集合,其中A是非终结符,a是(TUN)*,如<句子>-><主语><宾语>
S是唯一的开始符号,是非终结符

另外,小写希腊字符表示文法符号串(可为空)

暂时没有自动生成上下文无关文法的工具,必须手动写

推导方法

给定文法G,从G的开始符号S开始推导,不断用相应规则的右部来替代规则的左部,每次仅用一条规则去推导,直到所有的非终结符都被终结符号替代为止。
依据上述过程,最终的串称为句子,所有句子的集合称为语言。定义如下: L ( G ) = { s ∣ S = > ∗ s } L(G)=\{s|S=>*s\} L(G)={sS=>s},其中,推出符号*表示经过0或多步推导出。

最左推导和最右推导

有若干语法成分同时存在时,总是从最左的语法成分进行推导,这称之为最左推导。(同理可以定义最右推导)
例:
文法:

exp->exp op exp|(exp)|**number**
op->+|-|\*

需要分析的字符串:(34-3)*42
推导过程:

exp=>exp op exp
=>exp op number
=>exp * number
=> (exp)*number
=>(exp op exp)*number
=>(exp op number)*number
=>(exp - number) * number
=>(number - number ) * number

上例是最右推导,最左推导如下:

(1) exp => exp op exp [exp -> exp op exp]
(2) => (exp) op exp [exp -> (exp)]
(3) => (exp op exp) op exp [exp -> exp op exp]
(4) => (number op exp) op exp [exp -> number]
(5) => (number - exp) op exp [ op -> - ]
(6) => (number - number) op exp [exp -> number]
(7) => (number - number) * exp [ op -> *]
(8) => (number - number) * number [exp -> number]

上下文无关文法举例:

  1. 文法G:E->(E)|a, 文法定义的语言是:L(G)={a,(a),((a)),…}={ ( n a ) n ∣ (^na)^n| (na)nn是>=0的整数}
  2. G:E->E+a|a,文法定义的语言是:L(G)={a,a+a,a+a+a,…}
  3. 正则式:a+,文法是G:A->Aa|a或者A->aA|a,语言是L(G)={ a n a^n an,n是>=1的整数}
  4. 正则式:a*,文法是G:A->Aa|ε或者A->aA|ε,语言是L(G)={ a n a^n an,n是>=0的整数}
  5. 文法G:E->(E) ,语言是L(G)={},没有终结符,没有句子,无限递归

分析树

以上例为例,
在这里插入图片描述
看序号可知是最左推导,与前序编号对应
下面是最右推导,与后序遍历对应
在这里插入图片描述

①父节点和子结点之间构成了一条文法规则
②叶节点都是终结符号,内部结点都是非终结符号

每个分析树只有唯一的一个最左推导和一个最右推导

分析树->抽象语法树

在这里插入图片描述
分析树复杂,但信息丰富,而抽象语法树简洁、抽象,用于语义分析

常见的上下文无关文法

  1. 算数表达式
exp->exp op exp|(exp)|**number**
op->+|-|\*
  1. if-else
    下面这个文法,有重叠的部分,比较低效
G: statement -> if-stmt | other
if-stmt -> if ( exp ) statement |if ( exp ) statement else statement
exp -> 0 | 1

下面这个文法是有歧义的文法

G: statement -> if-stmt | other
if-stmt -> if ( exp ) statement else-part
else-part -> else statement | ε
exp -> 0 | 1
  1. 括号匹配文法
G: A ->(A)A|ε
  1. 带分号的文法
    这个文法是错的,他的缺点是最后一个语句没有结束的分号
stmt-sequence -> stmt ; stmt-sequence | stmt
stmt -> s

下面这个文法可以,但是会推导出空语句:L(G’)= {ε, s;, s;s;, s;s;s;,…}

stmt-sequence -> stmt ; stmt-sequence | stmt | ε
stmt -> s

下面这个也是

stmt-sequence -> stmt-other1 stmt-other2
stmt-other1 -> stmt | ε
stmt-other2 -> ;stmt stmt-other2 | ;
stmt -> s

文法设计

二义性文法

可生成两个不同分析树的串的文法叫二义性文法。
34-3*42的分析树与语法树可以有两种。
算术表达式文法存在二义性的根源是什么?有2条规则都能往下推导,没有考虑优先级。

消除二义性的方法:
1.不修改文法,指定正确的分析树(只需手动修改生成的代码)LL分析表有冲突时选择其中一条
2.修改文法,会改得很乱

1.算术表达式修改文法,确定乘法优先级于加法;

exp -> exp addop exp | term
addop -> + | -
term -> term mulop term| factor
mulop -> *
factor -> (exp) | number

在此基础上,确定乘法和加法都是左结合的

exp -> exp addop term | term
addop -> + | -
term -> term mulop factor | factor
mulop -> *
factor -> (exp) | number

下面这个文法的缺陷是,输入者必须输入带括号的表达式

exp  factor op factor | factor
factor  (exp) | number
op  + || *

2.if-else,悬挂的else问题在这里插入代码片
最近嵌套规则用于解决悬挂else问题

statement  matched-stmt | unmatched-stmt
matched-stmt  if ( exp ) matched-stmt else matched-stmt | other
unmatched-stmt  if ( exp ) statement | if ( exp ) matched-stmt else unmatched-stmt
exp  0 | 1

下面的文法是强制if加上end

if-stmt -> if condition then statement-sequence end if |if condition then statement-sequence else statement-sequence end if

3.无关紧要的二义性文法:分号结尾的语句

stmt-sequence -> stmt-sequence ; stmt-sequence | stmt
stmt -> s

扩展巴科斯范式:EBNF extended Backus Normal Form

{}表示重复
在这里插入图片描述

用[]表示可选,比如:

G: statement  if-stmt | other
if-stmt  if ( exp ) statement [ else statement ]
exp  0 | 1

文法和语言分类

0型、1型、2型、3型(乔姆斯基层次)

-产生式左部范围右部范围左部右部备注
0型u->v(TUN)+(TUN)*>=1>=0可计算枚举语言,短语结构文法
1型xUy->xuy(TUN)+(TUN)*>=1>=0上下文相关文法
2型U->vN(TUN)*=1>=0上下文无关文法
3型U->t,U->WtNTUN=1<=2正则文法、线性文法

越往高级,限制越多,高级的语言符合低级

(左线性) P:U -> t 或 U -> Wt 其中 U、W∈N t∈T
(右线性) P:U -> t 或 U -> tW 其中 U、W∈N t∈T
在这里插入图片描述
这一分类的研究意义在于模型的可解释性,但是它的描述能力较弱

相关术语

直接推导

在这里插入图片描述

+推导

在这里插入图片描述
等于说是通过一步或多步推导出来的

*推导

在这里插入图片描述
通过0步或多步推导

句型、句子、语言

文法G = (T, N, P, S),S =>* a ,
如果a是(TUN)*,那么a是句型 (存在非终结符号。即分析树的剖面);
如果a是T*,那么a是句子(全部是终结符号,也就是叶子节点)(句子属于句型)
文法G产生的语言是L(G[S]) = {a | S =>* a ,a ∈ T* }

短语、简单短语、句柄

G = (T, N, P, S),w = xuy ∈ (TUN)* 为文法的句型
若:S => xUy ,且 U =>+ u,则u是句型w相对于U的短语(子树)
若:S => xUy, 且 U => u,则u是句型w相对于U 的简单短语;
U是非终结符,u是一步或多步的TUN,xy都是0步或多步的TUN
任一句型的最左简单短语称为该句型的句柄。

例子:
在这里插入图片描述
黄色是剖面(句型)
在这里插入图片描述
可以发现,这种话的说法就是“u是句型xx相对于U的短语”,其中句型是固定的,因为这是题里给的,u是黄色的结点,U是他们规约以后蓝色的结点
在这里插入图片描述
简单短语也就是一步可以得出的,最左的简单短语是句柄

正则文法

在这里插入图片描述

DFA->正则文法

在这里插入图片描述
例子:

在这里插入图片描述
普通的转移直接把吃进的字符和到达的状态连起来当右部,出发点当左部;可接收的状态再加一条可以推出epsilon

正则文法->DFA

在这里插入图片描述在这里插入图片描述
先按反过程画出来DFA,画完所有的以后加一个终态Z,把那些可以推出epsilon的状态都指向Z,把那些直接推出终结符的语句,也指向Z

DFA->正则表达式

在这里插入图片描述在这里插入图片描述
将词法分析的流程反向做一遍
在这里插入图片描述
r = ( a ∣ b ) ∗ ( a a ∣ b b ) ( a ∣ b ) ∗ r = (a|b)*(aa|bb)(a|b)* r=(ab)(aabb)(ab)

正则文法->正则表达式

在这里插入图片描述
递归即闭包
在这里插入图片描述

正则表达式->正则文法

上表反过来
在这里插入图片描述
在这里插入图片描述

自顶向下分析方法(LL分析算法) top-down parsing

从文法G的开始符号S开始推导得出句子t,遍历所有t,如果t==给定的句子s,那么s可以由G推导出来。

回溯分析方法backtracking parser

思想就是往下推导,如果不匹配就回溯,效率非常低,不聪明。没人用。
在这里插入图片描述

tokens[ ]; /* 词法分析得到的单词列表 */
int i = 0;
stack = [S]; /* 栈内放文法的开始符号 */
while ( stack != [] )if (stack[top] 是终结符号 t )if ( t == tokens[i] ) { i++; pop(); }else { backtrack( ) }else if (stack[top] 非终结符号 T )pop( ); push( 关于非终结符号T的下一条规则的右部 )

在这里插入图片描述
在这里插入图片描述
压栈的时候,是从右往左压,一旦栈顶是终结符就去匹配:不匹配就回溯,匹配就消掉

预测分析方法 predictive paeser

递归下降分析 recursive-descent parsing

LL(1)分析法 ll(1) parsing (重点)

First集合,Follow集合 (重点)

自底向上分析方法(LR分析算法)bottom-up parsing

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

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

相关文章

Kettle 数据抽取工具使用教程:从入门到实战

一、简介 Kettle 是 Pentaho Data Integration (PDI) 的一个组成部分&#xff0c;是一个开源的数据集成工具。它被广泛用于数据的抽取、转换和加载 (ETL) 过程。Kettle 提供了一个易于使用的图形界面&#xff0c;可以轻松设计和执行 ETL 流程。 github 源码地址&#xff1a;ht…

机器学习第四十三周周报 aGNN

文章目录 week43 aGNN摘要Abstract1. 题目2. Abstract3. 网络架构3.1 aGNN3.1.1 输入与输出模块3.1.2 嵌入层3.1.3编码器解码器模块&#xff1a;带有多头注意力层的GCN 3.2 可释性模型&#xff1a;SHAP 4. 文献解读4.1 Introduction4.2 创新点4.3 实验过程4.3.1 实验区域以及场…

Golang免杀-分离式加载器(传参)AES加密

目录 enc.go 生成: dec.go --执行dec.go...--上线 cs生成个c语言的shellcode. enc.go go run .\enc.go shellcode 生成: --key为公钥. --code为AES加密后的数据, ----此脚本每次运行key和code都会变化. package mainimport ("bytes""crypto/aes"&…

Linux - 复盘一次句柄数引发的故障

文章目录 Pre&#xff08;内核、用户、进程&#xff09;句柄数设置问题 shell修复 Pre Linux - 深入理解/proc虚拟文件系统&#xff1a;从基础到高级 &#xff08;内核、用户、进程&#xff09;句柄数设置 在Linux系统中&#xff0c;进程打开的最大句柄数可以通过多种方式配置…

立创·天空星开发板-GD32F407VE-Timer

本文以 立创天空星开发板-GD32F407VET6-青春版 作为学习的板子&#xff0c;记录学习笔记。 立创天空星开发板-GD32F407VE-Timer 定时器基本定时器示例 定时器 定时器是嵌入式系统中常用的一种外设&#xff0c;它可以产生一定的时间间隔、延时、定时等功能&#xff0c;广泛应用于…

如何自动生成数据库的样本数据(以MySQL和SQLynx为例)

目录 1 功能概述 2 主要特点 3 使用场景 4 使用示例 5 结论 SQLynx 是一款领先的 SQL 集成开发环境&#xff08;IDE&#xff09;&#xff0c;其强大的功能得到了全球用户的广泛认可。SQLynx 不仅在数据库管理和 SQL 查询方面表现出色&#xff0c;还提供了一项特别实用的功能…

VMware 三种网络模式

目录 一、网卡、路由器、交换机 二、虚拟网络编辑器 三、网络模式 1.桥接模式 通信方式 特点 配置 连通情况 使用场景 2.NAT模式 通信方式 特点 配置 连通情况 使用场景 3.仅主机 通信方式 特点 配置 连通情况 使用场景 一、网卡、路由器、交换机 网卡(Ne…

visio添加表格

插入Excel表格&#xff1a; 打开Microsoft Visio&#xff0c;新建一个空白画布。点击菜单栏中的“插入”。在插入中点击“图表”。在弹出的插入对象设置页面中选择“Microsoft Excel工作表”。点击确定按钮&#xff0c;然后在表格中输入内容。将鼠标点击到画布的空白处&#x…

OpenCV计算形状之间的相似度ShapeContextDistanceExtractor类的使用

操作系统&#xff1a;ubuntu22.04OpenCV版本&#xff1a;OpenCV4.9IDE:Visual Studio Code编程语言&#xff1a;C11 1.功能描述 ShapeContextDistanceExtractor是OpenCV库中的一个类&#xff0c;主要用于计算形状之间的相似度或距离。它是基于形状上下文&#xff08;Shape Co…

OpenStack云平台管理

OpenStack云平台管理 文章目录 OpenStack云平台管理资源列表基础环境一、部署Openstack二、创建网络和路由2.1、删除默认的网络2.2、创建网络和路由2.2.1、创建外部网络2.2.2、创建内部网络 2.3、创建路由 三、创建实例3.1、配置实例3.2、配置NAT转换 四、绑定浮动IP地址五、添…

C# WinForm —— 34 ToolStrip 工具栏 介绍

1. 简介 工具栏 ToolStrip&#xff0c;一般紧贴在菜单栏下面 2. 属性 属性解释(Name)控件ID&#xff0c;在代码里引用的时候会用到Enabled控件是否启用Dock定义要绑定到容器的控件边框&#xff0c;默认是topAnchor定义某个控件绑定到的容器的边缘。当控件锚定到某个边缘时&a…

分类模型:MATLAB判别分析

1. 判别分析简介 判别分析&#xff08;Discriminant Analysis&#xff09; 是一种统计方法&#xff0c;用于在已知分类的样本中构建分类器&#xff0c;并根据特征变量对未知类别的样本进行分类。常见的判别分析方法包括线性判别分析&#xff08;Linear Discriminant Analysis, …

韩顺平0基础学java——第22天

p441-459 异常exception 选中代码块&#xff0c;快捷键ctraltt6&#xff0c;即trt-catch 如果进行了异常处理&#xff0c;那么即使出现了异常&#xff0c;但是会继续执行 程序过程中发生的异常事件分为两大类&#xff1a; 异常体系图※ 常见的运行异常&#xff1a;类型转换…

EFuse概念解析

EFuse概念解析 EFUSE Key Parameter iNOM 代表的是&#xff0c;Efuse运行时候的电流 tNOM 代表的是&#xff0c;Efuse电流与时间的曲线 INOM通过VOC_Thrs设置 VOC_THRS VOC_THRS/Rsense Vsense采样小于VOC_THRS时候不动作 Vsense采样大于VOC_THRS时候根据Efuse_I2T曲线来…

平时的财经日历会影响黄金现货走势吗?

现货黄金的价格走势会受到诸多因素的影响&#xff0c;比如在财经日历上&#xff0c;美国的非农就业报告、GDP、利率公告、通胀数据等新闻和经济公告&#xff0c;都可能会对市场产生重大影响&#xff0c;尤其是当这些数据与市场预期不符的时候。所以比起单纯地进行技术分析和图表…

【C++ | 移动构造函数】一文了解C++11的 移动构造函数

&#x1f601;博客主页&#x1f601;&#xff1a;&#x1f680;https://blog.csdn.net/wkd_007&#x1f680; &#x1f911;博客内容&#x1f911;&#xff1a;&#x1f36d;嵌入式开发、Linux、C语言、C、数据结构、音视频&#x1f36d; ⏰发布时间⏰&#xff1a;2024-06-12 2…

Linux基础IO【II】真的很详细

目录 一.文件描述符 1.重新理解文件 1.推论 2.证明 2.理解文件描述符 1.文件描述符的分配规则 3.如何理解文件操作的本质&#xff1f; 4.输入重定向和输出重定向 1.原理 2.代码实现重定向 3.dup函数 ​编辑 4.命令行中实现重定向 二.关于缓冲区 1.现象 …

【学习笔记】Linux

Linux 1、 介绍 1.1、概述 1.2、特点 1.3、Linux的发行版2、 基础篇 —— 文件系统 2.1、文件系统 2.2、目录结构3、 基础篇 —— VI/VIM 编辑器 3.1、概述 3.2、编辑器模式及常用命令4、 基础篇 —— 网络配置 4.1、VMware NetWork …

电路笔记 : 嘉立创EDA 导入、查找、设计管理器(快速寻找网络标签)功能+DRC错误检查和处理

导入功能 查找功能 可查找多种类型&#xff0c;如原件名称、网络标签等 设计管理器 图层查看 DRC错误 规则设置 线距问题 大多数PCB制造商能够可靠地生产5 mil间距的走线和间隙。这是一个常见的标准&#xff0c;适合大多数消费级和工业级电子产品。在5 mil以上的间距&#xff…

Android APP memory统计方法

目录 进程的内存信息概述 关键的术语 测试步骤 测试步骤 数据处理 数据分析&#xff1a; 进程内存信息 Dumpsys meminfo -a PID Procrank Procmem PID 特殊内存信息 Mali ION(multi-media&#xff0c;gralloc) 进程地址空间信息 /proc/pid/smaps Showmap PID …