32语言和文法 329形式语言鸟瞰 文法G=(Vr,VS,P) ·0型文法:a→B,a,B∈(VN∪V),|a|≥1 1型文法:a|≤B|,但S→E可以例外 ·2型文法:A→B,A∈V,B∈( VNUVT 短语文法、上下文有关文法、上下文无关文 法
3.2 语言和文法 3.2.9 形式语言鸟瞰 • 文法 G = (VT , VN , S, P) • 0型文法：→ b， , b (VN VT ) * , | | 1 • 1型文法：| | |b |，但S → 可以例外 • 2型文法：A → b，AVN , b (VN ∪VT ) * • 短语文法、上下文有关文法、上下文无关文 法
32语言和文法 329形式语言鸟瞰 文法G=(Vr,VS,P) ·0型文法:a→B,a,B∈(VN∪V),|a|≥1 1型文法:a|≤B|,但S→E可以例外 ·2型文法:A→B,A∈V,B∈( V uv) 3型文法:A→dB或4→a,A,B∈VM,a∈Vr 短语文法、上下文有关文法、上下文无关文 法
3.2 语言和文法 3.2.9 形式语言鸟瞰 • 文法 G = (VT , VN , S, P) • 0型文法：→ b， , b (VN VT ) * , | | 1 • 1型文法：| | |b |，但S → 可以例外 • 2型文法：A → b，AVN , b (VN ∪VT ) * • 3型文法：A → aB或A → a，A, BVN , a VT • 短语文法、上下文有关文法、上下文无关文 法
32语言和文法 329形式语言鸟瞰 文法G=(Vr,VS,P) ·0型文法:a→B,a,B∈(VN∪V),|a|≥1 1型文法:a|≤B|,但S→E可以例外 ·2型文法:A→B,A∈V,B∈( V uv) 3型文法:A→dB或4→a,A,B∈VM,a∈Vr 短语文法、上下文有关文法、上下文无关文 法、正规文法
3.2 语言和文法 3.2.9 形式语言鸟瞰 • 文法 G = (VT , VN , S, P) • 0型文法：→ b， , b (VN VT ) * , | | 1 • 1型文法：| | |b |，但S → 可以例外 • 2型文法：A → b，AVN , b (VN ∪VT ) * • 3型文法：A → aB或A → a，A, BVN , a VT • 短语文法、上下文有关文法、上下文无关文 法、正规文法
32语言和文法 例L3={ambn≥1}的上下文有关文法 S→aSBC S→aBC CB→BC aB→)ab bB→)bb bC→bc CC→cc abc的推导过程如下: S→*mn1S(BCn1用S→ a Sbc n-1次 S→+u"(BC 用S→>aBC1次 S→+a"BCn 用CB→>BC交换相邻的CB S→+abBn-1C 用aB→mb1次 S→+abCn 用bB→bbn-1次 S→+ ancoN-1 用bC→bc1次 S→+ anb"cnl 用cC→ccn-1次
3.2 语言和文法 • 例 L3 ＝{a nb nc n | n 1}的上下文有关文法 S → aSBC S → aBC CB → BC aB → ab bB → bb bC → bc cC → cc a nb nc n的推导过程如下： S * a n-1S(BC) n−1 用S → aSBC n-1次 S + a n (BC) n 用S → aBC 1次 S + a nBnCn 用CB → BC交换相邻的CB S + a nbBn−1Cn 用aB → ab 1次 S + a nb nCn 用bB → bb n-1次 S + a nb ncCn-1 用bC → bc 1次 S + a nb nc n 用cC → cc n-1次
33自上而下分析 331自上而下分析的一般方法 例文法S→aCbC→cl|c 为输入串w=acb建立分析树 不能处理左递归
3.3 自上而下分析 3.3.1 自上而下分析的一般方法 • 例 文法 S → aCb C → cd | c 为输入串w = acb建立分析树 S a C b S a C b c d S a C b c 不能处理左递归