实验三、 语法分析程序的设计
【实验目的与要求】
语法分析是编译过程的核心部分，常用的语法分析方法有：LL(1)分析法、递归子程序分析法、算符优先分析法、LR(0)分析法、SLR(1)分析法等。语法分析的主要任务是根据程序语言的语法规则，对词法分析产生的单词序列进行语法检查。
通过设计、编制、调试一个典型的语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，进一步掌握常用的语法分析方法。要求：选择具有代表性的语法分析方法，如：LL(K)分析法、递归子程序法、运算符优先数法、LR(K)分析法等方法之一进行设计；选择对各种常见程序语言都通用的语法结构，如赋值语句（尤指算术表达式）作为分析对象，并与所选语法分析方法要比较贴切。【实验设备和环境】
本实验使用C、C++或Java等语言编写程序。
【实验内容】
编写算术表达式的语法分析程序，进行调试，调试例子应包括符合语法规则的算术表达式，以及分析程序能够判别的若干错例。
首先先给出〈表达式〉的文法
〈表达式〉::=〈项〉│〈表达式〉+〈项〉│〈表达式〉-〈项〉
〈项〉::=〈因子〉│〈项〉*〈因子〉│〈项〉/〈因子〉
〈因子〉::= 〈初等量〉│〈因子〉↑〈初等量〉
〈初等量〉::= （〈表达式〉）│i
或表示为：G[E]
表达式 E→E+T | E-T | T
项 T→T*F | T/F | F
因子 F→F↑P | P
初等量 P→(E) | i
消除左递归：
E→T { ( + | - ) T }
T→F { ( * | / ) F }
F→P {↑P }
P→(E) | i
下面给出LL(1)分析法、递归子程序分析法、算符优先分析法、LR(0)分析法、SLR(1)分析法中用到的内容。
LL(1)语法分析方法LL(1)是一种自顶向下的语法分析方法，又称为预测分析法。
图3-1 LL(1)分析器的逻辑结构
构造LL(1)分析表的算法如下:
1)对于A::=Dβ(D∈VN)且select(A::=Dβ)={b1,b2…bn}
则M[A,bi]=RE(Dβ)/R
表示:用Dβ的逆替换A,重读当前字符.
2)对于A::=aβ(a∈VT)
则M[A,a]= RE(β)/C
表示:用β的逆替换A,继续读入下一字符.
3)对于A::=ε且select(A::=ε)={b1,b2…bn}
则M[A,bi]=RE(ε)/R=ε/R
4)对所有没出现在规则右部的首部的终结符a,
令M[a,a]=RE(ε)/C=ε/C
5)对于#,令M[#,#]=succ,表示分析成功,结束.
6)其他情况属于出错，在分析表中用空白表示.
【实验总结】 对实验结果进行分析，讨论如何解决语法分析过程中遇到的问题及解决办法，总结本次实验的收获及感想。
实验说明：学生应在实验课前仔细阅读实验相关内容，明确实验的目的和要求，然后了解词法分析和语法分析的基本方法，利用一种高级语言（如C语言、C++语言、PASCAL语言等），编写无符号数的词法分析程序、逆波兰式生成程序、语法分析程序（其中实验一必做，实验二和三选做一个）。调试程序后，打印程序代码及实验结果，写出实验报告。
这个我写的是LL1 分析法的，表达式。
我先给弄成消除左递归的，消除左递归算法，无敌。
然后这就可以搞出来一个LL1分析表
用这个表，完了就是打代码了。
先看代码效果
如对代码有疑问，下面有详细的解释
package com.cbt.compiler; import java.util.Scanner; import java.util.Stack; class AnalysisTable { public String[][] table = { // 0 1 2 3 4 5 6 7 8 // i * / + - ( ) @ # /* 0 */ { "eT", "", "", "", "", "eT", "", "", "" }, // E /* 1 */ { "", "", "", "eT", "eT", "", ".", "", "." }, // e /* 2 */ { "tF", "", "", "eT", "eT", "tF", "", "", "" }, // T /* 3 */ { "", "tF", "tF", ".", ".", "", ".", "", "." }, // t /* 4 */ { "fP", "", "", "", "", "fP", "", "", "" }, // F /* 5 */ { "", ".", ".", ".", ".", "", ".", "fP", "." }, // f /* 6 */ { ".", "", "", "eT", "eT", ")E", "", "", "" }, // P /* 7 */ { "", "", "", "", "", "", ".", "", "" }, // ) /* 8 */ { "", "", "", "", "", "", "", "", "succ" } }; public int[][] flag = new int[9][9]; AnalysisTable() { flag[1][3] = 1; flag[1][4] = 1; flag[3][1] = 1; flag[3][2] = 1; flag[5][7] = 1; flag[6][0] = 1; flag[6][5] = 1; flag[7][6] = 1; } } public class Comprehensive { public static void main(String[] args) { boolean hasPrinted = false; Stack<Character> stack = new Stack<Character>(); // String[] strArr = {"i*i+i*i+i/(i)","i*i", "i+*i", "i+i*i", "i*i*i", "i*i+(i+i)", "iii", "i+(", "i+(i*i)", "iiiii", "s","i/i/i" }; // for (String s : strArr) { Scanner sc = new Scanner(System.in); String s = sc.nextLine(); hasPrinted = false; s = s + "#"; String[] str = new String[20]; for (int i = 0, k = 0; i < s.length(); i++) { if (s.charAt(i) != ' ') { str[k++] = "" + s.charAt(i); } } stack.clear(); stack.add('#'); stack.add('E'); AnalysisTable table = new AnalysisTable(); // 挨个去读它 System.out.print("分析栈\t\t\t\t"+"余留输入串\t\t\t\t"+"动作\n"); for (int i = 0; i <= getLen(str); i++) { String temp = str[i]; int row = analyNoneCharacter(stack.peek()); int column = AnalysisTCharacter(temp); if (row == -1 || column == -1) { System.out.println(s + "No"); hasPrinted = true; break; } // 不是空，表示可以继续读取 String value = table.table[row][column]; //输出分析栈 for(Character s1:stack) { System.out.print(s1); } System.out.print("\t\t\t\t"); //输出余留输入串 for(int j = i;j<=getLen(str);j++) { System.out.print(str[j]); } System.out.print("\t\t\t\t"); if (value.equals("succ")) { hasPrinted = true; System.out.println(s + "Yes"); break; } // value 表示表里的是空的出错 if (!value.equals("")) { int flag = table.flag[row][column]; // 如果是C if (flag == 1) { System.out.print(value+"/C\n"); stack.pop(); // 如果不是空串替换 if (!value.equals(".")) { for (int j = 0; j < value.length(); j++) { stack.add(value.charAt(j)); } } if (getLen(str) == i) { i--; } } else { // 如果是R System.out.print(value+"/R\n"); stack.pop(); // 如果不是空串替换 if (!value.equals(".")) { for (int j = 0; j < value.length(); j++) { stack.add(value.charAt(j)); } } i--; } } else { if (!hasPrinted) { System.out.println(s + "No"); hasPrinted = true; break; } } } // for if (!hasPrinted) { System.out.println("No"); } // } // String s :strArr } public static int analyNoneCharacter(char ch) { char c = ch; int flag = -1; switch (c) { case 'E': flag = 0; break; case 'e': flag = 1; break; case 'T': flag = 2; break; case 't': flag = 3; break; case 'F': flag = 4; break; case 'f': flag = 5; break; case 'P': flag = 6; break; case ')': flag = 7; break; case '#': flag = 8; } return flag; } public static int AnalysisTCharacter(String s) { char ch = s.charAt(0); switch (ch) { case 'i': return 0; case '*': return 1; case '/': return 2; case '+': return 3; case '-': return 4; case '(': return 5; case ')': return 6; case '@': return 7; case '#': return 8; } return -1; } public static int getLen(String[] str) { if (str == null) return 0; for (int i = 0; i < str.length; i++) { if (str[i] == null) { return i - 1; } } return 0; } }思路是：
table用来存放LL1分析表。
用.表示空串
flag数组 表示C或者R
输入字符串s,先在s后面添加一个#号
用栈stack来存放分析栈,先在栈底放一个#,然后添加E.
从开始一直往后对这个s进行遍历,如果碰到r就重读当前的,直到#碰到#value = succ;
emmmmm,描述的好像不是很准确.
欢迎讨论交流,后来看这段代码有点冗余,但是懒得改了,其实不用这么麻烦.对字符串的操作不熟练导致.
QQ:1410497065
欢迎交流
