Monthly Archives: January 2008

计算机性能的高速增长受益于：电路技术的发展，体系结构技术的发展。 ————————————————————————————————————— 从计算机语言的角度，把计算机系统按功能划分成多级层次结构。 层次结构：计算机系统可以按语言的功能划分为多级层次结构，每一层以不同的语言为特征。 ————————————————————————————————————— 语言实现的两种基本技术 翻译：先把N+1级程序全部变换成N级程序后， 再去执行新产生的N级程序，在执行过程中N+1 级程序不再被访问。 解释：每当一条N+1级指令被译码后，就直接 去执行一串等效的N级指令，然后再去取下一 条N+1级的指令，依此重复进行。 解释执行比翻译花的时间多，但存储空间占用较少。 ————————————————————————————————————— 计算机体系结构：程序员所看到的计算机的属性，即概念性结构与功能特性。 按照计算机系统的多级层次结构，不同级程序员所看到的计算机具有不同的属性。 Amdahl提出的体系结构是传统机器级的体系结构。即一般所说的机器语言程序员所看到的传统机器级所具有的属性。 经典计算机体系结构概念的实质：计算机系统中软硬件界面的确定，也就是指令集的设计，该界面之上由软件的功能实现，界面之下由硬件和固件的功能来实现。 透明性：在计算机技术中，对本来存在的事物或属性，从某一角度来看又好像不存在的概念称为透明性。 —————————————————————————————————————

词法分析的任务是：从左至右逐个字符的对源程序进行扫描，产生一个个的单词符号，把作为字符串的源程序改造成为单词符号串的中间程序。 单词符号有：关键字、标识符、常数、运算符和界符这几种类型。 输出的单词符号常常用二元式表示：（单词种别，单词符号的属性值） 单词种别通常用整数编码；对于一个种别内有多个单词的符号，那么还需要给出单词的符号属性信息。 ————————————————————————————————————— 输入和预处理 通常将输入的字符存入缓冲器中，常常还需要将它们进行预处理，去除多余的白字符。 用双缓冲技术可以避免缓冲器的边界打断单词的识别。 单词符号的识别，超前搜索 有的时候需要用超前搜索的技术才能识别某一符号的具体类别。 状态转换图 状态转换图是一张有向图，结点代表状态，状态之间用箭弧链接，上标记可能出现的输入字符。 ————————————————————————————————————— 设计词法分析器的步骤 1. 设计表格（单词符号/种别编码<单词种别>/助记符/内码值<单词符号的属性值>） 2. 画状态转换图 3. 编码 正规式和正规集 假定有字母表Σ (1)ε和Φ都是Σ上的正规式，它们对应的正规集是{ε}和{Φ}。 (2) 任何a属于Σ都是Σ上的正规式，对应的正规集是{a}。 (3) 如果u和v都是Σ上的正规式，它们所表示的正规集为L(u)和L(v)。那么(u|v)、(u.v)、(u)*也都是正规式，他们所表示的正规集为L(u) U L(v)、L(u)L(v)（连接积）、(L(u))*（闭包）。 也就是说，正规式形如ab*，ab(a|b)，a*b*等等，他们所能代表的字符串的集合就是对应的正规集。 正规式的运算顺序为先有*后.再而|。 ————————————————————————————————————— DFA（确定优先自动机）和NFA（非确定优先自动机） 两者都是一个五元式(S,Σ,δ,S0,F) S：有限状态集 Σ：有穷字母表，每一个元素称为一个输入字符 δ：一个映射关系，对于DFA这是一个从S*Σ到S的单值部分映射，对于NFA这是一个从S*Σ*到2S（S的子集的幂集）的映射。 S0是初态，是S的一个元素 F是终态集合，是S的一个子集 ————————————————————————————————————— … Continue reading →

程序语言 一个程序语言是一个记号系统，程序语言主要由语法和语义两个方面定义。 语法包括词法规则和语义规则。词法规则是指单词符号的形成规则；语法规则则规定了如何从单词符号形成更大的结构（语法单位）。 对于一个语言来说，不仅要给出它的词法和语法规则，而且要定义它的单词符号和语法单位的意义。这就是语义问题。语义规则的阐明目前常使用基于属性文法的语法制导翻译方法。 ————————————————————————————————————— 上下文无关文法 文法：描述语言的语法结构的形式规则（即语法规则）。 上下文无关文法所定义的语法范畴（或语法单位）是完全独立于这种范畴可能出现的环境的。（就事论事的考虑问题） 一个上下文无关文法G是一个四元式（VT，VN，S，ρ），其中 VT是一个非空有限集，它的每个元素都称为终结符号。 VN是一个非空有限集，它的每个元素都称为非终结符号。 S是一个非终结符号，成为开始符号。 ρ是一个产生式集合（有限），每个产生式的形式是P→α，其中P属于VN，α属于(VT U VN)*。开始符号S至少必须在某个产生式的左部出现一次。 ————————————————————————————————————— 我们常常用大写字母表示非终结符，小写字母表示终结符，希腊字母表示由非终结符和终结符组成的符号串。 作为描述程序语言的上下文无关文法，我们对它有限制。 (1)    没有任何产生式如同P→P (2)    每个非终结符P都必须有用处。一方面意味着，必须存在含P的句型；也就是从S出发，存在推导；另一方面，必须存在非终结符串γ，使得P经过有限步推导到达γ，也就是P不存在永不终结的回路。 这种有限制的上下文无关文法称为简化了的文法。 ————————————————————————————————————— 直接推出：我们称 当且仅当A→γ且α、β属于(VT U VN)* 。 推导：一个推出的序列成为推导，用 表示经过0步或者多步的推出，用 表示经过1步或者多步的推出。 最左（右）推导：任何一步 都是对α的最左（右）非终结符进行替换的。 ————————————————————————————————————— 句型和句子 假定G是一个文法，S是它的开始符号。如果 ，则称α是一个句型。仅含终结符的句型称为句子。文法G产生的句子的全体是语言，记做L(G)， ————————————————————————————————————— 短语、直接短语、句柄，需要仔细理解 … Continue reading →

编译程序相关的几个概念 翻译程序：把一种语言程序（源语言程序）转换成另一种语言程序（目标语言程序），并且两者在逻辑上等价。 汇编程序：源程序是汇编语言，目标程序是机器语言的翻译程序。 编译程序：源程序是高级语言，目标程序是某种汇编语言或机器语言的翻译程序。 解释程序：将某种高级语言程序作为输入，但不产生目标程序，而是边解释边执行源程序本身。 编译和解释的根本区别是：是否生成目标代码。 ————————————————————————————————————— 诊断编译程序：专门用于帮助程序开发和调试的编译程序 优化编译程序：着重于提高目标代码效率的编译程序 宿主机：运行编译程序的计算机 目标机：运行编译程序产生的目标代码的计算机 可变目标编译程序：不需要重新编译程序中与机器无关的部分就能改变目标机，则这种编译程序称为可变目标编译程序。 ————————————————————————————————————— 编译各个阶段任务 词法分析：输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个的单词（或成为单词符号或符号）。在词法分析中，所依据的是语言的词法规则，描述词法规则的有效工具是正规式和有限自动机。 语法分析：在词法分析基础上，根据语言的语法规则，把词法符号分解成各类语法单位。语法分析所依据的是语言的语法规则，语法规则通常用上下文无关文法描述。 词法分析是一种线性分析，而语法分析是一种层次结构分析。 语义分析与中间代码产生：对于语法分析识别出的各类语法范畴分析其含义，并进行初步翻译生成中间代码。包含两部分工作，首先对各种语法范畴进行静态语义检查；另一方面，进行中间代码的翻译。这一阶段依据的是语言的语义规则，通常用属性文法描述语义规则。 中间代码通常用四元式形式表示。四元式包含算法、左操作数、右操作数和结果四个部分。 优化：对中间代码进行加工变换，以期在最后阶段能产生出更为高效（省时间和空间）的目标代码。主要包括公共子表达式的提取，循环优化，删除无用代码等等。 目标代码生成：把目标代码（或经过优化处理之后）变换成特定机器上的低级语言代码，目标代码可以是绝对代码或可重定位的指令代码或汇编语言代码。而现今，大部分编译程序产生的目标代码是可重定位的指令代码。 ————————————————————————————————————— 编译程序的总体结构 编译程序主要包括：词法分析器、语法分析器、语义分析和中间代码产生器（可选）、优化器（可选）和目标代码生成器五个主要部分和“表格管理”、“出错处理”两个模块。 词法分析器（又称为扫描器），它接收输入的源程序，对源程序进行扫描和分解（词法分析），识别出一个个的单词符号，其输出结果为单词符号。 语法分析器（又称为分析器），对单词符号串进行语法分析（根据语义规则进行推导和规约），识别出程序中的各类语法单位，最终判断输入串是否构成语法上正确的“程序”。 语义分析和中间代码产生器，按照语义规则对语法分析器规约出（或推导出）的语法单位进行语义分析，并把它们翻译成一定形式的中间代码。 优化器对中间代码进行优化处理。 目标代码生成器将中间代码翻译成目标程序。 表格管理模块保持着一系列的表格，登记源程序的各类信息和编译各阶段的进展情况。编译程序各个阶段所产生的中间结果都记录在表格中，所需要的信息也大多从表格中获取，整个编译过程都在不断的和表格打交道。 出错管理程序对出现在源程序中的错误进行处理。如果源程序有错误，编译程序应设法发现错误，将有关错误信息报告给用户。编译程序的各个阶段都有可能发生错误，出错处理程序要对发现的错误进行处理、记录并反映给用户。 ————————————————————————————————————— 编译前端和编译后端 编译前端主要由与源语言有关但与目标机无关的那些部分组成。通常包括词法分析、语法分析、语义分析和中间代码产生和有部分代码优化工作。 编译后段包括编译程序中与目标代码有关的部分，包括与目标机有关的代码优化，以及目标代码的生成等。 ————————————————————————————————————— 遍：对源程序（或其中间形式）从头到尾扫描一次，并进行有关加工处理，生成新的中间形式或最终目标程序，称为一遍。每遍的工作都由从外存上获前一遍的工作结果开始（或源程序），到完成它所包含的有关阶段程序的工作，并把结果记录于外存上为止。 ————————————————————————————————————— 计算题型1：地址的转换 三维数组a[2:5,-2:2,5:7]首地址为100，每个数组元素占4个存储单位，给出a[3,1,6]的地址。 … Continue reading →