编译原理:语法分析
目录
- 引言
- 上下文无关文法 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序列->分析树、抽象语法树
语法错误可能有:
- 关键字、标识符拼写错误,如intege
- 语法结构出错,少分号,begin/end不匹配
- 静态语义错误:类型不一致、参数不匹配,如需要传入double却传入了char
- 动态语义错误:无穷递归(这就是为什么有的编译器会报错whille(t){}里没有t–,即使你在块里写了它也找不到,因为它只看一开始有没有,很傻)、0作除数
处理目标:
- 正确报告错误以及地点(有一些明明是x行错误,却报y行错误)
- 迅速恢复(要么一直找,直到找到想要的记号,这样比较愚蠢;要么替换纠正,容易改不对,引发更多报错)
- 不影响源程序的分析速度
词法分析可以合并到文法当中
上下文无关文法 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)={s∣S=>∗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]
上下文无关文法举例:
- 文法G:E->(E)|a, 文法定义的语言是:L(G)={a,(a),((a)),…}={ ( n a ) n ∣ (^na)^n| (na)n∣n是>=0的整数}
- G:E->E+a|a,文法定义的语言是:L(G)={a,a+a,a+a+a,…}
- 正则式:a+,文法是G:A->Aa|a或者A->aA|a,语言是L(G)={ a n a^n an,n是>=1的整数}
- 正则式:a*,文法是G:A->Aa|ε或者A->aA|ε,语言是L(G)={ a n a^n an,n是>=0的整数}
- 文法G:E->(E) ,语言是L(G)={},没有终结符,没有句子,无限递归
分析树
以上例为例,
看序号可知是最左推导,与前序编号对应
下面是最右推导,与后序遍历对应
①父节点和子结点之间构成了一条文法规则
②叶节点都是终结符号,内部结点都是非终结符号
每个分析树只有唯一的一个最左推导和一个最右推导
分析树->抽象语法树
分析树复杂,但信息丰富,而抽象语法树简洁、抽象,用于语义分析
常见的上下文无关文法
- 算数表达式
exp->exp op exp|(exp)|**number**
op->+|-|\*
- 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
- 括号匹配文法
G: A ->(A)A|ε
- 带分号的文法
这个文法是错的,他的缺点是最后一个语句没有结束的分号
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->v | N | (TUN)* | =1 | >=0 | 上下文无关文法 |
3型 | U->t,U->Wt | N | TUN | =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=(a∣b)∗(aa∣bb)(a∣b)∗
正则文法->正则表达式
递归即闭包
正则表达式->正则文法
上表反过来
自顶向下分析方法(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
相关文章:

编译原理:语法分析
目录 引言上下文无关文法 CFG: Context-Free Grammar定义推导方法最左推导和最右推导 分析树分析树->抽象语法树常见的上下文无关文法文法设计二义性文法扩展巴科斯范式:EBNF extended Backus Normal Form 文法和语言分类相关术语直接推导推导*推导句型、句子、语…...

React 中的 Lanes
React 中有一个 Lane 的概念,Lane 就像高速路上的不同车道,具有不同优先级,在 React Lane 通过一个 32 位的二进制数来表示。越小优先级别越高,SyncLane 级别最高。用二进制存储的方式,可以通过逻辑操作快速判断 Lane …...

【复旦邱锡鹏教授《神经网络与深度学习公开课》笔记】线性分类模型损失函数对比
本节均以二分类问题为例进行展开,统一定义类别标签 y ∈ { 1 , − 1 } y\in\{1,-1\} y∈{1,−1},则分类正确时 y f ( x ; w ) > 0 yf(x;w)>0 yf(x;w)>0,且值越大越正确;错误时 y f ( x ; w ) < 0 yf(x;w)<0 yf(x;…...

数组(C语言)(详细过程!!!)
目录 数组的概念 一维数组 sizeof计算数组元素个数 二维数组 C99中的变⻓数组 数组的概念 数组是⼀组相同类型元素的集合。 数组分为⼀维数组和多维数组,多维数组⼀般比较多见的是二维数组。 从这个概念中我们就可以发现2个有价值的信息:(1)数…...

视频生成模型 Dream Machine 开放试用;微软将停止 Copilot GPTs丨 RTE 开发者日报 Vol.224
开发者朋友们大家好: 这里是 「RTE 开发者日报」 ,每天和大家一起看新闻、聊八卦。我们的社区编辑团队会整理分享 RTE(Real-Time Engagement) 领域内「有话题的 新闻 」、「有态度的 观点 」、「有意思的 数据 」、「有思考的 文…...

Vue30-自定义指令:对象式
一、需求:创建fbind指定 要用js代码实现自动获取焦点的功能! 二、实现 2-1、步骤一:绑定元素 2-2、步骤二:input元素获取焦点 此时,页面初始化的时候,input元素并没有获取焦点,点击按钮&…...

2024/06/13--代码随想录算法(贪心)3/6|134.加油站、135.分发糖果、860.柠檬水找零、406.根据身高重建队列
134.加油站 力扣链接 class Solution:def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:curSum 0 # 当前累计的剩余油量totalSum 0 # 总剩余油量start 0 # 起始位置for i in range(len(gas)):curSum gas[i] - cost[i]totalSum gas[i] - co…...
机器学习的分类
机器学习分类 机器学习是人工智能的一个分支,它使计算机系统能够从数据中学习并做出决策或预测。机器学习(Machine Learning)是一种基于数据驱动的方法,旨在通过自动化的统计模型和算法从数据中学习和提取模式,以进…...

【Linux】进程控制3——进程程序替换
一,前言 创建子进程的目的之一就是为了代劳父进程执行父进程的部分代码,也就是说本质上来说父子进程都是执行的同一个代码段的数据,在子进程修改数据的时候进行写时拷贝修改数据段的部分数据。 但是还有一个目的——将子进程在运行时指向一个…...

PFC旁路二极管、继电器驱动电路以及PFC主功率
R001和R002以及R003三个电阻作用是限放X电容上的电 整流桥串联两个BJ1和BJ2 电容C3:给整流桥储能,给后续llc供电 PFC工作是正弦波上叠加高频电流 PFC功率部分 2个PFC电感(选择两个磁芯骨架小,有利于散热)、2个续流二极管&…...

CrossOver 2024软件下载-CrossOver 2024详细安装教程
Crossover软件是一款可以在Mac、Linux和Chromebook上运行Windows程序的软件。 它是一款商业软件,由CodeWeavers公司开发,Crossover不是一个虚拟机或模拟器,它使用Wine技术来将Windows程序直接转换成可以在其他操作系统上运行的程序࿰…...
Spark MLlib机器学习
前言 随着大数据时代的到来,数据处理和分析的需求急剧增加,传统的数据处理工具已经难以满足海量数据的分析需求。Apache Spark作为一种快速、通用的集群计算系统,迅速成为了大数据处理的首选工具。而在Spark中,MLlib(…...

React Native将 ipad 端软件设置为横屏显示后关闭 Modal 弹窗报错
问题: 将 ipad 端软件设置为横屏显示后,关闭 Modal 弹窗报错。 Modal was presented with 0x2 orientations mask but the application only supports 0x18.Add more interface orientations to your apps Info.plist to fix this.NOTE: This will cras…...

JavaEE大作业之班级通讯录系统(前端HTML+后端JavaEE实现)PS:也可选网络留言板、图书借阅系统、寝室管理系统
背景: 题目要求: 题目一:班级通讯录【我们选这个】 实现一个B/S结构的电子通讯录,其中的每条记录至少包含学号、姓名、性别、班级、手机号、QQ号、微信号,需要实现如下功能: (1)…...

代码随想录算法训练营第37天|● 56.合并区间● 738.单调递增的数字
合并区间 56. 合并区间 - 力扣(LeetCode) 按照左边界从小到大排序之后,如果 intervals[i][0] < intervals[i - 1][1] 即intervals[i]的左边界 < intervals[i - 1]的右边界,则一定有重叠。(本题相邻区间也算重贴…...
SQL Server中的CTE和临时表优化
在SQL Server中,优化查询性能是数据库管理的核心任务之一。使用公用表表达式(CTE)和临时表是两种重要的技术手段。本文将深入探讨CTE如何简化代码,以及临时表如何优化查询性能。通过实例和详尽解释,我们将展示这两种技…...
CCRC信息安全服务资质认证是什么
什么是CCRC认证? CCRC 全称 China Cybersecurity Review Technology and Certification Center。CCRC认证是指中国网络安全审查技术与认证中心进行的信息安全服务资质认证。简称信息安全服务资质认证。 CCRC,即中国网络安全审查技术与认证中心࿰…...

第五十一天 | 1143.最长公共子序列
题目:1143.最长公共子序列718.最长重复子数组的区别是,子序列不要求连续,子数组要求连续。这一差异体现在dp数组含义和递推公式中,本题是子序列,那就要考虑上nums1[i - 1] ! nums2[j - 1]的情况。 本道题与 1.dp数组…...
未来的5-10年,哪些行业可能会被AI代替?
在未来的5-10年,多个行业可能会受到AI技术的影响,其中一些工作可能会被AI所代替。以下是对可能被AI替代的行业及工作的一些概述: 客户服务与代表:随着AI技术的发展,特别是自动话术对话和语音生成技术的进步࿰…...

据报道,FTC 和 DOJ 对微软、OpenAI 和 Nvidia 展开反垄断调查
据《纽约时报》报道,联邦贸易委员会 (FTC) 和司法部 (DOJ) 同意分担调查微软、OpenAI 和 Nvidia 潜在反垄断违规行为的职责。 美国司法部将牵头对英伟达进行调查,而联邦贸易委员会将调查 OpenAI 与其最大投资者微软之间的交易。 喜好儿网 今年 1 月&a…...

python打卡day49
知识点回顾: 通道注意力模块复习空间注意力模块CBAM的定义 作业:尝试对今天的模型检查参数数目,并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...

全球首个30米分辨率湿地数据集(2000—2022)
数据简介 今天我们分享的数据是全球30米分辨率湿地数据集,包含8种湿地亚类,该数据以0.5X0.5的瓦片存储,我们整理了所有属于中国的瓦片名称与其对应省份,方便大家研究使用。 该数据集作为全球首个30米分辨率、覆盖2000–2022年时间…...

Kafka入门-生产者
生产者 生产者发送流程: 延迟时间为0ms时,也就意味着每当有数据就会直接发送 异步发送API 异步发送和同步发送的不同在于:异步发送不需要等待结果,同步发送必须等待结果才能进行下一步发送。 普通异步发送 首先导入所需的k…...

day36-多路IO复用
一、基本概念 (服务器多客户端模型) 定义:单线程或单进程同时监测若干个文件描述符是否可以执行IO操作的能力 作用:应用程序通常需要处理来自多条事件流中的事件,比如我现在用的电脑,需要同时处理键盘鼠标…...
Caliper 配置文件解析:fisco-bcos.json
config.yaml 文件 config.yaml 是 Caliper 的主配置文件,通常包含以下内容: test:name: fisco-bcos-test # 测试名称description: Performance test of FISCO-BCOS # 测试描述workers:type: local # 工作进程类型number: 5 # 工作进程数量monitor:type: - docker- pro…...

通过 Ansible 在 Windows 2022 上安装 IIS Web 服务器
拓扑结构 这是一个用于通过 Ansible 部署 IIS Web 服务器的实验室拓扑。 前提条件: 在被管理的节点上安装WinRm 准备一张自签名的证书 开放防火墙入站tcp 5985 5986端口 准备自签名证书 PS C:\Users\azureuser> $cert New-SelfSignedCertificate -DnsName &…...
libfmt: 现代C++的格式化工具库介绍与酷炫功能
libfmt: 现代C的格式化工具库介绍与酷炫功能 libfmt 是一个开源的C格式化库,提供了高效、安全的文本格式化功能,是C20中引入的std::format的基础实现。它比传统的printf和iostream更安全、更灵活、性能更好。 基本介绍 主要特点 类型安全:…...
Leetcode33( 搜索旋转排序数组)
题目表述 整数数组 nums 按升序排列,数组中的值 互不相同 。 在传递给函数之前,nums 在预先未知的某个下标 k(0 < k < nums.length)上进行了 旋转,使数组变为 [nums[k], nums[k1], …, nums[n-1], nums[0], nu…...

C++实现分布式网络通信框架RPC(2)——rpc发布端
有了上篇文章的项目的基本知识的了解,现在我们就开始构建项目。 目录 一、构建工程目录 二、本地服务发布成RPC服务 2.1理解RPC发布 2.2实现 三、Mprpc框架的基础类设计 3.1框架的初始化类 MprpcApplication 代码实现 3.2读取配置文件类 MprpcConfig 代码实现…...

Windows电脑能装鸿蒙吗_Windows电脑体验鸿蒙电脑操作系统教程
鸿蒙电脑版操作系统来了,很多小伙伴想体验鸿蒙电脑版操作系统,可惜,鸿蒙系统并不支持你正在使用的传统的电脑来安装。不过可以通过可以使用华为官方提供的虚拟机,来体验大家心心念念的鸿蒙系统啦!注意:虚拟…...