【软考笔记】7. 程序设计语言与语言处理程序基础

编译与解释

编译过程

词法分析：正规式，有限自动机

1. 词法错误：非法字符 拼写错误

语法分析：根据语言语法规则

1. 语法错误：if endif 不匹配 缺分号等

语义分析：语义检查

1. 语义错误：死循环 除 0

中间代码生成

代码优化

目标代码生成：中间代码转低级语言代码

文法

定义：$G=(V,T,S,P)$

G = ( { a , b } , { S , A } , S , P ) G=(\{a,b\}, \{S,A\},S,P) G=({a,b},{S,A},S,P)
$S\to aAS|a$
$A\to SbA|SS|ba$

1. V：非终结符， { S , A } \{S,A\} {S,A}，可以推出其他符号
2. T：终结符， { a , b } \{a,b\} {a,b}
3. S：起始符，$S$
4. P：产生式，下面两个式子

文法类型

1. 0 型：短语文法：图灵机
2. 1 型：上下文有关文法
3. 2 型：上下文无关文法
4. 3 型：正规文法：有限自动机

语法推导树

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Iznsyx3B-1680779700646)(/assets/image_owtcl5pdh.png)]

上图就是 aabAa 的语法推导树

正规式（重要）和有限自动机

有限自动机

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-l8wSCAXU-1680779700647)(/assets/image_gv38jh68i.png)]

1. 单圈$S$：起始点
2. 双圈$f$：结束
3. [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-NWtoToWu-1680779700648)(/assets/image_huf0t5yg9.png)]
   对应 状态转换函数 $\delta (S,1)=A$，意思是从 S 这个状态加上一个 1 可以转移到 A 状态

如果能从 S 到 f 找到一条路，路上的内容连起来是那个串，说明该串是满足该文法的

正规式

本质是有限自动机的另一种表达形式

如 $(a|b)\ast$

表达式（重要）

前缀表达式（+ab）
中缀表达式（a+b）
后缀表达式（ab+）

主要考表达式直接的转换，如中缀转后缀等

传值与传址（重要）

多种程序语言特点

要会根据描述选语言

1. Fortran 科学计算
2. Pascal 教学
3. C
4. Lisp 人工智能
5. C++
6. Java
7. C#
8. Prolog 逻辑推理