一次扫描就可以把相应的FIRST集加入到FOLLOW集中,设置FOLLOW集完成标记位,设置队列,把未完成的非终结符送入队列,依次取出队列元素,把求出FOLLOW集的非终结符的FOLLOW集加入到相应的FOLLOW集中,把未求出的送回队列。如果碰到死循环使用FIRST集一样的方法处理就可以。Р(4)确定SELLECT集РFIRST集&FOLLOW集都已经求出来后SELLECT集就很好求了,扫描每一个产生式,使用以下三个步骤确定: РA→α A∈VN,α∈V*, Р1)、若α是终结符,那么SELLECT(A→α)={α}; Р2)、若α是$,则SELECT(A→α)=FOLLOW(A); Р3)、若α是非终结符,那么Р若α*=>$,则SELECT(A→α)=(FIRST(α)-$)∪FOLLOW(A);Р 若α┐*=>$ 则SELECT(A→α)=FIRST(α)。Р(5)LL(1)文法的判定Р当SELLECT集求出来后就可以判断是不是一个文法是不是LL(1)文法了,扫描产生式左部相同的SELLCET集是否含有相同元素,一旦发现相同元素立刻返回0,扫描结束没有发现相同元素则返回1。Р(6)句子的判定Р当一个文法确定是LL(1)文法时就可以对输入的语句进行判定了。首先要安装SELLECT集生成LL(1)预测分析表,最简单的方法是使用哈希表来表示,把每一个产生式左部依次和这个产生式SELLECT集中的每一个终结符组成关键字,其值即为这个产生式,送入哈希表。这样在进行句子的分析时就可以很容易判断是否使用某一个产生式来进行规约。在实际分析时设置两个栈,把"#"压入分析栈和剩余栈,把开始符压入分析栈,把输入串从右向左送入剩余栈,然后只要两个栈元素个数同时大于1,那么依次从两个栈中取出两个元素进行比较,假如一样就匹配,假如可以规约就规约,否则就不是该文法的句子。Р图1 整个系统控制流程图
全文预览
