例如，有产生式： 语句->if条件then语句else语句 |while条件do语句 |begin语句表end 若要寻找一个语句，那么关键字if,while,begin就 提示我们哪一个替换式是仅有可能成功的替换式。 >抽象地看问题： 若要求不得回湖，文法G(当然G不含左递归) 的必要条件是什么，也即对文法有什么要求？
例如，有产生式： 语句->if条件 then 语句 else 语句 | while 条件 do 语句 |begin 语句表 end 若要寻找一个语句，那么关键字if，while，begin就 提示我们哪一个替换式是仅有可能成功的替换式。 ➢抽象地看问题： 若要求不得回溯，文法G（当然G不含左递归） 的必要条件是什么，也即对文法有什么要求？
若由a;吉a…,选该a必中，但若心吉a…, 就会导致无法百发百中，解决办法是对文法本身提 出要求：“不会出现以上情况”，把这些阐明清楚 是用一个FIRST(a)。 ●定义FIRST(): FIRST(a)=aaa.,aEVT} 若a当e,规定e∈FIRST(a)
若由αi a…，选该α必中，但若αj a… ， 就会导致无法百发百中，解决办法是对文法本身提 出要求：“不会出现以上情况”，把这些阐明清楚 是用一个FIRST(α)。 ⚫定义FIRST(α)： FIRST(α)={ a | α a…,a∈VT } 若α ε，规定ε∈FIRST(α)
●定理 若一个A∈VN,就有许多FIRST(a),如果A的 任何两个候选式a和j,均有 FIRST(a)∩FIRST(j)=φ 意味着，A的每一候选式心推导后所得的字符串 第一个VT均不同。 于是，对输入符号a,如果a∈FIRST(ai),则a not E FIRST(aj),(j≠i),因此，对A的展开无疑应 选候选式i,才有可能命中
⚫定理 若一个 A∈VN，就有许多FIRST(αi )，如果A的 任何两个候选式αi和αj，均有 FIRST(αi ) ∩ FIRST(αj ) = φ 意味着，A的每一候选式α推导后所得的字符串 第一个VT均不同。 于是，对输入符号a，如果a∈FIRST(αi )，则a not∈FIRST(αj )，( j≠i )，因此，对A的展开无疑应 选候选式αi ，才有可能命中
●消除回湖目的： 非终结符A的所有侯选式的首符集两两不相交 ●方法：提取公共左因子 若：A->8B1l8B2…|8 Bnl rilY2|Ym (其中，每个Y不以⑧开头) 那么，可以把这些规则改写成 A->8A′|YlY2Ym A′->BlB2…|n
⚫消除回溯目的： 非终结符A的所有侯选式的首符集两两不相交 ⚫方法：提取公共左因子 若：A —＞ δβ1|δβ2|…|δβn|γ1|γ2|…|γm (其中,每个γ不以δ开头) 那么,可以把这些规则改写成 A —＞ δA′|γ1| γ2…|γm A′—＞β1|β2|…|βn
四、递归下降分析程序构造 在不含左递归和每个非终结符的所有候选 式的终结首符集都两两不相交条件下，构造一 个不带回湖的自上而下分析程序，该分析程序 由一组递归过程组成，每个过程对应文法的一 个非终结符。 这样的一个分析程序称为递归下降分析器
四、递归下降分析程序构造 在不含左递归和每个非终结符的所有候选 式的终结首符集都两两不相交条件下，构造一 个不带回溯的自上而下分析程序，该分析程序 由一组递归过程组成，每个过程对应文法的一 个非终结符。 这样的一个分析程序称为递归下降分析器