第5章语法分析——自底q.ppt

第5章 语法分析——自底向上分析 5.1 规范推导、规范句型和规范归约 5.2自底向上分析方法的一般过程 5.2自底向上分析方法的一般过程 5.3 LR分析方法 5.3.1 LR分析器逻辑结构 5.3.2 LR分析表的构成 5.3.2 LR分析表的构成 5.3.2 LR分析表的构成 5.3.3 LR分析过程 5.3.3 LR分析过程 5.4 LR(0)分析方法 5.4.1活前缀和可归前缀 5.4.1活前缀和可归前缀 5.4.2 LR(0)项目 第5章 语法分析——自底向上分析 第5章 语法分析——自底向上分析 第5章 语法分析——自底向上分析 第5章 语法分析——自底向上分析 5.4.3 构造识别活前缀的有穷自动机 5.4.3 构造识别活前缀的有穷自动机 5.4.3 构造识别活前缀的有穷自动机 5.4.3 构造识别活前缀的有穷自动机 5.4.3 构造识别活前缀的有穷自动机 5.4.3 构造识别活前缀的有穷自动机 5.4.3 构造识别活前缀的有穷自动机 5.4.3 构造识别活前缀的有穷自动机 5.4.4 LR(0)分析表的构造 5.4.4 LR(0)分析表的构造 5.4.4 LR(0)分析表的构造 5.4.5 LR(0)分析器的工作过程 5.4.5 LR(0)分析器的工作过程 5.4.6 LR(0)文法 5.4.6 LR(0)文法 5.5 SLR(1)分析器 5.4.4 LR(0)分析表的构造 5.5.1 SLR解决方法的基本思想 5.5.1 SLR解决方法的基本思想 5.5.2 SLR(1)分析表的构造 5.5.2 SLR(1)分析表的构造 5.5.2 SLR(1)分析表的构造 5.5.2 SLR(1)分析表的构造 5.5.2 SLR(1)分析表的构造 5.5.2 SLR(1)分析表的构造 5.6 LR(1)分析方法 5.6 LR(1)分析方法 5.6.1 LR(1)项目 5.6.1 LR(1)项目 5.6.2 LR(1)项目集规范族构造算法 5.6.2 LR(1)项目集规范族构造算法 输入符号为)，查动作表5行)列为R1，用A→(A) 归约，(A)出符号栈、A入符号栈，245出状态栈、2为栈顶，查GOTO表2行A列得4，4入状态栈。 4 R1 )# #((A) 02245 6 输入符号为)，查动作表4行)列为S5，5入状态栈，)入符号栈。 S5 )# #(A 024 7 输入符号为#，查动作表5行#列为R1，用A→(A) 归约，(A)出符号栈、A入符号栈，245出状态栈、0为栈顶，查GOTO表0行A列得1，1入状态栈。 1 R1 # #(A) 0245 8 输入符号为#，查动作表1行#列为ACCEPT，接受。 ACC # #A 01 9 输入符号为)，查动作表4行)列为S5，5入状态栈，)入符号栈。 S5 ))# #((A 0224 5 输入符号为)，查动作表3行)列为R2，用A→a 归约，a 出符号栈、A入符号栈，3出状态栈、2为栈顶，查GOTO表2行A列得4，4入状态栈。 4 R2 ))# #((a 0223 4 输入符号为a，查动作表2行a列为S3，3入状态栈，a入符号栈。 S3 a))# #(( 022 3 输入符号为(，查动作表2行(列为S2，2入状态栈，(入符号栈。 S2 (a))# #( 02 2 开始时，0入状态栈，#入符号栈，输入符号为(，查动作表0行(列为S2，2入状态栈，(入符号栈。 S2 ((a))# # 0 1 说明 GOTO ACTION 输入符号串 符号栈 状态栈 步骤 表5.4符号串 (a)的分析过程 项目分成4类：移进项目、归约项目、待约项目和接受项目。一个项目集中可能包含不同类型的项目，但必须满住下面两个条件： 1)不能有移进项目和归约项目并存， 2)不能有多个归约项目并存。 ?如果某一项目集出现移进项目和归约项目并存，我们说该项目集存在“移进-归约冲突”；如果某一项目集出现多个归约项目并存，我们说该项目集存在“归约-归约冲突”。 例如，某项目集为{ S →E.,E →E.+T }，因S →E.是归约项目，而E →E.+T是移进项目，所以该项目集存在“移进-归约冲突”。 如果一个文法的项目集规范族不存在“移进-归约冲突”或“归约-归约冲突”的项目集，那么，称该文法为LR(0)文法，所构造的分析表为LR(0)分析表。 只有LR(0)文法才能构造LR(0)分析表，否则，构造的分析表会出现多重定义。LR(0)文法是一种非常简单的文法，在这种文法的识别活前缀的自动机中，每一个状态对应的项目集都不含冲突项目。然而，很多文法都不是LR(0)文法，如在上一章我们使用的表达式文法就不是