判定算符优先文法.pdfVIP

判定算符优先文法--第1页

国家人才培养模式创新实验区、云南省教学团队、云南大学软件学院

教育创新基金（编号：2009EI08）联合资助项目

判定算符优先文法

姓名：

学号：

专业：软件工程

任课教师：柳青

编制时间：2014年5月14日

成绩：

云南大学软件学院

2012年6月制表

判定算符优先文法--第1页

判定算符优先文法--第2页

1.实现目标

编写一个程序，用于判定给定的文法是否为算符优先文法。

1．文法的机内表示；

2.FIRSTVT集和LASTVT集的计算；

3.算符优先关系矩阵的构造。

2.实现方案

2.1开发工具及环境

开发工具：eclipse工具

开发环境：

硬件环境：

CPUP3800MHZ以上，建议P52.0GHZ

硬盘100G以上，建议用250G

显卡标准VGA，24位真彩色

内存256MB以上，建议512M

其他键盘、鼠标、网卡、能连通互联网

软件环境：

Win7操作系统

安装一个java的JDK包以及配置相应的环境变量参数

2.2程序的架构

本次实验实现的词法分析器，采用的是C/S架构，这样的架构优点是

效率高，交互性强。

判定算符优先文法--第2页

判定算符优先文法--第3页

3.实现步骤

3.1算符优先分析方法原理：

算符优先分析方法是根据算符之间的优先关系而设计的一种自下而上的分

析方法。算符优先分析的基本思想是只规定算符之间的优先关系，也就是只考虑

终结符之间的优先关系。算符优先分析过程是自下而上的归约过程，所谓的算符

优先分析就是定义算符之间（确切地说，终结符之间）的某种优先关系，借助于

这种优先关系寻找“可归约串”和进行归约。

该文法必须满足以下条件：

文法它的任一产生式的右部都不含两个相继（并列）的非终结符，即不含如

下产生式右部：…QR…；

首先求出该文法的优先关系表，在程序中用2维数组表示，-1表示小于或

者等于，大于为1，其它为0表示错误。

在输入一串字符串以后进行按照文法一步一步的进行规约，我所进行的是直

接规约到文法的符号而不是规约到N。

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

个符号的指针。

3.2程序分析步骤：

在程序的主界面中首先用cout列出了在词法分析中需要用到的几个文法:

直接输入根据已知文法构造的算符优先关系矩阵。

输入已知文法的FIRSTVT和LASTVT集合，由程序自动生成该文法的算符优

先关系矩阵。

S→A

A→V:=E

E→E+T|T

T→T*F|F

F→(E)|i