编译原理第3章-文法与语言

编译原理
2022/3/23
语言是由句子组成的集合，是由一组符号所构成的集合
➢ 字母表上的一个语言是上的一些符号串的集合 ➢字母表上的每个语言是*的一个子集
例如：字母表 Σ={a,b} ,Σ*={ε,a,b,aa,ab,ba,bb,aaa,aab,…}
集合{ab,aabb,aaabbb,…,anbn,…}
• 看起来有点乱！
编译原理
2022/3/23
没有这个看着“舒服”
句子 → 主语 谓语 主语 → 冠词 形容词 名词 谓语 → 动词 直接宾语 动词 → 助动词 动词原形 直接宾语 → 冠词 名词
冠词 → the 形容词 → gray 助动词 → will 动词原形 → eat 名词 → wolf 名词 → goat
• 语言是字和组合字的规则——结构性描述
– 例：今次课是三日上编译第 – 今日是上第三次编译课
编译原理
2022/3/23
• 程序设计语言(Programming Language)——形式化 的内容提取
– 程序设计语言为组成程序的所有语句的集合 – 程序(Program)：满足语法规则的语句序列 – 语句(Sentence) ：满足语法规则的单词序列 – 单词(Token) ：满足词法规则的字符串
编译原理
2022/3/23
符号串集合的乘积 设A、B为符号串集合，则A和B的乘积定义 为：AB＝{ xy |x∈A,y∈B}
例如，A＝{a,b}，B={c,d}
则AB={ac,ad,bc,bd}
编译原理
2022/3/23
符号串集合的幂运算
有符号串集合A，定义A0 ={ε}, A1=A, A2=AA, A3=AAA,…… An＝An-1A=AAn-1 ，n>0
例如，A＝{0,1}，则 A0= {ε} A1= {0,1} A2= {00,01,10,11} A3= {000,001,010,011,100,101,110,111}
编译原理
2022/3/23
符号串集合的闭包运算
设A是符号串集合，定义
A＋＝ A1 ∪ A2 ∪ A3 ∪……∪ An ∪…… 称为集合A的正闭包。
或表示为{w|w∈Σ*且w=anbn,n≥1}为字母表上的一个语
言 集合{a,aa,aaa,…}
或表示为{w|w∈Σ*且w=an,n≥1} 为字
母表上的一个语言
编译原理
2022/3/23
3.3 文法和语言的形式定义
文法是对语言结构的定义与描述。（或称为“语法”）。
<赋值语句>::=<标识符>“=”<表达式>
冠词 → the 形容词 → gray 助动词 → will 动词原形 → eat 名词 → wolf 名词 → goat
编译原理
Variable2022/3/23 Terminal
句子的语法组成
——终结符号集，非终结符号集，语法规则，开始符号
终结符号集VT = {the, gray, wolf, will, eat, goat}
•例
– 变量=表达式 – if 条件 then 语句 – while条件 do 语句 – call 过程名(参数表)
编译原理
2022/3/23
• 描述形式——文法 – 语法——语句 • 语句的组成规则 • 描述方法：BNF范式、语法(描述)图 – 词法——单词 • 单词的组成规则 • 描述方法：BNF范式、正规式
<表达式>::=<表达式>“+”<表达式> | <表达式>“*”<表达式 >
<表达式>::=“(”<表达式>“)” | <标识符> | <整数> | <实数>
如何实现语言结构的形
式化描述？
编译原理
2022/3/23
考虑一个句子——文法要素的提取
分析：The gray wolf will eat the goat
例如x=00，y=11，则xy=0011 对于任意一个符号串s，有εs= sε=s
编译原理
2022/3/23
符号串的幂运算
符号串自身连接n次得到的符号串sn 定义为 ss…ss ，包括n个s，称为符号串的幂运算
s0=ε，s1=s，s2=ss，…… 设s=01，则 s0=ε s1=01 s2=0101 ……
非终结符号集VN = { 句子，主语，谓语，
冠词，形容词，名词 ， 动词 ，直接宾语
，助动词 ，动词原形 }
语法规则集P = {句子 → 主语谓语 ，……}
开始符号S = 句子
编译原理
文法：以有穷的集合刻 画无穷集合的工具。
2022/3/23
定义3.1 文法的形式定义
V＝VN ∪VT 称为文法的字母表
Σ的正闭包+ 表示上的除ε外的所有符号串组成的集合
*{}2......
* {} * 2 3 ......
例：Σ={a,b} Σ*={ε,a,b,aa,ab,ba,bb,aaa,aab,…} Σ+={a,b,aa,ab,ba,bb,aaa,aab,…}
编译原理
2022/3/23
为什么对符号、符号串、符号串集合以及它们的运算感兴趣？
编译原理
2022/3/23
3.1.2 字母表和符号串
符号就是字符不如，对=对{i吗f,e？lse,for,while} 字母表：符号的非空有限集 例：={0，1}
C语言的字母表 A＝{a,b,…,0,1,…,9, +,－,×,_/, ( , ), =… if, else,for...}
符号：字母表中的元素 例： 0，1 符号串：由字母表中的符号组成的任何有穷序列
析！ 成分。
4. 对形式语言的理论有一个初步认识。
编译原理
2022/3/23
教学内容
• 3.1 字母表和符号串的基本概念 • 3.2 文法和语言的形式定义 • 3.3 句型的分析 • 3.4 文法和语言的分类
编译原理
2022/3/23
3.1 语言概述
• 什么是语言 – 自然语言(Natural Language) • 是人与人之间的通讯工具 • 语义(Semantics):环境、背景知识、语气、二 义性——难以形式化 – 计算机语言(Computer Language) • 计算机系统间、人机间通讯工具 • 严格的语法(Grammar)、语义(Semantics) — —易于形式化：严格 – 语言是用来交换信息的工具——功能性描述
A*＝ A0 ∪A＋ 称为集合A的闭包。
例：A={x,y}
A＋＝？{x,y, xx,xy,yx,yy , xxx,xxy,xyx,xyy, ……}
A1
A2
A3
A*＝ ？{ε, x,y, xx,xy,yx,yy , xxx,xxy,xyx,xyy, ……}
Hale Waihona Puke A0 A1A2A3
编译原理
2022/3/23
Σ的闭包* 表示上的一切符号串（包括ε）组成的集合
第3章 文法和语言
教学目标
把阳光剪 成窗纸 贴在心 口你是 我沿途 最美的 风景﹌ 你的温 柔颠覆 我的灵 魂︶ㄣ 巴 黎铁塔下的仰望、一抹夏凉、卡农的 旋律ろ 我们一 起背靠 背看星 星 -七月丶我在 繁花中想你飘落的黄叶、柠檬树下的 阳光。 记住、 你永远 是我的 唯一下 一站 思念 还想念那 年你的 温柔ミ 小世界 里存在 你的身 影▲尽 一生思 念、想 你从今 、以后 浅 怀感伤。流年乱了浮生穿过眼瞳的那 明媚阳 光ゝ路 灯下↘ 你清澈 的眼眸~樱花树 下 那属于我们的回忆想你//只因为你是我 的全部 朝朝暮 暮、只 记得你 的暖戒 不掉丶 对 你的依赖没有你的世界/我不要眼泪告 诉我你 很幸福 、你是 我左心 房的风 景。゜ 漠 颜╮你，我从未忘记。_幸福是灵魂的 一种香 味聆听 ，流星 飞逝的 炫彩那 时的， 温 柔只求曾经拥有微笑在青春中如花绽 放.▼那 一抹忧 郁的蓝 。想念汇集成河想念是 每一年第五个季节重温 那逝去的记忆曾经那些美好的记忆 ╮说过 、要牵 着手一 辈 子。╭ァ回忆ゝ那些往事ゞ听ゝ海的 声音留 守，那 思念思 念如絮 夕阳染 红了天 １ 朵狗尾巴花。忘了说晚安割舍不断的 羁绊ㄅ ◆◇╮逝 爱﹌说 寂寞。 - - 只为他倾心宁 静的分手夜你的快乐 就是我的欢笑心会慢慢接受遗失、爱 情一瞬 间旳回 眸ぅ＇ 伴
文法G[S]=（VN，VT，P，S） VN ：非终结符号集 VT ：终结符号集 P： 产生式或规则的集合 S： 开始符号（识别符号） S∈ VN ，S至少要在 一条规则中作为左部出现
补: 规则P的定义 α :: β 或αβ α∈V+且至少有一个非终结符，而β∈(VN ∪ VT)*
编译原理
2022/3/23
例：0,1, 01, 10, 011，.. 空符号串：无任何符号的符号串，用ε表示 符号串的长度：含有的符号个数|x|=m
编译原理
2022/3/23
符号串的前缀（头）和后缀（尾）: 从符号串s的尾（头）部删去若干个(包括0个)符号之后所 余下的部分称为s的前（后）缀
ε，0，01及011都是符号串011的前缀 ε，1，11及011都是符号串011的后缀
– 表达式加上括号后是表达式
编译原理
2022/3/23
例3-1 算术表达式的文法
考虑用式子表示这个定义 标识符(id) 是表达式 表达式加表达式是表达式 表达式减表达式是表达式 表达式乘表达式是表达式 表达式除表达式是表达式 表达式加上括号后是表达式
E→id E→E + E E→E - E E→E *E E→E / E
若A为某语言的字母表 A＝{a,b,…,0,1,…,9, +,－,×,_/, ( , ), =… if, else,for...}