实验二：语法分析器
一、实验目的：
1．强化对系统软件综合工程实现能力的训练；
2．加强对语法分析原理、方法和基本实现技术的理解；
二、实验内容：
1) 用C语言或者其他的高级语言作为宿主语言完成C0语言的词法分析器的设计和实现.
2) 针对if语句的文法编写一个递归下降分析程序，输出结果为抽象语法树。注意，if语句文法中的表达式E采用四则运算表达式的文法；抽象语法树的格式自行设计，如果需要降低难度的话，也可用具体语法树而不用抽象语法树作为输出.
三、实验要求：
1. 编写C0语言的语法分析器的源程序并调试通过。其中语法分析程序既可以自己手动去完成，也可以利用YACC自动生成。
2. 通过测试程序的验收；
3.实验报告按照提供的模板填写：
（1）功能描述：该程序具有什么功能？
（2）程序结构描述：函数调用格式、参数含义、返回值描述、函数功能；另外可以附加函数之间的调用关系图、程序总体执行流程图。
（3）实验总结：你在编程过程中花时多少？多少时间在纸上设计？多少时间上机输入和调试？多少时间在思考问题？遇到了哪些难题？你是怎么克服的？你对你的程序的评价？你的收获有哪些？
四、评判标准：
1. 输出正确的实验结果；
2. 代码清晰，格式良好；
3. 提交报告，报告阐述清楚。
五、程序工作说明：（以C0语言为例）
由于语法分析是在词法分析上做的进一步分析，所以要求在上次输出词法分析结果的同时，也需要输出语法分析的结果。该结果用xml格式的文件表示，如：
<root>
<Tree lineNo=’…’ nodeType=’…’ string=’…’ dataType=’…’ isArray=’…’ value='...'>
<Child>
<Tree >
…
</Tree>
</Child>
…
</Tree>
…
</root>
程序输入/输出示例：
如源程序为如下：
void main()
{
int a=0;
int b=2;
while(a==b)
++a;
}
则要求得到如下输出文件：
<?xml version="1.0"?>
<root>
<Tree lineNo=1 nodeType="function" string="main"
dataType="void" value="none">
<Child>
<Tree lineNo=3 nodeType="var_declarations" string="none"
dataType="none" value="0">
<Child>
<Tree lineNo=3 nodeType="var_declaration" string="a"
dataType="int" value="0">
</Tree>
</Child>
<Child>
<Tree lineNo=4 nodeType="var_declaration" string="b"
dataType="int" value="2">
</Tree>
</Child>
</Tree>
</Child>
<Child>
<Tree lineNo=5 nodeType="sentences" string="none"
dataType="none" value="none">
<Child>
<Tree lineNo=5 nodeType="while" string="none"
dataType="none" value="none">
<Child>
<Tree lineNo=5 nodeType="condition"
string="a==b" dataType="boolean" value="unknown">
</Tree>
<Tree lineNo=6 nodeType="sentences" ...>
<Child>
<Tree lineNo=6 nodeType="expression"
String="++a" ...>
</Tree>
</Child>
</Tree>
</Child>
</Tree>
</Child>
</Tree>
</Child>
</Tree>
</root>
说明：NodeType实际输出的内容可根据你定的节点类型来输出，也可以后面附带附加信息。另外，对于nodeType为"var_declaration"和"sentences"的标签，你可以输出，也可以不输出，这里这样输出主要是为了让变量声明和语句更好地区分，建议大家也这样输出。这里的实例只列举一个函数，为了考虑多个函数的情况，你可能还需要"function_declaration"和参数表。
六、相关知识：
词法分析器任务：
将词法分析过程输出的记号输入到语法分析器中，按照C0的文法规则，将记号和相关数据输出到语法树中。
1）语法树中节点的类型
public enum NodeKind
{
FuncK,SenK,ExpK
};
public enum SenKind
{
IfK,WhileK，RetureK
...
}
public enum ExpKind
{
SimpleK,AssignK
}
2）语法树的节点数据结构
public class treeNode
{
Struct treeNode * child[MAXCHILD];
NodeKind nodeKind;
Union
{
SenKind sen;
ExpKind exp;
}kind;
Union
{
TokenType op;
Int val;
Char * name;
}attr;
ExpType type;
int lineNo;
}
3）C0的语法
program→ { var-declaration | fun-declaration }
var-declaration→ int ID { , ID }
fun-declaration→ ( int | void ) ID ( params ) compound-stmt
params → int ID { , int ID } | void | empty
compound-stmt→ { { var-declaration } { statement } }
statement→ expression-stmt∣compound-stmt ∣if-stmt ∣while-stmt
|return-stmt
expression-stmt→ [ expression ] ;
if-stmt→ if( expression ) statement [ else statement ]
while-stmt→ while( expression ) statement
return-stmt→ return [ expression ] ;
expression→ ID = expression | simple-expression
simple-expression→ additive-expression [ relop additive-expression ]
relop → < | <= | > | >= | == | !=
additive-expression→ term [( + | - ) term ]
term→ factor [ ( * | / ) factor ]
factor→ ( expression )| ID | call | NUM
call→ ID( args )
args→ expression { , expression } | empty
ID →… ;参见C语言标识符定义
NUM →… ;参见C语言数的定义
七、参考书目：
1. Kenneth C. Louden著，冯博琴译《编译原理及实践》，机械工业出版社，20##年
2. Andrew W.Appel著，赵克佳等译《现代编译原理C语言描述》人民邮电出版社，20##年
3. 陈火旺，刘春林等，《程序设计语言编译原理》第三版，国防科大出版社，20##年
第二篇：实验二 递归下降语法分析报告
学 生 实 验 报 告
（理工类）
课程名称： 编译原理 专业班级： 08计算机科学与技术（单）
所属院部： 信息技术学院 指导教师：
20XX ——20XX 学年 第 二 学期
金陵科技学院教务处制
实验报告书写要求
实验报告原则上要求学生手写，要求书写工整。若因课程特点需打印的，要遵照以下字体、字号、间距等的具体要求。纸张一律采用A4的纸张。
实验报告书写说明
实验报告中一至四项内容为必填项，包括实验目的和要求；实验仪器和设备；实验内容与过程；实验结果与分析。各院部可根据学科特点和实验具体要求增加项目。
填写注意事项
（1）细致观察，及时、准确、如实记录。
（2）准确说明，层次清晰。
（3）尽量采用专用术语来说明事物。
（4）外文、符号、公式要准确，应使用统一规定的名词和符号。
（5）应独立完成实验报告的书写，严禁抄袭、复印，一经发现，以零分论处。
实验报告批改说明
实验报告的批改要及时、认真、仔细，一律用红色笔批改。实验报告的批改成绩采用百分制，具体评分标准由各院部自行制定。
实验报告装订要求
实验批改完毕后，任课老师将每门课程的每个实验项目的实验报告以自然班为单位、按学号升序排列，装订成册，并附上一份该门课程的实验大纲。
实验项目名称： 递归下降语法分析 实验学时： 6
同组学生姓名： 无 实验地点： B513
实验日期： 2011.3.10/3.24/4.7 实验成绩：
批改教师： 批改时间：
一、实验目的和要求
通过本实验，了解递归下降预测分析的原理和过程以及可能存在的回溯问题，探讨解决方法，为预测分析表方法的学习奠定基础。分析递归下降子程序的优缺点。
二、实验仪器和设备
硬件系统：586以上计算机、服务器要求内存256以上、Cpu 2.0GHz以上、Clinet内存128以上、CPU奔腾III以上，硬盘，光驱等
软件系统：Visual Studio 2005中文版软件
三、实验过程
1、设计框架
图1-1 递归下降程序框架图
2、设计步骤
1)给定文法：
EàE+T｜T
TàT*F｜F
Fà(E)｜i
2)构造FIRST()集和FOLLOW()集
表2-1 FIRST()集和FOLLOW()集
3、程序源代码
using System;
using System.Collections.Generic;
using System.Text;
namespace 递归下降语法分析
{
public class Program
{
public static char []a=new char[50];
public static char []b=new char[50];
public static char []d=new char[200];
public static char []e=new char[10];
public static char ch;
public static int n1,i1=0,flag=1,n=5;
public static int total=0;/*步骤计数器*/
public static int E1()
{
int f,t;
Console.Write(total);
Console.Write("\tE--＞TG\t");total++;
flag=1;
input();
input1();
f=T();
if (f==0) return(0);
t=G();
if (t==0) return(0);
else return(1);
}
public static int E()
{
int f,t;
Console.Write(total);
Console.Write("\tE--＞TG\t");total++;
e[0]='E';e[1]='=';e[2]='＞';e[3]='T';e[4]='G';e[5]='#';
output();
flag=1;
input();
input1();
f=T();
if (f==0) return(0);
t=G();
if (t==0) return(0);
else return(1);
}
public static int T()
{
int f,t;
Console.Write(total);
Console.Write("\tT--＞FS\t");total++;
e[0]='T';e[1]='=';e[2]='＞';e[3]='F';e[4]='S';e[5]='#';
output();
flag=1;
input();
input1();
f=F();
if (f==0) return(0);
t=S();
if (t==0) return(0);
else return(1);
}
public static int G()
{
int f;
if(ch=='+') {
b[i1]=ch;
Console.Write(total);
Console.Write("\tG--＞+TG\t");total++;
e[0]='G';e[1]='=';e[2]='＞';e[3]='+';e[4]='T';e[5]='G';e[6]='#';
output();
flag=0;
input();input1();
ch=a[++i1];
f=T();
if (f==0) return(0);
G();
return(1);
}
Console.Write(total);
Console.Write("\tG--＞^\t");total++;
e[0]='G';e[1]='=';e[2]='＞';e[3]='^';e[4]='#';
output();
flag=1;
input();input1();
return(1);
}
public static int S()
{
int f,t;
if(ch=='*') {
b[i1]=ch;
Console.Write(total);
Console.Write("\tS--＞*FS\t");total++;
e[0]='S';e[1]='=';e[2]='＞';e[3]='*';e[4]='F';e[5]='S';e[6]='#';
output();
flag=0;
input();input1();
ch=a[++i1];
f=F();
if (f==0) return(0);
t=S();
if (t==0) return(0);
else return(1);}
Console.Write(total);
Console.Write("\tS--＞^\t");total++;
e[0]='S';e[1]='=';e[2]='＞';e[3]='^';e[4]='#';
output();
flag=1;
a[i1]=ch;
input();input1();
return(1);
}
public static int F()
{
int f;
if(ch=='(') {
b[i1]=ch;
Console.Write(total);
Console.Write("\tF--＞(E)\t");total++;
e[0]='F';e[1]='=';e[2]='＞';e[3]='(';e[4]='E';e[5]=')';e[6]='#';
output();
flag=0;
input();input1();
ch=a[++i1];
f=E();
if (f==0) return(0);
if(ch==')') {
b[i1]=ch;
Console.Write(total);
Console.Write("\tF--＞(E)\t");total++;
flag=0;input();input1();
ch=a[++i1];
}
else {
Console.Write("error\n");
return(0);
}
}
else if(ch=='i') {
b[i1]=ch;
Console.Write(total);
Console.Write("\tF--＞i\t");total++;
e[0]='F';e[1]='=';e[2]='＞';e[3]='i';e[4]='#';
output();
flag=0;input();input1();
ch=a[++i1];
}
else {Console.Write("error\n");return(0);}
return(1);
}
public static void input()
{
int j=0;
for (;j＜=i1-flag;j++)
Console.Write(b[j]); /*输出分析串*/
Console.Write("\t\t");
Console.Write("\t\t",ch); /*输出分析字符*/
}
public static void input1()
{
int j;
for (j=i1+1-flag;j
Console.Write(a[j]); /*输出剩余字符*/
Console.Write("\n");
}
public static void output()
{ /*推导式计算*/
int m,k,j,q;
int i=0;
m=0;k=0;q=0;
i=n;
d[n]='=';d[n+1]='＞';d[n+2]='#';n=n+2;i=n;
i=i-2;
while(d[i]!='＞'&&i!=0) i=i-1;
i=i+1;
while(d[i]!=e[0]) i=i+1;
q=i;
m=q;k=q;
while(d[m]!='＞') m=m-1;
m=m+1;
while(m!=q) {
d[n]=d[m];m=m+1;n=n+1;
}
d[n]='#';
for(j=3;e[j]!='#';j++){
d[n]=e[j];
n=n+1;
}
k=k+1;
while(d[k]!='=') {
d[n]=d[k];n=n+1;k=k+1;
}
d[n]='#';
//system("pause");
}
static void Main(string[] args)
{ /*递归分析*/
int f,p,j=0;
char x;
d[0]='E';
d[1]='=';
d[2]='＞';
d[3]='T';
d[4]='G';
d[5]='#';
Console.Write("请输入字符串(长度＜50,以#号结束）\n");
do{
ch=(char)Console.Read();
a[j]=ch;
j++;
}while(ch!='#');
n1=j;
ch=b[0]=a[0];
Console.Write("步骤\t文法\t分析串\t\t分析字符\t剩余串\n");
f=E1();
if (f==0) return;
if (ch=='#')
{
Console.Write("accept\n");
p=0;
x=d[p];
while(x!='#') {
Console.Write(x);p=p+1;x=d[p]; /*输出推导式*/
}
}else {
Console.Write("error\n");
Console.Write("回车返回\n");
Console.ReadLine();
Console.ReadLine();
return;
}
Console.Write("\n");
Console.Write("回车返回\n");
Console.ReadLine();
Console.ReadLine();
}
}
}
程序输入输出举例:
1、输入“(i+i)*i”，分析如下图所示：
2、输入“i#”，分析如下图所示：
3、输入“i+i#”，分析如下图所示：
四、实验结果与分析
通过本次实验基本掌握了语法分析的原理和递归下降子程序分析方法，并且能将学到的知识学以致用，提高了对代码的分析能力，掌握了递归下降语法的构造，对自上再而下的语法分析模式有了更好的认识和理解。
通过编写程序进一步复习巩固了C#语言的相关知识，由于对C#语言的掌握不扎实，在编程过程中遇到了很多基础性问题，通过不断的查阅课本，最终解决了问题，但程序仍然存在很多值得改进和完善的地方，这就提醒我们在以后的学习过程当中应该及时复习巩固以前学过的相关知识。