文档介绍：第2章形式语言的基本知识
本章是编译原理课程的理论基础,要求掌握形式语言的基本术语和概念。
掌握文法和语言的定义,文法的二义性与递归性的判断方法及句型的分析方法。
熟练使用文法定义程序设计语言的单词和语法成分。
对形式语言的理论有一个初步认识。
教学目标
Friday, November 10, 2017
字母表和符号串的基本概念
文法和语言的形式定义
句型的分析
文法和语言的分类
PL/0编译程序概述
教学内容
Friday, November 10, 2017
字母表:符号的非空有限集例:={0,1}
字母表和符号串
符号:字母表中的元素例: 0,1
符号串:由字母表中的符号组成的任何有穷序列
例:0,1, 01, 10, 011,..
空符号串:无任何符号的符号串,用ε表示
C语言的字母表
A={a,b,…,0,1,…,9, +,-,×,_/, ( , ), =… if, else,for...}
不对
如={if,else,for,while}
符号就是字符,对吗?
Friday, November 10, 2017
符号串的前缀和后缀:
从符号串s的尾部删去若干个(包括0个)符号之后所余下的部分称为s的前缀
ε,0,01及011都是符号串011的前缀
ε,1,11及011都是符号串011的后缀
符号串集合:若集合A中的一切元素都是某字母表上的符号串,则称A为该字母表上的符号串集合。
例:={a,b,c} A={ a,aa,ac}
Friday, November 10, 2017
符号串的运算
符号串x和y的连接:是把y的符号写在x的符号之后得到的符号串xy
例如x=00,y=11,则xy=0011
对于任意一个符号串s,有εs= sε=s
符号串的连接运算
Friday, November 10, 2017
符号串自身连接n次得到的符号串sn 定义为 ss…ss ,包括n个s,称为符号串的幂运算
s0=ε,s1=s,s2=ss,……
设s=01,则
s0=ε
s1=01
s2=0101
……
符号串的幂运算
Friday, November 10, 2017
设A、B为符号串集合,则A和B的乘积定义为:AB={ xy |x∈A,y∈B}
例如,A={a,b},B={c,d}
则AB=
符号串集合的乘积
{ac,ad,bc,bd}
Friday, November 10, 2017
有符号串集合A,定义A0 ={ε}, A1=A, A2=AA, A3=AAA,…… An=An-1A=AAn-1 ,n>0
例如,A={0,1},则
A0=
A1=
A2=
A3=
符号串集合的幂运算
{ε}
{0,1}
{00,01,10,11}
{000,001,010,011,100,101,110,111}
Friday, November 10, 2017
设A是符号串集合,定义
A+= A1 ∪ A2 ∪ A3 ∪……∪ An ∪……
称为集合A的正闭包。
A*= A0 ∪A+
称为集合A的闭包。
例:A={x,y}
A+=?
A*= ?
{x,y, xx,xy,yx,yy , xxx,xxy,xyx,xyy, ……}
A1 A2 A3
{ε, x,y, xx,xy,yx,yy , xxx,xxy,xyx,xyy, ……}
A0 A1 A2 A3
符号串集合的闭包运算
Friday, November 10, 2017
Σ的闭包*
表示上的一切符号串(包括ε)组成的集合
Σ的正闭包+
表示上的除ε外的所有符号串组成的集合
例:Σ={a,b}
Σ*={ε,a,b,aa,ab,ba,bb,aaa,aab,…}
Σ+={a,b,aa,ab,ba,bb,aaa,aab,…}
Friday, November 10, 2017