文档介绍:判定LL1型文法试验汇报-A版
一、试验目标首先能让用户输入一个文法,然后让计算机自动判定是否是一个LL(1)文法,经过试验教学,加深学生对所学的有关编译的理论知识的了解,增强学生对所学知识的综合应用能力,并经过实践达成对所学的知识进行验证。
二、试验环境供windows系统的Pc机,可用c++/c#/java等编程工具编写三、试验内容1、让计算机接收一个文法,示比如:
G[S]为:S→ABS→bcA→εA→bB→εB→aDc→ADc→bD→aSD→、编程实现对上述文法是否是LL(1)文法的判定,是则给出肯定回复,不然给出否定回复。
(1)文法试验步骤图以下:
,FoLLow集和SELEcT集是SELEcT(A→α)∩S输出肯定ELEcT(A→β)=Φ?回复否输出否定回复
四、概要设计(1)、LL(1)文法的定义
LL(1)分析法属于确定的自顶向下分析方法。LL(1)的含义是:第一个L表明自顶向下分析是从左向右扫描输入串,第2个L表明分析过程中将使用最左推导,1表明只需向右看一个符号便可决定怎样推导,即选择哪个产生式(规则)进行推导。
LL(1)文法的判别需要依次计算FIRST集、FoLLow集和SELLEcT集,然后判定是否为LL(1)文法,最终再进行句子分析。
需要预计分析器对所给句型进行识别。即在LL(1)分析法中,每当在符号栈的栈顶出现非终极符时,要预计用哪个产生式的右部去替换该非终极符;当出现终止符时,判定其和剩下输入串的第一个字符是否匹配,假如匹配,则继续分析,不然报错。LL(1)分析方法要求文法满足以下条件:对于任一非终极符A的两个不一样产生式Aà,Aà,全部要满足下面条件:
SELEcT(Aà)∩SELEcT(Aà)=
(2)、预计分析表结构LL(1)分析表的作用是对目前非终极符和输入符号确定应该选择用哪个产生式进行推导。
它的行对应文法的非终极符,列对应终极符,表中的值有两种:一是产生式的右部的字符串,一是null。若用m表示LL(1)分析表,则m可表示以下:
m:VN×VTàP∪{Error}m(A,t)=Aàα,当tselect(Aàα),不然m(A,t)=Error其中P表示全部产生式的集合。
(3)、语法分析程序结构
LL(1)分析中X为符号栈栈顶元素,a为输入流目前字符,E为给定测试数据的开始符号,#为句子括号即输入串的括号。分析表用一个二位数组m表示,数组元素m[A,a]中的下标A表示非终止符,a为终止符或句子括号‘#’,二维数组中存放的是一条有关A的产生式,表明当非终止符A向下推导时,面临输入符a时,所采取的候选产生式,当元素内容无产生式时,则表明用A的左部向下推导时出现了不该出现的符号,所以元素内容转向犯错处理的信息。
LL(1)分析过程关键包含以下四个动作:
替换:当XVN时选对应产生式的右部去替换X。此时X出栈,逆序入栈。
匹配:当XVT时它和a进行匹配,其结果可能成功,也可能失败,假如成功则符号栈中将X退栈并将输入流指针向前移动一位,不然报错。
接收:当格局为(#,空#)时汇报分析成功。