预测分析程序与LL(1)文法
一、预测分析程序
1.带预测分析的PDA：
1）在PDA中加入预测分析之后，可以消除自上而下分析中出现回溯的现象，此时PDA可以改造为：
2）注：a、改造后，整
一、预测分析程序
1.带预测分析的PDA：
1）在PDA中加入预测分析之后，可以消除自上而下分析中出现回溯的现象，此时PDA可以改造为：
2）注：a、改造后，整
新浪博客
个分析过程都在预测分析程序控制下工作。B、预测分析程序用了一个预测分析表，它是预测分析程序分析时的主要依据。
3）预测分析表：预测分析表是一矩阵M[A,a]，其中行标A是非终结符，列标a是终结符或串结束符；矩阵元素M[A,a]是存放A的一个候选式，指出当前栈顶符号为A且面临读入符号为a时应选的候选式；或者存放“出错标志”，指出A不该面临读入符号a。
2.预测分析程序算法描述
设栈顶符号为X，读入符号为a，则
1）若X=a=‘#’，则表示识别成功，退出分析程序；
2）若X=a=‘#’，则表示匹配，弹出栈顶符号X，读头前进一格，让读头指向下一个符号，以读入下一个符号；若X是终结符，但X<>a，则调用error处理；
3）若X属于非终结符，则查预测分析表M。若M[X,a]中存放着关于X的产生式，则弹出X，且将相应产生式右部以自右向左的顺序压入栈，在输出带上记下产生式编号；若M[X,a]中存放着出错标记，则调用相应Error处理。
二、求串α的终结首符集和非终结符A的随符集
a)
i.
注：1）若α推导出空串，那么空串就属于First(α)。
2）First(α)集合是α的所有可能推导出的开头终结符或空串所组成的集合。
ii.
具体步骤：
b)
i.
ii.
1.
2.
3.
注：这里的文法必须消除左递归且提取了左因子后的文法。
三、构造预测分析表
a)
b)
预测分析表的形式化：
四、LL(1)文法、
a)
注：1）LL(1)文法是无二义的，二义文法一定不是LL(1)文法。
2）LL的含义是从左到右扫描输入串，采用最做推导分析句子。
3）数字1表示分析句子时需向前看一个输入符号。
4）有LL(1)就有LL(k)，LL(k)向前看k个输入符号，选择候选式更加准确，但M的尺寸会以n的k次方增长，其中![编译原理笔记10 <wbr> <wbr>自上而下分析-预测分析程序与LL(1)文法]( "编译原理笔记10 <wbr> <wbr>自上而下分析-预测分析程序与LL(1)文法")
对程序设计语言去k=1就够了。
b)
文法G是LL(1)文法当且仅当对于G的每个非终结符A的任何两个不同产生式A->α|β有：
五、状态表：
3）预测分析表：预测分析表是一矩阵M[A,a]，其中行标A是非终结符，列标a是终结符或串结束符；矩阵元素M[A,a]是存放A的一个候选式，指出当前栈顶符号为A且面临读入符号为a时应选的候选式；或者存放“出错标志”，指出A不该面临读入符号a。
2.预测分析程序算法描述
设栈顶符号为X，读入符号为a，则
1）若X=a=‘#’，则表示识别成功，退出分析程序；
2）若X=a=‘#’，则表示匹配，弹出栈顶符号X，读头前进一格，让读头指向下一个符号，以读入下一个符号；若X是终结符，但X<>a，则调用error处理；
3）若X属于非终结符，则查预测分析表M。若M[X,a]中存放着关于X的产生式，则弹出X，且将相应产生式右部以自右向左的顺序压入栈，在输出带上记下产生式编号；若M[X,a]中存放着出错标记，则调用相应Error处理。
二、求串α的终结首符集和非终结符A的随符集
a)
i.
注：1）若α推导出空串，那么空串就属于First(α)。
2）First(α)集合是α的所有可能推导出的开头终结符或空串所组成的集合。
ii.
具体步骤：
b)
i.
ii.
1.
2.
3.
注：这里的文法必须消除左递归且提取了左因子后的文法。
三、构造预测分析表
a)
b)
预测分析表的形式化：
四、LL(1)文法、
a)
注：1）LL(1)文法是无二义的，二义文法一定不是LL(1)文法。
2）LL的含义是从左到右扫描输入串，采用最做推导分析句子。
3）数字1表示分析句子时需向前看一个输入符号。
4）有LL(1)就有LL(k)，LL(k)向前看k个输入符号，选择候选式更加准确，但M的尺寸会以n的k次方增长，其中
b)
文法G是LL(1)文法当且仅当对于G的每个非终结符A的任何两个不同产生式A->α|β有：
五、状态表：