分析-综合模型 源程序计算其基本属性，生成源程序的中间表示——是什么？ 源程序的中间表示转换为目标代码。 汇编语言——计算机里运行 1、 什么是计算、在哪里计算 2、 CPU/内存、物理设备如何配合完成计算 3、 汇编语言在计算过程中扮演什么角色？ CPU的部件执行机器指令，即CPU执行计算 就是将这串二进制数字在物理上转换成高低电平驱动计算机运行 一串相同的十六进制数字 —— 递增的数字，表示某种编号信息—— 一起表示内存编号 十六进制数字—— 机器指令（ 英语单词 十六进制数字）——汇编指令，机器指令与汇编指令相互对应 都是十六进制 机器指令，又称作机器语言是一套计算过程的表示系统 用汇编指令表示机器指令 MOV AX,005 翻译器——编译器 汇编语言 1、 汇编指令 汇编指令（这套系统）可以通过编译器表示成机器指令（这套系统）（机器码）、 2、 伪指令 告诉编译器（翻译软件）这里怎么翻译 3、 其他符号 +-*/ 同样有编译器处理 内存 内存储器 内存条——主内存 绝大多数的指令和数据放在主内存中 内存编号为什么从-0开始？ 统一穿16进制数字，产生了2种解释 机器指令和数据。只有被读到CPU里，CPU才会去区分指令和数据。不然在内存只是数据。 CPU 如何读到？如何去区分？ 内存的最小单位是一个字节。 ## 编译器概述 ### 程序设计语言 计算机不能直接执行汇编指令，需要通过一个语言翻译其将其翻译成机器指令。 将汇编语言程序翻译为机器语言程序的语言翻译器成为汇编器。 如果源语言是高级语言，目标语言是低级语言，那么这个语言翻译器就成为编译器。 编译是实现高级语言的一种方式，包括了编译器和汇编器，即编译器将源程序翻译为目标代码模块，通过链接、加载，使之成为内存中可执行的目标程序。下一程序运行时不需要再次编译，只需要调用目标代码即可。 高级语言的另一种实现方式是解释，程序运行时，解释器接收用户的输入，直接执行源程序中的指定操作，一遍遍翻译一遍执行，解释器不能生成可重复执行的目标代码模块。 而Java语言比较特殊，它采用了编译和解释相结合的混合翻译方式，以支持跨平台性。首先Java源程序被编译（翻译器）为一个称为字节码的中间表示形式，然后由虚拟机来对字节码做解释执行。因此只要有虚拟机，就可以运行字节码。 ### 词法分析 **完成从字符序列到单词符号序列的转换** 键盘敲入的字符流本身没有意义，要想有意义必须转换为单词符号序列 词法分析首先读入字符流行式的源程序，然后（从左至右）扫描、切分源程序字符流，从中识别出单词（又称为记号token）。空格、回车、注释等首先被略去以获得有效成分。 有效成分识别单词的依据是源语言的构词规则，但此刻已是标识符、保留字、运算符、分界符、常数。 经过词法分析之后，源程序字符流转化为一个单词的序列，生产了符号表。 如 ![](https://chenalna.oss-cn-hangzhou.aliyuncs.com/img/image-20251218124853015.png) p: 标识符 =： 赋值运算符 60： 常数 ### 语法分析 单词符号序列->分析树 根据源语言的语法规则，判断源程序在语法上是否合法。如果合法则对源程序单词序列进行层次分析，并输出分析树或者语法树反映源程序的语法结构，通常采用Backus-Naur Form BNF作为语法规则的表示方式 <赋值语句>::=<标识符> 分析树反映了赋值语句的层次结构和运算顺序，即变量r和常数60首先做乘运算 position"=initial+rate*60 image-20251218124812618 语法树同样反映了赋值语句的层次结构和运算顺序，但是结点数更少（省略了赋值语句等称呼） ![image-20251218130400675](https://chenalna.oss-cn-hangzhou.aliyuncs.com/img/image-20251218130400675.png) ### 语义分析 分析树->带注释的树 语义分析使用语法树和符号表中的信息来检查源程序在语义上是否合法。这个阶段要同时分析源程序的说明部分来收集源程序中定义的标识符（变量）等类型的信息，并把这些信息存放到符号表中。 这个阶段的重要任务是类型检查。 ### 中间代码生成 带注释的树——>中间代码（中间表示） 编译器会将源程序转化为一个低级或者类机器语言的中间表示。 这个中间表示一般与平台无关（递推，递归，迭代），并且易于生成和易于翻译成目标代码。 三地址代码就是一种常见的中间代码。 ![image-20251218131232724](https://chenalna.oss-cn-hangzhou.aliyuncs.com/img/image-20251218131232724.png) ### 代码优化 代码优化氛围针对中间代码优化和针对目标代码优化，运行更快、所需的运运行空间内存更小，其中对中间代码优化由于器平台无关性，更具有普遍意义 ### 目标代码生成 中间代码->机器指令/汇编代码 将优化之后的中间代码映射为目标代码。包括绝对机器指令、可重定位的机器指令、汇编语言代码等。目标代码生成需要为源程序中 ### **符号表管理** 词法分析中，创建了符号表 功能：管理分析过程中得到的源程序中的标识符的各种信息 记录源程序中使用的标识符（identifier） 每个标识符的各种属性（attribute）.类型（type)/作用域（scope）、存储分配（storage allocated）信息 ### 出错处理 功能： 检查错误的位置 检查错误的性质（语法、词法、语义） 错误恢复 ### 编译器构造方法 每个过程都有可能出错，每个过程都要用到符号表 前端 只依赖于源程序，独立于目标机器 生成中间代码 后端 依赖于目标机器，与源程序无关，至于中间语言有关 从中间代码生产目标代码 编译器也需要编译代码后运行的 增加重用性 ### 遍 在实现编译器的时候，读入源程序的源代码，由语法分析器来读； 里面调用的是词法分析程序。 •遍是对源程序或源程序的中间结果从头到尾扫描一次，并作有关的加工处理，生成新的中间结果或目标程序。 •编译程序可以通过一遍或者多遍来组织 •根据源语言特征、系统资源的状况、运行目标的要求。 开发高级语言的编译器—— 自展技术 2. 用已有高级语言实现其它高级语言的编译程序： 用语言L的编译器编译用L书写的另一高级语言的编译器 例如，用C写PASCAL语言的编译器，然后编译 词法分析器的自动生成程序Lex •语法分析器自动生成程序 — YACC •构造编译程序的工具称为编译程序-编译程序、编译程序产生器或翻译程序书写系统 •扫描器生成器: 产生词法分析器，如lex/flex •语法分析器生成器: 自动产生语法分析器，如yacc/bison •语法制导翻译引擎: 生成一组用于遍历分析树并生成中间代码的程序集 •其他更多工具 ![image-20251218135850978](https://chenalna.oss-cn-hangzhou.aliyuncs.com/img/image-20251218135850978.png) 我们编译原理的编译器其实包含了编译器和汇编器，将源程序转换为绝对机器代码 狭义的汇编仅限生成汇编代码的阶段 ## 形式文法和形式语言 ### 文法和语言的形式定义 字母表和符号串 字母表是符号的非空有穷集合，记为$\Sigma$. 符号是一个抽象实体，表示可以互相区分的记号或者元素。 字母表中至少包含一个元素，字母表中的元素，可以是字母、数字或者其它符号。 •符号串: 字母表上的符号的有穷序列,也称为句子 空符号串ε不包含任何符号的符号串，是任何Σ上的符号串 连接(Concatenation): 符号串α、β的连接，是把β的符号写在α的符号之后得到的符号串αβ 如 α= ab, β= cd 则αβ = abcd，βα=cdab 注：εα = αε = α 幂(Power):符号串α自身连接n次得到的符号串α α…αα(n个α)表示为αn α0=ε， α1=α， α2=αα，……， αn= αα...α 符号串的长度表示符号串中包含符号的个数 w = a1a2...an，|w| = n，|ε| = 0 子串(substring): 符号串中的连续子序列 x=αβδ，则β是x的一个子串 •前缀：删去符号串 s 尾部的零个或多于零个符号得到的符号串 •后缀：删去符号串 s 头部的零个或多于零个符号得到的符号串 •符号串的真前缀、真后缀和真子串——删去多于零个字符(非空) 必须是连续的 子序列：是从s中删除0个或者多个符号后得到的串，这些被删除的符号可能不相邻。 对于w=uv，u是前缀，v是后缀 •语言的定义 •语言就是某个字母表上的符号串的集合 •如{ε，0，00，000，…}，{ε}，∅ •任何一个语言都是Σ*的一个子集 •如语言L={anbn|n≥0} •既然语言是符号串的集合，那么符号串集合中的各种运算也可用于语言，如并、交、减等 •同样也可以定义语言上的连接、幂、闭包等运算。 C语言的语言：合法的程序构成的集合 空集{}/$Phi$和{$\epsilon$} •如何来描述一个语言？ •如果语言是有穷的(只包含有穷个句子)，可以将所有的句子列出来 •如果语言是无穷的，则要找出语言的有穷表示 •生成方式 (文法)：语言中的每个句子可以用严格定义的规则来构造。 •识别方式(自动机)：用一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就会停止并回答“是”，若不属于，要么能停止并回答“不是”，要么永远继续下去。 •文法理论是乔姆斯基在上世纪50年代提出的，包含四类形式文法理论，在编译原理中，主要用到的是上下文无关文法和正规文法(也叫正则文法) •文法G是一个四元组G=(VT, VN, S, P) •VT是终结符号集 •VN是非终结符号集 •其中VT∩VN=∅，V=VT∪VN是词汇表 •S是开始符号 •P是产生式规则集合 •P={α→β|α至少包含一个非终结符号} 终结符号的一般形式：在字母表里排在前面的小写字母，如a,b,c 运算符号，比如 +-*/ 标点符号，如逗号括号 阿拉伯数字如0，1，。。。 非终结符号： 大写字母如ABC 大写字母S表示开始符号 小写、斜体的名字，比如expr或stmt 用一对尖括号括起来的一个字符串，如<表达式> 当讨论程序设计语言时，语法单位英文单词的第一个字母的大写形式可以代表对应语法单位的非终结符号，比如表达式expression/项term、因子factor，通常用E/T/F 字母表中排在后面的大写字母X/Y/Z表示终结符也可表示非终结符 小写字母表示终结符号串u，v。。。 小写的希腊字母，表示文法符号串，可能为空串 •用文法“生成”语言的句子(符号串) 从开始符号S形成的串开始，对串中的每个子串α，如果在P中有规则α→β，则α可以替换为β，如此重复进行。当串中的每个符号都是终结符号的时候，重写结束，称最后得到的串可以从文法生成。 产生式的简写 对一组有相同左部的产生式 α→β1，α→β2…，α→β*n* 可以简单地记为： α→β1| β2 |…|β*n* 读作：α定义为或者β1 ，或者β2 ，…，或者β*n* 。并且称它们为α产生式。β1 ，β2 ，…，β*n*称为候选式。 α产生β，α生成β α可以由β组成 非终结符：至少一次出现在产生式左部 • •直接推导(direct derivation) •如果A→γ是一条产生式，则αAβ Þαγβ是一个直接推导(**指把产生式的右部****γ****替换产生式的左部****A**) •推导(0步或多步直接推导) •如果有α1 Þα2 Þ α3，则α1 Þ* α3 •用Þ+表示1步或多步直接推导 •句型和句子 •如果存在推导S Þ*α，则称α是一个**句型** •如果α是一个句型，并且α∈VT*，则称α是一个**句子**，即只包含**终结符号**的句型 即包含中间过程 •文法产生的语言L(G)={α|α是G的句子} 在推导一个句型的过程中，选择哪一个非终结符号来进行推导呢？ •最左推导: 每一步的推导都施加在句型的最左边的非终结符号上，记为Þlm •最右推导: 每一步的推导都施加在句型的最右边的非终结符号上，记为Þrm，最右推导也称为**规范推导** •由最左推导或最右推导生成的句型分别称为左句型和右句型 ![image-20251218160047421](https://chenalna.oss-cn-hangzhou.aliyuncs.com/img/image-20251218160047421.png) 可归约串的概念：不是只看你位置，有一个可归约串的判定， 为什么对左边的F规约不是最右边的规约？ 最左边的F是可归约串 最右边的F不是可归约串 规约都是要归约到开始符号 •等价文法 •一个文法对应一个语言，但一个语言可能由若干个文法产生它，这若干个文法是等价的，称为等价文法 例 G2 与 G3 •推导的过程可以用一棵树来描述 •**分析树**是描述推导的一种直观方法，也称为推导树 •分析树的特性: •根标识为开始符号 •内部结点标识为非终结符号 •每一内部结点及其子结点对应一条产生式，该结点是产生式的左部，子结点从左至右排列构成产生式的右部 •叶结点从左至右排列构成句型 •分析树和推导之间的关系 •分析树是推导过程的图形表示 •分析树忽略了推导过程中非终结符号替换的顺序 •说明一棵分析树可能对应若干个推导 最左推导和最右推导具有相同的分析树 •分析树和推导之间的关系 •分析树是推导过程的图形表示 •分析树忽略了推导过程中非终结符号替换的顺序 •说明一棵分析树可能对应若干个推导 •但是一棵分析树对应一个最左推导，也只能对应一个最右推导 ![image-20251218181948893](https://chenalna.oss-cn-hangzhou.aliyuncs.com/img/image-20251218181948893.png) 句型分析 •句型是从文法的开始符号推导而来的符号串 •设αβδ是文法G[S]的一个句型，如果存在推导 ​ S Þ*αAδ 且 A Þ+β 则称β是句型αβδ相对于非终结符号A的**短语** •我们也可以从句型的分析树角度来看短语的定义 •短语可以看作是分析树中以非终结符号为子树根节点的所有叶子节点序列 **一棵子树的所有叶子自左至右排列起来形成一个相对于子树根的短语。** •直接短语 •对于句型αβδ，如果存在推导S Þ*αAδ 且 A Þβ，则称β是αβδ相对于A的直接短语 •从分析树来看，直接短语是句型的分析树中非终结符号的直接子节点构成的符号串 •句柄: 最左边的直接短语 实际上相当于要求文法中存在产生式规则A→β ![image-20251218182545174](https://chenalna.oss-cn-hangzhou.aliyuncs.com/img/image-20251218182545174.png) ![image-20251218182553591](https://chenalna.oss-cn-hangzhou.aliyuncs.com/img/image-20251218182553591.png) •句型的素短语、最左素短语 •1. β是句型αβδ相对于A的一个短语 •2. 至少含有一个终结符 •3.β除自身外不含更小的带终结符的短语 •称β是句型αβδ相对于 A 的一个**素短语** •句型最左边的素短语称为**最左素短语** **E** **→ E + T** **E** **→ T** **T** **→ T \* F** **T** **→ F** **F** **→ (E)** **F** **→ a** ![image-20251218182634038](https://chenalna.oss-cn-hangzhou.aliyuncs.com/img/image-20251218182634038.png) •句型: T + T * F + a •短语: T+T*F+a、 T+T*F、 T、 T*F、a •直接短语: T、 T*F、a •句柄: T •素短语: T*F、a •最左素短语: T*F •句子、文法和语言的二义性 •如果一个文法的句子有两棵或两棵以上的分析树，称此句子是二义的 •最左(右)推导与分析树一一对应，句子二义说明它有两个或以上最左(右)推导 正规式(r)匹配的串集称为正规集合（Regular Set），这是一个正规语言，记为L（r） 正规式与正规集的递归定义 a--{a}，a作为字符、字符串、正规式 DFA的最小化 •基本思想: 寻找等价状态，合并之 •等价状态必须满足两个条件: 1.一致性条件 — 状态 s 和 t 必须同时为接受状态或非接受状态 蔓延性条件 — 对于所有的输入符号，状态 s 和 t 必须转移到等价的状态中 1. 一致性条件: 状态p和q必须同时为接受状态或非接受状态 2.蔓延性条件: 对于所有的a∈∑，δ(p, a)=s，δ(q, a)=r，则要求s和r必须等价。相反, 若r和s不等价, 则p和q不等价。 n初态：含有原DFA初态的状态 n终态：含有原DFA终态的状态集 •基本思想 •首先将状态划分为接受状态与非接受状态两组，然后逐步将这个划分精细化，最后得到一个不可再细化的状态集的划分，每个状态子集作为一个状态。 正规式——NFA——DFA求同——DFA最小化——程序化 词法分析图 求同：等价以后合并 求异：不等价以后拆分 •正规文法，正规表达式，有限自动机都是等价的. (从语言的等价性来考虑) •有限自动机和正规表达式的等价性 •把正规表达式化为有限自动机 •把有限自动机化为正规表达式 •正规文法和有限自动机的等价性 •把有限自动机化为正规文法(下面讲) •把正规文法化为自动机(略) 文法是用来生成串的， L（G）={串1，串2，。。。} 串的集合也叫做语言 L（M）={串1，串2.。。} 而这些串是由自动机DFA来识别的 语法分析的任务： 每种程序设计语言都有描述程序语法结构的规则，这些规则一般可以用上下文无关文法来描述。 由词法分析给出的单词符号序列是否是给定（上下文）无关符合文法的正确的序列 自顶向下分析 从跟到叶子来建立句子的分析树或给出句子的一个从开始符号出发的推到序列。 从开始符号出发，用到了五条产生式，用了五步，产生了产生式序列，来反映到树上，作为子节点 自底向上分析 从叶子到根来建立句子的分析树 或，给出一个从句子出发到开始符号的规约序列 不确定的自顶向下分析： 带回溯的分析方法： 缺点：回溯，造成效率低下 确定的自顶向下分析： 基本思想：从文法的开始符号出发，根据当前的输入符号和其他信息，唯一的确定选用哪条产生式往下推导构造分析树。 无论对错，没有回溯。 这种分析对文法有限制，并不是任意的文法都适合这种分析方法。 确定：指选择的产生式确定 预测，能够预测出正确的产生式 在每一步推导过程中可以根据产生式的右部的首符号集选择产生式。 文法符号串的首符号集的重要性 要作出确定性分析，左部相同产生式的右部首符号集交集为空集。 ccap 有个指针，匹配完毕往右走 非终结符号的后跟符号集的重要性。 要作出确定性分析，左部相同产生式的右部的首符号集交集为空集。 如果存在空产生式，与左部非终结符的后跟符号集也不想交。 FIRST(α)={a| α通过任意次（大于等于0次）推导出的符号串的首个终结符号} 1. 构造单个文法符号的首符号集 2. 构造文法符号串的首符号集 构造单个文法符号X的首符号集 α：X单个文法符号 1. α本身是终结符，FIRST(X)=FIRST(a)={a} 2. 非终结符，X->ε，FISRT(X)=∪{ε} 3. X->Y1Y2..., 判断FIRST(Y1) 1. ε∈FIRST(Y1),FIRST(X)=∪FIRST(Y1)-{ε}求FIRST(Y2) 2. 不属于FIRST(Y1)，FIRST(X)=∪FIRST(Y1) 如果ε都属于每个Y1,Y2,,YK，FIRST(x)=∪{ε} FIRST(X1X2X3...XN) 分析FIRST{ε} 1.有ε，∪FIRST(X1)-{ε}，求FIRST(Y2) 2. 无ε ，∪FIRST(X2) 如果ε都属于每个X1,X2,,YK，FIRST(x)=∪{ε} 参考P59的FIRST集求解 FOLLOW（A）={a|S大于等于0的推导后紧跟在这个非终结符号后面的终结符的集合} 1. 就是A开始符号，{$} 2. A->αBβ，FOLLOW(B)=∪FIRST(β)-{ε}中的非空符号，意思是说跟在B后面的，肯定是终结符 3. 若有A->αB,FLOOW(B)=∪FOLLOW(A) (跟在A后面的肯定是跟在B后面的) # LEX&BISON Lex：词法分析程序生成器（Lexical Analyzer Generator） 改写Lex的版本改写为C语言实现，为FLEX,快速词法分析器生成程序(Fast Lexical Analyzer Generator) LEX源程序 LEX.l ->LEX编译器->Lex.yy.c Lex.yy.c->C语言编译器->a.out 输入源代码->a.out->单词符号序列 LEX程序包含三个部分，每个部分之间通过仅有的“%%”行隔开。 第一个部分包含声明和选项设置； C语言的说明必须用分界符“%{”和“%}”括起来。 - 出现在括号中的任何内容都直接抄写到词法分析器mylex.c中，不作为正规定义和翻译规则的一部分。辅助过程也按同样方式处理 包括： - 变量说明 - 标识符常量说明 - 正规定义 正规定义中的名字可在翻译规则中用作正规表达式的成分 第二个部分是一系列模式和动作定义 形式： P1 { 动作1 } P2 { 动作2 } … Pn { 动作n } •Pi是一个正规表达式，描述一种记号的模式。 •动作i是C语言的程序语句，表示当一个串匹配模式Pi时，词法分析器应执行的动作。 第三部分是辅助过程，会被拷贝到生成的词法分析器的C语言代码 对规则的补充 规则部分中某些动作需要调用的过程，如果不是C语言的库函数，则要在此给出具体的定义。 这些过程也可以存入另外的程序文件中，单独编译，然后和词法分析器连接装配在一起。 基本过程如下： 声明部分 %% 识别规则部分 %% 辅助声明过程部分 •LEX生成的词法分析器的执行：最长匹配原则 传递单词的属性，是把属性值赋给全程变量yylval •正规定义式： if -> if then -> then else -> else relop -> < | <= | = | <> | > | >= id -> letter(letter|digit)* num -> digit+(.digit+)?(E(+|-)?digit+)? ``` 相应的LEX源程序 /*定义部分 */ %{ /* C语言描述的标识符常量的定义，如LT、LE、EQ、NE、GT、GE、IF、THEN、ELSE、ID、NUMBER、RELOP */ extern yylval; %} /* 正规定义式 */ delim [ \t\n] ws {delim}+ letter [A-Za-z] digit [0-9] id {letter}({letter}|{digit})* num {digit}+(\.{digit}+)?(E[+\-]?{digit}+)? %% /* 规则部分 */ {ws} {/* 没有动作，也不返回 */} if { return(IF); } then { return(THEN); } else { return(ELSE); } {id} { yylval=install_id(); return(ID); } {num} { yylval=install_num(); return(NUMBER); } “<” { yylval=LT; return(RELOP); } “<=” { yylval=LE; return(RELOP); } “=” { yylval=EQ; return(RELOP); } “<>” { yylval=NE; return(RELOP); } “>” { yylval=GT; return(RELOP); } “>=” { yylval=GE; return(RELOP); } %% /* 辅助过程 */ install_id() { /* 把单词插入符号表并返回指针， yytext指向该单词的第一个字符， yyleng给出它的长度 */ } install_num() { /* 类似于上面的过程，但单词是常数 */ } ``` YACC(Yet Another Compiler Compiler) YACC结合LEX可以构造编译器的前端 YACC生成的编译器主要有C语言写成的语法分析器，需要与词法分析器LEX结合一起使用，再将两部分生成的C程序一并编译。 YACC源程序 translate.y ->YACC编译器->y.tab.c y.tab.c -> C语言编译器 -> a.out 输入源代码->a.out 输出 YACC源程序由三个部分构成：声明、翻译规则、辅助规则 声明部分 %% 翻译规则部分 %% 辅助过程部分 YACC声明部分包含两种可选的内容。一种是用{%%}括起来的C语言声明，通常是声明后面内容可用的常量和变量信息。另一种内容是生命文法的终结符号。 翻译规则部分是多个候选的产生式规则，如： 左部 ：A1{语义动作程序1} | A2{语义动作程序2} ... 当然, 你可能已经在其他课程中了解到, 编译器把源代码变成可执行文件的过程 (通常) 又分为: 1. **编译:** 将源代码编译为汇编代码 (assembly). 2. **汇编:** 将汇编代码汇编为目标文件 (object file). 3. **链接:** 将目标文件链接为可执行文件 (executable). 我们在课程中实现的编译器, 只涉及上述的第一点内容. 也就是, 我们只需要设计一个程序, 将输入的 SysY 源代码, 编译到 RISC-V 汇编即可. 在这种意义之下, 编译器通常由以下几个部分组成: - **前端:** 通过词法分析和语法分析, 将源代码解析成抽象语法树 (abstract syntax tree, AST). 通过语义分析, 扫描抽象语法树, 检查其是否存在语义错误. - **中端:** 将抽象语法树转换为中间表示 (intermediate representation, IR), 并在此基础上完成一些机器无关优化. - **后端:** 将中间表示转换为目标平台的汇编代码, 并在此基础上完成一些机器相关优化. ## [词法/语法分析](https://pku-minic.github.io/online-doc/#/lv1-main/structure?id=词法语法分析) 在前端中, 我们的目的是把文本形式的源代码, 转换为内存中的一种树形的数据结构. 因为相比于处理字符串, 在树形结构上进行处理显然要更方便, 且效率更高. 把文本形式的源代码变成数据结构形式的 AST 有很多种方法, 但相对科学的方法是对源代码进行词法分析和语法分析. 对于这样一段保存在文件里的源程序: ```c int main() { return 0; } ``` 按照常规的思路, 在程序中, 我们会打开文件, 然后逐字符读入文件的内容. 此时相当于我们在操作一个字节流 (byte stream). 但这样做并不利于我们对输入程序作进一步处理, 因为在编程语言中, 单个的字节/字符通常没什么意义, 真正有意义的是字符组成的 “单词” (token). 就像你正在读的这篇文档, 文档里的每个字单拎出来都没什么意义, 连在一起, 组成单词, 组成句子, 组成段落和文章之后, 才会有意义. 词法分析的作用, 是把字节流转换为单词流 (token stream). 词法分析器 (lexer) 会按照某种规则读取文件, 并将文件的内容拆分成一个个 token 作为输出, 传递给语法分析器 (parser). 同时, lexer 还会忽略文件里的一些无意义的内容, 比如空格, 换行符和注释. Lexer 生成的 token 会包含一些信息, 用来让 parser 区分 token 的种类, 以及在必要时获取 token 的内容. 例如上述程序可能能被转换成如下的 token 流: 1. **种类:** 关键字, **内容:** `int`. 2. **种类:** 标识符, **内容:** `main`. 3. **种类:** 其他字符, **内容:** `(`. 4. **种类:** 其他字符, **内容:** `)`. 5. **种类:** 其他字符, **内容:** `{`. 6. **种类:** 关键字, **内容:** `return`. 7. **种类:** 整数字面量, **内容:** `0`. 8. **种类:** 其他字符, **内容:** `;`. 9. **种类:** 其他字符, **内容:** `}`. 而语法分析的目的, 按照程序的语法规则, 将输入的 token 流变成程序的 AST. 例如, 对于 SysY 程序, 关键字 `int` 后跟的一定是一个标识符, 而不可能是一个整数字面量, 这便是语法规则. Parser 会通过某些语法分析算法, 例如 LL 分析法或 LR 分析法, 对 token 流做一系列的分析, 并最终得到 AST. 上述程序经分析后, 可能能得到如下的 AST: ```c CompUnit { items: [ FuncDef { type: "int", name: "main", params: [], body: Block { stmts: [ Return { value: 0 } ] } } ] } ``` 在这里和之前解释 token 流的部分, 我们都用了 “可能”, 是因为 token 和 AST 这类数据结构仅在编译器内部出现, 并没有固定的规范. 它们的设计可以有很多种形式, 只要能够方便程序处理即可 ## [语义分析](https://pku-minic.github.io/online-doc/#/lv1-main/structure?id=语义分析) 在语法分析的基础上, 编译器会对 AST 做进一步分析, 以期 “理解” 输入程序的语义, 为之后的 IR 生成做准备. 一个符合语法定义的程序未必符合语义定义, 例如对于如下的 SysY 程序: ```c int main() { int a = 1; int a = 2; return 0; }复制错误已复制 ``` 它在语法上是正确的 (符合 [SysY 语法定义](https://pku-minic.github.io/online-doc/#/misc-app-ref/sysy-spec?id=文法定义)), 能被 parser 构建得到 AST. 但我们可以看到, 程序在 `main` 函数里定义了两个名为 `a` 的变量, 这在 SysY 的语义约束上是不被允许的. 语义分析阶段, 编译器通常会: - **建立符号表**, 跟踪程序里变量的声明和使用, 确定程序在某处用到了哪一个变量, 同时也可发现变量重复定义/引用未定义变量之类的错误. - **进行类型检查**, 确定程序中是否存在诸如 “对整数变量进行数组访问” 这种类型问题. 同时标注程序中表达式的类型, 以便进行后续的生成工作. 对于某些编程语言 (例如 C++11 之后的 C++, Rust 等等), 编译器还会进行类型推断. - **进行必要的编译期计算**. SysY 中支持使用常量表达式作为数组定义时的长度, 而我们在生成 IR 之前, 必须知道数组的长度 (SysY 不支持 [VLA](https://en.wikipedia.org/wiki/Variable-length_array)), 这就要求编译器必须能在编译的时候算出常量表达式的值, 同时对那些无法计算的常量表达式报错. 对于某些支持元编程的语言, 这一步可能会非常复杂. 至此, 我们就能得到一个语法正确, 语义清晰的 AST 表示了. Sys语法规范 ## 词法规范 ### 标识符 SysY 语言中标识符 `IDENT` (identifier) 的规范如下: ```ebnf identifier ::= identifier-nondigit | identifier identifier-nondigit | identifier digit;复制错误已复制 ``` 其中, `identifier-nondigit` 为下划线, 小写英文字母或大写英文字母; `digit` 为数字 0 到 9. ### [数值常量](https://pku-minic.github.io/online-doc/#/lv1-main/?id=数值常量) SysY 语言中数值常量可以是整型数 `INT_CONST` (integer-const), 其规范如下: ```ebnf integer-const ::= decimal-const | octal-const | hexadecimal-const; decimal-const ::= nonzero-digit | decimal-const digit; octal-const ::= "0" | octal-const octal-digit; hexadecimal-const ::= hexadecimal-prefix hexadecimal-digit | hexadecimal-const hexadecimal-digit; hexadecimal-prefix ::= "0x" | "0X";复制错误已复制 ``` 其中, `nonzero-digit` 为数字 1 到 9; `octal-digit` 为数字 0 到 7; `hexadecimal-digit` 为数字 0 到 9, 或大写/小写字母 a 到 f. ### [注释](https://pku-minic.github.io/online-doc/#/lv1-main/?id=注释) SysY 语言中注释的规范与 C 语言一致, 如下: - 单行注释: 以序列 `//` 开始, 直到换行符结束, 不包括换行符. - 多行注释: 以序列 `/*` 开始, 直到第一次出现 `*/` 时结束, 包括结束处 `*/`. ## [语法规范](https://pku-minic.github.io/online-doc/#/lv1-main/?id=语法规范) 开始符号为 `CompUnit`. ```ebnf CompUnit ::= FuncDef; FuncDef ::= FuncType IDENT "(" ")" Block; FuncType ::= "int"; Block ::= "{" Stmt "}"; Stmt ::= "return" Number ";"; Number ::= INT_CONST;复制错误已复制 ``` ## [语义规范](https://pku-minic.github.io/online-doc/#/lv1-main/?id=语义规范) - 在本章中, `IDENT` 的名称一定为 `main`. - `INT_CONST` 的范围为 [0,231−1][0,231−1], 不包含负号. ## [一个例子](https://pku-minic.github.io/online-doc/#/lv1-main/lexer-parser?id=一个例子) 我们将使用词法/语法分析器生成器生成一个能解析下列程序的词法/语法分析器: ```c int main() { // 忽略我的存在 return 0; }复制错误已复制 ``` 这个程序的语法用 EBNF 表示为 (开始符号为 `CompUnit`): ```ebnf CompUnit ::= FuncDef; FuncDef ::= FuncType IDENT "(" ")" Block; FuncType ::= "int"; Block ::= "{" Stmt "}"; Stmt ::= "return" Number ";"; Number ::= INT_CONST;复制错误已复制 ``` 其他规范见本章开头. ## 看懂 EBNF EBNF, 即 Extended Backus–Naur Form, 扩展巴科斯范式, 可以用来描述编程语言的语法. 基于 SysY 的 EBNF, 我们可以从开始符号出发, 推导出任何一个符合 SysY 语法定义的 SysY 程序. 那么, 如何从上述的 EBNF 推导出示例的 SysY 程序呢? 我们不难注意到, EBNF 由若干条形如 `A ::= B;` 的规则构成. 这种规则告诉我们, 当我们遇到一个 `A` 时, 我们可以把 `A` 代换成 `B`, 这就完成了一次推导. 这其中, `A` 被称为非终结符, 因为它可以推导出其他的符号. 我们可以先从开始符, 即 `CompUnit` 开始推导: ```ebnf CompUnit复制错误已复制 ``` 利用规则 `CompUnit ::= FuncDef;`, 我们可以把 `CompUnit` 替换成: ```ebnf FuncDef复制错误已复制 ``` 进一步应用规则 `FuncDef ::= FuncType IDENT "(" ")" Block;`, 我们得到: ```ebnf FuncType IDENT "(" ")" Block复制错误已复制 ``` 这里我们遇到了一些看起来和其他符号画风不太一样的符号, 比如 `IDENT`, `"("` 和 `")"`. 在我们使用的 EBNF 记法中, 这种使用大写蛇形命名法的符号, 或者被双引号引起的字符串, 被称为终结符, 它们不能进一步被其他符号所替换, 你也不会在 EBNF 中看到它们出现在规则的左侧. 我们的目标是, 利用 EBNF 中的规则, 把开始符号推导成一系列终结符. 需要注意的是, 在谈论词法/语法分析器的时候, 词法分析器返回的一个 token 通常就代表终结符. 比如这里的 `IDENT`, 对应到词法分析器中, 实际上是词法分析器返回的, 表示标识符 (identifier) 的 token. 示例程序里的 `main` 就是一个 `IDENT`. 持续利用 `FuncType`, `Block`, `Stmt`, `Number` 规则, 我们最终可以得出这样的一串终结符: ```ebnf "int" IDENT "(" ")" "{" "return" INT_CONST ";" "}"复制错误已复制 ``` 把 `IDENT` 对应为 `main`, `INT_CONST` 对应为 `0`, 这串终结符表示的就是示例程序. 你没在这串终结符中看到空格, 换行符和注释, 是因为我们之前提到, 词法分析器会自动忽略空白符和注释. 除了非终结符, 在我们使用的 EBNF 中还会出现一些别的记法: - `A | B` 表示可以推导出 `A`, 或者 `B`. - `[...]` 表示方括号内包含的项可被重复 0 次或 1 次. - `{...}` 表示花括号内包含的项可被重复 0 次或多次. 例如: ```ebnf Params ::= Param {"," Param}; Param ::= Type IDENT; Type ::= "int" | "long"; ``` 可以表示类似 `int param`, `int x, long y, int z` 这样的参数列表. ## [C/C++ 实现](https://pku-minic.github.io/online-doc/#/lv1-main/lexer-parser?id=cc-实现) 在 C/C++ 中, 你可以使用 Flex 和 Bison 来分别生成词法分析器和语法分析器. 其中: - Flex 用来描述 EBNF 中的终结符部分, 也就是描述 token 的形式和种类. 你可以使用正则表达式来描述 token. - Bison 用来描述 EBNF 本身, 其依赖于 Flex 中的终结符描述. 它会生成一个 [LALR parser](https://en.wikipedia.org/wiki/LALR_parser). 关于如何入门 Flex/Bison, 你可以参考 [Calc++](https://www.gnu.org/software/bison/manual/html_node/A-Complete-C_002b_002b-Example.html), 或者自行 STFW/RTFM. 此处我们只介绍与开篇的示例程序相关的基本用法. 首先选择一个项目模板, 此处我们以 [`Makefile` 模板](https://github.com/pku-minic/sysy-make-template)为例. 在模板的 `src` 目录中新建两个文件: `sysy.l` 和 `sysy.y`, 前者将会描述词法规则并被 Flex 读取, 后者将会描述语法规则并被 Bison 读取. 由于 Flex 和 Bison 生成的 lexer 和 parser 会互相调用, 所以这两个文件里的内容也相互依赖. `.l`/`.y` 文件有一些共同点, 比如它们的结构都是: 我们提供的 Make/CMake 模板会采用如下方式处理你的 Flex/Bison 文件: ```bash # C++ 模式 flex -o 文件名.lex.cpp 文件名.l bison -d -o 文件名.tab.cpp 文件名.y # 此时 bison 还会生成 `文件名.tab.hpp` # C 模式 flex -o 文件名.lex.c 文件名.l bison -d -o 文件名.tab.c 文件名.y # 此时 bison 还会生成 `文件名.tab.h` ```