文档库

最新最全的文档下载
当前位置:文档库 > 编译原理课程设计报告 算符优先分析表

编译原理课程设计报告 算符优先分析表

课程设计(论文)任务书

软件学院学院软件工程专业07-1班

一、课程设计(论文)题目算符优先分析表生成模拟

二、课程设计(论文)工作自2010年6月20 日起至 2010 年6月25日止。

三、课程设计(论文) 地点:

四、课程设计(论文)内容要求:

1.本课程设计的目的

1、使学生增进对编译原理的认识,加强用程序设计语言实现编译算法能力。

2、进一步培养学生编译器设计的思想,加深对编译原理和应用程序的理解,针对编译过程的重点和难点内容进行编程,独立完成有一定工作量的程序设计任务,同时强调好的程序设计风格,并综合使用程序设计语言、数据结构和编译原理的知识,熟悉使用开发工具VC6.0 或JA V A。

2.课程设计的任务及要求

1)基本要求:

动态模拟算法的基本功能是:

(1)输入一个给定文法,及FIRSTVT和LASTVT集;

(2)输出算符优先分析表生成算法;

(3)输出算法优先分析表构造过程的过程。

2)课程设计论文编写要求

1)要按照书稿的规格打印誊写课设报告;

2)报告分为封面、课程设计任务书(本文档)分析、总结和附录;

3)报告正文包括以下部分:

①问题描述:题目要解决的问题是什么;

②分析、设计、实现:解决问题的基本方法说明,包括主要算法思想,算法的流程图,程序中主要函数或过程的功能说明;

④运行结果分析:分析程序的运行结果是否正确以及出现的问题;

⑤总结:遇到的主要问题是如何解决的、对设计和编码的回顾讨论和分析、进一步改进设想、经验和体会等;

⑥附录,包括源程序清单和运行结果。

学生签名:

2009 年6 月25 日

课程设计(论文)评审意见

(1)编译器思想的正确性(20分):优()、良()、中()、一般()、差();

(2)程序实现的正确性(20分):优()、良()、中()、一般()、差();

(3)程序功能的完善程度(20分):优()、良()、中()、一般()、差();

(4)学生的态度(20分):优()、良()、中()、一般()、差();

(5)课程设计报告(20分):优()、良()、中()、一般()、差();

(6)格式规范性、设计态度及考勤是否降等级:是()、否()

评阅人:职称:教授

2010 年6月28 日

目录

一、课设题目 (4)

二、概要设计 (5)

三、详细设计 (7)

四、运行结果……………………………………………………

五、总结…………………………………………………………

六、附录…………………………………………………………

一、课设题目

1、问题描述

设计一个给定文法和对应FIRSTVT和LASTVT集,能依据依据文法和FIRSTVT和LASTVT生成算符优先分析表。(算法参见教材)

2、基本要求

动态模拟算法的基本功能是:

(1)输入一个给定文法,及FIRSTVT和LASTVT集;

(2)输出算符优先分析表生成算法;

(3)输出算法优先分析表构造过程的过程;

3、测试数据

输入文法:

E->TE’

E’->+TE’|ε

T->FT’

T’->*FT’|ε

F->(E)|i

二、概要设计

用结构体数组存储多行正规式,用LIST控件显示算法,用CDC类依据进行算法进行作图。并实现算法与生成过程的关联。

根据已知优先文法构造相应优先关系矩阵,并将文法的产生式保存,设置符号栈S,算法步骤如下:

1、将输入符号串a1a2a3...an#依次逐个存入符号栈S中,直到遇到栈顶符号ai的优先性>下一个待输入符号aj时为止。

2、栈顶当前符号ai为句柄尾,由此向左在栈中找句柄的头符号ak,即找到ak-1

3、由句柄ak...ai在文法的产生式中查找右部为ak...ai 的产生式,若找到则用相应左部代替句柄,若找不到则为出错,这时可断定输入串不是该文法的句子。

重复这三步,直到归约完输入符号串,栈中只剩文法的开始符号为止。

求出该文法的优先关系表,在程序中用2维数组表示,-1表示小于或者等于,大于为1,其它为0表示错误。

在输入一串字符串以后进行按照文法一步一步的进行规约,我所进行的是直接规约到文法的符号而不是规约到N。

数据结构使用的是链表,用一个STRUCT来表示一个元素,其中包含符号和下一个符号的指针。

计算优先符关系,

1) ‘=‘关系

直接看产生式的右部,若出现了

A →…ab…或A →…aBb,则a=b

2)’<‘关系

求出每个非终结符B的FIRSTVT(B)

若A→…aB…,则b∈FIRSTVT(B),a’关系

求出每个非终结符B的LASTVT(B)

若A→…Bb…,则a∈LASTVT(B),a>b

构造分析表M

①对每个产生式A→ 1|…| n执行②,③.

②对FIRST(A)中每个终结符a, 把A→ i 加入到M[A,a],其中为终结首符集中

含a的候选式 i或唯一候选式.

③若ε∈FIRST(A), 则对任何属于FOLLOW(A)的终结符b,将A→ε

加入M[A,b].

④把所有无定义的M[A,a]标记为出错.

三、详细设计

1、优先关系矩阵的构造过程:

(1) = 关系

由产生式 F->(E) 知‘(’=‘)’

FIRSTVT集

FIRSTVT(E)={ +,-,*,/,(,i }

FIRSTVT(F)={ (,i }

FIRSTVT(T)={ *,/,(,i }

LASTVT(E)={ +,-,*,/,),i }

LASTVT(F)={ ),i }

LASTVT(T)={ *,/,),i }

(2) < 关系

+T 则有:+ < FIRSTVT(T)

-T 则有:- < FIRSTVT(T)

*F 则有:* < FIRSTVT(F)

/F 则有:/ < FIRSTVT(F)

(E 则有:( < FIRSTVT(E)

(3) > 关系

E+ 则有: LASTVT(E) > +

E- 则有: LASTVT(E) > -

T* 则有: LASTVT(T) > *

T/ 则有: LASTVT(T) > /

E) 则有: LASTVT(E) > )

终结符之间的优先关系是唯一的,该文法是算符优先文法。

2、程序的功能描述:

程序由文件读入字符串(以#结束),然后进行算符优先分析,分

析过程中如有错误,则终止程序并报告错误位置,最终向屏幕输出移近规约过程。

主程序流程图:

编译原理课程设计报告 算符优先分析表

功能模块:

编译原理课程设计报告 算符优先分析表

3、程序所调用的函数清单及其功能

private bool TestGrammar()

//测试是否为算符优先文法

//构造语法规则集合(去除“|”符号)

private void AddToGrammarRules(string LeftPart, string RightPart)

private void AddToVtVn(string LeftPart, string RightPart) //构造终结符与非终结符

public string RetJudgement()

//返回对于输入语法规则的判断

//是FirstVt()函数和LastVt()函数所调用的一个过程,作用是入栈

private void Insert(char Vn, char Vt, bool[,] TempArr) private string FirstVt()

//计算FIRSTVT集合

private string LastVt()

//计算LASTVT集合

public string RetFirstLastVt()

//返回FIRSTVT集合与LASTVT集合

private void RetPreRelationTable()

//计算优先关系表

public StringCollection DrawPreRelationTable()

//返回优先关系表

private string TraceBack(string s, int m, int n) //分析过程所调用的归约函数

private bool AnalysisProcess(string InputSentence)

//分析过程

public StringCollection RetAnalysisProcess(string

InputSentence)

//返回分析(归约移进)过程

/****构造函数,参数为规则数组,构造函数将规则分为两部

分,

分别存于LeftPartRuleTemp和RightPartRuleTemp中****/

public Grammar(String[] GrammarRules)

{ foreach (String ruleTemp in GrammarRules)

{ if (!ruleTemp.Contains("->")) return;

else

ruleTemp.Replace("->", ">");

String[] temp = ruleTemp.Split('>');

LeftPartRuleTemp.Add(temp[0]);

RightPartRuleTemp.Add(temp[1]);

}

}

/****测试是否为算符优先文法,

若是返回true,否则返回false****/

private bool TestGrammar()

{ foreach (String tempRule in RightPartRuleTemp)

{ for (int i = 0; i <= tempRule.Length - 2; i++)

{ if (tempRule[i] >= 'A' && tempRule[i] <=

'Z' && tempRule[i + 1] >= 'A' && tempRule[i + 1] <= 'Z')

return false;

}

}

return true;

}

/****构造语法规则集合(去除“|”符号)****/

private void AddToGrammarRules(string LeftPart, string RightPart)

{ String partTemp = String.Empty;

for(int i=0;i<=RightPart.Length-1;i++)

{ char vt = RightPart[i];

if (vt != '|')

partTemp += vt.ToString();

else

{ RightPartRule.Add(partTemp); LeftPartRule.Add(LeftPart[0].ToString());

partTemp = String.Empty;

}

if (i == (RightPart.Length -1 ))

{ RightPartRule.Add(partTemp);

LeftPartRule.Add(LeftPart[0].ToString());

partTemp = String.Empty;

}

}

}

/****构造终结符集合和非终结符集合,

输入的字符串应不包含‘|’符号****/

private void AddToVtVn(string LeftPart, string RightPart) { if (!VN.Contains(LeftPart[0]))

VN.Add(LeftPart[0]);

foreach (char vt in RightPart)

{ if ((vt < 'A' || vt > 'Z') && !VT.Contains(vt) && vt != '|')

VT.Add(vt);

}

}

/****返回对于输入语法规则的判断****/

public string RetJudgement()

{ string RetString = string.Empty;

if (TestGrammar())

{ RetString += "这是一个算符优先文法!\r\n"; for (int i = 0; i <= LeftPartRuleTemp.Count - 1; i++)

{ AddToGrammarRules(LeftPartRuleTemp[i].ToString(), RightPartRuleTemp[i].ToString());

AddToVtVn(LeftPartRuleTemp[i].ToString(), RightPartRuleTemp[i].ToString());

}

RetString += "非终结符为:\r\n";

foreach (char vn in VN)

RetString += vn.ToString();

RetString += "\r\n终结符为:\r\n";

foreach (char vt in VT)

RetString += vt.ToString();

}

else

RetString += "这不是一个算符优先算法!"; return RetString;

}

四、运行结果

执行程序弹出算符优先分析表生成的界面:

编译原理课程设计报告 算符优先分析表

输入或者读取文法

编译原理课程设计报告 算符优先分析表

执行,运行出FIRSTVT集和LASTVT集并得出算符优先关系表

编译原理课程设计报告 算符优先分析表

五、总结

由于编译原理课学的并不好,开始看见题目不知该如何下手,后面把课本复习了一下,才开始算符优先文法的设计。通过设计,对算符优先文法有了更深入的了解,原来并不理解算符优先文法为什么会设计成那样,后面经过程序的逐步调试,也逐步理解算符文法的设计原理。通过编写语法分析这样一个程序,让我对于算符优先分析有了更加深刻和直观的了解,对于整个过程也变得非常清晰,去除了当初学习过程中似是而非的理解。

此次试验最终能够完成,程序能够运行且能实现预计功能,但有些地方还有待改进,比如输出结果框应改变一下显示模式,以便能够对程序运行结果一目了然。通过此次课程设计实验,我加深了对算符优先文法的理解,巩固了编程技术和对C#的使用。

通过这次学课设,我发现有很多东西,很多细节没注意,如经常漏大小写问题等很小的问题,真正自己动手做了才发现了自己的理论知识是如此的不扎实。有时候一个很小的问题卡一下就要处理很久,细节方面会带来很大的问题等等。我深刻体会到这给我带来的障碍。不过也因为通过这次的课程设计巩固了我的知识,查漏补缺,巩固我已有的知识,把那些遗忘掉的知识再重新学习一遍,使我学到很多,得到很多。

在算符优先程序设计过程中,我觉得比较复杂,其中在优先关系矩阵的构造时遇到了非常大的困难,由于最初对程序的总体流程不是十分清晰,而且实验中因本人马虎将优先关系矩阵输入错误,造成了设计与调试的困难。这个课程设计的思路我能掌握,但要不参考任何资料完全靠自己编确有不小的难度。在编程之前,我参考了很多网上的一个程序和同学的程序,在吸收其精华的基础上,自己做了些改进,最终将程序调出来了。但经过自己的努力,通过多次调试,最终构造出优先关系矩阵并调试成功。

通过本次实验一定程度上提高了软件开发能力,对编译原理这一门课程也有了比较深刻的了解。最后,由于所学知识不够全

面,实验在很多方面还有待完善,在以后的学习过程中,会掌握更多知识,力求做到更好。

六、附录

1、参考文献

[1]《程序设计语言编译原理》陈火旺等. 国防工业出版社

[2]《编译原理》张素琴吕映芝蒋维杜戴桂兰. 清华大学出版社

[3]《编译原理及编译程序构造》高仲仪. 北京航天航空大学出版社

2、部分代码

using System;

using System.Collections;

using System.Collections.Specialized;

using System.Windows.Forms;

namespace GrammarAnalyzer

{ class Grammar

{ StringCollection LeftPartRuleTemp = new StringCollection();

StringCollection RightPartRuleTemp = new StringCollection(); StringCollection LeftPartRule = new StringCollection();

StringCollection RightPartRule = new StringCollection();

ArrayList VT = new ArrayList();

ArrayList VN = new ArrayList();

bool[,] FirstVtTable;

bool[,] LastVtTable;

char[,] PreRelationTable;

StringCollection ProcessStr = new StringCollection();

Stack stack = new Stack();

public Grammar(String[] GrammarRules)

………… //略

private bool TestGrammar()

………… //略

private void AddToGrammarRules(string LeftPart, string RightPart) ………… //略

private void AddToVtVn(string LeftPart, string RightPart) ………… //略

public string RetJudgement()

………… //略

private void Insert(char Vn, char Vt, bool[,] TempArr)

{ int VnNum = VN.IndexOf(Vn);

int VtNum = VT.IndexOf(Vt);

if (!TempArr[VnNum, VtNum])

{ TempArr[VnNum, VtNum] = true;

stack.Push(Vn.ToString() + Vt.ToString());

}

}

private string FirstVt() //计算FIRSTVT集合

{ string strFirst = "以下为FIRSTVT集合:\r\n";

stack.Clear();

FirstVtTable = new bool[VN.Count, VT.Count];

for (int i = 0; i <= LeftPartRule.Count - 1; i++)

{ if (VT.Contains(RightPartRule[i][0]))

{Insert(LeftPartRule[i][0], RightPartRule[i][0], FirstVtTable);

}

else if (RightPartRule[i].Length >= 2 && VT.Contains(RightPartRule[i][1]))

{Insert(LeftPartRule[i][0], RightPartRule[i][1], FirstVtTable);

}

}

while (stack.Count >= 1)

{ string tempQa = stack.Pop().ToString();

string tempQ = tempQa[0].ToString();

string tempa = tempQa[1].ToString();

for (int i = 0; i <= LeftPartRule.Count - 1; i++)

{ if (RightPartRule[i][0].ToString() == tempQ)

{Insert(LeftPartRule[i][0], tempa[0], FirstVtTable);

}

}

}

for (int i = 0; i <= VN.Count - 1; i++)

{ strFirst += "FIRSTVT(" + VN[i].ToString() + ")={ ";

for (int j = 0; j <= VT.Count - 1; j++)

{ if (FirstVtTable[i, j] == true)

strFirst += VT[j].ToString() + " ";

}

strFirst += "}\r\n";

}

return strFirst;

}

private string LastVt()

{ string strLast = "以下为LASTVT集合:\r\n";

stack.Clear();

LastVtTable = new bool[VN.Count, VT.Count];

for (int i = 0; i <= LeftPartRule.Count - 1; i++)

{ int j = RightPartRule[i].Length;

if (VT.Contains(RightPartRule[i][j - 1]))

{ Insert(LeftPartRule[i][0], RightPartRule[i][j - 1], LastVtTable);

}

else if (RightPartRule[i].Length >= 2 && VT.Contains(RightPartRule[i][j - 2]))

{ Insert(LeftPartRule[i][0], RightPartRule[i][j - 2], LastVtTable);

}

}

while (stack.Count >= 1)

{ string tempQa = stack.Pop().ToString();