LL(1)文法以及判别,First集,Follow集,Select集,Select集合的解释 | 您所在的位置:网站首页 › 计算select集 › LL(1)文法以及判别,First集,Follow集,Select集,Select集合的解释 |
一、LL(1)文法的定义
是一种预测分析,预测分析是递归下降技术的一个特例,通过在输入中向前看1个符号来选择正确的产生式 第一个L表示:自顶向下分析是从左向右扫描输入串。 第二个L表示:分析过程中将用最左推导。 1表示:只需向右看一个符号便可决定如何推导(即选择哪个产生式进行推导)。 类似也可以有LL(K)文法:需向前查看K个符号才可确定选用哪个产生式。 LL(1)文法的性质:每一步推导都是确定无疑的。简单的说,只要你能确定它是LL(1)文法,推就完事了,有手就行。 所以要进行判断是否是LL(1)文法: 1.计算First集合 2.计算Follow集合 3.计算Select集合,两个相同左部的产生式Select是否有交集,有交集则不是LL(1)文法,交集为空则是LL(1)文法。 (以下暂时不考虑左递归,回溯问题,如有需要,再写) 二、First集 举个例子: 1、β如果是终结符号,那么β∈Follow(A) 2、如果β是非终结符号,则First(β)∈Follow(A) 3、如果非终结符号β可以*推导出ε,Follow(X)∈Follow(A) 4、如果X是开始符号,规定的#∈Follow(X),A又处于S的*推导的末尾,自然而然#∈Follow(A) 三、Select集合 俩种情况下的Select集: Select不过是对First与Follow集合的归纳整理罢了,如下图所示 四、Select的意义: 因为LL(1)文法每次只能识别一个字符,所以一定要保证选择的单一性,即同一左部的产生式,不要推出同样的前缀 如A->aB,A->aC,这样就不知道选择哪一个产生式了 五、为什么a*=>ε,Select(A->a)=(First(A)-{ε})UFollow(A)(这里的a是非终结符) 首先要明确一个东西,a*=>ε,并不代表a一定要取ε!!它代表俩种情况: 1、a取ε时,那么此时的A->ε,那我到底是采用产生式A->β,还是产生式子A->a呢,这就要看Follow(A)了(即紧靠A右边的一个终结符号),如果Follow(A)匹配上了,那么就用A->a,否则就用A->β,如果俩个产生式都匹配上了,那么抱歉,你这俩相同左部产生式的交集不为空,压根就不是LL(1)文法。 2、a不取ε时,此时的Select(A->a)==First(a),又因为题里面的a*=>ε,所以要减去一个{ε}才是正宗的First(a); 俩种情况取并集,即Select(A->a)=(First(A)-{ε})UFollow(A) 六、例题
|
CopyRight 2018-2019 实验室设备网 版权所有 |