自上而下的语法分析面临的问题实现 考虑 回朔 文法的左递归性 S→→Sa
11 自上而下的语法分析面临的问题-实现 考虑 回朔 文法的左递归性 S→Sa
自上而下分析对文法的要求 例文法G[S (1)S→Sa (2)S→b 分析baa是不是文法的句子 按照自上而下的分析思想 选用产生式(1)来推导S→Sa 语法树末端结点最左符号为非终结符,所以选用(1)继续 推导S→Sa→Saa 此时语法树末端结点最左符号仍为非终结符,所以选用(1)继 续推导S→Sa→Sa→Saa 问题—试图用S匹配输入串时,出现:在没有读入任何输入符 号的情况下,又得重新要求S去进行新的匹配 原因一—文法含有左递归, 12
12 自上而下分析对文法的要求 例文法G0 [S]: (1) S→Sa (2) S→b 分析baa是不是文法的句子 按照自上而下的分析思想 选用产生式(1)来推导SSa 语法树末端结点最左符号为非终结符，所以选用（1）继续 推导SSaSaa 此时语法树末端结点最左符号仍为非终结符，所以选用（1）继 续推导SSaSaa Saaa 问题——试图用S匹配输入串时，出现：在没有读入任何输入符 号的情况下，又得重新要求S去进行新的匹配 原因——文法含有左递归
自上而下的语法分析一一左递归规则 G[S]: S→Sa S→b L={a|n≥1} W=baaa s a s a 13
13 自上而下的语法分析－－左递归规则 G[S]: S→Sa S→b L={ban | n≥1} W=baaa S b S S a S a
左递归一关于非终结符P的规则 直接左递归若P→Pa|β a、β∈V*且α、β不以P开头 一般左递归若P→>*Pa S→Aa A→Sb 14
14 左递归 －关于非终结符P的规则 直接左递归 若 P → P α| β α、β ∈V*且α、β不以P开头 一般 左递归 若 P =>* P α S→Aa A→Sb …
自上而下分析的进一步讨论 自上而下分析也称面向目标的分析方法,也就是从 文法的开始符号出发企图推导出与输入的符号串 完全匹配的句子,若能构造出推导则表明输入串 是给定文法的句子,否则表明该输入不是给定文 法的句子。 自上而下分析对文法的要求一文法不能含有左递归 规则。 自上而下分析又可分为确定的和不确定的两种 不确定的分析方法称为带回溯的分析方法,这 种方法实际上是一种穷举的试探方法 确定的分析方法需对文法有一定的限制 15
15 自上而下分析的进一步讨论 自上而下分析也称面向目标的分析方法，也就是从 文法的开始符号出发企图推导出与输入的符号串 完全匹配的句子，若能构造出推导则表明输入串 是给定文法的句子，否则表明该输入不是给定文 法的句子。 自上而下分析对文法的要求－文法不能含有左递归 规则。 自上而下分析又可分为确定的和不确定的两种 不确定的分析方法称为带回溯的分析方法，这 种方法实际上是一种穷举的试探方法 确定的分析方法需对文法有一定的限制