编译原理
实验报告
实验名称:词法分析及语法分析专业班级:
姓名:
学号:
完成日期:
实验一、sample语言的词法分析
一、实验目的
给出SAMPLE文法规范,要求编写SAMPLE语言的词法分析程序。
二、实验准备
了解sample语言单词的定义,选择任一种编程语言实现词法分析。
三、实验内容
给出SAMPLE语言文法,输出单词(关键字、专用符号以及其它标记)。
1、格式
输入:源程序文件。输出:关键字、专用符号以及其它标记。
2、实现原理
程序中先判断这个句语句中每个单元为关键字、常数、运算符、界符,对与不同的单词符号给出不同编码形式的编码,用以区分之。
3、实验方法
读懂Sample源代码,自己重点独立实现对常量的判别。
四、实验设计
1、设计SAMPLE语言的词法分析器
A、字符集定义
1. <字符集> → <字母>│<数字>│<单界符>
2. <字母> → A│B│…│Z│a│b│…│z
3. <数字> → 0│1│2│…│9
4. <单界符> → +│-│*│/│=│<│>│(│)│[│]│:│. │; │, │'
B、单词集定义
5.<单词集> → <保留字>│<双界符>│<标识符>│<常数>│<单界符>
6.<保留字> → and│array│begin│bool│call│case│char│constant│dim│do│else │end│false│for│if│input│integer│not│of│or│output│procedure│program
│read│real│repeat│set│stop│then│to│true│until│var│while│write 7.<双界符> → <>│<=│>=│:= │/*│*/│..
8.<标识符> → <字母>│<标识符> <数字>│<标识符> <字母>
9.<常数> → <整数>│<布尔常数>│<字符常数>
10.<整数> → <数字>│<整数> <数字>
11.<布尔常数> → true│false
12.<字符常数> → ' 除 {'} 外的任意字符串 '
2、词法分析系统流程设计
四、源程序清单
1、源代码
/**
* 读取测试文件中的每一行然后传入Scaner中扫描
*/
import java.io.File;
import java.io.RandomAccessFile;
public class Analyzer {
private Scaner scaner;
private File testFile;
public static final String testFileAdd = "e:\\t7.txt"; //测试文件的绝对地址private RandomAccessFile fileReandomReader;
public void initAnalayzer() {
this.scaner = new Scaner();
try {
testFile = new File(testFileAdd);
this.fileReandomReader = new RandomAccessFile(testFile, "r");
} catch (Exception e) {
System.out.println("测试文件不存在");
}
}
public void startAnalyze() {
String tmpString = "";
String result;
int row = 0;
System.out.println("······················开始分析·····················");
try {
while ((tmpString = this.fileReandomReader.readLine()) != null) {
++row;
System.out.println("·····················analyze row " + row
+ "·················");
// System.err.println(tmpString + "!! " +row);
result = scaner.scan(tmpString);
System.out.println(result);
scaner.cleanScaner();
tmpS tring = "";
}
} catch (Exception e) {
e.printStackTrace();
}
}
public static void main(String[] args) {
Analyzer a = new Analyzer();
a.initAnalayzer();
a.startAnalyze();
}
}
/**
* 分析从analyze传过来的每一行源码
*/
import java.util.HashMap;
import java.util.Map;
public class Scaner {
private char ch;
private String token;
private String result;
private int index = 0;
private char[] strChar = new char[1000];
private int rowLength = 0;
// private KeywordConfig keywordConfig;
// private PunctuationConfig punctuationConfig;
//保留字键值对表
private Map
//单界符键值对表
private Map
//双界符键值对表
private Map
public Scaner() {
this.result = "";
// this.keywordConfig = new KeywordConfig();
// this.punctuationConfig = new PunctuationConfig();
//保留字键值对表创建
this.keywords = new HashMap
keywords.put("and", 1); keywords.put("array", 2);
keywords.put("begin", 3); keywords.put("bool", 4);
keywords.put("call", 5); keywords.put("case", 6);
keywords.put("char", 7); keywords.put("constant", 8);
keywords.put("dim", 9); keywords.put("do", 10);
keywords.put("else", 11); keywords.put("end", 12);
keywords.put("write", 13); keywords.put("for", 14);
keywords.put("if", 15); keywords.put("input", 16);
keywords.put("integer", 17); keywords.put("not", 18);
keywords.put("of", 19); keywords.put("or", 20);
keywords.put("output", 21); keywords.put("procedure", 22);
keywords.put("program", 23); keywords.put("read", 24);
keywords.put("real", 25); keywords.put("repeat", 26);
keywords.put("set", 27); keywords.put("stop", 28);
keywords.put("then", 29); keywords.put("to", 30);
keywords.put("while", 31); keywords.put("until", 32);
keywords.put("var", 33);
//单界符键值对表创建
this.punctuations = new HashMap
punctuations.put("+", "加号"); punctuations.put("-", "减号");
punctuations.put("*", "星号"); punctuations.put("/", "除号");
punctuations.put("(", "左圆括号"); punctuations.put(")", "右圆括号");
punctuations.put("{", "左花括号"); punctuations.put("}", "右花括号");
punctuations.put("[", "左方括号"); punctuations.put("]", "右方括号");
punctuations.put(",", "逗号"); punctuations.put(".", "点号");
punctuations.put(";", "分号"); punctuations.put("%", "百分号");
punctuations.put("\'", "单引号"); punctuations.put("\"", "双引号");
//双界符键值对初始化
this.doublePun = new HashMap
doublePun.put("<>", "双界符1"); doublePun.put(">=", "双界符2");
doublePun.put("<=", "双界符3"); doublePun.put("/*", "双界符4");
doublePun.put("*/", "双界符5"); doublePun.put(":=", "双界符6");
doublePun.put("..", "双界符7");
}
public String scan(String rowString) {
strChar = rowString.toCharArray();
rowLength = strChar.length;
while (this.index <= rowLength) {
this.token = "";
//获取字符
this.ch = this.getBC(strChar);
if (this.ch == ';') {
break;
} else if (https://www.sodocs.net/doc/5210827994.html,ng.Character.isLetter(ch)) {//判断首ch是否为字符
this.token = this.contact(token, ch);
//获取下一字符
ch = this.getNextChar(strChar);
//如果指定的字符是字符或者数字
while ((https://www.sodocs.net/doc/5210827994.html,ng.Character.isLetter(ch)) ||
(https://www.sodocs.net/doc/5210827994.html,ng.Character.isDigit(ch))) {
//拼凑当前读取的字符串
this.token = this.contact(token, ch);
ch = this.getNextChar(strChar);
}
this.index--;
// System.err.println("!!!"+this.token);
//判断hashmap键值对中有没有该字符串,有则匹配输出
if (this.findKeyword(token)) {
this.result += "[保留字] " + this.token.toString() + "\n";
}else if(token.equals("true")){
this.result += "[布尔常数] " + this.token.toString() + "\n";
}else if(token.equals("false")){
this.result += "[布尔常数] " + this.token.toString() + "\n";
}
else
this.result += "[标识符] " + this.token.toString() + "\n";
this.token = "";
} else if (https://www.sodocs.net/doc/5210827994.html,ng.Character.isDigit(ch)) {//如果首个字符是数字
this.token = this.contact(token, ch);
ch = this.getNextChar(strChar);
while (https://www.sodocs.net/doc/5210827994.html,ng.Character.isDigit(ch)) {
this.token = this.contact(token, ch);
ch = this.getNextChar(strChar);
}
this.index--;
this.result += "[数字] " + this.token.toString() + "\n";
this.token = "";
} else {//如果首字符不是字母也不是数字
char a = ch;
String key = String.valueOf(ch);
//如果是符号,则到键值对中匹配输出
if (this.findPunctuation(key)) {
this.result += "[单界符:" + this.getPunctuation(key)
+ "] " + key + "\n";
}
else if (key.equals(" ") || key.equals(" ")) {
break;
} else{
//获取下一字符
ch = this.getNextChar(strChar);
if(!https://www.sodocs.net/doc/5210827994.html,ng.Character.isDigit(ch)&&!https://www.sodocs.net/doc/5210827994.html,ng.Character.isLetter(ch)){
this.token = this.contact(token, a);
this.token = this.contact(token, ch);
//
System.out.println(a+"%%%%%%%%"+token+"$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$"+thi s.finddoublePun(token));
if(this.finddoublePun(token)){
this.result += "[" + this.getdoublePun(token)
+ "] " + token + "\n";
}
}
else{
this.index -= 1;
// System.out.println("未知字符:");
}
this.token = "";
}
}
}
return result;
}
public void cleanScaner() {
this.ch = ' ';
this.index = 0;
this.result = "";
this.rowLength = 0;
this.strChar = null;
}
public char getBC(char[] strChar) {
try {
while ((strChar[this.index]) == ' ') {
this.index++;
}
this.index++;
} catch (ArrayIndexOutOfBoundsException e) {
return';';
}
return strChar[this.index - 1];
}
public char getNextChar(char[] strChar) {
this.index++;
return strChar[this.index - 1];
}
public String contact(String token, char ch) {
// System.out.println(token + String.valueOf(ch)+"&&&&&&&&&&&&&&&&&");
return token + String.valueOf(ch);
}
public boolean findKeyword(String str){
if(this.keywords.containsKey(str)){
return true;
}
return false;
}
public boolean findPunctuation(String str){
if(this.punctuations.containsKey(str)){
return true;
}
else return false;
}
public boolean finddoublePun(String str){
if(this.doublePun.containsKey(str)){
return true;
}
else return false;
}
public String getdoublePun(String str){
return this.doublePun.get(str);
}
public String getPunctuation(String str){
return this.punctuations.get(str);
}
}
2、测试文件
program example;
var
a,b,c:integer;
x:char;
begin
if(a+c*3>b) and (b>3)
then c:=3;
x:=2+(3*a)-b*c*8;
if(2+3>a) and (b>3) and (a>c)
then c:=3;
for x:=1+2 to 3 do
b:=100;
while a>b do
c:=5;
for x:=1+d to 3 do
b:=15;
while t>b do
c:=5;
repeat a:=10; until a>b;
end.
3、测试结果
······················开始分析····················· ·····················analyze row 1·················
[保留字] program
[标识符] example
·····················analyze row 2·················
[保留字] var
·····················analyze row 3················· [标识符] a
[单界符:逗号] ,
[标识符] b
[单界符:逗号] ,
[标识符] c
[保留字] integer
·····················analyze row 4················· [标识符] x
[保留字] char
·····················analyze row 5················· [保留字] begin
·····················analyze row 6················· [保留字] if
[单界符:左圆括号] (
[标识符] a
[单界符:加号] +
[标识符] c
[单界符:星号] *
[数字] 3
[标识符] b
[单界符:右圆括号] )
[保留字] and
[单界符:左圆括号] (
[标识符] b
[数字] 3
[单界符:右圆括号] )
·····················analyze row 7················· [保留字] then
[标识符] c
[双界符6] :=
[数字] 3
·····················analyze row 8················· [标识符] x
[双界符6] :=
[数字] 2
[单界符:加号] +
[单界符:左圆括号] (
[数字] 3
[单界符:星号] *
[标识符] a
[单界符:右圆括号] )
[单界符:减号] -
[标识符] b
[单界符:星号] *
[标识符] c
[单界符:星号] *
[数字] 8
·····················analyze row 9················· [保留字] if
[单界符:左圆括号] (
[数字] 2
[单界符:加号] +
[数字] 3
[标识符] a
[单界符:右圆括号] )
[保留字] and
[单界符:左圆括号] (
[标识符] b
[数字] 3
[单界符:右圆括号] )
[保留字] and
[单界符:左圆括号] (
[标识符] a
[标识符] c
[单界符:右圆括号] )
·····················analyze row 10················· [保留字] then
[标识符] c
[双界符6] :=
[数字] 3
·····················analyze row 11················· [保留字] for
[标识符] x
[双界符6] :=
[数字] 1
[单界符:加号] +
[数字] 2
[保留字] to
[数字] 3
[保留字] do
·····················analyze row 12················· [标识符] b
[双界符6] :=
[数字] 100
·····················analyze row 13················· [保留字] while
[标识符] a
[标识符] b
[保留字] do
·····················analyze row 14················· [标识符] c
[双界符6] :=
[数字] 5
·····················analyze row 15················· [保留字] for
[标识符] x
[双界符6] :=
[数字] 1
[单界符:加号] +
[标识符] d
[保留字] to
[数字] 3
[保留字] do
·····················analyze row 16················· [标识符] b
[双界符6] :=
[数字] 15
·····················analyze row 17················· [保留字] while
[标识符] t
[标识符] b
[保留字] do
·····················analyze row 18················· [标识符] c
[双界符6] :=
[数字] 5
·····················analyze row 19·················
[保留字] repeat
[标识符] a
[双界符6] :=
[数字] 10
·····················analyze row 20·················
[保留字] end
[单界符:点号] .
实验二、sample语言的语法分析
一、实验目的
给出SAMPLE文法规范,要求编写SAMPLE语言的语法分析程序。
二、实验准备
了解sample语言语法的定义,选择任一种编程语言实现语法分析。
三、实验内容
已给SAMPLE语言文法,利用递归子程序法,编制语法分析程序,要求将错误信息输出到语法错误文件中,输出语法树。
1、实验方法
读懂Sample源代码,给出相关源代码的注释。
2、SAMPLE编译程序结构:
目标程序
3、文法分析
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)={<,<= ,>,>=,==,!= };
FOLLO W(S)={#};
FOLLO W(K)={;};
FOLLO W(C)={}};
FOLLO W(Y)={;}
FOLLO W(F)={;};
FOLLO W(T)={;};
FOLLO W(X)={;};
FOLLO W(J)={{,;};
FOLLO W(B)={+,-,*,/,),<,<= ,>,>=,==,!=,;};
FOLLO W(B’)={+,-,*,/,),<,<= ,>,>=,==,!=,;};
FOLLO W(Z)={(,ID,NUM };
FOLLO W(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)分析表
(注:在表中用上一步的编号表示所需要的产生式)
四、程序代码清单
1、源代码
//////////////////////////////////////file word.java/////////////////////////////////////
public class word {
String value;
int ID;
public int getID() {
return ID;
}
public void setID(int id) {
ID = id;
}
public String getV alue() {
return value;
}
public void setV alue(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].setV alue("main");
w[1] = new word();w[1].setID(2);w[1].setV alue("int");
w[2] = new word();w[2].setID(3);w[2].setV alue("char");
.........................................................................//省略
w[27] = new word();w[27].setID(28);w[27].setV alue("!=");
w[28] = new word();w[28].setID(29);w[28].setV alue("ERROR");
}
public int Reserve(String value){
for(int i = 0 ; i<28 ; i++){
if(value.equals(w[i].getV alue())){
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; //////////////////////////////////
编译原理实验报告实验名称:实验一编写词法分析程序 实验类型:验证型实验 指导教师:何中胜 专业班级:13软件四 姓名:丁越 学号: 电子邮箱: 实验地点:秋白楼B720 实验成绩: 日期:2016年3 月18 日
一、实验目的 通过设计、调试词法分析程序,实现从源程序中分出各种单词的方法;熟悉词法分析 程序所用的工具自动机,进一步理解自动机理论。掌握文法转换成自动机的技术及有穷自动机实现的方法。确定词法分析器的输出形式及标识符与关键字的区分方法。加深对课堂教学的理解;提高词法分析方法的实践能力。通过本实验,应达到以下目标: 1、掌握从源程序文件中读取有效字符的方法和产生源程序的内部表示文件的方法。 2、掌握词法分析的实现方法。 3、上机调试编出的词法分析程序。 二、实验过程 以编写PASCAL子集的词法分析程序为例 1.理论部分 (1)主程序设计考虑 主程序的说明部分为各种表格和变量安排空间。 数组 k为关键字表,每个数组元素存放一个关键字。采用定长的方式,较短的关键字 后面补空格。 P数组存放分界符。为了简单起见,分界符、算术运算符和关系运算符都放在 p表中 (编程时,还应建立算术运算符表和关系运算符表,并且各有类号),合并成一类。 id和ci数组分别存放标识符和常数。 instring数组为输入源程序的单词缓存。 outtoken记录为输出内部表示缓存。 还有一些为造表填表设置的变量。 主程序开始后,先以人工方式输入关键字,造 k表;再输入分界符等造p表。 主程序的工作部分设计成便于调试的循环结构。每个循环处理一个单词;接收键盘上 送来的一个单词;调用词法分析过程;输出每个单词的内部码。 ⑵词法分析过程考虑 将词法分析程序设计成独立一遍扫描源程序的结构。其流程图见图1-1。 图1-1 该过程取名为 lexical,它根据输入单词的第一个字符(有时还需读第二个字符),判断单词类,产生类号:以字符 k表示关键字;i表示标识符;c表示常数;p表示分界符;s表示运算符(编程时类号分别为 1,2,3,4,5)。 对于标识符和常数,需分别与标识符表和常数表中已登记的元素相比较,如表中已有 该元素,则记录其在表中的位置,如未出现过,将标识符按顺序填入数组id中,将常数 变为二进制形式存入数组中 ci中,并记录其在表中的位置。 lexical过程中嵌有两个小过程:一个名为getchar,其功能为从instring中按顺序取出一个字符,并将其指针pint加1;另一个名为error,当出现错误时,调用这个过程, 输出错误编号。 2.实践部分
编译原理课程设计Course Design of Compiling (课程代码3273526) 半期题目:词法和语法分析器 实验学期:大三第二学期 学生班级:2014级软件四班 学生学号:2014112218 学生姓名:何华均 任课教师:丁光耀 信息科学与技术学院 2017.6
课程设计1-C语言词法分析器 1.题目 C语言词法分析 2.内容 选一个能正常运行的c语言程序,以该程序出现的字符作为单词符号集,不用处理c语言的所有单词符号。 将解析到的单词符号对应的二元组输出到文件中保存 可以将扫描缓冲区与输入缓冲区合成一个缓冲区,一次性输入源程序后就可以进行预处理了 3.设计目的 掌握词法分析算法,设计、编制并调试一个词法分析程序,加深对词法分析原理的理解 4.设计环境(电脑语言环境) 语言环境:C语言 CPU:i7HQ6700 内存:8G 5.概要设计(单词符号表,状态转换图) 5.1词法分析器的结构 词法分析程序的功能:
输入:所给文法的源程序字符串。 输出:二元组(syn,token或sum)构成的序列。 词法分析程序可以单独为一个程序;也可以作为整个编译程序的一个子程序,当需要一个单词时,就调用此法分析子程序返回一个单词. 为便于程序实现,假设每个单词间都有界符或运算符或空格隔开,并引入下面的全局变量及子程序: 1) ch 存放最新读进的源程序字符 2) strToken 存放构成单词符号的字符串 3) Buffer 字符缓冲区 4)struct keyType 存放保留字的符号和种别 5.2待分析的简单词法 (1)保留字 break、case、char、const、int、do、while… (2)运算符和界符 = 、+、-、* 、/、%、,、;、(、)、?、# 5.3各种单词符号对应的种别码
编译原理语法分析实验报告 - 班级:XXX 学号:XXX 姓名:XXX 年月日 1、摘要: 用递归子程序法实现对pascal的子集程序设计语言的分析程序 2、实验目的: 通过完成语法分析程序,了解语法分析的过程和作用 3、任务概述 实验要求:对源程序的内码流进行分析,如为文法定义的句子输出”是”否则输出”否”,根据需要处理说明语句填写写相应的符号表供以后代码生成时使用 4、实验依据的原理 递归子程序法是一种自顶向下的语法分析方法,它要求文法是LL(1)文法。通过对文法中每个非终结符编写一个递归过程,每个过程的功能是识别由该非终结符推出的串,当某非终结符的产生式有多个候选式时,程序能够按LL(1)形式唯一地确定选择某个候选式进行推导,最终识别输入串是否与文法匹配。 递归子程序法的缺点是:对文法要求高,必须满足LL(1)文法,当然在某些语言中个别产生式的推导当不满足LL(1)而满足LL(2)时,也可以采用多向前扫描一个符号的办法;它的另一个缺点是由于递归调用多,所以速度慢占用空间多,尽管这样,它还是许多高级语言,例如PASCAL,C等编译系统常常采用的语法分析方法。
为适合递归子程序法,对实验一词法分析中的文法改写成无左递归和无左共因子的,,,如下: <程序>?<程序首部><分程序>。 <程序首部>?PROGRAM标识符; <分程序>?<常量说明部分><变量说明部分><过程说明部分> <复合语句> <常量说明部分>?CONST<常量定义><常量定义后缀>;|ε <常量定义>?标识符=无符号整数 <常量定义后缀>?,<常量定义><常量定义后缀> |ε <变量说明部分>?VAR<变量定义><变量定义后缀> |ε <变量定义>?标识符<标识符后缀>:<类型>; <标识符后缀>?,标识符<标识符后缀> |ε <变量定义后缀>?<变量定义><变量定义后缀> |ε <类型>?INTEGER | LONG <过程说明部分>?<过程首部><分程序>;<过程说明部分后缀>|ε <过程首部>?PROCEDURE标识符<参数部分>; <参数部分>?(标识符: <类型>)|ε <过程说明部分后缀>?<过程首部><分程序>;<过程说明部分后缀>|ε <语句>?<赋值或调用语句>|<条件语句>|<当型循环语句>|<读语句> |<写语句>|<复合语句>|ε <赋值或调用语句>?标识符<后缀> <后缀>?:=<表达式>|(<表达式>)|ε <条件语句>?IF<条件>THEN<语句> <当型循环语句>?WHILE<条件>DO <语句> <读语句>?READ(标识符<标识符后缀>)
实验1-3 《编译原理》S语言词法分析程序设计方案 一、实验目的 了解词法分析程序的两种设计方法之一:根据状态转换图直接编程的方式; 二、实验内容 1.根据状态转换图直接编程 编写一个词法分析程序,它从左到右逐个字符的对源程序进行扫描,产生一个个的单词的二元式,形成二元式(记号)流文件输出。在此,词法分析程序作为单独的一遍,如下图所示。 具体任务有: (1)组织源程序的输入 (2)拼出单词并查找其类别编号,形成二元式输出,得到单词流文件 (3)删除注释、空格和无用符号 (4)发现并定位词法错误,需要输出错误的位置在源程序中的第几行。将错误信息输出到屏幕上。 (5)对于普通标识符和常量,分别建立标识符表和常量表(使用线性表存储),当遇到一个标识符或常量时,查找标识符表或常量表,若存在,则返回位置,否则返回0并且填写符号表或常量表。 标识符表结构:变量名,类型(整型、实型、字符型),分配的数据区地址 注:词法分析阶段只填写变量名,其它部分在语法分析、语义分析、代码生成等阶段逐步填入。 常量表结构:常量名,常量值 三、实验要求 1.能对任何S语言源程序进行分析 在运行词法分析程序时,应该用问答形式输入要被分析的S源语言程序的文件名,然后对该程序完成词法分析任务。 2.能检查并处理某些词法分析错误 词法分析程序能给出的错误信息包括:总的出错个数,每个错误所在的行号,错误的编号及错误信息。 本实验要求处理以下两种错误(编号分别为1,2): 1:非法字符:单词表中不存在的字符处理为非法字符,处理方式是删除该字符,给出错误信息,“某某字符非法”。 2:源程序文件结束而注释未结束。注释格式为:/* …… */ 四、保留字和特殊符号表
编译技术 班级网络0802 学号3080610052姓名叶晨舟 指导老师朱玉全2011年 7 月 4 日
一、目的 编译技术是理论与实践并重的课程,而其实验课要综合运用一、二年级所学的多门课程的内容,用来完成一个小型编译程序。从而巩固和加强对词法分析、语法分析、语义分析、代码生成和报错处理等理论的认识和理解;培养学生对完整系统的独立分析和设计的能力,进一步培养学生的独立编程能力。 二、任务及要求 基本要求: 1.词法分析器产生下述小语言的单词序列 这个小语言的所有的单词符号,以及它们的种别编码和内部值如下表: 单词符号种别编码助记符内码值 DIM IF DO STOP END 标识符 常数(整)= + * ** , ( )1 2 3 4 5 6 7 8 9 10 11 12 13 14 $DIM $IF $DO $STOP $END $ID $INT $ASSIGN $PLUS $STAR $POWER $COMMA $LPAR $RPAR - - - - - - 内部字符串 标准二进形式 - - - - - - 对于这个小语言,有几点重要的限制: 首先,所有的关键字(如IF﹑WHILE等)都是“保留字”。所谓的保留字的意思是,用户不得使用它们作为自己定义的标示符。例如,下面的写法是绝对禁止的: IF(5)=x 其次,由于把关键字作为保留字,故可以把关键字作为一类特殊标示符来处理。也就是说,对于关键字不专设对应的转换图。但把它们(及其种别编码)预先安排在一张表格中(此表叫作保留字表)。当转换图识别出一个标识符时,就去查对这张表,确定它是否为一个关键字。 再次,如果关键字、标识符和常数之间没有确定的运算符或界符作间隔,则必须至少用一个空白符作间隔(此时,空白符不再是完全没有意义的了)。例如,一个条件语句应写为
学号107 成绩 编译原理上机报告 名称:编写递归下降语法分析器 学院:信息与控制工程学院 专业:计算机科学与技术 班级:计算机1401班 姓名:叶达成 2016年10月31日
一、上机目的 通过设计、编制、调试一个递归下降语法分析程序,实现对词法分析程序所提供的单词序列进行语法检查和结构分析,掌握常用的语法分析方法。通过本实验,应达到以下目标: 1、掌握从源程序文件中读取有效字符的方法和产生源程序的内部表示文件的方法。 2、掌握词法分析的实现方法。 3、上机调试编出的词法分析程序。 二、基本原理和上机步骤 递归下降分析程序实现思想简单易懂。程序结构和语法产生式有直接的对应关系。因为每个过程表示一个非终结符号的处理,添加语义加工工作比较方便。 递归下降分析程序的实现思想是:识别程序由一组子程序组成。每个子程序对应于一个非终结符号。 每一个子程序的功能是:选择正确的右部,扫描完相应的字。在右部中有非终结符号时,调用该非终结符号对应的子程序来完成。 自上向下分析过程中,如果带回溯,则分析过程是穷举所有可能的推导,看是否能推导出待检查的符号串。分析速度慢。而无回溯的自上向下分析技术,当选择某非终结符的产生时,可根据输入串的当前符号以及各产生式右部首符号而进行,效率高,且不易出错。 无回溯的自上向下分析技术可用的先决条件是:无左递归和无回溯。 无左递归:既没有直接左递归,也没有间接左递归。 无回溯:对于任一非终结符号U的产生式右部x1|x2|…|x n,其对应的字的首终结符号两两不相交。 如果一个文法不含回路(形如P?+ P的推导),也不含以ε为右部的产生式,那么可以通过执行消除文法左递归的算法消除文法的一切左递归(改写后的文法可能含有以ε为右部的产生式)。 三、上机结果 测试数据: (1)输入一以#结束的符号串(包括+—*/()i#):在此位置输入符号串例如:i+i*i# (2)输出结果:i+i*i#为合法符号串 (3)输入一符号串如i+i*#,要求输出为“非法的符号串”。 程序清单: #include
编译技术实验报告 实验题目:词法分析 学院:信息学院 专业:计算机科学与技术学号: 姓名:
一、实验目的 (1)理解词法分析的功能; (2)理解词法分析的实现方法; 二、实验内容 PL0的文法如下 …< >?为非终结符。 …::=? 该符号的左部由右部定义,可读作“定义为”。 …|? 表示…或?,为左部可由多个右部定义。 …{ }? 表示花括号内的语法成分可以重复。在不加上下界时可重复0到任意次 数,有上下界时可重复次数的限制。 …[ ]? 表示方括号内的成分为任选项。 …( )? 表示圆括号内的成分优先。 上述符号为“元符号”,文法用上述符号作为文法符号时需要用引号…?括起。 〈程序〉∷=〈分程序〉. 〈分程序〉∷= [〈变量说明部分〉][〈过程说明部分〉]〈语句〉 〈变量说明部分〉∷=V AR〈标识符〉{,〈标识符〉}:INTEGER; 〈无符号整数〉∷=〈数字〉{〈数字〉} 〈标识符〉∷=〈字母〉{〈字母〉|〈数字〉} 〈过程说明部分〉∷=〈过程首部〉〈分程序〉{;〈过程说明部分〉}; 〈过程首部〉∷=PROCEDURE〈标识符〉; 〈语句〉∷=〈赋值语句〉|〈条件语句〉|〈过程调用语句〉|〈读语句〉|〈写语句〉|〈复合语句〉|〈空〉 〈赋值语句〉∷=〈标识符〉∶=〈表达式〉 〈复合语句〉∷=BEGIN〈语句〉{;〈语句〉}END 〈条件〉∷=〈表达式〉〈关系运算符〉〈表达式〉 〈表达式〉∷=〈项〉{〈加法运算符〉〈项〉} 〈项〉∷=〈因子〉{〈乘法运算符〉〈因子〉} 〈因子〉∷=〈标识符〉|〈无符号整数〉|'('〈表达式〉')' 〈加法运算符〉∷=+|- 〈乘法运算符〉∷=* 〈关系运算符〉∷=<>|=|<|<=|>|>= 〈条件语句〉∷=IF〈条件〉THEN〈语句〉 〈字母〉∷=a|b|…|X|Y|Z 〈数字〉∷=0|1|2|…|8|9 实现PL0的词法分析
实验二语法分析器 一、实验目的 通过完成预测分析法的语法分析程序,了解预测分析法和递归子程序法的区别和联系。使学生了解语法分析的功能,掌握语法分析程序设计的原理和构造方法,训练学生掌握开发应用程序的基本方法。有利于提高学生的专业素质,为培养适应社会多方面需要的能力。 二、实验内容 ◆根据某一文法编制调试LL (1 )分析程序,以便对任意输入的符号串 进行分析。 ◆构造预测分析表,并利用分析表和一个栈来实现对上述程序设计语言的分 析程序。 ◆分析法的功能是利用LL(1)控制程序根据显示栈栈顶内容、向前看符号 以及LL(1)分析表,对输入符号串自上而下的分析过程。 三、LL(1)分析法实验设计思想及算法 ◆模块结构: (1)定义部分:定义常量、变量、数据结构。 (2)初始化:设立LL(1)分析表、初始化变量空间(包括堆栈、结构体、数组、临时变量等); (3)控制部分:从键盘输入一个表达式符号串; (4)利用LL(1)分析算法进行表达式处理:根据LL(1)分析表对表达式符号串进行堆栈(或其他)操作,输出分析结果,如果遇到错误则显示错误信息。
四、实验要求 1、编程时注意编程风格:空行的使用、注释的使用、缩进的使用等。 2、如果遇到错误的表达式,应输出错误提示信息。 3、对下列文法,用LL(1)分析法对任意输入的符号串进行分析:(1)E->TG (2)G->+TG|—TG (3)G->ε (4)T->FS (5)S->*FS|/FS (6)S->ε (7)F->(E) (8)F->i 输出的格式如下:
五、实验源程序 LL1.java import java.awt.*; import java.awt.event.*; import javax.swing.*; import javax.swing.table.DefaultTableModel; import java.sql.*; import java.util.Vector; public class LL1 extends JFrame implements ActionListener { /** * */ private static final long serialVersionUID = 1L; JTextField tf1; JTextField tf2; JLabel l; JButton b0; JPanel p1,p2,p3; JTextArea t1,t2,t3; JButton b1,b2,b3;
词法分析 一、实验目的 设计、编制并调试一个词法分析程序,加深对词法分析原理的理解。 二、实验要求 2.1 待分析的简单的词法 (1)关键字: begin if then while do end 所有的关键字都是小写。 (2)运算符和界符 : = + - * / < <= <> > >= = ; ( ) # (3)其他单词是标识符(ID)和整型常数(SUM),通过以下正规式定义: ID = letter (letter | digit)* NUM = digit digit* (4)空格有空白、制表符和换行符组成。空格一般用来分隔ID、SUM、运算符、界符和关键字,词法分析阶段通常被忽略。 2.2 各种单词符号对应的种别码: 输入:所给文法的源程序字符串。 输出:二元组(syn,token或sum)构成的序列。 其中:syn为单词种别码; token为存放的单词自身字符串; sum为整型常数。 例如:对源程序begin x:=9: if x>9 then x:=2*x+1/3; end #的源文件,经过词法分析后输出如下序列: (1,begin)(10,x)(18,:=)(11,9)(26,;)(2,if)…… 三、词法分析程序的算法思想: 算法的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号,其基本思想是根据扫描到单词符号的第一个字符的种类,拼出相应的单词符号。
3.1 主程序示意图: 主程序示意图如图3-1所示。其中初始包括以下两个方面: ⑴关键字表的初值。 关键字作为特殊标识符处理,把它们预先安排在一张表格中(称为关键字表),当扫描程序识别出标识符时,查关键字表。如能查到匹配的单词,则该单词为关键字,否则为一般标识符。关键字表为一个字符串数组,其描述如下: Char *rwtab[6] = {“begin”, “if”, “then”, “while”, “do”, “end”,}; 图3-1 (2)程序中需要用到的主要变量为syn,token和sum 3.2 扫描子程序的算法思想: 首先设置3个变量:①token用来存放构成单词符号的字符串;②sum用来整型单词;③syn用来存放单词符号的种别码。扫描子程序主要部分流程如图3-2所示。
. 编译原理实验专业:13级网络工程
语法分析器1 一、实现方法描述 所给文法为G【E】; E->TE’ E’->+TE’|空 T->FT’ T’->*FT’|空 F->i|(E) 递归子程序法: 首先计算出五个非终结符的first集合follow集,然后根据五个产生式定义了五个函数。定义字符数组vocabulary来存储输入的句子,字符指针ch指向vocabulary。从非终结符E函数出发,如果首字符属于E的first集,则依次进入T函数和E’函数,开始递归调用。在每个函数中,都要判断指针所指字符是否属于该非终结符的first集,属于则根据产生式进入下一个函数进行调用,若first集中有空字符,还要判断是否属于该非终结符的follow集。以分号作为结束符。 二、实现代码 头文件shiyan3.h #include
#include int a=0; cout<<"按1结束程序"< 词法分析 三、词法分析程序的算法思想: 算法的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号,其基本思想是根据扫描到单词符号的第一个字符的种类,拼出相应的单词符号。 3.1 主程序示意图: 扫描子程序主要部分流程图 其他 词法分析程序的C语言程序源代码: // 词法分析函数: void scan() // 数据传递: 形参fp接收指向文本文件头的文件指针; // 全局变量buffer与line对应保存源文件字符及其行号,char_num保存字符总数。 void scan() { char ch; int flag,j=0,i=-1; while(!feof(fp1)) { ch=fgetc(fp1); flag=judge(ch); printf("%c",ch);//显示打开的文件 if(flag==1||flag==2||flag==3) {i++;buffer[i]=ch;line[i]=row;} else if(flag==4) {i++;buffer[i]='?';line[i]=row;} else if(flag==5) {i++;buffer[i]='~';row++;} else if(flag==7) continue; else cout<<"\n请注意,第"< 词法分析器实验报告 一、实验目的 选择一种编程语言实现简单的词法分析程序,设计、编制并调试一个词法分析程序,加深对词法分析原理的理解。 二、实验要求 待分析的简单的词法 (1)关键字: begin if then while do end 所有的关键字都是小写。 (2)运算符和界符 : = + - * / < <= <> > >= = ; ( ) # (3)其他单词是标识符(ID)和整型常数(SUM),通过以下正规式定义: ID = letter (letter | digit)* NUM = digit digit* (4)空格有空白、制表符和换行符组成。空格一般用来分隔ID、SUM、运算符、界符和关键字,词法分析阶段通常被忽略。 各种单词符号对应的种别码: 表各种单词符号对应的种别码 词法分析程序的功能: 输入:所给文法的源程序字符串。 输出:二元组(syn,token或sum)构成的序列。 其中:syn为单词种别码; token为存放的单词自身字符串; sum为整型常数。 例如:对源程序begin x:=9: if x>9 then x:=2*x+1/3; end #的源文件,经过词法分析后输出如下序列: (1,begin)(10,x)(18,:=)(11,9)(26,;)(2,if)…… 三、词法分析程序的算法思想: 算法的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号,其基本思想是根 据扫描到单词符号的第一个字符的种类,拼出相应的单词符号。 主程序示意图: 主程序示意图如图3-1所示。其中初始包括以下两个方面: ⑴关键字表的初值。 关键字作为特殊标识符处理,把它们预先安排在一张表格中(称为关键字表),当扫描程序识别出标识符时,查关键字表。如能查到匹配的单词,则该单词为关键字,否则为一般标识符。关键字表为一个字符串数组,其描述如下: Char *rwtab[6] = {“begin”, “if”, “then”, “while”, “do”, “end”,}; 图3-1 (2)程序中需要用到的主要变量为syn,token和sum 扫描子程序的算法思想: 首先设置3个变量:①token用来存放构成单词符号的字符串;②sum用来整型单词;③syn 用来存放单词符号的种别码。扫描子程序主要部分流程如图3-2所示。 编译原理实验报告 实验名称:编写语法分析分析器实验类型: 指导教师: 专业班级: 学号: 电子邮件: 实验地点: 实验成绩: 一、实验目的 通过设计、编制、调试一个典型的语法分析程序,实现对词法分析程序所提供的单词序列进行语法检查和结构分析,进一步掌握常用的语法分析方法。 1、选择最有代表性的语法分析方法,如LL(1) 语法分析程序、算符优先分析程序和LR分析分析程序,至少选一题。 2、选择对各种常见程序语言都用的语法结构,如赋值语句(尤指表达式)作为分析对象,并且与所选语法分析方法要比较贴切。 二、实验过程 编写算符优先分析器。要求: (a)根据算符优先分析算法,编写一个分析对象的语法分析程序。读者可根据自己的能力选择以下三项(由易到难)之一作为分析算法中的输入: Ⅰ:通过构造算符优先关系表,设计编制并调试一个算法优先分析程序Ⅱ:输入FIRSTVT,LASTVT集合,由程序自动生成该文法的算符优先关系矩阵。 Ⅲ:输入已知文法,由程序自动生成该文法的算符优先关系矩阵。(b)程序具有通用性,即所编制的语法分析程序能够使用于不同文法以及各种输入单词串,并能判断该文法是否为算符文法和算符优先文法。 (c)有运行实例。对于输入的一个文法和一个单词串,所编制的语法分析程序应能正确地判断,此单词串是否为该文法的句子,并要求输出分析过程。 三、实验结果 算符优先分析器: 测试数据:E->E+T|T T->T*F|F F->(E)|i 实验结果:(输入串为i+i*i+i) 四、讨论与分析 自下而上分析技术-算符优先分析法: 算符文法:一个上下无关文法G,如果没有且没有P→..QR...(P ,Q ,R属于非终结符),则G是一个算符文法。 FIRSTVT集构造 1、若有产生式P →a...或P →Qa...,则a∈FIRSTVT(P)。 2、若有产生式P→...,则FIRSTVT(R)包含在FIRSTVT(P)中。由优先性低于的定义和firstVT集合的定义可以得出:若存在某个产生式:…P…,则对所有:b∈firstVT(P)都有:a≦b。 构造优先关系表: 1、如果每个非终结符的FIRSTVT和LASTVT集均已知,则可构造优先关系表。 2、若产生式右部有...aP...的形式,则对于每个b∈FIRSTVT(P)都有 信息工程学院实验报告(2010 ~2011 学年度第一学期) 姓名:柳冠天 学号:2081908318 班级:083 词法分析 一、实验目的 设计、编制并调试一个词法分析程序,加深对词法分析原理的理解。 二、实验要求 2.1 待分析的简单的词法 (1)关键字: begin if then while do end 所有的关键字都是小写。 (2)运算符和界符 := + - * / < <= <> > >= = ; ( ) # (3)其他单词是标识符(ID)和整型常数(SUM),通过以下正规式定义: ID = letter (letter | digit)* NUM = digit digit* (4)空格有空白、制表符和换行符组成。空格一般用来分隔ID、SUM、运算符、界符和关键字,词法分析阶段通常被忽略。 2.2 各种单词符号对应的种别码: 表2.1 各种单词符号对应的种别码 2.3 词法分析程序的功能: 输入:所给文法的源程序字符串。 输出:二元组(syn,token或sum)构成的序列。 其中:syn为单词种别码; token为存放的单词自身字符串; sum为整型常数。 例如:对源程序begin x:=9: if x>9 then x:=2*x+1/3; end #的源文件,经过词法分析后输出如下序列: (1,begin)(10,x)(18,:=)(11,9)(26,;)(2,if)…… 三、词法分析程序的算法思想: 算法的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号,其基本思想是根据扫描到单词符号的第一个字符的种类,拼出相应的单词符号。 3.1 主程序示意图: 编译原理实验报告 实验一 实验题目:词法分析 指导老师:任姚鹏 专业班级:计算机科学与技术系网络工程方向1002班姓名:xxxx 2013年 4月13日 实验类型__验证性__ 实验室_软件实验室三__ 一、实验项目的目的和任务: 了解和掌握词法分析的方法,编程实现给定源语言程序的词法分析器,并利用该分析器扫描源语言程序的字符串,按照给定的词法规则,识别出单词符号作为输出,发现其中的词法错误。 二、实验内容: 1.设计一个简单的程序设计语言(语言中有若干运算符和分界符;有若干关健字;若干标识符及若干常数) 2.确定编译中使用的表格、词法分析器的输出形式、标识符与关键字的区分方法。 3.把词法分析器设计成一个独立的过程。 三、实验要求: 1.从键盘上输入源程序; 2.处理各单词,计算个单词的值和类型; 3.输出个单词名、单词的值和类型。 四、实验代码 #include 一、实验目的 了解词法分析程序的两种设计方法:1.根据状态转换图直接编程的方式;2.利用DFA 编写通用的词法分析程序。 二、实验内容及要求 1.根据状态转换图直接编程 编写一个词法分析程序,它从左到右逐个字符的对源程序进行扫描,产生一个个的单词的二元式,形成二元式(记号)流文件输出。在此,词法分析程序作为单独的一遍,如下图所示。 具体任务有: (1)组织源程序的输入 (2)拼出单词并查找其类别编号,形成二元式输出,得到单词流文件 (3)删除注释、空格和无用符号 (4)发现并定位词法错误,需要输出错误的位置在源程序中的第几行。将错误信息输出到屏幕上。 (5)对于普通标识符和常量,分别建立标识符表和常量表(使用线性表存储),当遇到一个标识符或常量时,查找标识符表或常量表,若存在,则返回位置,否则返回0并且填写符号表或常量表。 标识符表结构:变量名,类型(整型、实型、字符型),分配的数据区地址 注:词法分析阶段只填写变量名,其它部分在语法分析、语义分析、代码生成等阶段逐步填入。 常量表结构:常量名,常量值 2.编写DFA模拟程序 算法如下: DFA(S=S0,MOVE[][],F[],ALPHABET[]) /*S为状态,初值为DFA的初态,MOVE[][]为状态转换矩阵,F[] 为终态集,ALPHABET[] 为字母表,其中的字母顺序与MOVE[][] 中列标题的字母顺序一致。*/ { Char Wordbuffer[10]=“”//单词缓冲区置空 Nextchar=getchar();//读 i=0; while(nextchar!=NULL)//NULL代表此类单词 { if (nextcha r!∈ALPHABET[]){ERROR(“非法字符”),return(“非法字符”);} S=MOVE[S][nextchar] //下一状态 if(S=NULL)return(“不接受”);//下一状态为空,不能识别,单词错误 wordbuffer[i]=nextchar ;//保存单词符号 i++; nextchar=getchar(); } Wordbuffer[i]=‘\0’; 编译原理词法分析程序实现实验报告实验一词法分析程序实现 一、实验内容 选取无符号数的算术四则运算中的各类单词为识别对象,要求将其中的各个单词识别出来。输入:由无符号数和+,,,*,/, ( , ) 构成的算术表达式,如 1.5E+2,100。输出:对识别出的每一单词均单行输出其类别码(无符号数的值暂不要求计算)。二、设计部分 因为需要选取无符号数的算术四则运算中的各类单词为识别对象,要求将其中的各个单词识别出来,而其中的关键则为无符号数的识别,它不仅包括了一般情况下的整数和小数,还有以E为底数的指数运算,其中关于词法分析的无符号数的识别过程流程图如下: 输入字符p指向第一个字符 符号识别*p=+||-||*||/ YYNN*p=0~9*p=E*p=0~9||"." N无效符号Y *p=“.”GOTO 2 GOTO 1 GOTO 1: NY无符号数GOTO 1*p=0~9*p='/0' YN P++NNP++*p=E*p='+'||'-' YY P++P++continue YY *p=0~9*p=0~9 NN 无符号数无符号数 P++P++ continuecontinue GOTO 2: GOTO 2 *p=Econtinue Y 无符号数 P++ continue 三、源程序代码部分 #include 昆明理工大学信息工程与自动化学院学生实验报告 (2011 —2012 学年第 1 学期) 课程名称:编译原理开课实验室: 445 2011年 12 月 19日年级、专业、 班 计科093 学号200910405310 姓名孙浩川成绩 实验项目名称语法分析器指导教师严馨 教 师评语 该同学是否了解实验原理: A.了解□ B.基本了解□ C.不了解□ 该同学的实验能力: A.强□ B.中等□ C.差□ 该同学的实验是否达到要求: A.达到□ B.基本达到□ C.未达到□ 实验报告是否规范: A.规范□ B.基本规范□ C.不规范□ 实验过程是否详细记录: A.详细□ B.一般□ C.没有□ 教师签名: 年月日 一、实验目的及内容 实验目的:编制一个语法分析程序,实现对词法分析程序所提供的单词序列进行语法检 查和结构分析。 实验内容:在上机(一)词法分析的基础上,采用递归子程序法或其他适合的语法分析方法,实现其语法分析程序。要求编译后能检查出语法错误。 已知待分析的C语言子集的语法,用EBNF表示如下: <程序>→main()<语句块> <语句块> →‘{’<语句串>‘}’ <语句串> → <语句> {; <语句> }; <语句> → <赋值语句> |<条件语句>|<循环语句> <赋值语句>→ID=<表达式> <条件语句>→if‘(‘条件’)’<语句块> <循环语句>→while’(‘<条件>’)‘<语句块> <条件> → <表达式><关系运算符> <表达式> <表达式> →<项>{+<项>|-<项>} <项> → <因子> {* <因子> |/ <因子>} <因子> →ID|NUM| ‘(’<表达式>‘)’ <关系运算符> →<|<=|>|>=|==|!= 二、实验原理及基本技术路线图(方框原理图或程序流程图) 语法分析器的设计 一、实验内容 语法分析程序用LL(1)语法分析方法。首先输入定义好的文法书写文件(所用的文法可以用LL(1)分析),先求出所输入的文法的每个非终结符是否能推出空,再分别计算非终结符号的FIRST集合,每个非终结符号的FOLLOW集合,以及每个规则的SELECT集合,并判断任意一个非终结符号的任意两个规则的SELECT 集的交集是不是都为空,如果是,则输入文法符合LL(1)文法,可以进行分析。对于文法: G[E]: E->E+T|T T->T*F|F F->i|(E) 分析句子i+i*i是否符合文法。 二、基本思想 1、语法分析器实现 语法分析是编译过程的核心部分,它的主要任务是按照程序的语法规则,从由词法分析输出的源程序符号串中识别出各类语法成分,同时进行词法检查,为语义分析和代码生成作准备。这里采用自顶向下的LL(1)分析方法。 语法分析程序的流程图如图5-4所示。 语法分析程序流程图 该程序可分为如下几步: (1)读入文法 (2)判断正误 (3)若无误,判断是否为LL(1)文法 (4)若是,构造分析表; (5)由句型判别算法判断输入符号串是为该文法的句型。 三、核心思想 该分析程序有15部分组成: (1)首先定义各种需要用到的常量和变量; (2)判断一个字符是否在指定字符串中; (3)读入一个文法; (4)将单个符号或符号串并入另一符号串; (5)求所有能直接推出&的符号; (6)求某一符号能否推出‘& ’; (7)判断读入的文法是否正确; (8)求单个符号的FIRST; (9)求各产生式右部的FIRST; (10)求各产生式左部的FOLLOW; (11)判断读入文法是否为一个LL(1)文法; (12)构造分析表M; (13)句型判别算法; (14)一个用户调用函数; (15)主函数; 下面是其中几部分程序段的算法思想: 1、求能推出空的非终结符集 Ⅰ、实例中求直接推出空的empty集的算法描述如下: void emp(char c){ 参数c为空符号 char temp[10];定义临时数组 int i; for(i=0;i<=count-1;i++)从文法的第一个产生式开始查找 { if 产生式右部第一个符号是空符号并且右部长度为1, then将该条产生式左部符号保存在临时数组temp中 将临时数组中的元素合并到记录可推出&符号的数组empty中。 } Ⅱ、求某一符号能否推出'&' int _emp(char c) { //若能推出&,返回1;否则,返回0 int i,j,k,result=1,mark=0; char temp[20]; temp[0]=c; temp[1]='\0'; 存放到一个临时数组empt里,标识此字符已查找其是否可推出空字 如果c在可直接推出空字的empty[]中,返回1 for(i=0;;i++) { if(i==count) return(0); 找一个左部为c的产生式 j=strlen(right[i]); //j为c所在产生式右部的长度 if 右部长度为1且右部第一个字符在empty[]中. then返回1(A->B,B可推出空) if 右部长度为1但第一个字符为终结符,then 返回0(A->a,a为终结符) else 编译原理 实验报告 实验名称:词法分析及语法分析专业班级: 姓名: 学号: 完成日期: 实验一、sample语言的词法分析 一、实验目的 给出SAMPLE文法规范,要求编写SAMPLE语言的词法分析程序。 二、实验准备 了解sample语言单词的定义,选择任一种编程语言实现词法分析。 三、实验内容 给出SAMPLE语言文法,输出单词(关键字、专用符号以及其它标记)。 1、格式 输入:源程序文件。输出:关键字、专用符号以及其它标记。 2、实现原理 程序中先判断这个句语句中每个单元为关键字、常数、运算符、界符,对与不同的单词符号给出不同编码形式的编码,用以区分之。 3、实验方法 读懂Sample源代码,自己重点独立实现对常量的判别。 四、实验设计 1、设计SAMPLE语言的词法分析器 A、字符集定义 1. <字符集> → <字母>│<数字>│<单界符> 2. <字母> → A│B│…│Z│a│b│…│z 3. <数字> → 0│1│2│…│9 4. <单界符> → +│-│*│/│=│<│>│(│)│[│]│:│. │; │, │' B、单词集定义 5.<单词集> → <保留字>│<双界符>│<标识符>│<常数>│<单界符> 6.<保留字> → and│array│begin│bool│call│case│char│constant│dim│do│else │end│false│for│if│input│integer│not│of│or│output│procedure│program │read│real│repeat│set│stop│then│to│true│until│var│while│write 7.<双界符> → <>│<=│>=│:= │/*│*/│.. 8.<标识符> → <字母>│<标识符> <数字>│<标识符> <字母> 9.<常数> → <整数>│<布尔常数>│<字符常数> 10.<整数> → <数字>│<整数> <数字> 11.<布尔常数> → true│false 12.<字符常数> → ' 除 {'} 外的任意字符串 ' 2、词法分析系统流程设计编译原理词法分析和语法分析报告 代码(C语言版)
编译原理词法分析实验报告
编译原理-语法分析-算符优先文法分析器
编译原理词法分析和语法分析报告+代码(C语言版)
编译原理实验(词法分析)
编译原理词法分析器
编译原理词法分析程序实现实验报告
昆明理工大学 编译原理 实验二 语法分析器
编译原理语法分析器实验
编译原理词法分析及语法分析