第1页：第四章语法分析—自上而下分析
第四章语法分析—自上而下分析
第2页：第四章语法分析—自上而下分析（续）
第四章语法分析—自上而下分析（续）
- 析器语义分析与中间代码生成器优化段源程序表格管理出错处理目标代码生成器
第3页：第四章语法分析—自上而下分析
第四章语法分析—自上而下分析
- 本章主要介绍语法分析的处理
- 要进行语法分析，必须对语言的语法结构进行描述。
- 采用正规式和有限自动机可以描述和识别语言的单词符号；
- 用上下文无关文法来描述语法规则。
第4页：第四章语法分析—自上而下分析（续）
第四章语法分析—自上而下分析（续）
- VT
- 终结符集合(非空)
- VN
- 非终结符集合(非空)，且VT
- S
- 文法的开始符号，S
- P
- 产生式集合(有限)，每个产生式形式为P
- VN=
- VN
- ，P
- VN，
- (VT
- VN)*
- 开始符S至少必须在某个产生式的左部出现一次。
第5页：第四章语法分析—自上而下分析
第四章语法分析—自上而下分析
第6页：直接推出
直接推出
- 例
- 对文法(1)E
- A
- ，即
- A
- 仅当A
- 是一个产生式，且
- ，
- (VT
- VN)*。
- 1
- 2
- n，则我们称这个序列是从
- 1到
- n的一个推导。若存在一个从
- 1到
- n的推导，则称
- 1可以推导出
- n。
- (E)
- (E+E)
- (i+E)
- (i+i)
第7页：假定G是一个文法
假定G是一个文法
- 假定G是一个文法，S是它的开始符号。如果，则
- 1出发，经过一步或若干步，可以推出
- n。用表示：从
- 1出发，经过0步或若干步，可以推出
- n。所以：即或
- 称是一个句型。仅含终结符号的句型是一个句子。文法G所产生的句子的全体是一个语言，将它记为L(G)。
第8页：4.1语法分析器的功能
4.1语法分析器的功能
- 语法分析器的功能
- 按照文法的产生式(语言的语法规则)，识别输入符号串是否为一个句子(合式程序)。
第9页：4.1语法分析器的功能（续）
4.1语法分析器的功能（续）
第10页：基本思想
基本思想
- 算符优先分析法
- 按照算符的优先关系和结合性质进行语法分析。适合分析表达式。
- LR分析法
- 规范归约
- 从输入串开始，逐步进行“归约”，直到文法的开始符号。即从树末端开始，构造语法树。所谓归约，是指根据文法的产生式规则，把产生式的右部替换成左部符号。
- 自下而上分析法(Bottom-up)
第11页：基本思想（续）
基本思想（续）
- E
- i| E+E | E-E | E*E | E/E | (E)i*i+iE*i+iE*E+iE+iE+EEi+*EiiEEEE
第12页：基本思想
基本思想
- 递归下降分析法
- 对每一语法变量(非终结符)构造一个相应的子程序，每个子程序识别一定的语法单位，通过子程序间的信息反馈和联合作用实现对输入串的识别。
- 优点
- 直观、简单和宜于手工实现。
- 它从文法的开始符号出发，反复使用各种产生式，寻找"匹配"的推导。
- 自下而上分析法(Bottom-up)
- 自上而下分析法(Top-down)
- 预测分析程序
第13页：4.2自上而下分析面临的问题
4.2自上而下分析面临的问题
- 自上而下分析的主旨
- 对任何输入串，试图用一切可能的办法，从文法开始符号(根结点)出发，自上而下地为输入串建立一棵语法树。或者说，为输入串寻找一个最左推导。
- 自上而下就是从文法的开始符号出发，向下推导，推出句子。
- 带“回溯”的
- 不带回溯的递归子程序(递归下降)分析方法。
第14页：4.2自上而下分析面临的问题（续）
4.2自上而下分析面临的问题（续）
- )。Sx*yIPSx*yIPAxySx*yIPAxySx*yIPAxy**Sx*yIPAxy**Sx*yIPAxy*Sx*yIPAxy*
第15页：含有左递归的文法将使自上而下
含有左递归的文法将使自上而下
当某个非终结符有多个产生式候选时，可能带来如下问题:1.分析过程中，当一个非终结符用某一个候选匹配成功时，这种匹配可能是暂时的。出错时，不得不“回溯”。2.文法左递归问题。一个文法是含有左递归的，如果存在非终结符P 含有左递归的文法将使自上而下的分析陷入无限循环。
第16页：含有左递归的文法将使自上而下（续）
含有左递归的文法将使自上而下（续）
- 构造不带回溯的自上而下分析算法
- 要消除文法的左递归性
- 克服回溯
第17页：4.3.1左递归的消除
4.3.1左递归的消除
- 直接消除见诸于产生式中的左递归：假定关于非终结符P的规则为P→P
- |
- 其中
- 不以P开头。我们可以把P的规则等价地改写为如下的非直接左递归形式：P→
- P
- P
- →
- P
- |
- 左递归变右递归
第18页：4.3.1左递归的消除（续）
4.3.1左递归的消除（续）
- 1| P
- 2| … | P
- m|
- 1|
- 2|…|
- n其中，每个
- 都不等于
- ，每个
- 都不以P开头那么，消除P的直接左递归性就是把这些规则改写成：P→
- 1P
- 2P
- | … |
- nP
- P
- →
- 1P
- 2P
- |… |
- mP
- 左递归变右递归
第19页：4.3.1左递归的消除
4.3.1左递归的消除
- →+TE
- |
- T→FT
- T
- →*FT
- |
- F→(E) | i(4.2)P→P
- 1| P
- 2| … | P
- m|
- 1|
- 2|…|
- nP→
- 1P
- |
- 2P
- | … |
- nP
- P
- →
- 1P
- |
- 2P
- |… |
- mP
- |
第20页：4.3.1左递归的消除（续）
4.3.1左递归的消除（续）
- Qc
- Rbc
- Sabc一个文法消除左递归的条件：
- 不含以
- 为右部的产生式
- 不含回路。
第21页：4.3.1左递归的消除
4.3.1左递归的消除
- 的规则改写成Pi→
- 1
- |
- 2
- |…|
- k
- ;(其中Pj→
- 1|
- 2|…|
- k是关于Pj的所有规则)消除关于Pi规则的直接左递归性END3.化简由2所得的文法。去除那些从开始符号出发永远无法到达的非终结符的产生规则。
第22页：令它的非终结符的排序为R
令它的非终结符的排序为R
- Q、S。
- 对于R，不存在直接左递归。
- 把R代入到Q的有关候选后，把Q的规则变为Q→Sab | ab | b
第23页：令它的非终结符的排序为R（续）
令它的非终结符的排序为R（续）
- Q、S。
- Q的规则变为Q→Sab | ab | b
- 现在的Q不含直接左递归，把它代入到S的有关候选后，S变成S→Sabc | abc | bc | c
第24页：令它的非终结符的排序为R
令它的非终结符的排序为R
- 消除S的直接左递归后
- S→abcS
- | bcS
- | cS
- S
- →abcS
- |
- Q→Sab |ab | bR→Sa|a
第25页：消除S的直接左递归后
消除S的直接左递归后
- S→abcS
- | bcS
- | cS
- S
- →abcS
- |
- Q→Sab |ab | bR→Sa|a
- 关于Q和R的规则已是多余的，化简为：S→abcS
- | bcS
- | cS
- S
- →abcS
- |
- (4.4)
第26页：消除S的直接左递归后（续）
消除S的直接左递归后（续）
- 例如，若对文法(为S、Q、R，那么，最后所得的无左递归文法是：S→Qc | cQ→Rb | bR→bcaR
- | caR
- |a R
- (4.5)R
- → bca R
- |
- 文法(4.4)和(4.5)的等价性是显然的。
第27页：4.3.2消除回溯
4.3.2消除回溯
- 为了消除回溯就必须保证
- 对文法的任何非终结符，当要它去匹配输入串时，能够根据它所面临的输入符号准确地指派它的一个候选去执行任务，并且此候选的工作结果应是确信无疑的。
- 、提左因子
- A→
- 1|
- 2| … |
- nSa….IPA......
第28页：定义它的终结首符集FIRST
定义它的终结首符集FIRST
- )为
- 特别是，若，则规定
- 定义它的终结首符集FIRST(
- FIRST(
- )。•如果非终结符A的所有候选首符集两两不相交，即A的任何两个不同候选
- i和
- jFIRST(
- i)∩FIRST(
- j)＝
- 当要求A匹配输入串时，A就能根据它所面临的第一个输入符号a，准确地指派某一个候选前去执行任务。这个候选就是那个终结首符集含a的
- 。
第29页：定义它的终结首符集FIRST（续）
定义它的终结首符集FIRST（续）
- 1|
- 2| …|
- n|
- 1|
- 2| … |
- m(其中，每个
- 不以
- 开头)那么，可以把这些规则改写成A→
- A
- 1|
- 2| … |
- mA
- →
- 1|
- 2| … |
- n
- 经过反复提取左因子，就能够把每个非终结符(包括新引进者)的所有候选首符集变成为两两不相交。
第30页：定义它的终结首符集FIRST
定义它的终结首符集FIRST
- →+TE
- |
- T→FT
- T
- →*FT
- |
- F→(E) | i
- i + i4.3.3 LL(1)分析条件
第31页：定义它的终结首符集FIRST（续）
定义它的终结首符集FIRST（续）
- G(E)
- E→TE
- E
- →+TE
- |
- T→FT
- T
- →*FT
- |
- F→(E) | i
第32页：定义它的终结首符集FIRST
定义它的终结首符集FIRST
- G(E)
- E→TE
- E
- →+TE
- |
- T→FT
- T
- →*FT
- |
- F→(E) | i
第33页：定义它的终结首符集FIRST（续）
定义它的终结首符集FIRST（续）
- G(E)
- E→TE
- E
- →+TE
- |
- T→FT
- T
- →*FT
- |
- F→(E) | i
第34页：定义它的终结首符集FIRST
定义它的终结首符集FIRST
- G(E)
- E→TE
- E
- →+TE
- |
- T→FT
- T
- →*FT
- |
- F→(E) | i
第35页：定义它的终结首符集FIRST（续）
定义它的终结首符集FIRST（续）
- G(E)
- E→TE
- E
- →+TE
- |
- T→FT
- T
- →*FT
- |
- F→(E) | i
第36页：定义它的终结首符集FIRST
定义它的终结首符集FIRST
- G(E)
- E→TE
- E
- →+TE
- |
- T→FT
- T
- →*FT
- |
- F→(E) | i
第37页：定义它的终结首符集FIRST（续）
定义它的终结首符集FIRST（续）
- G(E)
- E→TE
- +TE’
- E
- →+TE
- |
- T→FT
- T
- →*FT
- |
- F→(E) | i
第38页：定义它的终结首符集FIRST
定义它的终结首符集FIRST
- G(E)
- E→TE
- +TE’
- E
- →+TE
- |
- T→FT
- T
- →*FT
- |
- F→(E) | i
第39页：定义它的终结首符集FIRST（续）
定义它的终结首符集FIRST（续）
- G(E)
- E→TE
- +TE’FT’
- E
- →+TE
- |
- T→FT
- T
- →*FT
- |
- F→(E) | i
第40页：定义它的终结首符集FIRST
定义它的终结首符集FIRST
- G(E)
- E→TE
- +TE’FT’i
- E
- →+TE
- |
- T→FT
- T
- →*FT
- |
- F→(E) | i
第41页：定义它的终结首符集FIRST（续）
定义它的终结首符集FIRST（续）
- G(E)
- E→TE
- +TE’FT’i
- E
- →+TE
- |
- T→FT
- T
- →*FT
- |
- F→(E) | i
第42页：定义它的终结首符集FIRST
定义它的终结首符集FIRST
- G(E)
- E→TE
- +TE’FT’i
- E
- →+TE
- |
- T→FT
- T
- →*FT
- |
- F→(E) | i
第43页：定义它的终结首符集FIRST（续）
定义它的终结首符集FIRST（续）
- G(E)
- E→TE
- +TE’FT’i
- E
- →+TE
- |
- T→FT
- T
- →*FT
- |
- F→(E) | iS
- …T’+…
第44页：定义它的终结首符集FIRST
定义它的终结首符集FIRST
第45页：定义它的终结首符集FIRST（续）
定义它的终结首符集FIRST（续）
- 1|
- 2|…|
- n则FIRST(
- i)∩FIRST(
- j)＝
- (i
- j)3.对文法中的每个非终结符A，若它存在某个候选首符集包含
- ，则FIRST(
- i)∩FOLLOW(A)=
- i=1,2,...,n如果一个文法G满足以上条件，则称该文法G为LL(1)文法。
第46页：定义它的终结首符集FIRST
定义它的终结首符集FIRST
- 1|
- 2| … |
- n1.若a
- FIRST(
- i)，则指派
- i执行匹配任务；2.若a不属于任何一个候选首符集，则：(1)若
- 属于某个FIRST(
- i)且a
- FOLLOW(A)，则让A与
- 自动匹配。(2)否则，a的出现是一种语法错误。
第47页：定义它的终结首符集FIRST（续）
定义它的终结首符集FIRST（续）
- LL(1)分析法
- 构造不带回溯的自上而下分析算法
- 要消除文法的左递归性
- 克服回溯
第48页：定义它的终结首符集FIRST
定义它的终结首符集FIRST
- 1| P
- 2| … | P
- m|
- 1|
- 2|…|
- n其中，每个
- 都不等于
- ，每个
- 都不以P开头那么，消除P的直接左递归性就是把这些规则改写成：P→
- 1P
- 2P
- | … |
- nP
- P
- →
- 1P
- 2P
- |… |
- mP
第49页：定义它的终结首符集FIRST（续）
定义它的终结首符集FIRST（续）
- 的规则改写成Pi→
- 1
- |
- 2
- |…|
- k
- ;(其中Pj→
- 1|
- 2|…|
- k是关于Pj的所有规则)消除关于Pi规则的直接左递归性END3.化简由2所得的文法。去除那些从开始符号出发永远无法到达的非终结符的产生规则。
第50页：定义它的终结首符集FIRST
定义它的终结首符集FIRST
- LL(1)分析法
- 构造不带回溯的自上而下分析算法
- 要消除文法的左递归性
- 克服回溯
第51页：4.3.2消除回溯
4.3.2消除回溯
- 为了消除回溯就必须保证
- 对文法的任何非终结符，当要它去匹配输入串时，能够根据它所面临的输入符号准确地指派它的一个候选去执行任务，并且此候选的工作结果应是确信无疑的。
- 、提左因子
- A→
- 1|
- 2| … |
- nSa….IPA......
第52页：定义它的终结首符集FIRST
定义它的终结首符集FIRST
- )为
- 特别是，若，则规定
- 定义它的终结首符集FIRST(
- FIRST(
- )。•如果非终结符A的所有候选首符集两两不相交，即A的任何两个不同候选
- i和
- jFIRST(
- i)∩FIRST(
- j)＝
- 当要求A匹配输入串时，A就能根据它所面临的第一个输入符号a，准确地指派某一个候选前去执行任务。这个候选就是那个终结首符集含a的
- 。
第53页：定义它的终结首符集FIRST（续）
定义它的终结首符集FIRST（续）
- 1|
- 2| …|
- n|
- 1|
- 2| … |
- m(其中，每个
- 不以
- 开头)那么，可以把这些规则改写成A→
- A
- 1|
- 2| … |
- mA
- →
- 1|
- 2| … |
- n
- 经过反复提取左因子，就能够把每个非终结符(包括新引进者)的所有候选首符集变成为两两不相交。
第54页：定义它的终结首符集FIRST
定义它的终结首符集FIRST
- +TE’
- E→TE
- E
- →+TE
- |
- T→FT
- T
- →*FT
- |
- F→(E) | i
第55页：定义它的终结首符集FIRST（续）
定义它的终结首符集FIRST（续）
第56页：定义它的终结首符集FIRST
定义它的终结首符集FIRST
- 1|
- 2|…|
- n则FIRST(
- i)∩FIRST(
- j)＝
- (i
- j)3.对文法中的每个非终结符A，若它存在某个候选首符集包含
- ，则FIRST(
- i)∩FOLLOW(A)=
- i=1,2,...,n如果一个文法G满足以上条件，则称该文法G为LL(1)文法。
第57页：定义它的终结首符集FIRST（续）
定义它的终结首符集FIRST（续）
- 1|
- 2| … |
- n1.若a
- FIRST(
- i)，则指派
- i执行匹配任务；2.若a不属于任何一个候选首符集，则：(1)若
- 属于某个FIRST(
- i)且a
- FOLLOW(A)，则让A与
- 自动匹配。(2)否则，a的出现是一种语法错误。
第58页：构造FIRST
构造FIRST
第59页：构造FIRST（续）
构造FIRST（续）
- VT∪VN构造FIRST(X)连续使用下面的规则，直至每个集合FIRST不再增大为止：1.若X
- VT，则FIRST(X)＝{X}。2.若X
- VN，且有产生式X→a…，则把a加入到FIRST(X)中；若X→
- 也是一条产生式，则把
- 也加到FIRST(X)中。
第60页：构造FIRST
构造FIRST
- 若X→Y…是一个产生式且Y
- VN，则把FIRST(Y)中的所有非
- -元素都加到FIRST(X)中；
- 若X→Y1Y2…Yk是一个产生式，Y1，…，Yi-1都是非终结符，而且，对于任何j，1
- j
- i-1，FIRST(Yj)都含有
- (即Y1…Yi-1
- )，则把FIRST(Yi)中的所有非
- -元素都加到FIRST(X)中；特别是，若所有的FIRST(Yj)均含有
- ，j＝1，2，…，k，则把
- 加到FIRST(X)中。
第61页：构造FIRST（续）
构造FIRST（续）
- =X1X2…Xn构造集合FIRST(
- )。1.置FIRST(
- )＝FIRST(X1)\{
- }；2.若对任何1
- j
- i-1，
- FIRST(Xj)，则把FIRST(Xi)\{
- }加至FIRST(
- )中；特别是，若所有的FIRST(Xj)均含有
- ，1
- j
- n，则把
- 也加至FIRST(
- )中。显然，若
- ＝
- 则FIRST(
- )＝{
- }。
第62页：构造FOLLOW(A)
构造FOLLOW(A)
第63页：构造FOLLOW(A)（续）
构造FOLLOW(A)（续）
- B
- 是一个产生式，则把FIRST(
- )\{
- }加至FOLLOW(B)中；3.若A→
- B是一个产生式，或A
- B
- 是一个产生式而
- (即
- FIRST(
- ))，则把FOLLOW(A)加至FOLLOW(B)中。
第64页：构造FOLLOW(A)
构造FOLLOW(A)
- →+TE
- |
- T→FT
- T
- →*FT
- |
F→(E) | i构造每个非终结符的FIRST和FOLLOW集合：FIRST(E) ={(,i}FIRST(E- )={+,
- }FIRST(T) ={(,i}FIRST(T
- )={*,
- }FIRST(F) ={(,i}FOLLOW(E) ={),#}FOLLOW(E
- )={),#}FOLLOW(T) ={+,),#}FOLLOW(T
- )={+,),#}FOLLOW(F) ={*,+,),#}
第65页：4.4递归下降分析程序构造
4.4递归下降分析程序构造
- 构造不带回溯的自上而下分析程序
- 要消除文法的左递归性
- 克服回溯
第66页：分析程序由一组递归过程组成
分析程序由一组递归过程组成
- 文法中每个非终结符对应一个过程；所以这样的分析程序称为递归下降分析器。(因为文法的定义通常是递归的)
- 几个全局过程和变量：
- ADVANCE，把输入串指示器IP指向下一个输入符号，即读入一个单字符号
- SYM，IP当前所指的输入符号
- ERROR，出错处理子程序
第67页：分析程序由一组递归过程组成（续）
分析程序由一组递归过程组成（续）
- →+TE
- |
- T→FT
- T
- →*FT
- |
- F→(E) | i
- 每个非终结符有对应的子程序的定义，首先在分析过程中，当需要从某个非终结符出发进行展开(推导)时，就调用这个非终结符对应的子程序。
第68页：分析程序由一组递归过程组成
分析程序由一组递归过程组成
- 对应的递归下降子程序为
- PROCEDURE E；BEGINT；E
- →+TE
- |
- T→FT
- T
- →*FT
- |
- F→(E) | i
- END；PROCEDURE E
- ；IF SYM=‘+’ THENBEGINADVANCE；T；E
- END
第69页：分析程序由一组递归过程组成（续）
分析程序由一组递归过程组成（续）
- 例
- 文法G(E):E→TE
- BEGINF；T
- ENDPROCEDURE T
- ；IF SYM=‘*’ THENBEGINADVANCE；F；T
- END；
- E
- →+TE
- |
- T→FT
- T
- →*FT
- |
- F→(E) | i
- 对应的递归下降子程序为:
第70页：分析程序由一组递归过程组成
分析程序由一组递归过程组成
- 对应的递归下降子程序为
- PROCEDURE F；IF SYM=‘i’ THEN ADVANCEELSEIF SYM=‘(’ THENBEGINADVANCE;E；IF SYM=‘)’ THEN ADVANCEELSE ERRORENDELSE ERROR;
第71页：分析程序由一组递归过程组成（续）
分析程序由一组递归过程组成（续）
PROGRAM PARSER;BEGINADVANCE;E;IF SYM <>’#’ THENERROREND;
第72页：分析程序由一组递归过程组成
分析程序由一组递归过程组成
- BEGINIF SYM
- FIRST(TE’)THENT；E
- ELSEIF SYM
- FIRST(BC)THENB; CELSE ERROREND；
第73页：分析程序由一组递归过程组成（续）
分析程序由一组递归过程组成（续）
- →+TE
- |
- T→FT
- T
- →*FT
- |
F→(E) | I对应的递归下降子程序为:PROCEDURE E；BEGINT；E- END；PROCEDURE T；BEGINF；T
- END
第74页：分析程序由一组递归过程组成
分析程序由一组递归过程组成
- →+TE
- |
- T→FT
- T
- →*FT
- |
- F→(E) | I对应的递归下降子程序为:PROCEDURE E
- ；IF SYM=‘+’ THENBEGINADVANCE；T；E
ENDELSE IF SYM<>‘#’ AND SYM<>’)’ THEN ERROR
第75页：分析程序由一组递归过程组成（续）
分析程序由一组递归过程组成（续）
- →+TE
- |
- T→FT
- T
- →*FT
- |
- F→(E) | I对应的递归下降子程序为:PROCEDURE T
- ；IF SYM=‘*’ THENBEGINADVANCE；F；T
ENDELSE IF SYM<>‘#’ ANDSYM<>’)’ AND SYM<>’+’ THEN ERROR
第76页：分析程序由一组递归过程组成
分析程序由一组递归过程组成
- →+TE
- |
- T→FT
- T
- →*FT
- |
F→(E) | i对应的递归下降子程序为:PROCEDURE F；IF SYM=‘i’ THEN ADVANCEELSEIF SYM=‘(’ THENBEGINADVANCE;E；IF SYM=‘)’ THEN ADVANCEELSE ERRORENDELSE ERROR;
第77页：分析程序由一组递归过程组成（续）
分析程序由一组递归过程组成（续）
- →+TE
- |
- T→FT
- T
- →*FT
- |
F→(E) | i对应的递归下降子程序为:主程序:PROGRAM PARSER;BEGINADVANCE;EEND;
第78页：}表示闭包运算
}表示闭包运算
- *。2.用表示{
- }0n可任意重复0次至n次，。3.用方括号[
- ]表示{
- }01，即表示
- 的出现可有可无(等价于
- |
- )。引入上述元符号的文法亦称扩充的巴科斯范式。文法的另一种表示法和转换图
第79页：}表示闭包运算（续）
}表示闭包运算（续）
第80页：}表示闭包运算
}表示闭包运算
例4.5文法E→T | E+TT→F | T*FF→i | (E)可表示成E→T{+T}T→F{*F}F→i | (E)(4.6)
第81页：可以用语法图来表示语言的文法
可以用语法图来表示语言的文法
第82页：可构造一组递归下降分析程序
可构造一组递归下降分析程序
PROCEDURE E；BEGINT；WHILE SYM=‘+’ DOBEGINADVANCE；TENDEND；
第83页：可构造一组递归下降分析程序（续）
可构造一组递归下降分析程序（续）
BEGINF；WHILE SYM=‘*’ DOBEGINADVANCE；FENDEND；- E→T{+T}T→F{*F}F→i | (E)(4.6)
- 可构造一组递归下降分析程序：
第84页：可构造一组递归下降分析程序
可构造一组递归下降分析程序
PROCEDURE F；IF SYM=‘i’ THEN ADVANCEELSEIF SYM=‘(’ THENBEGINADVANCE;E；IF SYM=‘)’ THEN ADVANCEELSE ERRORENDELSE ERROR;
第85页：1.文法不含左递归
1.文法不含左递归
- 2.对于文法中每一个非终结符A的各个产生式的候选首符集两两不相交。即，若A→
- 1|
- 2|…|
- n则FIRST(
- i)∩FIRST(
- j)＝
- (i
- j)3.对文法中的每个非终结符A，若它存在某个候选首符集包含
- ，则FIRST(
- i)∩FOLLOW(A)=
- i=1,2,...,n如果一个文法G满足以上条件，则称该文法G为LL(1)文法。回顾：LL(1)文法条件
第86页：1.文法不含左递归（续）
1.文法不含左递归（续）
- 首先在分析过程中，当需要从某个非终结符出发进行展开(推导)时，就调用这个非终结符对应的子程序。回顾：构造不带回溯的自上而下分析器
第87页：4.5预测分析程序
4.5预测分析程序
- 一、预测分析程序工作原理
- 预测分析程序或LL(1)分析法：
- 总控程序
- 分析表M[A，a]矩阵，A
- VN，a
- VT是终结符或‘＃’，
- 分析栈STACK用于存放文法符号
第88页：总控程序分析表X
总控程序分析表X
#输入串分析栈STACKa1a2...ai…#预测分析程序的工作图# Sa1a2...ai…#分析开始时：
第89页：总控程序分析表X（续）
总控程序分析表X（续）
- ‘＃’，则把X从STACK栈顶逐出，让a指向下一个输入符号。匹配成功
第90页：3.若X是一个非终结符
3.若X是一个非终结符
- 则查看分析表M。
- 若M[X，a]中存放着关于X的一个产生式，把X逐出STACK栈顶，把产生式的右部符号串按反序一一推进STACK栈(若右部符号为
- ，则意味不推什么东西进栈)。在把产生式的右部符号推进栈的同时应做这个产生式相应的语义动作。
- 若M[X，a]中存放着“出错标志”，则调用出错诊察程序ERROR。推导
第91页：3.若X是一个非终结符（续）
3.若X是一个非终结符（续）
- VTTHENIF X= a THEN把下一输入符号读进aELSE ERROR匹配成功
第92页：3.若X是一个非终结符
3.若X是一个非终结符
HEN FLAG=FALSEELSE ERRORELSE IF M[X,a]={X→X1X2…Xk}THEN把Xk,Xk-1,…,X1一一推进STACK栈ELSE ERROREND OF WHILE;STOP END分析成功推导
第93页：3.若X是一个非终结符（续）
3.若X是一个非终结符（续）
- →+TE
- |
- T→FT
- T
- →*FT
- |
- F→(E) | i输入串为i1*i2+i3，利用分析表进行预测分析：
第94页：3.若X是一个非终结符
3.若X是一个非终结符
- #E
- Ti1*i2+i3#E→TE
- 2#E
- T
- Fi1*i2+i3#T→FT
- 3#E
- T
- ii1*i2+i3#F→i
第95页：3.若X是一个非终结符（续）
3.若X是一个非终结符（续）
- T
- ii1*i2+i3#F→i4#E
- T
- *i2+i3#5#E
- T
- F**i2+i3#T
- →*FT
- 6#E
- T
- F i2+i3#7#E
- T
- ii2+i3# F→i
第96页：3.若X是一个非终结符
3.若X是一个非终结符
- T
- ii2+i3# F→i8#E
- T
- +i3#9#E
- +i3#T
- →
- 10#E
- T++i3#E
- →+TE
- 11#E
- Ti3#
第97页：3.若X是一个非终结符（续）
3.若X是一个非终结符（续）
- Ti3#12#E
- T
- Fi3#T→FT
- 13#E
- T
- ii3#F→i14#E
- T
- #15#E
- #T
- →
- 16##E
- →
第98页：3.若X是一个非终结符
3.若X是一个非终结符
- ，a]的构造
- 构造FIRST(
- )和FOLLOW(A)
- 构造分析表M[A，a]
第99页：构造FIRST
构造FIRST
第100页：构造FIRST（续）
构造FIRST（续）
- VT∪VN构造FIRST(X)连续使用下面的规则，直至每个集合FIRST不再增大为止：1.若X
- VT，则FIRST(X)＝{X}。2.若X
- VN，且有产生式X→a…，则把a加入到FIRST(X)中；若X→
- 也是一条产生式，则把
- 也加到FIRST(X)中。
第101页：构造FIRST
构造FIRST
- 若X→Y…是一个产生式且Y
- VN，则把FIRST(Y)中的所有非
- -元素都加到FIRST(X)中；
- 若X→Y1Y2…Yk是一个产生式，Y1，…，Yi-1都是非终结符，而且，对于任何j，1
- j
- i-1，FIRST(Yj)都含有
- (即Y1…Yi-1
- )，则把FIRST(Yi)中的所有非
- -元素都加到FIRST(X)中；特别是，若所有的FIRST(Yj)均含有
- ，j＝1，2，…，k，则把
- 加到FIRST(X)中。
第102页：构造FIRST（续）
构造FIRST（续）
- =X1X2…Xn构造集合FIRST(
- )。1.置FIRST(
- )＝FIRST(X1)\{
- }；2.若对任何1
- j
- i-1，
- FIRST(Xj)，则把FIRST(Xi)\{
- }加至FIRST(
- )中；特别是，若所有的FIRST(Xj)均含有
- ，1
- j
- n，则把
- 也加至FIRST(
- )中。显然，若
- ＝
- 则FIRST(
- )＝{
- }。
第103页：构造FOLLOW(A)
构造FOLLOW(A)
第104页：构造FOLLOW(A)（续）
构造FOLLOW(A)（续）
- B
- 是一个产生式，则把FIRST(
- )\{
- }加至FOLLOW(B)中；3.若A→
- B是一个产生式，或A
- B
- 是一个产生式而
- (即
- FIRST(
- ))，则把FOLLOW(A)加至FOLLOW(B)中。
第105页：构造FOLLOW(A)
构造FOLLOW(A)
- →+TE
- |
- T→FT
- T
- →*FT
- |
F→(E) | i构造每个非终结符的FIRST和FOLLOW集合：FIRST(E) ={(,i}FIRST(E- )={+,
- }FIRST(T) ={(,i}FIRST(T
- )={*,
- }FIRST(F) ={(,i}FOLLOW(E) ={),#}FOLLOW(E
- )={),#}FOLLOW(T) ={+,),#}FOLLOW(T
- )={+,),#}FOLLOW(F) ={*,+,),#}
第106页：都构造出FIRST
都构造出FIRST
- 都构造出FIRST(
- )和FOLLOW(A)之后，现在可以用它们来构造G的分析表M[A，a]。1.对文法G的每个产生式A→
- 执行第2步和第3步；2.对每个终结符a
- FIRST(
- )，把A→
- 加至M[A，a]中；3.若
- FIRST(
- )，则对任何b
- FOLLOW(A)把A→
- 加至M[A，b]中。4.把所有无定义的M[A，a]标上“出错标志”。
第107页：
第108页：可以证明
可以证明
- 一个文法G的预测分析表M不含多重定义入口，当且仅当该文法为LL(1)的。
第109页：可以证明（续）
可以证明（续）
- S
- iCtS | iCtSeS | aC
- b提取左因子之后，改写成：G(S):S
- iCtSS’ | aS’
- eS |
- C
- b最近匹配原则
第110页：可以证明
可以证明
