一、LR语法分析器模型 二、LR语法分析算法输入：一个输入串w和一个LR语法分析表 输出：如果w在L(G)中，输出w的自底向上的语法分析过程中的归约步骤；否则给出错误提示 方法：最初，语法分析器栈中的内容为初试状态S0，输入缓冲区的内容为w $。然后，执行语法分析程序。 分析实例 LR(0)的自动机 分析表 分析过程 三、LR分析算法的特点 定义LR文法：我们能为之构造出所有条目都唯一的LR分析表。 直观上说，只要存在这样一个从左到右扫描的移入-归约语法分析器，它总是能够在某文法的最右句型的句柄出现在栈顶时识别出这个句柄，那么这个文法就是LR的。 特点集合 栈中的文法符号总是形成一个可行前缀 分析表的转移函数本质上是识别可行前缀的DFA 栈顶的状态符号包含了确定句柄所需要的一切信息 是已知的最一般的无回溯的移进——归约方法 能分析的文法类是预测分析法能分析的文法类的真超集 能及时发现语法错误 手工构造分析表的工作量太大 四、LR分析方法和LL分析方法的比较LR文法 vs LL文法 LR(K)文法:向前看k个输入符号能够知道一个产生式的右部所能推导出的所有 ...

一、自底向上语法分析 一个自底向上语法分析过程对应于为一个输入串构造语法分析树的过程，它从叶子节点开始，逐步向上到达根节点。即把输入串归约成文法的开始符号。 二、规约 若一个子串和某个产生式的右部匹配，则用该产生式的左部符号代替这个子串。 归约可以看成是推导的逆过程 三、句柄 句型的句柄是和某产生式右部匹配的子串，并且，把它归约成该产生式左部的非终结符代表了最右推导过程的逆过程的一步。 该段文字中蓝色部分就是句柄 如果说文法存在二义性，那么句柄可能不一致 四、用栈实现移进——归约语法分析 移进——归约语法分析是自底向上语法分析的一种形式。 使用栈来保存文法符号，并用一个输入缓冲区来存放将要进行语法分析的其余符号。 移进——归约语法分析的四种动作： 移进：把下一个输入符号移进栈 归约：分析器知道句柄的右端已在栈顶，然后确定句柄的左端在栈中的位置，再决定用什么样的非终结符代替句柄 接受：分析器宣告分析成功 报错：分析器发现语法错误，调用错误恢复例程 下面是一个例子 五、id1 * id + id的归约语法分析 关于这个流程，大家可以仔细关注一下，通过这个流程，应该可 ...

定义对于一个文法G的每一个产生式A->a，进行如下处理： 对于FIRST(A)中的每一个终结符号m，将A->a添加到[A,m]。 如果e在FIRST(A)中，那么对于FOLLOW(A)中的每一个终结符b，将A->a添加到M[A,b]中，如果e在FIRST(a)中，且$在FOLLOW(A)中，也将A->a加入M[A,$]。 通俗一点来讲，就是建立一个通道，即是两个终结符之间通过什么可以完成可达性。 实例 特殊的一个文法的预测分析表有没有多重定义的条目，当且仅当该文法是LL(1)的 如果文法G是左递归或二义的，则M至少含一个多重定义的条目 案例 id + id * id $ 的推导过程 (初始情况) 已匹配 栈 输入 E $ id + id * id $ TE’ $ id + id * id $ FT’E’$ id + id * id $ idT’E’$ id + id * id $ id T’E’$ + id * id $ id E’$ + id * id $ id +TE’$ + id * id $ ...

LL文法的两个函数FIRST AND FOLLOW 花了很长时间，终于搞明白了LL文法的FIRST和FOLLOW相关的内容，希望对大家有所帮助 FIRST 对于FIRST(α)我们看产生式头可以推导得到的产生式体中的首个符号集合，即计算FIRST时非终结符号处于产生式的头部。 定义 FIRST（a）被定义为可以从a推导得到的串的首符号的集合，其中a是任意的文法符号串 FIRST（a）=｛a=>*b…,b是终结符｝ 如果a=>*e,e也属于FIRST（a） 计算方法 如果X是终结符，那么FIRST(X)=X 如果X->Y1Y2Y3…Yk，且a在FIRST(Yi)中，且Y1=>*e,Y2=>*e,…,Yi-1=>*e，那么a在FIRST(X)中 如果X->e，那么e在FIRST(X)中 例子 FOLLOW 计算FOLLOW时非终结符号位于产生式体中，查看当前产生式体中（或者叫句型的右边部分）非终结符号紧挨着的 终结符号 集合。 定义 FOLLOW（A）被定 ...

我的图床探索之旅：从踩坑到最优解前言搭建个人博客时，图床的选择让我走了不少弯路。经过几天的反复测试，我终于找到了一套稳定高效的解决方案。本文将详细介绍我的探索历程，希望能帮助到有同样需求的朋友。 一、云服务商方案体验1. 阿里云OSS使用体验： 上传速度：★★★★☆ 访问速度：★★★★★ 管理界面：★★★☆☆ 痛点： 备案流程繁琐，耗时3天才完成，一般人不太容易拿到域名的备案，需要域名费用＋对象存储费用+服务器费用，其中服务器费用太过巨大 费用计算复杂，一不小心就会超支 防盗链设置不够灵活 2. 腾讯云COS使用体验： 上传速度：★★★★★ 访问速度：★★★★☆ 管理界面：★★★★☆ 痛点： 与阿里云类似需要备案 API文档不够友好 3.cloudfare R2存储总结 这个听说很好用，但是有一个致命缺点，你需要有信用卡或者PayPal账号 虽然国内的银联卡理论上也可以注册，但是国内的卡没有安全码，注册PayPal也有一定困难 二、成品图床深度评测1. SM.MS优点： 开箱即用 国内访问速度快 支持API调用 致命缺陷： 免费版5GB空间很快用完 图片管理功 ...

自我介绍大家好，非常开心，能够在这里和大家见面。 我再次希望向大家介绍一下我的个人代码托管平台，GitHub和gitee。 如果大家感兴趣，可以前往看看，希望能够对于你有所帮助 GitHubGitee

多重背包问题问题描述多重背包问题是一个经典的动态规划问题。在这个问题中，我们有 N 件物品，每件物品都有一个体积、一个价值和一个数量上限。我们的目标是将这些物品放入一个容量为 V 的背包中，使得背包中的物品总价值最大。 动态规划思路我们使用动态规划来解决这个问题。定义 dp[i][j] 表示前 i 件物品恰好放入一个容量为 j 的背包可以获得的最大价值。 状态转移方程状态转移方程为： 1dp[i][j] = max(dp[i-1][j], dp[i-1][j-k * wi] + k * vi) 其中 0 <= k <= si，wi 是第 i 件物品的体积，vi 是第 i 件物品的价值，si 是第 i 件物品的数量上限。 原始代码实现以下是原始的多重背包问题的代码实现： 123456789N, V = map(int, input().split())dp = [[0] * (V + 1) for _ in range(N + 1)]for i in range(1, N + 1): # 体积，价值，数量 wi, vi, si = map(int, input() ...

回溯法求排列数123456789101112131415161718192021222324252627def dfs(depth): # depth: 当前深度 if depth == n: # 到达叶子节点，输出路径 print(path) return # 选择范围 for i in range(1, n+1): # 已经访问过的节点，跳过 if vis[i]: continue # 符合条件的节点，加入路径 vis[i] = True path.append(i) dfs(depth+1) # 回溯的时候，将当前节点从路径中移除 vis[i] = False path.pop(-1)n = int(input())vis = [False] * (n+1)path = []dfs(0) 回溯法求子集123456789101112131415161718n = ...

DFS剪枝简介DFS剪枝是一种启发式搜索算法，它通过对搜索树进行剪枝，来减少搜索树的大小，从而减少搜索时间。 DFS剪枝的基本思想是，在搜索树的每一步，都要判断是否可以直接跳过某些分支，从而减少搜索树的大小。 具体来说，DFS剪枝有以下几种方法： 剪枝准则：在搜索树的每一步，都要判断是否可以直接跳过某些分支，从而减少搜索树的大小。 启发式函数：启发式函数是指对节点的评估函数，它可以帮助搜索算法更好地选择下一步要探索的节点。 代价估计：代价估计是指估计节点的代价，并据此来判断是否应该继续探索该节点的子节点。 动态规划：动态规划是指利用搜索树的结构性质，对搜索树进行预处理，从而减少搜索树的大小。 启发式搜索：启发式搜索是指利用启发式函数对搜索树进行排序，从而减少搜索树的大小。 备忘录：备忘录是指在搜索树的每一步，都记录下已经探索过的节点，从而减少搜索树的大小。 并行搜索：并行搜索是指在多线程或多进程环境下，对搜索树进行搜索，从而减少搜索树的大小。 剪枝策略：剪枝策略是指对搜索树进行剪枝，从而减少搜索树的大小。 多目标搜索：多目标搜索是指在搜索树的每一步，都要同时考虑多个目标，从而减少搜索 ...