LL1实验报告1.设计原理所谓LL（1）分析法，就是指从左到右扫描输入串（源程序），同时采用最左推导，且对每次直接推导只需向前看一个输入符号，便可确定当前所应当选择的规则。
实现LL（1）分析的程序又称为LL（1）分析程序或LL1（1）分析器。
我们知道一个文法要能进行LL（1）分析，那么这个文法应该满足：无二义性，无左递归，无左公因子。
当文法满足条件后，再分别构造文法每个非终结符的FIRST和FOLLOW 集合，然后根据FIRST和FOLLOW集合构造LL（1）分析表，最后利用分析表，根据LL(1)语法分析构造一个分析器。
LL（1）的语法分析程序包含了三个部分，总控程序，预测分析表函数，先进先出的语法分析栈，本程序也是采用了同样的方法进行语法分析，该程序是采用了C++语言来编写，其逻辑结构图如下：LL（1）预测分析程序的总控程序在任何时候都是按STACK栈顶符号X和当前的输入符号a做哪种过程的。
对于任何（X，a），总控程序每次都执行下述三种可能的动作之一：（１）若X = a =‘#’，则宣布分析成功，停止分析过程。
（２）若X = a ‘#’，则把X从STACK栈顶弹出，让a指向下一个输入符号。
（３）若X是一个非终结符，则查看预测分析表M。
若M[A，a]中存放着关于X的一个产生式，那么，首先把X弹出STACK栈顶，然后，把产生式的右部符号串按反序一一弹出STACK栈（若右部符号为ε，则不推什么东西进STACK栈）。
若M[A，a]中存放着“出错标志”，则调用出错诊断程序ERROR。
事实上，LL（1）的分析是根据文法构造的，它反映了相应文法所定义的语言的固定特征，因此在LL（1）分析器中，实际上是以LL（1）分析表代替相应方法来进行分析的。
2.分析LL ( 1) 分析表是一个二维表，它的表列符号是当前符号，包括文法所有的终结和自定义。
的句子结束符号#，它的表行符号是可能在文法符号栈SYN中出现的所有符号，包括所有的非终结符，所有出现在产生式右侧且不在首位置的终结符，自定义的句子结束符号#表项。
中南大学编译原理实验报告班级：计科1205姓名：***学号：**********实验一词法分析程序设计与实现一、实验目的加深对词法分析器的工作过程的理解；加强对词法分析方法的掌握；能够采用一种编程语言实现简单的词法分析程序；能够使用自己编写的分析程序对简单的程序段进行词法分析。
二、实验内容自定义一种程序设计语言，或者选择已有的一种高级语言，编制它的词法分析程序。
词法分析程序的实现可以采用任何一种编程语言和编程工具。
从输入的源程序中，识别出各个具有独立意义的单词，即关键字、标识符、常数、运算符、界符。
并依次输出各个单词的内部编码及单词符号自身值。
（遇到错误时可显示“Error”，然后跳过错误部分继续显示）三、实验要求：1.对单词的构词规则有明确的定义；2.编写的分析程序能够正确识别源程序中的单词符号；3.识别出的单词以<种别码，值>的形式保存在符号表中，正确设计和维护符号表；4.对于源程序中的词法错误，能够做出简单的错误处理，给出简单的错误提示，保证顺利完成整个源程序的词法分析；四、实验步骤1.定义目标语言的可用符号表和构词规则；2.依次读入源程序符号，对源程序进行单词切分和识别，直到源程序结束；3.对正确的单词，按照它的种别以<种别码，值>的形式保存在符号表中；4.对不正确的单词，做出错误处理。
五、设计思路和实现过程本实验是词法分析器，我是用的是MFC实现的，我的设计思路就是按照书上提示的算法，先将几个词法分析器所需的基本函数用C++的形式实现，然后使用循环语句读入输入串的每一个字符，然后用if…else…语句实现，具体判断方式如下：1、如果读入的是字母，那么继续读入，知道读入的字符不是字母或者数字为止，对照标识符表，如果是标识符，则显示该串及对应标识符；如果不是，则显示该串和“$ID”；2、如果读入的是数字，则继续读入，知道不是数字为止，并显示该串和“$INT”；3、如果读入的是“=”，“+”，";",“(”,")","{","}"，则分别输出该串和“$ASSIGN”，"$PLUS"，"$SEMICOLON"，"$LPAR"，"$RPAR"，"$LBRACE"，"$RBRACE"；4、如果读入的是“*”，那么继续读入，如果下一个是“*”，则输出该串和"$POWER"；否则输出该串和"$STAR"，并将指针回退；5、如果独到输入串末尾，则退出。
编译原理词法分析器-ll1-lr0-python实现代码计算机科学与通信工程学院编译原理实验报告题目： 1.词法分析器2. LL(1)分析器3. LR(0)分析器班级：姓名:学号：指导老师：2017年月目录一、实验题目 (1)二、实验目的和要求 (1)三、代码实现 (2)四、总结 (25)一、实验题目1.词法分析器分析一段程序代码，将代码中的单词符号分解出来，并对其进行检查，输出token表和error表2.LL(1)文法分析器分析给定文法。
求出文法的FIRST集，FOLLOW集，并构建分析表，对给定输入串进行分析。
3.LR(0)文法分析器分析给定文法。
用Ꜫ_CLOSURE方法构造文法的LR(0)项目集规范族，根据状态转换函数GO构造出文法的DFA,并转换为分析表，对给定输入串进行分析。
二、实验目的和要求1.学会词法分析器的实现思路。
2.学会求解FIRST集， FOLLOW集，构造LL(1)分析表。
3.学会Ꜫ_CLOSURE方法，状态转换函数GO, 构造LR(0)分析表。
三、代码实现1.词法分析器program.txt 中存放要分析的文法：E->TRR->+TR|-TR|~T->FGG->*FG|/FG|~F->(E)|i代码：KEYWORD_LIST = ['while', 'if', 'else', 'switch', 'case']SEPARATOR_LIST = [';', ':', ',', '(', ')', '[', ']', '{', '}']OPERATOR_LIST1 = ['+', '-', '*']OPERATOR_LIST2 = ['<=', '<', '==', '=', '>', '>=']CATEGORY_DICT = {# KEYWORD"while": {"while": ""},"if": {"if": ""},"else": {"else": ""},"switch": {"switch": ""},"case": {"case": ""},# OPERATOR"+": {"+": ""},"-": {"-": ""},"*": {"*": ""},"<=": {"relop": "LE"},"<": {"relop": "LT"},">=": {"relop": "GE"},">": {"relop": "GT"},"==": {"relop": "EQ"},"=": {"=": ""},# SEPARATOR";": {";": ""},":": {":": ""},",": {",": ""},"(": {"(": ""},")": {")": ""},"[": {"]": ""},"]": {"]": ""},"{": {"{": ""},"}": {"}": ""},}CONSTANTTABLE = []TOKENTABLE = []OPERATORTABLE = []KEYWORDTABLE = []SEPARATORTABLE = []UNDEFINEDTABLE = []# READ FILEdef read_file(path, method):temp_str = ""try:file = open(path, method)for line in file:line = line.replace('\n', " ") temp_str += linetemp_str = str(temp_str)except IOError as e:print(e)exit()finally:file.close()return temp_str.strip() + " "# GETBEdef getbe():global tokengetchar()token = ""return# GETCHARdef getchar():global characterglobal locationwhile all_string[location] == " ":location = location + 1character = all_string[location]return character# LINK TOKENdef concatenation():global tokenglobal charactertoken = token + character# IS NUMBERdef digit():if '0' <= character <= '9':return Truereturn False# IS ALPHABETdef letter():if 'A' <= character <= 'Z' or 'a' <= character <= 'z': return Truereturn False# IS IDENTIFIERdef reserve():if token in KEYWORD_LIST:return CATEGORY_DICT[token]else:return 0# RETRACTdef retract():global locationglobal character# location = location - 1character = ""return# MAIN FUNCTIONdef main():global tokenglobal characters = getchar()getbe()if 'a' <= s <= 'z' or 'A' <= s <= 'Z':while letter() or digit():concatenation()location = location + 1character = all_string[location]retract()c = reserve()if c == 0:TOKENTABLE.append(token)print("这是标识符：{'", token, "':'", TOKENTABLE.index(token), "'}") else:KEYWORDTABLE.append(token)print("这是保留字：", CATEGORY_DICT[token])elif '0' <= s <= '9':while digit():concatenation()location = location + 1character = all_string[location]retract()CONSTANTTABLE.append(token)print("这是常数：{'", token, "':'", CONSTANTTABLE.index(token), "'}") elif s in OPERATOR_LIST1:location = location + 1OPERATORTABLE.append(s)print("这是单操作符：", CATEGORY_DICT[s])elif s in OPERATOR_LIST2:location = location + 1character = all_string[location]if character == '=':OPERATORTABLE.append(s + character)print("这是双操作符：", CATEGORY_DICT[s + character])else:retract()location = location + 1OPERATORTABLE.append(s)print("这是单操作符:", CATEGORY_DICT[s])elif s in SEPARATOR_LIST:location = location + 1SEPARATORTABLE.append(s)print("这是分隔符：", CATEGORY_DICT[s])else:UNDEFINEDTABLE.append(s)print("error:undefined identity :'", s, "'")if __name__ == '__main__':character = ""token = ""all_string = read_file("program.txt", "r")location = 0while location + 1 < len(all_string):main()print('KEYWORDTABLE:', KEYWORDTABLE)print('TOKENTABLE:', TOKENTABLE)print('CONSTANTTABLE:', CONSTANTTABLE)print('OPERATORTABLE:', OPERATORTABLE)print('SEPARATORTABLE:', SEPARATORTABLE)运行结果：2.LL(1)分析器program.txt 中存放要分析的文法：E->TRR->+TR|-TR|~T->FGG->*FG|/FG|~F->(E)|i输入串：i+i*i代码：NonTermSet = set() # 非终结符集合TermSet = set() # 终结符集合First = {} # First集Follow = {} # Follow集GramaDict = {} # 处理过的产生式Code = [] # 读入的产生式AnalysisList = {} # 分析表StartSym = "" # 开始符号EndSym = '#' # 结束符号为“#“Epsilon = "~" # 由于没有epsilon符号用“~”代替# 构造First集def getFirst():global NonTermSet, TermSet, First, Follow, FirstAfor X in NonTermSet:First[X] = set() # 初始化非终结符First集为空for X in TermSet:First[X] = set(X) # 初始化终结符First集为自己Change = Truewhile Change: # 当First集没有更新则算法结束Change = Falsefor X in NonTermSet:for Y in GramaDict[X]:k = 0Continue = Truewhile Continue and k < len(Y):if not First[Y[k]] - set(Epsilon) <= First[X]: # 没有一样的就添加，并且改变标志if Epsilon not in First[Y[k]] and Y[k] in NonTermSet and k > 0: # Y1到Yi候选式都有~存在Continue = Falseelse:First[X] |= First[Y[k]] - set(Epsilon)Change = Trueif Epsilon not in First[Y[k]]:Continue = Falsek += 1if Continue: # X->~或者Y1到Yk均有~产生式First[X] |= set(Epsilon)# FirstA[Y] |= set(Epsilon)# 构造Follow集def getFollow():global NonTermSet, TermSet, First, Follow, StartSymfor A in NonTermSet:Follow[A] = set()Follow[StartSym].add(EndSym) # 将结束符号加入Follow[开始符号]中Change = Truewhile Change: # 当Follow集没有更新算法结束Change = Falsefor X in NonTermSet:for Y in GramaDict[X]:for i in range(len(Y)):if Y[i] in TermSet:continueFlag = Truefor j in range(i + 1, len(Y)): # continueif not First[Y[j]] - set(Epsilon) <= Follow[Y[i]]:Follow[Y[i]] |= First[Y[j]] - set(Epsilon) # 步骤2 FIRST(β)/~ 加入到FOLLOW(B)中。
学生学号实验课成绩武汉理工大学学生实验报告书实验课程名称《编译原理》开课学院计算机科学与技术学院指导老师姓名何九周学生姓名小灰灰的爸爸学生专业班级中国好学长系列2013 —2014 学年第一学期实验课程名称：编译原理实验项目名称单词的词法分析器的设计实验成绩实验者专业班级组别同组者实验日期年月日第一部分：实验分析与设计（可加页）一、实验内容描述（问题域描述）1．实验目的：设计，编制并调试一个词法分析程序，加深对词法分析原理的理解。
2．实验要求要求：在上机前应认真做好各种准备工作，熟悉机器的操作系统和语言的集成环境，独立完成算法编制和程序代码的编写；上机时应随带有关的高级语言教材或参考书；要学会程序调试与纠错；每次实验后要交实验报告。
3．实验报告的内容（1）实验题目、班级、学号、姓名、完成日期；（2）待分析的某种语言子集的词法描述；（3）词法分析程序的功能；（4）详细的算法描述；（5）程序清单；（6）运行结果(给3组典型输入数据进行测试)；（7）收获与体会。
二、实验基本原理与设计（包括实验方案设计，实验手段的确定，试验步骤等，用硬件逻辑或者算法描述）1．待分析的简单语言的词法：（1）关键字：bengin if then while do end所有的关键字都是小写。
（2）运算符和界符：：= + - * / < <= <> > >= = ; ( ) #（3）其他单词是标志符（ID）和整形常数（NUM），通过以下正规式定义：ID=letter（letter|digit）* NUM=digit digit*（4）空格空白、制表符和换行符组成。
空格一般用来分隔ID、NUM、运算符、界符和关键字，词法分析阶段通常被忽略。
2．各种单词符号对应的种别码单词符号种别码单词符号种别码begin 1 ：17if 2 ：= 18then 3 < 20while 4 <> 21do 5 <= 22end 6 > 23 Letter(letter|digit) 10 >= 24digit digit * 11 = 25 + 13 ; 26- 14 ( 27* 15 ) 28/ 16 # 03．实验源代码如下：#include<stdio.h>#include<string.h>char prog[80],token[6];char ch;int syn,p,m,n,sum;char * rwtab[6]={"begin","if","then","while","do","end"};main(){p=0;printf("\nplease intput string:");do{ch=getchar();prog[p++]=ch;}while(ch!='#');p=0;do{scaner();switch(syn){case 11:printf("(%d,%d)\n",syn,sum);break;case -1:printf("input error\n"); break;default:printf("(%d,%s)\n",syn,token);}}while(syn!=0);getch();}scaner(){for(n=0;n<8;n++)token[n]=NULL;m=0;ch=prog[p++];while(ch==' ')ch=prog[p++];if((ch<='z'&&ch>='a')||(ch<='Z'&&ch>='A')){while((ch<='z'&&ch>='a')||(ch<='Z'&&ch>='A')||(ch<='9'&&ch>='0')) {token[m++]=ch;ch=prog[p++];}token[m++]='\0';ch=prog[--p];syn=10;for(n=0;n<6;n++)if(strcmp(token,rwtab[n])==0){syn=n+1;break;}}elseif((ch<='9'&&ch>='0')){sum=0;while((ch<='9'&&ch>='0')){sum=sum*10+ch-'0';ch=prog[p++];}ch=prog[--p];syn=11;}elseswitch(ch){case '<':m=0;token[m++]=ch;ch=prog[p++];if(ch=='>'){syn=21;token[m++]=ch;}elseif(ch=='='){syn=22;token[m++]=ch;}else{syn=20;ch=prog[--p];}break;case '>':token[m++]=ch;ch=prog[p++];if(ch=='='){syn=24;token[m++]=ch;}else{syn=23;ch=prog[--p];}break;case ':':token[m++]=ch;ch=prog[p++];if(ch=='='){syn=18;token[m++]=ch;}else{syn=17;ch=prog[--p];}break;case '+':syn=13;token[0]=ch;break; case '-':syn=14;token[0]=ch;break; case '*':syn=15;token[0]=ch;break; case '/':syn=16;token[0]=ch;break;case ':=':syn=18;token[0]=ch;break;case '<>':syn=21;token[0]=ch;break;case '<=':syn=22;token[0]=ch;break;case '>=':syn=24;token[0]=ch;break;case '=':syn=25;token[0]=ch;break;case ';':syn=26;token[0]=ch;break;case '(':syn=27;token[0]=ch;break;case ')':syn=28;token[0]=ch;break;case '#':syn=0;token[0]=ch;break;default:syn=-1;}}三、主要仪器设备及耗材PC机一台，Miscrosoft VisualC++6.0第二部分：实验调试与结果分析（可加页）一、调试过程（包括调试方法描述、实验数据记录，实验现象记录，实验过程发现的问题等）按照要求编写完代码之后，首先检查一下有没有错误语法错误，然后编译连接运行，输入所给文法的源程序字符串，经此法分析之后，程序就会输出如下结果所示的二元组构成的序列：二、实验结果及分析（包括结果描述、实验现象分析、影响因素讨论、综合分析和结论等）（1）输入字符串begin x:=9; if x>0 then x:= 2*x+1/3; end #其结果如下图所示（2）输入字符串hello#其输出结果如下图所示：（3）输入字符串if x>2; y=3; end #其结果如下图所示：三．实验小结、建议及体会词法分析是编译的第一个阶段，它的主要任务是从左至右逐个字符地对源程序进行扫描，产生一个单词序列，用以语法分析，执行词法分析的程序成为词法分析程序或扫描程序。
