正则表达式可以对token进行表示
用正则表达式对token进行描述，而后可以很方便有 效的执行（使用DFA）
不能够使用正则表达式来描述程序语言的语法：
原因：正则表达式没有足够的描述能力来描述程序 语言的语法。 例如：嵌套的等价结构
比如括号嵌套
{ (), ()(), (()), (())(), ()(()), (())(()), ((())(())), etc. }
通过调用的惯例，我们可以这么说： G是产生式S → aSbS | ε的文法。从调用惯例中，我 们可以推断出终结符、非终结符和开始符号。
2020/11/13
编译原理
13
推导
设G = <V,Σ,S,→>，是一个上下文无关文法，“直接的推 导”关系 (⇒) 定义为 { <αAγ, αβγ> | A→β }. 例如：
语法分析——上下文无关文法
授课：胡静
目录
上下文无关文法（CFGs） 推导 语法分析树和抽象语法 二义性文法
2020/11/13
编译原理
2
语法分析器所处的法分析的例子
2020/11/13
编译原理
4
语法分析的类比
针对自然语言的语法分析：
识别一个句子是不是符合语法规范&识别每一个成分 的功能。
也就是说，属于L(G)
2020/11/13
编译原理
16
文法和接受器
上下文无关文法的接受器如下：
语法分析器 = CFG接受器，当token流被接受时，输 出相应的推导
例子： LL(k), LR(k), SLR, LALR
2020/11/13
编译原理
17
每个正则语言都是CFL
为每个RE归纳的建立一个CFG
2020/11/13
编译原理
7
先决条件：语言的理论
设Σ是一个有限的符号集合，叫做字母表 Σ* 表示由Σ中的符号组成的所有有限字符串的集 合。 ε表示空字符串。 任意子集L ⊆ Σ* 叫做语言。
2020/11/13
编译原理
8
先决条件：二元关系
如果S1和S2是集合，S1× S2是它们的笛卡尔积，用 集合表示为：{ <s1,s2> | s1 ∈ S1 and s2 ∈ S2} 将S×S 记作 S2 如果S1和S2是集合，那么集合R ⊆ S1× S2 称为S1和 S2的二元关系 如果 <s1,s2> ∈ R，就记作s1Rs2
A 是产生式的左边(lefthand side,LHS) α是产生式的右边( righthand side, RHS)
A→α1|…|αn 表示产生式 A→ α1 ,…, A→ αn
2020/11/13
编译原理
12
简单的文法
<V,Σ,S,→>，其中
V 是 { S }，也就是说，只有一个非终结符S Σ 是 { a, b }，也就是说，有两个终结符 “a”和“b” → 是 {<S,aSbS>, <S,ε>}，也就是说，有两个产生式 S→aSbS和 S→ε
2020/11/13
编译原理
10
上下文无关文法
上下文无关文法是一个四元组表示形式 <V,Σ,S,→>
V是非终结符的有限集合 Σ是终结符的有限集合 S ∈ V 是一个特殊的非终结符，叫做开始符号 →⊆ V × (V ∪ Σ)* 是一个有限关系，叫做产生式。
上下文无关文法简写为 CFG
2020/11/13
2020/11/13
编译原理
5
语法分析总述
达到的目标：确定输入的token流是否符合程序的语 法，如果符合的话，要识别出其结构。 语法分析需要如下条件：
对语法进行描述的方法 一个接受器的机制，来确定输入的token流是否符合 语法描述。 能够还原语法结构的方法。
2020/11/13
编译原理
6
为什么不能用正则表达式
ε
S→ε
a
S→a
R1R2
S → S1S2
R1 | R2
S → S1 | S2
R1 *
其中:
S → S1 S | ε
G1 = 是R1的文法，以符号S1作为开始符号 G2 = 是 R2的文法，以符号S2作为开始符号
2020/11/13
编译原理
18
求和的文法
文法：
S→E+S|E E → number | ( S )
如, α果1 , x...∈, αLn=(Gx,)，其那中么每x一的个推α导i ⇒是α一i+1个当字0≤符i<串n。序我列们S写=α0 作α0⇒α1 ... ⇒ αn。
2020/11/13
编译原理
15
举例
设有文法G，其产生式是S → aSbS | ε 那么
S ⇒ aSbS ⇒ aaSbSbS ⇒ aabSbS ⇒ aabbS ⇒ aabbaSbS ⇒aabbabS ⇒ aabbab
编译原理
11
更多的概念和一些约定
A, B, C, … 用来表示非终结符 a, b, c, … 表示终结符 …, X, Y, Z 可以用来表示终结符或者非终结符 …, w, x, y, z 表示终结符号串 α, β, γ, δ, … 表示由终结符或非终结符构成的符号串 A→α表示产生式<A,α> 在产生式A→α中，
2020/11/13
编译原理
9
先决条件：幂和闭包
如果R1和R2是关系，那么R1 • R2 ，称为R1和R2关系 的组合表示为{ <x,z> | <x,y> ∈ R1 and <y,z> ∈ R2 } 如果R是S×S中的关系，那么
R2是R•R For i>2, Ri = R • Ri-1
R1=R; R0 = { <x,x> | x ∈ S }，这是S上的恒等关系 R+ =R1 ∪ R2 ∪ R3 ∪ …, 这是R上的传递闭包 R* =R0 ∪ R+，这是R上的传递自反闭包
上下文无关语言
设G = <V,Σ,S,→>是CFG，由G所产生的语言表示为 L(G)， L(G) = { x | S ⇒* x }
L(G) = 从开始符号开始，将产生式作为规则改写的 手段，重复的使用，最后得到的终结符号串的集合， 叫做L(G)。
上下文无关语言(CFLs)是由上下文无关文法产生的语 言。
设G的文法的产生式是 S → aSbS | ε 那么
S ⇒ aSbS aSbS ⇒ aaSbSbS aaSbSbS ⇒ aabSbS aabSbS ⇒ aabbS aabbS ⇒ aabbaSbS aabbaSbS ⇒ aabbabS aabbabS ⇒ aabbab
2020/11/13
编译原理
14
