编译原理知识点参考.docx

第三章3.1 对于词法分析器的要求1词法词法分析的任务：从左至右逐个字符地对源程序进行扫描，产生一个个单词符号。词法分析器(Lexical Analyzer) 又称扫描器(Scanner)：执行词法分析的程序。2程序语言的单词符号：关键字、标识符、常数、运算符、界符。3输出的单词符号的表示形式:(单词种别，单词自身的值)Eg：while (i=j) i-;输出单词符号：=, - 4词法分析器作为一个独立子程序：结构简洁、清晰和条理化，有利于集中考虑词法分析一些枝节问题。5词法分析器3.2 词法分析器的设计1词法分析器2输入、预处理：输入串放在输入缓冲区中。预处理子程序：剔除无用的空白、跳格、回车和换行等编辑性字符;区分标号区、捻接续行和给出句末符等扫描缓冲区（指向开始位置，向前搜索确定终点）3单词符号的识别、超前搜索：(1)基本字识别Eg：DO99K=1，10 DO 99 K = 1，10 IF(5.EQ.M)GOTO55 IF (5.EQ.M) GOTO 55DO99K=1.10IF(5)=55需要超前搜索才能确定哪些是基本字(2)标识符(3)常数(4)算符和界符4状态转换图(有限方向图)结点代表状态状态之间用箭弧连结，箭弧上的标记(字符)代表射出结状态下可能出现的输入字符或字符类。一个状态转换图可用于识别(或接受)一定的字符串。5语法分析的状态转换图6状态转换图的实现思想：每个状态结对应一小段程序。7状态转换图实现(了解)1)ch 字符变量、存放最新读入的源程序字符2)strToken 字符数组，存放构成单词符号的字符串3)GetChar 子程序过程，把下一个字符读入到 ch 中4)GetBC 子程序过程，跳过空白符，直至 ch 中读入一非空白符5)Concat 子程序，把ch中的字符连接到 strToken6)IsLetter和 IsDisgital 布尔函数，判断ch中字符是否为字母和数字7) Reserve 整型函数，对于 strToken 中的字符串查找保留字表，若它是保留字则给出它的编码，否则回送08) Retract 子程序，把搜索指针回调一个字符位置9)InsertId 整型函数，将strToken中的标识符插入符号表，返回符号表指针10)InsertConst 整型函数过程，将strToken中的常数插入常数表，返回常数表指针。8一个词法分析器的例子(多看看、了解吧)：int code, value;strToken := “ ”;/*置strToken为空串*/GetChar(); GetBC();if (IsLetter()beginwhile (IsLetter() or IsDigit()beginConcat(); GetChar(); endRetract();code := Reserve();if (code = 0)beginvalue := InsertId(strToken);return ($ID, value);endelsereturn (code, -);endelse if (IsDigit()beginwhile (IsDigit()beginConcat( ); GetChar( );endRetract();value := InsertConst(strToken);return($INT, value);endelse if (ch =) return ($ASSIGN, -);else if (ch =+) return ($PLUS, -);else if (ch =*)beginGetChar();if (ch =*) return ($POWER, -);Retract(); return ($STAR, -);endelse if (ch =;) return ($SEMICOLON, -);else if (ch =() return ($LPAR, -);else if (ch =) return ($RPAR, -);else ProcError( );/* 错误处理*/3.3正规表达式和有限自动机1. 正规集与正规式a. 正规式与正规集的递归定义（见课本P46，47）b. 若两个正规式所表示得正规集相同，则二者等价。2. 确定有限自动机（DFA）a. 确定有限自动机的定义。（课本P47）b. DFA可以表示为状态转换图。假定DFA M含有m个状态和n个输入字符，那么，这个图含有m个状态结点，每个结点顶多含有n条箭弧射出，且每条箭弧用上的不同的输入字符来作标记。c. DFA M所识别的字的全体记为L(M)。d. 对于S*中的任何字a，若存在一条从初态到某一终态的道路，且这条路上所有弧上的标记符连接成的字等于a，则称a为DFA M所识别(接收)3. 非确定有限自动机（NFA）a. 非确定有限自动机的定义。（课本P49）b. NFA 和DFA的区别： （1） 弧上的标记可以是S*中的一个字，而不一定是单个字符； （2 ）同一个字可能出现在同状态射出的多条弧上。c. DFA是NFA的特例。d.替换规则（课本P50图3.7）4. NFA向DFA的变换 课本P51例3.3，课后习题7，12(1)5. 确定有限自动机的化简。具体步骤课本P56,57页课后习题12（b）考试的时候注意题目要求，如果没有明确要求将DFA简化，可不写6. 正规文法与有限自动机得等价性，正规式与有限自动机的等价性。P51 P53 记住结论就可以，证明过程可以不看。第四章知识点总结：1，定义： 语法分析：在词法分析分析出符号串单词后，分析判定程序是否符合语法规则，在整个架构中起到承上启下作用。（图见第四张ppt第二页） 自上而下语法分析：从文法的开始符号出发，向下推导，把句子推出。上下文无关文法的定义： 一个上下文无关文法G是一个四元式 G=(VT，VN，S，P)，其中VT：终结符集合(非空)VN：非终结符集合(非空)，且VT VN=S：文法的开始符号，SVNP：产生式集合(有限)，每个产生式形式为开始符S至少必须在某个产生式的左部出现一次。2，自上而下语法分析基本思想： 它从文法的开始符号出发，反复使用各种产生式，寻找匹配的推导（简单说就是看见类似的往上凑，发现后面错误了就回溯到出错前的一步进行推导）3，消除左递归：（1） 假设文法中有这样的规则：则判定该文法含有直接左递归，要消除它的办法是：将式子右边所有P打头的候选式提取出来，把他们修改成P，P规则右边候选式格式变为P，并且添加空候选式。即，然后在原来P规则右边每个终结符后添加P，即。（2） 间接左递归：如上述文法中S经过3步推到最终会得到Sabc的式子，形成左递归，但是这个左递归并没有直接显示在某一个规则中，称为间接左递归。要消除间接左递归就要求该文法：（1）没有直接左递归；（2）不存在回路。消除一个文法所有左递归的算法在书上70页。4，消除回溯（1）消除回溯关键在于保证：对文法每一个非终结符，都能在面对输入符号时准确指派他的一个候选式去匹配输入串，既不存在模棱两可的选择。（2）First集定义：对任意一个非终结符G，它的所有候选式的第一个终结符或空符号的集合。（3）消除回溯：如果消除后扔存在会导致回溯的候选式存在，就再进行一次提取，直到不存在回溯的候选式存在。5,ll（1）文法（1） follow集定义：紧跟在非终结符A后面的终结符首位或空的集合，叫做A的follow集。（2） LL（1）文法分析条件：1，文法不含任何形式左递归，不含回溯；2，文法中每一个非终结符A对应的任意两个个候选式，不妨设为j1与j2其首个终结符各不相同，即first（j1）first（j2）；3，文法中如果有非终结符假设为A其follow中含有空，则他的first集与follow集不能有交集即，first（A）follow（A）=。6，递归下降分析程序构造（自学）因为这部分内容重要性较低，稍微看看就好，ppt第四章56-75页。7，预测分析程序（1） 对于first集的求法：对于任意一个非终结符A求他的first集时：1，对其候选式首字符进行一次扫描，把其中的终结符或空加入集合；2，寻找剩下的非终结符的first集（即对非终结符进行第一步）加入集合。（2） 对于follow集求法：对于任意一个非终结符A求它的follow集时：1，若其在某一个候选式如AB或Ab中出现，则把其后面的终结符，或者非终结符的first集加入follow集中（若A后表达式可形成空，也归入步骤2）；2，若其在形如E-A中出现则把follow（E）整个加入follow（A）中。（3） 预测分析表构造：在求出first集及follow集后，要构造预测分析表，其步骤为：ps：在手动运算中出错标志可放空白为示。预测分析程序主控程序思想：见书上76-77页。 第五章1. 小题 归约的基本思想（ppt第4张） 自下而上语法分析器的四个动作（ppt第21张） 关于可归约串o 规范归约：句柄（无求法）o 算符优先文法：最左素短语o LR分析法：句柄（通过活前缀来求句柄） 移进归约过程存在的问题（ppt第27张） 关于优先函数o 优先函数存在性不确定：不是所有的文法都存在优先函数o 优先函数唯一性不确定：存在优先函数则必定不唯一 关于LR分析法o LR的含义（ppt第83张）o LR的优缺点（ppt第84张）o LR文法不是二义的，二义文法肯定不会是LR的。o 规范归约的过程中栈内永远不会出现句柄之后的符号o 识别活前缀的本质就是识别句柄 二义性和各种分析法的关系o 每个SLR(1)文法都是无二义的。但也存在许多无二义文法不是SLR(1)的.o LR文法不是二义的，二义文法肯定不会是LR的。 关于LALR文法o 如果文法G是LALR(1)文法，则G可采用LALR(1)分析法。o 如果文法G是LALR(1)文法，则G是无二义性的。o 如果文法G是LALR(1)文法，则G一定是LR(1)。 关于小题部分，上述只是列出了考试概率比较大的几个关键问题，并不能保证100%的概率，如果要保险一点的话请看第5章ppt的旁白部分。2. 大题 关于规范归约o 求短语，直接短语，句柄o 写出移进-归约过程（ppt第25张）（第7章也会用）o 构造某输入串的语法树（ppt第26张） 关于算符优先o 判断是否为算符优先文法（课本133页3题）o 求短语，素短语，最左素短语（ppt第59张）o 求FIRSTVT，LASTVT（ppt第52张）o 构造算符优先表（ppt第52张）o 构造优先函数（ppt第78张）o 应用算符优先文法分析输入串（ppt第67张） 关于LR（0）o 求活前缀（ppt第101张）o 构造识别LR（0）活前缀的DFA（课本134页5题（1）（2） 求文法的所有LR（0）项目 构造文法的项目集规范族（包括GO函数和DFA两种方法）o 判断文法是否为LR（0）文法o 通过LR（0）的DFA构造LR（0）分析表（ppt123张）o 应用LR（0）分析法分析输入串（ppt第126张） 关于SLR（1）o 判断文法是否SLR（1）文法（课本134页5题（3）o 通过LR（0）和FOLLOW集构造SLR（1）分析表（ppt136张）o 通过SLR（1）分析法分析输入串 关于LR（1）o 构造识别LR（1）的DFA（ppt152张）o 判断文法是否为LR（1）文法（课本134页5题（4）o 通过LR（1）文法的DFA构造LR（1）分析表（ppt第154张）o 应用LR（1）分析法分析输入串（ppt第155张） 关于LALR（1）o 通过LR（1）的DFA构造LALR（1）的DFA（ppt第163张）o 判断文法是否为LALR（1）（课本134页5题（4）o 通过LALR（1）的DFA构造LALR分析表（ppt第165张）o 应用LALR（1）分析法输入串第六章属性文法与语法制导翻译属性文法o 综合属性与继承属性定义 P136o VT只有综合属性o 综合属性的值还可以依赖于自己o 树o 语法树&带注释的语法树(语法树结点有值的计算)o 依赖图(通过依赖图看值是否可计算，是否为良定义的文法) 虚拟属性 P140o 树遍历的属性计算方法 P143 能理解自上而下，从左向右 能判断几次扫描可完成o 抽象语法树 P144 操作符和关键字不做为叶节点 与DAG的区别(DAG可以合并重复子树)o s属性文法o 仅含有综合属性(因此自下而上)o 在LR分析基础上，加上语义规则；在具体实现中加上属性值栈 P148L属性文法与自上而下翻译o L属性文法定义(能判断出是否为L属性文法) P150o S属性文法属于L属性文法o 翻译模式将语义规则嵌入到产生式中，语法树中语义规则看成VTo 如何嵌入(如何建立翻译模式) P151 综合属性的计算放在末尾 继承属性的计算放在符号之前o 自上而下翻译o 消除左递归 示例P155（消除左递归翻译模式的改变方式PPT62页） 新增的VN