计算思维 是运用计算机科学的基础概念去求解问题、设计系统和理解人类的行为，它包括 了一系列广泛的计算机科学的思维方法。

翻译程序 是把某一种语言程序(称为源语言程序)等价地转换成另一种语言程序(称为目标语 言程序)的程序。

编译程序 是把某一种高级语言程序等价地转换成另一种低级语言程序(如汇编语言或机器 语言程序)的程序。

解释程序 是把源语言写的源程序作为输入，但不产生目标程序，而是边解释边执行源程序 本身。

词法分析器 ，又称扫描器，输入源程序，进行词法分析，输出单词符号。

语法分析器， 简称分析器，对单词符号串进行语法分析，识别出各类语法单元，最终判断 输入串是否构成语法上正确的“程序”。

遍 就是对源程序或源程序的中间表示从头到尾扫描一次，并作有关的加工处理，生成新的 中间结果或目标程序。

语法 是指这样的一组规则，用它可以形成和产生一个合式的程序。

语义 是指这样的一组规则，用它可以定义一个程序的意义。

所谓 程序 ，本质上说是描述一定数据的处理过程。

作用域 是指一个名字能被使用的区域范围。

文法 是描述语言的语法结构的形式规则（即语法规则）。

标识符 是指由字母或数字组成的以字母为开头的一个字符串。

αAβ 直接推出 αγβ ，即aAβ => aγβ仅当A -> γ是一个产生式，且a，b∈(VT ∪ VN)* 。 如果 ，则我们称这个序列是从a1到an的一个 推导 。若存在一个从a1 到an的推导，则称a1可以推导出an 。

假定G是一个文法，S 是它的开始符号。如果，则a称是一个 句型 。仅含终结符号的句型是 一个 句子 。文法G所产生的句子的全体是一个 语言 ，将它记为 L(G)。

最左推导 ：任何一步a Þ b都是对a中的最左非终结符进行替换。

最右推导 ：任何一步a Þ b都是对a中的最右非终结符进行替换。

用一张图表示一个句型的推导，称为 语法树 。

如果一个文法存在某个句子对应两颗不同的语法树，则说这个 文法是二义的 。

一个 语言是二义性的 ，如果对它不存在无二义性的文法。

执行词法分析的程序称为 词法分析器 。

关键字 是由程序语言定义的具有固定意义的标识符。

输入串一般是放在一个缓冲区中，这个缓冲区称 输入缓冲区 。

不包含任何字符的序列称为 空字 ，记为ε。

∑*的子集U和V的 连接（积） 定义为UV＝{ ab | aÎU & bÎV } 。

令 V*=V0∪V1∪V2∪V3 … ∪ 称V*是V的 闭包 。

记 V＋＝V V* ，称V+是V的 正规闭包 。

若两个正规式所表示的正规集相同，则称这两个正规式 等价 。

对于S*中的任何字a，若存在一条从初态到某一终态的道路，且这条路上所有弧上的标记 符连接成的字等于a，则称a为DFA M 所识别(接收) 。

确定有限自动机(DFA) M是一个五元式  M=(S, S, f, S0, F),其中：

非确定有限自动机(NFA) M是一个五元式M=(S, S, f, S0, F)，其中：

对于任何两个有限自动机M和M’，如果L(M)=L(M’)，则称M与 M’ 等价 。

一个上下文无关文法 G 是一个四元式G=(VT，VN，S，P)，其中

当一个文法满足LL（1）条件时，我们就可以为它构造一个不带回溯的自上而下分析程序， 这个分析程序是由一组递归过程组成的，每个过程对应文法的一个非终结符。这样的一个分 析程序称为 递归下降分析器 。

令G是一个文法，S是文法的开始符号，假定 是文法G的一个句型，如果有 且 则β称是句型 相对于非终结符A的 短语 。特别是，如果有 ,则称b是句型 相对 于规则A->b的 直接短语 。

一个句型的最左直接短语称为该句型的 句柄 。

假定a是文法G的一个句子，我们称序列 是a的一个规范归约，如果 此序列满足：

在形式语言中，最右推导通常被称为 规范推导 。

由规范推导推出的句型称为 规范句型 。

所谓 算符优先分析法 就是定义算符(终结符)之间的某种优先关系，借助于这种关系寻找 “可归约串”和进行归约。

一个文法，如果它的任一产生式的右部都不含两个相继(并列)的非终结符，即不含如下形 式的产生式右部： …QR… 则我们称该文法为 算符文法 。

一个文法G的句型的 素短语 是指这样一个短语，它至少含有一个终结符，并且，除它自身 之外不再含任何更小的素短语。

最左素短语 是指处于句型最左边的那个素短语。

对于一个文法，如果能够构造一张分析表，使得它的每个入口均是唯一确定的，则这个文 法就称为 LR文法 。

一个文法，如果能用一个每步顶多向前检查 k个输入符号的LR分析器进行分析，则这个文 法就称为 LR(k)文法 。

字的前缀 是指字的任意首部，如字abc的前缀有 ，a，ab，abc。

活前缀 是指规范句型的一个前缀，这种前缀不含句柄之后的任何符号。即，对于规范句型 ，β为句柄，如果 ，则符号串 是 的活前缀( 必为终结符 串)。

假若一个文法G的拓广文法G’的活前缀识别自动机中的每个状态(项目集)不存在下述情况：

1) 既含移进项目又含归约项目，

2) 含有多个归约项目

则称G是一个 LR(0)文法 。

每个项目的一般形式是 ，这样的一个项目称为一个 LR(k)项目 。项目中的 称为它的 向前搜索符串(或展望串)

属性文法 （也称属性翻译文法）是在上下文无关文法的基础上，为每个文法符号（终结符 或非终结符）配备若干相关的“值”（称为属性）。这些属性代表与文法符号相关信息，如 类型、值、代码序列、符号表内容等。属性可以进行计算和传递。对于文法的每个产生式都配备 了一组属性的计算规则称为 语义规则 。

在语法树中，一个结点的 继承属性 由其父结点、其兄弟结点和其本身的某些属性确定。

在一棵语法树中的结点的继承属性和综合属性之间的相互依赖关系可以由 依赖图 (有向图) 来描述。

如果一属性文法不存在属性之间的循环依赖关系，那么称该文法为 良定义的 。

所谓 语法制导翻译法 ，直观上说就是为文法中每个产生式配上一组语义规则，并且在语 法分析的同时执行这些语义规则。

一个属性文法称为 L-属性文法 ，如果对于每个产生式 ，其每个语义规则中的每 个属性或者是综合属性，或者是 的一个继承属性且这个继承属性仅依赖于：

(1) 产生式中Xj左边符号X1，X2，…，Xj-1的属性

(2) A的继承属性

一个表达式E的 后缀形式 可以如下定义：

1）如果E是一个变量或常量，则E的后缀式是E自身。

2）如果E是E1 op E2形式的表达式，其中 op是任何二元操作符，则 E的后缀式为E1’E2’op，其中E1’和E2’ 分别为E1 和E2的后缀式。

3）如果E是(E1)形式的表达式，则E1 的后缀式就是E的后缀式。

无循环有向图 (Directed Acyclic Graph，简称DAG)，对表达式中的每个子表达式，DAG中都 有一个结点，一个内部结点代表一个操作符，它的孩子代表操作数，在一个DAG中代表公 共子表达式的结点具有多个父结点。

代码生成 是指把语法分析后或优化后的中间代码变换成目标代码。

绝对指令代码 是指能够立即执行的机器语言代码，所有地址已经定位。

可重新定位指令代码 是指待装配的机器语言模块，执行时，由连接装配程序把它们和某 些运行程序连接起来，转换成能执行的机器语言代码。 汇编指令代码是指尚须经过汇编程序汇编，转换成可执行的机器语言代码。

如果在一个基本块内，四元式i对A定值，四元式j要引用A值，而从i到j之间没有A的其 他定值，那么，我们称j是四元式i的变量A的 待用信息 。

一个过程的 活动 指的是该过程的一次执行 。

过程P一个 活动的生存期 ，指的是从执行该过程体第一步操作到最后一步操作之间的操作 序，包括执行P时调用其它过程花费的时间。

动态链 指向调用该过程前的最新活动记录地址的指针。

静态链 指向静态直接外层最新活动记录地址的指针，用来访问非局部数据。

形式单元 存放相应的实在参数的地址或值。

一个名字能被使用的区域范围称作这个名字的 作用域 。

为了管理过程在一次执行中所需要的信息，使用一个连续的存储块，我们把这样的一个连 续存储块称为 活动记录。

如果在编译时就能够确定一个过程在运行时所需要的存储空间的大小，则在编译时就能够 安排好目标程序运行时的全部数据空间，并能确定每个数据项的单元地址。存储空间的这种 分配方法叫做 静态分配 。

优化 是指对程序进行各种等价变换，使得从变换后的程序出发，能生成更有效的目标代码。 每个流图以基本块为结点 ，如果一个结点的基本块的入口语句是程序的第一条语句，则称 此结点为 首结点 如果在某个执行顺序中，基本块B2紧接在基本块B1之后执行，则从B1到 B2有一条有向边。即，如果有一个条件或无条件转移语句从 B1的最后一条语句转移到B2的 第一条语句；或者在程序的序列中，B2紧接在B1的后面，并且B1的最后一条语句不是一个 无条件转移语句。我们就说B1是B2的 前驱 ，B2是B1的 后继 。

所谓 基本块 ，是指程序中一顺序执行的语句序列，其中只有一个入口和一个出口，入口就 是其中的第一个语句，出口就是其中的最后一个语句。

局限于基本块范围内的优化称为 基本块内的优化 ，或称 局部优化 。

描述计算过程的 DAG 是一种带有下述标记或附加信息的DAG：

1. 图的 叶结点 以一标识符或常数作为标记，代表该变量或常数的值；

2. 图的 内部结点 以一运算符作为标记，表示该结点代表应用该运算符对其后继结点所代表 的值进行运算的结果；

3. 图中各个结点上可能附加一个或多个标识符(称附加标识符)表示这些变量具有该结点所 代表的值。

所谓变量A在某点d的 定值到达 另一点u（或称变量A的定值点d到达另一点u），是指 流图中从d有一通路到达u且该通路上没有A的其它定值。

循环不变运算 是指对四元式A:=B op C,若B和C是常数，或者到达它们的B和C的定值点 都在循环外。

如果循环中对变量I只有唯一的形如I:=I±C的赋值，且其中C为循环不变量，则称I为循环 中的 基本归纳变量 。

如果I是循环中一基本归纳变量，J在循环中的定值总是可化归为 I的同一线性函数，也即 J=C1*I ± C2，其中C1和C2都是循环不变量，则称J是 归纳变量 ，并称它与I同族。

由计算机的机器指令构成的程序。 目标语言可以是机器语言，也可以是汇编语言，或者是其它中间语言，但最终结果必定为机器语言。 3、翻译程序 能够把某一种语言程序（源程序）改造成另一种语言程序（目标程序）将源程序译成逻辑上等价的目标程序的程序。翻译程序有两种工作方式：编译和 解释 。 4、 解释 程序 有些翻译程序在翻译过程中并不产生完整的目标程序... Tutorial 你可以使用任何你想要的软件来实现以下任务（Excel、MATLAB、R、Python等）。但我推荐学习python，也仅给出python的对应提示。 全文 名词解释 皆用英文，建议掌握英文，因为计算机术语的中文翻译很混乱。 准备：认识你的工作区 进入数据分析的准备工作。 Editor（文本编辑器） 一旦面对相对复杂的数据分析任务，text editor就是一个必不可少的工具了，无论你是使用excel的VBA、R的R Script......即使是用手计算:slightly_smiling_face:，你也需要一个“草稿纸”来记录自己的计算思路和过程对吗？——在电脑里，这个草稿纸就是text editor。 任何可以显示纯文本、缩进、换行的东西都可以算作text editor，最简单的就是Windows自带的“记事本” (Notepad)。 但不要小看“纯文本”、“缩进”、“换行”这些看似理所当然的细节，实际上不正确的使用导致的错误可以让代码完全无法运行。 “纯文本”：指UTF-8编码编译的Unicode字符，从一些应用/网站直接复制的不一定符 编译原理 ——常见 名词解释 ，包括 编译原理 课程每一章节重要名词和常见名词的介绍和 解释 。 例如：编译程序是一种程序，它把高级语言编写的源程序翻译成与之在逻辑上等价的机器语言或汇编语言的目标程序。 一个高级语言程序的执行通常分为两个阶段，即编译阶段和运行阶段。如果编译生成的目标程序是汇编语言形式，那么在编译与运行阶段之间还要添加一个汇编阶段。 文法是什么？ 文法就是起描述的元语言，通过元语言可以判断句子结构是否符合规范，也就是说，根据一些规则，来确定编程语言的语法，从而实现编译器的功能，不然编译器怎么知道我们写的程序语句是什么意思呢 语义（Semantics）：单个元素的含义 语法（Syntax）：各个元素之间的组合规律 语用（Pragmatics）：语句和使用者之间的关系 文法是由非终结符（大写字母）和终结符（小写... 翻译程序：是指这样的程序能够把某一种语言程序（源语言程序）转化成另一种语言程序（目标语言），而后者与前者在逻辑上是等价的 编译程序：源语言是诸如Java、C、Ada、Pascal这样的“高级语言”，目标语言是诸如汇编语言的“低级语言”，这样的一个翻译程序就称为编译程序 编译程序的工作一般可以划分为5个阶段：词法分析、语法分许、语义分析及中间代码的生成、优化、目标代码生成编译程序各... 1.编译程序就是翻译程序的一种1.机器语言程序可以直接在计算机上运行，并得到计算结果2.编译程序具有以下几种分类：1.诊断编译程序侧重于对源语言程序的调试核检查2.优化编译程序则侧重于对源语言程序的执行效率的优化3.交叉编译程序：前置知识：运行编译程序的机器称为宿主机，运行机器语言程序的是目标机，一般来说宿主机和目标机是同一台机器但是当宿主机和目标机不是同一台机器，也就是说编译程序编译出不同于他所在的机器（宿主机）的机器代码时，我们称这种为交叉编译程序。 1.期末试卷题型2.考点集锦第一章 绪论第二章 词法分析3.各章例题集锦第一章 ——> 题型一：概念题1. 名词解释 遍：一个编译过程可由一遍、两遍或多遍完成。所谓"遍"，也称作"趟"，是对源程序或其等价的中间语言程序从头到尾扫视并完成规定任务的过程。每一遍扫视可完成上述一个阶段或多个阶段的工作。对于多遍的编译程序，第一遍的输入是用户书写的源程序，最后一遍的输出是目标语言程序，其余是上一遍的输出为下一遍的输入。 符号表：是一种用于语言翻译器(例如编译器和 解释 器)中的数据结构。符号表在编译程序工作的过程中需 一：知识点总结自下而上分析法是从输入串开始，逐步进行”规约“，直至规约到文法的开始符号；或者说，从语法树的末端开始，步步向上”规约“，直至根结。Ⅰ、归约1、短语：令G是一个文法，S是文法的开始符号，假定αβδ是文法G的一个句型，如果有S=*>αAδ，且S=+>β，则称β是句型αβδ相对于非终结符的短语。2、直接短语：特别是，如果有A=>β，则称β是句型αβδ相对于规则的A-&gt...