当前位置: 首页 > >

《编译方法》实验指导书

发布时间:

目录
实验一 词法分析器设计 ....................................... 错误!未定义书签。 错误!未定义书签。 【实验目的】 ................................................... 错误!未定义书签。 错误!未定义书签。 【实验内容】 ................................................... 错误!未定义书签。 错误!未定义书签。 【流程图】........................................................ 错误!未定义书签。 错误!未定义书签。 【源代码】........................................................ 错误!未定义书签。 错误!未定义书签。 【程序部分截图】 ............................................................................18 实验二 LL(1)语法分析程序设计 ......................................................20 【实验目的】 ....................................................................................20 【实验内容】 ....................................................................................20 【实验步骤和要求】 ........................................................................20 【流程图】.........................................................................................20 【源代码】.........................................................................................21 【程序截图】 ................................................... 错误!未定义书签。 错误!未定义书签。

实验一 词法分析器设计
【实验目的】 1.熟悉词法分析的基本原理,词法分析的过程以及词法分析中要注意的问题。 2.复*高级语言,进一步加强用高级语言来解决实际问题的能力。 3.通过完成词法分析程序,了解词法分析的过程。

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

调用语法分析函数

Y
判断文字是否读完

Y N

输出二元组及 常数表, 标识符

从文本中读入一行字 符,存于一个字符串

N
程序结束 从字符串中读出一个字符

字母
判断为何种字符

符号

不断读入,直到 出现非字母或数 字符号

不断读入,直 到出现非数字 符号

Y

看是否有算 符或运算符

N

将该项插入常数表 增加一个对 判断是否为保留字 应的二元组 法字符 报错, 出现非

Y
增加一个对 应的二元组

N
将该项插入 标识符表中

判断是否到行尾

1

【源代码】
package accidence_analyse; import java.io.*; import java.util.*; import buffer.*; public class AccidenceAnalyser { private java.io.File SourceFile; private java.io.File ReserveFile; private java.io.File ClassFile; private java.io.File OutputFile; public Pretreatment pretreatment; public KeyWordTable keyWordTable; public ClassIdentity classIdentity; public Scaner scaner; public ConcreteScanBufferFactory csbFactory; /** * 2) 词法分析器主程序 */ public AccidenceAnalyser() { System.out.println("[INFOR]已经建立词法分析器!"); } public void initAA() { //创建缓冲工厂 this.csbFactory=newConcreteScanBufferFactory(); //创建字符串扫描对象 scaner = new Scaner(this); //创建 pre 处理对象 pretreatment=newPretreatment(SourceFile, this); //创建关键字表对象 keyWordTable= new KeyWordTable(ReserveFile); //创建对象种别码表对象 classIdentity = new ClassIdentity(ClassFile); System.out.println("[INFOR]已经初始化词法分析器!"); } public void setFilesPath(String reserveFileName, String ClassFileName,String sourceFileName, String outputFileName) { //创建文件对象 SourceFile = new java.io.File(sourceFileName); //创建文件对象 ReserveFile = new java.io.File(reserveFileName); //创建文件对象 ClassFile = new java.io.File(ClassFileName); //创建文件对象 OutputFile = new java.io.File(outputFileName); //如果文件已经存在,先删除,然后建立新文件 2

if (OutputFile.exists()) {OutputFile.delete();} try {OutputFile.createNewFile();} catch(Exceptione){e.printStackTrace(System.err);} try { // 创 建 文 件 随 机 读 取 对 象 java.io.RandomAccessFile(this. OutputFile, "rw"); //提示信息 ROutputFile.write("///////////////////////////////////////\n".getBytes()); ROutputFile.write( ("//JAccidenceAnalyser version " + getVersion() +" design by yellowicq//\n").getBytes()); ROutputFile.write("//java 词法分析器//////////////\n".getBytes()); ROutputFile.write("//使用 java 语言开发///\n".getBytes()); ROutputFile.write("\n".getBytes()); ROutputFile.write("词法分析结果如下:\n".getBytes()); //关闭文件流 ROutputFile.close(); } catch (Exception e) { e.printStackTrace(System.err); } } public void startAA() { //从预处理开始词法分析 this.pretreatment.startPretreatment(); } public void outputAccidence(String outputString) { //把分析出来的单词写入文件 outputString="\n[第" + this.pretreatment.fileRow + "行]\n" + outputString; try { //创建文件随机读取对象 java.io.RandomAccessFile ROutputFile = new java.io.RandomAccessFile(this.OutputFile, "rw"); //移动指针到文件末尾 ROutputFile.seek(ROutputFile.length()); //Start appending! ROutputFile.write(outputString.getBytes()); //关闭文件流 ROutputFile.close(); } catch (Exception e) { e.printStackTrace(System.err); } //将分析的单词结果输出到终端 System.out.print(outputString); } 3 java.io.RandomAccessFile ROutputFile = new

public void controlThread() { //控制扫描器启动扫描 scaner.controlThread(); } //获得版本号 public String getVersion() { return "1.0"; } }

package accidence_analyse; import java.util.*; import java.io.*; public class ClassIdentity { private Hashtable ClassHash; private File ClassFile; private FileReader classFileReader; //读文件对象 private int TMP_BUFFER_SIZE = 30; /** * 6) 类型种别码程序 */ public ClassIdentity(java.io.File ClassFile) { System.out.println("[INFOR]类型种别码表已创建!"); this.ClassFile = ClassFile; } //查找类型种别码 public int findKey(String classWord) { int KEY; for (Enumeration e = this.ClassHash.keys(); e.hasMoreElements(); ) { KEY=Integer.parseInt((String)e.nextElement()); if( ( (String)this.ClassHash.get(Integer.toString(KEY))).equalsIgnoreCase(classWord)) {return KEY;} } return -1; } public void initClassIdentityTable() { ClassHash = new Hashtable(); //创建 hash 表 int intLength; char[] chrBuffer = new char[TMP_BUFFER_SIZE]; String classWord; int classCounter = 0; try { if (ClassFile.exists()) { //文件存在 4

//创建读文件对象 classFileReader=newjava.io.FileReader(ClassFile); //读文件内容到 hash 表 while((intLength=classFileReader.read(chrBuffer)) != -1) { classCounter++; //填写 hash 表 classWord = String.valueOf(chrBuffer).trim(); System.out.println("[INFOR]读取类型种别码: [KEY: " + classCounter + "][VALUE: " + classWord + "]"); this.ClassHash.put(Integer.toString(classCounter), classWord); } //关闭读文件对象 classFileReader.close(); } else { //文件不存在 System.err.println("[ERROR]类型种别码文件不存在!"); } } catch (Exception e) { e.printStackTrace(System.err); } } }

package accidence_analyse; import java.util.*; import java.io.*; public class KeyWordTable { private Hashtable KWHash; private File ReserveFile; private FileReader resFileReader; //读文件对象 private int TMP_BUFFER_SIZE = 30; /** * 5) 表留字表程序 */ public KeyWordTable(java.io.File ReserveFile) { System.out.println("[INFOR]关键字表已创建!"); this.ReserveFile = ReserveFile; } public boolean isKeyWord(String inw) { String resWord; //查找 hash 表 for (Enumeration e = this.KWHash.elements(); e.hasMoreElements(); ) { resWord = (String) e.nextElement(); if (resWord.equalsIgnoreCase(inw)) { 5

return true; } } return false; } public void initKeyWordTable() { KWHash = new Hashtable(); //创建 hash 表 int intLength; char[] chrBuffer = new char[TMP_BUFFER_SIZE]; String resWord; int resCounter = 0; try { if (ReserveFile.exists()) { //文件存在 //创建读文件对象 resFileReader = new java.io.FileReader(ReserveFile); //读文件内容到 hash 表 while((intLength = resFileReader.read(chrBuffer))!= -1) { //填写 hash 表 resWord = String.valueOf(chrBuffer).trim(); System.out.println("[INFOR]读取关键字: [INDEX: " + resCounter +"][VALUE: " + resWord + "]"); this.KWHash.put(Integer.toString(resCounter), resWord);} //关闭读文件对象 resFileReader.close(); } else { //文件不存在 System.err.println("[ERROR]保留字文件不存在!"); } } catch (Exception e) { e.printStackTrace(System.err); } } } resCounter++;

package accidence_analyse; import javax.xml.parsers.*; import org.w3c.dom.*; public class main { /** * 1) 词法分析器引导文件 */ 6

public static void main(String[] args) { //读取配置文件,得到系统属性 String cfgString[] = new String[4]; try { cfgString = main.loadAACfg("d:\\aaCfg.xml"); } catch (Exception e) { e.printStackTrace(System.err); } //设置待读文件名 //保留字表文件 String reserveFileName = cfgString[0]; //类型种别码表文件 String classFileName = cfgString[1]; //需要分析的源文件 String sourceFileName = cfgString[2]; //输出文件 String outputFileName = cfgString[3]; //创建词法分析器 AccidenceAnalyser aa=new AccidenceAnalyser(); aa.setFilesPath(reserveFileName, classFileName, sourceFileName,outputFileName); //建立所需要的文件对象 //初始化词法分析器 aa.initAA(); //初始化关键字表 aa.keyWordTable.initKeyWordTable(); //初始化类型种别码表 aa.classIdentity.initClassIdentityTable(); //开始进行词法分析 aa.startAA(); //分析完毕 } //读取配置文件 private static String[] loadAACfg(String name) throws Exception { String cfgString[] = new String[4]; /*解析 xml 配置文件*/ try { /*创建文档工厂*/ DocumentBuilderFactory factory = DocumentBuilderFactory.newInstance(); /*创建文档解析器*/ DocumentBuilder builder = factory.newDocumentBuilder(); /*解析配置文件*/ Document doc = builder.parse(name); /*规范化文档*/ 7

doc.normalize(); /*查找接点表*/ NodeList nlists = doc.getElementsByTagName("FilePath"); for (int i = 0; i < nlists.getLength(); i++) { Element item = (Element) nlists.item(i); //取得需要的配置属性 cfgString[0] item.getElementsByTagName("ReserveFileName").item(0).getFirstChild().getNodeValue().trim(); cfgString[1] = item.getElementsByTagName("ClassFileName").item(0). getFirstChild().getNodeValue().trim(); cfgString[2] = item.getElementsByTagName("SourceFileName").item(0). getFirstChild().getNodeValue().trim(); cfgString[3] = item.getElementsByTagName("OutputFileName").item(0). getFirstChild().getNodeValue().trim(); } } catch (Exception e) { e.printStackTrace(); throw new Exception("[ERROR]加载配置文件 " + name + " 错误!"); } //返回属性数组 return cfgString; } } =

package accidence_analyse; import java.io.*; import buffer.*; public class Pretreatment { private String tmpString; private String outputString; private int BUFFER_SIZE = 100; private AccidenceAnalyser aa; public InputBuffer inputBuffer; //输入缓冲区--共享 private java.io.File SourceFile; //文件对象 private java.io.RandomAccessFile randomAFile; //随机文件对象 public static int fileRow = 0; /** * 3) 预处理子程序 */ public Pretreatment(File SourceFile, AccidenceAnalyser aa) { 8

try { this.SourceFile = SourceFile; this.randomAFile = new java.io.RandomAccessFile(this.SourceFile, "r"); } catch (FileNotFoundException e) { e.printStackTrace(System.err); } this.aa = aa; inputBuffer = aa.csbFactory.createInputBuffer(BUFFER_SIZE); System.out.println("[INFOR]预处理器已经创建!"); } public void putSourceToINBuffer(String tmpString) { this.inputBuffer.Data = tmpString.toCharArray(); } public void putFinToSCBuffer(String filtratedString) { aa.scaner.scanBuffer.Data = filtratedString.toCharArray(); } public void controlThread() { int intLength; int resCounter = 0; String tmpString; String filtratedString; System.out.println("[INFOR]开始单词分析////////////////////////////////////////"); try { if (SourceFile.exists()) { //文件存在 //读文件内容到缓冲区 while ( (tmpString = this.randomAFile.readLine()) != null) { ++fileRow; //分割符 System.out.println("...................begin row " + this.fileRow + "......................."); //开始这一行分析 System.out.println("[INFOR]正在处理行: " + String.valueOf(fileRow)); //放入输入缓冲区 this.putSourceToINBuffer(tmpString); //处理字符串 filtratedString = this.filtrateSource(this.inputBuffer.Data); System.out.println("[INFOR]已过滤句子: " + filtratedString); //放入扫描缓冲区 this.putFinToSCBuffer(filtratedString); aa.controlThread(); } System.out.println( "[INFOR]分析完毕////////////////////////////////////////////"); 9

} else { //文件不存在 System.err.println("[ERROR]源文件不存在!"); } } catch (Exception e) { e.printStackTrace(System.err); } } public String filtrateSource(char[] Data) { String filtratedString = String.valueOf(Data).trim(); return filtratedString; } public void startPretreatment() { this.controlThread(); } }

package accidence_analyse;

import buffer.*; public class Scaner { public ScanBuffer scanBuffer; //扫描缓冲区--共享 private String finalAccidence; private AccidenceAnalyser aa; private int BUFFER_SIZE = 100; private String toDelString; private int senLength = 0; private char[] sentenceChar = new char[1000]; private String TOKEN; private char CHAR; private int index = 0; private String IDENTITY = "identity"; private String DIGIT = "digit"; private String WORD_ERROR_INF = "在此行发现不能识别的单词,此行分析终止!"; private boolean ASTATE = true; /** * 4) 扫描子程序 */ public Scaner(AccidenceAnalyser aa) { this.aa = aa; initBuffer(); this.finalAccidence = ""; System.out.println("[INFOR]扫描处理器已经创建!"); 10

} public String readFromBuffer(char[] Data) { String toDelString = String.valueOf(Data); return toDelString; } public String scan(String toDelString) { sentenceChar = toDelString.toCharArray(); this.senLength = sentenceChar.length; int i = 0; //分析单词 while (this.index <= this.senLength) { //state0: this.TOKEN = ""; this.CHAR = GETBC(sentenceChar); if (this.CHAR == ';') { break; //';'表示这一行结束 } //进入状态判断 switch (this.CHAR) { //judge letter case 'a':case 'b':case 'c':case 'd':case 'e':case 'f':case 'g':case 'h':case 'i':case 'j':case 'k': case 'l':case 'm':case 'n':case 'o':case 'p':case 'q':case 'r':case 's':case 't':case 'u':case 'v':case 'w':case 'x':case 'y': case 'z':case 'A':case 'B':case 'C':case 'D':case 'E':case 'F':case 'G':case 'H':case 'I':case 'J':case 'K':case 'L':case 'M': case 'N':case 'O':case 'P':case 'Q':case 'R':case 'S':case 'T':case 'U':case 'V':case 'W':case 'X':case 'Y':case 'Z': //do this.TOKEN = this.CONTACT(TOKEN, CHAR); //state1 CHAR = this.GETCHAR(sentenceChar); while (this.ISLETTER(CHAR) || this.ISDIGIT(CHAR)) { this.TOKEN = this.CONTACT(this.TOKEN, CHAR); CHAR = this.GETCHAR(sentenceChar); } this.RETRACT(); //state2 if (aa.keyWordTable.isKeyWord(TOKEN)) { this.finalAccidence = this.finalAccidence + "[保留字] " + this.returnAWord(TOKEN) + "\n"; } else { this.finalAccidence = this.finalAccidence + "[标识符] " + this.returnAWord(TOKEN) + "[种别码] " + String.valueOf(aa.classIdentity.findKey(IDENTITY)) + "\n"; } //clear up token 11

this.TOKEN = ""; break; //judge ditital case '0':case '1':case '2':case '3':case '4':case '5':case '6':case '7':case '8': case '9': //do this.TOKEN = this.CONTACT(TOKEN, CHAR); //state3 CHAR = this.GETCHAR(sentenceChar); while (this.ISDIGIT(CHAR)) { this.TOKEN = this.CONTACT(TOKEN, CHAR); CHAR = this.GETCHAR(sentenceChar); } this.RETRACT(); //state4 this.finalAccidence = this.finalAccidence + "[数字] " + this.returnAWord(TOKEN) + "[种别码] " + String.valueOf(aa.classIdentity.findKey(DIGIT)) + "\n"; //clear up token this.TOKEN = ""; break; case '=': //state5 this.TOKEN = this.CONTACT(TOKEN, CHAR); this.finalAccidence = this.finalAccidence + "[等号] " + this.returnAWord(TOKEN) + "[种别码] " + String.valueOf(aa.classIdentity.findKey(String.valueOf(CHAR))) + "\n"; //clear up token this.TOKEN = ""; break; case '+': //state6 this.TOKEN = this.CONTACT(TOKEN, CHAR); this.finalAccidence = this.finalAccidence + "[加号] " + this.returnAWord(TOKEN) + "[种别码] " + String.valueOf(aa.classIdentity.findKey(String.valueOf(CHAR))) + "\n"; //clear up token this.TOKEN = ""; break; case '*': //state7 this.TOKEN = this.CONTACT(TOKEN, CHAR); CHAR = this.GETCHAR(sentenceChar); 12

//state8 if (CHAR == '*') { this.TOKEN = this.CONTACT(TOKEN, CHAR); this.finalAccidence = this.finalAccidence + "[乘方] " + this.returnAWord(TOKEN) + "[种别码] " + String.valueOf(aa.classIdentity.findKey(String.valueOf(CHAR))) + "\n"; } //state9 else { this.finalAccidence = this.finalAccidence + "[乘号] " + this.returnAWord(TOKEN) + "[种别码] " + String.valueOf(aa.classIdentity.findKey(String.valueOf(CHAR))) + "\n"; } //clear up token this.TOKEN = ""; break; case ',': //state10 this.TOKEN = this.CONTACT(TOKEN, CHAR); this.finalAccidence = this.finalAccidence + "[逗号] " + this.returnAWord(TOKEN) + "[种别码] " + String.valueOf(aa.classIdentity.findKey(String.valueOf(CHAR))) + "\n"; //clear up token this.TOKEN = ""; break; case '(': //state11 this.TOKEN = this.CONTACT(TOKEN, CHAR); this.finalAccidence = this.finalAccidence + "[左括号] " + this.returnAWord(TOKEN) + "[种别码] " + String.valueOf(aa.classIdentity.findKey(String.valueOf(CHAR))) + "\n"; //clear up token this.TOKEN = ""; break; case ')': //state12 this.TOKEN = this.CONTACT(TOKEN, CHAR); this.finalAccidence = this.finalAccidence + "[右括号] " + this.returnAWord(TOKEN) + "[种别码] " + String.valueOf(aa.classIdentity.findKey(String.valueOf(CHAR))) + 13

"\n"; //clear up token this.TOKEN = ""; break; case '{': //state13 this.TOKEN = this.CONTACT(TOKEN, CHAR); this.finalAccidence = this.finalAccidence + "[左大括号] " + this.returnAWord(TOKEN) + "[种别码] " + String.valueOf(aa.classIdentity.findKey(String.valueOf(CHAR))) + "\n"; //clear up token this.TOKEN = ""; break; case '}': //state14 this.TOKEN = this.CONTACT(TOKEN, CHAR); this.finalAccidence = this.finalAccidence + "[右大括号] " + this.returnAWord(TOKEN) + "[种别码] " + String.valueOf(aa.classIdentity.findKey(String.valueOf(CHAR))) + "\n"; //clear up token this.TOKEN = ""; break; case '[': //state15 this.TOKEN = this.CONTACT(TOKEN, CHAR); this.finalAccidence = this.finalAccidence + "[左中括号] " + this.returnAWord(TOKEN) + "[种别码] " + String.valueOf(aa.classIdentity.findKey(String.valueOf(CHAR))) + "\n"; //clear up token this.TOKEN = ""; break; case ']': //state16 this.TOKEN = this.CONTACT(TOKEN, CHAR); this.finalAccidence = this.finalAccidence + "[右中括号] " + this.returnAWord(TOKEN) + "[种别码] " + String.valueOf(aa.classIdentity.findKey(String.valueOf(CHAR))) + "\n"; //clear up token this.TOKEN = ""; break; 14

case '.': //state17 this.TOKEN = this.CONTACT(TOKEN, CHAR); this.finalAccidence = this.finalAccidence + "[点号] " + this.returnAWord(TOKEN) + "[种别码] " + String.valueOf(aa.classIdentity.findKey(String.valueOf(CHAR))) + "\n"; //clear up token this.TOKEN = ""; break; default: //state18 this.TOKEN = this.CONTACT(this.TOKEN, this.CHAR); //追加出错信息 this.finalAccidence = this.finalAccidence + "[ERROR]" + this.WORD_ERROR_INF + "'" + this.TOKEN + "'" + "\n"; this.ASTATE = false; //clear up token this.TOKEN = ""; break; } if (this.ASTATE == false) { break; } } return this.finalAccidence; } public void controlThread() { this.toDelString = this.readFromBuffer(this.scanBuffer.Data); this.aa.outputAccidence(this.scan(this.toDelString)); //分割符 System.out.println("...................end row " + aa.pretreatment.fileRow + "........................."); //结束这一行分析 //clear up the var this.index = 0; this.finalAccidence = ""; this.ASTATE = true; this.toDelString = ""; this.senLength = 0; this.TOKEN = ""; } public String returnAWord(String TOKEN) { return TOKEN; 15

} public void initBuffer() { this.scanBuffer = aa.csbFactory.createScanBuffer(BUFFER_SIZE); } //以下为字符的处理方法 public char GETBC(char[] sentenceChar) { try { while ( (sentenceChar[this.index]) == ' ') { this.index++; } this.index++; } catch (java.lang.ArrayIndexOutOfBoundsException e) { return ';'; //表示此行已经结束 } return sentenceChar[index - 1]; } public char GETCHAR(char[] sentenceChar) { next(); return sentenceChar[this.index - 1]; } public void next() { this.index++; } public boolean ISLETTER(char letter) { return java.lang.Character.isLetter(letter); } public boolean ISDIGIT(char letter) { return java.lang.Character.isDigit(letter); } public String CONTACT(String TOKEN, char CHAR) { String tmpS = TOKEN + String.valueOf(CHAR); TOKEN = tmpS; return TOKEN; } public boolean ISRESERVE(String TOKEN) { return aa.keyWordTable.isKeyWord(TOKEN); } public void RETRACT() { this.index--; } }

16

package buffer; //abstract buffer interface public interface Buffer { }

package buffer; public interface BufferFactory { /** * 7) 抽象扫描缓冲区工厂 */ public ScanBuffer createScanBuffer(int size);

public InputBuffer createInputBuffer(int size); }

package buffer;

public class ConcreteScanBufferFactory implements BufferFactory { /** * 8) 缓冲区工厂 */ public ConcreteScanBufferFactory() { System.out.println("[INFOR]缓冲区工厂已经建立!"); } public ScanBuffer createScanBuffer(int size) { System.out.println("[INFOR]创建扫描缓冲区!"); return new ScanBuffer(size); } public InputBuffer createInputBuffer(int size) { System.out.println("[INFOR]创建输入缓冲区!"); return new InputBuffer(size); } }

package buffer; import java.io.*;

public class InputBuffer implements Buffer { public char[] Data; 17

/** * 10) 输入缓冲区对象 */ public InputBuffer(int size) { this.Data = new char[size]; } }

package buffer; public class ScanBuffer implements Buffer { public char[] Data; /** * 11) 扫描缓冲区对象 */ public ScanBuffer(int size) { this.Data = new char[size]; } }

【程序部分截图】

18

19

实验二 LL(1)语法分析程序设计

【实验目的】 1.熟悉判断 LL(1)文法的方法及对某一输入串的分析过程。 2.学会构造表达式文法的预测分析表。

【实验内容】 编写一个语法分析程序,对于给定的输入串,能够判断识别该串是否为给定文法的句型。

【实验步骤和要求】 1. 从键盘读入输入串,并判断正误; 2. 若无误,由程序自动构造 FIRST、FOLLOW 集以及 SELECT 集合,判断是否为 LL(1)文法; 3. 若符合 LL(1)文法,由程序自动构造 LL(1)分析表; 4. 由算法判断输入符号串是否为该文法的句型。 (可参考教材 96 页的例题 1) 【流程图】

开始

#和<程序>读入

取一输入符 a 取一输入符 a 弹出栈顶符号放入 X

X 是非终结符?

N
是终结符?

Y
M[X,a]存在规则?

N

Y
X=a?

Y
若 M[X,a] 存 在 规 则 X->X1X2X3…Xn

N

Y
X=#?

Y 出错 成功

20

【源代码】 #include "stdio.h" #include "stdlib.h" #define MaxRuleNum 8 #define MaxVnNum 5 #define MaxVtNum 5 #define MaxStackDepth 20 #define MaxPLength 20 #define MaxStLength 50 struct pRNode /*产生式右部结构*/ { int rCursor; /*右部序号*/ struct pRNode *next; }; struct pNode /*产生式结点结构*/ { int lCursor; /*左部符号序号*/ int rLength; /*右部长度*/ /*注当 rLength = 1 时,rCursor = -1 为 空产生式*/ struct pRNode *rHead; /*右部结点头指 针*/ }; char Vn[MaxVnNum + 1]; /*非终结符集*/ int vnNum; char Vt[MaxVtNum + 1]; /*终结符集*/ int vtNum; struct pNode P[MaxRuleNum]; /*产生式*/ int PNum; /*产生式实际个数*/ char buffer[MaxPLength + 1]; char ch; /*符号或 string ch;*/ char st[MaxStLength]; /*要分析的符号串 */

int analyseTable[MaxVnNum + 1][MaxVtNum + 1 + 1]; /*预测分析表存放为产生式的编号, 用于 +1 存放结束符,多+1 用于存放#(-1)*/ int analyseStack[MaxStackDepth + 1]; /* 分析栈*/ int topAnalyse; /*分析栈顶*/ /*int reverseStack[MaxStackDepth + 1]; /*颠倒顺序栈*/ /*int topReverse; /*倒叙栈顶*/

struct collectNode /*集合元素结点结构 */ { int nVt; /*在终结符集中的下标*/ struct collectNode *next; }; struct collectNode* first[MaxVnNum + 1]; /*first 集*/ struct collectNode* follow[MaxVnNum + 1]; /*follow 集*/
21

void Init();/*初始化*/ int IndexCh(char ch); /*返回 Vn 在 Vn 表中的位置+100、Vt 在 Vt 表中的位置,-1 表示未找到*/ void InputVt(); /*输入终结符*/ void InputVn();/*输入非终结符*/ void ShowChArray(char* collect, int num);/*输出 Vn 或 Vt 的内容*/ void InputP();/*产生式输入*/ bool CheckP(char * st);/*判断产生式正 确性*/ void First(int U);/* 计 算 first 集,U->xx...*/ void AddFirst(int U, int nCh); /*加入 first 集*/ bool HaveEmpty(int nVn); /*判断 first 集中是否有空(-1)*/ void Follow(int V);/*计算 follow 集*/ void AddFollow(int V, int nCh, int kind);/*加入 follow 集, kind = 0 表加入 follow 集,kind = 1 加 入 first 集*/ void ShowCollect(struct collectNode **collect);/*输出 first 或 follow 集*/ void FirstFollow();/* 计 算 first 和 follow*/ void CreateAT();/*构造预测分析表*/ void ShowAT();/*输出分析表*/ void Identify(char *st);/*主控程序,为 操作方便*/ /*分析过程显示操作为本行变换所用, 与教 程的显示方式不同*/

void void void void */

InitStack();/*初始化栈及符号串*/ ShowStack();/*显示符号栈中内容*/ Pop();/*栈顶出栈*/ Push(int r);/*使用产生式入栈操作

{ st[i++] = ch; } ch = getchar(); } if('#' == ch && i < MaxStLength) { st[i] = ch; Identify(st); } else printf("输入出错!\n"); } } getchar(); } void Init() { int i,j; vnNum = 0; vtNum = 0; PNum = 0; for(i = 0; i <= MaxVnNum; i++) Vn[i] = '\0'; for(i = 0; i <= MaxVtNum; i++) Vt[i] = '\0'; for(i = 0; i < MaxRuleNum; i++) { P[i].lCursor = NULL; P[i].rHead = NULL; P[i].rLength = 0; } PNum = 0; for(i = 0; i <= MaxPLength; i++) buffer[i] = '\0'; for(i = 0; i < MaxVnNum; i++) { first[i] = NULL; follow[i] = NULL; } for(i = 0; i <= MaxVnNum; i++) { for(j = 0; j <= MaxVnNum + 1; j++) analyseTable[i][j] = -1;
22

#include "LL1.h"

void main(void) { char todo,ch; Init(); InputVn(); InputVt(); InputP(); getchar(); FirstFollow(); printf("所得 first 集为:"); ShowCollect(first); printf("所得 follow 集为:"); ShowCollect(follow); CreateAT(); ShowAT(); todo = 'y'; while('y' == todo) { printf("\n 是否继续进行句型分析?(y / n):"); todo = getchar(); while('y' != todo && 'n' != todo) { printf("\n(y / n)? "); todo = getchar(); } if('y' == todo) { int i; InitStack(); printf("请输入符号串(以#结束) : "); ch = getchar(); i = 0; while('#' != ch && i < MaxStLength) { if(' ' != ch && '\n' != ch)

} } /*返回 Vn 在 Vn 表中的位置+100、Vt 在 Vt 表中的位置,-1 表示未找到*/ int IndexCh(char ch) { int n; n = 0; /*is Vn?*/ while(ch != Vn[n] && '\0' != Vn[n]) n++; if('\0' != Vn[n]) return 100 + n; n = 0; /*is Vt?*/ while(ch != Vt[n] && '\0' != Vt[n]) n++; if('\0' != Vt[n]) return n; return -1; } /*输出 Vn 或 Vt 的内容*/ void ShowChArray(char* collect) { int k = 0; while('\0' != collect[k]) { printf(" %c ", collect[k++]); } printf("\n"); } /*输入非终结符*/ void InputVn() { int inErr = 1; int n,k; char ch; while(inErr) { printf("\n 请输入所有的非终结符,注 意:"); printf("请将开始符放在第一位,并以# 号结束:\n"); ch = ' '; n = 0; /*初始化数组*/
23

while(n < MaxVnNum) { Vn[n++] = '\0'; } n = 0; while(('#' != ch) && (n < MaxVnNum)) { if(' ' != ch && '\n' != ch && -1 == IndexCh(ch)) { Vn[n++] = ch; vnNum++; } ch = getchar(); } Vn[n] = '#'; /*以“#”标志结束用于判 断长度是否合法*/ k = n; /*k 用 于 记 录 n 以 便 改 Vn[n]='\0'*/ if('#' != ch) { if( '#' != (ch = getchar())) { while('#' != (ch = getchar())) ; printf("\n 符号数目超过限制!\n"); inErr = 1; continue; } } /*正确性确认,正确则,执行下下面,否 则重新输入*/ Vn[k] = '\0'; ShowChArray(Vn); ch = ' '; while('y' != ch && 'n' != ch) { if('\n' != ch) { printf("输入正确确认?(y/n):"); } scanf("%c", &ch); } if('n' == ch)

{ printf("录入错误重新输入!\n"); inErr = 1; } else { inErr = 0; } } } /*输入终结符*/ void InputVt() { int inErr = 1; int n,k; char ch; while(inErr) { printf("\n 请输入所有的终结符,注意: "); printf("以#号结束:\n"); ch = ' '; n = 0; /*初始化数组*/ while(n < MaxVtNum) { Vt[n++] = '\0'; } n = 0; while(('#' != ch) && (n < MaxVtNum)) { if(' '!= ch && '\n' != ch && -1 == IndexCh(ch)) { Vt[n++] = ch; vtNum++; } ch = getchar(); } Vt[n] = '#'; /*以“#”标志结束*/ k = n; /*k 用 于 记 录 n 以 便 改 Vt[n]='\0'*/ if('#' != ch) {
24

if( '#' != (ch = getchar())) { while('#' != (ch = getchar())) printf("\n 符号数目超过限制!\n"); inErr = 1; continue; } } /*正确性确认,正确则,执行下下面,否 则重新输入*/ Vt[k] = '\0'; ShowChArray(Vt); ch =' '; while('y' != ch && 'n' != ch) { if('\n' != ch) { printf("输入正确确认?(y/n):"); } scanf("%c", &ch); } if('n' == ch) { printf("录入错误重新输入!\n"); inErr = 1; } else { inErr = 0; } } } /*产生式输入*/ void InputP() { char ch; int i = 0, n,num; printf("请输入文法产生式的个数:"); scanf("%d", &num); PNum = num; getchar(); /*消除回车符*/ printf("\n 请输入文法的%d 个产生式,并 以回车分隔每个产生式:", num); printf("\n");

while(i < num) { printf("第%d 个:", i); /*初始化*/ for(n =0; n < MaxPLength; n++) buffer[n] = '\0'; /*输入产生式串*/ ch = ' '; n = 0; while('\n' != (ch = getchar()) && n < MaxPLength) { if(' ' != ch) buffer[n++] = ch; } buffer[n] = '\0'; /* printf("%s", buffer);*/ if(CheckP(buffer)) { /*填写入产生式结构体*/ pRNode *pt, *qt; P[i].lCursor = IndexCh(buffer[0]); pt = (pRNode*)malloc(sizeof(pRNode)); pt->rCursor = IndexCh(buffer[3]); pt->next = NULL; P[i].rHead = pt; n = 4; while('\0' != buffer[n]) { qt = (pRNode*)malloc(sizeof(pRNode)); qt->rCursor = IndexCh(buffer[n]); qt->next = NULL; pt->next = qt; pt = qt; n++; } P[i].rLength = n - 3; i++; /*调试时使用*/ } else printf("输入符号含非法在成分,请重
25

新输入!\n"); } } /*判断产生式正确性*/ bool CheckP(char * st) { int n; if(100 > IndexCh(st[0])) return false; if('-' != st[1]) return false; if('>' != st[2]) return false; for(n = 3; '\0' != st[n]; n ++) { if(-1 == IndexCh(st[n])) return false; } return true; } /*====================first & follow======================*/ /*计算 first 集,U->xx...*/ void First(int U) { int i,j; for(i = 0; i < PNum; i++) { if(P[i].lCursor == U) { struct pRNode* pt; pt = P[i].rHead; j = 0; while(j < P[i].rLength) { if(100 > pt->rCursor) { /*注:此处因编程出错,使空产生式时 rlength 同样是 1,故此处同样可处理 空产生式*/ AddFirst(U, pt->rCursor); break; } else

{ if(NULL == first[pt->rCursor 100]) { First(pt->rCursor); } AddFirst(U, pt->rCursor); if(!HaveEmpty(pt->rCursor)) { break; } else { pt = pt->next; } } j++; } if(j >= P[i].rLength) /*当产生式右 部都能推出空时*/ AddFirst(U, -1); } } } /*加入 first 集*/ void AddFirst(int U, int nCh) /*当数值 小于 100 时 nCh 为 Vt*/ /*当处理非终结符时,AddFirst 不添加空项 (-1)*/ { struct collectNode *pt, *qt; int ch; /*用于处理 Vn*/ pt = NULL; qt = NULL; if(nCh < 100) { pt = first[U - 100]; while(NULL != pt) { if(pt->nVt == nCh) break; else { qt = pt;
26

pt = pt->next; } } if(NULL == pt) { pt = (struct collectNode *)malloc(sizeof(struct collectNode)); pt->nVt = nCh; pt->next = NULL; if(NULL == first[U - 100]) { first[U - 100] = pt; } else { qt->next = pt; /*qt 指向 first 集的 最后一个元素*/ } pt = pt->next; } } else { pt = first[nCh - 100]; while(NULL != pt) { ch = pt->nVt; if(-1 != ch) { AddFirst(U, ch); } pt = pt->next; } } } /*判断 first 集中是否有空(-1)*/ bool HaveEmpty(int nVn) { if(nVn < 100) /*为终结符时(含-1),在 follow 集中用到*/ return false; struct collectNode *pt; pt = first[nVn - 100]; while(NULL != pt)

{ if(-1 == pt->nVt) return true; pt = pt->next; } return false; } /*计算 follow 集,例:U->xVy,U->xV.(注: 初始符必含#——"-1")*/ void Follow(int V) { int i; struct pRNode *pt ; if(100 == V) /*当为初始符时*/ AddFollow(V, -1, 0 ); for(i = 0; i < PNum; i++) { pt = P[i].rHead; while(NULL != pt && pt->rCursor != V) /*注此不能处理:U->xVyVz 的情况*/ pt = pt->next; if(NULL != pt) { pt = pt->next; /*V 右侧的符号*/ if(NULL == pt) /*当 V 后为空时 V->xV, 将左符的 follow 集并入 V 的 follow 集中*/ { if(NULL == follow[P[i].lCursor 100] && P[i].lCursor != V) { Follow(P[i].lCursor); } AddFollow(V, P[i].lCursor, 0); } else /*不为空时 V->xVy,(注意:y->), 调用 AddFollow 加入 Vt 或 y 的 first 集*/ { while(NULL != pt && HaveEmpty(pt->rCursor)) { AddFollow(V, pt->rCursor, 1); /*y 的前缀中有空时,加如 first 集*/ pt = pt->next; }
27

if(NULL == pt) /*当后面的字符可以 推出空时*/ { if(NULL == follow[P[i].lCursor 100] && P[i].lCursor != V) { Follow(P[i].lCursor); } AddFollow(V, P[i].lCursor, 0); } else /*发现不为空的字符时*/ { AddFollow(V, pt->rCursor, 1); } } } } } /*当数值小于 100 时 nCh 为 Vt*/ /*#用-1 表示,kind 用于区分是并入符号的 first 集,还是 follow 集 kind = 0 表加入 follow 集,kind = 1 加入 first 集*/ void AddFollow(int V, int nCh, int kind) { struct collectNode *pt, *qt; int ch; /*用于处理 Vn*/ pt = NULL; qt = NULL; if(nCh < 100) /*为终结符时*/ { pt = follow[V - 100]; while(NULL != pt) { if(pt->nVt == nCh) break; else { qt = pt; pt = pt->next; } } if(NULL == pt) {

pt = (struct collectNode *)malloc(sizeof(struct collectNode)); pt->nVt = nCh; pt->next = NULL; if(NULL == follow[V - 100]) { follow[V - 100] = pt; } else { qt->next = pt; /*qt 指向 follow 集的 最后一个元素*/ } pt = pt->next; } } else /*为非终结符时,要区分是加 first 还是 follow*/ { if(0 == kind) { pt = follow[nCh - 100]; while(NULL != pt) { ch = pt->nVt; AddFollow(V, ch, 0); pt = pt->next; } } else { pt = first[nCh - 100]; while(NULL != pt) { ch = pt->nVt; if(-1 != ch) { AddFollow(V, ch, 1); } pt = pt->next; } } } }
28

/*输出 first 或 follow 集*/ void ShowCollect(struct collectNode **collect) { int i; struct collectNode *pt; i = 0; while(NULL != collect[i]) { pt = collect[i]; printf("\n%c:\t", Vn[i]); while(NULL != pt) { if(-1 != pt->nVt) { printf(" %c", Vt[pt->nVt]); } else printf(" #"); pt = pt->next; } i++; } printf("\n"); } /*计算 first 和 follow*/ void FirstFollow() { int i; i = 0; while('\0' != Vn[i]) { if(NULL == first[i]) First(100 + i); i++; } i = 0; while('\0' != Vn[i]) { if(NULL == follow[i]) Follow(100 + i); i++; } }

/*=================构造预测分析表,例: U::xyz=============*/ void CreateAT() { int i; struct pRNode *pt; struct collectNode *ct; for(i = 0; i < PNum; i++) { pt = P[i].rHead; while(NULL != pt && HaveEmpty(pt->rCursor)) { /*处理非终结符,当为终结符时,定含 空为假跳出*/ ct = first[pt->rCursor - 100]; while(NULL != ct) { if(-1 != ct->nVt) analyseTable[P[i].lCursor 100][ct->nVt] = i; ct = ct->next; } pt = pt->next; } if(NULL == pt) { /*NULL == pt,说明 xyz->,用到 follow 中的符号*/ ct = follow[P[i].lCursor - 100]; while(NULL != ct) { if(-1 != ct->nVt) analyseTable[P[i].lCursor 100][ct->nVt] = i; else /*当含有#号时*/ analyseTable[P[i].lCursor 100][vtNum] = i; ct = ct->next; } } else { if(100 <= pt->rCursor) /*不含空的非
29

终结符*/ { ct = first[pt->rCursor - 100]; while(NULL != ct) { analyseTable[P[i].lCursor 100][ct->nVt] = i; ct = ct->next; } } else /*终结符或者空*/ { if(-1 == pt->rCursor) /*-1 为空产生 式时*/ { ct = follow[P[i].lCursor - 100]; while(NULL != ct) { if(-1 != ct->nVt) analyseTable[P[i].lCursor 100][ct->nVt] = i; else /*当含有#号时*/ analyseTable[P[i].lCursor 100][vtNum] = i; ct = ct->next; } } else /*为终结符*/ { analyseTable[P[i].lCursor 100][pt->rCursor] = i; } } } } } /*输出分析表*/ void ShowAT() { int i,j; printf("构造预测分析表如下:\n"); printf("\t|\t"); for(i = 0; i < vtNum; i++) {

printf("%c\t", Vt[i]); } printf("#\t\n"); printf("- - -\t|- - -\t"); for(i = 0; i <= vtNum; i++) printf("- - -\t"); printf("\n"); for(i = 0; i < vnNum; i++) { printf("%c\t|\t", Vn[i]); for(j = 0; j <= vtNum; j++) { if(-1 != analyseTable[i][j]) printf("R(%d)\t", analyseTable[i][j]); else printf("error\t"); } printf("\n"); } } /*================= 主 控 程 序 =====================*/ void Identify(char *st) { int current,step,r; /*r 表使用的产生 式的序号*/ printf("\n%s 的分析过程:\n", st); printf("步骤\t 分析符号栈\t 当前指示字 符\t 使用产生式序号\n");

step = 0; current = 0; /*符号串指示器*/ printf("%d\t",step); ShowStack(); printf("\t\t%c\t\t-\n", st[current]); while('#' != st[current]) { if(100 > analyseStack[topAnalyse]) /* 当 为 终 结 符时*/ { if(analyseStack[topAnalyse] ==
30

IndexCh(st[current])) { /*匹配出栈,指示器后移*/ Pop(); current++; step++; printf("%d\t", step); ShowStack(); printf("\t\t%c\t\t 出栈、后移\n", st[current]); } else { printf("%c-%c 不 匹 配 ! ", analyseStack[topAnalyse], st[current]); printf("此串不是此文法的句子! \n"); return; } } else /*当为非终结符时*/ { r = analyseTable[analyseStack[topAnalyse] - 100][IndexCh(st[current])]; if(-1 != r) { Push(r); /*产生式右部代替左部,指 示器不移动*/ step++; printf("%d\t", step); ShowStack(); printf("\t\t%c\t\t%d\n", st[current], r); } else { printf("无可用产生式, 此串不是此文 法的句子!\n"); return; } } } if('#' == st[current]) {

if(0 == topAnalyse && '#' == st[current]) { step++; printf("%d\t", step); ShowStack(); printf("\t\t%c\t\t 分 析 成 功 ! \n", st[current]); printf("%s 是给定文法的句子!\n", st); } else { while(topAnalyse > 0) { if(100 > analyseStack[topAnalyse]) /* 当 为 终 结 符时*/ { printf("无可用产生式, 此串不 是此文法的句子!\n"); return; } else { r = analyseTable[analyseStack[topAnalyse] - 100][vtNum]; if(-1 != r) { Push(r); /*产生式右部代替 左部,指示器不移动*/ step++; printf("%d\t", step); ShowStack(); if(0 == topAnalyse && '#' == st[current]) { printf("\t\t%c\t\t 分 析 成功!\n", st[current]); printf("%s 是给定文法的句子! \n", st); } } } /*栈顶出栈*/ void Pop() { topAnalyse--; } /*使用产生式入栈操作*/
31

else printf("\t\t%c\t\t%d\n", st[current], r); } else { printf("无可用产生式, 此串 不是此文法的句子!\n"); return; } } } } } } /*初始化栈及符号串*/ void InitStack() { int i; /*分析栈的初始化*/ for(i = 0; i < MaxStLength; i++) st[i] = '\0'; analyseStack[0] = -1; /*#(-1)入栈*/ analyseStack[1] = 100; /*初始符入栈*/ topAnalyse = 1; } /*显示符号栈中内容*/ void ShowStack() { int i; for(i = 0; i <= topAnalyse; i++) { if(100 <= analyseStack[i]) printf("%c", Vn[analyseStack[i] 100]); else { if(-1 != analyseStack[i]) printf("%c", Vt[analyseStack[i]]); else printf("#"); }

void Push(int r) { int i; struct pRNode *pt; Pop(); pt = P[r].rHead; if(-1 == pt->rCursor) /*为空产生式时*/ return; topAnalyse += P[r].rLength; for(i = 0; i < P[r].rLength; i++) { /*不为空产生式时*/ analyseStack[topAnalyse - i] = pt->rCursor;/*逆序入栈*/ pt = pt->next; }/*循环未完时 pt 为空,则说明 rLength 记录等出错*/ } 【程序截图】

32

33




友情链接: