编译原理复习笔记

摘要:

祝我活过七月QAQ

第二章 文法和语言

  • 符号串长度 符号串α的长度是指符号串α中含有符号的个数,记为︱α︱。特别约定,空串ε为零,即︱α︱=0。

  • 符号串连接运算 设x和y是字母表∑上的符号串,在符号串x的最后一个符号之后顺序接上符号串y的符号得到的新符号串z,则称符号串z是由符号串x和符号串y经过连接运算的结果,记为z=x·y,其中,·是连接运算符。

  • 符号串集连接运算:设A,B是字母表∑上的符号串集,·是符号串集连接运算,则C=A·B={x·y︱xÎA,yÎB}。 笛卡尔积

  • 符号串集正闭包运算 设A是字母表∑上的符号串集, A+是A的正闭包,则: A+=A1∪A2∪A3∪···∪An···

  • 符号串集闭包运算 设A是字母表∑上的符号串集, A是A的闭包,则 : A =A0∪A+ ,

    ​ 即:A* =A0∪A1∪A2∪A3∪···∪An···

    文法G定义为一个四元组(VN,VT,P,S),记为G=(VN,VT,P,S)。其中,

    ① VN是非空有穷集合,称为非终结符集,其元素称为非终结符;

    ② VT是有穷集合,称为终结符集,其元素称为终结符;

    ③ P是非空有穷集合,称为规则集,其元素是字母表VN∪VT上的规则,VN∪VT称为文法的字母表V,且VN∩VT=F;

    ④ S∈VN,称为开始符。

  • 直接推导和直接归约即为只需一步就可以完成的推导或者归约

  • 句型与句子:设文法G=(VN,VT,P,S),如果有S星步推导出β,则称β是文法G的句型。如果有S星步推导出β,且β∈VT*,则称β是文法G的句子。

  • 语言:文法G=(VN,VT,P,S)的产生语言定义为文法G的句子集合,记为L(G)

  • 文法等价:设G1 和G2是两个文法,如果L(G1)=L(G2),则称文法G1和G2是等价的。

  • 文法类型:

    • 0型文法 设文法G=(VN,VT,P,S),如果任意α→β∈P,α中至少含有一个非终结符,则称文法G属于0型文法。0型文法,也称为短语文法。

    • 1型文法 设文法G=(VN,VT,P,S),如果任意α→β∈P,α中至少含有一个非终结符,且除空规则之外,α的长度不大于β的长度,即︱α︱≤︱β︱,则称文法G属于1型文法。 1型文法,也称为上下文有关文法。

    • 2型文法 设文法G=(VN,VT,P,S),如果任意α→β∈P,α∈VN ,则称文法G属于2型文法。2型文法,也称为上下文无关文法。

    • 3型文法 设文法G=(VN,VT,P,S),如果任意α→β∈ P,α∈ VN ,且β只能是aB或a(除空规则之外),则称文法G属于右线性3型文法。

      设文法G=(VN,VT,P,S),如果任意α→β∈ P,α∈ VN ,且β只能是Ba或a(除空规则之外),则称文法G属于左线性3型文法。

      左线性3型文法和右线性3型文法,统称3型文法,也称为正规文法。

    • 注意:2型文法和3型文法中α∈ VN而不是α∈ VN,即文法左部就是*有且仅有**一个非终结符。

  • 上下无关文法一个显著特征是规则左部一定有且仅有一个非终结符。利用这个特征,可以不列出VN和VT ,给出一个上下无关文法的简洁描述方法:①文法名G改写成G[S],其中,S表示开始符;②规则集P,仅书写其具体规则。例如:

    G6[S]:

    S→A0︱BS0

    A→0︱1

    B→0︱1

  • 最左推导、最右推导、规范推导、规范归约、规范句型:如果在推导的每一步总是选择当前句型的最左(最右)边非终结符进行推导,则称这种推导过程为最左(最右)推导。最右推导,也叫规范推导。由规范推导所得的句型,叫做规范句型。规范推导的逆过程,是最左归约,最左归约也叫做规范归约,另外,在自下而上的归约过程中,如果每次都是对句柄进行归约,那么这个过程就是规范归约。

  • 语法树:假设文法G=(VN,VT,P,S),则文法G的语法树是一个满足下列条件的多叉树:

    (1)以文法开始符S做为树根;

    (2)以终结符号或非终结符号做为树的其他结点,且子树根和其孩子结点分别是某规则的左部和右部。

    注意: (1)语法树是和句子相对应的,而不是和文法相对应。构造出来的语法树是某个句子的语法树,而不是某个文法的语法树。(2)非叶子节点一定是非终结符(3)全部叶子节点组成的符号串是文法的句子

    图:ppt p35

  • 语法的二义性:如果一个文法G,某个句子存在对应的至少两棵不同的语法树,则称文法G是二义性的。

    推论:如果文法是无二义性的,一个句子的语法树反映了该句子的全部推导过程;② 如果文法是无二义性的,一个句子的最左(最右)推导是唯一的

  • 句型分析:假设文法G[S]是语言L之文法,即L(G)=L,则“符号串α是否符合语言L的语法问题” 被等价地转化成“推导或归约问题”,这样,自然地形成了推导法和归约法两大类分析方法。推导法和归约法,也分别称为自上而下的分析方法和自下而上的分析方法。

  • 短语的找法:在一个句型对应的语法树中,以某个非终结符为根的两层或两层以上的子树的所有末端节点从左到右的排列就是相对于该非终结符的一个短语

  • 直接短语的找法:接上一条,如果子树只有两层,则这个短语就是直接短语

  • 句柄的找法:句型的最左直接短语,称为该句型的句柄

  • 短语、直接短语、句柄之间的关系:短语是可归约串,直接短语是可以立即归约的短语,句柄是在当前的从左到右、自下而上的分析过程中,应该立即归约的短语

  • 短语、直接短语、句柄都是既可以由终结符也可以有非终结符的

第三章 词法分析

  • 正规文法:见上一章3型文法处的介绍

  • 正规式:基于字母表∑上的正规式(也称为正则表达式)定义如下,正规式e的计算值称为正规集,记为L(e)。 如果忘了正规式是什么,想一想正则表达式就知道了

    1. ε是∑上的正规式,L(ε)= {ε}

    2. Ф是∑上的正规式,L(Ф)=Ф

    3. 任何a∈∑,a是∑上的正规式,L(a)= {a}

    4. 如果e1和e2是∑上的正规式,则

      4.1 (e1)是∑上的正规式,L((e1))=L(e1)

      4.2 e1︱e2 是∑上的正规式,L(e1︱e2)=L(e1)∪L(e2)

      4.3 e1 · e2 是∑上的正规式,L(e1· e2)=L(e1)·L(e2)

      4.4 e1* 是∑上的正规式,L(e1*)=L(e1)*

  • 两个正规式e1和e2相等,是指正规式e1和e2 计算值相等(即L(e1)= L(e2)),记为e1= e2 。

    设r,s,t为正规式,则正规式有如下定律:

    1. 交换律:r︱s = s︱r

    2. 结合律:(r︱s)︱t = r︱(s︱t)

    ​ (r·s)·t = r·(s·t)

    1. 分配律:r·(s︱t)= r·s︱r·t

    ​ (s︱t)·r = s·r︱t·r

  • 如果正规式r和文法G,有L(r)=L(G)则称正规式r和文法G是等价的。

  • 正规式转换成正规文法的转换规则和例子,见ppt p10 p11。正规文法转换成正规式的规则见第12页

  • DFA与NFA的区别

    1.NFA的状态转换箭头上可以有ε。

    2.NFA状态转换函数转换后的结果是一个集合,也就是说,某一个状态接受了一个字母后,可能会同时通向不同的状态。但是DFA在接受一个字母后会通向唯一确定的一个状态

    3.DFA的开始状态是唯一的,NFA的开始状态是一个集合。这就是为什么在LR分析构建识别活前缀的DFA中,一定要对文法进行扩展,是为了保证开始状态只有一个

  • 自动机的等价性:如果FA M1 和FA M2接受相同的符号串的集合(即L(M1)=L(M2)),则称FA M1和FA M2是等价的。

  • NFA到DFA的转换:ppt27页:先求初始状态的ε闭包,作为一个新的状态。然后对这个新状态中的每一个状态再求ε闭包,知道不再出现新的状态。所有包含了原本的结束状态的新状态都是新的结束状态。

    注意:每一个状态都是闭包

  • DFA的最小化:现根据是否是结束状态划分为两个集合,然后看哪些集合不是“一家人”再进行进一步的划分(注意:这里仅仅是DFA的最小化方法,如果给出的是NFA需要先转换成DFA

  • 正规式与有穷自动机的等价性:如果正规式r和有穷自动机M,有L(r)=L(M)则称正规式r和有穷自动机M是等价的。

  • NFA -> 正规式:ppt41页,牢记三个转换规则。注意:X要通过ε 指向NFA的所有开始状态,NFA的所有结束状态都要通过ε指向Y

  • 正规式 -> NFA:ppt43页,重点关注规则三:对于R1这种正规式,需要在前后加上*ε边。这个ε**之后可以视情况去掉。

  • 右线性正规文法 -> NFA:首先需要注意前期的准备不能出错,原本的右线性正规文法是G=(VN,VT,P,S),其中S是开始符号,P是推导规则。在构造与之等价的NFA时,毋庸置疑需要S作为开始符号,对于结束符号,则需要我们新定义一个符号,这个符号不能在原本的VN中出现过。假如说这个新的结束状态我们定义为Z,那么NFA可以表示为M=(VN∪{Z},VT,f,{S},{Z}),其中VN∩{Z}=Φ

  • 左线性正规文法 -> NFA:ppt46页。整体和上面的是反过来的,相当于归约,新增加的状态不再是结束状态而是开始状态,原本的文法中的开始符号变为NFA的结束状态。

  • DFA -> 右线性正规文法

  • 总结前面的一大堆转换:(ppt55页的图是一个很好的概括)

    NFA转换成DFA

    DFA的最小化

    正规式转换成NFA

    NFA转换成正规式

    左线性正规文法转换成NFA

    右线性正规文法转换成NFA

    DFA转换成右线性正规文法

第四章 自顶向下语法分析方法

  • 不确定的自顶向下分析方法是,在确定要选择非终结符的哪个规则进行推导时,采用的方法是挨个试。而确定的自顶向下分析方法会选择唯一的可能推导出输入串的规则进行推导,这里的唯一意思是推导出输入串α的解只有一种且每次在选择使用非终结符的哪一个规则时,选择是确定的。需要注意,确定的自顶向下语法分析方法采用的是最左推导

  • First集:设文法G=(VN,VT,P,S),则

    ​ FIRST(α)={a︱α星步推导出aβ,a∈VT,α,β∈V*}

    特别地,α星步推导出ε,约定ε∈FIRST(α)

  • FOLLOW集在最左推导中,一旦句型的最左非终结符A,除空规则外,其它所有规则都不可能推导出由输入符(假定为ai )开头的符号序列,这时使用空规则,意味着将匹配d的工作交给了句型A之后的部分,也就是后面这部分要能推导出以ai开头的符号串才有可能匹配成功 FOLLOW(A)是由任意句型中紧邻非终结符号A之后出现的终结符号a组成的集合。

  • SELECT集:使用统一的方法来选择使用规则,即当某规则右部能推导出空时,将其FIRST和FOLLOW这2个集合合并考虑,以确定在什么情况下选择该规则。只有在规则右部能推出空时才考虑FOLLOW。

    定义:ppt13页

  • 理清关系:如果要采用确定的自顶向下分析方法,那么文法必须是LL(1)文法,这里的关键在于,我们要采用的是确定的自顶向下分析方法。假如说我们要使用的是不确定的自顶向下方法,那么就不需要关心文法是不是LL(1),当然,在本课程中我们要讨论的都是确定的自顶向下方法。另外,我们必须知道的是,确定的自顶向下分析方法一定是采用最左推导,这个是规定,也是“确定”的原因。

  • 确定的自顶向下语法分析思想:

    假定文法G是LL(1)文法,在SÞα 最左推导过程中,遇到选用U规则时,如果输入串α 的当前符号a,属于某个U规则的 SELECT(U→αi),则采用U→αi进行唯一可能正确的推导。

    如果当前符号a,不属于任何一个U规则的 SELECT(U→αi),则结束推导,同时断定α不是文法G的句子。

    注意:这段文字的前提是假定文法时LL(1)文法,如果文法不是LL(1)文法,那么就不一定有“如果当前符号a,不属于任何一个U规则的 SELECT(U→αi),则结束推导,同时断定α不是文法G的句子”

  • 计算FOLLOW集:ppt20页。需要注意:第一步要置FOLLOW(S) = {井}

  • FIRST集里面可以有空,但是FOLLOW集和SELECT集里面不能有空

  • LL(1)文法的判别:文法G是LL(1)文法的充分必要条件是文法G每个U→α1︱α2︱···︱αn规则,满足下列条件:

    SELECT(U→αi)∩SELECT(U→αj)=Φ

    (i≠j ,1≤i≤n,1≤j≤n)

    注意:是单个非终结符的规则的SELECT之间两两相交为空,而不是所有非终结符规则SELECT两两相交为空

    在判断一个文法是不是LL(1)的时候可以先看是不是左递归文法或者是否有左公因子,如果是的话直接判断不是LL(1)就不用指向下面的步骤了

    具体步骤

    1. 计算可以推出空的非终结符(即考察哪些非终结符在计算SELECT时需要考虑FOLLOW)(这一步其实可以跳过)
    2. 计算非终结符的FIRST集(这一步其实可以跳过)
    3. 计算规则右部的FIRST集
    4. 计算非终结符的FOLLOW集
    5. 计算规则的SELECT集
    6. 判断非终结符各自的规则之间是否两两不相交
  • 某些非LL(1)文法到LL(1)文法的等价变换:提取左公因子法和消除左递归法

    注意:这些方法仅仅确保变化前后的等价性,至于变换后的文法是不是LL(1)文法,需要再做判断

  • 提取左公因子法:顾名思义,ppt25页

  • 消除左递归法:ppt28页

  • 确定的自顶向下语法分析方法——递归子程序法,即将每个非终结符编写成一个递归子程序 ppt32页

  • 确定的自顶向下语法分析方法——预测分析法:首先需要判断文法是不是LL(1)文法,如果不进行这个判断,在话预测分析表时可能会出现不同规则撞进了同一个格子。在将非LL(1)文法转换成LL(1)文法时,注意要将消除左公因子和消除左递归一起使用。之后分为分析栈、输入栈,并且在开始前将井S入分析栈。

    注意:画分析表时,非终结符不要忘记井。要学会ppt41页的步骤表格的画法,其中动作那一列,如果是归约动作就写出归约规则,如果是匹配动作就写清楚是谁匹配

第六章 LR分析

  • LR分析法的两个性质:

    1. 当分析栈中出现句柄时,LR分析器会马上将他识别出来,并进行归约
    2. 任何时刻,分析栈和输入栈的符号串拼接起来,都是一个规范句型。(规范归约过程中的每一个句型都是规范句型)
  • 前缀:将符号串的任意含有头符号的子串称为前缀。特别地,空串ε为任意串的前缀。

  • 对于一个规范句型,刚刚好包含句柄的前缀就是可归前缀,可归前缀的前缀就是活前缀。活前缀和可归前缀都不会包含句柄之后的符号。例如文法G[S],句型aAbcde的句柄为Ab,活前缀有:ε、a、aA和aAb,其中,aAb为可归前缀。

    注意:活前缀不要忘了ε

  • 一个正确的LR分析表会保证分析栈中的符号始终是活前缀

  • LR(0)项目:在每个产生式右部添加一个圆点,表示我们在分析过程中看到了产生式的多大部分

  • LR(0)项目的分类:

    ① 移进项目(·在终结符前面):

    ​ 形如A→α· aβ之项目称为移进项目。

    ② 待约项目:等待X被规约出来

    ​ 形如A→α·Xβ之项目称为待约项目。

    ③ 归约项目:

    ​ 形如A→α· 之项目称为归约项目。

    ④ 接受项目:

    ​ 形如S′→α· 之项目称为接受项目

    特别地,空规则A→ ε对应的LR(0)项目为A→ ·

  • 构造识别活前缀的DFA

    第一种方法分为两步(一般不用这种方法)

    1. 构造由LR(0)项目连接而成的NFA
    2. 将NFA转换为DFA(子集法)

    第二种方法(常用,其实就是将上面的两步合成了一步):

    1. 构造LR(0)项目的闭包一个完整的闭包就是DFA的一个状态。闭包的定义:

      设I是文法G的LR(0)项目子集,则closure(I)定义如下:

      ⑴ I 包含于 closure(I)

      ⑵ {B→·γ︱A→α·Bβ∈closure(I)} 包含于 closure(I)

       ⑶ 重复⑵,直到closure(I),不再扩大为止

    2. 这样就可以直接写出DFA,ppt 21 22页

    我们为转换后的DFA的各个状态编号,这个编号即为LR分析表中的状态。LR分析的移进和归约实际上就是在这个DFA上游走

  • LR分析过程中,归约操作的解释:LR分析法出现归约时,会先将目前分析栈栈顶要归约的符全部出栈,然后将规约成的非终结符入栈,这个过程就对应于DFA上从某个结束状态回退了一步。紧接着,LR分析会再找到新入栈的非终结符的状态编号,这对应于DFA上回退到的那个状态在获得了这个非终结符之后,又前进了一步,前进到达的那个状态的编号即为LR分析中非终结符的编号

  • DFA的每一个状态叫做项目集,所有项目集的集合叫做项目集规范族

  • LR(0)分析表的构造:ppt 23页24页

  • 移进-归约冲突和归约-归约冲突如果同时含有移进项目和归约项目的项目集称为含有移进-归约冲突的项目集。如果同时含有一个以上的归约项目的项目集称为含有归约-归约冲突的项目集。

  • LR(0)文法的定义:如果文法G的LR(0)项目集规范族不存在移进-归约冲突或归约-归约冲突的项目集,则文法G称为LR(0)文法。

  • LR(0)文法的性质:

    ⑴如果文法G是LR(0)文法,则G可采用LR(0)分析法。

    ⑵如果文法G是LR(0)文法,则G是无二义性的。

  • 当存在移进归约冲突或者归约归约冲突时,LR(0)分析法就不好用了,SLR(1)分析法可以解决这个问题

  • SLR(1)文法的定义与性质 ppt28页

  • SLR(1)举例 ppt29-32页

  • LR(1):写累了 ppt33-39

  • LR(0) SLR(1) LR(1)的个人小结:对于LR(0),每一个项目集都没有冲突,只需要根据接下来会出现的符号在DFA里面游走就行了,不会出现分歧,这是一种比较理想的状况,这就是LR(0)。进一步,如果某个项目集中存在冲突,也就是说现在有移进和归约两个选择,如何做选择呢?假如说这个时候,可以被移进的终结符是a,可以被归约出来的非终结符的FOLLOW是只有一个非终结符b(准确来讲a和b都应该是集合),也就是说他们两个相交为空,这个时候就好办了:如果接下来遇到的是a,那么就移进,如果接下来遇到的是b,那就归约,这就是SLR(1)。接下来来到LR(1),也就是现在a和b相交不为空了,比如说交集是c,那么当我现在遇到c的时候,该移进还是该归约呢?这就要看如果这一步归约了,接下来出现的符号是否能否满足后续的移进和归约。这部分看下ppt34页会清楚一点。

  • 注意:在判断是否是某种LR文法时,不要只关注引进符号集和归约相关符号集相交是否为空,还要关注归约符号集之间相交是否为空,也就是说不要只关注移进-归约冲突,还要关注归约-归约冲突

  • 任何一个二义性文法决不是LR类文法

第七章 语法制导的语义计算

仅补充了ppt上没有或者没写清楚的内容

  • 属性文法:属性文法是以上下文无关文法为基础,另外添加了两种东西而形成的,他们是:

    1. 为每个符号添加属性
    2. 为每个产生式添加语义规则

    所以,如果简单理解的话,属性文法 = 上下文无关文法 + 符号属性 + 语义规则

  • 终结符只有综合属性,由词法分析器提供

  • 对于S属性文法,我们可以将语法树的构造以及每个节点属性的计算合并在一起同时进行,在计算机中对S属性文法进行语义计算时,采取的方法和LR分析法类似。

  • 对于L属性文法,因为有继承属性,这个时候一般就是先把语法树画出来,然后再根据语义规则计算节点的属性,课件上介绍的一种计算L属性文法的属性值的方法是深度优先遍历语法树,简单来讲就是在语法树向深处遍历的时候,将沿途经过的节点的继承属性全都算出来,当没法继续深入时就开始往回走,并把之前途径的节点的综合属性计算出来。

  • S属性文法一定是L属性文法

  • 前面的属性文法没有体现属性计算的顺序等细节,但是翻译模式会体现出这些细节,这就是翻译模式和属性文法最重要的一个区别

  • 对于S翻译模式,一般使用LR分析法

  • 对于L翻译模式,当其中不包含继承属性时,可以使用自顶向下的分析方法(类似于LL(1)分析法),如果其中包含继承属性,就需要将继承属性用综合属性表示,然后再使用自底向上的分析方法(类似于LR分析法)。