期中开卷笔记
编译原理 期中开卷笔记
词法分析
1.【题型】构造最小化DFA
·第一步：根据Thompson法则，构造NFA。
·第二步：构造等价DFA，具体方法是：先找初始状态的\(\epsilon\)-闭包，再依次找各个\(\epsilon\)-闭包接受不同字符输入时，进入的新状态的\(\epsilon\)-闭包，确定各个\(\epsilon\)-闭包的转化关系。
·第三步：DFA最小化。
2.DFA最小化方法：状态集合细分法。
·首先，将所有状态分成两个集合：接受状态集合、非接受状态集合。
·然后，针对每个集合，分别使用字符表中各个字符\(\alpha \in \Sigma\)尝试对每个集合进行细分。
·直到每个集合均无法被任一字符继续细分，则得到的每个状态集合就对应于一个equivalence class，完成了最小化DFA的状态寻找。
语法分析
一、上下文无关文法
1.自顶向下分析：\(S \Rightarrow^* w\)
·两个选择：替换当前句型中的哪个非终结符、用该非终结符的哪个产生式进行替换。
·最左推导：总是选择每个句型的最左非终结符进行替换；与最右归约相对应。
·最右推导：总是选择每个句型的最右非终结符进行替换；与最左归约相对应。
·自底向上分析总是采用最左归约；自顶向下语法分析采用的是最左推导。
2.歧义文法及其解决方案
·歧义文法：不同语法分析树对应于同一个token序列，但不同语法分析树含义不同（如：符号优先级不同）。
·符号优先级：在语法分析树中，距离树根越远的操作优先级越高。
·解决方案：改造文法/声明优先级（实际做法，不降低文法可读性）。
二、递归向下分析法
1.定义：由一组过程组成，每个过程对应于一个非终结符及其所有产生式。
2.预测分析法与递归下降分析法
·预测分析法：向前看固定个数的符号，选择正确的产生式；是递归下降分析法的特例。
·预测分析法确定、无需回溯；递归下降分析法可能需要回溯。
·向前看\(k\)个输入符号的分析法，称为\(LL(k)\)分析法。
三、文法转换
1.回溯问题及其解决方案
·回溯问题：同一非终结符的多个产生式存在共同前缀，则导致回溯问题。
·解决方案：尽可能延迟决策时间（即：左公因子提取），如\(S \rightarrow aA | aB\)改为\(S \rightarrow aS', S' \rightarrow A | B\)。
2.左递归问题及其解决方案
·直接左递归问题：含有\(A \rightarrow Aw\)形式的产生式，即为直接左递归。
·间接左递归问题：经\(\geq 2\)步的推导，产生终结符本身，即为间接左递归。
·直接左递归消除：原始形式\(A \rightarrow A\alpha_1 | A\alpha_2 | \cdots | A\alpha_n | \beta_1 | \cdots | \beta_m\)改为\(A \rightarrow \beta _1A'|\beta_2 A'| \cdots \beta_mA', A'\rightarrow \alpha_1A'|\alpha_2A'|\cdots|\alpha_nA' | \epsilon\)
·间接左递归消除：首先将间接左递归替换为直接左递归，再消除直接左递归。
四、\(LL(1)\)语法分析
1.\(FIRST/FOLLOW\)集合与\(LL(1)\)分析表
·如果\(FOLLOW(B) = \{a, c\}, B\rightarrow bC|dB|\epsilon\)，那么\(B\)遇到\(a\)或\(c\)时，表项应填充规则\(B \rightarrow \epsilon\)。
·需注意：若\(B\)是可空的，则\(FIRST(B)\)应该包含\(\epsilon\)。
2.\(LL(1)\)文法的等价判定条件
①文法不含左递归。
②对任意两个产生式\(A\rightarrow\alpha, A\rightarrow\beta\)：\(FIRST(\alpha) \cap FIRST(\beta) = \empty\).
③若\(A \rightarrow \epsilon\)，则\(FIRST(A) \cap FOLLOW(A) = \empty\)。
3.\(LL(1)\)含义：从左向右扫描输入、进行最左推导、向前看\(1\)个输入符号。
4.\(LL(1)\)分析表的填充
·\(\forall t \in FIRST(A)\)，选择能够得到\(A \Rightarrow^* tw\)的产生式\(A \rightarrow \alpha\)进行填充。
·若\(t \in FOLLOW(A)\)且\(A\)可空，选择能够得到\(A \Rightarrow ^* \epsilon\)的产生式\(A \rightarrow \alpha\)进行填充。
·概括：对于每个表项\((X, \alpha)\)，需同时考虑“可空导出”、“非空导出”两种情形，“可空导出”对应于\(\alpha \in FOLLOW(X)\)，“非空导出”对应于\(\alpha \in FIRST(X)\)。
5.\(LL(1)\)分析表的匹配
·非终结符：匹配、出栈；终结符：根据前瞻字符查询分析表，进行产生式替换，替换所得符号序列倒序进栈。
6.自顶向下语法分析的错误恢复
·若栈顶为\(A\)时，前瞻符号为非预期符号（对应于文法分析表中\(A\)的空白表项），则跳过该符号，直到后续的token落入\(FOLLOW(A)\)，再退出\(A\)函数。
·做法的目的：使得后续的处理过程不受到A()函数中错误的影响。
五、\(LR\)语法分析
1.基本方法与操作
·基本方法：最左归约（反向构造最右推导）。
·基本操作：shift，token依次进栈；reduce，栈顶的若干个终结符、非终结符组成的序列恰好与某产生式右端匹配，全部出栈，替换为产生式左端非终结符。
2.\(LR(0)\)分析表
·item：点号左侧为已完成分析的符号序列，右侧为即将分析的符号序列。
·点号在最右侧的complete item，下一步是归约操作；点号尚未到达最右侧的incomplete item，下一步是移入操作。
·每个状态要不断对点号右边的非终结符进行展开，直到规则无法增加，形成闭包为止。
·在\(LR(0)\)分析表中，只包含complete item的状态，无论遇到的下一个符号是什么，都会直接发生归约。
3.\(LR(0)\)分析法
·引入item，但是每条规则没有前瞻符号。
4.\(SLR\)分析法
·DFA的构建过程与\(LR(0)\)分析法完全相同。
·表达能力强于\(LR(0)\)，原因是对归约添加了约束，只有遇到的下一终结符在将要归约到的非终结符的\(FOLLOW\)集合中，归约动作才能执行。
5.\(LR(1)\)分析法
·每条规则后增加终结符，如\(A \rightarrow \alpha.X\beta, z\)中，对\(X\)展开时，\(X\)产生式的规则后应添加\(w \in FIRST(\beta z)\)的终结符作为限制。
·起始状态：\((S' \rightarrow .S\$, ?)\)的闭包。
6.\(LALR\)分析法（一些著名编译器实际采用的分析法）
·构造方法与\(LR(1)\)类似，但是进行了同类项合并，更为简洁，但表达能力有所下降。
·\(LALR/LR(1)\)表达能力的区别：在于是否能解决reduce-reduce冲突。
·同类项合并：包含点号的规则相同，终结符不同的状态合并为一个等价状态。
7.冲突问题
·\(LR\)分析法只存在shift-reduce和reduce-reduce冲突。
·\(LR(1)\)分析法不存在reduce-reduce冲突。
·\(LR(0), SLR, LALR\)分析法可能存在reduce-reduce和shift-reduce冲突。
8.冲突解决方案
·shift-reduce冲突：优先shift（Yacc的默认选择），reduce优先级更低。
·reduce-reduce冲突：位置优先，选择第一条产生式进行归约。
抽象语法树
1.作用：语法分析树去除无意义符号得到抽象语法树，从而简化语法树。
2.Yacc自底向上分析：值栈、文法分析栈进行并行操作，计算各个非终结符、终结符的语义值。
语义分析
1.符号表：建立标识符及其属性（位置、类型等）的映射，与语法树并行存在，使用binding。
2.原始符号表\(S_0\) + 新增规则\(\{a \rightarrow int\}\)，加号两侧不可颠倒，原因是若新增规则与原始符号表中相同标识符的规则冲突，则新规则会覆盖旧的规则。
3.函数式风格：新增规则时，对旧表作拷贝，针对旧表的copy进行修改；命令式风格：直接针对符号表进行更改，退出作用域后通过撤销更改得到之前的符号表。
4.符号表：插入binding时使用头插法，越靠近bucket头部的binding，距离当前所处作用域也越近。
5.类型检查：基于抽象语法树的递归函数。
活动记录
一、函数调用基本概念
1.函数调用与栈帧变化过程
（1）函数g调用函数f
①栈指针(sp)：指向函数g给函数f传递的第一个参数的位置。
②函数f申请一个帧的空间，范围是sp - frame_size ~ sp。
（2）进入函数f
①新的帧指针fp用sp进行赋值，即指向static link位置；旧的fp保存在内存中。
②此时，fp和sp指向的位置相同。
（3）函数f执行
sp指针随着空间分配，可能不断往低地址增长；fp不变。
（4）退出函数f
①栈指针sp设为fp，恢复到进入f前的状态。
②从内存中，将保存的fp值恢复给fp。
2.寄存器与参数传递
①叶子过程（不再调用其他过程的过程）：无需将incoming arguments写入内存，而是直接放入寄存器，从而节约内存，提高效率。
②一些优化过的编译器，采用过程间寄存器分配。
③函数f调用h函数时，若位于寄存器r1中的变量x已经成为死变量，则可以直接覆盖该寄存器r1。
④寄存器窗口：存在于部分体系结构之中。
3.返回地址保存
·叶子过程可直接将返回地址保存在寄存器中，非叶子过程需将返回地址写入内存栈保存。
·若采用过程间寄存器分配技术，则非叶子过程可能无需将返回地址写入内存。
二、静态链接
1.block feature：某些语言中，内部函数可能用到外部函数定义的一些变量。
2.静态链接：调用函数f时，给函数f传递父函数(caller)的帧指针，父函数的帧指针即为静态链接。
3.lambda lifting：子函数实际访问的父函数中的每个变量，都作为一个额外的参数传递给子函数。
4.注意：进行递归调用时，假设prettyprint->show->show为调用关系，则show->show调用时，传递的static link并非父show函数的static link，而是prettyprint的static link。
5.结构体：定义时无需申请空间，真正进入结构体时再作申请；结构体可以视为函数定义，为其申请活动记录，但该方法不高效；可视为临时表达式。
三、参数传递的分类
1.传值(pass by value)：实参的数值传递给形参。
2.传引用(pass by reference)：传递变量的地址。
3.双向值传递(pass by value-result)：函数调用时，实参的值传给形参；函数返回时，形参的值也会返回给实参。
4.命名传递(pass by name)
中间表示
1.中间语言表达形式：提高编译器的模块化程度和可移植性。
2.前端：词法分析、语法分析、语义分析、中间表达生成；后端：中间表达优化、机器代码生成。
3.三地址码：复合表达式拆分成基本表达式；可使用四元组（三个地址、一个操作符）进行表示。
测验、课件例题、期中考真题
课件例题
·\(LR(0)\)分析：注意同一产生式，点号位置不同，则为不同的item，不能混淆。
·\(LR(1)\)分析与\(LALR\)分析：同样的item，不同的终结符，对应状态是否能合并，是\(LR(1)\)文法和\(LALR\)文法的本质区别。
测验一
测验二
（1）FIRST/FOLLOW集合的计算
·注意每添加一项，都要针对其他非终结符进行检查，看是否需要相应地进行补项，如此迭代直到不再更新。
·注意非终结符是否为可空非终结符。若\(D\)可空，则由\(C \rightarrow SD\)可知：\(FOLLOW(C) \subset FOLLOW(D)\)。
期中考真题（判断）
1.A LR(1) parser cannot parse any left-recursive CFG without ambiguity.
【解答】错。\(LR(1)\)分析法可以分析一部分\(CFG\)文法。左递归可能会导致shift-reduce冲突，但如果对reduce作出限制的FOLLOW集合不包含shift字符，则这类左递归不会影响\(LR(1)\)分析器的正常行为，不会在\(LR(1)\)分析中产生二义性。
2.LL(1) grammar cannot be left-recursive.
【解答】对。LL(1)文法等价判断条件的三个要求之一，就是不能为左递归文法。
3.Given a legal string of tokens for a CFG, there must be a unique parsing tree to derivate the string.
【解答】错，要看CFG是歧义文法还是非歧义文法。
4.The language L={a^n b^n|n>=1} can’t be generated by any regular expression.
【解答】对，DFA存储能力有限，无法应对“无限内存”的场景。
5.There is only one parse tree for the string of an unambiguous grammar.
【解答】对。
6.If a grammar is LR(1), but not LALR(1). There may be shift-reduce conflicts in its parsing table of LALR(1).
【解答】错。\(LR(1)\)和\(LALR(1)\)表达能力的区别在于reduce-reduce冲突，它们面临shift-reduce冲突的表达能力是相同的。
7.Finding the next handle is the man task of a LR parser.
【解答】
对。句柄即已分析的句型（含终结符、非终结符）中，与产生式右侧序列相匹配的字串。
8.Both DFA and NFA can recognize regular set.
【解答】对。正则集(regular set)即正则表达式表达的字符串集合，在表达能力上，正则表达式、NFA、DFA是一致的。
9.The parse tree will completely reflect the derivation steps for a string.
【解答】错。仅语法分析树本身，不能完全看出推导过程。
10.Left recursion is commonly used to make operations left associative.
【解答】对。自行举例展开\(S \rightarrow S + a\)，根据操作离语法分析树树根越远，越优先执行的原则，可验证该结论。
选择真题
1.\(LL(1)\)文法的等价判断条件（见知识点）。
2.YACC的分析方法是：LALR(1)分析法。
3.LL(1)分析属于自顶向下分析，因此其分析表只有generate, accept两种动作，没有自底向上分析表中的shift, reduce动作。
4.When inheriting a previously computed synthesized attribute during LR parsing, it is suitable to treat the computed synthesized attribute as (external data structure).
5.All inherited attributes can be changed into synthesized attributes by suitable modification of the grammar, without changing the language of the grammar.
6.继承属性：应通过语法分析树的前序遍历进行计算。
解答真题
1.【题型——\(LL(1)\)分析法】
①如果\(T \rightarrow \epsilon\)，要在\(FIRST(T)\)中写上\(\epsilon\)符号。②由于\(T \rightarrow ST'\)，\(T'\)可空，因此\(FOLLOW(T) \subset FOLLOW(S)\)。特别关注与nullable符号相关的\(FOLLOW\)集合的包含问题。