实验目的
通过设计、编制、调试一个典型的语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，进一步掌握常用的语法分析中预测分析方法。
实验内容
设计一个文法的预测分析程序，判断特定表达式的正确性。
实验要求
1、给出文法如下：
G[E]：
E->T|E+T;
T->F|T*F;
F->i|(E);
2、根据该文法构造相应的LL(1)文法及LL(1)分析表，并为该文法设计预测分析程序，利用C语言或C++语言或Java语言实现；
3、利用预测分析程序完成下列功能：
1）手工将测试的表达式写入文本文件，每个表达式写一行，用“；”表示结束；
2）读入文本文件中的表达式；
3）调用实验一中的词法分析程序搜索单词；
4）把单词送入预测分析程序，判断表达式是否正确（是否是给出文法的语言），若错误，应给出错误信息；
5）完成上述功能，有余力的同学可以进一步完成通过程序实现对非LL(1)文法到LL（1）文法的自动转换（见实验二附加资料1）。
实验环境
PC微机
DOS操作系统或 Windows 操作系统
Turbo C 程序集成环境或 Visual C++ 程序集成环境或Eclipse集成环境
五、实验步骤
1、分析文法，将给出的文法转化为LL(1)文法；
2、学习预测分析程序的结构，设计合理的预测分析程序；
3、编写测试程序，包括表达式的读入和结果的输出；
4、测试程序运行效果，测试数据可以参考下列给出的数据。
测试数据
输入数据：
编辑一个文本文文件expression.txt，在文件中输入如下内容：
10;
1+2;
(1+2)*3+(5+6*7);
((1+2)*3+4;
1+2+3+(*4+5);
(a+b)*(c+d);
((ab3+de4)**5)+1;
正确结果：
（1）10;
输出：正确
（2）1+2;
输出：正确
（3）(1+2)*3+(5+6*7);
输出：正确
（4）((1+2)*3+4
输出：错误
（5）1+2+3+(*4+5)
输出：错误
（6）(a+b)*(c+d)
输出：正确
（7）((ab3+de4)**5)+1
输出：错误
代码
package com;
import java.util.*;
public class test2 {
static String[] gram = {"E->TA", "A->+TA", "A->@", "T->FB", "B->*FB", "B->@", "F->P", "F->(E)"};
static String[] followE = {")", "#"};
static String[] followEA = {")", "#"};
static String[] followT = {"+", ")", "#"};
static String[] followTB = {"+", ")", "#"};
static String[] followF = {"*", "+", ")", "#"};
static String[] firstE = {"i", "("};
static String[] firstEA = {"+", "@"};
static String[] firstT = {"i", "("};
static String[] firstTB = {"*", "@"};
static String[] firstF = {"i", "("};
static String[][] list = {{"", "i", "+", "*", "(", ")", "#"},
{"E", "TA", null, null, "TA", null, null},
{"A", null, "+TA", null, null, "@", "@"},
{"T", "FB", null, null, "FB", null, null},
{"B", null, "@", "*FB", null, "@", "@"},
{"F", "i", null, null, "(E)", null, null}};
public static void main(String[] args) throws Exception {
String infile = "E:/expression.txt";
String outfile = "E:/result2.txt";
Stack<String>[] tmpword = new Stack[20];
Stack<String>[] expression = new Stack[20];
//初始化栈
for (int i = 0; i < tmpword.length; i++) {
tmpword[i] = new Stack<String>();
expression[i] = new Stack<String>();
}
main.scan(infile, outfile, tmpword, expression);
int i = 0;
//循环输出结果
while (tmpword[i].size() > 2) {
String[] tmp = expression[i].toArray(new String[0]);
printArray(tmp);
isLL1(tmpword[i]);
i++;
}
}
//输出表达式
public static void printArray(String[] s) {
for (int i = 0; i < s.length; i++) {
System.out.print(s[i]);
}
System.out.println();
}
//判断是否为LL1文法，是则输出正确，否则输出错误
public static void isLL1(Stack<String> tmpword) {
String[] input = tmpword.toArray(new String[0]);
int inputCount = 0;
Stack<String> status = new Stack<String>();
status.push(input[inputCount++]);
status.push("E");
boolean flag = true;
boolean result = true;
while (flag) {
if (isVt(status.peek())) {
if (status.peek().equals(input[inputCount])) {
status.pop();
inputCount++;
} else {
flag = false;
result = false;
}
} else if (status.peek().equals("#")) {
if (status.peek().equals(input[inputCount])) flag = false;
else {
flag = false;
result = false;
}
} else if (list[indexInList(status.peek(), input[inputCount])[0]][indexInList(status.peek(), input[inputCount])[1]] != null) {
int[] a = indexInList(status.peek(), input[inputCount]);
if (list[a[0]][a[1]].endsWith("@"))
status.pop();
else {
status.pop();
for (int i = list[a[0]][a[1]].length() - 1; i >= 0; i--) {
status.push("" + list[a[0]][a[1]].charAt(i));
}
}
} else {
flag = false;
result = false;
}
}
if (result)
System.out.println("正确");
else
System.out.println("错误");
}
public static boolean isVt(String s) {
for (int i = 1; i < list[0].length - 1; i++) {
if (s.equals(list[0][i])) {
return true;
}
}
return false;
}
public static int[] indexInList(String m, String a) {
int i = 0, j = 0;
for (int c = 1; c < list.length; c++) {
if (m.equals(list[c][0])) i = c;
}
for (int c = 1; c < list[0].length; c++) {
if (a.equals(list[0][c])) {
j = c;
}
}
return new int[]{i, j};
}
}package com;
import java.io.PrintWriter;
import java.util.Scanner;
import java.util.Stack;
public class main {
static String[] key_word = {"main", "if", "then", "while", "do", "int", "else"};
static String[] cal_word = {"+", "-", "*", "/", "<", ">", "{", "}", "(", ")", "[", "]", "==", "!=", "!", "=", ">=", "<=", "+=", "-=", "*=", "/=", ";"};
public static void main(String[] args) throws Exception {
String infile = "E:/program.txt";
String outfile = "E:/result.txt";
Stack[] word = new Stack[5];
Stack[] expression = new Stack[word.length];
for (int i = 0; i < word.length; i++) {
word[i] = new Stack<String>();
expression[i] = new Stack<String>();
}
scan(infile, outfile, word, expression);
}
//对源程序进行扫描
public static void scan(String infile, String outfile, Stack<String>[] word, Stack<String>[] expression) throws Exception {
java.io.File file = new java.io.File(infile);
Scanner input = new Scanner(file);
java.io.PrintWriter output = new PrintWriter(outfile);
int count = 0;
word[count].push("#");
while (input.hasNext()) {
String tmp = input.next();
int i = 0;
while (i < tmp.length()) {
if (tmp.charAt(i) <= '9' && tmp.charAt(i) >= '1') {//检查十进制数字
String num = "";
while (tmp.charAt(i) <= '9' && tmp.charAt(i) >= '0') {
num += tmp.charAt(i);
i++;
if (i == tmp.length()) break;
}
output.println("< " + 1 + ", " + num + ">");
word[count].push("i");
expression[count].push(num);
}
if (i + 2 < tmp.length())// 检查十六进制数字
if (tmp.charAt(i) == '0' && tmp.charAt(i + 1) == 'x') {
i += 2;
String num = "";
while ((tmp.charAt(i) <= '9' && tmp.charAt(i) >= '0') || (tmp.charAt(i) <= 'f' && tmp.charAt(i) >= 'a')) {
num += tmp.charAt(i);
i++;
if (i == tmp.length()) break;
}
output.println("< " + 3 + ", " + num + ">");
word[count].push("i");
expression[count].push(num);
}
if (i + 1 < tmp.length())// 检查八进制数字
if (tmp.charAt(i) == '0') {
i++;
String num = "";
while (tmp.charAt(i) <= '7' && tmp.charAt(i) >= '0') {
num += tmp.charAt(i);
i++;
if (i == tmp.length()) break;
}
output.println("< " + 2 + ", " + num + ">");
word[count].push("i");
expression[count].push(num);
}
// 检查关键字和变量
if (i < tmp.length()) {
if (i < tmp.length() && tmp.charAt(i) >= 'a' && tmp.charAt(i) <= 'z') {
String tmp_word = "";
while (tmp.charAt(i) >= 'a' && tmp.charAt(i) <= 'z') {
tmp_word += tmp.charAt(i);
i++;
if (i == tmp.length()) break;
}
boolean is_keyword = false;
for (int j = 0; j < key_word.length; j++) {
if (tmp_word.equals(key_word[j])) {
output.println("< " + key_word[j] + ", " + "->");
word[count].push(key_word[j]);
expression[count].push(key_word[j]);
is_keyword = true;
break;
}
}
if (!is_keyword) {
output.println("< " + 0 + ", " + tmp_word + ">");
word[count].push("i");
expression[count].push(tmp_word);
}
}
}
// 检查运算符以及';'
if (i < tmp.length()) {
if (i + 1 < tmp.length()) {
if (tmp.charAt(i + 1) == '=') {
for (int j = 0; j < cal_word.length; j++) {
if (cal_word[j].equals("" + tmp.charAt(i) + tmp.charAt(i + 1))) {
output.println("< " + cal_word[j] + " ," + "->");
word[count].push(cal_word[j]);
expression[count].push("-");
if (word[count].peek() == ";") {
word[count].pop();
word[count].push("#");
count++;
word[count].push("#");
}
i += 2;
break;
}
}
}
}
for (int j = 0; j < cal_word.length; j++) {
if (cal_word[j].equals("" + tmp.charAt(i))) {
output.println("< " + cal_word[j] + ", " + "->");
word[count].push(cal_word[j]);
expression[count].push(cal_word[j]);
if (word[count].peek() == ";") {
word[count].pop();
word[count].push("#");
count++;
word[count].push("#");
}
i++;
break;
}
}
}
}
}
input.close();
output.close();
}
}
