南昌大学编译原理实验--语法分析（含代码）

南昌大学实验报告

学生姓名： 学 号： 专业班级：

实验类型：□ 验证□综合 □ 设计 □ 创新 实验日期： 实验成绩：

√

]实验二 语法分析程序的设计（1）

一、实验目的

通过设计、编制、调试一个典型的语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，进一步掌握常用的语法分析中预测分析方法。

二、实验内容

设计一个文法的预测分析程序，判断特定表达式的正确性。

三、实验要求

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++ 程序集成环境

五、实验步骤

1、 分析文法，将给出的文法转化为LL(1)文法；

2、 学习预测分析程序的结构，设计合理的预测分析程序； 3、 编写测试程序，包括表达式的读入和结果的输出； 4、 测试程序运行效果，测试数据可以参考下列给出的数据。

六、测试数据

输入数据：

编辑一个文本文文件expression.txt，在文件中输入如下内容：

正确结果：

（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 输出：错误

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、 给定文法的LL（1）形式； 2、 预测分析程序的算法和结构； 3、 程序运行流程； 4、 程序的测试结果和问题； 5、 实验总结。

package compile2;

import java.util.Stack;

public class text2 {

/*

* 给定文法G[E]： E->T|E+T; T->F|T*F; F->i|(E); */

static String[] gram = { \, \, \, \, \,

\, \, \ };

static String[] followE = { \, \ }; static String[] followEA = { \, \ };

static String[] followT = { \, \, \ }; static String[] followTB = { \, \, \ };

static String[] followF = { \, \, \, \ }; static String[] firstE = { \, \ }; static String[] firstEA = { \, \ }; static String[] firstT = { \, \ }; static String[] firstTB = { \, \ }; static String[] firstF = { \, \ };

static String[][] list = { { \, \, \, \, \, \, \ }, { \, \, null, null, \, null, null }, { \, null, \, null, null, \, \ }, { \, \, null, null, \, null, null }, { \, null, \, \, null, \, \ },

{ \, \, null, null, \, null, null } };

public static void main(String[] args) throws Exception { String infile = \; String outfile = \;

Stack[] tmpword = new Stack[20]; Stack[] expression = new Stack[20]; for (int i = 0; i < tmpword.length; i++) { tmpword[i] = new Stack(); expression[i] = new Stack(); }

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(); }

public static void isLL1(Stack tmpword){ String[] input = tmpword.toArray(new String[0]); int inputCount = 0;

Stack status = new Stack(); status.push(input[inputCount++]); status.push(\); 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)); }

//inputCount++; } }

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 compile2; import java.io.*; import java.util.*;

public class main {

public static void scan(String infile,String outfile, Stack[] word, Stack[]

throws Exception {

expression)

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()) { }

public static void main(String[] args) throws Exception {

String infile = \String outfile = \Stack[] word = new Stack[5];

Stack[] expression = new Stack[word.length]; for (int i = 0; i < word.length; i++){ }

scan(infile, outfile, word, expression);

word[i] = new Stack(); expression[i] = new Stack();

static String[] key_word = { \

\

\\

static String[] cal_word = { \

String tmp = input.next(); int i = 0;

while (i < tmp.length()) {

if (tmp.charAt(i) <= '9' && tmp.charAt(i) >= '1') {//检查十进制数字 }

if (i + 2 < tmp.length())// 检查十六进制数字

if (tmp.charAt(i) == '0' && tmp.charAt(i + 1) == 'x') { }

if (tmp.charAt(i) == '0') {

i++;

String num = \

while (tmp.charAt(i) <= '7' && tmp.charAt(i) >= '0') { }

output.println(\word[count].push(\

num += tmp.charAt(i); i++;

if (i == tmp.length())

break;

i += 2; String num = \

while ((tmp.charAt(i) <= '9' && tmp.charAt(i) >= '0') || }

output.println(\word[count].push(\expression[count].push(num);

i++;

if (i == tmp.length())

break;

(tmp.charAt(i) <= 'f' && tmp.charAt(i) >= 'a')) { num += tmp.charAt(i);

String num = \

while (tmp.charAt(i) <= '9' && tmp.charAt(i) >= '0') { }

output.println(\word[count].push(\expression[count].push(num);

num += tmp.charAt(i); i++;

if (i == tmp.length())

break;

if (i + 1 < tmp.length())// 检查八进制数字

}

expression[count].push(num);

// 检查关键字和变量 if (i < tmp.length()) { }

// 检查运算符以及';' 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 + 1))) {

+ \

output.println(\word[count].push(cal_word[j]); expression[count].push(\

if (i < tmp.length() && tmp.charAt(i) >= 'a' }

&& tmp.charAt(i) <= 'z') { String tmp_word = \

while (tmp.charAt(i) >= 'a' && tmp.charAt(i) <= 'z') { }

boolean is_keyword = false;

for (int j = 0; j < key_word.length; j++) { }

if (!is_keyword) { }

output.println(\word[count].push(\

expression[count].push(tmp_word); if (tmp_word.equals(key_word[j])) { }

output.println(\word[count].push(key_word[j]); expression[count].push(key_word[j]); is_keyword = true; break;

tmp_word += tmp.charAt(i); i++;

if (i == tmp.length())

break;

}

}

}

}

}

}

}

}

}

if (word[count].peek() == \ } i += 2; break;

word[count].pop(); word[count].push(\count++;

word[count].push(\

for (int j = 0; j < cal_word.length; j++) { }

if (cal_word[j].equals(\ }

output.println(\word[count].push(cal_word[j]); expression[count].push(cal_word[j]); if (word[count].peek() == \ } i++; break;

word[count].pop(); word[count].push(\count++;

word[count].push(\

input.close(); output.close();

八、思考题

1、 如果使用递归下降分析法来进行语法分析，为什么文法必须先转化为LL（1）文法

再做递归下降分析？

本文来源：https://www.bwwdw.com/article/a2gh.html