四川大学王红老师编译原理课程设计,LL(1)文法判定
{$},FIRST(Yi)都包含在FIRST(X)中,即: FIRST(Yi-1)-{$} ∈FIRST(X)
所有Y1,…Yn *=> $ ,则把$加到FIRST(X)中,即: FIRST(Yi) ∈FIRST(X)
其中第1~3个方法都很好处理,关键是第四个方法判断时首先判断第一个字符为非终结符,设定一个布尔型扫描标志FLAG,赋初值TRUE,接下去依次扫描产生式右部每一个字符Yi,假如第i个字符可以推出空,那么就把这个字符的FIRST集去除$加入到产生式左部字符的FIRST集中,即FIRST(Yi)-{$} FIRST(X),假如Yi是终结符或者不可以推出$,那么就把这个字符的FIRST集直接加入到FIRST(X)中,即FIRST(Yi) FIRST(X)同时置FLAG为FALSE不再向下扫描,假如Yi恰好是最后一个字符,那么不管它能不能星推导出空都直接把它的FIRST集加入到FIRST(X)中。同时要设置一个队列和一组布尔型变量记录FIRST集是否完成,队列用来记录FIRST(X)用到了哪些其它非终结符的FIRST集。
第一遍扫描完成后就扫描队列,把FIRST集完成的非终结符的FIRST集加入到那些没有完成的非终结符的FIRST集中去,没有完成的非终结符再送回到队列,这时候可能出现死循环,比如FIRST(S)用到了FIRST(A),而FIRST(A)用到了FIRST(B),FIRST(B)又用到了FIRST(S),这时候S,A,B的FIRST标志均为FALSE,无限循环下去。这时候可以记录一下,比如循环了100次,强行设置FIRST(S)的标志为TRUE,那么FIRST(A),FIRST(B)也就依次可以求出了。我们在实际计算时也是这样处理的。只是没有把标志写出来而是记录在心里的。
对于100次循环或许有些多了,那么到极限情况,可能就是循环总共产生式的个数次数时如果再循环就可以确定是进入死循环了。
如何判断一个文法是LL(1)文法_计算机软件及应用_IT/计算机_专业资料 暂无评价0人阅读0次下载举报文档 如何判断一个文法是LL(1)文法_计算机软件及应用_IT/...
LL(1)文法判定算法_电脑基础知识_IT/计算机_专业资料。1、判断各非汇总结符是否可以推出空 (1)将各非终结符出示状态置为“未知” (2)按顺序扫描各产生式右部...
LL(1)文法的含义:第一个L 第二个L 1 从左到右扫描输入串 生成的是最左推导 向右看一个输入符号便可决定选择哪个产生式。 例1:判断下列文法是否是LL(1)...
? LL(1)文法的判别 (1) (2) (3) (4) (5) (6) 文法化简 - 不...(,i 例: 判断文法是否是LL1文法 G: S→AB S→bC A→b A→ε B→ε ...
实验小结 通过本次实验,熟悉了 LL(1)文法,掌握了 LL(1)文法的判定方法,具 体实践了 FIRST 集、FOLLOW 集、SELECT 集的计算,加深了对 LL(1)文法的理 解。...
LL(1)文法的判别需要依次计算 FIRST 集、FOLLOW 集和 SELLECT 集,然后判断是否 为 LL(1)文法,最后再进行句子分析。 2 需求分析本次课程设计要求编写一个程序,...
国家人才培养模式创新实验区、 云南省教学团队、 云南大学软件学院 教育创新基金(编号:2009EI08)联合资助项目 判定 LL(1)文法 姓学专 名: 号: 业: 软件工程 ...
LL(1)文法的判别_计算机软件及应用_IT/计算机_专业资料 暂无评价0人阅读0次下载举报文档 LL(1)文法的判别_计算机软件及应用_IT/计算机_专业资料。...
课程设计报告 课程: 学号: 姓名: 班级: 教师: 时间: 编译原理课程设计 计算机科学与技术系 设计名称: LL(1)文法的判定(假设文法符合的 First 和 Follow 集...
求出能推出 的非终结符 求出能推出ε的非终结符例4.7 文法4.2 P79 消除...(A) -∪ 补充例: 判断文法是否是LL1文法 判断文法是否是 文法 G: S→AB ...
热门文档