编译原理
校验码
奇偶校验
通常用于对少量数据的校验
- 奇校验
将信息数据的各位进行模二加法并作为校验码的称为奇校验。 - 偶校验
将信息数据的各位进行模二加法并取反作为校验码的称为偶校验。 - 海明码
采用多位校验码的方式，可以发现、纠正错误。数据位和校验位必须满足关系式：2校验位-1≥数据位+校验位。码距至少是3。 - 循环冗余校验码
检错能力非常强，但是不能纠错。编码长度(CRC字长)为数据位+校验位
文法
终结符和非终结符
文法格式通常为：ɑ→β，若字符为大写字母，则是非终结符，若字符为小写字母，则是终结符
文法的分类
0 型文法(短语文法)
设G=（VN，VT，P，S），如果它的每个产生式α→β是这样一种结构：α∈(VN∪VT)且至少含有一个非终结符，而β∈(VN∪VT)，则G是 一个0型文法。一个非常重要的理论结果是：0型文法的能力相当于图灵机(Turing)。或者说，任何0型文语言都是递归可枚举的，反之，递归可枚举集必定是一个0型语言。0型文法是这几类文法中，限制最少的一个，所以我们在试题中见到的,至少是0型文法。
1 型文法(上下文有关文法)
此文法对应于线性有界自动机。它是在0型文法的基础上每一个α→β,都有|β|>=|α|。这里的|β|表示的是β的长度。
注意：虽然要求|β|>=|α|，但有一特例：α→ε也满足1型文法。
如有A->Ba则|β|=2,|α|=1符合1型文法要求。反之,如aA->a，则不符合1型文法。
2 型文法(上下文无关文法)
此文法对应于下推自动机。2型文法是在1型文法的基础上,再满足：每一个α→β都有α是非终结符。如A->Ba,符合2型文法要求。大多数程序设计语言的语法规则可以用上下文无关文法描述
如Ab->Bab虽然符合1型文法要求,但不符合2型文法要求，因为其α=Ab，而Ab不是一个非终结符。
3 型文法(正规文法)
此文法对应于有限状态自动机。它是在2型文法的基础上满足:A→α|αB（右线性）或A→α|Bα（左线性）。
如有：A->a,A->aB,B->a,B->cB，则符合3型文法的要求。但如果推导 为:A->ab,A->aB,B->a,B->cB或推导 为:A->a,A->Ba,B->a,B->cB则不符合3型方法的要求了。具体的说，例子 A->ab,A->aB,B->a,B->cB中的A->ab不符合3型文法的定义,如果把后面的ab,改成“一个非终结 符＋一个终结符”的形式（即为aB）就对了。例子A->a,A->Ba,B->a,B->cB中如果把B->cB改为 B->Bc的形式就对了,因为A→α|αB（右线性）和A→α|Bα（左线性）两套规则不能同时出现在一个语法中,只能完全满足其中的一个,才能算 3型文法。
数据流图(Data Flow Diagram，DFD)
在面向数据流的设计方法中，一般把数据流图中的数据流划分为两种类型，一种是变换流，一种是事务流。DFD由数据流、加工、数据存储和外部实体4个要素构成。
编译过程
词法分析
从左到右逐个字符地扫描，从中识别出一个个“单词”符号。“单词”符号是程序设计语言的基本语法单位，如关键字、标识符、常数、运算符和分隔符等。
语法分析
根据语言的语法规则将单词符号序列分解成各类语法单位，比如表达式、语句和程序等。语法规则就是各类语法单位的构成规则。通过语法分析确定整个输入串是否构成一个语法上正确的程序。
语义分析
检查源程序是否包含静态语义错误，并收集类型信息供后面的代码生成阶段使用。只有语法和语义都正确的源程序才能被翻译成正确的目标代码。
语义分析的一个主要工作是进行类型分析和检查。程序语言中的一个数据类型一般包含两个方面的内容：类型的载体及其上的运算。例如：整除取余运算只能对整型数据进行运算，若其运算对象中有浮点数就认为是类型不匹配的错误。静态的语义错误是指编译程序可以发现，动态的语义错误是指源程序虽然能够被编译和执行，但是结果不对，一般是逻辑上的错误。
PV操作
进入临界区时执行P操作（申请），退出临界区时执行V操作（释放）