文法和语言的基本知识

一、什么形式化的方法

---

用一套带有严格规定的符号体系来描述问题的方法

二、什么是非形式化的方法

---

对程序设计语言的描述从语法、语义和语用三个方面因素来考虑

所谓语法是对语言结构定义

所谓语义是描述了语言的含义

所谓语用则是从使用的角度去描述语言

三、符号串

---

字母表和符号串

---

字母表

符号串

EX：

={a,b,c},则a,b,ab,ba,……都是上的符号串（两个1都不要）

注意：

①符号串中符号的顺序很重要；如：ab 不等于 ba

②不包括任何符号的符号串称为空串，用表示

EX：={a,b,c,d,……z}。a,b,c……都成为符号

hello，world，def，cout，cin，都是上的符号串

符号串的长度：符号串所包含的个数，设x是一符号串，其长度记为|x|

EX: |hello|=5, |mian|=4, ||=0

四、符号串的运算

---

符号串的连接

设X和Y是符号串，则串XY称为它们的连接

EX：ABC，Y=10A，则XY=ABC10A，YX=10AABC

注意：X=X=X=X

符号串的集合：若集合A中元素都是某字母表上的符号串，则A是上的符号串集合

集合的乘积

设A和B是符号串的集合，则定义AB={XY | X∈A，Y∈B}

EX：A={a，b} B={c，d}，则AB={ac，ad，bc，bd}

注意：A{}={}A=A，{}≠{}＝

符号串的幂运算

EX：设X是符号串，则x自身的连接称为符号串的方幂

如：

符号串集合的幂运算

设A是符号串的集合，则定义={}，=A，=AA，=A

符号串集合的正背包和闭包