编译原理（第四版）复习 （一）

第一章：编译概述

编译程序：将高级语言所写的源程序翻译成等价的机器语言或汇编语言的目标程序；

解释程序：也是一种翻译程序，将源程序翻译并执行，边解释边执行；

两者的区别：解释程序的执行过程不会生成目标程序；

编译过程的5个阶段：词法分析，语法分析，语义分析及中间代码生成，代码优化，目标代码生成；

第二章：文法和语言的基本知识

文法的自我理解：就是像一个公式一样的规则化；

这章的目标就是如何求：已知文法求语言？已知语言求文法？

∑（西格玛） 代表字母表

（伊姆逊） 代表空字符串

推导用的是=> 规则用的是-> 推导的依据是规则

最右推导叫做规范推导，规范规约就是规范推导的逆过程；

句型和句子：如果起始符号推导出带非终结符的是句型；全是终结符则为句子；

S—>01|0S1

像01，0S1，00S11····就是文法的句型； 01，000111···则是文法的句子；

要求是不是某个文法的句子？ 只要能推导出这个句子就可以证明是~~~~

短语、直接短语、句柄： 看例题中理解

句柄：最左边的直接短语就是句柄；

素短语：就是在短语中最基本的，素短语不能在其他短语中出现；

文法的二义性：一个文法存在某个句子有两种不同的语法树；

消除二义性方法：1.加一些语法的非形式规定，比如*比+先等；2.构造一个等价的无二义性的文法；

0型文法：左侧至少含有一个非终结符； A->AB （无限制文法）

1型文法：左右两侧有一个相容的符号； BA->BC （上下文有关文法）

2型文法：左侧有一个非终结符； A->aA （上下文无关文法）

3型文法；左侧只有一个非终结符，右侧有0个或一个非终结符； A->a A->aA（正规文法）

0>1>2>3