第四章语法分析-自顶向下分析技术 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 问题及其解决 • 效率问题 • 对语义的影响 • 语法错误的校正 • 左递归 第四章 语法分析----自顶向下分析技术