软考-软件设计师-程序设计语言

正规式必考，传值与传址考频较高，表达式偶尔考查。

一、编译过程

编译器工作阶段示意图：

注：

（1）中间代码生成和代码优化并不是每个编译器所必须的。

（2）中间代码生成阶段与具体机器无关，起着编译器前端和后端分水岭的作用，所以有助于提高编译程序的可移植性，常用的中间代码是三地址码，其实现方式是四元式。常用的中间代码有后缀式、三元式、四元式、树（图）等。

（3）目标代码生成与具体机器密切相关，分配寄存器是在这个阶段。目标代码生成阶段考虑直接影响目标代码速度的三个问题：1.如何生成较短的目标代码，2.如何充分利用寄存器，减少目标代码访问存储单元的次数，3.如何充分利用计算器指令的特点，提供目标代码质量。

（4）符号表在编译程序工作的过程中需要不断收集、记录和使用源程序中一些语法符号的类型和特征等必要信息，这些信息一般以表格形式存储于系统之中。符号表的使用有时会延续到目标代码的运行阶段。

二、文法的定义以及语法推导树

1文法定义

文法G = ( VN , VT , P , S )，VN和VT都是V，VN为非终结符，VT为终结符，P为产生式，S为开始符。

2文法的类型

3语法推导树

1.每个节点都有一个标记，此标记是V的一个符号。

理解：每个节点都有一个名称，要么是非终结符，要么是终结符。

2.根的标记是S。

理解：根为起始符，即为S。

3.若一结点n至少有一个它自己除外的子孙，并且有标记A，则A肯定在Vn中。

理解：一个节点他有子孙的话，那它A应该就不是终结符，因为终结符不能推出β，A肯定属于Vn。

4.如果结点n的直接子孙，从左到右的次序是结点n1，n2，。。。nk，其标记分别是：A1,A2,…Ak,那么A->A1,A2…，一定是P中的一个产生式。

理解：意思就是上往下推导，父节点推导出子孙节点。

例题如图，一般小写字母代表终结符，S和A是非终结符，意思是可以推出其他符号，后面的S是起始符，P为产生式。产生式包括上面两个式子。

第一个推导式的意思是S可以推出aAS以及S可以推出a，所以S是非终结符，因为可以推出别的符号出来，a则是终结符。

将左边两个式子写成树可以构成右侧的图。

注：程序设计语言的大多数语法现象可用其中的上下文无关文法来描述。

4短语、简单短语、句柄

令G是一个文法，S是文法的开始符号，abc是文法G的一个句型。

短语：如果S经过若干步骤推导出aAc（S=>* aAc）且A经过1步或者多步推出b（A=>+ b），则称b是句型abc相对于非终结符A的短语；

如果有了一棵语法推导树，则这棵推导树上任意一棵子树的叶子结点的序列就是一个短语。

直接短语：如果A直接推出b（A=>b），则称b是句型abc相对于规则A->b的直接短语（简单短语）；

句柄：一个句型的最左直接短语称为该项句型的句柄；

素短语：是个短语，至少含有一个终结符，并且，除它自身之外不再含任何更小的素短语。

最左推导：对句型右部的最左非终结符进行推导。

句型：如果S=>a，其中S是文法G的开始符号，我们可以称a是G的一个句型，当a是一个终结符时，此时这个句型可以称为句子。

句子：仅含终结符的句型。

简单理解：

S经过若干推导，得到aAc，然后A又经过若干推导得到b，则b为A的短语，如上例题图，S=>A，A->a1，所以a1为A的短语。任意一颗子树中，如果根结点经过若干步才推导出了叶子结点，则这些叶子结点组成的序列就是相对于这棵子树的短语。

如果，A只有一个子结点，即A->b，则b是A的直接短语。

最左边的直接短语就是句柄。

上图例题解答：

短语就是任意一个子树的叶子序列，对于A、S子树，a1就是短语，a2、a3也是，对于B子树，∑、b1、b2也是短语。

直接短语就是直接推出的，只有一个子结点，A->a1、S->∑、B->b2、A->a2，这些例子都是。而S->a3则不是直接短语，因为还有另一个子树A->a2，所以不是直接推出。

a1是句柄。

步骤：

（1）找出这棵树的所有子树

（2）找出每一颗子树的短语

第1棵：a1ɛb1b2a2a3

第2棵：ɛb1b2

第3棵：a2a3

第4棵：a1

第5棵：ɛ

第6棵：b1

第7棵：b2

第8棵：a2

（3）找出每一颗子树的直接短语

第1棵：因为这棵树的叶子结点是经过若干步推导出来的没有一步就推导出来的，所以没有直接短语

第2棵：同上

第3棵：同上，虽然a3是直接推导出来的，但是a2不是，所以它们组成的序列不能说是直接短语

第4棵：a1

第5棵：ɛ

第6棵：b1

第7棵：b2

第8棵：a2

（4）从这些直接短语中找那个排在最左边的直接短语，即句柄，这道题的句柄就是a1。

5最左推导和最右推导

最左推导：在最左推导中，总是选择每个句型的最左非终结符号。（画图的时候总是选择左边的非终结符替换左边的非终结符）

最右推导：在最右推导中，总是选择每个句型的最右非终结符号。

例1：文法

S=>AB

A=>a | t

B=>+CD

C=>a

D=>a

最右推导：

S=>AB=>A+CD=>A+Ca=>A+aa=>a+aa

最左推导：

S=>AB=>aB=>a+CD=>a+aD=>a+aa

例2：文法

相应的语法树：（这是最右推导的语法树）

6例题

例1：

例2：已知文法G(S)  

E→E+T | T  

T→T*F| F  

F→(E)| i  

(1) 给出句型 (i+i)*i+i的最左推导及画出语法树；

(2) 给出句型(E+T)*i+F 的短语，素短语和最左素短语。

答：

（1）

E=>E+T=>T+T=>T*F+T=>F*F+T=>(E)*F+T=>(E+T)*F+T=>(T+T)*F+T=>(F+T)*F+T=>(i+T)*F+T=>(i+F)*F+T=>(i+i)*F+T=>(i+i)*i+T=>(i+i)*i+F=>(i+i)*i+i

（2）

短语：i, F,  E+T,  (E+T),  (E+T)*i,  (E+T)*i+F （看语法树，只有垂直的那种线才能单个，比如子树F为i，那种分叉的要都写起，比如子树F为（E+T））

素短语：i,  E+T 

最左素短语：E+T

例3：对于文法G(S)                                                    

S→bMb

M→(L | a

L→Ma)

（1）给出句型b(Ma)b的最左推导及画出语法树；

（2）求上述句型的短语、直接短语和句柄。

答：

（1）S=>bMa=>b(Lb=>b(Ma)b； 

（2）短语:  Ma)，  (Ma)， b(Ma)b 直接短语:  Ma) 句柄:  Ma)

例4：

答：

例5：

（2）句型（T，a，（T））的短语、直接短语、素短语、最左素短语、句柄、活前缀及语法树

短语：a || T，a || （T）|| T，a，（T）|| (T，a，（T）)

直接短语：a ||（T）

素短语：a || （T）

最左素短语：a

句柄：a

活前缀： ||（ ||（T || T ||（T，a

三、有限自动机与正规式

非确定有限自动机（NFA），确定有限自动机（DFA）

1 有限自动机

图注：(S,0)=B表示S通过路径0（可以叫0串，也就是一般题目中让求的串）可以得到B，而S即为初态，f即为终态。

正规式和有限自动机有相互转化的关系。

正规式是有限自动机的另外一种表达形式。

考察形式：设定一个值：如串10或01或001，问是否能够构建这样一条通路？实际上该题即问终态与初态相连，求出其路径，再看其路径值是否与题意相符。

例题：

2 正规式

图注：“ | ”代表“或”，“ * ”代表循环多次，如在或运算中，可以任意选择左式和右式的循环次数，循环次数可以从零到无穷大，该题的答案为D和C。

题中S可推导aA，A推导bS，S推导aA。。。最后A推导b，即ababab

S可推导bB，B推导aS，S推导bB。。。最后B推导a，即bababa

同理C选项也可以被推导，D选项不可以。

第二问：通常用代入法，本题已知第一问几种可能，看第二问的选项哪一个可以表达，选C。

3 非确定有限自动机（NFA），确定有限自动机（DFA）

确定有限自动机（DFA）：对每一个可能的输入只有一个状态的转移

非确定有限自动机（NFA）：对每一个可能的输入有多个状态的转移，接受到输入时从这多个状态中非确定地选择一个。

双圈表示的结点是终态结点。

任何一个NFA都可以转换为DFA。

a(a|b)*a：a开头a结尾，期间的a、b任意排列 [任意个a或（和）任意个b]

如：a aaa a ，a bbb a，a abab a， a abaaaaba a

空串的情况就是他自己开始自己结束，根本不走路径。

有了正规式和有限自动机的基础理论后，就可以构造出编译程序的词法分析模块。

4 正规式与有限自动机之间的转换

（1）有限自动机转正规式

消除结点，用正规式标记弧

（2）正规式转有限自动机

四、表达式（逆波兰式/后序式）

解析逆波兰式的时候仅需要从左到右一次解析，但要考虑括号的优先级。

图注：首先将表达式(括号无需构造)构造为一颗中序表达树，然后再进行下一步运算，该题答案即为D。

后缀式（逆波兰式，就是中间代码的形式之一）：把运算符写在运算对象后面，例如a+b写成ab+

五、函数调用——传值与传址

函数调用的方式分为两种：传值调用和传址调用

概念及特点

1.传值调用：形参取的是实参的值，形参的改变不会导致调用点所传的实参的值发生改变，调用时实际上是把调用的值复制给了一个变量。

2.传址调用(也称引用调用)：形参取的是实参的地址，即相当于实参存储单元的地址引用，因此其值的改变同时就改变了实参的值，调用时实际上是将实参的地址的指针赋值给了变量，因此它的改变会引起实参的改变。

六、各种程序语言的特点

C++

1.特点：既支持面向对象程序设计的概念，也支持原来在c语言中的面向过程程序设计，因此有人称其为混合式的面向对象语言，C++是一门过渡性的语言，它不想C语言那样纯面向过程，又不想Java那样纯面向对象。属于面向对象的编译型语言。

2.适用场景：系统程序的设计，包括嵌入式、桌面式和服务器操作系统的设计，大型软件系统的核心模块的设计，以及各类桌面软件的设计。

Java

1.特点：java是一个纯面向对象的程序设计语言，属于半解释型语言。

2.适用场景：互联网信息系统的开发。

Lisp

1.特点：属于函数式程序设计语言。

2.适用场景：用于符号演算、微分和积分演算，游戏推演、以及人工智能的其他领域

Prolog

1.特点：逻辑编程语言，以特殊的逻辑推理形式回答用户的查询。

2.应用：多用于数据库和专家系统。

Python

1.特点：是一种面向对象、解释型计算机程序设计语言

2.适用场景：快速生成程序的原型，然后对其中有特别要求的部分，用更适合的语言改写，比如3D游戏中的图形渲染模块。

C#

1.特点：是一种面向对象的、运行于.NET Framwork之上的高级程序设计语言。

2.适用场景：由微软公司发布的，主要用于构件.NET Windows网络框架。

汇编语言

汇编语言是面向机器的程序设计语言，使用汇编语言编写的程序，机器不能直接识别，要由一种程序将汇编语言翻译成机器语言，这种起翻译作用的程序叫做汇编程序，汇编程序输入的是用汇编语言书写的源程序，输出的是用机器语言表示的目标程序，汇编语言的指令语句必须具有操作码字段，可以没有操作数字段。

C语言

特点：面向过程的编程语言。

适用场景：

C语言的应用领域分两大块：系统软件开发和应用软件开发。其中C语言最主要用于编写系统软件，编写应用软件不是它的强项。

系统软件开发

>操作系统：UNIX、Windows、Linux。

>驱动程序：比如主板驱动、显卡驱动、摄像头驱动。驱动一般是用C语言和汇编语言写的，C++ 在这方面稍弱。

>数据库：SQL Server、Oracle、MySQL、DB2。

应用软件开发

办公软件：WPS。

>图形图像多媒体：Photoshop、Mediaplayer。

>嵌入式软件开发：嵌入式软件开发说得简单点就是芯片编程，比如单片机和 ARM 上进行的开发都属于嵌入式软件开发。

>游戏开发：2D、3D 游戏。CS 整个游戏的引擎全部是用纯C写的。