对外经济贸易大学《编译原理》课件-第3-4章 程序设计语言的语法描述.pptVIP

* 4.4 提取左因子 ㈠实例引入 例定义无符号整数的文法 N→DN|D D→0|1|2|3|4|5|6|7|8|9 因first(DN)∩first(D)={0,1,2,3,4,5,6,7,8,9}，故文法含有左因子。 ㈡解决方法 提取左因子，引进ε产生式，将文法改造为G。 N→D N N→N|ε D→0|1|2|3|4|5|6|7|8|9 ㈢提取左因子一般规则 考虑一般情况，设非终结符P的规则为 P→δβ1|δβ2|…|δβn，δ∈(VT∪VN)+，βi∈(VT∪VN)* 引进非终结符P，可以把这些规则改写成 P→δP P→β1|β2|…|βn * 先讨论文法符号，然后再讨论候选式、任意文法符号串的first集的构造。 ㈠first集定义 α是文法G的任一符号串（包括候选式），α∈(VT∪VN)* first(α)={a∣αa……，a∈VT} 若αε，则规定ε∈first(α)。 first(α)直观意义是：从α推导出的所有符号串的第一个终结符。或者，从α可推导至空字ε。 ㈡文法符号first集构造算法 ①终结符的first集为终结符本身。 ②观察每个产生式，若有X→a……，其中a∈VT，则a∈first(X)；若X→ε，则ε∈first(X)。 ③观察每个产生式，若有X→Y……，其中Y∈VN，则将first(Y)中的非ε元素（记为first(Y)/ε）加到first(X)中。 4.5.1 first集的定义及构造算法 * 证： 设终结符a∈first(Y)，根据定义有Ya…。 ∵X→Y…… ∴XY……a…… 即Xa……，根据定义有a∈first(X)。 考虑更一般情况,X→Y1Y2…Yi…Yn,其中Y1、Y2、…Yi-1∈VN。 若first(Y1)中含有ε，则将first(Y2)/ε加到first(X)中，否则终止计算。 若first(Y1)和first(Y2)中含有ε，则将first(Y3)/ε加到first(X)中，否则终止计算。 若first(Y1)、first(Y2)、…first(Yi-1)均含有ε，即Y1Y2…Yi-1ε，则把first(Yi)/ε加到first(X)中，否则终止计算。 若所有first(Yj) 均含有ε(1≤j≤n)，即Y1Y2…Ynε，则ε∈first(X)。 反复使用规则③，直至每个非终结符的first集不再增长为止。规则③实质上是一个传递规则。 * 例，文法G如下所示, 求文法符号的first集。 E→TE E→+TE|ε T→FT T→*FT|ε F→(E) | i | x | y 解：文法符号first集的计算规则如下 First集 规则① 规则② 规则③ E first(E)∪first(T)/ε E {+,ε} T first(T)∪first(F)/ε T {*, ε} F {(,i,x,y} + {+} … … * 在“规则③”列处填入的是计算公式，需多次重复计算，直至每个非终结符的first集不再增长为止。计算过程如下 First集 规则② 规则③1 规则③2 规则③3 E {} {} {(,i,x,y} {(,i,x,y} E {+,ε} {+,ε} {+,ε} {+,ε} T {} {(,i,x,y} {(,i,x,y} {(,i,x,y} T {*, ε} {*, ε} {*, ε} {*, ε} F {(,i,x,y} {(,i,x,y} {(,i,x,y} {(,i,x,y} 说明： 由于终结符的first集计算较为简单，在计算过程中不再列出。 在计算E的 first集时（E→TE），因first(T)不含ε，故没有必要考虑E的first集，同理T的first集计算（T→FT）。 计算也可从下至上进行。 * ㈢候选式first集构造算法 设A→α，α=X1X2…Xn，计算规则如下所示： ①置first(α)=first(X1)/ε。 ②若ε∈first(X1)，则把first(X2)/ε加至first(α)中；若ε∈first(X1)且ε∈first(X2)，则把first(X3)/ε加至first(α)；……；依次类推。 ③若所有的first(Xi)均含有ε,其中1≤i≤n，则ε∈first(α)。特别当α=ε,则first(α)={ε}。 接上例，求文法G候选式的first集： E→TE first(TE)=first(T) /ε={(,i,x,y} E→+TE|ε first(+TE)={+},first(ε)={ε} T→FT