编译程序/翻译程序：把某一种程序设计语言写的源程序翻译成等价的另一种语言程序的程序
编译：从源语言表示的算法向目标语言表示的算法的等价变换
源程序：被编译的程序
源语言：编写源程序的语言
目标程序：源程序经过编译程序翻译后生成的程序
宿主机/目标机：运行编译程序的计算机
宿主语言/实现语言：编译程序实现的语言
需要编译程序支持的执行过程分为两个阶段：编译阶段和运行阶段
编译阶段对整个源程序进行分析，翻译成等价的目标程序，然后在运行子程序的支持下在目标机上运行
运行子程序是为了支持目标的运行而开发的程序
汇编程序：汇编语言是计算机语言的符号形式。若源程序用汇编语言编写，经翻译生成的是机器语言表示的目标程序，该翻译程序称为“汇编程序”。
编译程序：若源程序用高级语言编写，经翻译加工生成某种形式的目标程序，该翻译程序称为“编译程序”。
解释程序：接收某语言的源程序（或经翻译生成的中间代码程序）直接在机器上解释执行的一类翻译程序
解释执行：逐句地边分析，边翻译并执行。优点：易于查错，在程序执行过程中可以修改程序。
编译执行：将原程序先翻译成一个等价的目标程序，然后再运行此目标程序。分为编译阶段和运行阶段。
并行编译器 优化型编译器 交叉型编译程序 诊断型编译器 可重定向型编译器
任务：对输入的符号串形式的源程序进行最初的加工处理。依次扫描读入的源程序中的每个字符，识别出源程序中有独立意义的源语言单词，用某种特定的数据结构对它的属性予以表示和标注。是一种线性分析。
属性字/记号 (Token)：“单词类型”和“单词值”。单词属性字的数据结构可据不同语言及编译程序实现方案来设计。是单词机器内部表示的一种记号
属性字流
任务：在词法分析基础上，依据源语言的语法规则，对词法分析的结果进行语法检查，并识别出单词符号串所对应的语法范畴。通常将语法分析的结果表示为抽象的分析树或称语法树，是一种层次结构的形式
任务：依据源语言限定的语法规则对语法分析所识别的语法范畴进行语义检查并分析其含义，初步翻译成与其等价的中间代码。
任务：为了改进目标代码的质量。
实质：在不改变源程序语义的基础上对其进行加工变换，以期获得更高效的目标代码。
任务：根据中间代码及编译过程中产生的各种表格的有关信息，最终生成所期望的目标代码程序。
对源程序仅进行结构分析和语义分析的处理看作是分析部分，而将生成翻译代码及进一步对代码优化的处理看作是综合部分。
按照编译器是依赖于对源语言的操作还是依赖于对目标语言的操作，将其分为前端和后端两部分。
中间语言是前端和后端的分界或接口
编译程序在对源程序的分析过程中，需要保留和管理一系列表格，以登记源程序中的数据实体的有关信息和编译各阶段所产生的信息，以益于完成从源程序到目标程序的等价变换。
对源程序中可能存在的错误进行自动检查、分析和报告，并尽可能保障恢复编译。能准确地发现源程序中的错误并能把错误限制在尽可能小的范围里。
对源程序或源程序的中间形式从头到尾扫描一遍，并作有关的分析加工，生成新的源程序的中间形式或生成目标程序，各遍之间通过临时文件相关联。
遍数多的优点是编译系统逻辑结构清晰，可减少对主存容量的要求，各遍程序功能独立，相互联系简单，优化的准备工作充分，但也会带来许多重复性的工作，增加各遍间相互切换、连接的开销。
基本因素：
在实质的编译开始前由编译器调用的独立程序。产生编译器的输入。可以删除注释；进行宏低缓；处理文件包含；根据语言的要求提供扩充语言的附加功能等
编译器和汇编程序经常依赖于连接程序，它将分处于不同目标文件中编译或汇编的代码收集到一个可执行的文件中。连接程序还连接目标程序和所使用的标准库函数的代码，以及连接目标程序和由计算机操作系统提供的资源。连接程序对目标机和操作系统有极大的依赖性。
编译器、汇编程序或连接程序生成的代码往往不能直接执行，这是由于它们对存储器的访问与一个不确定的起始位置相关，这样的代码被看成为可重定位的。装入程序可以处理所有与基地址或起始地址有关的可重定位地址。
调试程序往往与编译程序共存于一个集成开发环境中，它判定被编译的程序执行是否出错。
巴科斯-诺尔范式 (Backus-Naur Form)， 简称BNF。
- < >：表示语法成分
-
$\rightarrow$ ：表示“定义为”或“由......组合成”的含义 或 ::= - |：“或”的含义。表示具有相同左部的产生式规则可用"|"分开
又：符号（字符）集。 字母表是元素的非空有穷集合。字母表中的元素称为该字母表的一个字母。通常用大写希腊字母$\Sigma$或大写英文字母等表示字母表。
例：字母表A={a,b,c,d}, 字母表$\Sigma={0,1}$
已知$\Sigma$是字母表，$\Sigma$上的字符串的集合$\Sigma^*$可递归定义如下：
-
$\epsilon$ ($\epsilon$ 是由$\Sigma$中的0个字符组成的符号，称为空串)$\in$$\Sigma^*$ - 如果$\omega \in \Sigma^$且$a \in \Sigma$ ，那么 $\omega a \in \Sigma^$
-
$\omega \in \Sigma^*$ 当且仅当$\omega$ 由有限步 1. 和 2. 产生
如果某符号串$\omega$中有$m$个字母表中的符号，则称其长度为$m$，表示为$|\omega|=m$。
设$\omega$是一个符号串，把从$\omega$的尾部删去0个或若干个符号之后剩余的部分称为$\omega$的前缀。
类似，从$\omega$的首部删去0个或若干个符号之后剩余的部分称为$\omega$的后缀。
设$\omega=abc$，则$\epsilon, a, ab, abc$都是$\omega$的前缀；而$\epsilon,c,bc,abc$都是$\omega$的后缀。
若$\omega$的前缀（后缀）不是$\omega$自身，则将其称为$\omega$的真前缀（真后缀）。
从一个符号串中删去它的一个前缀和一个后缀之后剩余的部分称为该符号穿的子符号串或子串。
例如，
设$\omega$和$\upsilon$是两个符号串，如果将符号串$\upsilon$直接拼接在符号串$\omega$之后，则称此操作为符号串$\omega$和$\upsilon$的连接，记作$\omega\upsilon$。
例如，$\omega=abc,\upsilon=xyz$，则$\omega\upsilon=abcxyz,\upsilon\omega=xyzabc$。
连接运算是有序的。
设$\omega$是某字母表上的符号串，把$\omega$自身连接$n$次得到符号串$\upsilon$，即$\upsilon=\omega\omega...\omega(n个\omega)$，称$\upsilon$是符号串$\omega$的$n$次幂，记作$\upsilon=\omega^n$
设$\omega$是符号串，则有定义 $$ \begin{align*} \omega^0 &= \epsilon \ \omega^1 &= \omega \ \omega^2 &= \omega^2\omega = \omega\omega^2 = \omega\omega\omega \ ... & \ \omega^n&=\omega^{n-1}\omega=\omega\omega^{n-1}=\underbrace{\omega\omega...\omega}_{n个} \end{align*} $$ 例如，$\omega=abc$，则$\omega^2=abcabc$，$\omega^3=abcabcabc$
设A、B是两个符号串集合，AB表示A与B的乘积，其定义为 $$ AB=\set{\omega\upsilon|(\omega \in A) \and (\upsilon \in B)} $$ 例如，设$A=\set{ab,c}, B=\set{d,ef}$，则$AB=\set{abd,abef,cd,cef}$
注意有$\set{\epsilon}A=A\set{\epsilon}=A,\ \varnothing A=A \varnothing=\varnothing,$其中$\varnothing$为空集。
设A是符号串集合，A与自身的乘积可以用方幂表示。其定义为 $$ \begin{align*} A^0 &= \set{\epsilon} \ A^1 &= A \ A^2 &= AA \ A^3 &= A^2A = AAA\ ... & \ A^n&=A^{n-1}A==\underbrace{AA...A}_{n个} \end{align*} $$ 显然有 $$ A^{i+j} = A^iA^j $$ 例如，$P={ab,x,aby}$，则 $$ P^2=PP=\set{abab,abx,ababy,xab,xx,xaby,abyab,abyx,abyaby} $$ 设$\Sigma$为字母表，显然有 $$ \Sigma^*=\Sigma^0\cup\Sigma\cup\Sigma^2\cup...\cup\Sigma^n\cup... $$
设A为一集合，A的正闭包记作$A^+$，定义为 $$ A^+=A^1\cup A^2\cup ...\cup A^n\cup... $$ $A^$定义为A的自反闭包，显然有 $$ A^=A^0 \cup A^+ = \set{\epsilon} \cup A^+ = A^+ \cup \set{\epsilon} $$ 由定义知，$A^+=A A^*$。
例如，$A=\set{01,10}$，则 $$ \begin{align*} &A^=\set{\epsilon,01,10,0101,1010,0110,1001,010101,101010,......}\ &A^+=\set{01,10,0101,1010,0110,1001,010101,101010,......}\ \end{align} $$
（1）文法
一部文法$G$是一个四元组 $$ G=(V_N,V_T,S,P) $$
-
$V_N$ 为非空有限的非终结符号集，其中的元素称为非终结符或语法变量 -
$V_T$ 为非空有限的终结符号集，其中的元素称为终结符，代表了组成语言的不可再分的基本符号集。$V_T$即字母表$\Sigma$ ==？==
设 V 是文法 G 的符号集，则有： $$ V=V_T \cup V_N， 并且 V_T \cap V_N = \varnothing $$
- S 为文法的开始符号或识别符号，亦称公理，$S \in V_N$. S 代表语言最终要得到的语法范畴。
- P 为产生式集。产生式是按一定格式书写的定义语法范畴的文法规则。
产生式的形式为：
$$
\alpha \rightarrow \beta \quad或 \quad \alpha ::=\beta(\alpha \in V^+，且\alpha中至少包含V_N中的一个元素，\beta\in V^*)
$$
其中
注意，公理 S 必须至少在文法某个产生式的左部出现一次。
描述另一种语言的语言称为元语言，元语言中的符号称为元语言符号。
为了把文法产生式中的符号，例如"$\rightarrow$", "|"等与非终结符和终结符相区别，因此给出元语言。
文法规则描述中的符号"$\rightarrow$", "|", "$<$" 和 "$>$"均为元语言符号。
一般约定大写字母表示非终结符，小写字母表示终结符，产生式集合 P 中第一个产生式的左部为开始符号。
（2）语言
文法用来产生规定字母表上的语言，语言是字符串/句子的集合。
设有文法
相对应：称
设有文法
在推导过程中，总是对字符串中最左（右）边的非终结符进行替换，称为最左（右）推导。最右推导也称为规范推导，规范推导的逆序称为规范归约。
设有文法
设有文法
仅用规范推导得到的句型称为规范句型。
设有文法
设有文法
- 给定文法 G ，能从结构上唯一地确定相应的语言。
- 给定一种语言，能构造其文法，但这种文法不是唯一的，既有
若
在原来BNF的4个元语言符号"$\rightarrow$"("$::=$")，“$<$”，“$>$”，“|”之上，引入三对符号：
- 花括号${t}^m_n$表示字符串 t 的任意次出现，其中下角标 n 表示串 t 重复的最小次数，上角标 m 表示字符串 t 重复的最大次数。省略m，n表示可重复0到任意多次
- 圆括号
$()$ 提取产生式中的公共因子，简化产生式的表示。 - 方括号
$[t]$ ，表示字符串 t 可有可无
文法的语法图由一组图组成，每个图定义了一个非终结符的产生式。每个图都有一个起始点和一个终点，其他节点的标记为文法符号。
终结符用圆形区域表示，非终结符用方形区域表示。起始点和终点之间的穿过其他的非终结符和终结符节点的可能路径定义候选式。
分析树的根节点是文法的开始符号，结点间的父子关系为产生式规则。若叶节点都是由终结符组成，则这些结点组成的符号串为句子。
对一部文法 G， 如果至少存在一个句子，对应两棵（或两棵以上）不同的分析树，则称该句子是二义性的。包含有二义性句子的文法称为二义文法。否则，该文法是无二义性的。
或：若文法中存在某个句子，它有两个不同的最左（规范）推导，则这个文法是二义性的。
