软件设计师考试-程序设计语言与语言处理程序基础

1. 编译过程

1.1 词法分析

词法分析器的任务是把源文件的字符流转换成记号流。

词法错误包括：非法字符，关键字或标识符拼写错误。

词法分析阶段会对构成源程序的字符集进行扫描和分解，分析构成程序的字符集由字符按照构造规则构成的符号是否符合程序语言的规定。

1.2 语法分析

语法分析器根据语法规则识别出记号流中的结构（短语，句子），并构造一棵能够正确反映该结构的语法树。语法分析主要检查句子的结构是否符合语法规则，语法错误包括：括号不配对，缺分号等

1.3 语义分析

语义分析：审查源程序是否有语义的错误，当不符合语言规范的时候，程序就会报错。程序设计语言的语义分为静态语义和动态语义，其中静态语义分析方法是语法制导翻译，其基本思想是将语言结构的语义以属性的形式赋予代表此结构的文法符号，而属性的计算以语义规则的形式赋予文法的产生式。

1.4 中间代码生成

中间代码生成是产生中间代码的过程。所谓“中间代码”是一种结构简单、含义明确的记号系统，这种记号系统复杂性介于源程序语言和机器语言之间，容易将它翻译成目标代码。另外，还可以在中间代码一级进行与机器无关的优化。

1.5 代码优化

这个阶段是对前阶段的中间代码进行变换或改造，目的是使生成的目标代码更为高效，即节省时间和空间。

1.6 目标代码生成

目标代码生成，也就是把优化后的中间代码变换或指令代码或汇编代码

1.7 符号表

在程序的编译过程中，符号表的作用是说及、记录源程序中各个符号的必要信息，以辅助语义的正确性检查和代码生成。

2. 文法

2.1 文法定义

当我们要描述一种语言时，需要给出这种语言的所有句子，当句子的数目是有限可数时，就要都列出来；当句子是一个无穷集，也就是无限不可数时，就要给出可以表示它们的结构的描述方法或者说，句子的组成规则。这种规则就是文法。

从形式上用于描述和规定结构的称为文法（或者说语法）

下面是文法的定义：

文法G定义为一个四元组（VN,VT,P,S），其中，VN为非终结符集合，VT终结符集合；P是产生式结合；S称为识别符或开始符号，也是一个非终结符，至少要在一条产生式的左边出现。

出现了几个名词，终结符、非终结符、产生式、识别符/开始符号等。下面具体聊聊这些名词和文法的定义。

VN是非终结符集合，非终结符N指的是可以被拆分的字符或串，它采取递归定义：一个非终结符是由终结符和至少一个非终结符组成的串，相对应的，终结符就是不可拆分的，语言中要用到的字符。所以VN中所存储的是所有的非终结符，VT中存储的是所有的终结符。

简单点讲：终结符就是推导到终结符时，不可再推导下去；而非终结符可以继续推导下去。

2.2 文法类型

上下文无关文法

上下文无关文法是形式语言理论中一种重要的变换文法，用来描述上下文无关语言，在乔姆斯基分层中称为2型文法，由于程序设计语言中的语法基本上都是上下文无关文法，因此上下文无关文法的应用十分广泛。

3. 语法推导树

补充

在编译方式下，编译过程生成的是与源程序等价的目标程序，源程序和编译程序都不再参与目标程序的执行过程。而在解释过程生成的不是源程序的目标程序，而是中间代码。

4. 有限自动机

5. 正规式

文法推导与正规式例题

1.题目1

答案：（1）D （2）C
2.题目2

6. 程序语言基础

6.1 表达式

前缀表达式：前缀表达式是一种没有括号的算术表达式，与中缀表达式不同的是，其将运算符写在前面，操作数写在后面。为纪念其发明者波兰数学家Jan Lukasiewicz，前缀表达式也称为“波兰式”。例如，- 1 + 2 3，它等价于1-(2+3)。

前缀表达式是一种十分有用的表达式，将中缀表达式转换为前缀表达式后，就可以只依靠出栈、入栈两种简单操作完全解决中缀表达式的全部运算。
例如，(a+b)(c+d)转换为,+,a,b,+,c,d。
后面的前缀表达式的运算方式为：如果当前字符(或字符串)为数字或变量，则压入栈内；如果是运算符，则将栈顶两个元素弹出栈外并作相应运算，再将结果压入栈内。当前缀表达式扫描结束时，栈里的就是中缀表达式运算的最终结果。对比中缀运算的步骤，不难发现前缀运算在计算机上的优势。

中缀表达式就是常见的运算表达式，如(3+4)×5-6

后缀表达式：后缀表达式源自于前缀表达式，为了区分前缀和后缀表示，通常将后缀表示称为逆波兰表示；因前缀表示并不常用，所以有时也将后缀表示称为波兰表示。

例题：