- 综合排序
- 最热优先
- 最新优先
- 来自专栏编译原理
编译原理 第二章上: 字母表和符号串 文法概述
空符号串：无任何符号的符号串，记为ε1.符号串的长度：|abc|=3 |abcc|=42.符号串的相等：依次相等（有序），符号串x和符号串y相等，记作x=y3.符号串的前缀和后缀前缀，从后删除。 7.符号串的幂运算：即把x重复写n次，记作z=x^n^8.集合的幂运算：跟符号串的幂运算相对比，注意，集合得排列，符号串不需要。 2.语法规则：通过建立一组规则(产生式）,来描述语言中句子的语法结构，规定用“::=”表示“由...组成”或"定义为..."3.由产生式推导句子推导方法：从一个要识别的符号开始推导，即用相应产生式的右部来替代产生式的左部 元符号｜,如：<数字>→0|1|2|3|4|5|6|7|8|9元符号< >,表示多个非终结符或多个字母组成的符号，如：<数字>元符号{ },表示可重复连接，{t}^m^~n~，表示符号串t可连接n-m次 ，而{t}表示符号串t可连接0到无穷次。
1.1K10编辑于 2024-09-19 - 来自专栏姓王者的博客
计算理论-形式语言
定义 符号串由字母表中的符号组成的序列 例如abc就是上述字母表V上的一个符号串，它的长度为3，例如ɑ=abc，那么用|ɑ|=3表示该符号串的长度。 Am+n 闭包v+与v* v0-由空符号串的集合。 v-由v中长度为1的符号串的集合。 v2-由v中长度为2的符号串的集合。 v+=v∪v2∪v3∪… v*=ɛ∪v∪v2∪v3∪… 语言 定义 设V是个字母表，L属于V* v={0,1} L1 = ∅ L2 = {0,00,000,……} L3 = {1,11,111,1111 3型文法：G中所有产生式的右部都是终极符串或非终极符串，且右部的非终极符串均不相同。
69210编辑于 2024-10-31 - 来自专栏机器学习炼丹之旅
编译原理：第二章 文法和语言
C语言是C程序的集合，C程序是在C基本字符集上定义的，按一定规则构成的符号串。 2.2 符号串 定义：由字母表中的符号所组成的任何有穷序列称为该字母表上的符号串。 2.2.2 字符串集合 定义：若集合A中的一切元素都是某字母表上的符号串，则称A为该字母表上的符号串的集合。 操作： 乘积： UV = {αβ|α∈U且β∈V} 方幂 ：V的n次方幂就是将n个V相乘 符号串集V的闭包 V^* =V^0∪ V^1 ∪ V^2 ∪ V^3 ∪… ，，即 V 上的所有符号串(包括空字 符号串集V的闭包 V^+ =V^1 ∪ V^2 ∪ V^3 ∪… ，，即 V 上的所有非空符号串(包括空字ε)的集合。 6.4.2 自下而上的句型分析 在归约的时候，同样也会遇到多种选择的情况，如果用（3）将 a 归约成 A，则会出错，必须用（2）进行归约。
2.8K10编辑于 2022-08-09 - 来自专栏理想二旬不止
【编译原理】第二讲：程序设计语言及其文法【笔记】
= {0，1}{0，1}{0，1} = {000，001，010，011，100，101，110，111} 通过举例看到字母表（数字）的3次方，最后的结果，就是一些长度为3的数字串的集合 结论：字母表的 n次幂：长度为n的符号串构成的集合 C：字母表 ∑ 的正闭包(positive closure) ∑+ = ∑ ∪ ∑2 ∪ ∑3 ∪ … 例：{a, b, c, d }+ = {a, b, c, d 如E(表达式)、T(项)、F(因子) C：文法符号 ① 字母表中排在后面的大写字母(如X、Y、Z) D：终结符号串 ① 字母表中排在后面的小写字母（u、v、…、z) （包括空串） E：文法符号串 (2) 句型和句子 一个开始符号 S 通过若干步，可以推导出 α，则称 α 是G的一个句型 α 是一个文法符号串 如果 α 中的每一个 都是终结符，经过若干部可以推导出一个终结符号串 w，称 w 是 无二义性的 6、乔姆斯基(Chomsky)把文法分为四种类型，即0型、1型、2型、3型。其中3型文法是( ) 正确答案（B） A. 非限制文法 B. 正则文法 C. 上下文有关文法 D.
2.1K40发布于 2020-04-22 - 来自专栏前端之旅
编译原理学习笔记-2：文法和语言
符号串的长度指的是符号串符号的个数，以 m = 000 为例，|m|= 3。 空符号串 ε 长度为 0，表示不包含任何符号，类似于编程中的空字符串 ""。所以有 εm = mε= m。 （3）P： P 即 production，指的是产生式集合。终结符和非终结符的转换依靠的就是产生式（或者说生成式，推导规则）。 （3）最左/最右推导： 推导的过程并不是唯一的。对于任何一步 α ⇒ β，如果都是对 α 中的最左非终结符进行替换，那么就说最左推导，反之就是最右推导。 3. 语法分析树与文法的二义性 我们可以借助语法分析树（这里的语法分析树是具体语法树，即 parse tree，不是抽象语法树）这个结构来描述句型的推导。 （4） 3 型文法 在 3 型文法的基础上加以限制，规定对于每一个 α→β，要么必须满足 A→ α | αB（右线性），要么必须满足 A→ α | Bα（左线性）。这里的 AB 代表非终极符号。
2.6K21发布于 2020-03-23 - 来自专栏Triciaの小世界
编译原理学习（到LL1文法部分）
语法分析 3. 语义分析和中间代码生成 4. 优化 5. 目标代码生成 6. 表格管理和错误处理 1. 标识符 sum ，first，count … 3. 运算符 *,+,- … 4. 分界符 （，{，[, ]，}，）… 5. 数值型常量 10,3，… 2. 如：10 “->”意思是“定义为” 语法单位的单词符号：=，+，* ，X1,Y,Z,10 语法单位表达式 赋值语句： X1（标识符）= Y + 10*Z; 语法单位内部表示：语法树 3. + E|E * E|( E )|i 文法G所描述的语言：含有+、*和 括号 的算术表达式 文法： 0型文法：图灵文法、短语文法 1型文法：上下文有关文法、长度增加文法 2型文法：上下文无关文法 3型文法 有限方向图） 结点 —— 状态，用○表示；终态，用◎表示 有向弧 ── 箭头 弧上标记 ── 输入字符 利用状态转换图识别单词： 从初态出发； 读入一字符； 按当前字符转入下一状态； 重复 2,3
1.4K20编辑于 2023-04-12 - 来自专栏前端之旅
编译原理学习笔记-5：自顶向下语法分析
|Pαm|β1|β2|β3|βn（右部的一部分含左部，一部分不含），则将其改写为：P → |β1P'|β2P'|...|βnP' 和 P’ → α1P'|α2P‘|... 2.3 空符号串 我们已经消除了左递归和回溯，这样文法是不是就真的确定了呢？其实不是，因为我们还得考虑空符号串的问题。 ② 空符号串的处理 有没有注意到 Follow 集的定义刚好与我们谈到的空符号串的处理有相关的地方？ 3. 假设给定如下文法和输入符号串： // 文法 E → E + T|T T → T * F|F F → i|(E) // 输入符号串 i + i * i 符号串是否符合给定文法呢？
5.7K82发布于 2020-05-12 - 来自专栏地鼠窝里有个Gopher
位运算总结
汉明距离 3. Brian Kernighan 算法 4. lowbit操作 一、位运算基本概念 1. 汉明重量 汉明重量是一串符号中非零符号的个数。因此它等同于同样长度的全零符号串的汉明距离。 在最为常见的数据位符号串中，它是1的个数。 2. 3. Brian Kernighan 算法 用于去掉二进制数字的最后面的一位1，也常用于计算汉明权重。 算法：x & (x - 1)。
66810编辑于 2022-10-30 - 来自专栏U3D技术分享
形式语言与自动机
正则语言 NFA 导论 自动机理论历史 主要学习内容：有穷自动机、下推自动机、图灵机 有穷自动机 ： 1、具有有限内存的设备可以做什么 以及不能做什么 2、引入仿真：一台设备“模仿”另一台设备的 能力 3、 3、语法是枚举语言中所有句子的装置 4、如果一个句子属于该语言，则一定可以枚举出来 5、如果枚举出一个句子，则一定属于该语言 课程大纲 有穷自动机和正则语言 有穷自动机 Deterministic finite 语言到DFA，举例构造{0,1}上DFA接受所有已101结尾的符号串 解法1：构建所有状态，选取指定的状态作为终态 ---- 有穷自动机引论 什么·是FA？ ∑ , δ, q0, F }，包含： 1、状态：A finite set of states (Q, typically) 2、字母表：An input alphabet(Σ, typically) 3、 （此时，Final等同于Accept） 图示例： 转移表： DFA的语言：1、有种类的自动机都定义了语言 2、如果A是自动机，则L(A)是它的语言 3、对于DFA A，L(A)是从起始状态到终结状态的路径上标记符号串的集合
91520编辑于 2022-09-21 - 来自专栏codechild
文法和语言
={0，1}{0，1}{0，1}={000，001，010，011，100，101，110，111} 字母表中的n次幂：长度为n的符号串构成的集合 字母表的正闭包——U表示的并集 (∑)+=∑U(∑)2U 字母表的正闭包：长度正数的符号串构成的集合 字母表的克林闭包 (∑)∗=(∑)0U(∑)U(∑)2U(∑)3.... 字母表的克林闭包：任意符号串（长度可以为0）构成的集合。 串 设∑\sum∑是一个字母表，对于任意的x属于(∑)∗(\sum)^*(∑)∗,x称为是∑\sum∑上的一个串。 产生式的简写 对于一组由相同左部的α产生式：α->β1，α->β2，α->β3…… 可以简写为：α->β1|β2|β3…… 读作：α定义为β1，或者β2，或者β3…… β1,β2,β3……称为α的候选式 A就是非终结符 3型文法 w是终结符号串，A，B都是非终结符 四种文法的关系 上下文无关文法(CFG)分析树 短语 给定一个句型，其分析树中的每一棵子树的边缘称为该句型的一个短语。
64630编辑于 2023-05-30 - 来自专栏编译原理
编译原理 第二章下: 推导，规约，句型句子，语言，文法分类，二义性
2.3.1 直接推导/直接规约简言之，一步直接退换例如：有文法GS:S→0S1,S→01有直接推导 0S1⇒0011有直接推导 0S1⇒00S11有直接推导S⇒0S12.3.2 推导/规约若存在直接推导序列，符号串一直进行直接推导 ，直到没有非终结符号时，推导就必须终止推导例题：2.3.3 规范推导规范推导也叫最右推导，每步只变换符号串中最右边的非终结符，直到推导结束2.4 句型和句子1.句型 有文法GZ，若Z 0步以上推导出x， ==：3型语言或正则语言3型文法是程序设计语言构词规则2.6.1 0型文法对产生式基本无限制2.6.2 1型文法文法左部符号个数不超过右部符号个数2.6.3 2型文法任意产生式A→B，A属于非终结符号， 1.画出句型语法树2.找出所有子树3.子树叶子结点组成的符号串为该句型针对子树根节点的短语4.去掉重复的短语找短语的关键还是找子树简单短语与句柄所有短语中，一步推导得来的即为简单短语。 人为避免产生二义性2.9.1 有关文法的实用限制多余规则：指文法中任何句子的推导都不会用到的规则，若有则删去- 不可到达：非终结符不再任何规则的右部出现，称该非终结符为不可到达- 不可终止：由它不能退出终结符号串
1.2K10编辑于 2024-09-20 - 来自专栏图灵技术域
编译原理自动生成LR(0)分析表Python实现
（3）使用闭包函数（CLOSURE）和转向函数(GO(I,X))构造文法G’的LR(0)的项目集规范族，再由转换函数建立状态之间的连接关系来得到识别活前缀的DFA。 符号串的前缀是指该符号串的任意首部，包括空串ε。例如，对于符号串abc，其前缀有ε，a，ab，abc。如果输入串没有错误的话，一个规范句型的活前缀是该句型的一个前缀，但它不含句柄之后的任何符号。 （3）活前缀不含有句柄的任何符号，此时期望A→β的右部所推出的符号串。 在文法G的每个产生式的右部（候选式）的任何位置上添加一个圆点，所构成的每个产生式称为LR（0）项目。 （3）A→.β 刻划没有句柄的任何符号在栈顶，此时期望A→β的右部所推出的符号串。 （4）对于A→ε的LR(0)项目只有A→．。 （3）移进项目： 表现形式：A→a.（bVT） 这类LR(0)项目表示分析栈中是不完全包含句柄的活前缀，为构成恰好有句柄的活前级，需将b移进分析栈。
2.3K33发布于 2021-05-21 - 来自专栏前端之旅
编译原理学习笔记-3：词法分析(一)基本过程、正规式和有限自动机
我们可以先走几条路线看看（假定在遇到状态 3 就停止），不难发现它可以识别出诸如 aa，bb，abb，baa 这样的符号串。 由于 aa 和 bb 都可以独立存在，说明 (aa|bb)的前面和后面必须可以是空符号串，说到空符号串，我们会想到闭包，所以它的前面后面必定会分别出现一个闭包。 组合符号串，都能够被识别并循环转换到状态 3，这里说明后面的状态是任意的，所以确定后面是 (a|b)*。 （因为输入符号来自于集合闭包，所以输入符号接受空符号串 ε） 看下面的例子： 假设有非确定有限自动机 NFA M＝({0,1,2,3,4},{a,b},δ,{0},{2,4})，其中， δ(0,a)={ 这样的集合，因为 A 自由组合形成的符号串是可以用一个 A 的自循环来表示的，所以中间有一个自循环，而 ε 则可以用 εε 来表示，所以考虑在前后各加一个 ε，对于 A 的符号串不影响。
12.8K52发布于 2020-04-13 - 来自专栏机器学习炼丹之旅
编译原理：第三章 词法分析
一、 词法分析程序的设计（理解） 1.1 词法分析主要功能 从左至右逐个字符地对源程序进行扫描，产生 一个个的单词符号，把作为字符串的源程序改造成为单词符号串的中间程序或者说：逐个读入源程序字符，并按照词法规则分割成一系列单词 image-20210917104940523.png 二、 单词的描述工具（理解） 正规集(正规语言)：某字母表上，我们感兴趣的符号串的集合。 δ（0，b）=2 δ（1，a）=3 δ（1，b）=2 δ（2，a）=1 δ（2，b）=3 δ（3，a）=3 δ（3，b）=3 3.3.3 NFA确定为DFA的原因 使用NFA判定某个输入符号串的时候，可能出现不确定的情况：不知道下面选择哪个状态。如果选择不好，该输入符号串可能不能到达终止状态。 但是，我们不能说该输入符号串不能被该NFA接受。如果通过尝试的方法，不断试探来确定输入符号串是否可被接受，那么判定的效率将降低。解决的方法是将NFA转换为等价的DFA。
5.6K11编辑于 2022-08-09 - 来自专栏机器学习炼丹之旅
编译原理：第一章 编译原理引论
image-20210903112514512.png 2.1.2 语法分析 输入单词符号串 根据语言的语法规则对单词符号串进行扫描和分解 识别出各类语法单位 语法单位内部表示：语法树 image } 翻译成如下的四元式序列（中间代码）： (操作符,左操作数,右操作数,存储位置) (1) (inttofloat, 10, _， T1 ) (2) ( *, count，T1，T2 ) (3) ( +, first，T2，T3 ) (4) ( =, T3, _, sum) 其中，Ti为语义分析程序为存放中间结果而生成的临时变量。
2.5K10编辑于 2022-08-09 - 来自专栏编译原理
编译原理 第四章&第五章:语法分析 LR(0)分析器 SLR(1)分析器
练习:给定LR分析表和文法,分析((a))方法步骤:初始化,状态栈为0,符号栈为#,输入符号串为(题目待分析字符串,以#结束)紧盯状态栈和输入符号串栈顶,通过状态栈和符号串栈顶来查表一般来说查表结果有三个 S或R或ACC,当查表是S什么时,需要进行移进操作,将输入符号串栈顶元素放入符号栈中,将S的下标数字压入状态栈,再进行下一步.若是R,就是规约操作,规约操作需要我们填写goto这一项,根据R下标的值,看对应的文法
2.3K20编辑于 2024-09-25 - 来自专栏全栈程序员必看
编译原理之文法
VT∩VN=∅ 产生式，其形式为α→β，α称为产生式的左部，β称为产生式的右部，符号“→”表示“定义为”，并且α、β∈(VT∪VN) *，α≠ε，即α、β是由终结符和非终结符组成的符号串。 解释： (VT∪VN) *：也就是VT∪VN的Kleene闭包 α≠ε：α不等于空符号串 用小写字母代表终结符，如：abc……，不能被拆分 用大写字母代表非终结符，如：ASBX……，可以被拆分 著名语言学家NoamChomsky(乔姆斯基)根据对产生式所施加的限制的不同，把文法分成四种类型，即0型、1型、2型和3型。 ：如有：A→a,A→aB,B→a,B→cB，则符合3型文法的要求。 但如果推导为：A→ab,A→aB,B→a,B→cB或推导为：A→a,A→Ba,B→a,B→cB则不符合3型方法的要求了。
2.5K20编辑于 2022-08-09 - 来自专栏全栈程序员必看
样品GA的良好理解
例：求下述二元函数的最大值： (1) 个体编码 遗传算法的运算对象是表示个体的符号串，所以必须把变量 x1, x2 编码为一种 符号串。 本题中。 所以分别用3位无符号二进制整数来表示。将它 们连接在一起所组成的6位无符号二进制数就形成了个体的基因型。表示一个可 行解。 如：011101，101011，011100，111001 (3) 适应度汁算 遗传算法中以个体适应度的大小来评定各个个体的优劣程度，从而决定其遗传 机会的大小。
60910编辑于 2022-07-14 - 来自专栏全栈程序员必看
很好的理解遗传算法的样例
例：求下述二元函数的最大值： (1) 个体编码 遗传算法的运算对象是表示个体的符号串，所以必须把变量 x1, x2 编码为一种 符号串。 因 x1, x2 为 0 ~ 7之间的整数，所以分别用3位无符号二进制整数来表示，将它 们连接在一起所组成的6位无符号二进制数就形成了个体的基因型，表示一个可 行解。 如：011101，101011，011100，111001 (3) 适应度汁算 遗传算法中以个体适应度的大小来评定各个个体的优劣程度，从而决定其遗传 机会的大小。
50420编辑于 2021-12-09 - 来自专栏数据结构与算法
24:单词的长度
没有被空格间开的符号串，都算作单词。 输入一行单词序列，最少1个单词，最多300个单词，单词之间用至少1个空格间隔。单词序列总长度不超过1000。输出依次输出对应单词的长度，之间以逗号间隔。 样例输出 3,3,4,2,10,3,4,7,5 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath
2.4K50发布于 2018-04-03
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号