中国科学技术大学：《编译原理与技术》课程教学资源（PPT课件讲稿）第3章 语法分析

3.2语言和文法 3.2.9形式语言鸟瞰 ·文法G=(YT,VS,P ·0型文法：ax→B,a,B∈(WUV),la|≥1 ·1型文法：a≤B,但S→ε可以例外 2型文法：A→B,A∈VN,B∈(YNUV) 短语文法、上下文有关文法、上下文无关文 法

3.2 语言和文法 3.2.9 形式语言鸟瞰 • 文法 G = (VT , VN , S, P) • 0型文法：→ b， , b  (VN VT ) * , | |  1 • 1型文法：| |  |b |，但S → 可以例外 • 2型文法：A → b，AVN , b  (VN ∪VT ) * • 短语文法、上下文有关文法、上下文无关文 法

3.2语言和文法 3.2.9形式语言鸟瞰 ·文法G=(YT,VS,P ·0型文法：a-→p,&,B∈(VU,|al≥1 ·1型文法：1a≤B1,但S→ε可以例外 2型文法：A→B,A∈VN,阝∈(YU) 3型文法：A→aB或A→4，A,B∈N,4∈V 短语文法、上下文有关文法、上下文无关文 法

3.2 语言和文法 3.2.9 形式语言鸟瞰 • 文法 G = (VT , VN , S, P) • 0型文法：→ b， , b  (VN VT ) * , | |  1 • 1型文法：| |  |b |，但S → 可以例外 • 2型文法：A → b，AVN , b  (VN ∪VT ) * • 3型文法：A → aB或A → a，A, BVN , a VT • 短语文法、上下文有关文法、上下文无关文 法

3.2语言和文法 3.2.9形式语言鸟瞰 ·文法G=(YT,VS,P ·0型文法：a→B,a,B∈(WUV),|a|≥1 ·1型文法：1a≤B1,但S→ε可以例外 2型文法：A→B,A∈VN,阝∈(VUV) 3型文法：A→aB或A→4，A,B∈VN,M∈YT 短语文法、上下文有关文法、上下文无关文 法、正规文法

3.2 语言和文法 3.2.9 形式语言鸟瞰 • 文法 G = (VT , VN , S, P) • 0型文法：→ b， , b  (VN VT ) * , | |  1 • 1型文法：| |  |b |，但S → 可以例外 • 2型文法：A → b，AVN , b  (VN ∪VT ) * • 3型文法：A → aB或A → a，A, BVN , a VT • 短语文法、上下文有关文法、上下文无关文 法、正规文法

3.2语言和文法 ·例L3={ab"cmn≥1}的上下文有关文法 S→aSBC S→BC CB→BC aB→ab bB-→bb bC-→bc cC-→cC a"b"cn的推导过程如下： S→*a-lS(BC)n-1 用S→aSBC n-1次 S→+an(BC)A 用S→aBC1次 S→+aBnCn 用CB→BC交换相邻的CB S→+abBn-1C 用aB→ab 1次 S→+anbnCn 用bB→bb n-1次 S→+abncCn--l 用bC→bc 1次 S→+anbnch 用cC→cc n-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次

3.3自上而下分析 3.3.1自上而下分析的一般方法 ·例文法S→aCbC→cdc 为输入串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 不能处理左递归