第四章语法分析 语法分析是编译程序的核心部分、语法分析的作用是识别 由词法分析给出的单词符号序列是否是给定文法的正确句子 (程序), 自顶向下分析法也就是从文法的开始符号出发企图推导 出与输入的单词串完全相匹配的句子,若输入串是给定文法 的句子,则必能推出,反之必然出错。自顶向下分析法又可 分为确定的和不确定的两种,确定的分析方法需对文法有 定的限制,但由于实现方法简单、直观,便于手工构造或自 动生成语法分析器,因而仍是目前常用的方法之一。不确定 的方法即带回溯的分析方法(又称回溯法),这种方法实际上 是一种穷举的试探方法,因此效率低,代价高,因而极少使 用
第四章 语法分析 语法分析是编译程序的核心部分、语法分析的作用是识别 由词法分析给出的单词符号序列是否是给定文法的正确句子 （程序）， 自顶向下分析法也就是从文法的开始符号出发企图推导 出与输入的单词串完全相匹配的句子，若输入串是给定文法 的句子，则必能推出，反之必然出错。自顶向下分析法又可 分为确定的和不确定的两种，确定的分析方法需对文法有一 定的限制，但由于实现方法简单、直观，便于手工构造或自 动生成语法分析器，因而仍是目前常用的方法之一。不确定 的方法即带回溯的分析方法(又称回溯法)，这种方法实际上 是一种穷举的试探方法，因此效率低，代价高，因而极少使 用
4.1自顶向下的语法分析 4.1.1自顶向下的分析思想 不确定的自顶向下分析思想主要是带回溯的自上而下的分析 方法,所谓带回溯的自顶而下的分析方法是对任何输入串试 图用一切可能的办法,从文法符号开始符号(根结点)出发, 自上而下,从左到右地为输入串建立分析树。或者说,为输 入串寻找一个最左推导。这种。这种过程本质上是一种试探 过程,是反复使用不同的产生式谋求匹配输入串的过程。 例:设有文法G[S] s→aBCB-bbC→ DE FGc D→)dE→ehF→deGt 假定输入串为 abdet
4.1 自顶向下的语法分析 4.1.1自顶向下的分析思想 不确定的自顶向下分析思想主要是带回溯的自上而下的分析 方法，所谓带回溯的自顶而下的分析方法是对任何输入串试 图用一切可能的办法，从文法符号开始符号（根结点）出发， 自上而下，从左到右地为输入串建立分析树。或者说，为输 入串寻找一个最左推导。这种。这种过程本质上是一种试探 过程，是反复使用不同的产生式谋求匹配输入串的过程。 例：设有文法G[S]: S→aBC B→ib|b C→DE|FG|c D→d E→eh F→de G→t 假定输入串为 abdet
B B S|B|b B B d
显然上述分析法中不能有形如P→Pα的规则,也不能有 对某一非终结符P存在P=+=>Pa,即不能有规则左递归和文法 左递归。 确定的自顶向下分析方法,首先要解决从文法的开始符 号出发,如何根据当前的输入符号(单词符号)唯一地确定 选用哪个产生式替换相应非终结符往下推导,或构造一棵相 应的语法树,现举例说明: 例:若有文法G1[S] s→pAs→qBA→cAdA->a 若输入串W= pccadd,自顶向下的推导过程为 S=>pA=>pcAd=>pccAdd=>pccadd
显然上述分析法中不能有形如P→Pα的规则，也不能有 对某一非终结符P存在P=+=>Pα,即不能有规则左递归和文法 左递归。 确定的自顶向下分析方法，首先要解决从文法的开始符 号出发，如何根据当前的输入符号（单词符号）唯一地确定 选用哪个产生式替换相应非终结符往下推导，或构造一棵相 应的语法树，现举例说明： 例：若有文法G1［S］： S→pA S→qB A→cAd A→a 若输入串W=pccadd,自顶向下的推导过程为 S =>pA=>pcAd=>pccAdd=>pccadd
p A-pA=P=p A c a d ca d ca d cad ca d (d)