一个编译器实验的设计与实现摘要:本文介绍了一个适合描述球类比赛战术特点的脚本描述语言,并把该语言作为实验题目进行实验教学,介绍了学生设计并实现的脚本描述语言编译器,该脚本描述语言的词法和文法描述定义,给出词法分析器和语法分析器的结构设计,最后介绍实现中采用的关键技术。
关键词:脚本描述语言;词法分析器;语法分析器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 breakelse if field(word,start_position )and field(word,target_position )= num then return //词法检测结束//else if field(previous_word,target_position)=numthen field(word, start_position)=field(previous_word,target_position); word=read(code);enddoStep2: 词法检测、动作补偿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);enddoend在上面的算法中,每一个单词由四位码构成,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’)={#}; FOLLO W(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把栈顶的元素删除elseFlag = 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结论笔者在本文中设计了一个球类比赛脚本描述语言编译器实验,给出球类脚本描述语言的语法结构,包括词法和文法规则;给出了词法分析器和语法分析器实现需要的关键算法,为学生进一步实现奠定了基础;给出词法分析器和语法分析器实验模板,为学生完成实验规范了必要的格式和实验要求。