2.2符号和符号串p20 n字母表 n符号串 n符号串的运算 ☒D1138
2.2 符号和符号串 p20 n 字母表 n 符号串 n 符号串的运算 11/38
基本概念符号和字母表p20 语言闭包和正闭包p21 n号 符号（元素）可以相互区别的记号：例ab01 n字母表（语言的基本字符集）非空有穷集 u例∑={0,1}二进制数语言的字母表 A={a,b}由符号a和b组成的字母表 u字母表包含语言中所允许出现的一切符号。 语言：某个字母表∑上的符号串集合，是∑*的一个子集。 u例有字母表∑={0,1} 闭包∑*={0,1}*={e,0,1,00,01,10,11,000,001,.} u 则∑*的一个子集{1,11,111,1111，.}是一种语言。 正闭包∑*={0,1}+={0,1,00,01,10,11,000,001，.} 也是∑*的一个子集，是二进制语言。 u 特别空集记为中={}，注意与空串ε、只有空串一个 元素的集合{e}区别。 ☑D12138
基本概念 符号和字母表 p20 语言 闭包和正闭包 p21 n 符号(元素) 可以相互区别的记号: 例 a b 0 1 n 字母表（语言的基本字符集）非空有穷集 u 例∑={0，1} 二进制数语言的字母表 A={a，b} 由符号a和b组成的字母表 u 字母表包含语言中所允许出现的一切符号。 n 语言：某个字母表∑上的符号串集合，是∑*的一个子集。 u 例有字母表∑={0，1} 闭包∑* ={0,1}* ={ε,0,1,00,01,10,11,000,001,.} u 则∑*的一个子集{1,11,111,1111,.}是一种语言。 正闭包∑+ ={0,1}+ = {0,1,00,01,10,11,000,001,.} 也是∑*的一个子集，是二进制语言。 u 特别 空集记为ф ={ }，注意与空串ε、只有空串一个 元素的集合{ε}区别。 12/38
语言的概念 n一种程序设计语言的字母表是该语言的基本字符集合。 uC语言字符集：大小写字母a-zA-Z、数字0-9、空白符、 标点和特殊符号。 {a,b.z,A.Z0,.9,+,*>,.} u C程序是在C基本字符集上按一定规则构成的符号串。 符合词法和语法规则的字符串。 uint mainO int mainO u{integer a,b, int a,b,c; C; c =a b; u a =b$c; u C语言字母表={所有C语言基本字符} u合法吗？ C语言=符合C语言语法规则的符号串集合{所有C语言基本字符}的子集。 如何构造语法规则一文法 章节目录 D13/38
n 一种程序设计语言的字母表是该语言的基本字符集合。 u C语言字符集：大小写字母a-z A-Z、数字0-9、空白符、 标点和特殊符号。 {a,b,.z,A,.Z,0,.9,+,*,>,.} u C程序是在C基本字符集上按一定规则构成的符号串。 符合词法和语法规则的字符串。 int main() { int a, b, c; c = a + b; } C语言字母表 = {所有C语言基本字符} C语言 = 符合C语言语法规则的符号串集合{所有C语言基本字符} *的子集。 如何构造语法规则-文法 uint main() u{ integer a, b, c; u a = b $ c; u} u合法吗？ 章节目录 语言的概念 13/38
2.3文法和语言的形式定义p21 n规则或产生式 n文法的定义 n直接)推导和（直接）归约 n句型和句子 n文法描述的语言 文法的等价性 章节目录 ☑1438
2.3 文法和语言的形式定义 p21 n 规则或产生式 n 文法的定义 n (直接)推导和 (直接)归约 n 句型和句子 n 文法描述的语言 n 文法的等价性 章节目录 14/38
规则或产生式p21 形式：a→BY或a::=B u例如：〈代词>→He u例如：E→E*E ua称为产生式的左部 uB称为产生式的右部 u读作“a定义为B” n举例 uA→a这是关于A的一条规则 u〈标识符〉→〈字母〉 u《字母〉→albl.|z 小节目录 15 国
15 规则或产生式 p21 n 形式：α→β|γ或α::=β u 例如：<代词> → He u 例如：E → E * E u α称为产生式的左部 u β称为产生式的右部 u 读作“α定义为β” n 举例 u A→a 这是关于A的一条规则 u <标识符> →<字母> u <字母> →a|b|.|z 小节目录