编译原理_语法分析器_(java完美运行版)

编译原理语法分析器（java完美运行版）第一篇：编译原理语法分析器 (java完美运行版)实验二语法分析器一、实验目的通过完成预测分析法的语法分析程序，了解预测分析法和递归子程序法的区别和联系。

使学生了解语法分析的功能，掌握语法分析程序设计的原理和构造方法，训练学生掌握开发应用程序的基本方法。

有利于提高学生的专业素质，为培养适应社会多方面需要的能力。

二、实验内容υ根据某一文法编制调试 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 P=null;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;//储存VtObject 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(newJScrollPane(table));add(p2,“Center”);add(p3,“South”);b0.addActionListener(this);b1.addActionListener(this);b2.ad dActionListener(this);b3.addActionListener(this);setDefaultClose Operation(JFrame.EXIT_ON_CLOSE);table.setPreferredScrollable ViewportSize(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();String s[]=t1.getText().split(”n“);for(int i=0;ireturn;}if(s[i].charAt(0)<='Z'&&s[i].charAt(0)>='A'&&s[i].charAt(1)=='→'){ for(k=0;k=Vnnum){ Vn[Vnnum]=s[i].substring(0, 1);//存入Vn数据 Vnnum++;} P.add(s[i]);} else { t3.setText(”文法输入有误，请重新输入“);return;} } yn_null=new char[100];first=new char[Vnnum][100];int flag=0;String firstVn[]=null;firstComplete=new int[Vnnum];for(int i=0;Vn[i]!=null;i++)//依次求FIRST** { flag=0;firstVn=new String[20];if((flag=add_First(first[i],Vn[i],firstVn,flag))==-1)return;firstComplete[i]=1;} t3.append(”first集：“+”n“);//显示FIRST**for(inti=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(”fol low集：“+”n“);//显示FOLLOW**for(inti=0;Vn[i]!=null;i++){ t3.append(”follow(“+Vn[i]+”)={ “);for(i nt j=0;follow[i][j]!='';j++){ t3.append(follow[i][j]+” , “);} t3.append(”}“+”n“);} select=new char[P.size()][100];for(int i=0;itianjiaSelect(select[i],(String)P.elementAt(i),flag);}t3.append(”select集：“+”n“);//显示SELECT**for(int i=0;ifor(int i=0;Vn[i]!=null;i++)//判断select交集是否为空{ intbiaozhi=0;char save[]=new char[100];for(int j=0;jif(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];bia ozhi++;} 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.cha rAt(j))){ Vt[biaozhi]=t.charAt(j);biaozhi++;} } } } if(puanduanChar(Vt,'#'))//若可推出空集，则将#加入Vt。

编译原理考试题及答案汇总一、选择1．将编译程序分成若干个“遍”是为了_B__。

A . 提高程序的执行效率B.使程序的结构更加清晰C. 利用有限的机器内存并提高机器的执行效率D.利用有限的机器内存但降低了机器的执行效率2．正规式 MI 和 M2 等价是指__C__。

A . MI 和 M2 的状态数相等 B.Ml 和 M2 的有向弧条数相等。

C .M1 和 M2 所识别的语言集相等 D. Ml 和 M2 状态数和有向弧条数相等3．中间代码生成时所依据的是 _C_。

A．语法规则 B．词法规则 C．语义规则 D．等价变换规则4．后缀式 ab+cd+/可用表达式__B_来表示。

A． a+b/c+d B．(a+b)/(c+d) C． a+b/(c+d) D． a+b+c/d6．一个编译程序中，不仅包含词法分析，_A____，中间代码生成，代码优化，目标代码生成等五个部分。

A．( ) 语法分析 B．( )文法分析 C．( )语言分析 D．( )解释分析7．词法分析器用于识别__C___。

A．( ) 字符串 B．( )语句 C．( )单词 D．( )标识符8．语法分析器则可以发现源程序中的___D__。

A．( ) 语义错误 B．( ) 语法和语义错误C．( ) 错误并校正 D．( ) 语法错误9．下面关于解释程序的描述正确的是__B___。

(1) 解释程序的特点是处理程序时不产生目标代码(2) 解释程序适用于 COBOL 和 FORTRAN 语言(3) 解释程序是为打开编译程序技术的僵局而开发的A．( ) (1)(2) B．( ) (1) C．( ) (1)(2)(3) D．( ) (2)(3)10．解释程序处理语言时 , 大多数采用的是__B___方法。

A．( ) 源程序命令被逐个直接解释执行B．( ) 先将源程序转化为中间代码 , 再解释执行C．( ) 先将源程序解释转化为目标程序 , 再执行D．( ) 以上方法都可以11．编译过程中 , 语法分析器的任务就是__B___。

Java的编译原理概述java语⾔的"编译期"分为前端编译和后端编译两个阶段。

前端编译是指把*.java⽂件转变成*.class⽂件的过程; 后端编译(JIT, Just In Time Compiler)是指把字节码转变成机器码的过程。

在编译原理中, 将源代码编译成机器码, 主要经过下⾯⼏个步骤:Java中的前端编译java的前端编译(即javac编译)可分为解析与填充符号表、插⼊式注解处理器的注解处理、分析与字节码⽣成等三个过程。

解析与填充符号表解析步骤包括词法分析和语法分析两个阶段。

词法分析是将源代码的字符流转变为标记(Token)集合, 单个字符是程序编写过程的最⼩单位, ⽽标记则是编译过程的最⼩单位, 关键字、变量名、字⾯量、运算符都可以成为标记。

语法分析是根据Token序列构造抽象语法树的过程, 抽象语法树(AST)是⼀种⽤来描述程序代码语法结构的树形表⽰⽅式, 语法树的每⼀个节点都代表着程序代码中的⼀个语法结构, 如包、类型、修饰符、运算符、接⼝、返回值都可以是⼀个语法结构。

符号表是由⼀组符号地址和符号信息构成的表格。

在语法分析中, 符号表所登记的内容将⽤于语义检查和产⽣中间代码。

在⽬标代码⽣成阶段, 符号表是当对符号名进⾏地址分配时的依据。

插⼊式注解处理器插⼊式注解处理器可以看做是⼀组编译器的插件, 在这些插件⾥⾯, 可以读取、修改、添加抽象语法树中的任意元素。

如果这些插件在处理注解期间对语法数进⾏了修改, 编译器将回到解析与填充符号表的过程重新处理, 直到所有插⼊式注解处理器都没有再对语法数进⾏修改为⽌,每⼀次循环称为⼀个Round。

语义分析与字节码⽣成语法分析后, 编译器获得了程序代码的抽象语法树表⽰, 语法数能表⽰⼀个结构正确的源程序的抽象, 但⽆法保证源程序是符合逻辑的。

⽽语义分析的主要任务是对结构正确的源程序进⾏上下⽂有关性质的审查。

Javac的编译过程中, 语义分析过程分为标注检查、数据及控制流分析两个步骤。

Java实现《编译原理》简单-语法分析功能-LL（1）⽂法-程序解析Java 实现《编译原理》简单-语法分析功能-LL(1)⽂法 - 程序解析编译原理学习，语法分析程序设计（⼀）要求及功能已知 LL(1) ⽂法为：G'[E]: E→TE'E'→+TE'|εT→FT'T'→*FT'|εF→(E)|i为了⽅便处理，⽤：M 代替 E'，N 代表 T'；并展开相同同⼀⾮终结符的产⽣式；不影响含义，可⾃⾏再优化即有：G[E]: E→TMM→+TMM→εT→FNN→*FNN→εF→(E)F→i根据⽂法建⽴ LL(1) 分析表，并对输⼊串 i+i*i 进⾏语法分析，判断其是否是合法的句⼦（⼆）整体与执⾏结果所需类：执⾏结果：（三）程序源代码（1）Grammar.java ⽂件：package com.java997.analyzer.grammar; import java.io.File;import java.io.FileWriter;import java.io.Serializable;import java.io.Writer;import java.util.ArrayList;import java.util.HashMap;import java.util.Iterator;import java.util.Set;import java.util.TreeMap;import java.util.TreeSet;/*** LL(1)⽂法* 1.获取 First 集* 2.获取 Follow 集* 3.获取 SELECT 集** @author XiaoPengwei* @since 2019-06-18*/public class Grammar implements Serializable {private static final long serialVersionUID = 1L;public Grammar() {super();gsArray = new ArrayList<String>();nvSet = new TreeSet<Character>();ntSet = new TreeSet<Character>();firstMap = new HashMap<Character, TreeSet<Character>>();followMap = new HashMap<Character, TreeSet<Character>>();selectMap = new TreeMap<Character, HashMap<String, TreeSet<Character>>>(); }private String[][] analyzeTable;/*** Select集合*/private TreeMap<Character, HashMap<String, TreeSet<Character>>> selectMap;/*** LL（1）⽂法产⽣集合*/private ArrayList<String> gsArray;/*** 表达式集合*/private HashMap<Character, ArrayList<String>> expressionMap;/*** 开始符*/private Character s;/*** Vn⾮终结符集合*/private TreeSet<Character> nvSet;/*** Vt终结符集合*/private TreeSet<Character> ntSet;/*** First集合*/private HashMap<Character, TreeSet<Character>> firstMap;/*** Follow集合*/private HashMap<Character, TreeSet<Character>> followMap;public String[][] getAnalyzeTable() {return analyzeTable;}public void setAnalyzeTable(String[][] analyzeTable) {this.analyzeTable = analyzeTable;public TreeMap<Character, HashMap<String, TreeSet<Character>>> getSelectMap() {return selectMap;}public void setSelectMap(TreeMap<Character, HashMap<String, TreeSet<Character>>> selectMap) { this.selectMap = selectMap;}public HashMap<Character, TreeSet<Character>> getFirstMap() {return firstMap;}public void setFirstMap(HashMap<Character, TreeSet<Character>> firstMap) {this.firstMap = firstMap;}public HashMap<Character, TreeSet<Character>> getFollowMap() {return followMap;}public void setFollowMap(HashMap<Character, TreeSet<Character>> followMap) {this.followMap = followMap;}public HashMap<Character, ArrayList<String>> getExpressionMap() {return expressionMap;}public void setExpressionMap(HashMap<Character, ArrayList<String>> expressionMap) {this.expressionMap = expressionMap;}public ArrayList<String> getGsArray() {return gsArray;}public void setGsArray(ArrayList<String> gsArray) {this.gsArray = gsArray;}public Character getS() {return s;}public void setS(Character s) {this.s = s;}public TreeSet<Character> getNvSet() {return nvSet;}public void setNvSet(TreeSet<Character> nvSet) {this.nvSet = nvSet;}public TreeSet<Character> getNtSet() {return ntSet;}public void setNtSet(TreeSet<Character> ntSet) {this.ntSet = ntSet;}/*** 获取⾮终结符集与终结符集*/public void getNvNt() {for (String gsItem : gsArray) {String[] nvNtItem = gsItem.split("->");String charItemStr = nvNtItem[0];char charItem = charItemStr.charAt(0);// nv在左边nvSet.add(charItem);}for (String gsItem : gsArray) {String[] nvNtItem = gsItem.split("->");// nt在右边String nvItemStr = nvNtItem[1];// 遍历每⼀个字for (int i = 0; i < nvItemStr.length(); i++) {char charItem = nvItemStr.charAt(i);if (!nvSet.contains(charItem)) {ntSet.add(charItem);}}}}/*** 初始化表达式集合*/public void initExpressionMaps() {expressionMap = new HashMap<Character, ArrayList<String>>(); for (String gsItem : gsArray) {String[] nvNtItem = gsItem.split("->");String charItemStr = nvNtItem[0];String charItemRightStr = nvNtItem[1];char charItem = charItemStr.charAt(0);if (!expressionMap.containsKey(charItem)) {ArrayList<String> expArr = new ArrayList<String>();expArr.add(charItemRightStr);expressionMap.put(charItem, expArr);} else {ArrayList<String> expArr = expressionMap.get(charItem);expArr.add(charItemRightStr);expressionMap.put(charItem, expArr);}}}/*** 获取 First 集*/public void getFirst() {// 遍历所有Nv,求出它们的First集合Iterator<Character> iterator = nvSet.iterator();while (iterator.hasNext()) {Character charItem = iterator.next();ArrayList<String> arrayList = expressionMap.get(charItem);for (String itemStr : arrayList) {boolean shouldBreak = false;// Y1Y2Y3...Ykfor (int i = 0; i < itemStr.length(); i++) {char itemitemChar = itemStr.charAt(i);TreeSet<Character> itemSet = firstMap.get(charItem);if (null == itemSet) {itemSet = new TreeSet<Character>();}shouldBreak = calcFirst(itemSet, charItem, itemitemChar); if (shouldBreak) {break;}}}}}/*** 计算 First 函数** @param itemSet* @param charItem* @param itemitemChar* @return boolean*/private boolean calcFirst(TreeSet<Character> itemSet, Character charItem, char itemitemChar) {// 将它的每⼀位和Nt判断下// 是终结符或空串,就停⽌，并将它加到FirstMap中if (itemitemChar == 'ε' || ntSet.contains(itemitemChar)) {itemSet.add(itemitemChar);firstMap.put(charItem, itemSet);// break;return true;} else if (nvSet.contains(itemitemChar)) {// 这⼀位是⼀个⾮终结符ArrayList<String> arrayList = expressionMap.get(itemitemChar);for (int i = 0; i < arrayList.size(); i++) {String string = arrayList.get(i);char tempChar = string.charAt(0);calcFirst(itemSet, charItem, tempChar);}}return true;}/*** 获取 Follow 集合*/public void getFollow() {for (Character tempKey : nvSet) {TreeSet<Character> tempSet = new TreeSet<Character>();followMap.put(tempKey, tempSet);}// 遍历所有Nv,求出它们的First集合Iterator<Character> iterator = nvSet.descendingIterator();while (iterator.hasNext()) {Character charItem = iterator.next();System.out.println("charItem:" + charItem);Set<Character> keySet = expressionMap.keySet();for (Character keyCharItem : keySet) {ArrayList<String> charItemArray = expressionMap.get(keyCharItem);for (String itemCharStr : charItemArray) {System.out.println(keyCharItem + "->" + itemCharStr);TreeSet<Character> itemSet = followMap.get(charItem);calcFollow(charItem, charItem, keyCharItem, itemCharStr, itemSet);}}}}/*** 计算 Follow 集** @param putCharItem 正在查询item* @param charItem 待找item* @param keyCharItem 节点名* @param itemCharStr 符号集* @param itemSet 结果集合*/private void calcFollow(Character putCharItem, Character charItem, Character keyCharItem, String itemCharStr, TreeSet<Character> itemSet) {// （1）A是S（开始符)，加⼊#if (charItem.equals(s)) {itemSet.add('#');System.out.println("---------------find S:" + charItem + " ={#}+Follow(E)");followMap.put(putCharItem, itemSet);}// (2)Ab,=First(b)-ε,直接添加终结符if (TextUtil.containsAb(ntSet, itemCharStr, charItem)) {Character alastChar = TextUtil.getAlastChar(itemCharStr, charItem);System.out.println("---------------find Ab:" + itemCharStr + " " + charItem + " =" + alastChar);itemSet.add(alastChar);followMap.put(putCharItem, itemSet);// return;}// (2).2AB,=First(B)-ε,=First(B)-ε，添加first集合if (TextUtil.containsAB(nvSet, itemCharStr, charItem)) {Character alastChar = TextUtil.getAlastChar(itemCharStr, charItem);System.out.println("---------------find AB:" + itemCharStr + " " + charItem + " =First(" + alastChar + ")");TreeSet<Character> treeSet = firstMap.get(alastChar);itemSet.addAll(treeSet);if (treeSet.contains('ε')) {itemSet.add('#');}itemSet.remove('ε');followMap.put(putCharItem, itemSet);if (TextUtil.containsbAbIsNull(nvSet, itemCharStr, charItem, expressionMap)) {char tempChar = TextUtil.getAlastChar(itemCharStr, charItem);System.out.println("tempChar:" + tempChar + " key" + keyCharItem);if (!keyCharItem.equals(charItem)) {System.out.println("---------------find tempChar bA: " + "tempChar:" + tempChar + keyCharItem+ " " + itemCharStr + " " + charItem + " =Follow(" + keyCharItem + ")");Set<Character> keySet = expressionMap.keySet();for (Character keyCharItems : keySet) {ArrayList<String> charItemArray = expressionMap.get(keyCharItems);for (String itemCharStrs : charItemArray) {calcFollow(putCharItem, keyCharItem, keyCharItems, itemCharStrs, itemSet);}}}}}// (3)B->aA,=Follow(B),添加followBif (TextUtil.containsbA(nvSet, itemCharStr, charItem, expressionMap)) {if (!keyCharItem.equals(charItem)) {System.out.println("---------------find bA: " + keyCharItem + " " + itemCharStr + " " + charItem+ " =Follow(" + keyCharItem + ")");Set<Character> keySet = expressionMap.keySet();for (Character keyCharItems : keySet) {ArrayList<String> charItemArray = expressionMap.get(keyCharItems);for (String itemCharStrs : charItemArray) {calcFollow(putCharItem, keyCharItem, keyCharItems, itemCharStrs, itemSet);}}}}}/*** 获取 Select 集合*/public void getSelect() {// 遍历每⼀个表达式// HashMap<Character, HashMap<String, TreeSet<Character>>>Set<Character> keySet = expressionMap.keySet();for (Character selectKey : keySet) {ArrayList<String> arrayList = expressionMap.get(selectKey);// 每⼀个表达式HashMap<String, TreeSet<Character>> selectItemMap = new HashMap<String, TreeSet<Character>>(); for (String selectExp : arrayList) {/*** 存放select结果的集合*/TreeSet<Character> selectSet = new TreeSet<Character>();// set⾥存放的数据分3种情况,由selectExp决定// 1.A->ε,=follow(A)if (TextUtil.isEmptyStart(selectExp)) {selectSet = followMap.get(selectKey);selectSet.remove('ε');selectItemMap.put(selectExp, selectSet);}// 2.Nt开始,=Nt// <br>终结符开始if (TextUtil.isNtStart(ntSet, selectExp)) {selectSet.add(selectExp.charAt(0));selectSet.remove('ε');selectItemMap.put(selectExp, selectSet);}// 3.Nv开始，=first(Nv)if (TextUtil.isNvStart(nvSet, selectExp)) {selectSet = firstMap.get(selectKey);selectSet.remove('ε');selectItemMap.put(selectExp, selectSet);}selectMap.put(selectKey, selectItemMap);}}}/*** ⽣成预测分析表*/public void genAnalyzeTable() throws Exception {Object[] ntArray = ntSet.toArray();Object[] nvArray = nvSet.toArray();// 预测分析表初始化analyzeTable = new String[nvArray.length + 1][ntArray.length + 1];System.out.println("====================\n预测分析表\n====================");File outputFile = new File("D:\\template\\analyzer\\src\\main\\java\\com\\java997\\analyzer\\grammar\\analyzeTable.txt"); try (Writer writer = new FileWriter(outputFile)) {writer.write("====================\n预测分析表\n====================\n");// 输出⼀个占位符System.out.print("表" + "\t");writer.write("表" + "\t");analyzeTable[0][0] = "Nv/Nt";// 初始化⾸⾏for (int i = 0; i < ntArray.length; i++) {if (ntArray[i].equals('ε')) {ntArray[i] = '#';}writer.write(ntArray[i] + "\t\t");System.out.print(ntArray[i] + "\t\t");analyzeTable[0][i + 1] = ntArray[i] + "";}System.out.println("");writer.write("\n");for (int i = 0; i < nvArray.length; i++) {// ⾸列初始化writer.write(nvArray[i] + "\t");System.out.print(nvArray[i] + "\t");analyzeTable[i + 1][0] = nvArray[i] + "";for (int j = 0; j < ntArray.length; j++) {String findUseExp = TextUtil.findUseExp(selectMap, Character.valueOf((Character) nvArray[i]),Character.valueOf((Character) ntArray[j]));if (null == findUseExp) {writer.write("空\t\t");System.out.print("空\t\t");analyzeTable[i + 1][j + 1] = "";} else {writer.write(nvArray[i] + "->" + findUseExp + "\t");System.out.print(nvArray[i] + "->" + findUseExp + "\t");analyzeTable[i + 1][j + 1] = nvArray[i] + "->" + findUseExp; }}writer.write("\n");System.out.println();}} catch (Exception e) {e.printStackTrace();}}}（2）Analyzer.javapackage com.java997.analyzer.grammar;import java.util.ArrayList;import java.util.Stack;/*** <p>* 主程序句⼦分析器** @author XiaoPengwei* @since 2019-06-18*/public class Analyzer {public Analyzer() {super();analyzeStatck = new Stack<Character>();// 结束符进栈analyzeStatck.push('#');}private ArrayList<AnalyzeProduce> analyzeProduces;/*** LL（1）⽂法*/private Grammar ll1Grammar;public Grammar getLl1Grammar() {return ll1Grammar;}public void setLl1Grammar(Grammar ll1Grammar) {this.ll1Grammar = ll1Grammar;}/*** 开始符*/private Character startChar;/*** 分析栈*/private Stack<Character> analyzeStatck;/*** 剩余输⼊串*/private String str;/*** 推导所⽤产⽣或匹配*/private String useExp;public ArrayList<AnalyzeProduce> getAnalyzeProduces() {return analyzeProduces;}public void setAnalyzeProduces(ArrayList<AnalyzeProduce> analyzeProduces) {this.analyzeProduces = analyzeProduces;}public Character getStartChar() {return startChar;}public void setStartChar(Character startChar) {this.startChar = startChar;}public Stack<Character> getAnalyzeStatck() {return analyzeStatck;}public void setAnalyzeStatck(Stack<Character> analyzeStatck) {this.analyzeStatck = analyzeStatck;}public String getStr() {return str;}public void setStr(String str) {this.str = str;}public String getUseExp() {return useExp;}public void setUseExp(String useExp) {eExp = useExp;}/*** 分析*/public void analyze() {analyzeProduces = new ArrayList<AnalyzeProduce>();// 开始符进栈analyzeStatck.push(startChar);System.out.println("====================\nLL(1)⽂法分析过程\n====================");System.out.println("开始符:" + startChar);System.out.println("序号\t\t符号栈\t\t\t输⼊串\t\t\t所⽤产⽣式");int index = 0;// 开始分析// while (analyzeStatck.peek() != '#' && str.charAt(0) != '#') {while (!analyzeStatck.empty()) {index++;if (analyzeStatck.peek() != str.charAt(0)) {// 到分析表中找到这个产⽣式String nowUseExpStr = TextUtil.findUseExp(ll1Grammar.getSelectMap(), analyzeStatck.peek(), str.charAt(0)); //打印表格注意, 制表符的个数if (analyzeStatck.size()==1){System.out.println(index + "\t\t" + analyzeStatck.toString() + "\t\t\t\t" + str + "\t\t\t"+ analyzeStatck.peek() + "->" + nowUseExpStr);}else if (analyzeStatck.size()==2){System.out.println(index + "\t\t" + analyzeStatck.toString() + "\t\t\t" + str + "\t\t\t"+ analyzeStatck.peek() + "->" + nowUseExpStr);}else if (analyzeStatck.size()==3){System.out.println(index + "\t\t" + analyzeStatck.toString() + "\t\t" + str + "\t\t\t"+ analyzeStatck.peek() + "->" + nowUseExpStr);}else {System.out.println(index + "\t\t" + analyzeStatck.toString() + "\t" + str + "\t\t\t"+ analyzeStatck.peek() + "->" + nowUseExpStr);}AnalyzeProduce produce = new AnalyzeProduce();produce.setIndex(index);produce.setAnalyzeStackStr(analyzeStatck.toString());produce.setStr(str);if (null == nowUseExpStr) {produce.setUseExpStr("⽆法匹配!");} else {produce.setUseExpStr(analyzeStatck.peek() + "->" + nowUseExpStr);}analyzeProduces.add(produce);// 将之前的分析栈中的栈顶出栈analyzeStatck.pop();// 将要⽤到的表达式⼊栈,反序⼊栈if (null != nowUseExpStr && nowUseExpStr.charAt(0) != 'ε') {for (int j = nowUseExpStr.length() - 1; j >= 0; j--) {char currentChar = nowUseExpStr.charAt(j);analyzeStatck.push(currentChar);}}continue;}// 如果可以匹配,分析栈出栈，串去掉⼀位if (analyzeStatck.peek() == str.charAt(0)) {if (analyzeStatck.size()==1){System.out.println(index + "\t\t" + analyzeStatck.toString() + "\t\t\t\t" + str + "\t\t\t" + "“" + str.charAt(0) + "”匹配");}else if (analyzeStatck.size()==2){System.out.println(index + "\t\t" + analyzeStatck.toString() + "\t\t\t" + str + "\t\t\t" + "“" + str.charAt(0) + "”匹配");}else if (analyzeStatck.size()==3){System.out.println(index + "\t\t" + analyzeStatck.toString() + "\t\t" + str + "\t\t\t" + "“" + str.charAt(0) + "”匹配");}else {System.out.println(index + "\t\t" + analyzeStatck.toString() + "\t" + str + "\t\t\t" + "“"+ str.charAt(0) + "”匹配");}AnalyzeProduce produce = new AnalyzeProduce();produce.setIndex(index);produce.setAnalyzeStackStr(analyzeStatck.toString());produce.setStr(str);produce.setUseExpStr("“" + str.charAt(0) + "”匹配");analyzeProduces.add(produce);analyzeStatck.pop();str = str.substring(1);continue;}}}}（3）AnalyzeProduce.javapackage com.java997.analyzer.grammar;import java.io.Serializable;/*** <p>* 分析过程 Bean** @author XiaoPengwei* @since 2019-06-18*/public class AnalyzeProduce implements Serializable {private static final long serialVersionUID = 10L;private Integer index;private String analyzeStackStr;private String str;private String useExpStr;public Integer getIndex() {return index;}public void setIndex(Integer index) {this.index = index;}public String getAnalyzeStackStr() {return analyzeStackStr;}public void setAnalyzeStackStr(String analyzeStackStr) { this.analyzeStackStr = analyzeStackStr;}public String getStr() {return str;}public void setStr(String str) {this.str = str;}public String getUseExpStr() {return useExpStr;}public void setUseExpStr(String useExpStr) {eExpStr = useExpStr;}}（4）Main.javapackage com.java997.analyzer.grammar;import java.util.ArrayList;import java.util.TreeSet;/*** <p>* 主程序** @author XiaoPengwei* @since 2019-06-18*/public class Main {public static void main(String[] args) throws Exception { // 第⼀步：获取 LL(1)⽂法ArrayList<String> gsArray = new ArrayList<String>(); Grammar grammar = new Grammar();//初始化 LL(1), 设定该⽂法的产⽣式initGs(gsArray);grammar.setGsArray(gsArray);grammar.getNvNt();grammar.initExpressionMaps();grammar.getFirst();// 设置开始符grammar.setS('E');grammar.getFollow();grammar.getSelect();//打印预测分析表, 并保存⽂件grammar.genAnalyzeTable();// 创建⼀个分析器Analyzer analyzer = new Analyzer();// 设定开始符号analyzer.setStartChar('E');analyzer.setLl1Grammar(grammar);// 待分析的字符串analyzer.setStr("i+i*i#");// 执⾏分析, 打印分析步骤, 保存⽂件analyzer.analyze();}/*** 获取⾮终结符集与终结符集** @param gsArray* @param nvSet* @param ntSet*/private static void getNvNt(ArrayList<String> gsArray, TreeSet<Character> nvSet, TreeSet<Character> ntSet) { for (String gsItem : gsArray) {String[] nvNtItem = gsItem.split("->");String charItemStr = nvNtItem[0];char charItem = charItemStr.charAt(0);// nv在左边nvSet.add(charItem);}for (String gsItem : gsArray) {String[] nvNtItem = gsItem.split("->");// nt在右边String nvItemStr = nvNtItem[1];// 遍历每⼀个字for (int i = 0; i < nvItemStr.length(); i++) {char charItem = nvItemStr.charAt(i);if (!nvSet.contains(charItem)) {ntSet.add(charItem);}}}}/*** 初始化 LL(1)⽂法, 设定产⽣式** @param gsArray*/private static void initGs(ArrayList<String> gsArray) {//E' = M//T' = NgsArray.add("E->TM");gsArray.add("M->+TF");gsArray.add("M->ε");gsArray.add("T->FN");gsArray.add("N->*FN");gsArray.add("N->ε");gsArray.add("F->(E)");gsArray.add("F->i");}}（5）TextUtil.javapackage com.java997.analyzer.grammar;import java.util.ArrayList;import java.util.HashMap;import java.util.Set;import java.util.TreeMap;import java.util.TreeSet;/*** <p>* 字符⼯具类** @author XiaoPengwei* @since 2019-06-18*/public class TextUtil {/*** (3)B->aA,=Follow(B)** @param nvSet* @param itemCharStr* @param a* @param expressionMap*/public static boolean containsbA(TreeSet<Character> nvSet, String itemCharStr, Character a,HashMap<Character, ArrayList<String>> expressionMap) {String aStr = a.toString();String lastStr = itemCharStr.substring(itemCharStr.length() - 1);return lastStr.equals(aStr);}/*** 形如 aBb,b=空** @param nvSet* @param itemCharStr* @param a* @param expressionMap*/public static boolean containsbAbIsNull(TreeSet<Character> nvSet, String itemCharStr, Character a, HashMap<Character, ArrayList<String>> expressionMap) {String aStr = a.toString();if (containsAB(nvSet, itemCharStr, a)) {Character alastChar = getAlastChar(itemCharStr, a);System.out.println("----------------+++++++++++++++++++--" + expressionMap.toString());ArrayList<String> arrayList = expressionMap.get(alastChar);if (arrayList.contains("ε")) {System.out.println(alastChar + " contains('ε')" + aStr);return true;}}return false;}/***是否包含这种的字符串<Br>* (2)Ab,=First(b)-ε,直接添加终结符** @param ntSet* @param itemCharStr* @param a* @return boolean*/public static boolean containsAb(TreeSet<Character> ntSet, String itemCharStr, Character a) {String aStr = a.toString();if (itemCharStr.contains(aStr)){int aIndex = itemCharStr.indexOf(aStr);String findStr;try {findStr = itemCharStr.substring(aIndex + 1, aIndex + 2);} catch (Exception e) {return false;}return ntSet.contains(findStr.charAt(0));} else {return false;}}/*** 是否包含这种的字符串<Br>* (2).2Ab,=First(b)-ε* @param nvSet* @param itemCharStr* @param a* @return boolean*/public static boolean containsAB(TreeSet<Character> nvSet, String itemCharStr, Character a) { String aStr = a.toString();if (itemCharStr.contains(aStr)) {int aIndex = itemCharStr.indexOf(aStr);String findStr;try {findStr = itemCharStr.substring(aIndex + 1, aIndex + 2);} catch (Exception e) {return false;}return nvSet.contains(findStr.charAt(0));} else {return false;}}/*** 获取 A 后的字符** @param itemCharStr* @param a*/public static Character getAlastChar(String itemCharStr, Character a) {String aStr = a.toString();if (itemCharStr.contains(aStr)) {int aIndex = itemCharStr.indexOf(aStr);String findStr = "";try {findStr = itemCharStr.substring(aIndex + 1, aIndex + 2);} catch (Exception e) {return null;}return findStr.charAt(0);}return null;}/*** 是否为ε开始的** @param selectExp*/public static boolean isEmptyStart(String selectExp) {char charAt = selectExp.charAt(0);return charAt == 'ε';}/*** 是否是终结符开始的** @param ntSet* @param selectExp*/public static boolean isNtStart(TreeSet<Character> ntSet, String selectExp) {char charAt = selectExp.charAt(0);return ntSet.contains(charAt);}/*** 是否是⾮终结符开始的** @param nvSet* @param selectExp* @return*/public static boolean isNvStart(TreeSet<Character> nvSet, String selectExp) {char charAt = selectExp.charAt(0);return nvSet.contains(charAt);}/*** 查找产⽣式** @param selectMap* @param peek 当前 Nv* @param charAt 当前字符* @return*/public static String findUseExp(TreeMap<Character, HashMap<String, TreeSet<Character>>> selectMap, Character peek, char charAt) {try {HashMap<String, TreeSet<Character>> hashMap = selectMap.get(peek);Set<String> keySet = hashMap.keySet();for (String useExp : keySet) {TreeSet<Character> treeSet = hashMap.get(useExp);if (treeSet.contains(charAt)) {return useExp;}}} catch (Exception e) {return null;}return null;}}执⾏ Main.java。

学院（系）名称：计算机工程系实验环境：Windows XP实验分析：（1）定义部分：定义常量、变量、数据结构。

（2）初始化：设立LL(1)分析表、初始化变量空间（包括堆栈、结构体、数组、临时变量等）；（3）控制部分：从键盘输入一个表达式符号串；（4）利用LL(1)分析算法进行表达式处理：根据LL(1)分析表对表达式符号串进行堆栈（或其他）操作，输出分实验程序：#include<iostream>#include<stack>using namespace std;stack<char> symbol;stack<int> state;char sen[50];char sym[12][6]={//符号表{'s','e','e','s','e','e'},{'e','s','e','e','e','a'},{'r','r','s','r','r','r'},{'r','r','r','r','r','r'},{'s','e','e','s','e','e'},{'r','r','r','r','r','r'},{'s','e','e','s','e','e'},{'s','e','e','s','e','e'},{'e','s','e','e','s','e'},{'r','r','s','r','r','r'},{'r','r','r','r','r','r'},{'r','r','r','r','r','r'}};char snum[12][6]={//数字表{5,1,1,4,2,1},{3,6,5,3,2,0},{2,2,7,2,2,2},{4,4,4,4,4,4},{5,1,1,4,2,1},{6,6,6,6,6,6},{5,1,1,4,2,1},{5,1,1,4,2,1},{3,6,5,3,11,4},{1,1,7,1,1,1},{3,3,3,3,3,3},{5,5,5,5,5,5}};int go2[12][3]={//goto表{1,2,3},{0,0,0},{0,0,0},{0,0,0},{8,2,3},{0,0,0},{0,9,3},{0,0,10},{0,0,0},{0,0,0},{0,0,0},{0,0,0}};void action(int i,char *&a,char &how,int &num,char &A,int &b)//action函数[i,a] {int j;switch(*a){case 'i':j=0;break;case '+':j=1;break;case '*':j=2;break;case '(':j=3;break;case ')':j=4;break;case '#':j=5;break;default:j=-1;break;}if(j!=-1){how=sym[i][j];num=snum[i][j];if(how=='r'){switch(num){case 1:A='E',b=3;cout<<"按E->E+T规约"<<endl; break;case 2:A='E',b=1;cout<<"按E->T规约"<<endl; break;case 3:A='T',b=3;cout<<"按T->T*F规约"<<endl; break;case 4:A='T',b=1;cout<<"按T->F规约"<<endl; break;case 5:A='F',b=3;cout<<"按F->(E)规约"<<endl; break;case 6:A='F',b=1;cout<<"按F->id规约"<<endl; break;default:break;}}}}int go(int t,char A)//goto[t,A] {switch(A){case 'E':return go2[t][0];break;case 'T':return go2[t][1];break;case 'F':return go2[t][2];break;}}void error(int i,int j,char *&a)//error处理函数{cout<<"error"<<endl;switch(j){case 1://期望输入id或左括号,但是碰到+,*,或$,就假设已经输入id了,转到状态5 state.push(5);symbol.push('i');//必须有这个,如果假设输入id的话,符号栈里必须有....cout<<"缺少运算对象id"<<endl;break;case 2://从输入中删除右括号a++;cout<<"不配对的右括号"<<endl;break;case 3://期望碰到+,但是输入id或左括号,假设已经输入算符+,转到状态6state.push(6);symbol.push('+');cout<<"缺少运算符"<<endl;break;case 4://缺少右括号,假设已经输入右括号,转到状态11state.push(11);symbol.push(')');cout<<"缺少右括号"<<endl;break;case 5:a++;cout<<"*号无效,应该输入+号!"<<endl;case 6:a++;}}int main(){int s;char *a;char how;int num;int b;char A;while(1){cin>>sen;a=sen;state.push(0);//先输入0状态while(*a!='\0'){b=0;num=0;how='\0';A='\0';s=state.top();action(s,a,how,num,A,b);if(how=='s')//移进{cout<<"移进"<<endl;symbol.push(*a);state.push(num);// if(*a=='i')// a++;//在这里忽略i后面的da++;}else if(how=='r')//规约{for(int i=0;i<b;i++){if(!state.empty())state.pop();if(!symbol.empty())symbol.pop();}int t=state.top();symbol.push(A);state.push(go(t,A));}else if(how=='a')//接受break;else{error(s,num,a);//错误处理}}cout<<"成功接受"<<endl;}return 0;}测试用例：i*(i+i)+i#测试结果：心得体会：通过这次实验，我对编译原理这门专业必修课有了进一步的深层次了解，把理论知识应用于实验中，实验过程中对于程序的逻辑理解欠缺了考虑，在多次的调试和改进中最终完善了程序，而在调试过程中学习的知识得到了完善和补充，对语法分析器的理解更进一步。

编译原理实验词法分析器与语法分析器实现词法分析器与语法分析器是编译器的两个重要组成部分，它们在编译过程中扮演着至关重要的角色。

词法分析器负责将源代码转化为一个个标记（token）序列，而语法分析器则根据词法分析器生成的标记序列构建语法树，验证源代码的语法正确性。

本实验旨在实现一个简单的词法分析器和语法分析器。

实验一：词法分析器实现在实现词法分析器之前，需要定义所需词法项的规则。

以C语言为例，常见的词法项包括关键字（如int、if、for等）、标识符、运算符（如+、-、*、/等）、常量（如整数、浮点数等）和分隔符（如括号、逗号等）。

接下来，我们来实现一个简单的C语言词法分析器。

1. 定义词法项的规则在C语言中，关键字和标识符由字母、数字和下划线组成，且首字符不能为数字。

运算符包括各种数学运算符和逻辑运算符。

常量包括整数和浮点数。

分隔符包括括号、逗号等。

2. 实现词法分析器的代码下面是一个简单的C语言词法分析器的实现代码：```pythondef lexer(source_code):keywords = ['int', 'if', 'for'] # 关键字列表operators = ['+', '-', '*', '/'] # 运算符列表separators = ['(', ')', '{', '}', ',', ';'] # 分隔符列表tokens = [] # 标记序列列表current_token = '' # 当前标记for char in source_code:if char.isspace(): # 如果是空格，则忽略continueelif char.isalpha(): # 如果是字母，则可能是关键字或标识符的一部分current_token += charelif char.isdigit(): # 如果是数字，则可能是常量的一部分current_token += charelif char in operators or char in separators: # 如果是运算符或分隔符，则当前标记结束if current_token:tokens.append(current_token)current_token = ''tokens.append(char)else: # 如果是其他字符，则当前标记结束if current_token:tokens.append(current_token)current_token = ''return tokens```以上代码通过遍历源代码的字符，根据定义的规则生成一个个标记，存储在`tokens`列表中。

编译原理实验⼆：LL（1）语法分析器⼀、实验要求 1. 提取左公因⼦或消除左递归（实现了消除左递归） 2. 递归求First集和Follow集 其它的只要按照课本上的步骤顺序写下来就好（但是代码量超多...），下⾯我贴出实验的⼀些关键代码和算法思想。

⼆、基于预测分析表法的语法分析 2.1 代码结构 2.1.1 Grammar类 功能：主要⽤来处理输⼊的⽂法，包括将⽂法中的终结符和⾮终结符分别存储，检测直接左递归和左公因⼦，消除直接左递归，获得所有⾮终结符的First集，Follow集以及产⽣式的Select集。

#ifndef GRAMMAR_H#define GRAMMAR_H#include <string>#include <cstring>#include <iostream>#include <vector>#include <set>#include <iomanip>#include <algorithm>using namespace std;const int maxn = 110;//产⽣式结构体struct EXP{char left; //左部string right; //右部};class Grammar{public:Grammar(); //构造函数bool isNotTer(char x); //判断是否是终结符int getTer(char x); //获取终结符下标int getNonTer(char x); //获取⾮终结符下标void getFirst(char x); //获取某个⾮终结符的First集void getFollow(char x); //获取某个⾮终结符的Follow集void getSelect(char x); //获取产⽣式的Select集void input(); //输⼊⽂法void scanExp(); //扫描输⼊的产⽣式，检测是否有左递归和左公因⼦void remove(); //消除左递归void solve(); //处理⽂法，获得所有First集，Follow集以及Select集void display(); //打印First集,Follow集,Select集void debug(); //⽤于debug的函数~Grammar(); //析构函数protected:int cnt; //产⽣式数⽬EXP exp[maxn]; //产⽣式集合set<char> First[maxn]; //First集set<char> Follow[maxn]; //Follow集set<char> Select[maxn]; //select集vector<char> ter_copy; //去掉$的终结符vector<char> ter; //终结符vector<char> not_ter; //⾮终结符};#endif 2.1.2 AnalyzTable类 功能：得到预测分析表，判断输⼊的⽂法是否是LL(1)⽂法，⽤预测分析表法判断输⼊的符号串是否符合刚才输⼊的⽂法，并打印出分析过程。