第04章 文法与语法分析(中)

《编译原理》电子教案 韶关学院计算机系程细柱
10
PA自动机：假设产生式[1]Z→A，则可构造如下Z PA自动机：假设产生式[1]Z→A，则可构造如下Z产 自动机 [1]Z→A 生式自动机，并记为PA(Z) PA(Z)。 生式自动机，并记为PA(Z)。
1.0 A 1.1
GA自动机：假设给定文法G的一组PA自动机： GA自动机：假设给定文法G的一组PA自动机： 自动机 PA自动机 PA(A1),…,PA(An)，则按如下方法构造的自动机称为 ),… 文法自动机，记为GA(G). G文法自动机，记为GA(G). PA(S)的初始状态作为GA(G)的初始状态 的初始状态作为GA(G)的初始状态； [1] 将PA(S)的初始状态作为GA(G)的初始状态； 连接各PA自动机； PA自动机 [2] 连接各PA自动机； 把原所有PA(A 的终止状态作为GA(G) GA(G)的终止 [3] 把原所有PA(Ai)的终止状态作为GA(G)的终止 状态。 状态。
• 短语：设S是文法的开始符，αηβ是句型(即有S 短语： 是文法的开始符， 是句型(即有S ⇒*αηβ），如果满足条件： αηβ），如果满足条件： ），如果满足条件 S ⇒* αA β A ⇒+ η 则称η是句型α 的一个短语 短语。 则称η是句型αηβ的一个短语。 • 直接短语（简单短语）：如果满足条件： 直接短语（简单短语）：如果满足条件： ）：如果满足条件 S ⇒* αA β A ⇒ η 则称η是句型α 的一个简单短语 简单短语。 则称η是句型αηβ的一个简单短语。 • 句柄：一个句型可能有多个简单短语，其中最左的 句柄：一个句型可能有多个简单短语，其中最左的 简单短语称之为句柄。 称之为句柄 简单短语称之为句柄。
《编译原理》电子教案
7
韶关学院计算机系程细柱
例：S → aAcBe [1] A → b [2] A → Ab [3] B → d [4] 输入流：abbcde。 输入流：abbcde。 规范推导过程为： 规范推导过程为：
逆过程: 分析栈，输入流) 逆过程:(分析栈，输入流) ( -, abbcde) ⇒(a,bbcde) //a为移入活前缀 a 移入活前缀 ab为 ⇒(ab,bcde) //ab为归约活前缀 (ab ab ⇒(aA,bcde) //aA为移入活前缀 为移入活前缀 ⇒(aAb,cde) //aAb为归约活前缀 (aAb,cde) Ab 为 ⇒(aA,cde) ⇒(aAc,de) //aA为移入活前缀 为移入活前缀 //aAc为移入活前缀 为移入活前缀
《编译原理》电子教案
9
韶关学院计算机系程细柱
设文法G[S]: 例，设文法G[S]: [1] S → aAc [2] A → Abb [3] A → b
1
a
2 b
[3]
A
3 b 4 b
[2]
c
[1]
求归约活前缀集如下： 求归约活前缀集如下： aAc[1] //因为 因为S Abb[2]c[1] aAbb[2] //因为S⇒aAc[1] ⇒aAbb[2]c[1] //因为 因为S b[3]c[1] ab[3] //因为S⇒aAc[1] ⇒ab[3]c[1] 以上结果见上图。 以上结果见上图。
《编译原理》电子教案
2
韶关学院计算机系程细柱
主要内容： 主要内容：
LR的几个基本概念 LR的几个基本概念 识别归约活前缀的识别器 LR(0)分析算法 LR(0)分析算法 SLR(1)分析算法 SLR(1)分析算法
《编译原理》电子教案
3
韶关学院计算机系程细柱
LR的几个基本概念 4.5.1 LR的几个基本概念
《编译原理》电子教案
13
韶关学院计算机系程细柱
• 例：假设G[S]: S→ … , D→aA, A→aB, A→Ba, B 假设G[S]: S→ D→ A→ A→ →b，求close({D→a·A}) 。 close({D→ A}) • 解： close({D→a·A}) ={D→a·A, A→·aB, A→·Ba, close({D→ A}) ={D→ A, A→ aB, A→ Ba, B→·b} b}
《编译原理》电子教案
4
韶关学院计算机系程细柱
例：
E E T T F ( E ) * F i + T F
句型: 句型:(E)*i+F 短语: 短语: 1.(E)*i+F 1.(E)*i+F 2.(E)*i 3.(E) 4. i 5. F 简单短语： 简单短语： (E),i,F 句柄： 句柄：(E)
《编译原理》电子教案
//S为规范前缀 为规范前缀
韶关学院计算机系程细柱
归约活前缀识别器---LR(0)自动机 ---LR(0) 4.5.3 归约活前缀识别器---LR(0)自动机
LR(0)归约活前缀定理：简称派生定理， LR(0)归约活前缀定理：简称派生定理，设增 归约活前缀定理 [0]S′ 则定理内容如下： 广产生式为[0]S 广产生式为[0]S′→S，则定理内容如下： [1] S[0]是LR(0)归约活前缀。 S[0]是LR(0)归约活前缀 归约活前缀。 [p]是LR(0)归约活前缀， [2] 若αAβ[p]是LR(0)归约活前缀，且 归约活前缀 [q]A→ 是产生式， απ[q]也是LR(0) [q]也是 [q]A→π是产生式，则απ[q]也是LR(0) 归约活前缀。 归约活前缀。
A 1.1 1.0 ε ε A a a 2.1 2.2 2.3 ε 2.0 ε b 3.1 3.0
《编译原理》电子教案
12
A 1 a b
2 a 3 A b 4 6 a 5
韶关学院计算机系程细柱
LR(0)项目： A→αβ是产生式，则称A→α•β为 αβ是产生式 A→α•β LR(0)项目：若A→αβ是产生式，则称A→α•β为 项目 LR(0)项目 简称项目），也写作α•β p]形式 项目( ），也写作α•β[ 形式。 LR(0)项目(简称项目），也写作α•β[p]形式。 项目集的投影：假设SS是LR(0)项目集，则称下面 项目集的投影：假设SS是LR(0)项目集， SS 项目集 nextstates(SS,X)为SS关于 的投影集： 关于X nextstates(SS,X)为SS关于X的投影集： nextstates(SS,X)={A→ •β|A→α•Xβ∈S SS,X)={A→α |A→α• nextstates(SS,X)={A→αX•β|A→α•Xβ∈SS, X∈(VT∪VN)} 项目集的闭包：假设IS是LR(0)项目集， 项目集的闭包：假设IS是LR(0)项目集，则称下面 IS 项目集 CLOSURE(IS)为IS的闭包集 的闭包集： CLOSURE(IS)为IS的闭包集： CLOSURE(IS)= IS ∪ {A→•π |B→α β∈CLOSURE(IS) A→π {A→•π |B→α•Aβ∈CLOSURE(IS) A→π∈G}
《编译原理》电子教案
11
韶关学院计算机系程细柱
设文法G[S]: 例，设文法G[S]: [1] Z → A [2] A → aAa [3] A → b
1.0 2.0 3.0
A a b
1.1 2.1 3.1 A 2.2 a 2.3
PA自动机见右上图 GA自动机见左下图 自动机见右上图； 自动机见左下图， 解：PA自动机见右上图；GA自动机见左下图，其 确定化后见右下图： 确定化后见右下图：
goto(IS,E)
T
E→T • T→T • *P P
3
goto(IS,T)
P→(• E) • E→• E+T • E→• T • T→ • T *P T→ • P P→• id • P→• ( E ) •
《编译原理》电子教案
6
韶关学院计算机系程细柱
4.5.2 活前缀
• • • 规范推导： 最右推导。 规范推导：即最右推导。 规范归约：即最左归约。 规范归约： 最左归约。 规范句型： 最右推导导出的句型 也称右句型 导出的句型( 右句型）。 规范句型：用最右推导导出的句型(也称右句型）。
• 规范前缀：若存在规范句型αη，且η是终极符串或空串，则称 规范前缀：若存在规范句型αη， αη 是终极符串或空串， 为规范前缀。 α为规范前缀。 • 活前缀：对个规范前缀α，如果： 活前缀：对个规范前缀α 如果： 不含简单短语（移入型活前缀） [1] 不含简单短语（移入型活前缀） 或 含一个简单短语，但其后没有符号（归约型活前缀） [2] 含一个简单短语，但其后没有符号（归约型活前缀） 则称规范前缀α为活前缀；它表示符号栈中的内容， 则称规范前缀α为活前缀；它表示符号栈中的内容，即输入串 中已被分析过的部分。 中已被分析过的部分。
《编译原理》电子教案
15
韶关学院计算机系程细柱
例：G[s]:E→E+T, E→T, T→ T *P, T→P , P→id , P→ (E) → → → →
0
E→• E+T • E→• T • T→ • T *P T→ • P P→• id • P→• ( E ) • (
5
E
1
E→E• +T •
2
a D→a·A A → ε A→·aB a → ε A→·Ba B → ε B→·b b →
a D→a·A A → A→·aB a → A→·Ba B → a B→·b →
《编译原理》电子教案
14
韶关学院计算机系程细柱
LR(0)项目表示法：有三种模式：A→α β LR(0)项目表示法：有三种模式：A→α·β（产生 项目表示法 式模式）、 β[p]（归约号模式）、[p,i]（ ）、α ）、[p,i] 式模式）、α·β[p]（归约号模式）、[p,i]（坐标 型模式）。 型模式）。 project函数 假设给定项目集IS 函数： IS， project函数：假设给定项目集IS，则： project(IS,X)={A→α•X |A→α• β∈I IS,X)={A→α• α•X project(IS,X)={A→α•Xβ|A→α•Xβ∈IS} 它表示IS IS中 后符号为X 它表示IS中“·”后符号为X的项目集。 后符号为 的项目集。 shift函数 假设给定项目集IS 函数： IS， shift函数：假设给定项目集IS，则： shift(IS)={A→ •β|A→α•Xβ∈I IS)={A→α |A→α• shift(IS)={A→αX•β|A→α•Xβ∈IS} 它表示IS IS中 右移一位所得的项目集。 它表示IS中“·”右移一位所得的项目集。 右移一位所得的项目集 goto函数 假设给定项目集IS 函数： IS， goto函数：假设给定项目集IS，则： goto(IS,X)=close(shift(project(IS,X))) IS,X)=close(shift(project( goto(IS,X)=close(shift(project(IS,X))) 它表示IS状态的X IS状态的 它表示IS状态的X输出边所指向状态的项目集闭 包。