4) 开始符号S，其中S∈VN
令G是一个如上所定义的文法，则G=(VT,VN,P,S)
mcy
15
文法举例
例 G1 =({N} , {0，1}, {N→0N, N→1N, N→0, N→1}, N） 其中:非终结符集合： VN ={N} 终结符集合： VT ={0，1} 产生式的集合： P={N→0N，N→1N，N→0，N→1}
mcy
20
3型文法：通常，我们把右线性文法及左线性文法
统称为3型文法或正规文法。 若文法G中任一产生式α→β的形式都为A→aB 或 A→a，其中 A∈VN ，B∈VN ，a∈VT ，则称G 为右线性文法； 类似地，如果G中仅含有形如A→Ba 或 A→a的 产生式，则称G为左线性文法；
mcy
mcy
27
直接推导“”或一步推导 若有v,w满足： v=γαδ, w=γβδ
其中：α→β是文法G的产生式，
γ∈ (VT ∪ VN)*,δ∈ (VT ∪ VN)*
则称v直接推导到w,记作 v w，称w直接归 约到v。 注：直接推导就是产生式规则的一次运用， 即用产生式的右部替换左部。
mcy
mcy
32
4. 句型和句子的定义
定义4 句型和句子:设G=(VN , VT , P , S)是一文 法,且 V=VN∪VT 若S =>*α,α∈V*,则称α为文法G的句型；
若S=>+α,α∈VT*,则称α为文法G的句子；
mcy
33
简单整型算术表达式文法：
exp → exp op exp|(exp)|number op → +|-|* 给出算术表达式（34-3）*42的一个推导，请 列出推导过程中出现的句型和句子。
的终结符、非终结符、开始符号分别为？
mcy
18
3.2 上下文无关文法的形式定义
1.
2. 3. 4. 5. 6. 7. 8.
上下文无关文法(即2型文法)的形式定义 chomsky文法的分类 推导和规约的定义 句型和句子的定义 最左和最右推导 文法定义的语言 递归产生式和递归文法 文法和语言
mcy
19
mcy
2
第三章 上下文无关文法及分析
形式工 3.1 语法分析过程 具 3.2 上下文无关文法的形式定义 3.3 二义性文法
作业
mcy 3
3.1 语法分析过程 语法分析程序的任务：
语法分析以词法分析程序输出的单词序列为输
入，分析源程序的语法结构，判断它是否为相 应程序设计语言的合法程序。 通常语法分析的结果是构造出表示该语法结构 的分析树（parse tree）或语法树(syntax tree)。 语法分析阶段可以确定单词流中违反源语言语 法结构规则的错误。
开始符号为：N
mcy
16
通常情况下，文法只用产生式的集合表示：
G1[N]: 也可写成：
N→0N N→1N N→0 N→1
G1[N]:
N→0N | 1N | 0 | 1
mcy
17
文法G[exp] exp → exp op exp exp →(exp)
exp → number
op → + | - | *
2. chomsky文法的分类
通过对产生式施加不同的限制，chomsky将文法分为四种类型： 0型文法：若文法G中任一产生式α →β ，都有 α ∈(VN∪VT)+，β ∈(VN∪VT)* ，则称G为0型文法 1型文法：若文法G中任一产生式α →β ，都有 α ∈(VN∪VT)+，β ∈(VN∪VT)* |β |≥|α |， 仅仅 S→ε 除外，则称G为1型文法 2型文法：若文法G中任一产生式α →β ，都有α ∈VN， β ∈(VN∪VT)* ，则称G为2型文法，也称为上下文无关文法
mcy
34
算术表达式（34-3）*42的推导： exp exp op exp exp op number exp * number (exp) * number (exp op exp) * number (exp op number) * number (exp - number) * number (number - number) * number
mcy
10
问:下面的语句是否是一个符合上述语法结构的简单句 子？
big elephant ate the peanut. 冠词 形容词 名词 动词 冠词 名词 我们把上述两个字符串中间用一箭头分隔构成的有序 对称为产生式。其中， “ →”表示“由……组成”, “ →”也可以用=，::=，:来代替。
mcy
8
Chomsky文法分为四个层次：0型，1型，2
型和3型文法。
其中2型文法（或上下文无关文法）被证明是程
序设计语言中最有用的。 今天2型语言已代表着程序设计语言语法结构的 标准方式。
mcy
9
Chomsky文法就是用生成方式来描述语言的：语言
中的每个句子可以用严格定义的规则来构造。 文法示例： 简单句子的语法结构可有以下规则表示: <句子>→<主语> <谓语> <主语>→ <冠词> <形容词> <名词> <谓词>→ <动词> <直接宾语> <直接宾语>→<冠词> <名词>
mcy
35
3.2 上下文无关文法的形式定义
1.
2. 3. 4. 5. 6. 7. 8.
上下文无关文法(即2型文法)的形式定义 chomsky文法的分类 推导和规约的定义 句型和句子的定义 最左和最右推导 文法定义的语言 递归产生式和递归文法 文法和语言
mcy
36
5. 最左和最右推导
最左推导 对于文法G[S]: S * 是一个最左推导 是指：在推导过程中的任何一步直接推导α β ， 都是对字符串α 中的最左非终结符进行替换，其中 α 、β 是句型。 简单整型算术表达式文法：
mcy
4
如何来描述一种语言(符号串的集合)？
如果语言是有穷的(只含有有穷个句子)，
可以将句子逐一列出来表示。
如果语言是无穷的，找出语言的有穷表示。
mcy
5
语言的有穷表示有两个途经：
生成方式(文法)：语言中的每个句子可以用
严格定义的规则来构造。 识别方式(自动机)：用一个过程，当输入的 一任意串属于语言时，该过程经有限次计 算后就会停止并回答“是”，若不属于， 要么能停止并回答“不是”，要么永远继 续下去 。
mcy
38
S * 是一个最右推导是指：在 推导过程中的任何一步直接推导α β ，都是 对字符串α 中的最右非终结符进行替换，其中 α 、β 是句型。
最右推导： 最右推导也被称为规范推导。由规范推导所得
的句型称为规范句型。
mcy
39
算术表达式（34-3）*42的最右推导： exp exp op exp exp op number exp * number (exp) * number (exp op exp) * number (exp op number) * number (exp - number) * number (number - number) * number
28
例：G[S]：S→0S1，S→01 直接推导： S 0S1 0S1 00S11 00S11 000S111 000S111 00001111
Байду номын сангаас
mcy
29
推导的定义
若存在v=w0w1 ... wn=w (n>0), 我们用
v=>+w表示一步或多步推导，称v推导出w， 或w归约到v； 若有v=>+w，或v=w，则记为v=>*w，表示 零步或多步推导。
21
例：1型（上下文有关）文法
文法G[S]： S→CD
C→aCA C→bCB AD→aD BD→bD Aa→bD
Ab→bA
Ba→aB Bb→bB C→ε D→ε
mcy
22
例：2型（上下文无关）文法 文法G[S]：S→AB A→BS|0
B→SA|1
mcy
23
例：3型（上下文无关）文法
G[S]： S→0A|1B|0 A→0A|1B|0S B→1B|1|0
作业
mcy 13
3.2 上下文无关文法的形式定义
1.
2. 3. 4. 5. 6. 7. 8.
上下文无关文法(即2型文法)的形式定义 chomsky文法的分类 推导和规约的定义 句型和句子的定义 最左和最右推导 文法定义的语言 递归产生式和递归文法 文法和语言
mcy
14
1. 上下文无关文法(即2型文法)的形式定义： 上下文无关文法是一个四元组(VT , VN , P , S)： 产生式 ① 终结符集合VT 产生式 的左部 的右部 ② 非终结符集合VN(与VT不相交) ③ 产生式或文法规则A→α形成的集合P, 其中A∈VN,α∈(VT∪VN)*
exp → exp op exp|(exp)|number op → +|-|*
mcy
37
算术表达式（34-3）*42的最左推导：
exp exp op exp (exp)op exp (exp op exp)op exp (number op exp)op exp (number - exp)op exp (number - number) op exp (number - number) * exp (number - number) * number
mcy
6
寻求程序设计语言语法结构的形式化描述： 正规表达式：？ Number=digit digit* Digit=0|1|2|3|4|5|6|7|8|9 有穷自动机：？