实验3LL(１)文法构造一、实验目的熟悉LL（1）文法的分析条件，了解ＬＬ（1）文法的构造方法。
二、实验内容1、编制一个能够将一个非LL(1）文法转换为LL（1)文法；2、消除左递归;3、消除回溯。
三、实验要求1、将一个可转换非LL（1）文法转换为LL（1）文法，要经过两个阶段，１）消除文法左递归,2）提取左因子，消除回溯。
2、提取文法左因子算法:1）对文法G的所有非终结符进行排序2)按上述顺序对每一个非终结符Pi依次执行：for（ｊ=１; j< i-1;ｊ＋＋)将Pj代入Pi的产生式(若可代入的话）；消除关于Pｉ的直接左递归:Pｉ-> Piα|β，其中β不以Pi开头,则修改产生式为:Pi —＞βPi′Pi′—> αPi′｜ε３）化简上述所得文法。
3、提取左因子的算法：A —＞δβ1|δβ2|…|δβn｜γ１|γ２|…|γm(其中,每个γ不以δ开头) 那么,可以把这些产生式改写成A —> δA′|γ1| γ２…|γmA′—＞β１｜β2|…｜βn4、利用上述算法，实现构造一个ＬL（1）文法：1）从文本文件g.tｘt中读入文法,利用实验1的结果，存入实验1设计的数据结构；2）设计函数ｒｅｍｏve_left＿recursion（）和remｏｖe_left_genｅ()实现消除左递归和提取左因子算法,分别对文法进行操作，消除文法中的左递归和提出左因子;3）整理得到的新文法;4）在一个新的文本文件neｗg.txｔ输出文法，文法输出按照一个非终结符号一行，开始符号引出的产生式写在第一行，同一个非终结符号的候选式用“|”分隔的方式输出。
四、实验环境PC微机ＤＯS操作系统或Ｗindows操作系统Ｔuｒbo Ｃ程序集成环境或Visual C++ 程序集成环境五、实验步骤１、学习LL（1)文法的分析条件；2、学习构造LL（1)文法的算法;3、结合实验１给出的数据结构,编程实现构造LL（1)文法的算法；４、结合实验１编程和调试实现对一个具体文法运用上述算法，构造它的LL(１)文法形式;5、把实验结果写入一个新建立的文本文件。
六、测试数据输入数据：编辑一个文本文文件g.ｔxt，在文件中输入如下内容:ﻩ正确结果：本实验的输出结果是不唯一的,根据消除左递归是选择非终结符号的顺序不同,或选择新的非终结符号的不同,可能会得到不同的结果，下面只是可能的一个结果：1、P->Ｐ之类的)，也不含以ε为右部的产生式。
一个文法要能进行LL（1)分析,那么这个文法应该满足：无二义性，无左递归,无左公因子。
首先需要定义一些规则：1.在程序运行前文法就必须输入进文本文件中,输入的文法只包含其中的所有产生式，并且默认其为可转换的非ＬL(1）文法,即通过消除左递归和反复提取公共左因子,就转换成了ＬL（1）文法。
2.输入的产生式为原实验1的结果，即一个非终结符只有一条产生式，候选之间用“｜”隔开。
3.产生式与产生式之间只能以换行符或分号隔开。
4.开始符号对应的产生式必须第一个输入,即默认输入的第一个产生式的左部的大写字母是开始符号。
5.输入与输出都会保存在文本文件中文件名分别是g.ｔxt和neｗg.txt，本实验测试数据时,将两个文本放在了桌面。
6.ε用＠代替,输入与输出都使用@。
7.新产生的非终结符统一使用没有在非终结符集合中出现的大写字母。
8.规定产生式最多只有２０个。
2、构造LL（1）文法的算法;算法:1)从文本文件ｇ.txt中读入文法,存入结构体中。
将第一个读到的大写字母记为开始符号S,将读到的包括开始符号在内的所有大写字母判定为非终结符，并将第一次出现的存入文法的非终结符集合中,终结符小写字母也一样。
将以换行符或分号隔开的字符串判断为一条产生式存入文法中。
实现函数是scanP()。
2)对文法中的产生式消除左递归。
实现函数是rｅmove_left＿reｃursｉｏn(）。
3)对文法中的产生式反复提取公共左因子。
实现函数是remoｖe_left_geｎe()。
4)向ｎｅwg.tｘt中输出文法的所有产生式。
3、消除左递归文法和提取左因子算法实现方法;消除左递归文法(包括其中用到其它的子函数）:/*字符串分割函数,将产生式右部的候选返回,识别‘|’,从poｓ位开始分割*/stｒｉｎg strsplit(sｔｒiｎg strTok,int pｏs ) { ﻩﻩﻩstｒｉng ｓtr；ﻩｓize_t posiｔion;pｏｓｉｔion = strTok.finｄ("｜",pｏs);ﻩｉｆ(ｐｏsition！= ｓtriｎg::npos) {ﻩﻩﻩ/／找到了‘|’ﻩstr= ｓtrＴok.ｓuｂｓtr(pos,poｓition － pos);ﻩ}ﻩeｌsｅ {ﻩﻩﻩﻩﻩ/／没找到ﻩﻩｓtｒ = strTok．sｕbsｔr(pｏs, ｓtrToｋ.ｓize() - pos）;}return str；}/*获得一个文法中尚未定义的非终结符，即特定的大写字母*/char GetWord(cｈａr *p）{ﻩcharｃｈ，ｗord［] ={ 'A', 'B＇, ＇C','D', 'E', 'F'，'G', ＇H'，'I', 'Ｊ'，'Ｋ', 'Ｌ','M', 'Ｎ','O', 'P',＇Q',ﻩ'R＇, 'S'，＇T', 'Ｕ', 'Ｖ＇，'W', 'Ｘ'，'Y'，'Ｚ'｝;intｗ，x；foｒ (w = ０;w < ２６； w＋+){ﻩｃh= wｏｒd[w];ﻩﻩfor (x＝０； x<m； x++) {ﻩif (ch == p[x］) ｛ﻩﻩbｒeak；ﻩ}ﻩ}ﻩﻩif（x == m)ｂrｅak；ﻩ}ﻩｒetuｒn ch;}/*判断非终结符是否已存在＊/ｂool cheｃｋWｏrｄ(cｈarｃh, stｒing Ｖn） {inｔ i;ﻩbｏolｆlag =tｒue;for（i =０；ｉ < Vn．ｓiｚe()； i++) ｛ﻩﻩif (ch＝=Ｖｎ[i］）ﻩﻩflag = fａｌse;}ﻩrｅｔurn flａg;}／*化简无用产生式*/ｖoid siｍｐlify(ｓtruct graｍｍar *gp） {string str;ﻩﻩ／/存储从开始符号可以到达的非终结符的序列ｉnｔ sVn[20]；ﻩﻩﻩ//标记在哪个产生式ﻩsＶｎ[0]=０；ﻩｓtr．ｉnseｒｔ(０,1,gp-＞Vn[0]); ﻩ//初始化设置开始符号boolｆｌａg[20];fｌａg[0] =fａｌse;ﻩﻩﻩﻩ//标记哪个产生式需要删除char ch；ﻩｉnｔ i,j，ｋ,l，o;ﻩfor(i ＝0； i <str.ｓize(); i++） {ﻩfｏr(j = 3； j < ｇp－>P[ｓVn[i]］.ｓize(); j++) {ﻩﻩｆor (k= 0;ｋ< m；k++){ﻩﻩﻩif (ｇｐ-＞P[sＶn[ｉ]]［j］ <'A' || ｇp－>P[sＶn[i］][j］ > 'Z') breａｋ;//不是非终结符无需判断ﻩﻩif(gp－>P[sVｎ[i]][j] ＝= gp->Ｖn［k]) {ﻩﻩﻩ//判断从开始符号可以到达的非终结符在Vｎ的哪个位置ﻩﻩﻩﻩflaｇ[k] ＝false;ﻩﻩif (checkWｏrｄ(gp－>Vn[k], sｔｒ)） { ﻩ//将在stｒ中没有的有用非终结符插入strﻩﻩint e = str.ｓiｚe（);ﻩﻩﻩsVn[e] ＝ k;ﻩｓtr．ｉｎserｔ(ｓｔr.sｉze()，1, ｇｐ->Ｖｎ[ｋ］);ﻩ}ﻩﻩｂreａｋ;ﻩﻩﻩ}ﻩﻩ}ﻩ}}for (l = 0；l < m； l++) ｛／/删除无用的产生式和相应的非终结符ﻩﻩchａr ch；ﻩｉf(fｌaｇ［l]）{ﻩﻩﻩgp->Vn［l] ＝＇＇；ﻩﻩｆor(o＝ l + １;o <m; o++）｛ch ＝ gp->Ｖn［ｏ - 1］;ﻩﻩgｐ－>Vn[o -1] =ｇｐ－>Ｖn[o］；ﻩﻩﻩﻩｇｐ->Vn[o]＝ｃｈ；ﻩﻩﻩgp->P［ｏ- 1].cｌear(）;ﻩﻩgp->P[o-1］．ｓ>Ｐ[o]);ﻩﻩ}ﻩｍ--；ﻩ}}}void remｏｖe_leｆt_recursion(stｒuct grａmmａｒ *ｇp） { ﻩﻩ//子函数,消除文法左递归ﻩｉｎｔｉ, ｊ,num_i,nｕm_ｊ，ｉpｏs，jｐos；chａｒch_i, cｈ_j；ﻩfoｒ (ｉ＝ 1; i<ｍ + 1;ｉ++) {ﻩﻩｂool repｅａt ＝true; ﻩﻩﻩ／/标记相对于本轮循环上轮过程产生式是否有过变化,有则需要重新分割得到候选ﻩﻩnum_ｉ= 0,ipｏｓ＝ 3;ﻩstrｉng ｓｔr_i［20］,ｒestr_i[２0], ｅx = "a"；ﻩﻩﻩch_ｉ = gp->Ｖn［ｉ - 1］;ﻩﻩﻩ//获取当前要被处理的非终结符，即Piﻩﻩﻩﻩ//分割产生式,得到右部的所有候选ﻩwhｉlｅ (ipos != ｇp->P［i - 1].ｓize() + 1) ｛ﻩstr＿i[ｎuｍ_i］＝ sｔrsplit(gp->P[i－1], ipos);ﻩrestr＿ｉ［num_i］= str＿ｉ[num_i］;ﻩﻩﻩipos= ｉpos ＋str＿ｉ［num_i].siｚe() + １;ﻩnum_ｉ++;ﻩﻩ｝ﻩｆor(j = 1;ｊ＜=i - １; j++) {ﻩﻩif (!rｅpeat) ｛ﻩnum_i ＝０, ipｏs= 3;ﻩﻩｃh_i ＝ｇp-＞Vn[i - 1]; ﻩ／／重新获取当前要被处理的非终结符,即Piﻩﻩﻩﻩ／/分割产生式,得到右部的所有候选ﻩﻩwhile (iｐos ！= gp-＞P[i- 1]．ｓｉzｅ() +１){ﻩﻩﻩstr_i［num_i]= ｓtrspｌit(gp－>P[i - １], iｐos）;ﻩrestr＿i[nuｍ＿i]=str_i［ｎum_ｉ]；ﻩﻩipos = ipos ＋ stｒ_i[nuｍ_i].sｉze（） + 1;ﻩﻩnum＿ｉ++;ﻩﻩ}ﻩ}ﻩrｅｐｅat= truｅ;ﻩﻩstｒiｎｇstｒ＿ｊ[２０]；ﻩﻩiｎt l;ﻩﻩjpoｓ = 3；ﻩﻩﻩnum_j =0;ch_ｊ＝ｇp->Vn［ｊ - １];ﻩﻩﻩﻩ/／获取当前要替换的非终结符,即P ｊﻩﻩﻩ//分割产生式,得到右部的所有候选ﻩﻩﻩﻩｗｈiｌｅ(ｊｐos!= ｇp->Ｐ[j - 1].siｚe() + 1)｛ﻩﻩstｒ＿j[nuｍ＿j]= sｔrsｐlit(gｐ->P[j-１], jｐｏs);ﻩﻩﻩjpoｓ= jpos ＋ stｒ_j[ｎum_ｊ］.sｉｚｅ(） + １；ﻩﻩﻩnum_j++；ﻩﻩﻩ｝ﻩｆor(ｌ = ０; l <num_i； l++) {ﻩ//逐个判断Ｐi的候选中是否含有Pｊ，有则进行替换ﻩﻩﻩﻩstringｃhange;ﻩﻩex［0] = ｃh＿j；ﻩﻩｓize_t poｓ = reｓtr_ｉ［l].find(ex); ﻩﻩﻩﻩif（poｓ ==stｒｉｎg::npoｓ){ ｃontinue;} ／／无需替换ﻩﻩelｓe iｆ (pos ==0){ﻩﻩﻩﻩ／/Pj在该候选的第一个字符ﻩﻩrｅpeat ＝false;／/ﻩﻩsｔｒing ｓ＝str_i[l]．sｕbstr(１， str_i［l].size()- １)；ﻩ／/得到候选中除Pj外的剩余部分ﻩﻩﻩｓtr_ｉ[l].ｓ）;ﻩﻩﻩ／/清空字符串ﻩﻩint link = 0;ﻩwhｉle（1) ｛ﻩﻩﻩ//将Pj的所有候选与Pi中匹配的候选的剩余部分连接，中间还添加“|”ﻩif (lｉｎｋ == ｎum_j）breａｋ；ﻩﻩsｔr_j[liｎk］＋=s; ﻩﻩﻩﻩﻩif（liｎk =＝ｎｕm_j - １) ﻩstr＿i[l］+＝ str＿ｊ［link]；ﻩeｌseﻩsｔｒ_i[ｌ］ = sｔr_ｉ[l］ + str_j[link] ＋"｜"；ﻩﻩﻩﻩ link++;ﻩ}ﻩﻩﻩ}ﻩﻩｅlsｅif (poｓ＝= ｓｔr＿i[l］.size() - 1) ｛//Pj在该候选的最后一个字符ﻩﻩｒｅpｅat =faｌsｅ;／/ﻩﻩﻩﻩsｔｒｉng s = stｒ_i[l].subsｔr(０, stｒ_i[l].size() － 1）;ﻩﻩﻩstr_i[l].s）;ﻩｉnｔｌink ＝0;ﻩﻩwｈｉle（1) { ﻩﻩﻩｉf(link =＝ｎｕm_j)ﻩbreak;ﻩﻩﻩﻩ stｒ＿j[liｎk] =ｓ＋ sｔr_j[ｌink］；ﻩﻩﻩｉf (liｎｋ == num_j - １）sｔr_i［l] += ｓtr＿j[ｌink];ﻩﻩｅlse stｒ_i[l] = str_i[l]+ str_j［linｋ] ＋"|"；ﻩﻩﻩﻩlｉnｋ+＋;ﻩﻩﻩ}}ﻩelsｅ { ﻩﻩﻩ／/Pj在该候选的中间ﻩﻩreｐeaｔ = falｓe;／/ﻩﻩﻩstriｎｇ s1 =ｓｔｒ＿i[l].suｂsｔr(0,pos － 1); ／/得到该候选中Pj前的字符串ﻩﻩﻩﻩｓtrｉng s2 = ｓtｒ_i[l］．suｂsｔr(poｓ+ 1, ｓtr＿i[l]．siｚe() - poｓ - 1）；/／得到该候选中Pｊ后的字符串ﻩﻩﻩstr_ｉ［l].ｓ);ﻩﻩﻩint liｎk ＝ 0;ﻩﻩﻩwhｉle(１) {ﻩﻩﻩﻩﻩﻩﻩｉf(link ==nuｍ_j)ﻩｂreaｋ;ﻩsｔr_ｊ[lｉnk] = s1+ｓtr＿j[link]＋ｓ2;ﻩﻩif (ｌiｎk＝＝ｎum_j －１) str＿i[l]+= str_j[link];ﻩelse str_i[l] = stｒ_i[l] + sｔr_j[linｋ］+ "|";ﻩﻩﻩｌink+＋;ﻩﻩﻩ}ﻩﻩﻩ}}ﻩsｔrinｇstri = "->";ﻩｓtri.iｎsert(０，１,ｃh＿i)；ﻩﻩﻩint indeｘ=0;ﻩﻩwhilｅ（1) {ﻩ//将替换后的Pｉ的所有候选进行重组并存进文法中ﻩﻩｉf（ｉndｅｘ==nuｍ_i)ﻩｂreak;ﻩﻩﻩif (iｎdeｘ == ｎum_i －1)ﻩstｒi = sｔｒi ＋str＿i[iｎdex］;ﻩﻩﻩelse stｒi=stｒi +ｓtr＿i[ｉndex] + "|"；ﻩﻩﻩindeｘ+＋；ﻩ}ﻩﻩｇｐ-＞Ｐ[ｉ - 1] = sｔｒi;ﻩ}ﻩ／/消除直接左递归string spliｔstr[30］， rｅsplｉtstr[30］;ﻩiｎｔ s = 0,ps = 3,h = 0;ﻩwhilｅ (１){ﻩﻩﻩ／/分割替换后的产生式ﻩﻩsplｉtsｔr[ｓ] =ｓｔrsplit(gp-＞P[i - 1],ps)；ﻩﻩrｅspｌｉtｓtr［s］＝splｉtstr[s]；ﻩps = ｐｓ + spｌｉtsｔr[ｓ].sｉｚe()+ 1;ﻩif (ps == gp-＞P[ｉ－ 1].ｓize() + １) ﻩｂｒeak;ﻩｓ++;ﻩ｝ﻩstrｉｎg Pｉ = "－>＂，Ｐichangｅ ="->";ﻩPｉ = ch_i+ Ｐi;ﻩｉnｔlink ＝0,fｌａg＝ -1;bool flagｐos[30］;ﻩﻩchar neｗWord;ﻩﻩｆｏr (; ｌｉｎk<= ｓ;linｋ+＋) { //遍历所有候选,校验其中是否有左递归ﻩﻩｓize_t posi;ﻩﻩposi = respliｔstr[link］.ｆｉｎd（ｃh_i);ﻩif(posｉ =＝0) {ﻩﻩ//存在直接左递归ﻩﻩflag++;ﻩﻩ//对候选标记左递归ﻩﻩｉｆ (flag ＝＝０) { ﻩﻩ//处理出现左递归的第一个候选ﻩﻩnewWｏrd ＝ＧｅtWorｄ(ｇp-＞Vn);ﻩ/／获取一个新的非终结符ﻩﻩgp->Ｖｎ［m] = newWord;ﻩﻩﻩPicｈａnge ＝newWorｄ + Piｃhange;ﻩﻩﻩm++；ﻩﻩﻩﻩsplｉｔstr[link] = splｉtsｔr[liｎk].ｓubstr(1）+ｎeｗＷord;ﻩﻩflagｐｏｓ[ｌinｋ] = ｆaｌse;ﻩﻩﻩﻩgp－>P[m － 1] = Pｉｃhａnge+ ｓplitsｔr[link]+ "|＂;ﻩ}ﻩﻩｉf（flaｇ > 0) {ﻩﻩsplitstr[liｎk］ = sｐlｉtsｔr［link]．substｒ(1） + ｎewWord;ﻩﻩﻩｆlaｇpos[lｉｎk] = false;ﻩﻩgp->P[m - １] ＝gｐ->Ｐ[m - 1] ＋ splitｓｔr[lｉnk] +"｜";ﻩﻩﻩ｝ﻩﻩ}}／/对消除了直接左递归的候选进行重组成为产生式并存入文法ﻩﻩif (flaｇ >-1） {ﻩﻩﻩﻩgp－>P[ｉ - 1] ="->＂;ﻩgp->Ｐ[i -1].inseｒt(０, １,ch_i);ﻩﻩfｏr (; ｈ <= s；ｈ++） {ﻩﻩiｆ(fｌagｐos［ｈ]） {ﻩﻩﻩｓplitsｔr[h] += nｅｗWord;ﻩﻩgp->P[ｉ－ 1] = gｐ-＞P［ｉ-1］ + spｌitstr［h]+ "|";ﻩ}}gp->P[m- 1］+= "@"；ﻩﻩｇｐ－>P［i -1].ｅrase(gp->Ｐ[i- 1］.siｚｅ（)-1,1);ﻩﻩ}ﻩ}ｓimplｉｆｙ（gｐ）；ﻩﻩﻩ／/化简无用的产生式}提取左因子（包括辅助函数)：//对字符串数组排序voｉd sｔr_ｓort(string＊str, int num) {intｉ，j;for (i = 0；i < nuｍ; i++） {ﻩfｏr (j = ｉ+ 1; ｊ＜nｕｍ；ｊ++) ｛ﻩｉf(sｔr[i] > sｔr[ｊ])ﻩﻩstr[i]．s［ｊ]);ﻩ}ﻩ｝}/*子函数，提取左因子*/vｏｉd remｏve_ｌeｆt_geｎe(sｔｒuct grammaｒ*gp） {ﻩﻩﻩﻩﻩinｔｒｕle＿a, i， j, ｋ， l, matcｈnuｍ，oldmaｔｃhｎｕm， reｓize,ｓize;ﻩchaｒch, newWord；ｆor（rｕle＿ａ = 0; rｕle_a <m;rｕle＿a++) { ／／遍历所有产生式ﻩintｂre = -１;ﻩﻩﻩﻩﻩ//标记已对产生式进行过左因子的提取ﻩinｔｏldpo ＝0;ﻩﻩint nｕm = 0, ps = 3；ﻩstｒinｇｓtr[30]，restr[30];ﻩﻩﻩﻩ／/前者用于判断,需要保持原样，后者用于对有公共左因子的候选进行提取,可变ﻩｗhile (ps != gp-＞Ｐ[ｒulｅ_a］．siｚe（)+1) { ﻩ／/分割替换后的产生式ﻩﻩｓｔr[nuｍ]＝strsplit(ｇp->P［ruｌe_a］, ps);ﻩrｅｓtｒ［num] = str[nuｍ];ps = ps + str[nuｍ］.size() +1；ﻩﻩﻩnｕm＋＋;}ﻩﻩｓtｒ_sort（str,num）; ﻩﻩ//对所有候选按AＳCII码进行排序,以便于简化对公共左因子的判断,只需先对前面候选判断ﻩstr_soｒt（restr,nuｍ）;ﻩint ca＿ｉ;ﻩsｔringＰa =＂->"；ﻩPa.insert(0, 1，gp->Ｖn[rule_a］);ﻩfor(cａ＿i ＝0; ca_ｉ < nｕｍ; ca_i+＋） {ﻩ//对排序后的候选进行重组并存入文法ﻩｉf (ca_i== nuｍ -1)ﻩPa +=stｒ[ca＿ｉ]；ﻩﻩelｓeﻩPa += ｓtr［cａ＿i] +＂|";ﻩﻩ}ﻩgp->P[rule_a] = Pa;ﻩﻩｉnｔ ipo ＝ 0; //辅助免除对已判断过有左因子的候选的遍历ﻩfor (i = 0；i ＜ num;i＋+，i += ｉpo） { //遍历候选ﻩｉpo = ０；ﻩﻩsize = 0；ﻩrｅｓize = 0;ﻩﻩoldmatchｎum = ０;intｉ_s =sｔr[ｉ]．sｉze();ﻩfｏｒ (j ＝0;j＜ｉ_s;j++) { ﻩﻩ//对候选的逐个字符遍历ﻩﻩﻩﻩｍａtchnuｍ＝０; ﻩﻩﻩ/／标记除了本身,有几个候选有公共左因子ﻩﻩﻩcｈ＝str[i][j];ﻩﻩint kf = num; ﻩﻩfor(ｋ＝ i +１;ｋ< num && ｋ<kf;k＋＋） { //对i之后的候选进行判断，是否有与ｉ对应的公共左因子ﻩﻩﻩﻩif（sｔr［ｋ][j] == ｃh) { ﻩ/／有公共左因子ﻩﻩｍatｃｈnum++;ﻩﻩﻩ}ﻩeｌsｅ {ﻩﻩﻩｂreak;ﻩ}ﻩﻩ}ﻩif (j == 0) { ﻩ／/判断是否有公共左因子是i的第一个字符的情况,有则特别处理ﻩﻩﻩif（mａtchnum ＝＝ 0)ﻩﻩｂreak;ﻩﻩelseﻩ{olｄmatchnｕm = maｔchnum; kf= i + 1 + ｏldmａtchｎum;} ﻩﻩﻩ}ﻩﻩﻩﻩelse{ﻩﻩﻩﻩﻩﻩif(oldmａtchnｕm!= matｃhnum) breａk;ﻩﻩ}ﻩﻩ}ﻩ／*有公共左因子的处理过程*/ﻩｉf（mａtｃhnum ！=oldｍatchｎum｜｜ j =＝ i_s) {ﻩﻩﻩﻩﻩｂｒe++;ﻩﻩstriｎｇmatｃｈ,ｒepstr，ｃaｎ, newＰ;ﻩmatｃh ＝ str［i].sｕbstr(0, ｊ)；//获取公共左因子ﻩﻩﻩﻩnewWoｒd =GｅtWord(gp->Vn)；ﻩﻩ//得到新的非终结符ﻩﻩﻩgp->Vn［m］=ｎｅwWoｒd；ﻩ//将新非终结符存入文法ﻩﻩm++；ﻩneｗP＝"->"；ﻩﻩﻩnｅwＰ.iｎsert(0,1,neｗWord）；ﻩrepstr= matcｈ + ｎewWord;ﻩ//得到要被替换的有公共左因子的所有候选ﻩint renuｍ = ｎｕm;ﻩﻩﻩﻩiｆ（bｒe> 0) ｛ﻩ//若对同一产生式还存在另一个公共左因子（之前提取过一次左因子),需进行特别处理ﻩﻩｓiｚe = rｅsｉze = ０;ﻩﻩﻩﻩｒenum = 0；ﻩpｓ = 3;ﻩﻩwhilｅ (ｐｓ！= gp->P[ｒｕle＿ａ].ｓize（) ＋1){ﻩﻩﻩ／/分割变化后的产生式ﻩﻩﻩﻩﻩrｅsｔr［reｎum]= ｓｔrｓｐlit(gp->P［ｒule_a], ｐs）;ﻩﻩﻩﻩﻩps = pｓ＋ restr［ｒeｎum].sｉｚe() +1;ﻩﻩrenｕm++；ﻩﻩﻩﻩ}ﻩﻩ}ﻩ/*将已经提取过左因子的以候选为单位的字符串重新组合成产生式(包括新产生式)*／ﻩﻩﻩﻩfor (l ＝０; l <＝ i－ oｌｄpo+ ｏldmatchnuｍ;l＋+) ｛ﻩﻩﻩﻩﻩif（ｌ >=i － oｌdpｏ) {ﻩﻩﻩﻩsｉze ＋= ｒeｓtr［l].sｉze()；ﻩﻩcaｎ=reｓtr［ｌ］．sｕbｓｔｒ(j）；ﻩﻩﻩﻩﻩif (can == ＂")ﻩﻩｃａn = "@＂;ﻩﻩﻩﻩif(l == i -oldpo+ ｏldｍatcｈnｕm) nｅwP += ｃan;ﻩﻩﻩﻩelsｅnｅwＰ =newP + can+ "|"；ﻩﻩﻩﻩﻩｇp-＞Ｐ[m － 1］= newＰ;ﻩﻩ｝ﻩﻩelse｛ﻩﻩﻩﻩｒｅsｉze+= restｒ［ｌ].sizｅ（）;ﻩﻩｒeｓiｚe＋＋；ﻩﻩ｝ﻩﻩ｝ﻩﻩgｐ－>P［ｒuｌe＿a].replａce(resize＋ 3,size + ｏｌdmaｔcｈnum,repstr)；//原产生式以替换的方式进行改变ﻩﻩiｆ（i + 1+oldmatchnum >nｕm) { break;}ﻩelsｅoldpｏ = ｉpｏ = olｄｍaｔcｈnum；ﻩ}ﻩ}ﻩ}}4、主程序代码;＃iｎcluｄe<ｉostream＞#iｎｃｌude＜strｉng>using namｅspace std;ｓｔrucｔgrammar｛ﻩﻩﻩ/／使用结构体定义文法ﻩchar Vn[2０]；ﻩﻩﻩﻩ//非终结符ﻩcｈar Vｔ［2０];ﻩﻩﻩﻩﻩ／/终结符ﻩcｈaｒS;ﻩﻩﻩ／/开始符号ｓtring P[２0]; ﻩﻩﻩﻩ//产生式};int m = 0, n ＝0;ﻩﻩﻩ/／全局变量，分别表示最近存入结构体的非终结符与终结符是字符数组的第几个位置ｃhａr GeｔBＣ（ＦILE* fpi）｛ﻩ／／子函数，用于读取一个非空格字符ｃhaｒ ch；ﻩdｏ｛ﻩcｈ = fgeｔc(fpi）;ﻩ} ｗhｉle(ch ==＇ '）;return ch;}ﻩ／＊ﻩ整型函数，读入一行产生式分析出文法成员,参数分别是输入文本的文件指针、文法结构体的指针ﻩ第几行的产生式ﻩﻩ*／voｉd scanP(FＩLE* ｆpｉ,ｓtruct gramｍar*gｐ) {ﻩﻩﻩｃｈaｒ ch;striｎｇｓtr; ﻩﻩﻩﻩ//存入一条产生式ﻩiｆ (feof（ｆpi))ﻩﻩrｅｔｕrn；ﻩﻩ/／到达文件尾则返回ﻩch ＝GetBＣ（ｆpｉ);ﻩif (ch＞=＇A＇ && cｈ＜＝'Z') ｛ﻩﻩﻩ//读入产生式左部的非终结符ﻩstr +=ｃｈ;ﻩgｐ－＞Vn[ｍ］ = ch；ﻩﻩﻩ//将非终结符存入结构体ﻩﻩm++;ﻩch ＝ GetBC(fｐｉ)；ﻩif（ch == '-') ｛ﻩﻩｓtr += ch；ﻩﻩｃh = GetBＣ(fpi)；ﻩﻩif(ch== '>'){ﻩﻩﻩstr +=cｈ;ﻩﻩwｈiｌｅ (1) ｛ch = GｅtBC(fｐi);ﻩﻩﻩｉf (ch=='\n' || ch == ';') ﻩbrｅａk; ﻩ//读入换行符或分号,退出循环ﻩﻩstr+＝ ch;ﻩﻩﻩﻩﻩiｆ（ch＞= 'ａ' && cｈ<= ＇z') {ﻩﻩ／/读入终结符ﻩﻩﻩiｎｔｎｕm;ﻩﻩfor (nuｍ =0； num< n; num＋＋){ ﻩﻩ//判断该终结符在当前结构体中是否已存在ﻩiｆ(gp-＞Vｔ[num]==ch)ﻩﻩﻩﻩﻩbｒeａk；ﻩﻩ}ﻩﻩﻩﻩﻩif(num ＝= n) {ﻩﻩ/／存入结构体中未出现的终结符ﻩﻩﻩﻩﻩgp->Ｖｔ[n] ＝cｈ;ﻩﻩﻩﻩﻩﻩｎ++;ﻩﻩ}ﻩﻩﻩ}ﻩﻩﻩ}ﻩﻩﻩ}ﻩ}ﻩｇp－>P[ｍ - 1]+＝ｓtr;ﻩﻩﻩ//将产生式存入结构体ﻩ｝}ｉnt main() {ﻩＦILE＊ fpi；ﻩﻩ//定义输入文本指针ﻩFIＬE* ｆｐo; ﻩﻩﻩﻩ/／定义输出文本指针ﻩerｒnｏ_t erｒ;ﻩｉf((err = fｏpｅn_s(＆fｐｉ,"Ｃ：＼\Users\\Ａdministｒatoｒ\\Desktｏp＼\g.txt＂，"r")) !＝0）｛ﻩ／/只读方式打开文件ﻩprinｔf(" not open！＼ｎ"); ﻩ//打开文件出错提示ﻩexit（０);ﻩﻩﻩﻩﻩﻩ//安全退出程序ﻩ}sｔruct gｒamｍar g,*gp; ﻩﻩｇp =&ｇ；ﻩﻩﻩﻩﻩ//定义结构体及其指针/／读取第一个大写字母作为开始符号ﻩｃhａr ch;ﻩｄｏ {ﻩch = GetBC（fpi);ﻩ}while (ch<= 'A＇｜| ch >＝'Z');ﻩgp->S =ch;fseek（fpi, －1L， 1); ﻩﻩ//搜索指示器回调一个字符ｗhilｅ (!feof(fpi)） {ﻩﻩﻩ//从文本文件中读入产生式得到文法四个部分，并存入结构体中ﻩscａnＰ(fpi，gp）;ﻩﻩﻩ｝fcｌoｓｅ(fpi）; ﻩﻩﻩ//关闭fpi指向的文件fｐi =NＵＬL; ﻩﻩﻩﻩﻩ//避免指向非法内存rｅmovｅ＿lｅft＿ｒecurｓion（gp）；ﻩremｏve_left_ｇeｎe(gp)；ｅrｒ＝fｏpen_s(＆fpo,"C:\＼Ｕseｒs\\Administraｔor\\Desktop\\nｅｗg.txt", "ｗ"）; //只写方式打开文件，不存在则自动建立ﻩif(ｅrｒ != 0） {ﻩﻩprｉntf(" not ｏpen！\n＂);ﻩﻩﻩﻩ/／打开文件出错提示ﻩﻩexiｔ（０）; ﻩﻩﻩﻩﻩ／/安全退出程序ﻩ}int i; ﻩﻩｆor (i =０; ｉ＜ m; i+＋) {ﻩﻩ//输出处理后的文法到文本中fputs（gp－>P[i］．daｔa(),fpｏ);ﻩﻩfpｕtｓ（"\n", fpo);ﻩ｝fcｌose(ｆpo); ﻩ//关闭fｐi指向的文件ﻩfpo ＝NUＬL；ﻩﻩﻩﻩ//避免指向非法内存}5、整个测试程序的流程；6、程序的测试结果和问题;实验源文法:ﻩ其它文法:向g.txt中输入文法启动程序main()反复调用scanP()到达文件尾完成文法输入调用remove_left_recursion()调用remove_left_gene()将文法输出到newg.txt程序结束查看结果文法ﻩ书上的文法，不过调换了顺序,且改变开始符号为R,结果会删除关于Q的无用产生式:ﻩﻩ实验中遇到的问题:1.开始设计程序的时候，并没有很好的运用数据结构来简化问题,只是使用了实验一的数据结构,构造了一个结构体。