语法分析程序
一、作业目的和要求
通过设计、编制、调试一个典型的语法分析程序（任选有代表性的语法分析方法，如LL(1)、递归下降分析法、LR、算符优先分析法）等，作为编制语法分析程序的依据，对词法分析器所提供的单词序列进行语法检测和结构分析，实现并进一步掌握常用的语法分析方法。
二、作业内容
选择对各种常见高级程序设计语言都较为通用的语法结构作为分析对象（例如表达式、if、while、for等等），给出其文法规则描述（注意，文法规则的描述要符合所选分析方法的要求，比如用LL(1)分析法，文法必须是LL(1)文法），设计并实现一个完整的语法分析程序。
- 输入：源程序以文件的形式输入。
- 输出：对于输入的源程序，如果输入源程序是给定文法定义的合法程序，则输出”success”，如果不是，即输入源程序有错误，则输出“Error”,并且尽可能指出出错位置和原因。
三、作业要求
运用的Java语言写成的语法分析程序，
语法成分包括：if选择结构，while循环结构，for循环结构。
2、说明选择的语法分析方法是哪种？描述总体设计思路和主要的流程图。
语法分析的方法是LL(1)文法。
- 设计思路：
- 1.构造单个文法符号X的first集：
如果X为终结符,First(X)=X；
如果X->ε是产生式，把ε加入First(X)；
如果X是非终结符，如X->YZW。从左往右扫描产生式右部，把First(Y)加入First(X)； 如果First(Y)不包含ε，表示Y不可为空，便不再往后处理；如果First(Y)包含ε，表示Y可为空，则处理Z，依次类推。
构造文法符号串的first集，如：X->YZW；求YZW的first集
从左往右扫描该式，加入其非空first集：把First(Y)加入First(YZW)
若包含空串，处理下一个符号：如果First(Y)包含空串，便处理Z；不包含就退出；处理到尾部，即所有符号的first集都包含空串 把空串加入First(YZW)。 - 2.在计算First(X)集之后的基础上：
(1)$属于FOLLOW(S)，S是开始符；
(2)查找输入的所有产生式，确定X后紧跟的终结符；
(3)如果存在A->αBβ，（α、β是任意文法符号串，A、B为非终结符），把first(β)的非空符号加入follow(B)；
(4)如果存在A->αB或A->αBβ 但first(β)包含空，把follow(A)加入follow(B)。 - 3.构造预测分析表：
对于每个产生式A->α，first(α)中的终结符a，把A->α加入M[A,a]。
如果空串在first(α)中，说明可为空，找它的follow集，对于follow(A)中的终结符b，把A->α加入M[A,b]；
如果空串在first(α)中，且 “$”也在follow(A)中，说明A后可以接终结符，故把A->α加入M[A,$]中。 - 4.执行分析：
输入一个串，文法G的预测分析表，输出推导过程：
$ 和 开始符S入栈，栈顶符号X，index指向分析串的待分析符号a。
栈非空执行以下循环：
如果X==a，表示匹配，符号栈弹出一个，index++指向下一个符号；
否则，如果X是终结符，出错；
否则，如果查表为error，出错；
否则，查表正确，弹出栈顶符号，把其右部各个符号进栈，令X为栈顶符号。 - 流程图：
package Try; interface MyAnalyseFun { void Init();//初始化 void getVnVt();//获取非终结符和终结符的集合 void getFirst(Character c);//first集 void getFirst(String s);//任意字符的first集 void getFollow(char c);//follow集 void createTable();//构造表 void analyzeLL();//LL(1)分析过程 String find(char X, char a);//查找 void insert(char X, char a,String s);//插入 void displayLL();//输出分析过程 void ouput();//其他输出信息 } package Try; import java.io.*; import java.util.*; public class MyAnalyse implements MyAnalyseFun{ / * 几个比较重要的参数 * @param MyfirstSet 终结符的first集合 * @param MyfirstSetX 任意符号的first集合 * @param start 文法的开始符 * @param MyfollowSet follow集 * @param VnSet 终结符的集合 * @param VtSet 终结符的集合 * @param inputStrings 文法拓展的输入 * @param outputSet 输出的集合 * @param table 分析表 * @param MyAnaStatck 分析栈 * @param strInput 需要使用预测分析器的输入串 * @param MyAction 分析动作 * @param Index 分析的索引值 */ //从文件中读入时后台无法识别空串ε，因此用符号&代替空串ε //first集是终结符的first集 protected HashMap
> MyfirstSet = new HashMap<>(); //firstX集是指任意符号串的first集 protected HashMap
> MyfirstSetX = new HashMap<>(); //文法的开始符 protected Character start = 'S'; //follow集 protected HashMap
> MyfollowSet = new HashMap<>(); //存储非终结符的结合 protected HashSet
VnSet = new HashSet<>(); //存储终结符的结合 protected HashSet
VtSet = new HashSet<>(); protected HashMap
> outputSet = new HashMap<>(); //输入文法 //S->a|^|(T) //T->SU //U->,SU|& // protected String [] inputStrings = { "S->a", // "S->^", // "S->(T)", // "T->SU", // "U->,SU", // //"U->ε", // "U->&" }; //定义分析表 protected String [][] table; //分析栈 protected Stack
MyAnaStatck = new Stack<>(); //定义要分析的输入串 protected String strInput = "(a,a)$"; //对动作的初始化 protected String MyAction = ""; int Index = 0; //从文件中读入 protected String[] inputStrings = getSource(); protected MyAnalyse() { } public static void main(String[] args){ MyAnalyse test = new MyAnalyse(); test.getVnVt(); test.Init(); test.createTable(); test.analyzeLL(); test.ouput(); } //从文件中读入文法的方法 public static String[] getSource(){ StringBuffer temp = new StringBuffer(); FileInputStream fis= null; try { fis = new FileInputStream("E:\\readin.txt"); byte[] buff=new byte[1024]; int len=0; while((len=fis.read(buff))!=-1){ temp.append(new String(buff,0,len)); } } catch (Exception e) { e.printStackTrace(); } finally { try { fis.close(); } catch (IOException e) { e.printStackTrace(); } } return temp.toString().split("\n"); } //初始化 @Override public void Init() { for (String s1 : inputStrings) { //"S->a", //"S->^", //"S->(T)", //"T->SU", //"U->,SU", //"U->&" String[] str = s1.split("->");//通过符号“->”分隔每行的文法 char c = str[0].charAt(0);//取得左边的非终结符 ArrayList
list = outputSet.containsKey(c) ? outputSet.get(c) : new ArrayList<>(); list.add(str[1]);//添加文法右边的内容到集合中 outputSet.put(c, list); } //求非终结符的first集 for (Character c1 : VnSet) getFirst(c1); for (Character c2 : VnSet) { ArrayList
l = outputSet.get(c2); for (String s2 : l) getFirst(s2); } //求出follow集 getFollow(start); for (Character c3 : VnSet) { getFollow(c3); } } @Override public void getVnVt() {//取出终结符和非终结符的集合 for (String s3 : inputStrings) { String[] str = s3.split("->"); VnSet.add(str[0].charAt(0)); } for (String s4 : inputStrings) { String[] str = s4.split("->"); String right = str[1]; for (int i = 0; i < right.length(); i++) if (!VnSet.contains(right.charAt(i))) VtSet.add(right.charAt(i)); } } @Override public void getFirst(Character c) { ArrayList
list = outputSet.get(c); HashSet
set = MyfirstSet.containsKey(c) ? MyfirstSet.get(c) : new HashSet
(); // c为终结符 直接添加 if (VtSet.contains(c)) { set.add(c); MyfirstSet.put(c, set); return; } // c为非终结符 处理其每条产生式 for (String s5 : list) { // c 推出空串 直接添加 if (s5 == Character.toString('&')) { set.add('&'); } // X -> Y1Y2Y3… 情况 else { // 从左往右扫描生成式右部 int i = 0; while (i < s5.length()) { char tn = s5.charAt(i); //先处理防止未初始化 getFirst(tn); HashSet
tvSet = MyfirstSet.get(tn); // 将其first集加入左部 for (Character tmp : tvSet) set.add(tmp); // 若包含空串 处理下一个符号 if (tvSet.contains('&')) i++; // 否则退出 处理下一个产生式 else break; } } } MyfirstSet.put(c, set); } @Override public void getFirst(String s) { HashSet
set = (MyfirstSetX.containsKey(s))? MyfirstSetX.get(s) : new HashSet
(); // 从左往右扫描该式 int i = 0; while (i < s.length()) { char tn = s.charAt(i); HashSet
tvSet = MyfirstSet.get(tn); // 将其非空 first集加入左部 for (Character tmp : tvSet) if(tmp != '&') set.add(tmp); // 若包含空串 处理下一个符号 if (tvSet.contains('&')) i++; // 否则结束 else break; // 到了尾部 即所有符号的first集都包含空串 把空串加入 if (i == s.length()) { set.add('&'); } } MyfirstSetX.put(s, set); } @Override public void getFollow(char ch) { ArrayList
list = outputSet.get(ch); HashSet
setA = MyfollowSet.containsKey(ch) ? MyfollowSet.get(ch) : new HashSet
(); //如果是开始符 添加 $ if (ch == start) { setA.add('$'); } //查找输入的所有产生式，确定c的后跟 终结符 for (Character cha : VnSet) { ArrayList
l = outputSet.get(cha); for (String s : l) for (int i = 0; i < s.length(); i++) if (s.charAt(i) == ch && i + 1 < s.length() && VtSet.contains(s.charAt(i + 1))) setA.add(s.charAt(i + 1)); } MyfollowSet.put(ch, setA); //处理c的每一条产生式 for (String s : list) { int i = s.length() - 1; while (i >= 0 ) { char tn = s.charAt(i); //只处理非终结符 if(VnSet.contains(tn)){ // 都按 A->αB& 形式处理 //若&不存在 followA 加入 followB //若&存在，把&的非空first集 加入followB //若&存在 且 first(&)包含空串 followA 加入 followB //若&存在 if (s.length() - i - 1 > 0) { String right = s.substring(i + 1); //非空first集 加入 followB HashSet
setF = null; if( right.length() == 1 && MyfirstSet.containsKey(right.charAt(0))) { setF = MyfirstSet.get(right.charAt(0)); } else{ if(!MyfirstSetX.containsKey(right)){ HashSet
set = new HashSet
(); MyfirstSetX.put(right, set); } setF = MyfirstSetX.get(right); } HashSet
setX = MyfollowSet.containsKey(tn) ? MyfollowSet.get(tn) : new HashSet
(); for (Character cha : setF) { if (cha != '&') { setX.add(cha); } } MyfollowSet.put(tn, setX); // 若first(&)包含& followA 加入 followB if(setF.contains('&')){ if(tn != ch){ HashSet
setB = MyfollowSet.containsKey(tn) ? MyfollowSet.get(tn) : new HashSet
(); for (Character cha : setA) { setB.add(cha); } MyfollowSet.put(tn, setB); } } } //若&不存在 followA 加入 followB else{ // A和B相同不添加 if(tn != ch){ HashSet
setB = MyfollowSet.containsKey(tn) ? MyfollowSet.get(tn) : new HashSet
(); for (Character cha : setA) setB.add(cha); MyfollowSet.put(tn, setB); } } i--; } //如果是终结符往前扫描 如 A->aaaBCDaaaa 此时&为 CDaaaa else i--; } } } @Override public void createTable() {//构造预测分析表的格式 //终结符数组 Object[] VtArray = VtSet.toArray(); //非终结符数组 Object[] VnArray = VnSet.toArray(); // 预测分析表初始化 table = new String[VnArray.length + 1][VtArray.length + 1]; table[0][0] = "Vn/Vt"; //初始化首行首列 for (int i = 0; i < VtArray.length; i++) table[0][i + 1] = (VtArray[i].toString().charAt(0) == '&') ? "$" : VtArray[i].toString(); for (int i = 0; i < VnArray.length; i++) table[i + 1][0] = VnArray[i] + ""; //全部置error for (int i = 0; i < VnArray.length; i++) for (int j = 0; j < VtArray.length; j++) table[i + 1][j + 1] = "error"; //插入生成式 for (char A : VnSet) { ArrayList
l = outputSet.get(A); for(String s : l){ HashSet
set = MyfirstSetX.get(s); for (char a : set) insert(A, a, s); if(set.contains('&')) {//如果包含& HashSet
setFollow = MyfollowSet.get(A); if(setFollow.contains('$'))//判断follow集中是否包含$ insert(A, '$', s); for (char b : setFollow) insert(A, b, s); } } } } @Override public void analyzeLL() { System.out.println("-------------------1.LL分析过程-------------------"); System.out.println("| 分析栈 输入串 动作| "); MyAnaStatck.push('$'); MyAnaStatck.push('S'); displayLL();//调用分析过程方法 char X = MyAnaStatck.peek(); while (X != '$') { char a = strInput.charAt(Index); if (X == a) { MyAction = "match " + MyAnaStatck.peek(); MyAnaStatck.pop(); Index++; } else if (VtSet.contains(X)) return; else if (find(X, a).equals("error")) return; else if (find(X, a).equals("&")) { MyAnaStatck.pop(); MyAction = X + "->&"; } else { String str = find(X, a); if (str != "") { MyAction = X + "->" + str; MyAnaStatck.pop(); int len = str.length(); for (int i = len - 1; i >= 0; i--) MyAnaStatck.push(str.charAt(i)); } else { System.out.println("error at '" + strInput.charAt(Index) + " in " + Index); return; } } X = MyAnaStatck.peek(); displayLL(); } System.out.println("LL(1)文法分析成功！"); System.out.println("-------------------LL分析过程-------------------"); } @Override public String find(char X, char a) { for (int i = 0; i < VnSet.size() + 1; i++) { if (table[i][0].charAt(0) == X) for (int j = 0; j < VtSet.size() + 1; j++) { if (table[0][j].charAt(0) == a) return table[i][j]; } } return ""; } @Override public void insert(char X, char a, String s) {//插入 if(a == '&') a = '$'; for (int i = 0; i < VnSet.size() + 1; i++) { if (table[i][0].charAt(0) == X) for (int j = 0; j < VtSet.size() + 1; j++) { if (table[0][j].charAt(0) == a){ table[i][j] = s; return; } } } } @Override public void displayLL() {// 对输入串(a,a)$ 输出 LL(1)分析过程 Stack
s = MyAnaStatck; System.out.printf("%23s", s );//输出第一列：分析栈 System.out.printf("%13s", strInput.substring(Index));//输出第二列：输入串 System.out.printf("%10s", MyAction);//输出第三列：动作 System.out.println(); } @Override public void ouput() { // 输出终结符的first集 System.out.println("-------------------2.first集-------------------"); for (Character c : VnSet) { HashSet
set = MyfirstSet.get(c); System.out.printf("%10s",c + " -> "); for (Character cha : set) System.out.print(cha+" "); System.out.println(); } System.out.println("-------------------first集-------------------"); // 输出任意符号串的first集 System.out.println("-------------------firstX集-------------------"); Set
setStr = MyfirstSetX.keySet(); for (String s : setStr) { HashSet
set = MyfirstSetX.get(s); System.out.printf("%10s",s + " -> "); for (Character cha : set) System.out.print(cha+" "); System.out.println(); } System.out.println("-------------------firstX集-------------------"); // 输出follow集 System.out.println("-------------------3.follow集-------------------"); for (Character c : VnSet) { HashSet
set = MyfollowSet.get(c); System.out.print("Follow " + c + " : "); for (Character cha : set) System.out.print(cha+" "); System.out.println(); } System.out.println("-------------------follow集-------------------"); //构造LL1文法预测分析表 System.out.println("-------------------4.LL1预测分析表-------------------"); for (int i = 0; i < VnSet.size() + 1; i++) { for (int j = 0; j < VtSet.size() + 1; j++) { System.out.printf("%8s", table[i][j] + " "); } System.out.println(); } System.out.println("-------------------LL1预测分析表-------------------"); } }
四、结果分析
- 优点：文法分析过程比较详细，任务整个完成过程是充实的，这个实验报告相当于对编译原理理论课的一次实践尝试，能收获很多课堂上面学不到的知识，同时也能巩固老师所教授的知识。
- 缺点：在写程序的时候，卡在了空串那个点。最开始尝试直接在程序中定义文法时，ε能在程序中分析成功。后来在用读入文件的方式定义文法时，控制台出现乱码，这个点解决起来花了一点时间，最后决定将符号ε替换为&，程序才能运行成功。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/204856.html原文链接：https://javaforall.net
