编译原理实验报告

　Compilers Principles Experiment Report

　所在学院：

　所在班级：

　学生姓名：

　学

　号：

　 指导教师：

　教

　务

　处

　2015 年 12 月

　词法分析程序

　 一、实验目的：

　设计、编制和调试一个具体的词法分析程序，加深对词法分析的理解。

　二、实验要求：

　1、通过对 PL/0 词法分析程序(GETSYS)的分析，编制一个具有以下功能的词法分析程序：

　a.输入为字符串（或待进行词法分析的源程序），输出为单词串，即由（单词，类别）所组成的二元组序列；

　b.有一定的错误检查能力，例如能发现 2a这类

　 不能作为单词的字符串。

　三、实验代 码

　#define ID 12//标识符

　#define INT 13//常数

　#define JF 14//界符

　#define YSF 15//运算符

　#define N 30//字符读取的最大长度

　char TOKEN[N];

　FILE *write;

　//查询一个字符串，看其是否与指定的字符相匹配，如果匹配返回 1 个非零的值，如果不匹配，则返回一个 0 值*/

　int looksame(char *a)

　{

　 int i;

　 char*key[22] = { "begin","end","if","then","else","for","do","while","and","or","not","BEGIN","END","IF","THEN","ELSE","FOR","DO","WHILE","AND","OR","NOT" };

　 for (i = 0;i < 22;i++)

　 {

　if (strcmp(key[i], a) == 0)//该字符串是否与关键字相匹配

　 return (i % 11 + 1);

　 }

　 return 0;

　}

　 //把 a输入到指定文件中，然后从该文件中读出字符串，放到一个数组中输出

　void out(int a, char *b)

　{

　 FILE *write;

　 write = fopen("E:\\b.txt", "a+");

　 if (write == NULL)

　 {

　printf("文件打开失败");

　exit(0);

　 }

　 fprintf(write, "%d\t", a);

　 fwrite(b, strlen(b), 1, write);

　 fprintf(write, "\n");

　 fclose(write);

　 printf("%d %20s\t\t", a, b);

　}

　int error()

　{

　 printf("书写格式错误，未被识别\n");

　 return 0;

　}

　void function(FILE *fp)

　{

　 char ch = " ";

　 int i, c;

　 while (ch != EOF)

　 {

　ch = fgetc(fp);//从文件中读取字符

　while (ch == " " || ch == "\t" || ch == "\n") {

　 ch = fgetc(fp);

　}

　if (isalpha(ch)) //isalpha()判断是否为英文字母，是则返回非

　零值，否则返回零

　{

　 TOKEN[0] = ch;

　 ch = fgetc(fp);

　 i = 1;

　 while (isalnum(ch))

　 //isalnum()判断字符是否为英文字

　母或数字,如果是则返回非零值，如果不是则返回零//

　 {

　TOKEN[i] = ch;

　i++;

　ch = fgetc(fp);

　 }

　 TOKEN[i] = "\0";

　 fseek(fp, -1, 1);

　 //用于二进制方式打开的文件,移动文件读写指针位置

　 c = looksame(TOKEN);

　 if (c == 0)

　 {

　out(ID, TOKEN);printf("标识符\n");

　 }

　 else

　 {

　out(c, TOKEN);printf("关键字\n");

　 }

　}

　else if (isdigit(ch))

　 //isdigit()判断是否为0-9 的数字

　{

　 TOKEN[0] = ch;

　 ch = fgetc(fp);

　 i = 1;

　 while (isdigit(ch))

　 {

　TOKEN[i] = ch;

　i++;

　ch = fgetc(fp);

　 }

　 TOKEN[i] = "\0";

　 fseek(fp, -1, 1);

　 out(INT, TOKEN);

　 printf("常数\n");

　}

　else

　{

　 switch (ch)

　 {

　 case"+":out(YSF, "+");printf("运算符\n");

　break;

　 case"-":out(YSF, "-");printf("运算符\n");

　break;

　 case";":out(JF, ";");printf("界符\n");

　break;

　 case",":out(JF, ",");printf("界符\n");

　break;

　 case"|":out(YSF, "|");printf("运算符\n");

　break;

　 case"{":out(JF, "{");printf("界符\n");

　break;

　 case"(":out(JF, "(");printf("界符\n");

　break;

　 case"!":out(JF, "!");printf("界符\n");

　break;

　 case"^":out(JF, "^");printf("界符\n");

　break;

　 case")":out(JF, ")");printf("界符\n");

　break;

　 case"}":out(JF, "}");printf("界符\n");

　break;

　 case"<":ch = fgetc(fp);

　if (ch == "=")

　{

　 out(YSF, "<=");

　 printf("运算符\n");

　}

　 else if (ch == ">")

　{

　 out(YSF, "<>");

　 printf("运算符\n");

　}

　else

　{

　 fseek(fp, -1, 1);

　 out(YSF, "<");

　 printf("运算符\n");

　}

　break;

　 case"=":out(YSF, "=");printf("运算符\n");

　break;

　 case">":ch = fgetc(fp);

　if (ch == "=")

　{

　 out(YSF, ">=");

　 printf("运算符\n");

　}

　else

　{

　 fseek(fp, -1, 1);

　 out(YSF, ">");

　 printf("运算符\n");

　}

　break;

　 case":":ch = fgetc(fp);

　if (ch == "=")

　{

　 out(YSF, ":=");

　 printf("运算符\n");

　}

　else

　{

　 fseek(fp, -1, 1);

　 out(JF, ":");

　 printf("界符\n");

　}

　break;

　 case"/":ch = fgetc(fp);

　if (ch == "*")

　{

　 out(JF, "/*");

　 printf("界符\n");

　 while (1)//注释的内容在词法分析中不显示

　while (ch != "/")

　 ch = fgetc(fp);

　 fseek(fp, -2, 1);

　 ch = fgetc(fp);

　 if (ch == "*")

　 {

　fseek(fp, 1, 1);

　break;

　 }

　 else

　 {

　fseek(fp, 2, 1);

　ch = fgetc(fp);

　 }

　 fseek(fp, -2, 1);

　}

　else

　{

　 fseek(fp, -1, 1);

　 out(JF, "/");

　 printf("界符\n");

　}

　break;

　 case"*":ch = fgetc(fp);

　if (ch == "/")

　{

　 out(JF, "*/");

　 printf("界符\n");

　}

　else

　{

　 fseek(fp, -1, 1);

　 out(YSF, "*");

　 printf("运算符\n");

　}

　break;

　 case EOF:break;

　 default:error();

　break;

　}

　 }

　}

　}

　int main()

　{

　 FILE *read;

　 read = fopen("E:\\a.txt", "r");

　 write = fopen("E:\\b.txt", "a+");

　 if (read == NULL)

　 {

　printf("FILE OPEN FAIL!");

　exit(0);

　 }

　 printf("===========================================================\n");

　 printf("====================词法分析程序===========================\n");

　 printf("===========该分析程序的文件存放在E：\\a.txt 目录下==========\n");

　 printf("===========该程序的分析结果存放在E：\\b.txt 目录下===========\n");

　 printf("===============================

　=============================\n");

　 function(read);

　 fclose(read);

　 system("pause");

　 return 0;

　}

　四、实验截图

　 a.txt

　b.txt

　基于 LL(1)方法的语法分析程序

　一、 实验目的

　设计、编制和调试一个典型的语法分析方法，进一步掌握常用的语法分析方法。

　二、实验要求

　1、根据 LL(1)分析法编写一个语法分析程序，可根据自己实际情况，选择以下一项作为分析算法的输入：

　 a.直接输入根据已知文法构造的分析表 M;

　 b.输入文法的 FIRST(α)和 FOLLOW(U)集合，由

　程序自动生成文法的分析表 M；

　 c.输入已知文法，由程序自动构造文法的分析表M。

　2、程序具有通用性

　所开发的程序可适用于不同的文法和任意输入串，且能判断该文法是否为 LL(1)文法。

　3、有运行实例

　对于输入的文法和符号串，所编制的语法分析程序应能正确判断此串是否为文法的句子，并要求输出分析过程。

　三、实验代码

　#include "stdafx.h"

　#include<stdio.h>

　#include<stdlib.h>

　#include<string.h>

　#include<dos.h>

　char A[20];/*分析栈*/

　char B[20];/*剩余串*/

　char v1[20] = { "i","+","*","(",")","#" };/*终结符

　*/

　char v2[20] = { "E","G","T","S","F" };/*非终结符

　 */

　 int j = 0, b = 0, top = 0, l;/*L 为输入串长度 */

　 typedef struct type

　 /*产生式类型定义

　*/

　{

　 char origin; /*大写字符

　*/

　 char array[5]; /*产生式右边字符 */

　 int length; /*字符个数

　*/

　}type;

　 type e, t, g, g1, s, s1, f, f1;/*结构体变量

　*/

　type C[10][10];/*预测分析表

　*/

　 void print()/*输出分析栈

　*/

　{

　 int a;/*指针*/

　 for (a = 0;a <= top + 1;a++)

　printf("%c", A[a]);

　 printf("\t\t");

　}/*print*/

　 void print1()/*输出剩余串*/

　{

　 int j;

　 for (j = 0;j<b;j++)/*输出对齐符*/

　printf(" ");

　 for (j = b;j <= l;j++)

　printf("%c", B[j]);

　 printf("\t\t\t");

　}

　int _tmain(int argc, _TCHAR* argv[])

　{

　 int m, n, k = 0, flag = 0, finish = 0;

　 char ch, x;

　 type cha;/*用来接受 C[m][n]*/

　/*把文法产生式赋值结构体*/

　 e.origin = "E";

　 strcpy(e.array, "TG");

　 e.length = 2;

　 t.origin = "T";

　 strcpy(t.array, "FS");

　 t.length = 2;

　 g.origin = "G";

　 strcpy(g.array, "+TG");

　 g.length = 3;

　 g1.origin = "G";

　 g1.array[0] = "^";

　 g1.length = 1;

　 s.origin = "S";

　 strcpy(s.array, "*FS");

　 s.length = 3;

　 s1.origin = "S";

　 s1.array[0] = "^";

　 s1.length = 1;

　 f.origin = "F";

　 strcpy(f.array, "(E)");

　 f.length = 3;

　 f1.origin = "F";

　 f1.array[0] = "i";

　 f1.length = 1;

　for (m = 0;m <= 4;m++)/*初始化分析表*/

　for (n = 0;n <= 5;n++)

　 C[m][n].origin = "N";/*全部赋为空*/

　 /*填充分析表*/

　 C[0][0] = e;C[0][3] = e;

　 C[1][1] = g;C[1][4] = g1;C[1][5] = g1;

　 C[2][0] = t;C[2][3] = t;

　 C[3][1] = s1;C[3][2] = s;C[3][4] = C[3][5] = s1;

　 C[4][0] = f1;C[4][3] = f;

　 printf("提示:本程序只能对由"i","+","*","(",")"构成的

　以"#"结束的字符串进行分析,\n");

　 printf("请输入要分析的字符串:");

　 do/*读入分析串*/

　 {

　scanf("%c", &ch);

　if ((ch != "i") && (ch != "+") && (ch != "*") && (ch != "(") && (ch != ")") && (ch != "#"))

　{

　 printf("输入串中有非法字符\n");

　 exit(1);

　}

　B[j] = ch;

　j++;

　 } while (ch != "#");

　 l = j;/*分析串长度*/

　 ch = B[0];/*当前分析字符*/

　 A[top] = "#"; A[++top] = "E";/*"#","E"进栈*/

　 printf("步骤\t\t 分析栈 \t\t 剩余字符 \t\t 所用产生式 \n");

　 do

　 {

　x = A[top--];/*x 为当前栈顶字符*/

　printf("%d", k++);

　printf("\t\t");

　for (j = 0;j <= 5;j++)/*判断是否为终结符*/

　 if (x == v1[j])

　 {

　flag = 1;

　break;

　 }

　if (flag == 1)/*如果是终结符*/

　{

　 if (x == "#")

　 {

　finish = 1;/*结束标记*/

　printf("acc!\n");/*接受 */

　getchar();

　getchar();

　exit(1);

　 }/*if*/

　 if (x == ch)

　 {

　print();

　print1();

　printf("%c匹配\n", ch);

　ch = B[++b];/*下一个输入字符*/

　flag = 0;/*恢复标记*/

　 }/*if*/

　 else/*出错处理*/

　 {

　print();

　print1();

　printf("%c出错\n", ch);/*输出出错终结符*/

　exit(1);

　 }/*else*/

　}/*if*/

　else/*非终结符处理*/

　{

　 for (j = 0;j <= 4;j++)

　if (x == v2[j])

　{

　 m = j;/*行号*/

　 break;

　}

　 for (j = 0;j <= 5;j++)

　if (ch == v1[j])

　{

　 n = j;/*列号*/

　 break;

　}

　 cha = C[m][n];

　 if (cha.origin != "N")/*判断是否为空*/

　 {

　print();

　print1();

　printf("%c->", cha.origin);/*输出产生式*/

　for (j = 0;j<cha.length;j++)

　 printf("%c", cha.array[j]);

　printf("\n");

　for (j = (cha.length - 1);j >= 0;j--)/*产生式逆序入栈*/

　 A[++top] = cha.array[j];

　if (A[top] == "^")/*为空则不进栈*/

　 top--;

　 }/*if*/

　 else/*出错处理*/

　 {

　print();

　print1();

　printf("%c出错\n", x);/*输出出错非终结符*/

　exit(1);

　 }/*else*/

　}/*else*/

　 } while (finish == 0);

　 return 0;

　}

　四、 实验截图

　 于 基于 LR(0) 方法的语法分析程序

　一、实验目的

　设计、编制和调试一个典型的语法分析方法，进一步掌握常用的语法分析方法。

　二、实验要求

　可根据自己实际情况，选择以下一项作为分析算法的输入：

　（1）直接输入根据己知文法构造的 LR(0)分析表。

　（2）输入已知文法的项目集规范族和转换函数，由程序自动生成 LR(0)分析表； （3）输入已知文法，由程序自动生成 LR(0)分析表。

　三、程序代码

　#include "stdafx.h"

　#include<iostream>

　#include<string.h>

　#include<iomanip>

　#include<stdlib.h>

　using namespace std;

　struct stack {

　 int

　top;

　 int

　st[15];

　 //状态栈

　 char sn[15];

　 //符号栈

　}*sign;

　struct analysis {

　 //动作表结构

　 char act;

　 int

　status;

　}action[][6] = {

　 {

　"s",5,"$",0,"$",0, "s",4,"$",0, "$",0

　 },

　 {

　"$",0,"s",6,"$",0, "$",0,"$",0, "A",0

　 },

　 {

　"$",0,"r",2,"s",7, "$",0,"r",2, "r",2

　 },

　 {

　"$",0,"r",4,"r",4, "$",0,"r",4, "r",4

　 },

　 {

　"s",5,"$",0,"$",0, "s",4,"$",0, "$",0

　 },

　 {

　"$",0,"r",6,"r",6, "$",0,"r",6, "r",6

　 },

　 {

　"s",5,"$",0,"$",0, "s",4,"$",0, "$",0

　 },

　 {

　"s",5,"$",0,"$",0, "s",4,"$",0, "$",0

　 },

　 {

　"$",0,"s",6,"$",0, "$",0,"s",11,"$",0

　 },

　 {

　"$",0,"r",1,"s",7, "$",0,"r",1, "r",1

　 },

　 {

　"$",0,"r",3,"r",3, "$",0,"r",3, "r",3

　 },

　 {

　"$",0,"r",5,"r",5, "$",0,"r",5, "r",5

　 }

　};

　analysis G[] = {

　 {

　"E",3

　 },{

　"E",1

　 },{

　"T",3

　 },{

　"T",1

　 },{

　"F",3

　 },{

　"F",1

　 }

　};

　 //此文法信息

　int go[][3] = {

　 1,2,3,99,99,99,99,99,99,99,99,99,8,2,3,99,99,99,99,9,3,99,99,10,99,99,99,99,99,99,99,99,99,99,99,99

　};

　int index(char m) {

　 int id;

　 if ((m == "i") || (m == "E"))

　 id = 0;

　 else if ((m == "+") || (m == "T"))

　id = 1;

　 else if ((m == "*") || (m == "F"))

　id = 2;

　 else if (m == "(")

　id = 3;

　 else if (m == ")")

　id = 4;

　 else if (m == "#")

　id = 5;

　 else

　 id = 99;

　 return id;

　}

　void main() {

　 cout << "参照文法为:\n" << "(1)E→E+T\n" << "(2)E→T\n" << "(3)T→T*F"\n"\

　<< "(4)T→F\n" << "(5)F→(E)\n" << "(6)F→i\n";

　 char instr[20], *current, a;

　 int i = 0, step = 0, ix1, ia, ix2, ig, iG, back;

　 bool flag = true;

　 sign = new stack;

　 cout << "请输入待分析的字符串(以#结束):\n";

　 do {

　cin >> instr[i++];

　 } while (instr[i - 1] != "#");

　 instr[i] = "\0";

　 current = instr;

　 sign->st[0] = 0;sign->sn[0] = "#";sign->sn[1] = "\0";sign->top = 0;

　 cout << "步骤" << setw(20) << "状

　态" << setw(20) << "符

　号" << setw(20) << "输 入 串\n";

　 cout << "====" << setw(20) << "======" << setw(20) << "======" << setw(20) << "========\n";

　 cout << step++ << setw(20) << sign->st[0] << setw(21) << sign->sn << setw(21) << instr << endl;

　 while (flag) {

　cout << step++ << setw(20);

　a = *current;ia = index(a);

　ix1 = sign->st[sign->top]; //cout<<a<<" "<<ia<<" "<<ix1<<" "<<action[ix1][ia].act;

　//hhjhj

　if (ia == 99) {

　 cout << "此文法无法识别该输入串!";

　 break;

　}

　if (action[ix1][ia].act == "s") {

　 sign->top += 1;

　 sign->sn[sign->top] = a;

　 sign->sn[(sign->top) + 1] = "\0";

　 sign->st[sign->top] = action[ix1][ia].status;

　 current++;

　}

　else if (action[ix1][ia].act == "r") {

　 iG = action[ix1][ia].status - 1;

　//零下表开始

　 back = G[iG].status;

　 sign->top -= back;

　 ix2 = sign->st[sign->top];

　 ig = index(G[iG].act);

　 if (go[ix2][ig] != 99)

　sign->top += 1;

　sign->st[sign->top] = go[ix2][ig];

　sign->sn[sign->top] = G[iG].act;

　sign->sn[(sign->top) + 1] = "\0";

　 }

　 else {

　cout << "此文法无法识别该输入串!";

　break;

　 }

　}

　else if (action[ix1][ia].act == "$") {

　cout << "此文法无法识别该输入串!";

　 break;

　}

　else if (action[ix1][ia].act == "A") {

　flag = false;

　}

　for (i = 0;i <= sign->top;i++)

　 cout << sign->st[i] << " ";

　cout << setw(20 - (sign->top)) << sign->sn << setw(20 - strlen(sign->sn)) << current << endl;

　if (flag == false)

　 cout << "文法分析成功!" << endl;

　 }

　}

　四、实验截图

　 中间代码生成程序（逆波兰表示）

　一、实验目的

　 加深对语义翻译的理解

　二、实验要求

　（1）编制一个中间代码生成程序，能将算术表达式等翻译成逆波兰形式； （2）程序具有通用性，即能接受各种不同的算术表达式等语法成分。

　（3）有运行实例．对于语法正确的算术表达式，能生成逆波兰表示，并输出结果；对不正确的表达式，能检测出错误。

　(4)

　提交实习报告，报告内容应包括：

　目的、要求，算法描述，程序代码，运行截图 三、程序代码

　#include "stdafx.h"

　#include <iostream>

　#include <string>

　using namespace std;

　class Transform

　{

　private:

　char s_stack[20];//栈

　 string s_result;//转换之后的字符串，也就是后缀表达式

　 int top;//栈顶

　public:

　 Transform()

　 {

　top=0;

　s_stack[0]="#";

　s_result="";

　 }

　 void pop()

　 {

　top--;

　 }

　 void push(char b)

　 {

　top++;

　s_stack[top]=b;

　 }

　 string TF(string a)

　 {

　bool q=0;

　for (int i=0;i<a.length();i++)

　{

　 switch (a[i])

　 {

　 case "+":

　case "-":

　q=1;

　if (s_stack[top]!="*"&&s_stack[top]!="/"&&s_stack[top]!="@"&&s_stack[top]!="+"&&s_stack[top]!="-")

　{

　 push(a[i]);

　}

　else

　{

　 while(s_stack[top]=="*"||s_stack[top]=="/"||s_stack[top]=="@"||s_stack[top]=="+"||s_stack[top]=="-")

　 {

　s_result+=s_stack[top];

　pop();

　 }

　 push(a[i]);

　}

　break;

　 case "*":

　 case "/":

　q=1;

　if (s_stack[top]!="@"&&s_stack[top]!="*"&&s_stack[top]!="/")

　{

　 push(a[i]);

　}

　else

　{

　 while(s_stack[top]=="@"||s_stack[top]=="*"||s_stack[top]=="/")

　 {

　s_result+=s_stack[top];

　 pop();

　 }

　 push(a[i]);

　}

　break;

　case ":=":

　q=1;

　if (s_stack[top]!="*"&&s_stack[top]!="/"&&s_stack[top]!="@"&&s_stack[top]!="+"&&s_stack[top]!="-")

　{

　 push(a[i]);

　}

　else

　{

　 while(s_stack[top]=="*"||s_stack[top]=="/"||s_stack[top]=="@"||s_stack[top]=="+"||s_stack[top]=="-")

　 {

　s_result+=s_stack[top];

　pop();

　 }

　push(a[i]);

　}

　break;

　 case "@"://负号

　q=1;

　if (s_stack[top]!="@")

　{

　 push(a[i]);

　}

　else

　{

　 while(s_stack[top]=="@")

　 {

　s_result+=s_stack[top];

　pop();

　 }

　push(a[i]);

　}

　break;

　 case "(":

　q=1;

　push(a[i]);

　break;

　 case ")":

　q=1;

　while(s_stack[top]!="(")

　{

　 s_result+=s_stack[top];

　 pop();

　}

　pop();//遇到第一个匹配的（

　while(s_stack[top]!="(")//可能有第二、三、四、、、、个（，

　 如果有，遇到会停

　{

　 if(s_stack[top]=="#")break;

　 s_result+=s_stack[top];

　 pop();

　}

　break;

　 }

　 if (q==0)

　 {

　s_result+=a[i];

　 }

　 else

　 {

　q=0;

　 }

　}

　while(s_stack[top]!="#")//把栈中的字符都出栈

　{

　 s_result+=s_stack[top];

　pop();

　}

　s_result+=s_stack[top];//末尾加上#

　return s_result;

　 }

　 };

　void main()

　{

　 cout<<"请输入表达式（取反用@表示,以#结束）";

　 string s_in;

　 string s_out;

　 cin>>s_in;

　 Transform T;

　 s_out=T.TF(s_in);

　 cout<<"逆波兰表达式为："<<s_out<<endl;

　 system("pause");

　}

　四、实验截图

　封面设计：

　贾丽

　地 址：中国河北省秦皇岛市河北大街 438 号

　邮 编：066004

　电 话：0335-8057068

　传 真：0335-8057068

　网 址：http://jwc.ysu.edu.cn

推荐访问:编译 原理 实验