编译原理课程设计LL(1)文法 do while 三地址输出 报告加代码

目录1 问题域描述 (3)2 文法及属性文法的描述 (3)2.1 WHILE循环语句的文法 (3)2.2 WHILE循环语句的属性文法 (4)3 语法分析方法及中间代码形式的描述 (4)3.1语法分析方法 (4)3.2中间代码形式描述 (6)4 编译系统的概要设计 (7)4.1词法分析 (7)4.2语法制导翻译 (8)5 详细的算法描述 (8)5.1 文法设计 (8)5.2 算法描述 (8)5.3 源程序代码 (9)6 软件的调试过程和结果测试 (19)6.1调试过程 (19)6.2结果测试 (19)7 使用说明 (20)8 课设总结 (20)9 参考文献 (22)WHILE循环语句的翻译程序设计（简单优先法、输出三地址表示）1 问题域描述while循环语句的翻译程序设计（简单优先法，输出单地址表示），要求完成：（1）用C++语言正确编写程序，完成WHILE循环语句的翻译程序设计。

（2）求能正确进行词法分析，语法分析，并能正确的输出预期结果。

（3）根据指定的文法，判定程序的正确性。

本次课程设计中要求设计一个WHILE循环语句的词法﹑语法及语义分析程序，语法分析选择简单优先法，采用语法制导翻译输出中间代码三元式。

通过设计、编制、调试一个WHILE循环语句的语法及语义分析程序，加深对语法及语义分析原理的理解，实现功能。

while循环语句的格式为：while（P）{do A}，其中A为循环体，可为一个或多个赋值语句；P为循环控制条件。

while循环语句首先根据循环控制条件P进行判断，若满足条件则执行循环体A，否则执行下面的程序段；本次课程设计中系统首先要进行词法分析，即从左到右把源文件的字符序列逐个进行扫描，产生一个个的单词序列，作为语法分析的输入从而继续编译过程。

该程序的语法分析读入词法分析的结果，并判断输入语句是否满足while循环语句的文法所描述的形式。

通过简单优先法对语句进行分析，看是否能通过给定的输入串归约到文法的开始符号。

本次课程设计主要是介绍LL(1)文法的一般原理，根据给定的一文法编制调试LL(1)文法语法分析程序，以便对任意输入的符号串进行分析。

本次课程设计的目的主要是加深对预测分析LL(1)文法语法分析的理解，加深对自顶向下语法分析方法的认识。

具体如下：1、对语法规则有明确的定义；2、编写的分析程序能够对给定文法进行正确的语法分析；3、对输入给定的文法，手工计算First、Follow集合以及各产生式的Select 集合，再根据Select集合构造出预测分析表；4、对于输入串，应能根据预测分析表判断识别该输入串是否为给定文法的句子；5、对于遇到的错误，给出简单的错误信息提示，保证能够顺利完成语法分析过程。

前言------------------------------------------------------------- Ⅰ目录------------------------------------------------------------- Ⅱ一、系统分析------------------------------------------------------ 11.1 判断LL(1)文法---------------------------------------------- 11.2 构造预测分析表---------------------------------------------- 1二、系统设计------------------------------------------------------ 22.1 基本设计---------------------------------------------------- 22.2 程序流程图-------------------------------------------------- 2三、系统实现------------------------------------------------------ 33.1 程序主要函数------------------------------------------------ 33.2 程序主要代码------------------------------------------------ 3四、系统测试------------------------------------------------------ 7五、总结---------------------------------------------------------- 8 参考文献---------------------------------------------------------- 9一、系统分析有文法G[E]：E->TG T->FSG->+TG|ε S->*FS|ε F->(E)|i 1.1 判断LL(1)文法当我们需选用自顶向下分析技术时，首先必须判别所给文法是否是LL(1)文法，分析所给文法可知文法中不含左公因子，也不存在左递归，因而再对给定文法计算First 集、Follow 集以及Select 集，对于求出的每个产生式的Select 集，看对于同一个左部非终结符是否存在交集，如果它们的交为空则表示所给文法是LL(1)文法，否则不是L(1)文法。

DO-WHILE循环语句的翻译程序设计（LR方法、输出三地址表示）1.系统描述1.1设计目的通过设计、编制、调试一个DO-WHILE循环语句的语法及语义分析程序，加深对语法及语义分析原理的理解，并实现词法分析程序对单词序列的词法检查和分析。

1.2设计内容及步骤对循环语句：DO〈赋值语句〉WHILE 〈表达式〉按给定的题目写出符合自身语法分析方法要求的文法和属性文法描述。

(1)按给定的题目给出语法分析方法的思想及分析表设计。

(2)按给定的题目给出中间代码序列的结构设计。

(3)完成相应的词法分析、语法分析和语义分析程序设计。

(4)编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。

2文法的描述本程序所用的文法如下：G[S]:(1)S->do{E;}while(B) {if B.true goto B.true else goto B.false;}(2)B->I1 rop I2 {B.type=bool;B.val=I1.val rop I2.val;}(3)E->I1=I2 op I3 {I1.val=I2.val op I3.val;}(4)I->id {I.val=id.val;}注意：rop is < or >，op is +,-,*,/, id is any number or identifier由上可知，非终结符B表示布尔表达式，E表示赋值表达式3.语法分析方法描述及语法分析表设计3.1语法分析方法描述本实验采用LR分析方法对DO-WHILE语句进行语法分析。

LR分析法是一种能根据当前分析栈中的符号串（通常以状态表示）和向右顺序查看输入串的K个（K>=0）符号就能惟一的确定分析器的动作是移进还是归约和用哪个产生式归约，因而也就能惟一的确定句柄。

LR分析法的归约过程是规范推导的逆过程，所以LR分析过程是一种规范过程。

一个LR分析器由3个部分组成：总控程序，也可以称为驱动程序。

专题3_LL(1)语法分析设计原理与实现李若森 13281132 计科1301一、理论传授语法分析的设计方法和实现原理；LL(1) 分析表的构造；LL(1)分析过程；LL(1)分析器的构造。

二、目标任务实验项目实现LL(1)分析中控制程序（表驱动程序）；完成以下描述算术表达式的 LL(1)文法的LL(1)分析程序。

G[E]:E→TE’E’→ATE’|εT→FT’T’→MFT’|εF→(E)|iA→+|-M→*|/设计说明终结符号i为用户定义的简单变量，即标识符的定义。

加减乘除即运算符。

设计要求(1)输入串应是词法分析的输出二元式序列，即某算术表达式“专题 1”的输出结果，输出为输入串是否为该文法定义的算术表达式的判断结果；(2)LL(1)分析程序应能发现输入串出错；(3)设计两个测试用例（尽可能完备，正确和出错），并给出测试结果。

任务分析重点解决LL(1)表的构造和LL(1)分析器的实现。

三、实现过程实现LL(1)分析器a)将#号放在输入串S的尾部b)S中字符顺序入栈c)反复执行c)，任何时候按栈顶Xm和输入ai依据分析表，执行下述三个动作之一。

构造LL(1)分析表构造LL(1)分析表需要得到文法G[E]的FIRST集和FOLLOW集。

构造FIRST(α)构造FOLLOW(A)构造LL(1)分析表算法根据上述算法可得G[E]的LL(1)分析表，如表3-1所示：表3-1 LL(1)分析表主要数据结构pair<int, string>:用pair<int, string>来存储单个二元组。

该对照表由专题1定义。

map<string, int>:存储离散化后的终结符和非终结符。

vector<string>[][]:存储LL(1)分析表函数定义init:void init();功能：初始化LL(1)分析表，关键字及识别码对照表，离散化（非）终结符传入参数：（无）传出参数：（无）返回值：（无）Parse:bool Parse( const vector<PIS> &vec, int &ncol )；功能：进行该行的语法分析传入参数：vec:该行二元式序列传出参数：emsg:出错信息epos:出错标识符首字符所在位置返回值：是否成功解析。

《编译原理》综合性实验报告实验学期2016 至2017 学年第 1 学期专业计算机科学与技术班级1403学生姓名黄世增学号1411640305任课教师曦实验成绩《编译原理》课程综合性实验报告开课实验室：C210 2016年12月6日四、实验步骤编写程序时，先定义几个全局变量，key[]事先存放7个关键字，words[]用来存放识别出来的单词二元组，text用来存放从文件读取的容，word用于存放识别出来的单词，length存放字符个数，k存放识别出来的单词个数。

首先，将文本容读取到text中，文本容最后一个字符是空白符，然后调用scan 法，逐个扫描每个字符，如果word的第一个字符是字母，则进行拼字符串，再判断是关键字还是标识符；如果word的第一个字符是数字，则在word清空之前判断是否有识别出非数字字符，若有，则出错，若没有，则识别出来的字符串是常数；若word第一个字符是运算符或界限符，则各自存到words[]中。

最后扫描结束后输出。

五、实验结果及分析六、实验小结和思考通过这次实验，我对词法分析器有了进一步的了解，而且对词法分析和语法分析在实践中的应用有了深入的掌握, 让我对高级语言的学习有了更深的认识，了解得更透彻。

七、源程序清单#include<stdio.h>#include<stdlib.h>#include<string>using namespace std;#define MAX 10000struct WordString{string Word;//单词int category;//类别};char *key[7] = {"int","for", "while", "do", "return", "break", "continue"};//关键字WordString words[MAX]; //创建一个单词符号串string text; //读入的文本存入text中string word; //分割出的单词用word表示int length; //字符个数int k; //总单词个数开课实验室：C210 2016年12月8日六、实验小结和思考本实验加深了我对LL(1)分析法的算法和思想的理解。

/* LL(1)文法<古城童话>$为空字; 输入0，表示结束测试案例：案例1.(编译原理P76的LL(1)文法,E'改成了A,T'改成了B);E->TA A->+TA|$ T->FB B->*FB|$ F->(E)|i 0案例2. （First和Follow有非空交集）S->Ab A->a|B|$ B->b|$ 0*/#include <iostream>#include <string>using namespace std;const int MAX=100;int FirstNum=0,FollowNum=0; // First集合Follow集的数目string SaveStr[MAX]; //预存输入的字符串string TerStr="#"; //保存终结字符串int FlagError1=0; //左递归错误标志struct Assemble{int FlagLast,FlagFirst; //首尾标志int Position ; //字符串的位置char Data;Assemble *Next;};Assemble *First[MAX]; //定义Fist集Assemble *Follow[MAX]; //定义Follow集int IsNonterminal(char Cur) //判断是否为非终结符{if(Cur<='Z'&&Cur>='A')return 1;return 0;}int IsTerminal(char Cur) //判断是否为终结符{if(IsNonterminal(Cur)||Cur=='|')return 0;return 1 ;}int Exist(Assemble* L,char Cur,int Flag) //L的集合里面是否有Cur字符{ //Flag为1表示First，为0表示Followif(!L) return 0;Assemble *P;for(P=L->Next;P;P=P->Next)if(P->Data==Cur)return Flag ? P->Position:1 ;return 0;}int IsEmptyStr(char Cur) //字符串里面是否有${for(int i=0;i<FirstNum;i++)if(SaveStr[i][0]==Cur){ if(SaveStr[i].find('$')==-1)return 0;return 1;}}void HideSame(Assemble* &L) //消除相同的字符{Assemble *P,*Pa;for(P=L->Next;P->Next;P=P->Next)for(Pa=P->Next;Pa;Pa=Pa->Next)if(P->Data==Pa->Data) Pa->Data=3;}Assemble* FindAddFirst(char Cur) //查找要添加的First集{for(int i=FirstNum-1;i>=0;i--)if(First[i]->Data==Cur) return First[i];return NULL;}Assemble* FindAddFollow(char Cur) //查找要添加的Follow集{for(int i=0;i<FollowNum;i++)if(Follow[i]->Data==Cur) return Follow[i];return NULL;}void CreatFirst(Assemble* &L,string Str) //创建Firs集{Assemble *P=L,*Pa;int FlagLeft=0,Pos=3,j,i;L->FlagLast=0;for(i=3;Str[i];i++){int FlagGo=1,FlagLa=1;char Ch=L->Data;if(Ch==Str[3]||Str[i-1]=='|'&&Str[i]==Ch) FlagError1=1; //含有左递归while(i<Str.length()&&Str[i]!='|'){if(IsNonterminal(Str[i]))FlagGo=(IsEmptyStr(Str[i])? 1:0);Pa=new Assemble;Pa->Data=Str[i];Pa->Position=Pos;P->Next=Pa;P=Pa;if(!FlagGo||IsTerminal(Str[i])){ FlagLa=0; break; }i++;}if(!FlagLa)while(Str[i]&&Str[i]!='|')i++;else { L->FlagLast=1; }Pos=i+1;}P->Next=NULL;}void CreatFollow(string Str) //创建Follow集{int i,j,Num;for(i=3;Str[i];i++){Num=-1;if(IsNonterminal(Str[i])){ for(j=0;j<FollowNum;j++)if(Follow[j]->Data==Str[i]){ Num=j; break; }if(Num<0){Follow[FollowNum]= new Assemble;Follow[FollowNum]->Data=Str[i];Follow[FollowNum]->Next=NULL;Num=FollowNum++;}int FlagGo=0,FlagLa=0;Assemble *Pa,*Pb,*P=Follow[Num];for(j=i+1;Str[j]&&Str[j]!='|';j++){Pa=new Assemble;Pa->FlagLast=0;for(;P->Next;P=P->Next);FlagGo=Exist(FindAddFirst(Str[j]),'$',1)? 1:0;Pa->Data=Str[j];P->Next=Pa;Pa->Next=NULL;if(!FlagGo){ FlagLa=1; break; } //是否继续添加}if(!FlagLa) //非终结符位于末尾{for(;P->Next;P=P->Next);Pb=new Assemble;Pb->FlagLast=1;Pb->Data=Str[0];Pb->Next=P->Next;P->Next=Pb;}}}}void InitFollow(int Num) //初始化Follow集{for(int i=0;i<Num;i++){if(!i){Follow[FollowNum]=new Assemble;Follow[FollowNum]->Data=SaveStr[0][0];Follow[FollowNum]->Next=new Assemble;Follow[FollowNum]->Next->Data='#';Follow[FollowNum++]->Next->Next=NULL;}CreatFollow(SaveStr[i]);}}//增添Follow集,Num=1,增添First集，Num=0,增添Follow集void AddFollow(Assemble* &L, Assemble* Head,int Num){Assemble *Pa,*Pb,*Pc;for(Pc=Head->Next;Pc;Pc=Pc->Next){ for(Pa=L->Next;Pa;Pa=Pa->Next)if(Pa->Data==Pc->Data)break;if(!Pa){if(Pc->Data=='$'&&Num) continue;Pb=new Assemble;Pb->Data=Pc->Data;Pb->Next=L->Next;L->Next=Pb;}}}void GetFollow(Assemble* &L) //得到Follow集{Assemble *P,*Head;for(P=L->Next;P;P=P->Next)if(IsNonterminal(P->Data)){if(P->FlagLast) //位于末尾,增添Follow集{Head=FindAddFollow(P->Data);AddFollow(L,Head,0);}else //不位于末尾,增添First集{Head=FindAddFirst(P->Data);AddFollow(L,Head,1);}}}int GetFirst(Assemble* &L) //得到First集{Assemble *P,*Pa,*Pb,*Pc,*Head;for(P=L->Next;P;P=P->Next)if(IsNonterminal(P->Data)){Head=FindAddFirst(P->Data);if(!Head)return 0;for(Pc=Head->Next;Pc;Pc=Pc->Next)if(Pc->Data=='$'&&!L->FlagLast)continue;Pb=new Assemble;Pb->Data=Pc->Data;Pb->Position=P->Position;Pb->Next=L->Next;L->Next=Pb;}}}void KeepTerStr(string Str) //保存终结符{for(int i=3;Str[i];i++)if(IsTerminal(Str[i])&&Str[i]!='$'){if(TerStr.find(Str[i])==-1)TerStr+=Str[i];}}void ShowLL1(Assemble *L,int num)//输出LL(1)文法{Assemble *P=L,*Head;int i,npos;string Str=SaveStr[num];cout<<First[num]->Data<<"\t";for(i=0;TerStr[i];i++){if(npos=Exist(L,TerStr[i],1)){cout<<First[num]->Data<<"->";if(npos==1)npos=3;while(Str[npos]!='|'&&npos<Str.length()){cout<<Str[npos];npos++;}}else if(Exist(L,'$',0)){Head=FindAddFollow(First[num]->Data);if(Exist(Head,TerStr[i],0))cout<<First[num]->Data<<"->"<<"$";cout<<"____";}else cout<<"____";cout<<"\t ";}cout<<"\n\n";}int IsError2()//测试是否有左因子{string AddStr,Str;for(int i=0;i<FirstNum;i++){AddStr="";Str=SaveStr[i];for(int j=0;Str[j];j++)if(j==3||Str[j-1]=='|'){if(AddStr.find(Str[j])!=-1) return 1;AddStr+=Str[j];}}return 0;}Assemble* IsError3(char &Ch) //测试First和Follow是否有非交集{Assemble *P,*Pa,*Head;for(int i=0;i<FirstNum;i++){for(P=First[i]->Next;P;P=P->Next){Head=FindAddFollow(First[i]->Data);if(P->Data!='$'&&IsTerminal(P->Data)&&P->Data!=3)for(Pa=Head->Next;Pa;Pa=Pa->Next)if(Pa->Data==P->Data){ Ch=First[i]->Data; return P; }}}return NULL;}int ShowForm() //显示LL(1)文法的终结符{Assemble *P;char Cur;if(FlagError1){ cout<<"\n文法中含有左递归...!\n"; return 1; }if(IsError2()){ cout<<"\n文法中含有左因子...!\n"; return 1; }if(P=IsError3(Cur)){ printf("\n文法中First(%c)和Follow(%c)有非空交集%c...!\n",Cur,Cur,P->Data);return 1;}cout<<"\nLL(1)分析表:\n\n";for(int i=0;TerStr[i];i++)cout<<"\t "<<TerStr[i];cout<<endl;for(int i=0;i<FirstNum;i++)ShowLL1(First[i],i);}void GetFistrFollow(int Num){int i,j;FirstNum=Num;for(i=0;i<Num;i++){First[i]=new Assemble;First[i]->Data=SaveStr[i][0];CreatFirst(First[i],SaveStr[i]); //创建First集}for(j=0,i=FirstNum-1;i>=0;i--,j++) //得到First集{GetFirst(First[i]);GetFirst(First[j]);}InitFollow(Num); //初始化Follow集for(i=0;i<FollowNum;i++)GetFollow(Follow[i]); //得到Follow集}int main(){int i,j,Num=0;cout<<"请输入文法产生式(以输入0结束):\n";while(cin>>SaveStr[Num]&&SaveStr[Num][0]!='0') {KeepTerStr(SaveStr[Num]);Num++;}GetFistrFollow(Num); //获得First集合Follw集ShowForm(); //输出LL(1)文法表system("pause");}。

实验3 ＬL(1）文法构造一、实验目的熟悉ＬL（１）文法的分析条件,了解LL(1)文法的构造方法。

二、实验内容1、编制一个能够将一个非LＬ(1)文法转换为ＬL（1）文法；２、消除左递归;3、消除回溯。

三、实验要求1、将一个可转换非ＬL(1）文法转换为LＬ（1）文法,要经过两个阶段，1）消除文法左递归，2）提取左因子，消除回溯。

2、提取文法左因子算法:１）对文法G的所有非终结符进行排序２)按上述顺序对每一个非终结符Pi依次执行:foｒ( j=1; j＜ i-１；j++）将Pj代入Pi的产生式(若可代入的话）;消除关于Pi的直接左递归:Pi －＞ Pｉα|β ,其中β不以Ｐi开头,则修改产生式为：Pi —> βPi′Pｉ′—＞αPi′｜ε3)化简上述所得文法。

3、提取左因子的算法:Ａ—＞δβ1｜δβ2|…|δβn|γ１｜γ2|…|γｍ(其中,每个γ不以δ开头) 那么,可以把这些产生式改写成A —＞δA′｜γ1| γ２…|γｍA′—>β１|β2|…|βn4、利用上述算法,实现构造一个LL（1）文法:1）从文本文件ｇ．ｔｘｔ中读入文法,利用实验1的结果，存入实验１设计的数据结构；2）设计函数remove_left_ｒeｃｕrｓioｎ(）和remoｖｅ_left＿gｅne()实现消除左递归和提取左因子算法，分别对文法进行操作,消除文法中的左递归和提出左因子；3）整理得到的新文法;4）在一个新的文本文件neｗg．txt输出文法，文法输出按照一个非终结符号一行,开始符号引出的产生式写在第一行,同一个非终结符号的候选式用“｜”分隔的方式输出。

四、实验环境ＰC微机DOS操作系统或Wiｎdoｗｓ操作系统Turbo Ｃ程序集成环境或ViｓuａｌC＋+ 程序集成环境五、实验步骤１、学习LＬ（1）文法的分析条件;２、学习构造LL(1）文法的算法;3、结合实验１给出的数据结构，编程实现构造ＬＬ（1）文法的算法;4、结合实验1编程和调试实现对一个具体文法运用上述算法,构造它的LＬ（１）文法形式;5、把实验结果写入一个新建立的文本文件。

一、实验目的及要求1．掌握LL(1)分析法的基本原理；2．掌握LL(1)分析表的构造方法；3．用LL（1）分析法分析高级语言表达式。

4、了解LL（1）分析器的工作过程。

文法：无二义性的算术表达式的文法（1）把词法分析作为语法分析的子程序实现（5分）（2）独立的语法分析程序（4分）（3）对表达式文法消除左递归、构造LL（1）分析表（4）LL（1）分析表可以直接输入（4分），也可以用程序实现（5分）（5）给一个表达式，给出分析过程（分析栈、输入串、所用规则）（4分）（6）生成一个棵语法树（5分）用二叉树的形式表示出来二、实验内容及原理1、实验原理（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→α，当t∈select(A→α) ，否则M(A, t) = Error其中P表示所有产生式的集合。

编译原理词法分析和l l(1)文法判定-CAL-FENGHAI.-(YICAI)-Company One1武汉科技大学实验报告课程名称编译原理专业班级姓名学号实验一词法分析器设计【实验目的】1．熟悉词法分析的基本原理，词法分析的过程以及词法分析中要注意的问题。

2．复习高级语言，进一步加强用高级语言来解决实际问题的能力。

3．通过完成词法分析程序，了解词法分析的过程。

【实验内容】用C语言编写一个PL/0词法分析器，为语法语义分析提供单词，使之能把输入的字符串形式的源程序分割成一个个单词符号传递给语法语义分析，并把分析结果（基本字，运算符，标识符，常数以及界符）输出。

【实验步骤和要求】1．要求绘出词法分析过程的流程图。

2．根据词法分析的目的以及内容，确定完成分析过程所需模块。

3．写出每个模块的源代码。

4．整理程序清单及所得结果。

【流程图】【源代码】//resource.h#define IDD_MAINDLG 101#define IDR_MENU 102#define IDI_ICON 104#define IDC_INPUT 1001#define IDC_OUTPUT 1003#define IDC_ERRPUT 1004#define IDC_BUTTON1 1005#define ID_START 40001#define ID_ABOUT 40003#define ID_OPEN 40005#define ID_SAVE 40006#define ID_LISTKEY 40007// Next default values for new objects//#ifdef APSTUDIO_INVOKED#ifndef APSTUDIO_READONLY_SYMBOLS#define _APS_NEXT_RESOURCE_VALUE 105#define _APS_NEXT_COMMAND_VALUE 40008#define _APS_NEXT_CONTROL_VALUE 1007#define _APS_NEXT_SYMED_VALUE 101#endif#endif//getsym.h#ifndef _GETSYM_H_#define _GETSYM_H_#include <stdlib.h> //For memset()#include <string.h> //For strcpy()#define ISLETTER(c) ((c)>='A'&&(c)<='Z'||(c)>='a'&&(c)<='z')#define ISNUMBER(c) ((c)>='0'&&(c)<='9')#define ISCHAR(c) ((c)>=33 &&(c)<=126)#define MAX_SYM 32768 //最大符号量#define MAX_SYMFORM 1024 //最大符号表长度#defineMAX_NUMFORM 4096 //最大常数表长度#define MAX_SYMLEN 31 //最大符号长度#define MAX_NUMLEN 10 //最大常数长度#define MAX_BUFFER MAX_SYMLEN+1//最大缓冲长度#define MAX_KEYWORD 27 //关键字数量#define MAX_OPWORDA 8 //单字运算符数量#define MAX_OPWORDB 4 //双字运算符数量#define MAX_ENDWORD 8 //单字界符数量#define MAX_ERROR 5 //错误类型数量#define TYPE_KEYWORD 1 //关键字类型号#define TYPE_SYMBOL 2 //符号类型号#define TYPE_NUMBER 3 //常量类型号#define TYPE_OPWORD 4 //运算符类型号#define TYPE_ENDWORD 5 //界符类型号#define TYPE_ERROR -1 //错误类型号#define ERR_OVERSYMLEN 1 //以下是一般错误号#define ERR_OVERNUMLEN 2#define ERR_NUMBER 3#define ERR_WRONGOP 4#define ERR_OVERSYMFORM 10001 //以下是严重错误号#define ERR_OVERNUMFORM 10002#define ERR_OVERSYMNUM 10003#define ERR_OVERERRNUM 10004#ifdef __cplusplusextern "C" {#endifstruct SYM //符号描述结构体(含错误描述结构){int type; //类型号(0:错误)int id; //ID号(错误值)int line; //所在行数// int no; //SYM编号/列号char name[MAX_SYMLEN+1]; //所取的词};struct FORM //表格结构体{int symnum;int numnum;struct SYMF //符号表项结构体{int id;char name[MAX_SYMLEN+1];}symf[MAX_SYMFORM];struct NUMF //常量表项结构体{int id;char name[MAX_NUMLEN+1];}numf[MAX_NUMFORM];};struct SYMINFO //词法分析信息结构体{int num;struct SYM sym[MAX_SYM];struct FORM form;};//取词函数(返回读字符数量,如果是0则表示结束,lin表示当前行数)int __stdcall getsym(const char *in,struct SYM *out,int *ln,struct FORM *form); //取所有词函数(正常返回0,否则返回严重错误号)int __stdcall getsyminfo(const char *in,struct SYMINFO *out);#ifdef __cplusplus}#endif#endif#include "getsym.h"//关键字[BASIC:13,EXTEND:14]const char* const keytxt[MAX_KEYWORD]={"procedure","call","begin","end","var","const","if","then","while","do","read","write","odd","program","type","function","array","integer","real","char","boobean","case","of","repeat","until","to","down"};//单字运算符const char opatxt[MAX_OPWORDA]={'+','-','*','/','=','#','<','>'};//双字运算符const char* const opbtxt[MAX_OPWORDB]={"<=",">=",":=","<>"};//单字界符const char eoptxt[MAX_ENDWORD]={'(',')',',',';','.','[',']',':'};//错误提示信息const char* const errtxt[MAX_ERROR]={"OK", //Not used."Too long symbol","Too long number","Mixed number and letter","Unkown operator",};int getsym(const char *in,struct SYM *out,int *ln,struct FORM *form){char b[MAX_BUFFER]; //建符号缓冲区int i,m=0,n=0,e=0; //序号/非字符数/字符数/出错标记memset(out,0,sizeof(struct SYM));while(!ISCHAR(*in)) //滤出前面的非字符{if(*in==10) (*ln)++;//换行时,ln++if(*in++) m++; else return 0; //如果无字符则退出}out->line=*ln;if(ISLETTER(*in)) //字母开头情况{while(ISLETTER(*in)||ISNUMBER(*in)){if(n<=MAX_SYMLEN) b[n]=*in;n++; in++;}b[MAX_SYMLEN]=0; //符号结尾置0if(n<MAX_SYMLEN) b[n]=0;strcpy(out->name,b);if(n>MAX_SYMLEN) //超出符号最大长度{out->type=TYPE_ERROR;out->id=ERR_OVERSYMLEN;}else{for(i=0;i<MAX_KEYWORD;i++)if(strcmp(b,keytxt[i])==0) break;if(i<MAX_KEYWORD) //属于关键字{out->type=TYPE_KEYWORD;out->id=i;}else //不属于关键字{for(i=0;i<form->symnum;i++)if(strcmp(b,form->symf[i].name)==0) break;if(i==form->symnum) //不在符号表中则添加{if(form->symnum>=MAX_SYMFORM){ //超出符号表范围产生严重错误out->type=TYPE_ERROR;out->id=ERR_OVERSYMFORM;return m+n;}form->symf[i].id=i;strcpy(form->symf[i].name,b);form->symnum++;}out->type=TYPE_SYMBOL; //符号类型out->id=i;}}return m+n;}if(ISNUMBER(*in)) //数字开头情况{e=0;while(ISNUMBER(*in)||ISLETTER(*in)){if(ISLETTER(*in)) e=1; //含字母则置出错标记if(n<=MAX_NUMLEN) b[n]=*in;n++; in++;}b[MAX_NUMLEN]=0; //数字尾置0if(n<MAX_NUMLEN) b[n]=0;strcpy(out->name,b);if(e||n>MAX_NUMLEN) //有出错标记或超出数字最大长度{out->type=TYPE_ERROR;if(e) //含字母情况out->id=ERR_NUMBER;else //超出数字最大长度情况out->id=ERR_OVERNUMLEN;}else //无错情况{if(form->numnum>=MAX_NUMFORM){ //超出常量表范围产生严重错误out->type=TYPE_ERROR;out->id=ERR_OVERNUMFORM;return m+n;}form->numf[form->numnum].id=form->numnum;strcpy(form->numf[form->numnum].name,b);out->type=TYPE_NUMBER;out->id=form->numnum;form->numnum++;}return m+n;}for(i=0;i<MAX_OPWORDB;i++) //双字运算符情况if(*(short*)in==*(short*)(opbtxt[i])) break;if(i<MAX_OPWORDB){out->type=TYPE_OPWORD;out->id=MAX_OPWORDA+i;*(short*)out->name=*(short*)opbtxt[i];out->name[2]=0;return m+2;}out->name[0]=*in;out->name[1]=0;for(i=0;i<MAX_OPWORDA;i++) //单字运算符情况if(*in==opatxt[i]) break;if(i<MAX_OPWORDA){out->type=TYPE_OPWORD;out->id=i;return m+1;}for(i=0;i<MAX_ENDWORD;i++) //单字界符情况if(*in==eoptxt[i]) break;if(i<MAX_ENDWORD){out->type=TYPE_ENDWORD;out->id=i;return m+1;}out->type=TYPE_ERROR;out->id=ERR_WRONGOP; //其他符号则出错return m+1;}int getsyminfo(const char *in,struct SYMINFO *out){int offset,ln=1; //每次取词偏移量/当前行数memset(out,0,sizeof(struct SYMINFO));while(1){offset=getsym(in,&out->sym[out->num],&ln,&out->form);if(offset==0) break; //完成取词则退出if(out->num>=MAX_SYM) return ERR_OVERSYMNUM;//超出符号信息最大值if(out->sym[out->num].type==TYPE_ERROR&&out->sym[out->num].id>=10000)return out->sym[out->num].id;//有严重错误则退出out->num++;in+=offset;}return 0;}Test.Txtprogram test;procedure func(a:integer,b:char);beginvar c:char;read(c);if c>=1234 thenb:=c*320;b:=(a-b)/10000;end;beginconst s:=4444;a:=b[333];while s=a dobegincall test;end;write(a);end.结果实验二 LL（1）语法分析程序设计【实验目的】1．熟悉判断LL（1）文法的方法及对某一输入串的分析过程。

课程设计题目WHILE循环语句的翻译程序设计（递归下降法、输出三地址表示）学院计算机科学与技术学院专业计算机科学与技术班级0806姓名张方纪指导教师郭羽成2010 年 1 月7 日课程设计任务书学生姓名：张方纪专业班级：计算机0806班指导教师：郭羽成工作单位：计算机科学与技术学院题目: WHILE循环语句的翻译程序设计（递归下降法、输出三地址表示）初始条件：理论：学完编译课程，掌握一种计算机高级语言的使用。

实践：计算机实验室提供计算机及软件环境。

如果自己有计算机可以在其上进行设计。

要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）（1）写出符合给定的语法分析方法的文法及属性文法。

（2）完成题目要求的中间代码三地址表示的描述。

（3）写出给定的语法分析方法的思想，完成语法分析和语义分析程序设计。

（4）编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。

（5）设计报告格式按附件要求书写。

课程设计报告书正文的内容应包括：1 系统描述（问题域描述）；2 文法及属性文法的描述；3 语法分析方法描述及语法分析表设计；4 按给定的题目给出中间代码形式的描述及中间代码序列的结构设计；5 编译系统的概要设计；6 详细的算法描述（流程图或伪代码）；7 软件的测试方法和测试结果；8 研制报告（研制过程，本设计的评价、特点、不足、收获与体会等）；9 参考文献（按公开发表的规范书写）。

时间安排：设计安排一周：周1、周2：完成系统分析及设计。

周3、周4：完成程序调试及测试。

周5：撰写课程设计报告。

设计验收安排：设计周的星期五第1节课开始到实验室进行上机验收。

设计报告书收取时间：设计周的次周星期一上午10点。

指导教师签名： 2010年 11月 23日系主任（或责任教师）签名： 2010年 11月 23日WHILE循环语句的翻译程序设计（递归下降法、输出三地址表示）1任务使用C++语言编写一个while循环语句的翻译程序，使用递归下降法进行语法分析，输出三地址码表示。

编译原理课程实验报告班级学号: 132055222 姓名:实验名称: LL(1)分析一、实验目的：根据某一文法编制调试LL（1）分析程序，以便对任意输入的符号串进行分析。

本次实验的目的主要是加深对预测分析LL（1）分析法的理解。

二、实验要求：对下列文法，用LL（1）分析法对任意输入的符号串进行分析：（1）E->TG（2）G->+TG|—TG（3）G->ε（4）T->FS（5）S->*FS|/FS（6）S->ε（7）F->(E)（8）F->i输出的格式如下：(1)LL（1）分析程序，编制人：姓名，学号，班级(2)输入一以#结束的符号串(包括+—*/（）i#)：在此位置输入符号串(3)输出过程如下：步骤分析栈剩余输入串所用产生式1 E i+i*i# E->TG(4)输入符号串为非法符号串(或者为合法符号串)备注：(1)在“所用产生式”一列中如果对应有推导则写出所用产生式；如果为匹配终结符则写明匹配的终结符；如分析异常出错则写为“分析出错”；若成功结束则写为“分析成功”。

(2) 在此位置输入符号串为用户自行输入的符号串。

(3)上述描述的输出过程只是其中一部分的。

注意：1.表达式中允许使用运算符（+-*/）、分割符（括号）、字符i，结束符#；2.如果遇到错误的表达式，应输出错误提示信息（该信息越详细越好）；三、实验过程：1.模块设计：将程序分成合理的多个模块（函数），每个模块做具体的同一事情。

2.写出（画出）设计方案：模块关系简图、流程图、全局变量、函数接口等。

3.程序编写（1）定义部分：定义常量、变量、数据结构。

Vt：终结符下标映射集。

Vn：非终结符下标映射集。

T ：LL（1）分析表。

Sym：符号栈，it为其栈顶，为方便输出用vector模拟。

In ：输出串。

St ：规约时所用产生式。

（2）初始化：设立LL(1)分析表、初始化变量空间（包括堆栈、结构体、数组、临时变量等）；（3）控制部分：从键盘输入一个表达式符号串；（4）利用LL(1)分析算法进行表达式处理：根据LL(1)分析表对表达式符号串进行堆栈（或其他）操作，输出分析结果，如果遇到错误则显示错误信息。

LL(1)文法分析及程序设计1.设计目的通过设计、编制、调试LL(1)语法分析程序，加深对LL(1) 语法分析原理的理解。

2.设计要求（1）写出符合LL(1)分析方法要求的文法，给出分析的算法思想、步骤、程序结构以及最终完成语法分析程序设计。

（2）编制完成分析程序后，选取几个例子，上机测试并通过所设计的分析程序。

3.设计方案用LL(1)分析法判别给定文法是否为LL(1)文法，提供其分析过程与结果，最终根据结果设计算法分析程序，对输入的符号串进行分析。

4.设计内容4.1 设计基本思想设计一个LL(1)文法分析器，构造出预测分析表，通过预测分析表，判别用户输入的字符串是否符合LL(1)文法。

并给出分析过程与结果。

4.2 LL(1)文法的基本原理与算法一个上下无关的文法是LL(1)文法的充要条件时，对每个非终结符A的两个不同产生式，A->α,A->β满足SELECT（A->α）∩SELECT（A->β）=φ，其中α和β不同时推出ξ。

如果某个文法满足上述条件，称该文法为LL(1)文法。

LL(1)分析法是一种采用确定的自顶向下的语法分析技术，其含义是：第一个L表明自顶向下分析是从左向右扫描输入串，第二个L表明分析过程中将用最左推导，1表明只需向右看一个符号便可以决定如何推导，即便选择哪个产生式规则进行推导。

4.3 LL(1)判别分析步骤(1)将数组X[]中对应的每一个非终结符的标记为“未定”。

(2)扫描文法中的产生式。

1.删除所有右部含有终结符的产生式。

若使得以某一非终结符为左部的所有产生式都被删除，则将数组中对应的非终结符的标记值改为“否”，说明该终结符不能推出ξ。

2.若某一非终结符的某一个产生式右部为ξ，则将数组中对应该非终结符的标志置为“是”，并从文法中删除该非终结符的所有产生式。

（3）扫描产生式右部的每一个符号。

1.若所扫描到的非终结符号在数组中对应的标志是“是”，则删去该非终结符，若使得产生式右部为空，则对产生式右部的非终结符在数组中对应的标志改为“是”，并删除该非终结符为左部的所有的产生式。

青岛科技大学LL(1)分析编译原理实验报告学生班级__________________________学生学号__________________________学生姓名________________________________年 ___月 ___日一、实验目的LL(1)分析法的基本思想是：自项向下分析时从左向右扫描输入串，分析过程中将采用最左推导，并且只需向右看一个符号就可决定如何推导。

通过对给定的文法构造预测分析表和实现某个符号串的分析，掌握LL(1)分析法的基本思想和实现过程。

二、实验要求设计一个给定的LL(1)分析表，输入一个句子，能根据LL(1)分析表输出与句子相应的语法数。

能对语法数生成过程进行模拟。

三、实验内容（1）给定表达式文法为：G(E’): E’→#E# E→E+T | T T→T*F |F F→(E)|i（2）分析的句子为:(i+i)*i四、模块流程五、程序代码#include<iostream>#include<stdio.h>#include <string>#include <stack>using namespace std;char Vt[]={'i','+','*','(',')','#'}; /*终结符*/char Vn[]={'E','e','T','t','F'}; /*非终结符*/ int LENVt=sizeof(Vt);void showstack(stack <char> st) //从栈底开始显示栈中的内容{int i,j;char ch[100];j=st.size();for(i=0;i<j;i++){ch[i]=st.top();st.pop();}for(i=j-1;i>=0;i--){cout<<ch[i];st.push(ch[i]);}}int find(char c,char array[],int n) //查找函数，返回布尔值{int i;int flag=0;for(i=0;i<n;i++){if(c==array[i])flag=1;}return flag;}int location(char c,char array[]) //定位函数,指出字符所在位置，即将字母转换为数组下标值{int i;for(i=0;c!=array[i];i++);return i;}void error(){cout<<" 出错!"<<endl;}void analyse(char Vn[],char Vt[],string M[5][6],string str){int i,j,p,q,h,flag=1;char a,X;stack <char> st; //定义堆栈st.push('#');st.push(Vn[0]); //#与识别符号入栈j=0; //j指向输入串的指针h=1;a=str[j];cout<<"步骤"<<"分析栈"<<"剩余输入串"<<" 所用产生式"<<endl;while(flag==1){cout<<h<<" "; //显示步骤h++;showstack(st); //显示分析栈中内容cout<<" ";for(i=j;i<str.size();i++) cout<<str[i]; //显示剩余字符串X=st.top(); //取栈顶符号放入X if(find(X,Vt,LENVt)==1) //X是终结符if(X==a) //分析栈的栈顶元素和剩余输入串的第一个元素相比较if (X!='#'){cout<<" "<<X<<"匹配"<<endl;st.pop();a=str[++j]; //读入输入串的下一字符}else{ cout<<" "<<"acc!"<<endl<<endl; flag=0;}else{error();break;}else{p=location(X,Vn); //实现下标的转换（非终结符转换为行下标）q=location(a,Vt); //实现下标的转换（终结符转换为列下标）string S1("NULL"),S2("null");if(M[p][q]==S1 || M[p][q]==S2) //查找二维数组中的产生式{error();break;} //对应项为空，则出错else{string str0=M[p][q];cout<<" "<<X<<"-->"<<str0<<endl; //显示对应的产生式st.pop();if(str0!="$") //$代表"空"字符for(i=str0.size()-1;i>=0;i--) st.push(str0[i]);//产生式右端逆序进栈}}}}main(){string M[5][6]={"Te" ,"NULL","NULL","Te", "NULL","NULL","NULL","+Te" ,"NULL","NULL","$", "$","Ft", "NULL","NULL","Ft", "NULL","NULL","NULL","$", "*Ft", "NULL","$", "$","i", "NULL","NULL","(E)", "NULL","NULL"}; //预测分析表j string str;int errflag,i;cout<<"文法：E->E+T|T T->T*F|F F->(E)|i"<<endl;cout<<"请输入分析串（以#结束）："<<endl;do{ errflag=0;cin>>str;for(i=0;i<str.size();i++)if(!find(str[i],Vt,LENVt)){ cout<<"输入串中包含有非终结符"<<str[i]<<"(输入错误)!"<<endl;errflag=1;}} while(errflag==1); //判断输入串的合法性analyse(Vn, Vt, M,str);return 0;}六、实验结果七、实验总结。

LL(1)语法分析器的构造摘要语法分析的主要任务是接收词法分析程序识别出来的单词符由某种号串，判断它们是否语言的文法产生，即判断被识别的符号串是否为某语法部分。

一般语法分析常用自顶向下方法中的LL分析法，采用种方法时，语法分程序将按自左向右的顺序扫描输入的的符号串，并在此过程中产生一个句子的最左推导，即LL是指自左向右扫描，自左向右分析和匹配输入串。

经过分析，我们使用VC++作为前端开发工具，在分析语法成分时比较方便直观，更便于操作。

运行程序的同时不断修正改进程序，直至的到最优源程序。

关键字语法分析文法自顶向下分析 LL(1)分析最左推导AbstractGrammatical analysis of the main tasks was to receive lexical analysis procedure to identify the words from a website, string, and judge whether they have a grammar of the language, that is, judging by the series of symbols to identify whether a grammar part. General syntax analysis commonly used top-down methods of LL analysis, using methods, Grammar hours will be from the procedures of the order left-to-right scanning input string of symbols, and in the process produced one of the most left the sentence is derived, LL is scanned from left to right, From left to right analysis and matching input strings. After analysis, we use VC + + as a front-end development tool for the analysis of syntax ingredients more convenient visual, more easy to operate. Operational procedures at the same time constantly improving procedures, until the source of optimal .Key WordsGrammatical analysis grammar Top-down analysis LL (1) AnalysisMost left Derivation目录摘要 (1)引言 (3)第一章设计目的 (4)第二章设计的内容和要求 (5)2.1 设计内容 (5)2.2 设计要求 (5)2.3 设计实现的功能 (5)第三章设计任务的组织和分工 (6)3.1 小组的任务分工 (6)3.2 本人主要工作 (6)第四章系统设计 (9)4.1 总体设计 (9)4.2 详细设计 (9)第五章运行与测试结果 (22)5.1 一组测试数据 (22)5.2 界面实现情况 (23)第六章结论 (27)课程设计心得 (28)参考文献 (29)致谢 (30)附录（核心代码清单） (31)引言编译器的构造工具是根据用户输入的语言的文法，编译器的构造工具可以生成程序来处理以用户输入的文法书写的文本。

学号：课程设计题目编译原理学院计算机科学与技术专业计算机科学与技术班级姓名指导教师2 年月日课程设计任务书学生姓名：专业班级：指导教师：工作单位：题目: DO-WHILE循环语句的翻译程序设计（LL（1）法、输出三地址表示）初始条件：理论：学完编译课程，掌握一种计算机高级语言的使用。

实践：计算机实验室提供计算机及软件环境。

如果自己有计算机可以在其上进行设计。

要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）（1）写出符合给定的语法分析方法的文法及属性文法。

（2）完成题目要求的中间代码三地址表示的描述。

（3）写出给定的语法分析方法的思想，完成语法分析和语义分析程序设计。

（4）编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。

（5）设计报告格式按附件要求书写。

课程设计报告书正文的内容应包括：1 系统描述（问题域描述）；2 文法及属性文法的描述；3 语法分析方法描述及语法分析表设计；4 按给定的题目给出中间代码形式的描述及中间代码序列的结构设计；5 编译系统的概要设计；6 详细的算法描述（流程图或伪代码）；7 软件的测试方法和测试结果；8 研制报告（研制过程，本设计的评价、特点、不足、收获与体会等）；9 参考文献（按公开发表的规范书写）。

时间安排：设计安排一周：周1、周2：完成系统分析及设计。

周3、周4：完成程序调试及测试。

周5：撰写课程设计报告。

设计验收安排：设计周的星期五第1节课开始到实验室进行上机验收。

设计报告书收取时间：设计周的次周星期一上午10点。

指导教师签名： 2011年 12月 23日系主任（或责任教师）签名： 2011年 12月 23日DO-WHILE语句的翻译程序设计(LL（1）文法输出3地址表达式)1课设的描述1.1课设要求首先按照课程设计的要求，写一个能识别do-while循环语句的文法，并使它符合LL(1)法的要求，按照这个文法编写一个程序，该程序能识别输入的语句是否符合do-while语句的文法，或者通过文法的开始符号能判断是否能推导出该语句。

集美大学计算机工程学院编译原理课程设计报告选题名称:LL（1）文法分析院（系）:计算机工程学院专业:计算机科学与技术班级:计算1412指导教师:付永刚学年学期:2016 ~ 2017 学年第 2 学期2017 年06 月29 日摘要：选题要求：根据某一文法编制调试LL(1) 文法语法分分析程序，以便对任意输入的符号串进行分析。

本次课程设计的目的主要是加深对预测分析LL(1)文法语法分析法的理解。

具体如下：1、对语法规则有明确的定义；2、编写的分析程序能够对给定文法进行正确的语法分析；3、对输入给定的文法，手工计算FIRST、FOLLOW集合和select集合，应能判断识别是否为给定文法的句子，并给出推导过程。

4、对输入给定的文法，由程序自动构造FIRST、FOLLOW集合。

5、对于遇到的语法错误，能够做出简单的错误处理，给出简单的错误提示，保证顺利完成语法分析过程。

关键词：语法分析；FIRST集合；FOLLOW集合；分析表一、设计内容及要求(1) 基于PL/0语言，通过编程判断该文法是否为LL(1)文法；(2)计算出文法的First() Follow()(3)构造相应文法的预测分析表(4)对某个输入句子进行语法分析二、实现原理1．LL(1)文法LL(1)文法是一类可以进行确定的自顶向下语法分析的文法。

就是要求描述语言的文法是无左递归的和无回溯的。

根据LL(1)文法的定义，对于同一非终结符A的任意两个产生式A:=a和A:=b，都要满足：SELECT(A：=a )∩SELECT(A:=b)=Ø。

（1）文法的左递归当一个文法是左递归文法时，采用自顶向下分析法会使分析过程进入无穷循环之中。

所以采用自顶向下语法分析需要消除文法的左递归性。

文法的左递归是指若文法中对任一非终结符A有推导AÞA…，则称该文法是左递归的。

左递归又可以分为直接左递归和间接左递归。

●直接左递归若文法中的某一产生式形如A→Aα，α∈V*，则称该文法是直接左递归的。