程序设计语言与语言处理程序基础
编译过程
文法定义
一个形式文法是一个有序四元组G=(V, T, S, P)，其中：
- V：非终结符。不是语言组成部分，不是最终结果，可理解为占位符。
- T：终结符。是语言的组成部分，是最终结果。$V\cap T=0$
- S：起始符。是语言的开始符号。
- P：产生式。用终结符替代非终结符的规则。形如a→β
语法推导树
一棵语法树应具有以下特征：
- 每个结点都有一个标记，此标记是V的一个符号
- 根的标记是S
- 若一结点n至少有一个它自己除外的子孙，并且有标记A，则A肯定在Vn中:
- 如果结点n的直接子孙，从左到右的次序是结点$n_1,n_2,..n_k$其标记分别是：$A_1,A_2,…,A_k$,那么A→$A_1,A_2…A_k$一定是P中的一个产生式。
例题：文法G= ({a,b}, {S,A},S,P)，其中：S→aAS|a；A→SbA|SS|ba，请构造句型aabAa的推导树。
S→aAS; S→a; A→SbA; A→SS; A→ba
有限自动机
正规式
==D C==
A：S→aA→abS→abaA→ababS→ababaA→ababab
B：S→bB→baS→babB→babaS→bababB→bababa
C：S→aA→abS→abbB→abbaS→abbaaA→abbaab
例题：下图所示为一个有限自动机(其中，A是初态、C是终态)，该自动机可识别(1)。
解析：如果选项路线可以使初态（A）到达终态（C），即为正确。故选C。
==D==
函数调用-传值与传址
各种程序语言特点
- Fortran语言(科学计算,执行效率高)
- Pascal语言(为教学而开发的,表达能力强, Delphi )
- C语言(指针操作能力强，高效)
- Lisp语言(函数式程序语言,符号处理，人工智能)
- C++语言(面向对象，高效)
- Java语言(面向对象,中间代码，跨平台)
- C#语言(面向对象,中间代码,.Net)
- Prolog语言(逻辑推理,简洁性,表达能力,数据库和专家系统)