Daily Archives: 2008年01月11号

程序语言 一个程序语言是一个记号系统，程序语言主要由语法和语义两个方面定义。 语法包括词法规则和语义规则。词法规则是指单词符号的形成规则；语法规则则规定了如何从单词符号形成更大的结构（语法单位）。 对于一个语言来说，不仅要给出它的词法和语法规则，而且要定义它的单词符号和语法单位的意义。这就是语义问题。语义规则的阐明目前常使用基于属性文法的语法制导翻译方法。 ————————————————————————————————————— 上下文无关文法 文法：描述语言的语法结构的形式规则（即语法规则）。 上下文无关文法所定义的语法范畴（或语法单位）是完全独立于这种范畴可能出现的环境的。（就事论事的考虑问题） 一个上下文无关文法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 →