文章作者: Musuyin
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 木素音的小站！
相关推荐
2026-04-13
LR分析
LR 分析概述什么是 LR 分析LR 分析（LR Parsing）是一种强大的自底向上语法分析方法。 LR 的含义： L（Left-to-right）：从左到右扫描输入 R（Rightmost derivation in reverse）：构造最右推导的逆序（规范归约） (k)：向前看 $k$ 个输入符号（通常 $k=0$ 或 $k=1$） LR 分析是最右推导的逆过程，也就是规范归约。 LR 分析的基本思想自底向上分析从输入串（叶节点）出发，逐步归约（Reduce）到文法的开始符号（根节点）。 核心问题： 何时归约？（识别句柄） 用哪个产生式归约？ 句柄（Handle）句柄是句型中最左边的直接短语，也就是下一步应该归约的部分。 回顾：如果有推导 $S\Rightarrow^\alpha A\delta\Rightarrow\alpha\beta\delta$，其中 $A\rightarrow\beta$，则 $\beta$ 是句型 $\alpha\beta\delta$ 相对于产生式 $A\rightarrow\beta$ 的*句柄。 移进-归约...
2026-03-04
文法和语言
符号和符号串 符号：可以相互区别的记号（元素） 字母表（$\Sigma$）：符号（元素）的非空有穷集合 符号串：由字母表中的符号组成的任何有穷序列 空符号串 $\varepsilon$ 是字母表 $\Sigma$ 上的符号串 若 $x$ 是 $\Sigma$ 上的符号串，$a$ 是 $\Sigma$ 的元素，则 $xa$ 是 $\Sigma$ 上的符号串 $y$ 是 $\Sigma$ 上的符号串，当且仅当它可以由上面两个表述导出 如 $\Sigma={a,b}$ 则：$\varepsilon,a,b,aa,ab,aabba,…$ 都是 $\Sigma$ 上的符号串 前缀（头）：移去符号串尾部的大于等于零个符号 $s$ 和 $\varepsilon$ 也是前缀 真前缀（固有头）：所有前缀的集合去除 $s$ 后缀（尾）：移去符号串头部的大于等于零个符号 $s$ 和 $\varepsilon$ 也是后缀 真后缀（固有尾）：所有后缀的集合去除 $s$ 子串：移去一个头和一个尾 $s$ 和 $\varepsilon$ 也是子串 符号串的长度符号串 $s$ 的...
2026-03-04
编译原理概述
编译程序一个编译程序就是一个语言翻译程序，把一种语言（源语言）书写的程序翻译成另一种语言（目标语言） ![[images/截屏2026-03-29 10.51.27.png]] 预处理程序一个源程序可能分为多个模块存放在不同文件中，通过预处理程序将所有源程序进行汇集 编译类型 一趟编译 多趟编译 具有调试和优化功能的编译 编译过程 词法分析 语法分析 语义分析 中间代码生成 代码优化 目标代码生成 ![[images/截屏2026-03-29 10.54.47.png]] 词法分析从左到右一个字符一个字符地读入源程序，并进行扫描和分解，识别出单词（或称为符号） 类别： 标识符 保留字 算符 界符 语法分析在词法分析的基础上将单词序列分解为各类语法短语，可以表示成语法树 ![[images/截屏2026-03-29 10.57.51.png]] 语法分析依据语言的语法规则，确定输入串是否构成一个在语法上正确的程序 程序的结构通常由递归规则表示 任何标识符是表达式 任何常数是表达式 若表达式 A 和表达式 B 都是表达式，则以下都是表达式： 4...
2026-04-01
自顶向下语法分析方法
语法分析概述语法分析（Syntax Analysis 或 Parsing）是编译器的第二个阶段，它接收词法分析器产生的单词符号序列，检查这些单词符号的组合是否符合语言的语法规则（由文法定义），并构造出语法树（或抽象语法树）。 语法分析的任务 检查语法正确性：判断输入的程序是否符合语言的语法规则 构造语法树：为正确的程序构造语法树（推导树或抽象语法树） 报告语法错误：对于错误的输入，指出错误位置和可能的原因 语法分析的分类根据构造语法树的方向，语法分析分为两大类： 1. 自顶向下分析（Top-Down Parsing） 方向：从文法的开始符号 $S$ 出发，推导输入串 推导方式：最左推导 构造语法树：从根节点开始，逐步向下扩展叶节点 代表方法： 递归下降分析（Recursive Descent Parsing） LL(k) 分析（LL：Left-to-right, Leftmost derivation） 思想：尝试为输入串构造一个最左推导序列。 2. 自底向上分析（Bottom-Up Parsing） 方向：从输入串出发，归约到开始符号 $S$ 推导方式：最右推导的逆过程...
2026-03-18
词法分析
词法分析程序设计词法分析程序和语法分析程序的接口方式词法分析程序完成的是编译第一阶段的工作，可以有以下方法： 独立的一遍，把字符流的源程序变成单词序列，输出到一个中间文件，这个文件作为语法分析程序的输入而继续编译过程 词法分析程序每得到一次调用，就从源程序文件中读入一些字符，直到识别出一个单词，或者直到下一个单词的第一个字符为止。可以节省中间文件或存储区 ![[images/截屏2026-04-08 10.08.57.png]] 词法分析程序输出当语法分析程序接收到下一个单词的请求时，另词法分析程序从左到右读入源程序的字符流，以识别下一个单词。 在识别出下一个单词同时验证其词法正确性之后，词法分析程序将结果以单词符号的形式发送至语法分析程序以回应其请求；若发现词法错误则返回出错信息 单词分类 关键字/保留字 标识符 常数 运算符 界符 表达式使用二元式表示： $$(\text{单词种类},\text{单词值})$$ 对于部分单词，除了需要值，还需要其他信息。如对标识符，还需要记录类别、层次以及其他属性，可以将这些属性全部收集在符号表中，设计成： $$(\...
公告
即使迷茫，也要前进！