南京工业大学：《计算机编译原理》(第二版) 第五章 语法分析——-自底向上分析技术

第五章语法分析-自底向上分析技术 5.1引言 52简单优先分析技术 53算符优先分析技术 54LR(k)分析技术 本章小结

5.1 引言 5.2 简单优先分析技术 5.3 算符优先分析技术 5.4 LR(k)分析技术 本章小结 第五章 语法分析----自底向上分析技术

第五章语法分析-自底向上分析技术 5.1引 51.1自底向上分析技术及识别算法 51.2讨论的前提 5.1.3基本实现方法

5.1 引言 5.1.1 自底向上分析技术及识别算法 5.1.2 讨论的前提 5.1.3 基本实现方法 第五章 语法分析----自底向上分析技术

第五章语法分析-自底向上分析技术 5.1引 51.1自底向上分析技术及识别算法 基本思想是,从输入符号串出发,在每一分析步对相 应句型中的某个简单短语进行归约。如果最终能归约到识 别符号,则该输入符号串是相应文法的句子,否则就不是。 当句型分析过程中每个分析步都对最左的简单短语进 行直接归约时,自底向上分析技术的两个基本问题可以更 确切地叙述为:如何找出句柄及把此句柄直接归约为哪个 非终结符号

5.1 引言 5.1.1 自底向上分析技术及识别算法 基本思想是，从输入符号串出发，在每一分析步对相 应句型中的某个简单短语进行归约。如果最终能归约到识 别符号，则该输入符号串是相应文法的句子，否则就不是。 当句型分析过程中每个分析步都对最左的简单短语进 行直接归约时，自底向上分析技术的两个基本问题可以更 确切地叙述为：如何找出句柄及把此句柄直接归约为哪个 非终结符号。 第五章 语法分析----自底向上分析技术

第五章语法分析-自底向上分析技术 5.1引 51.1自底向上分析技术及识别算法 51.2讨论的前提 识别过程是从左到右、自底向上地进行的,一般都将采 用规范归约;除了特别指明的以外,每一步总是对句柄 最左的简单短语进行直接归约

5.1 引言 5.1.1 自底向上分析技术及识别算法 5.1.2 讨论的前提 识别过程是从左到右、自底向上地进行的，一般都将采 用规范归约；除了特别指明的以外，每一步总是对句柄—— 最左的简单短语进行直接归约。 第五章 语法分析----自底向上分析技术

第五章语法分析-自底向上分析技术 51引言 511自底向上分析技术及识别算法 51.2讨论的前提 513基本实现方法 采用自底向上分析技术时,通常以移入一归约法为基础。 般地,动作共有4类,即移入、归约、接受与报错。 移入:读入下一个输入符号并把它下推进栈 归约:当栈顶的(部分)符号串形成一个句柄时,对此句柄进行直接归约; 接受:当识别程序发现栈中除了栈底标志符号#外仅有识别符号,而输 入也已到达右端#,则接受; 报错:当识别程序察觉一个错误,因此输入符号串不是句子而无法继续 识别工作时,调用一个出错处理子程序进行处理或停止

5.1 引言 5.1.1 自底向上分析技术及识别算法 5.1.2 讨论的前提 5.1.3 基本实现方法 采用自底向上分析技术时，通常以移入-归约法为基础。 一般地，动作共有4类，即移入、归约、接受与报错。 • 移入：读入下一个输入符号并把它下推进栈； • 归约：当栈顶的(部分)符号串形成一个句柄时，对此句柄进行直接归约； • 接受：当识别程序发现栈中除了栈底标志符号#外仅有识别符号，而输 入也已到达右端#，则接受； • 报错：当识别程序察觉一个错误，因此输入符号串不是句子而无法继续 识别工作时，调用一个出错处理子程序进行处理或停止。 第五章 语法分析----自底向上分析技术

例5.1设有文法G[E]:E∷=E+EE*|(E) 步骤 栈 输入 动作 规则 (1) 冰立十立# 移入 (2) #i +立# 归约 (3) #E 立十# 移入 #E* i+i# 移入 (5) #E丬 # 归约 (6) #E*E 十i# 归约 E∴:三凇 (7) #E # 移入 (8) #E+ 1# 移入 (9) #E+i # 归约 E∴:=i (10) #E+E # 归约 E∴:=E+E (11) #E # 接受 移入:读入下一个输入符号并把它下推进栈 归约:当栈顶的(部分)符号串形成一个句柄时,对此句柄进行直接归约; 接受:当识别程序发现栈中除了栈底标志符号#外仅有识别符号,而输 入也已到达右端#,则接受 报错:当识别程序察觉一个错误,因此输入符号串不是句子而无法继续 识别工作时,调用一个出错处理子程序进行处理或停止

• 移入：读入下一个输入符号并把它下推进栈； • 归约：当栈顶的(部分)符号串形成一个句柄时，对此句柄进行直接归约； • 接受：当识别程序发现栈中除了栈底标志符号#外仅有识别符号，而输 入也已到达右端#，则接受； • 报错：当识别程序察觉一个错误，因此输入符号串不是句子而无法继续 识别工作时，调用一个出错处理子程序进行处理或停止。 步骤 栈 输入 动作 规则 （1） （2） （3） （4） （5） （6） （7） （8） （9） （10） （11） # #i #E #E* #E*i #E*E #E #E+ #E+i #E+E #E i*i+i# *i+i# *i+i# i+i# +i# +i# +i# i# # # # 移入 归约 移入 移入 归约 归约 移入 移入 归约 归约 接受 E∷=i E∷=i E∷=E*E E∷=i E∷=E+E 例5.1 设有文法G[E]：E∷=E+E|E*E|(E)|i

第五章语法分析-自底向上分析技术 52简单优先分析技术 521优先关系与优先文法 522简单优先分析技术的实现 523简单优先分析技术的局限性及克服

5.2 简单优先分析技术 5.2.1优先关系与优先文法 5.2.2简单优先分析技术的实现 5.2.3简单优先分析技术的局限性及克服 第五章 语法分析----自底向上分析技术

第五章语法分析-自底向上分析技术 52简单优先分析技术 521优先关系与优先文法 寻找句柄的基本思想 优先关系及其应用 简单优先文法 So…S;S;S:…S;1S;S1…Sn k bI 句柄 句柄 句柄

5.2 简单优先分析技术 5.2.1优先关系与优先文法 • 寻找句柄的基本思想 • 优先关系及其应用 • 简单优先文法 第五章 语法分析----自底向上分析技术

第五章语法分析-自底向上分析技术 52简单优先分析技术 ±S1表示S与S1优先级相同, 521优先关系与优先文法它们同时成为句柄的一部分; k>S1表示S优先级大于S1,也 寻找句柄的基本思想 可称S优先于S1,Sk先于S1成为 优先关系及其应用 句柄的一部分; 简单优先文法 <S1表示Sk优先级小于S,Sk 后于S成为句柄的一部分 k bI 句柄 句柄 句柄

5.2 简单优先分析技术 5.2.1优先关系与优先文法 • 寻找句柄的基本思想 • 优先关系及其应用 • 简单优先文法 第五章 语法分析----自底向上分析技术 Sk±Sl表示Sk与Sl优先级相同， 它们同时成为句柄的一部分； Sk Sl表示Sk优先级大于Sl，也 可称Sk优先于Sl，Sk先于Sl成为 句柄的一部分； Sk Sl表示Sk优先级小于Sl，Sk 后于Sl成为句柄的一部分

第五章语法分析-自底向上分析技术 52简单优先分析技术 521优先关系与优先文法 寻找句柄的基本思想 Z M L a b 优先关系及其应用 Z 简单优先文法 M + a 例设有文法G[]:z∷=bMM∷=(LaL:=Ma)

5.2 简单优先分析技术 5.2.1优先关系与优先文法 • 寻找句柄的基本思想 Z M L a b ( ) • 优先关系及其应用 Z • 简单优先文法 M ± ± L a ± b ± ( ± ) 例 设有文法G[Z]： Z∷=bMb M∷=(L|a L∷=Ma) 第五章 语法分析----自底向上分析技术