第一篇:编译原理实验二(设计一个词法分析器)
编译原理实验二
1.实验名称:一个简单语言词法分析器设计
2.实验内容
(1)阅读并理解教材第三章词法分析p42“简单语言”词法分析构造实例
(2)完善P45给出的“简单语言”词法分析程序,使得该程序能够在计算机上运行,完
全达到词法分析器的设计基本要求:
① 读入“简单语言”源程序
②滤掉“简单语言”源程序中的“空白”字符
③滤掉“简单语言”源程序中的“注释”字符
④能够识别出“简单语言”源程序中的合法“单词”并输出识别出的一个个“单词”符号序列。
⑤ 识别出的一个个“单词”符号要求为二元组形式: 指出单词类别属性,标识符自身值,常数值.3.提交实验报告
“简单语言”词法分析程序“源程序”文件
“简单语言”词法分析程序“源程序”可执行文件
对“简单语言”词法分析程序的测试实例:“简单语言”源程序及其词法分析结果。
第二篇:《编译原理》课程设计报告--词法分析器
201X-201X学年第x学期
《编译原理》课程设计报告
院 系: 计算机科学与技术 班 级: XX级XX 班 学生姓名: XXXXXX 学 号: XXXXXXXX 指导老师: XXXXXX
计算机科学与技术学院监制
20XX年X月
目录
1.课程设计的目的 2.课程设计的内容和要求 3.问题分析和相关知识介绍 4.设计思路和关键问题及其解决方案 5.测试和结果分析 6.总结和心得体会
附件1:参考文献 附件2:核心源代码
1.课程设计的目的(1)编写词法分析器
(2)加深对词法分析器工作原理的了解和认识
2.课程设计的内容和要求
编写词法分析器,词法分析器能够识别关系算符,词法分析器能够识别标识符和关键字,词法分析器能够识别无符号数。
3.问题分析和相关知识介绍
构成词法分析器的一种简单方法是用状态转换图来描述源语言词法记号的结构,然后手工把这种状态转换图翻译成为识别词法记号的程序。词法分析器的任务是把构成源程序的字符流翻译成词法记号流。
4.设计思路和关键问题及其解决方案
把自然语言构造成正规式,把正规式构造成有限自动机NFA,然后根据子集构造法把有限自动机构造成无限自动机DFA,根据极小化DFA状态数算法把DFA构造成最简DFA,其次根据最简DFA画出转换表,根据转换表画出装换图,最后根据装换图就可以编写词法分析器。
5.测试和结果分析
6.总结和心得体会
通过本次试验,不仅仅是我学会了C#基础知识,而且还是我对词法分析器有了更深入的认识,虽然在编写词法分析器过程中遇到了很多困难,例如:C#语言不熟悉,对此法分析器的工作原理分析的不透彻,但在老师和同学的帮助下,我有了很大的提高,通过不断的努力最终顺利的完成了课程设计,很感谢帮助我的XX同学和XX老师。附件1:参考文献
《编译原理(第2版)》 高等教育出版社; 《C#程序设计及应用教程(第2版)》 人民教育出版社。附件2:
1.Code文档截图
2.程序源代码
using System;using System.Collections.Generic;using System.Text;using System.IO;
namespace LexicalAnalysis { class Program { static string[] keys = { “static”, “true”, “return”, “string”, “Length”, “break”, “Console”, “WriteLine”, “bool”, “false”, “ture”, “void”, “if”, “else”, “while”, “int”, “float”, “for”, “enum”, “default”, “case”, “double”, “do” };
static List
static List
static List
static List
static List
//数字,标识符,空白,关系符,运算符
static void Main(string[] args){
string[] date = File.ReadAllLines(@“d:code.txt”);//路径,并存入data
for(int i = 0;i < date.Length;i++){ Console.WriteLine(“第” +(i + 1)+ “行code: ” + date.GetValue(i));analysisByLine(date[i]);
} //分别输出存储在四个List中的String
Console.WriteLine(“关键字,输入回车”);//输出所有的关键字 Console.ReadLine();
foreach(string id in key){ Console.WriteLine(id);
}
Console.WriteLine(“标识符,输入回车”);//输出所有的标识符
Console.ReadLine();foreach(string id in bsf){ Console.WriteLine(id);
}
Console.WriteLine(“数字,输入回车”);Console.ReadLine();foreach(string id in sz){ Console.WriteLine(id);
}
Console.WriteLine(“关系运算符,输入回车”);Console.ReadLine();foreach(string id in gx){ Console.WriteLine(id);
}
Console.WriteLine(“算数运算符,输入回车”);Console.ReadLine();foreach(string id in ys){ Console.WriteLine(id);
}
Console.WriteLine(“输入回车退出”);
Console.ReadLine();
} static void analysisByLine(string code)
//输出所有的数字 //输出所有的关系运算符//输出所有的算数运算符
{
char a = ' ';string temp = “";int j = 0;while(j < code.Length){ a = code[j];temp = ”“;if(Char.IsLetter(a)|| a == '_')//是否为标识符 { temp = temp + a.ToString();j++;a = code[j];while(Char.IsLetterOrDigit(a)){ temp = temp + a.ToString();j++;a = code[j];} if(isKey(temp)){
//Console.WriteLine(”保留字:“+temp);
if(!key.Contains(temp)){ // Console.WriteLine(”添加成功“);key.Add(temp);}
} else {
//Console.WriteLine(”标识符:“+temp);
if(!bsf.Contains(temp)){ //Console.WriteLine(”添加成功标识符==“);bsf.Add(temp);} }
} else if(Char.IsDigit(a)){ temp = temp + a.ToString();j++;a = code[j];while(Char.IsDigit(a)){ temp = temp + a.ToString();j++;a = code[j];
} //判断是否是小数
if(a.Equals('.')){ temp = temp + a.ToString();j++;a = code[j];while(Char.IsDigit(a)){ temp = temp + a.ToString();j++;a = code[j];} //判读是否是科学记数法
if(a.Equals('E')|| a.Equals('e')){ temp = temp + a.ToString();j++;a = code[j];while(Char.IsDigit(a)){
temp = temp + a.ToString();j++;a = code[j];} }
}
// Console.WriteLine(”数字:“+temp);if(!sz.Contains(temp)){ //Console.WriteLine(”添加成功标识符==“);sz.Add(temp);} } else if(a == '<'){ temp = temp + a.ToString();j++;a = code[j];if(a == '='){ temp = temp + a.ToString();j++;a = code[j];} else if(a == '>'){ temp = temp + a.ToString();j++;a = code[j];} //Console.WriteLine(”关系符“+temp);if(!gx.Contains(temp)){ //Console.WriteLine(”添加成功标识符==“);gx.Add(temp);} } else if(a == '='){ temp = temp + a.ToString();j++;
a = code[j];// Console.WriteLine(”关系符“+temp);if(!gx.Contains(temp)){ //Console.WriteLine(”添加成功关系==“);gx.Add(temp);} } else if(a == '>'){ temp = temp + a.ToString();j++;a = code[j];if(a == '='){ temp = temp + a.ToString();j++;a = code[j];}
// Console.WriteLine(”关系符“+temp);if(!gx.Contains(temp)){ //Console.WriteLine(”添加成功标识符==“);gx.Add(temp);}
} else { if(a == '+' || a == '-' || a == '/' || a == '*'){ temp = temp + a.ToString();j++;a = code[j];//Console.WriteLine(”运算符“+temp);if(!ys.Contains(temp)){ //Console.WriteLine(”添加成功标识符==“);ys.Add(temp);} } else
{ j++;}
} } }
//判断是不是保留字的IsKey方法
static bool isKey(string key){
bool flag = false;for(int i = 0;i < keys.Length;i++)
if(keys[i] == key){ flag = true;//Console.WriteLine(key+”是不是key“+flag);break;} else { flag = false;
} //Console.WriteLine(key+”是不是key“);// Console.WriteLine(flag+”是不是key");return flag;
} } }
第三篇:实验一词法分析器的设计与实现
实验一词法分析器的设计与实现
一、实验目的1.了解并掌握词法分析器的原理及工作过程
2.理解词法分析器的状态图表示方法
二、实验内容
用适当的程序设计语言编制一个词法分析程序,并完成相应的调试,要求该程序能够从指定的文件中读入源程序,并将此源程序变成语义等价的单词序列,输出单词序列。
提示:
1.源程序可限定为某个语言的子语言,如C语言的子集,允许源程序中有注释行,其中的关键字自行设定,可参见书66页的编码表,保留字表为词法分析器已知的表格(可采用二维数组的形式存储)
2.参考程序见书中104-105页,程序中涉及的gettoken()和install_id()两个过程的解释见91页上面3段的说明。
3.词法分析器的输入输出示例:
输入:if(i>10)then i=0
输出:
(10, if)
(20,()
(50,i)
(21,>)
(51,10)
(22,))
(11,then)
(50,i)
(23,=)
(51,0)
其中:50代表标识符的编码,51代表常量的编码
第四篇:编译原理课程设计 LL递归下降分析器
仲恺农业技术学院
编译原理课程设计
课程设计题目 :LL(1)递归下降分析器
姓
名 : 院(系):
专业班级 : 学
号 :
指导教师 :
设计日期 :
目 录
1、需求分析...................................................................................................1
2、概要设计...................................................................................................2
3、详细设计...................................................................................................3
4、测试分析...................................................................................................8
5、用户手册...................................................................................................9
6、课程总结...................................................................................................9
7、参考文献.................................................................................................10
题目:LL(1)递归下降分析器
1、需求分析
语法分析是编译过程的核心部分。语法分析器的任务是识别和处理比单词更大的语法单位。如:程序设计语言中的表达式,各种说明和语句乃至全部源程序,指出其中的语法错误;必要时,可生成内部形式,便于下一阶段处理。
我们知道,语言的语法结构是用上下文无关文法描述的。按照语法分析树的建立方法,我们可以粗略地把语法分析办法分成两类,一类是自上而下分析,另一类是自下而上分析法。而自上而下这种方法是带“回溯”的,且存在许多困难和缺点。
首先,是文法的左递归性问题。一个文法是含有左递归的,如果存在非终结符P且PP,含有左递归的文法使上述的自上而下的分析过程陷入无限循环。即,当试图用P去匹配输入串时,我们会发现,在没有识别任何输入符号的情况下,有得重新要求P去进行新的匹配。因此,使用自上而下分析法必须消除文法的左递归性。
其次,由于回溯,就碰到一大堆麻烦问题。如果我们走了一大段错路,最后必须回头,那么,就应把已经做的一大堆语义工作(指中间代码产生工作和各种表格的簿记工作)推倒重来。这些事情既麻烦又费时间,所以,最好应设法消除回溯。
第三,在自上而下分析过程中,当一个非终结符用某一候选匹配成功时,这种成功可能仅是暂时的。
第四,当最终报告分析不成功时,我们难于知道输入串中出错的确切位置。
最后,由于带回溯的自上而下分析实际上采用了一种穷尽一切可能的试探法,因此,效率很低,代价极高。严重的低效使得这种分析法只有理论意义,而在实践上价值不大。
由于上述原因,我们需要把原算术表达式改写为LL(1)文法,LL(1)文法的文法条件如下: 文法不含左递归。
对于文法中每一个非终结符A的各个产生式的候选首集符两两不相交。即,若A1|2||n,则FIRSTiFIRSTj ij
对文法中的每个非终结符A,若它存在某个候选首符集包含ε,则FIRSTAFOLLOWA
LL(1)中的第一个L表示从左到右扫描输入串,第二个L表示最左推导,1表示分析时每 一步只需向前查看一个符号。当一个文法满足LL(1)条件时,我们就可以为它构造一个不带回溯的自上而下分析程序,这个分析程序是由一组递归过程组成的,每个过程对应文法的一个非终结符。这样的一个分析程序称为递归下降分析器。
2、概要设计
编程实现给定算术表达式的递归下降分析器。算术表达式文法如下: E-->E+T|E-T|T T-->T*F|T/F|F F-->(E)| i 首先改写文法为LL(1)文法;然后为每一个非终结符,构造相应的递归过程,过程的名字表示规则左部的非终结符;过程体按规则右部符号串的顺序编写。
上述算法表达式文法属于比较典型的递归下降语法分析。需要先将原算术表达式方法改写为LL(1)文法为:
E-->TE’
E’-->+TE’|-TE’| ε T-->FT’
T’-->*FT’|/FT’| ε F-->(E)| i 然后再为每个非终结符设计一个对应的函数,通过各函数之间的递归调用从而实现递归下降语法分析的功能。
具体方法为:
(1)当遇到终结符a时,则编写语句
If(当前读到的输入符号==a)读入下一个输入符号(2)当遇到非终结符A时,则编写语句调用A()。(3)当遇到A-->ε规则时,则编写语句
If(当前读到的输入符号不属于Follow(A))error()(4)当某个非终结符的规则有多个候选式时,按LL(1)文法的条件能唯一地选择一个候选式进行推导.递归下降子程序流程图:
图1递归下降子程序流程图
3、详细设计
#include
void main(){
}
void e(){
}
void e1()right=1;cout<<“--------------------”< } void t(){ } if(inputstream[temp]=='+'){ } else if(inputstream[temp]=='-'){ } else if(inputstream[temp]!='#'||inputstream[temp]!=')'){ } else right=0;cout<<“T'->^”< if(inputstream[temp]=='*'){ } else if(inputstream[temp]=='/'){ } else cout<<“T'->/FT'”< } void f(){ { } cout<<“T'->^”< } } else if(inputstream[temp]=='('){ cout<<“F->(E)”< } else } right=0;cout<<“F->(E)”< 4、测试分析 图2 测试分析成功 图3 测试分析失败 5、用户手册 开发工具:visual c++ 6.0 开发环境:windows XP操作系统 运行环境:windows 9x,windows NT,Windows 2000,windows XP 注意:输入时,程序最多只能接受50个字符,输入完算术表达式后要以“#”号结束。 6、课程总结 通过一个星期的努力,终于把编译原理课程设计给完成了。我觉得编译原理这门课是一门非常难学的课程,它涉及文法、词法分析、语法分析属性文法和语义分析等等一系列内容,课本里的内容和定义也非常的抽象且枯燥。如果上课没有好好的认真听课,自己独自学习就感到非常的吃力,而且效果也不好。本人因为上课无法做到打醒十二分专心听课,经常会分神,所以学习的效果也不怎么好。这也给做编译原理课程设计带来了困难。本次课程设计,我选的课程设计题目是LL(1)递归下降分析器,这个题目涉及的内容有关课本第四章 语法分析——自上而下分析里面的内容。在开始动手对题目进行设计和编程之前,我重复的仔细认真的阅读和理解课本第四章里面的内容,弄懂自上而下分析面临的问题、何谓左递归,搞清楚如何消除左递归、如何消除回溯、提左因子,理解构造LL(1)文件需要什么条件。虽然这花费了一定的时间和精力,但那点付出也是值得的,通过复习让我加深理解了有关自上而下语法分析的内容,而且也为用高级语言实现递归下降分析器带来便利。 在用C++编程时,基本上没有遇到什么困难,只需把所有递归过程都写出就行了。但是要注意的是,在编写代码时,要根据LL(1)文法的工作原理去设计。通过本次课程设计清楚地了解到递归下降分析法的优缺点,其优点是简单、直观,易于构造分析程序。缺点是对文法要求高,必须是LL(1)文法,同时由于递归调用较多,影响分析器的效率。 课程设计虽然只有短短的一周,但让我认识到学习好编译原理,是对程序设计和编译的一个很好的进化桥梁和奠基石。今后学习的日子还很长,希望通过这次编译原理的课程设计,不仅对编程语言的进一步复习,还是对更深层次的学习作一个简单的准备。编程的能力不是一朝一夕能锻炼出来,坚持学习,坚持编程的学习,多看,多编是最好的学习和提高方法。 通过本次编译原理课程设计,对面向对象的定义又有了更深一步的理解,对编译程序有了进一步的理解,同时也认识到自己各方面知识的薄弱点,以后在学习中也能有针对性对这方面进行深入学习。学习更好的知识重在基础,编译原理的学习为我们提供非常好的桥梁和道路。 7、参考文献 《编译原理》 机械工业出版社出版 Alfred V.Aho Ravi Sethi Jeffrey D,Ullman著 李建中 姜守旭等译 《程序设计语言 编译原理(第三版)》 国防工业出版社出版 陈火旺 刘春林 谭庆平赵克佳 刘越 著 实验二 语法分析器 一、实验目的 通过完成预测分析法的语法分析程序,了解预测分析法和递归子程序法的区别和联系。使学生了解语法分析的功能,掌握语法分析程序设计的原理和构造方法,训练学生掌握开发应用程序的基本方法。有利于提高学生的专业素质,为培养适应社会多方面需要的能力。 二、实验内容 根据某一文法编制调试 LL(1)分析程序,以便对任意输入的符号串进行分析。 构造预测分析表,并利用分析表和一个栈来实现对上述程序设计语言的分析程序。 分析法的功能是利用LL(1)控制程序根据显示栈栈顶内容、向前看符号以及LL(1)分析表,对输入符号串自上而下的分析过程。 三、LL(1)分析法实验设计思想及算法 模块结构: (1)定义部分:定义常量、变量、数据结构。 (2)初始化:设立LL(1)分析表、初始化变量空间(包括堆栈、结构体、数组、临时变量等); (3)控制部分:从键盘输入一个表达式符号串; (4)利用LL(1)分析算法进行表达式处理:根据LL(1)分析表对表达式符号串进行堆栈(或其他)操作,输出分析结果,如果遇到错误则显示错误信息。 四、实验要求 1、编程时注意编程风格:空行的使用、注释的使用、缩进的使用等。 2、如果遇到错误的表达式,应输出错误提示信息。 3、对下列文法,用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 输出的格式如下: 五、实验源程序 LL1.java import java.awt.*;import java.awt.event.*;import javax.swing.*;import javax.swing.table.DefaultTableModel;import java.sql.*;import java.util.Vector;public class LL1 extends JFrame implements ActionListener { /** * */ private static final long serialVersionUID = 1L;JTextField tf1;JTextField tf2;JLabel l;JButton b0;JPanel p1,p2,p3;JTextArea t1,t2,t3;JButton b1,b2,b3;JLabel l0,l1,l2,l3,l4;JTable table;Statement sta;Connection conn;ResultSet rs;DefaultTableModel dtm;String Vn[]=null;Vector int firstComplete[]=null;//存储已判断过first的数据 char first[][]=null;//存储最后first结果 int followComplete[]=null;//存储已判断过follow的数据 char follow[][]=null;//存储最后follow结果 char select[][]=null;//存储最后select结果 int LL=0;//标记是否为LL(1)String vt_tou[]=null;//储存Vt Object shuju[][]=null;//存储表达式数据 char yn_null[]=null;//存储能否推出空 LL1(){ setLocation(100,0);setSize(700,780);tf1=new JTextField(13);tf2=new JTextField(13);l=new JLabel(“>>”);l0=new JLabel(“输入字符串:”);l1=new JLabel(“输入的文 法”);l2=new JLabel(“ ”);l3=new JLabel(“ 分 析的结”);l4=new JLabel(“预测 分 析”);//p1=new JPanel(); p2=new JPanel();p3=new JPanel();t1=new JTextArea(24,20);t2=new JTextArea(1,30);t3=new JTextArea(24,40);b0=new JButton(“确定(S为开始)”);b1=new JButton(“ 判断文法 ”); 为 :果:表 : b2=new JButton(“输入”);b3=new JButton(“清空”);table=new JTable();JScrollPane jp1=new JScrollPane(t1);JScrollPane jp2=new JScrollPane(t2);JScrollPane jp3=new JScrollPane(t3);p2.add(tf1);p2.add(l);p2.add(tf2); p2.add(b0);p2.add(b1);p2.add(l0);p2.add(l2);p2.add(jp2);p2.add(b2);p2.add(b3); p2.add(l1);p2.add(l3);p2.add(jp1);p2.add(jp3); p3.add(l4);p3.add(new JScrollPane(table));add(p2,“Center”);add(p3,“South”); b0.addActionListener(this);b1.addActionListener(this);b2.addActionListener(this);b3.addActionListener(this);setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);table.setPreferredScrollableViewportSize(new Dimension(660,200));setVisible(true);} public void actionPerformed(ActionEvent e){ if(e.getSource()==b0){ String a=tf1.getText();String b=tf2.getText();t1.append(a+'→'+b+'n');} if(e.getSource()==b1){ t3.setText(“");int Vnnum=0,k;Vn=new String[100];P=new Vector return;} if(s[i].charAt(0)<='Z'&&s[i].charAt(0)>='A'&&s[i].charAt(1)=='→'){ for(k=0;k if((flag=add_First(first[i],Vn[i],firstVn,flag))==-1)return;firstComplete[i]=1;} t3.append(”first集:“+”n“);//显示FIRST** for(int i=0;Vn[i]!=null;i++){ t3.append(”first(“+Vn[i]+”)={ “);for(int j=0;first[i][j]!=' ';j++){ t3.append(first[i][j]+” , “);} t3.append(”}“+”n“);} follow=new char[Vnnum][100];String followVn[]=null;followComplete=new int[Vnnum];for(int i=0;Vn[i]!=null;i++)//求FOLLOW** { flag=0;followVn=new String[20]; if((flag=tianjiaFollow(follow[i],Vn[i],followVn,flag))==-1)return;followComplete[i]=1;} t3.append(”follow集:“+”n“);//显示FOLLOW** for(int i=0;Vn[i]!=null;i++){ t3.append(”follow(“+Vn[i]+”)={ “);for(int j=0;follow[i][j]!=' ';j++){ t3.append(follow[i][j]+” , “);} t3.append(”}“+”n“);} select=new char[P.size()][100];for(int i=0;i tianjiaSelect(select[i],(String)P.elementAt(i),flag);} t3.append(”select集:“+”n“);//显示SELECT** for(int i=0;i for(int i=0;Vn[i]!=null;i++)//判断select交集是否为空 { int biaozhi=0;char save[]=new char[100];for(int j=0;j if(t.substring(0,1).equals(Vn[i])){ for(k=0;select[j][k]!=' ';k++){ if(puanduanChar(save,select[j][k])){ save[biaozhi]=select[j][k];biaozhi++;} else//当有交集时,不为LL(1)文法 { t3.append(”不是LL(1)文法!“+”n“);return;} } } } } char Vt[]=new char[100];int biaozhi=0;for(int i=0;i { if(t.charAt(j)>'Z'||t.charAt(j)<'A'){ if(puanduanChar(Vt,t.charAt(j))){ Vt[biaozhi]=t.charAt(j);biaozhi++;} } } } if(puanduanChar(Vt,'#'))//若可推出空集,则将#加入Vt。{ Vt[biaozhi]='#';biaozhi++;} vt_tou=new String[biaozhi+1];//根据select和表达式生成预测分析表 shuju=new String[Vnnum][biaozhi+1];String f=”“;vt_tou[0]=f;for(int i=0;i if(e.getSource()==b2)//输入字符串并预测分析 { t3.setText(”“);if(LL==1){ String s=t2.getText();for(int i=0;i第五篇:编译原理 语法分析器 (java完美运行版)