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

第四章语法分析-自顶向下分析技术 4.1引言 42带回溯的自顶向下分析技术 4.3无回溯的自顶向下分析技术 本章小结

4.1 引言 4.2 带回溯的自顶向下分析技术 4.3 无回溯的自顶向下分析技术 本章小结 第四章 语法分析----自顶向下分析技术

第四章语法分析-自顶向下分析技术 4.1引 41.1自顶向下分析技术及识别算法 4.12讨论的前提 4.1.3要解决的基本问题

4.1 引言 4.1.1 自顶向下分析技术及识别算法 4.1.2 讨论的前提 4.1.3 要解决的基本问题 第四章 语法分析----自顶向下分析技术

第四章语法分析-自顶向下分析技术 4.1引言 41.1自顶向下分析技术及识别算法 从推导角度看,自顶向下识别算法是从识别符号出发, 试图构造一个推导,由它推导出与输入符号串相同的符号 串 从语法树角度看,自顶向下分析过程以识别符号为根 结点,试图向下构造一个语法树,其未端结点符号串正好 与输入符号串相同

4.1 引言 4.1.1 自顶向下分析技术及识别算法 从推导角度看，自顶向下识别算法是从识别符号出发， 试图构造一个推导，由它推导出与输入符号串相同的符号 串。 从语法树角度看，自顶向下分析过程以识别符号为根 结点，试图向下构造一个语法树，其末端结点符号串正好 与输入符号串相同。 第四章 语法分析----自顶向下分析技术

第四章语法分析-自顶向下分析技术 4.1引 41.1自顶向下分析技术及识别算法 4.1.2讨论的前提 定理2.7对于上下文无关文法,如果存在句型 X1X2…Xn=>y 则必存在y1、y2、…、yn,使得x;>y;(i=1,2,…,n) 且y=y1y2…yn

4.1 引言 4.1.1 自顶向下分析技术及识别算法 4.1.2 讨论的前提 定理2.7 对于上下文无关文法，如果存在句型 x=x1x2…xn，x1x2…xn=>y 则必存在y1、y2、…、yn，使得xi=>yi (i=1,2,…,n) 且y=y1y2…yn。 第四章 语法分析----自顶向下分析技术 * *

第四章语法分析-自顶向下分析技术 4.1引 41.1自顶向下分析技术及识别算法 4.12讨论的前提 4.1.3要解决的基本问题 U∷=u1|u2

4.1 引言 4.1.1 自顶向下分析技术及识别算法 4.1.2 讨论的前提 4.1.3 要解决的基本问题 U∷=u1｜u2｜…｜un 第四章 语法分析----自顶向下分析技术

第四章语法分析-自顶向下分析技术 42带回溯的自顶向下分析技术 4.2.1基本思想 4.2.2问题及其解决

4.2 带回溯的自顶向下分析技术 4.2.1 基本思想 4.2.2 问题及其解决 第四章 语法分析----自顶向下分析技术

第四章语法分析-自顶向下分析技术 42带回溯的自顶向下分析技术 4.2.1基本思想 G[S]: S∴=aBC B∴:=ib|b C: :=DE FGC D∴=d E∴:eh F∴:≡de G∷=t 输入符号串为x= abdet

4.2 带回溯的自顶向下分析技术 4.2.1 基本思想 G[S]： S∷=aBC B∷=ib｜b C∷=DE｜FG｜c D∷=d E∷=eh F∷=de G∷=t 输入符号串为x=abdet 第四章 语法分析----自顶向下分析技术

第四章语法分析-顶向下分析技术 S 4,2带回溯的自 B 4.2.1基本思想 G[S]: (a) (b) (c) S∴=aBC B∴:=ib|b C: :=DE FGC B C B D∴=d E∴:eh b D E b F F∴:≡de d G∷=t (d) 输入符号串为x= abdet

4.2 带回溯的自顶向下分析技术 4.2.1 基本思想 G[S]： S∷=aBC B∷=ib｜b C∷=DE｜FG｜c D∷=d E∷=eh F∷=de G∷=t 输入符号串为x=abdet 第四章 语法分析----自顶向下分析技术

第四章语法分析-顶向下分析技术 S 4,2带回溯的自 B 4.2.1基本思想 G[S]: (a) (c) S∴=aBC B∴:=ib|b C: :=DE FGC B C B D∴=d E∴:eh b D E b F F∴:≡de d G∷ (d) 输入符号串为x= abdet 回溯:当用某个非终结符号的某个选择去进行匹配而失败时, 删去失败的分支并回头查看输入符号,以便与其他选择 相匹配,这种过程称回溯

4.2 带回溯的自顶向下分析技术 4.2.1 基本思想 G[S]： S∷=aBC B∷=ib｜b C∷=DE｜FG｜c D∷=d E∷=eh F∷=de G∷=t 输入符号串为x=abdet 回溯：当用某个非终结符号的某个选择去进行匹配而失败时， 删去失败的分支并回头查看输入符号，以便与其他选择 相匹配，这种过程称回溯。 第四章 语法分析----自顶向下分析技术

第四章语法分析-自顶向下分析技术 42带回溯的自顶向下分析技术 4.2.1基本思想 4.2.2问题及其解决 效率问题 对语义的影响 ·语法错误的校正 左递归

4.2 带回溯的自顶向下分析技术 4.2.1 基本思想 4.2.2 问题及其解决 • 效率问题 • 对语义的影响 • 语法错误的校正 • 左递归 第四章 语法分析----自顶向下分析技术