编译原理实验二-语法分析器的设计

集美大学计算机工程学院实验报告

课程名称：编译原理班级：

指导教师：姓名：

实验项目编号：实验二学号：

实验项目名称：语法分析器的设计实验成绩：

一、实验目的

通过完成预测分析法的语法分析程序，了解预测分析法和递归子程序法的区别和联系。使了解语法分析的功能，掌握语法分析程序设计的原理和构造方法，训练掌握开发应用程序的基本方法。

二、实验内容

◆根据某一文法编制调试 LL （ 1 ）分析程序，以便对任意输入的符号串

进行分析。

◆构造预测分析表，并利用分析表和一个栈来实现对上述程序设计语言的分

析程序。

◆分析法的功能是利用LL（1）控制程序根据显示栈栈顶内容、向前看符号

以及LL（1）分析表，对输入符号串自上而下的分析过程。

三、实验要求

1、编程时注意编程风格：空行的使用、注释的使用、缩进的使用等。

2、如果遇到错误的表达式，应输出错误提示信息。

四、实验设计方案

1、设计思想

（1）、LL（1）文法的定义

LL(1)分析法属于确定的自顶向下分析方法。LL(1)的含义是：第一个L表明自顶向下分析是从左向右扫描输入串，第2个L表明分析过程中将使用最左推导，1表明只需向右看一个符号便可决定如何推导，即选择哪个产生式(规则)进行推导。

LL(1)文法的判别需要依次计算FIRST集、FOLLOW集和SELLECT集,然后判断是否为LL(1)文法,最后再进行句子分析。

需要预测分析器对所给句型进行识别。即在LL(1)分析法中，每当在符号栈的栈顶出现非终极符时，要预测用哪个产生式的右部去替换该非终极符；当出现终结符时，判断其与剩余输入串的第一个字符是否匹配，如果匹配，则继续分析，否则报错。LL(1)分析方法要求文法满足如下条件：对于任一非终极符A的两个不同产生式A→α,A→β，都要满足下面条件：SELECT(A→α)∩SELECT(A→β)=?

（2）、预测分析表构造

LL(1)分析表的作用是对当前非终极符和输入符号确定应该选择用哪个产生式进行推导。它的行对应文法的非终极符，列对应终极符，表中的值有两种：一是产生式的右部的字符串，一是null。若用M表示LL(1)分析表，则M可表示如下：

M: VN×VT→P∪{Error}

M(A, t) = A→α，当t∈select(A→α) ，否则

M(A, t) = Error

其中P表示所有产生式的集合。

（3）、语法分析程序构造

LL(1)分析中X为符号栈栈顶元素，a为输入流当前字符，E为给定测试数据的开始符号，#为句子括号即输入串的括号。分析表用一个二位数组M表示，数组元素M[A，a]中的下标A表示非终结符，a为终结符或句子括号‘#’，二维数组中存放的是一条关于A 的产生式，表明当非终结符A向下推导时，面临输入符a时，所采用的候选产生式，当元素内容无产生式时，则表明用A 的左部向下推导时出现了不该出现的符号，因此元素内容转向出错处理的信息。

LL(1)分析过程主要包括以下四个动作：

替换：当X∈VN时选相应产生式的右部β去替换X。此时X出栈，β逆序入栈。

匹配：当X∈VT时它与a进行匹配，其结果可能成功，也可能失败，如果成功则符号栈中将X退栈并将输入流指针向前移动一位，否则报错。

接受：当格局为（#，空#）时报告分析成功。

报错：出错后，停止分析。并给出相应的错误提示信息。

2.程序流程图：

‘#’’E ’进栈，当前终结符号送入a

显示分析步骤A ∈Vt?A=‘#’？产生式不存在？

若产生式为

A →A1A2…An,按逆序即[An …A2A1]入栈

产生式右部为空？出错

A=‘a ’？

读入下一符号

出错

N

Y Y

N

N Y

Y Y

N

输入要分析的字符串

判断字符串是否

正确

Y

N 显示栈中内容

显示剩余输入

串

显示产生式N Y

匹配字符串？

接受

N

Y

3、实验程序

（1）分析栈类：

public class stack {

private char s[];

private int top;

public stack() {

s = new char[200];

s[0] = '#';

top = 0;

}

char getTop() {

return s[top];

}

void push(String str) {

for (int i = str.length() - 1; i >= 0; i--) {

s[++top] = str.charAt(i);

}

}

void clear() {

top = 0;

}

char pop() {

if (top != 0) {

top--;

}

return s[top];

}

public String toString() {

String tmp = "";

for (int i = 0; i <= top; i++) {

tmp += s[i];

}

return tmp;

}

}

（2）语法分析器类：

public class anlysis {

//分析表

private String tab[][] = { { "$", "+", "-", "*", "/", "(", ")", "i", "#" },

{ "E", "$", "$", "$", "$", "TG", "$", "TG", "$" },

{ "G", "+TG", "-TG", "$", "$", "$", "ε", "$", "ε" },

{ "T", "$", "$", "$", "$", "FS", "$", "FS", "$" },

{ "S", "ε", "ε", "*FS", "/FS", "$", "ε", "$", "ε" },

{ "F", "$", "$", "$", "$", "(E)", "$", "i", "$" } };

private String input; //input中存放输入的表达式

private StringBuffer tempBuffer; //存放要输出的字符串

private int ptr, row, col, step; //指针，预测表中的行，列，当前步骤

private boolean symbol;

private stack stack;

public anlysis(){

stack =new stack();

tempBuffer = new StringBuffer();

symbol=true;

input="";

row=1;

ptr=0;

step=1;

}

//////////////////////////////////methods./////////////////////////// //////

public int column(char c) { //判断预测表中的列

switch (c) {

case'+':

return 1;

case'-':

return 2;

case'*':

return 3;

case'/':

return 4;

case'(':

return 5;

case')':

return 6;

case'i':

return 7;

case'#':

return 8;

default:

return -1;

}

}

public int line(char c) { //判定预测表中的行

switch (c) {

case'E':

return 1;

case'G':

return 2;

case'T':

return 3;

case'S':

return 4;

case'F':

return 5;

default:

return -1;

}

}

public void pri(String str) {

tempBuffer.append(String.format("%-8d%-20s%-20s%-20s\r\n", step, stack

.toString(), input.substring(ptr), str));

step++;

}

public void analyse() {

stack.push(tab[row][0]); //预测表中的第一个元素‘E’

pri("初始化");

String tmp;

char ctmp; //栈顶元素

while (!(input.charAt(ptr) == '#' && stack.getTop() == '#')) { ctmp = stack.getTop();

if (input.charAt(ptr) == ctmp) { //与栈顶元素比较

stack.pop();

ptr++;

pri("" + ctmp + "匹配");

continue;

}

col = column(input.charAt(ptr));

if (col == -1) {

symbol = false;

pri("未定义的字符");

ptr++;

continue;

}

row = line(ctmp);

if (row == -1) {

symbol = false;

pri("出错");

stack.pop();

if (input.charAt(ptr) != '#') {

ptr++;

}

continue;

}

tmp = tab[row][col];

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

symbol = false;

pri("出错");

stack.pop();

if (input.charAt(ptr) != '#') {

ptr++;

}

} else if (tmp.charAt(0) == 'ε') {

stack.pop();

pri("" + ctmp + "->" + 'ε');

} else {

stack.pop();

stack.push(tmp);

pri("" + ctmp + "->" + tmp);

}

}

}

public String work(String ts) {

input = ts;

input = input.trim()+ '#';

symbol = true;

stack.clear();

tempBuffer.append("\r\n步骤 分析栈剩余输入栈

所用产生式\r\n");

analyse();

if (symbol) {

tempBuffer.append("\r是正确的符号串\r");

return tempBuffer.toString();

} else {

tempBuffer.append("\r不是正确的符号串\r");

return tempBuffer.toString();

}

}

////////////////////////////////////gets and

sets////////////////////////////////

public StringBuffer getTempBuffer() {

return tempBuffer;

}

public void setTempBuffer(StringBuffer tempBuffer) { this.tempBuffer = tempBuffer;

}

public stack getStack() {

return stack;

}

public void setStack(stack stack) {

this.stack = stack;

}

public String[][] getTab() {

return tab;

}

public void setTab(String[][] tab) {

this.tab = tab;

}

public String getInput() {

return input;

}

public void setInput(String ns) {

this.input = ns;

}

public int getPtr() {

return ptr;

}

public void setPtr(int ptr) {

this.ptr = ptr;

}

public int getRow() {

return row;

}

public void setRow(int row) {

this.row = row;

}

public int getCol() {

return col;

}

public void setCol(int col) {

this.col = col;

}

public int getStep() {

return step;

}

public void setStep(int step) {

this.step = step;

}

public boolean isBoo() {

return symbol;

}

public void setBoo(boolean boo) {

this.symbol = boo;

}

}

（3）WINDOW窗体类：

import java.awt.BorderLayout;

import java.awt.GridLayout;

import java.awt.Panel;

import javax.swing.JFrame;

import javax.swing.JScrollPane;

public class gui extends javax.swing.JFrame {

/** Creates new form gui */

private javax.swing.JButton jButton1;

private javax.swing.JLabel jLabel1;

private javax.swing.JLabel jLabel2;

private javax.swing.JTextArea jTextArea1;

private javax.swing.JTextField jTextField1;

private Panel p1=new Panel();

private Panel p2=new Panel();

public gui() {

initComponents();

}

private void initComponents() {

jLabel1 = new javax.swing.JLabel();

jTextField1 = new javax.swing.JTextField();

jLabel2 = new javax.swing.JLabel();

jTextArea1 = new javax.swing.JTextArea(20,30);

jButton1 = new javax.swing.JButton();

setDefaultCloseOperation(javax.swing.WindowConstants.EXIT_ON_CLOS E);

jLabel1.setText("本程序只能对由'+','-','*','/','(',')','i'构成的以'#'结尾的字符串进行分析。请输入要翻译的表达式:");

jLabel2.setText("分析结果:");

jButton1.setText("分析");

jButton1.addActionListener(new java.awt.event.ActionListener() {

public void actionPerformed(java.awt.event.ActionEvent evt) {

jButton1ActionPerformed(evt);

}

});

final GridLayout gridLayout = new GridLayout(0, 1);//创建表格布局管理器

gridLayout.setVgap(0); //设置组件之间垂直距离

gridLayout.setHgap(0); //设置组件之间平行距离

p1.setLayout(gridLayout);

p1.add(jLabel1);

p1.add(jTextField1);

p2.add(jLabel2);

p2.add(new JScrollPane(jTextArea1));

getContentPane().add(p1, BorderLayout.NORTH);

getContentPane().add(p2, BorderLayout.CENTER);

getContentPane().add(jButton1, BorderLayout.SOUTH);

setSize(600,500);

setLocation(400, 100);

setVisible(true);

setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);

}

private void jButton1ActionPerformed(java.awt.event.ActionEvent evt) {

anlysis ans = new anlysis();

jTextArea1.setText(ans.work(jTextField1.getText()));

}

public static void main(String args[]) {

java.awt.EventQueue.invokeLater(new Runnable() {

public void run() {

new gui().setVisible(true);

}

});

}

}

五、实验结果

六、实验小结

1、本次实验主要运用java进行实验，通过完成预测分析法的语法分析程序，了解了预测分析法和递归子程序法的区别和联系，了解了语法分析的功能；

2、掌握了语法分析程序设计的原理和构造方法，掌握了开发应用程序的基本方法；

3、通过实验掌握了语法分析，能实现对普通字串的分析翻译。