SLR(1)分析方法实现开放式考试系统.pdf

总第2 4 1期 中国电化教育2 0 0 7 . 2 技 术 与 应 用 一、 引言 计算机考试系统是利用计算机技术支持某一学 科进行计算机实时考试的一种系统。它可以对考试 的全过程实行计算机的管理与控制,即在考前由计 算机对考生数据进行预处理;考试中对考试的过程 实施自动管理与控制;考试结束后进行自动评分处 理并对分数进行汇总分析等。 目前社会上有一些不同类型的考试系统,但这 些系统大都是比较传统的、 标准化的考试系统, 更主 要的是它们都是封闭的,即由开发人员根据试题的 要求编写评分代码。 从知识的表示方法上看, 这些系 统采用的是过程表示法。这种封闭的考试系统虽有 着评分效率较高、 控制系统容易实现等长处, 但其缺 点也是不容忽视的,其中最主要的就是需要由开发 人员根据对每次考试的试题要求,重新编写评分代 码。 这就导致不易对其修改和添加新知识, 且当对某 一过程进行修改时, 又极易影响到其他过程, 使系统 的维护十分不便。例如, 当需要改变试题时, 软件开 发人员必须重新开发新的评分系统,以适应新的试 题。 也就是说这种评分系统只能一次性使用, 从而造 成系统的使用率低、 开发周期长、 软件复用量小、 开 发工作量大、 开发费用高等, 同时系统中也容易遗留 较多的错误。 为了克服封闭式考试系统的不足,需要建立一 种开放式的考试系统,开放式考试系统允许用户根 据需要方便高效地输入试题并由系统形成相应的评 分答案库,进而可以对学生的计算机操作进行客观 公正地考核与评定。 二、 开放式考试系统的产生式表示法 1 .产生式和产生式系统 1 9 4 3年逻辑学家p o s t最早提出产生式的概念。 产生式的基本结构包括前提和结论两部分: 前提( 或 i f部分) 描述状态; 结论( 或t h e n部分) 描述在状 态存在的条件下所作的某些动作, 即: 前提条件结 论动作( 或:i f状态t h e n动作) 。 在产生式系统中, 论域的知识被分成两部分: (1) 事实: 用以表示静态的知识, 如事物、 事件和 它们之间的关系; (2) 产生式规则: 用以表示推理和行为的过程。 由于产生式系统的知识库中主要存储的是规则, 所以又称为基于规则的系统(r u l e b a s e d s y s t e m) 。相 应地, 产生式系统包括以下三个基本组成部分: (1) 事实库: 存储有关问题的状态、 性质等事实 的叙述性知识, 也称为综合数据库。 (2) 规则库: 存储有关问题的状态转移、 性质变化 等规则的过程性知识, 或称为规则集, 可以描述成: r i : i fr l st h e nr r s( i = 1 , 2 , . . . , n)其中, r i称为规则库中第i条规则; r l s是第i条规则条件部分,可以是任何子句 的逻辑组合; r r s是第i条规则结论部分,可以是一个结论 或操作, 或者是多个结论或操作的组合。 (3) 控制器: 根据有关问题的控制性知识, 选择 控制策略, 将规则与事实进行匹配, 控制利用知识推 理求解问题的过程, 推理出新的信息。 2 .开放式考试系统的产生式表示法 对于一个开放的考试系统,其系统结构应包括 答案库、 考生操作结果、 控制系统等主要部分。依据 上述产生式系统的基本组成,我们可以利用产生式 表示法的基本思想, 构筑开放式考试系统的模型, 如 下图所示。 从图中可以看出,开放式考试系统的基本结构 由三个基本模块构成: (1) 控制系统: 该模块完全由程序组成, 它分为 s l r ( 1 ) 分析方法实现开放式考试系统 柴欣,史巧硕,武优西 (河北工业大学计算机科学与软件学院, 天津3 0 0 1 3 0 ) 摘要: 该文介绍了封闭式考试系统所选用的知识表示法和开放式考试系统所选用的知识表示法, 以及选用产生 式表示法实现开放式考试系统的优点, 进而论述了用s l r分析方法实现对产生式表示法中的规则进行识别的过程。 关键词: 考试系统; 过程表示法; 产生式表示法;s l r ( 1 )分析方法 中图分类号:g 4 3 4 文献标识码:b 文章编号:1 0 0 69 8 6 0(2 0 0 7)0 20 1 0 40 3 1 0 4 2 0 0 7 . 2中国电化教育 总第2 4 1期技 术 与 应 用 两个部分:一部分用来指导和帮助用户根据实际试 题要求形成答案库, 即答案输入系统; 另一部分用来 控制整个产生式评分系统的运行,根据答案库的内 容, 依据考生操作结果, 决定问题的评分过程, 实现 对考生操作的自动评分, 即自动评分系统。 这两部分 程序由相应软件研发小组来完成。 (2) 答案库: 用来存放所有的试题答案, 它可以 以数据库的形式存储起来,它描述了考卷中所要求 考核的知识点的评分规则,以及该知识点所分配的 分数情况。 由此可见, 答案库是开放式考试系统进行 自动评分的基础, 其知识的完整性、 一致性、 准确性、 灵活性以及知识组织的合理性,对自动评分系统的 运行效率和准确性都有重要影响。答案库既可由相 应软件研发小组来提供,也可由用户自己通过答案 输入系统来完成。 (3) 考生操作结果: 存放在数据库中或以文件的 形式存在, 在评分时, 要根据答案库的要求, 依据评 分规则对考生的操作结果进行自动评判。 3 .为试题建立评分规则 为了对考核的知识点进行自动评分,需要为这 些知识点建立评分规则。 参照产生式系统的规则集, 我们可以将评分规则描述如下: r i :i f某知识点操作正确t h e n该知识点得 分, 分值( i = 1 , 2 , . . . , n)。 为了进一步说明答案库的形式,下面简要给出 一套wo r d上机操作考试的部分试题要求及相应的 试题的答案库。其试题说明为:打开考生目录下的 w o r d k t . d o c文件,将该文件的纸张大小设为a 4; 在 该文件内插入一个矩形, 其大小为高度2厘米, 宽度 3厘米; 根据上面的试题要求,答案库中与试题相对应 的评分规则如下: r 1i f页面宽度2 1厘米a nd页面高度2 9 . 7 厘米t h e n设置页面为a 4正确,1分; r 2i f存在矩形t h e n插入矩形正确,1分; r 3 i f存在矩形a nd该对象高度2厘米 a nd该对象宽度3厘米t h e n矩形大小设置正 确,1分 通过上述介绍,不难发现这样一种知识表示方 法具有自然性、 模块性。 由于产生式规则是答案库中 最基本的知识单元,各规则之间只能通过答案库发 生联系,而不能相互调用,从而增加了规则的模块 性, 有利于对知识的增加、 删除、 修改和扩充。 三、 开放式考试系统的答案库规则识别过程 l r分析法是一种从左至右扫描、 自下而上的语 法分析方法, 由于其适用范围大, 在编译程序中大都 采用此法进行语法分析,并且l r分析法还可用于 词法分析。 实际使用的l r分析法通常可分为s l r( 1 )分析 法( 简单l r分析) 、l r( 1 )分析法和l a l r( 1 )分析法 ( 向前l r分析) 。由于s l r( 1 ) 分析法的实现代价远 远低于l r( 1 )分析法, 算法又较l a l r( 1 )分析法简 单, 而且基本能够解决程序设计语言的词法/语法分 析问题, 因此s l r ( 1 )分析法更具有实用价值, 本文就 是利用s l r ( 1 )分析法对答案库中的规则进行识别。 由于选用了产生式表示法来表示试题答案, 因 此在产生式规则中必然会出现很多能够正确判断某 个知识的操作是否正确的小的基本函数和a nd ( 合 取联结词) 、or( 析取联结词) 、not( 否定联结词) 、 ( 、 ) 等运算符 1 2 , 为了对这些表识符进行识别, 构造 如下文法g e : 0 . i f t h e n s i fet h e n 1 . ore eort 2 . e t 3 . a nd t ta ndf 4 . t f 5 . not f notp 6 . f p 7 . ()p ( e ) 8 . p f u n 这里f u n是指那些能够判断某个知识点操作是 否正确的小基本函数。 对于不同的应用系统, 这些基 本的函数是不尽相同的; 即使对于相同的系统, 根据 考核基本知识点的不同,也可以对基本函数进行适 当增减。 对文法g e 按照s l r( 1 )分析方法 3 就可以对答 案库中的规则进行识别,我们仍以上面的wo r d测 试题为例进行说明:r 3i f存在矩形a nd该对象 高度2厘米a nd该对象宽度3厘米t h e n矩形 大小设置正确,1分。 首先识别出 “存在矩形” 是一个函数, 执行相 应函数并按照规则8规约为p; 将p按照规则6规约为f; 将f按照规则4规约为t; 移入a nd算符; 识别出 “该对象高度2厘米” 是一个函数, 执 1 0 5 总第2 4 1期 中国电化教育2 0 0 7 . 2 技 术 与 应 用 征订启事 欢迎订购 中国电化教育2 0 0 5年和2 0 0 6年合订本电子版光盘 为了满足广大教师和教育技术工作者的需要, 中国电 化教育杂志社编辑制作了中国电化教育2 0 0 5年和2 0 0 6 年合订本电子版光盘, 现已由电化教育电子出版社出版, 中 国电化教育杂志社发行。 中国电化教育 是中华人民共和国教育部主管, 中央 电化教育馆主办的国家级现代教育技术类专业期刊;是国 内知名的教育类核心刊物,入选c s s c i检索源期刊;创刊 2 6年来一直是教育技术行业的主流学术媒体;2 0 0 5年全国 教育类期刊检索排名第一; 内容集国内外教育技术理论、 课 堂电化教学实践、 信息技术与课程整合、 学习资源建设、 远 程教育与网络教育、 信息技术教育研究、 教育技术设备与产 品、 国际教育技术等多方面研究成果、 动态与信息于一体, 是广大教师和教育技术工作者了解中国和世界教育信息化 进程的重要窗口, 具有学术性、 权威性、 政策性、 指导性、 应 用性和服务性。 该光盘收录了 中国电化教育2 0 0 5年和2 0 0 6年的全 部文章, 以国际通用的标准文件格式对文章进行存储, 便于 查找和摘录; 同时, 以we b页面的形式对内容进行组织, 便 于检索并可在不同配置的计算机上使用,对各级教育技术 研究机构和大、 中、 小学从事相关工作的人员具有很大的参 考和收藏价值。 每套光盘定价8 0元。 地址: 北京复兴门内大街1 6 0号电教大楼0 1 3信箱 联系人: 李晓华邓军 邮编:1 0 0 0 3 1 传真: (0 1 0)6 6 4 1 9 0 4 7 电话:( 0 1 0 ) - 6 6 4 9 0 9 2 26 6 4 9 0 9 2 4 6 6 4 9 0 9 2 5 1 3 7 0 1 2 9 0 1 8 7 开户行: 北京银行营业部 户名: 中国电化教育杂志社 账号:0 1 0 9 0 5 2 0 5 0 0 1 2 0 1 1 1 0 2 5 7 0 2 !“ !“ !“ !“ 行相应函数并按照规则8变换为p; 将p按照规则6规约为f; 将ta ndf按照规则3规约为t, 并计算t 的值; 识别出 “该对象宽度3厘米” 是一个函数, 执 行相应函数并按照规则8变换为p; 将p按照规则6规约为f; 将ta ndf按照规则3规约为t, 并计算t 的值; 由于接下来的是t h e n关键字, 所以将t按 照规则2规约为e; 将e按照规则0规约为s。 至此, 整个规则识别完毕, 并将结果存放在s中。 通过上面分析可以看出, 对文法g e 按照s l r ( 1 )分析方法 3 可以有效地对产生式表示法中的规则 进行识别, 这也为自动评分提供了保证。据此, 我们 可以按照如下步骤完成自动评分系统的工作: (1) 打开答案库, 将要评分文件的答案读入, 并 关闭答案库文件; (2) 同时打开要评分的考生操作文件; (3) 读下一条产生式规则; (4) 对该条规则按s l r( 1 )分析方法进行自动评 分, 以判断考生某项操作是否正确, 若正确则给考生 成绩加上该操作的分数; (5)判断答案库中是否还存在没有判断的对该 操作文件进行自动评分的产生式规则,若存在待判 断的产生式规则, 则转向第(3) 步; 否则宣告对该文 件的自动评分过程结束,并关闭此评分的考生操作 文件; (6)判断答案库中是否还存在其他要评分的考 生操作文件,若存在待评分操作文件,则转向第2 步; 否则宣告对该考生的自动评分过程结束。 四、 结论 综上所述, 由于开放式考试系统采用了产生式表 示法,因此避免了传统考试系统的过程表示法的缺 点。这样用户能够根据自己的实际需要, 通过使用答 案输入系统形成答案库; 同时自动评分系统根据答案 库对考生的操作进行准确地自动评分, 改变了传统的 考试系统由专门的软件开发人员来开发的弊端, 大大 地缩短了考试系统的开发周期, 使得更多的人能够非 常简便地使用开放式考试系统。 又由于引入了答案库 的概念,用户也可以自行构造自己的考试试题库, 通 过使用现代化考试系统中随机组题功能使得试题的 复用变成了可能, 降低了开发的工作量, 节省了开发 费用, 并且能够降低系统在评分中的错误, 使考试系 统易于维护, 为现代化教