一个编译器实验的设计与实现

赵会群 孙 晶 谭效辉

摘要:本文介绍了一个适合描述球类比赛战术特点的脚本描述语言,并把该语言作为实验题目进行实验教学,介绍了学生设计并实现的脚本描述语言编译器,该脚本描述语言的词法和文法描述定义,给出词法分析器和语法分析器的结构设计,最后介绍实现中采用的关键技术。

关键词:脚本描述语言;词法分析器;语法分析器

中图分类号:G642 文献标识码:B

传统的编译原理实验基本以高级程序设计语言为对象进行组织,一般包括词法分析、语法分析和语义分析等,教学内容和实验设计几乎几十年不变。由于现在的本科生毕业后很少有机会从事高级语言翻译工作,所以学生对该课程的兴趣不大。随着计算机技术的发展和基于互联网的搜索技术和智能处理技术的广泛应用,编译技术已经不再局限于高级语言的翻译和处理——利用编译原理解决更广泛的应用问题是新的需求。因此笔者在这方面也做了有益尝试。

脚本语言是随着互联网发展起来的信息描述技术,它具有以下特点:

(1) 脚本语言简单易学,开发成本较低。

(2) 脚本语言很容易被解释执行,而且花费时间比较短。

(3) 脚本描述语言设计的设备无关性。

但是,脚本描述语言没有自然语言容易理解,所以最终还是要把脚本语言翻译为自然语言(目标语言)。一般编程语言编写的程序要在计算机上运行,必须转化为计算机能够识别的机器语言,转化过程一般包括词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成等环节。我们设计的球类脚本描述语言主要用于对体育比赛视频进行标准化,所以在语言构成上没有高级语言复杂,翻译时也不需要上面提到的编译实现全过程,只需要进行词法分析、语法分析和语义分析3个环节。

1球类脚本描述语言

随着社会文明的发展与进步,体育比赛已经成为人民文化生活中不可缺少的组成部分。2008年,北京成功举办了第29届奥林匹克运动会,运动员共打破38项世界纪录,取得了骄人的成绩。作为本次奥运会科技攻关课题组的成员,我们参加了国家乒乓球队攻关项目的研究工作,为中国乒乓球队设计实现了一个基于视频标注的技、战术分析系统。我们采用编译技术翻译乒乓球脚本描述语言,实时、准确地记录并分析比赛中发生的各种技、战术细节,为教练员提供客观翔实的分析数据。

作为“编译原理”的任课教师,我们认为该课对学生系统掌握计算机基础理论十分重要,但由于学生在今后工作中很难用到编译技术,就会产生厌学思想,因此为学生设计一个好的编译原理实验成为当务之急。为此,我们结合承担的科研课题,设计了一个既让学生感兴趣,又能加深他们对编译原理思想理解的实验。

根据球类比赛的特点和脚本描述语言的设计要求,球类比赛可分为两种:一是比赛需主、客队同台(场)竞技,如沙滩排球、乒乓球、篮球、足球和网球等;二是主、客队轮流上场,比赛对手不是同台竞技,如台球和保龄球等。第一种球类比赛具有以下特点:(1)进攻/防守形成博弈;(2)博弈双方的技术动作具有相似性。为此,我们把第一种比赛的相关技、战术描述抽象成如下形式:

队员+技术动作+技术动作发生区域+技术动作结束区域

我们的设计目标主要针对第一种比赛。脚本描述语言的语法结构如图1所示。

其中单词由英文字母构成,可以采用汉语拼音的字首进行编码;句子由单词加分隔符“●”构成。图2是一个乒乓球比赛脚本描述语言的案例。

2解释器的设计与实现

根据球类比赛技、战术分析的需求,设计的解释器由

词法器、语法器和语义分析模块三部分组成,如图3所示。其中词法分析器负责词法分析的预处理和输入单词的解释;语法分析器负责分析输入码的语法结构检查和解释;在词法和语法分析器的基础上,语义分析模块负责比赛技战术的分类与统计工作。下面分别介绍上述逻辑部件的设计与实现。

2.1词法分析器

根据第1节对球类比赛脚本描述语言语法结构的设计以及球类比赛描述的特点,我们对该描述语言的单词符号进行设计。单词符号有以下4种:

(1) 技术动作描述符:一般由四类字符组成,英文字母、数字、“+”和“-”。其中,英文字母是技术动作的编码,由一个编码映射表支持词法解释;数字用于描述技术动作发生的区域,该语言总是把比赛场地分割成若干个不同的区域;“+”和“-”是两个特殊符号,一般用于一些极其特殊的技、战术描述,如乒乓球中的“擦边球”或“擦网”等。

(2) 间隔符:用于区分不同的技术动作,一般用“●”表示。

(3) 保留字:为了明确标示比赛视频的开始和结束、每一小节或单局比赛的开始和结束、比赛中的暂停和开始,设计了一些保留字,如Match: Start、Match: End、Set1:Start、Set1:End等。

(4) 控制符:用于比赛中的比分调整,如ap03:05、*p02:05。

上述单词符号构成单词的词法分析状态转换描述如图4所示。

上述词法分析的算法如下:

算法1一个乒乓球脚本描述语言的词法分析算法

Input: 基于乒乓球比赛脚本简码的技战术输入码

Output: 描述语言完全码

Step1: 词法检测、运动区域补偿

Word=Read(code); // 输入一个单词符号//

Do while word<>‘

If field(word, Last_position )=‘● then break

else if field(word,start_position )and field(word,target_position )=

num then return //词法检测结束//

else if field(previous_word,target_position)=num

then field(word, start_position)=field(previous_word,target_position);

word=read(code);

enddo

Step2: 词法检测、动作补偿

Word=Read(code); //输入一个单词符号//

Do while word<>‘

If field(word, style_position )<>‘ then break;

else if word.artribute=offence and field(word,start_position )=right_domain //该动作为进攻动作//

then field(word, style_position)=‘z;

else if word.artribute=offence and field(word,start_position )=left_domain //该动作为进攻动作//

then field(word, style_position)=‘f;

else print(‘an error be found);

word=read(code);

enddo

end

在上面的算法中,每一个单词由四位码构成,field(word, style_position)是单词的第一位,表示动作的方式;field(word, act_position)是单词的第二位,表示动作的类型;field(word, start_position)是单词的第三位,表示球的起点;field(word, target_position)是单词的第四位,表示球飞行的结束位置。该算法需要两次遍历输入码,因此算法的复杂性为O(L)。

2.2语法分析器

根据图1所示的脚本描述语言结构,它的文法G如图5所示:

其中:S为开始符号,表示一个输入码,T为非终结符,它可以是ε 字;C1为动作方式码,它只能产生一个表示动作方式终结符号;C2为动作分类码,它只能产生一个表示动作的终结符号;N1为动作起始区域,它只能产生一个表示区域的终结符号,N2为动作终止区域,它只能产生一个表示区域的终结符号。

例如:乒乓球比赛的输入码为:ZX16●FB66●T62● ZH23●ZH33●ZH33●ZH31。它表示:正手发下旋球从1区到6区●对方反手摆短从6区到6区●反手挑到2区●对手正手弧圈球从2区到3区●正手弧圈球从3区到3区●对手正手弧圈球从3区到3区●正手弧圈球至对方1区后得分。

定理:文法G是LL(1)文法。

证明:为每一个非终结符求FIRST()集和FOLLOW()集如下:

FIRST(S)={w, ε}; FIRST(T)={w,ε}; FIRST(S)

={●,ε};FIRST(W)={w};

FOLLOW(S)={#}, FOLLOW(T)={● , #}; FIRST(S)

={#}; FOLLOW(W)={●, #}

由LL(1)文法的条件可知,G文法满足:

FIRST(αi) FIRST(αj)=;

FOLLOW(A) FOLLOW(A) = 

因此,G是LL(1)文法。

对文法G的语法分析可以采用递归下降法或预测分析表法。由于脚步描述语言中采用的文法符号可以自定义,符号的数量并不多,所以建议采用预测分析表来实现。下面是一个改进的预测分析表算法。

算法2基于预测分析的语法分析算法

首先把“#”,然后把文法开始符号“S”推进栈charstack;

把第一个输入符号读进a(char类型);

Flag = TRUE;

Do while (Flag)

{取栈(charstack)顶的元素放入X(char类型)中

If( X是文法中终结符号中的一个)

{If(X==a) Then

把下一个符号读进a

把栈顶的元素删除

else

Flag = FALSE; //词法错误

}

else if (X==#)

{if (X==a) then Flag = TRUE; //词法分析结束

else Flag = FALSE; //词法分析错误}

else

{

找出X在二维数组中的行数Row; //用二维数组表示预测分析表

找出a在二维数组中的列数Column; //CString m_strTemp[4[6]

If (m_strTemp[Row][Column]!=“ ” && m_strTemp[Row][Column]!=“E”) //E代表ε

把栈顶元素删除;

把m_strTemp[Row][Column]中的元素从后往前推入栈中;

else if (m_strTemp[Row][Column]==“E”) then 删除栈顶元素;

else Flag = FALSE;

}

}

算法2的执行时间为O(M*N),M和N分别为预测分析表的行和列下标。

3实验设计

根据第2节对球类脚本描述语言中词法、语法分析器的讨论,我们设计了两个实验:

实验一:基于球类脚本描述语言的词法分析器的设计与实现。

实验目的:通过本实验,学生掌握词法分析器的体系结构、各功能部件的设计与实现方法,为进一步学习语法分析器奠定基础,能够灵活掌握词法分析的原理和技术。

实验条件:图6给出了一个乒乓球台的分割图,用于表示击球的区域;表1和表2分别用于描述击球的方式和动作,这些描述信息可以供学生设计乒乓球脚本描述语言时参考。

实验要求:

 画出脚本描述语言的体系结构图,并定义各个功能模块的实现策略

 定义一个小型球类脚本描述语言,可以参照乒乓球比赛的技战术描述需求定义,具体形式如图6所示

 完成一个实验报告,分析具体输出结果的 语义

实验二:基于文法G的语法分析器设计与实现

实验目的:通过本实验,学生掌握语法分析器的体系结构、各功能部件的设计与实现方法,为进一步学习语义分析器奠定基础,能够灵活掌握语法分析的原理和技术。

实验条件:表3给出了预测分析表结构,学生根据所设计的描述语言填写具体预测动作。

实验要求:

 给出非简化G文法,对其进行消除左递归操作

 在实验一定义的球类脚本描述语言基础上设计具体的符号表

 手工完成预测分析表的构造,如表3所示,并用数组结构存储

 完成一个实验报告,分析具体输出结果的 语义

4结论

笔者在本文中设计了一个球类比赛脚本描述语言编译器实验,给出球类脚本描述语言的语法结构,包括词法和文法规则;给出了词法分析器和语法分析器实现需要的关键算法,为学生进一步实现奠定了基础;给出词法分析器和语法分析器实验模板,为学生完成实验规范了必要的格式和实验要求。

与传统的编译器实验相比,本文设计的编译器实验有较强的应用背景,更接近大学生的实际经历,能够激发绝大多数学生的学习热情,收到了比较好的教学效果。本实验并没有改变传统实验的本质,还是在高级语言编译器的实现技术基础上完成,只是对具体的语言背景进行了调整,同样可以达到系统掌握编译原理的教学要求,读者可以根据自己的实际情况,选择本实验作为教学补充内容。

自行设计脚本描述语言并实现其编译器是我们的一种尝试,该项工作基于我国的奥运攻关课题。在完成科研任务的同时,我们将对教学环节进行适当的补充和扩展,希望读者提出宝贵意见。

参考文献:

[1] 陈火旺,刘春林. 程序设计语言编译原理[M]. 3版. 北京:国防工业出版社,2000.

[2] 官尚元,张芝萍,徐立锋,等. C/C++代码自动生成脚本语言接口的实现[J]. 计算机工程,2005,31(8):102-104.

[3] 李爱萍,王家礼,段利国. ATLAS语言中大量关键词的处理方法研究[J]. 计算机工程与设计,2006,27(9):1581-1582,1600.

[4] 赵会群,孙晶. 体育计算:一个新的计算机应用研究领域[J]. 计算机科学,2004,31(8):89-92.

[5] Zhao HQ,Chen L. The Application of PipeFilter Architecture to Semantic Analysis and the Realization Skills and Tactics of Table Tennis Analysis System[C]. Nanjing,2008.