编译原理-词法分析 - 图文

编译原理实验报告

词法分析器与语法分析器

I. 问题描述

设计、编制并调试一个词法分析子程序，完成识别语言单词的任务；

设计、编制、调试一个语法分析程序，并用它对词法分析程序所提供的单词序列进行语法检查和结构分析。

ii. 设计简要描述

界面需求：

为了更加形象的模拟过程，此实验使用图形界面。要求从图形界面上输入输入串，点击词法分析，可以将词法分析后识别的单词符号显示，点击语法分析，可以将语法分析的堆栈过程显示，并且显示结果（是否是符合文法的句子），清空则可以将所有置空。

功能分析：

1、由用户输入输入串； 2、用户点击“词法分析”，可以将词法分析后识别的单词符号显示。 3、用户点击语法分析，可以将语法分析的堆栈过程显示，并且显示结果（是

否是符合文法的句子）

4、用户点击清空，则将界面所有组件置为空

思路描述：

一、设计构想：

本实验决定编写一个简易C语言的词法分析器和语法分析器。使其能够识别while，if等关键字，可以判断赋值语句、条件语句、循环语句。

二、文法分析

1、需要识别的关键字及其识别码有：

关键字 识别码 关键字 识别码 关键字 识别码 main 0 - 11 ； 22 int 1 * 12 > 23 char 2 / 13 < 24 if 3 ( 14 >= 25 else 4 ) 15 <= 26 for 5 [ 16 == 27 while 6 ] 17 != 28 ID 7 { 18 ERROR -1 NUM 8 } 19 = 9 , 20 + 10 : 21

2、文法

〈程序〉→ main()〈语句块〉 〈语句块〉→{〈语句串〉}

〈语句串〉→〈语句〉；〈语句串〉|〈语句〉；

〈语句〉→〈赋值语句〉|〈条件语句〉|〈循环语句〉 〈赋值语句〉→ ID =〈表达式〉;

〈条件语句〉→ if〈条件〉〈语句块〉 〈循环语句〉→ while〈条件〉〈语句块〉

〈条件〉→（〈表达式〉〈关系符〉〈表达式〉）

〈表达式〉→〈表达式〉〈运算符〉〈表达式〉|（〈表达式〉）|ID|NUM 〈运算符〉→+|-|*|/

〈关系符〉→＜|＜＝|＞|＞＝|＝|！＞

转化为符号表示：

S→ main() K|空

K→ { C } C→Y；C |空 Y→F | T | X F→ ID = B T→ if J K X→ while J K

J→（ B G B ）

B→ B Z B |（ B ）| ID | NUM Z→ + | - | * | /

G→＜ | ＜＝ | ＞ | ＞＝ | ＝＝ | ！＞

表示含义：

S：程序 K：语句块 C：语句串 Y：语句 F ：赋值语句 T：条件语句 X：循环语句 J：条件 B：表达式 I：项 Z ：运算符 G：关系符

3、LL（1）分析表

（1），求出first集及follow集： FIRST(S)={mian}

FIRST(K)={{}

FIRST(C)= FIRST(Y)= {ID,if,while，空}；

FIRST(Y)= FIRST(F)+ FIRST(T)+ FIRST(X)={ID,if,while}; FIRST(F)={ID}; FIRST(T)={if}; FIRST(X)={while};

FIRST(J)= FIRST(B)={}; FIRST(B)={(,ID,NUM }； FIRST(Z)={+，-，*，/}

FIRST(G)={ ＜， ＜= ，＞，＞=，＝＝，！= };

FOLLOW（S）={#}； FOLLOW（K）={；}； FOLLOW（C）={}}； FOLLOW（Y）={；} FOLLOW（F）={；}; FOLLOW（T）={；}; FOLLOW（X）={；}; FOLLOW（J）={{，；}； FOLLOW（B）={+，-，*，/，），＜， ＜= ，＞，＞=，＝＝，！=,;}； FOLLOW（B’）={+，-，*，/，），＜， ＜= ，＞，＞=，＝＝，！=,;}； FOLLOW（Z）={(,ID,NUM }; FOLLOW（G）={(,ID,NUM };

（2）消除左递归，拆分文法关系并编号

0、S→ 空

1、S→ main() K 2、K→ { C } 3、 C→Y；C 4、 C→空 5、Y→ F 6、Y→ T 7、Y→ X

8、F→ ID = B 9、 T→ if J K 10、X→ while J K 11、 J→（ B G B ） 12、 B→ （ B ）B' 13、B→ ID B' 14、B→ NUM B' 15、B'→ BZB B' 16、B'→ 空 17、 Z→ + 18、 Z→ - 19、 Z→ * 20、 Z→ / 21、 G→ < 22、 G→ <= 23、 G→ > 24、 G→ >= 25、 G→ == 26、 G→ !=

（3）构造LL（1）分析表

（注：在表中用上一步的编号表示所需要的产生式）

main 空 ( 4 ) { } ; = if while ID num + 3 6 9 3 7 10 3 5 8 13 15 14 15 - * / < <= > 16 23 >= 16 24 == != # 16 25 0 S 1 K C Y F T X J 2 4 11 12 B B' 16 15 16 16 16 16 16 16 16 16 17 18 19 20 16 Z G 21 22 26 iii. 详细设计描述 项目构架：

各函数功能介绍：

1、word.wordList包（存储了关键字）：

word:此类是定义了存储关键字的结构：包括String型的关键字,和int型的

识别符。

wordList：此类存储了29个关键字，在构造函数中初始化。 2、word包（进行词法分析）中：

basicFunction:此类定义了做词法分析的基本函数：

GetChar()将下一输入字符读到ch中，搜索知识器前移一个字符位置

GetBC()；检查ch中的字符是否为空白。若是，则调用GetChar直至不

是字符为止

Concat()；将ch中的字符连接到strToken之后 IsLetter()；判断ch中的字符是否为字母 IsDigit()；判断ch中的字符是否为数字

Reserve()；对strToken中的字符创查找保留字表，若是则返回它的编

码，否则返回0

Retract()；将搜索指示器回调一个字符位置 RetractStr()；将strToken置空

lexAnalysis：此类是用来进行词法分析，将分析后的单词存入word数组中，

（注：在词法分析中，若是一串字母，则认为是ID，若是数字，则认为是NUM。存储的时候识别符分别存ID与NUM的识别符，但是内容仍然是自己的内容）

其中的wordAnalysis函数就是词法分析函数（具体实现请看后面的重

要函数分析）

3、stack包（定义栈）中：

栈是通过链表来定义的，因此

StringListElement：次类定义了链表的每一个节点

StringStrack：此类定义了栈，其中有长度属性，有函数： Top();用来取得栈顶 Push（）；压栈 Pop（）；出栈 4、sentence包（语法分析）中：

juzi ：定义了文法的句子的结构：key（左边部分） content[](右边推出

的部分) lo（长度）

grammar ：存储了文法的27个关系式 AnalysisFB ：定义了分析表的存储结构 AnalysisF ：存储分析表

SentenceAnalysis ：语法分析

JuProduction(word w)：此函数是用来判断在当前栈与输入串的

情况下，用哪一个产生式,返回产生式在数组中的下标

若输入串的第一个字符与栈顶字符相同则表示可以规约，则

返回-1； 若不能过用产生式，则返回-2；

AnalysisBasic(word w)：此函数是分布进行语法分析，对栈操作 * 根据所需要的产生式对符号栈进行操作 * 返回0表示规约；返回1表示移进；否则表示输入串不是文

法的句子

5.Main包（主界面）中

Main：此类定义了图形界面

重要函数分析： 一、词法分析函数：

当搜索指示器小于输入串长度是，就循环执行如下操作：

得到当前char，如果是字母，判断下一个，如是数字或字母，继续直至不是

字母或者是数字，将此时的单词与关键字比较，获得识别符，存入word数组中

如果是数字，循环看下一个是否为数字，继续直至不是数字

为止，将单词存入数组中

如果是+、-、*、/、（、）、[、]、{、}、，、：、；与关键字比较，

直接存入数组中

如果是>、<、=、!时，要判断下一个，是否构成了>=、<=、

==、!=。然后在存入数组中

如果下一个字符是空，换行，则跳过去下一个字符。

在做词法分析的时候，注意每一次判断结束之后要将strToken清空，而且要

注意回退，即当输入串下一个不满足要求的时候，要回退一格。 二、语法分析函数

利用词法分析已经分析出来的单词数组，循环进行每一步的语法分析，每当归并一个单词之后，index指示器加一，直至index等于单词数组长度，循环结束。 在每一次循环中，根据当前指示器指示的单词及堆栈的栈顶判断： 若相同，则表示要归并，将index++；栈顶弹出

若不相同，在分析表中查找所需要的产生式，并将栈顶弹出，将产生式逆向堆栈。

在查询的过程中，如果不能够移进也不能够归并，表示输入串不符合文法，在提示栏中提示。如果循环结束，直至栈中是由#，输入串中只剩#，表示分析完毕，输入串是符合文法的句子。

iv. 结果分析（原始图示）

图形界面：

输入句子：main() {} //空的main函数，运行结果

1、点击词法分析之后，在右侧的词法分析结果中显示分析后的单词：

2、点击语法分析之后，在中间的表中显示堆栈过程：

3、语法分析结束，该语句是符合文法的句子，因此在提示栏中显示“该句子是符合文法的语句！

输入复杂一点的句子：

main(){

If(zhj= =zhj){ Zhj=good; }; }

则结果是：

则他输出的单词是：（1,main）( 14, ( ) (15 , ) ) ( 18 , { ) ( 4 , if ) ( 14 , ( ) ( 7 , zhj ) ( 27 , = = ) ( 7, zhj ) ( 15 , ) ) ( 18 , { ) ( 7 , zhj ) ( 9 , = ) ( 7 , good)

( 22 , ；) ( 19 , ｝) ( 22 , ；) ( 19 , ｝)

语法分析经过了从0到37 的38步，分析结束：（在下图中将语法分析的全过程拼合）

分析结束后的输出结果是：

下图为此次语法分析的堆栈全过程：

输出更加复杂的句子： Main() {

While ( lsq <= zhj ){ If ( zhj = = zhj ){ Zhj = good; }; }; }

则结果是：

右侧的单词符号序列为：

语法分析过程为：

输入串是符合文法的句子，因此，正常结束

输入一个不符合文法的句子：

Main(){ zhanghuijuan is a good student ; } // zhanghuijuan is a good student 语句即不是赋

值，条件，也不是循环，因此不符合文法

输出结果是：

词法分析仍然可以进行，但是语法分析中发现进行不下去了，因此输出错误提示： “此输入串不是一个语句，不符合文法！”

iiv. 调试报告：

程序在编写的过程中有很多小的地方并没有注意，在不断的调试的过程当中逐渐发现：

1、在文法中有A-->空 的情况，在文法产生式的存储过程中就用空格代替了空，但是当需要用这样的产生式移进的时候，如果跟其他的产生式一样处理，则会在堆栈中将空格压栈，因此使语法分析不能继续进行下去。因此，我们在压栈之前要先进行判断，若是这种情况，则只是弹出栈顶，而不对其进行压栈。 2、由于在此程序中应用了多个数组，因此很容易出现数组越界的情况，所以这里就要多加注意才行。

3、在堆栈过程输出的时候，要输出当前栈中的元素，以及剩余的输入串，一定要注意要将输入串的输出放在index的增加之后，否则就是输出上一次的执行时的输入串了

附：程序原代码

************************package word.wordList;********************************** //////////////////////////////////////file word.java///////////////////////////////////// public class word { String value; int ID; public int getID() { return ID; } public void setID(int id) { ID = id; } public String getValue() { return value; } public void setValue(String value) { this.value = value; } }

//////////////////////////////////////file word.java///////////////////////////////////// public class WordList { //此类定义了语言单词符号种别码 word[] w = new word[30]; public WordList(){ w[0] = new word();w[0].setID(1);w[0].setValue(\ w[1] = new word();w[1].setID(2);w[1].setValue(\ w[2] = new word();w[2].setID(3);w[2].setValue(\ .........................................................................//省略 w[27] = new word();w[27].setID(28);w[27].setValue(\ w[28] = new word();w[28].setID(29);w[28].setValue(\ } public int Reserve(String value){ for(int i = 0 ; i<28 ; i++){ if(value.equals(w[i].getValue())){ return w[i].getID(); } } return 0; //返回0表示不在保留字之中。 } }

************************package word;;********************************** //////////////////////////////////////file basicFunction .java///////////////////////////////////// import word.wordList.WordList;

//在此类中定义了一组全局变量和过程，将它们作为实现转换图的基本成分 public class basicFunction {

public String input=\ //输入的源程序

public char ch; //存放最新读进的源程序的字符 public String strToken=\存放构成单词符号的字符串

public int index=0; //存放此时搜索指示器指向的字符位置 public int index_buf; //buffer中搜索指示器指向的字符位置 basicFunction(String input){ this.input = input; }

public char getCh() { return ch; }

public void setCh(char ch) { this.ch = ch; }

public String getInput() { return input; }

public void setInput(String input) { this.input = input; }

public String getStrToken() { return strToken; }

public void setStrToken(String strToken) { this.strToken = strToken; }

//将下一输入字符读到ch中，搜索知识器前移一个字符位置 public int GetChar(){ this.ch = this.input.charAt(index); index++; return 0; }

//检查ch中的字符是否为空白。若是，则调用GetChar直至不是字符为止 public char GetBC(){ while(ch==' '||ch=='\\n'||ch=='\\r'){ GetChar(); } return ch;

}

//将ch中的字符连接到strToken之后 public String Concat(){ strToken=strToken.concat(String.valueOf(ch)); return strToken; }

//判断ch中的字符是否为字母 public boolean IsLetter(){ boolean flag=false; if(ch>='a' && ch<='z' || ch>='A' && ch<='Z' ){ flag=true; } return flag; }

//判断ch中的字符是否为数字 public boolean IsDigit(){ boolean flag=false; if(ch>='0' && ch<='9' ){ flag=true; } return flag; }

//对strToken中的字符创查找保留字表，若是则返回它的编码，否则返回0 //注：在编写保留字表的时候要从1开始编号，不能从0开始编号！ public int Reserve(){ WordList wl = new WordList(); int f = wl.Reserve(strToken); return f; //返回0表示不在保留字之中。 }

//将搜索指示器回调一个字符位置 public void Retract(){ ch=' '; int l = strToken.length(); if(l>1){ strToken = strToken.substring(0,l-1); } index--; }

//将strToken置空

public void RetractStr(){ strToken=\ } }

//////////////////////////////////file: lexAnalysis .java; //////////////////////////////////

import word.wordList.word;

public class lexAnalysis { String input; public word[] word = new word[1000]; public String getInput() { return input; } public void setInput(String input) { this.input = input; } public int wordAnalysis(){ int i = 0; basicFunction bf = new basicFunction(input); int lo = input.length(); while(bf.index

word[i].setID(m); } i++; bf.RetractStr(); }else if(bf.IsDigit()){ int f = 0; if(bf.index

bf.ch=='['||bf.ch==']'||bf.ch=='{'||bf.ch=='}'||bf.ch==','||bf.ch==':'||bf.ch==';'){ int m = bf.Reserve(); word[i].setValue(bf.strToken); word[i].setID(m); i++; bf.RetractStr(); }else if(bf.ch=='>'||bf.ch=='<'||bf.ch=='='||bf.ch=='!'){ int f = 0; if(bf.index

} int m = bf.Reserve(); if(m==0){ word[i].setValue(bf.strToken); }else{ word[i].setValue(bf.strToken); word[i].setID(m); } i++; bf.RetractStr(); }else if(bf.ch==' '||bf.ch=='\\n'||bf.ch=='\\r'){ bf.RetractStr(); } } return i; } }

*******************************package stack;********************************* //////////////////////////////////file: StringListElement .java; //////////////////////////////////

public class StringListElement { public String data; public StringListElement next = null; StringListElement(String value){ data = value; } StringListElement(String value,StringListElement next){ data = value; this.next = next; } }

//////////////////////////////////file: StringStack .java; ////////////////////////////////// public class StringStack {

public StringListElement top = new StringListElement(\ public int lo = 0; public String top(){ if(top!=null){ return top.data; }else{ return \ }

} public String pop(){ String result = top(); if(top!=null){ top = top.next; lo--; } return result; } public void push(String value){ if(top==null){ top = new StringListElement(value); lo++; }else{ StringListElement temp = new StringListElement(value); temp.next= top; top = temp; lo++; } } }

*******************************package sentence;******************************* //////////////////////////////////file: juzi .java; ////////////////////////////////// public class juzi { public String key; public int lo; public String[] content = {\ }

//////////////////////////////////file: grammar .java; ////////////////////////////////// public class grammar {

public juzi[] gram = new juzi[27]; public grammar(){ gram[0] = new juzi(); gram[0].key = \ gram[1] = new juzi(); gram[1].key = \ gram[1].content[1]=\ ...............................................省略 gram[26] = new juzi(); gram[26].key = \ }

public static void main(String[] args) { grammar g = new grammar(); System.out.println(g.gram[0].key); } }

//////////////////////////////////file: AnalysisFB .java; ////////////////////////////////// public class AnalysisFB { //此类定义了分析表中的每一个单元的数据结构 public String key; public String input; public int index; }

//////////////////////////////////file: AnalysisF .java; //////////////////////////////////

public class AnalysisF { public AnalysisFB[] A = new AnalysisFB[43]; public AnalysisF(){ A[0] = new AnalysisFB();A[0].key = \ A[0].input = \ A[0].index = 0; A[1] = new AnalysisFB();A[1].key = \ A[1].input = \ A[1].index = 1; A[2] = new AnalysisFB();A[2].key = \ A[2].input = \ A[2].index = 2; ...................................................//省略 A[42] = new AnalysisFB();A[42].key = \ A[42].input = \ A[42].index = 26; } }

//////////////////////////////////file: SentenceAnalysis .java; //////////////////////////////////

import stack.StringStack; import word.wordList.word; /*

*此类中是用于语法分析 */

public class SentenceAnalysis { public StringStack ss = new StringStack();//此堆栈是符号栈 public grammar gg = new grammar();

public AnalysisF af = new AnalysisF(); //初始化堆栈 public SentenceAnalysis(){ ss.push(\ ss.push(\ } /* *此函数是用来判断在当前栈与输入串的情况下，用哪一个产生式,返回产生式在数组中的下标 *若输入串的第一个字符与栈顶字符相同则表示可以规约，则返回-1； *若不能过用产生式，则返回-2； */ public int JuProduction(word w){ int f = -2; String top = ss.top(); System.out.println(\ String input=\ if(w.getID() == 7){ input = \ }else if(w.getID()==8){ input = \ }else{ input = w.getValue(); } if(top.equals(input)){ f = -1; } for(int i = 0 ; i < 43 ; i++){ if(top.equals(af.A[i].key) ){ if(input.equals(af.A[i].input) ){ f = af.A[i].index; } } } return f; } /* * 此函数是分布进行语法分析 * 根据所需要的产生式对符号栈进行操作 * 返回0表示规约；返回1表示移进；否则表示文法出错 */

public int AnalysisBasic(word w){ int f = 5; int pro = this.JuProduction(w); if(pro == -1){ ss.pop(); f=0; }else if(pro==0||pro==4 ||pro==16){ ss.pop(); f=1; }else if(pro>=0&&pro<=26){ int l = gg.gram[pro].lo; ss.pop(); for(int j =l-1 ; j>=0 ; j--){ ss.push(gg.gram[pro].content[j]); } f=1; } return f; } }

*********************************packet main********************************** 此图形界面代码不再黏贴了，只是将词法分析的函数及语法分析的函数黏贴 private JButton getJButton() { if (jButton == null) { jButton = new JButton(); jButton.setBounds(new java.awt.Rectangle(599,80,89,41)); jButton.setText(\词法分析\ jButton.addActionListener(new ActionListener(){ public void actionPerformed(ActionEvent arg0) { String input = getJTextArea().getText().toString().trim(); System.out.print(input); TableModel model = getJTable().getModel(); DefaultTableModel tablemodel = (DefaultTableModel)model; int counts = tablemodel.getRowCount(); for(int k = counts-1;k>=0;k--){ tablemodel.removeRow(k); } lexAnalysis lex = new lexAnalysis(); lex.setInput(input);

int i = lex.wordAnalysis(); for(int j = 0 ; j

private JButton getJButton1() { if (jButton1 == null) { jButton1 = new JButton(); jButton1.setBounds(new java.awt.Rectangle(599,143,89,41)); jButton1.setText(\语法分析\ jButton1.addActionListener(new ActionListener(){ public void actionPerformed(ActionEvent arg0) { String input = getJTextArea().getText().toString().trim(); // System.out.print(input); TableModel model = getJTable2().getModel(); DefaultTableModel tablemodel = (DefaultTableModel)model; int counts = tablemodel.getRowCount(); for(int k = counts-1;k>=0;k--){ tablemodel.removeRow(k); } SentenceAnalysis sa = new SentenceAnalysis(); lexAnalysis lex = new lexAnalysis(); lex.setInput(input); int i = lex.wordAnalysis(); // System.out.println(i); int index = 0; int b = 0; //用来求输入串 String inp0 =\ for (int j = index ; j

// Object[] obj={\ tablemodel.addRow(obj); while(index=0&&gra<=26){ gram = sa.gg.gram[gra].key; gram = gram+\ int lll = sa.gg.gram[gra].lo; for(int m = 0 ; m

System.out.println(f+\ //以下7行是用来求出当前栈中的元素 int l = sa.ss.lo; String stack = \ StringListElement t = sa.ss.top; for(int k = 0 ; k

} inp = inp+\ b++; Object[] obj1={String.valueOf(b),stack,inp,gram}; tablemodel.addRow(obj1); }else{ getJTextArea1().setText(\此输入串不是一个语句 ，不符合文法！\ break; } } if(index == i){ getJTextArea1().setText(\该输入串是符合文法的语句！\ } } }); } return jButton1; }