（教育技术学专业论文）教育信息管理领域语言计算方法的研究.pdf

摘要 建模语言是对现实环境的模拟，是真实系统的缩影，为解决具体问题提供了 一个系统的设计方案。云计算时代已经到来，新的时代有新的要求。服务成为新 时代的主旋律，计算机软件领域也应努力跟上，全方位地为用户提供优质的服务。 本论文尝试打破传统的设计开发流程，提出从“开发者设计范型”向“用户设计 范型”转变的总体设想。设计者设计特定领域建模语言，用户通过特定领域建模 语言描述自己的需求，由语言处理器直接调用基础服务，满足用户的各种需求。 u m l ( u n i f i e dm o d e l i n gl a n g u a g e ) 统一建模语言，是面向对象领域内的标准建 模语言，日益被业内人士所接受和认可，对u m l 的研究也是相当泛滥。通过对大 量建模语言国内外研究的分析发现，目前计算方法领域的研究还是相当欠缺的， 因此本论文尝试利用函数式编程语言f # ，从计算方法领域着手，采用建模语言 的设计理念，进行符号建模语言计算方法的研究。 伴随计算机网络技术的发展，教育信息铺天盖地，因此教育信息管理同趋凸 显，教育信息管理直接关系教育的绩效问题，关系到国家的发展和未来。并且通 过对大量建模语言国内外研究的分析发现，目前计算方法领域的研究还是相当欠 缺的，因此本论文尝试利用函数式编程语言f # ，从计算方法领域着手，采用建 模语言的设计理念，对教育信息管理领域语言计算方法进行研究。 本论文提出了“三步走 设计模型：扫描器、解析器和执行器。 第一步，扫描器的设计。扫描器是对用户输入的字符串( 用户各色的现实需 求) 进行扫描，通过扫描器程序中的正则表达式进行一一匹配，生成对应t o k e n 序列。正则表达式是强大、高效、便捷的文本处理工具，在文本编辑器或其他工 具里，它通常被用作来检索或者替换那些符合某种模式的文本内容。如同一门袖 珍编程语言的通用模式表示法( g e n e r a lp a t t e r nn o t a t i o n ) ，赋予使用者描述和分析 文本的能力。几乎任何一种程序设计语言都支持正则表达式，都可以使用正则表 达式与所搜索的字符串进行匹配。 第二步，解析器的设计。解析器的功能是对输入的标识符序列进行语法检查， 并生成语法树。解析器的核心是上下文无关文法的设计，通过上下文无关文法描 述的语法生成规则进行解析，生成对应的表达式树。上下文无关文法是一种描述 语言数学模型，功能异常强大，几乎所有的程序设计语言都可以利用上下文无关 文法进行定义。设计人员为程序设计语言设计编译器和解释器时，首先需要先获 取该程序设计语言的文法，进而才能为该程序设计语言量身定做编译器和解释 器，否则编写的编译器和解释器不能很好地或者说根本就不能为该语言翻译和使 用。 第三步，执行器的设计。将经过解析器解析生成的语法树结构，送入执行器， 经过执行器的运算，输出计算的最终结果。执行器中用到一个递归函数，将输入 的树结构由上往下分解，一直到不能继续分解( e n dc a s e ) 为止，然后再将计算 结果逐级向上返回合成最终结果。 本文首先以算术语言运算为代表，设计出了关于计算方法的“三步走”流程 模式，然后运用流程模式对案例关系代数具体研究，设计出解决该类具体问题的 方法步骤。对于案例二图形化语言，由于时间的紧迫，目前还没能开发出来，有 待今后的进一步研究。 最后对研究进行分析讨论，提出目前研究的不足和进一步的研究方向。 关键词：扫描器；解析器；执行器；正则表达式；上下文无关文法；f 群 a b s t r a c t m o d e l i n gl a n g u a g ei st h em o d e lo fr e a l i s t i ce n v i r o n m e n t ，i st h ee p i t o m eo ft r u e s y s t e m ，a n dp r o v i d e sas y s t e m i cd e s i g np a t t e r n sf o rs o l v i n gs p e c i f i cp r o b l e m s t h e t i m e so fc l o u dc o m p u t i n gh a sc o m e ，a n dt h e r ea r en e wr e q u i r e m e n t si nt h en e wt i m e s s e r v i c eb e c o m e st h ed o m i n a n tt h e m ei nt h en e wt i m e s t h ef i e l do fc o m p u t e rs o f t w a r e s h o u l da l s ok e e pu pw i t ht h en e wt i m e sa n dp r o v i d eh i g h q u a l i t ys e r v i c e sf o ru s e r s 1 1 1 i sp a p e rt r yt ob r e a kt h et r a d i t i o n a lp r o c e s so fd e s i g n - d e v e l o p m e n t a n do f f e ra o v e r a l l c o n c e p t i o n w h i c h t r a n s f o r m sf r o m “d e v e l o p e r s d e s i g np a r a d i g m ”t o u s e r s d e s i g np a r a d i g m ”n ed e v e l o p e rd e s i g n st h ed o m a i ns p e c i f i cm o d e l i n g l a n g u a g e ，a n dt h eu s e rd e s c r i b e st h e i rd e m a n d sb ym e a n so ft h ed o m a i ns p e c i f i c m o d e l i n g a tt h es a m et i m e t h eb a s i cs e r v i c e sa r ec a l l e dt om e e tt h e u s e r u m l ( u n i f i e dm o d e l i n gl a n g u a g e ) i s a ns t a n d a r d m o d e l i n gl a n g u a g ei n o b j e c t o r i e n t e df i e l d ，a n di ti si n c r e a s i n g l ya c c e p t e db yi n s i d e r s ，t h e r e f o r et h e r ea r e s om a n yr e s e a r c hf o ru m l t h e r ea r el i u l er e s e a r c ha b o u tt h ef i e l do fc a l c u l a t i n g m e t h o d ，s ot h i sp a p e rt r yt os t u d yt h i sp r o b l e ma d o p t i n gt h ed e s i g nc o n c e p to f m o d e l i n gl a n g u a g e u s i n gt h e f u n c t i o n a lp r o g r a m m i n gl a n g u a g e - f 释 t h i sp a p e rp u t sf o r w a r dt h ed e s i g nm o d e lo f “t h r e e - s t e p ”：s c a n n e r , p a r s e ra n d e n g i n e f i r s t l y , t h ed e s i g no ft h es c a n n e r t h es c a n r l e rt r a n s f o r m st h eu s e r s s t r i n gt oa s e r i e so ft o k e ns e q u e n c eu s i n gt h er e g u l a re x p r e s s i o n s t h er e g u l a re x p r e s s i o na r e p o w e r f u l e f j f i c i e n ta n dc o n v e n i e n t t e x t p r o c e s s i n g i ti su s e dt or e t r i e v et h e t e x t s ，w h i c hm e e tt h ed e m a n di nt e x te d i t o r s a l m o s ta n yk i n do fp r o g r a m m i n g l a n g u a g es u p p o r tt h er e g u l a re x p r e s s i o n , a n dm a t c ht h es t r i n gu s i n gr e g u l a r e x p r e s s i o n s s e c o n d l y , t h ed e s i g no fp a r s e r t h ep a r s e rg o e so v e rt h ei d e n t i f i e r s a n dg e n e r a t e s as y n t a c t i ct r e e c f gi st h ec o r eo ft h ep a r s e r i ti sap o w e r f u lm a t h e m a t i c a lm o d e lo f d e s c r i p t i o nl a n g u a g e a l m o s ta n yp r o g r a m m i n gl a n g u a g ec a nb ed e s i g n e db yc f g t h ed e s i g n e r sm u s to b t a i nt h ec f g a n dt h e nd e s i g nt h et a i l o r e dc o m p i l e r sa n d i n t e r p r e t e rw h e nt h e y d e s i g nt h ec o m p i l e r sa n di n t e r p r e t e rf o rap r o g r a m m i n g l a n g u a g e ，o rt h ed e s i g n sm a yn o tb es u i t a b l e t h i r d l y , t h ed e s i g no fe n g i n e t h ep u r p o s eo ft h ee n g i n ei st oo u t p u tt h e c a l c u l a t i o nf o rt h es y n t a c t i ct r e e t h e r ei sar e c u r s i v ef u n c t i o ni nt h ee n g i n e w h i c h d e c o m p o s i t i o nt h es y n t a c t i ct r e et o p t o b o t t o mu pt ot h ee n dc a s e ，a n dt h e nc a l c u l a t e t h er e s u l tb a c kt ot o ps t e pb ys t e p t 1 1 i sp a p e rd e s i g n st h ed e s i g nm o d e lo f t h r e e - s t e p ”o nb e h a l fo fa r i t h m e t i c o p e r a t i o n ，a n dt h e ng i v ea ne x a m p l eo fr e l a t i o n a la l g e b r aa n dg r a p h i c sl a n g u a g e i t s u r g e n tt od e v e l o pt h eg r a p h i c sl a n g u a g e , a n di t sm yf t l r t h e rs t u d y n el a s tb u tn o tt h el e a s t , t h e r ea r et h es h o r t a g eo ft h ep a p e ra n dt h ed i r e c t i o no f t h ef u r t h e rr e s e a r c h k e y w o r d s ：s c a n n e r ；p a r s e r ；e n g i n e ；r e g u l a re x p r e s s i o n ；c o n t e x t f r e eg r a m m a r ；f 撑 图表目录 图1 - 1 从开发者设计剑用户设计的转变2 图2 - 1 编译的各个阶段s 图2 2 语句s u m = a + b 的语法树7 图2 3 句子“大连是美丽的城市”图解1 4 图2 4 安装有f 孝的v i s u a ls t u d i o 的初始界面2 6 图2 5v i s u a ls t u d i o 中“新建项目”对话框2 6 图2 6 新建一个名为f i r s tp r o g r a m m i n g 的硎a p p l i c a t i o n 2 7 图3 1 算术语言计算方法的界面设计3 3 图3 2 通常用c # 设计的类似问题界面。3 3 图3 3 字符串转为树结构3 4 图3 4 建模语言计算的一般过程3 4 图3 5 算术语言的界面设计解决方案4 1 图3 6 算术运算的界面实现4 2 图4 1 关系代数案例的设计模型4 8 图4 2 图形化语言窗口设计5 7 表2 1 上例c 语言源程序中的t o k e n 7 表2 2c h o m s k y 层级类别【4 】1 6 表2 3 非打印字符及各自的含义1 9 表2 4 常用元字符1 9 上海师范人学硕十学位论文 论文独创性声明论文使j j 授权声明 论文独创性声明 本论文是我个人在导师指导下进行的研究工作及取得的研究成果。论文中除 了特别加以标注和致谢的地方外，不包含其他人或机构已经发表或撰写过的研究 成果。其他同志对本研究的启发和所做的贡献均已在论文中做了明确的声明并表 示了谢意。 作者签名劣竹嗍加沁z ， 论文使用授权声明 本人完全了解上海师范大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其它手段保存论文。保密的论文在解密后遵守此 规定。 作者签磙咯导师签名：叫街彪日期：矽幻，多沙 上海师范人学硕十学位论文第一章论文研究概述 第一章论文研究概述 1 1 问题的提出 云计算时代的到来，意味着软件向服务化方向发展的趋势，在这种趋势的推 动下，用户使用服务的方式则决定了i t 系统方案的生命力和竞争力。工t 系统构 建中合理的角色定位应该是：由用户来决定做什么，而怎么做则由开发者来决定。 然而我们传统的开发流程一般是：首先用户根据自己的实际需要提出需求，然后 开发者根据用户的需求分析设计、编写代码、测试、开发，最后形成最终产品。 此时并不是说本次开发就到此为止了，接下来用户可能会进一步提出要求，这时 开发者就必须根据用户变化的需求修改程序，有时甚至会重新来设计开发，浪费 了大量的劳动和开发成本。那么怎样才能使开发者的这种服务具有足够的弹性， 以满足用户个性化需求的变动? 这即牵涉到i t 系统的可持续发展力的问题。 鉴于此，本论文尝试改变传统的开发流程，于是产生了从“开发者设计范型” 向“用户设计范型”转变的总体设想。如图1 所示，在开发者主导的设计范型( 前 者) 下，用户通过自然语言( 即我们的日常用语无需专业术语) 来描述自己的需 求，然后再由开发者将实际需求转换为程序语言。用户只有通过开发者才能消费 服务。然而在用户主导的设计范型( 后者) 下，用户可以通过特定领域建模语言 来描述业务需求，再由语言处理器直接自动调用基础服务。这样不仅用户可以直 接消费服务，而且开发者的职责也可专注于提供系统的基础服务，而非僭越使用 者来制定业务层面的规则。这样就解决上文中提到的问题，通过用户设计范型使 开发者的服务具有足够的弹性，以满足用户个性化需求的变动，提高系统的可持 续发展力。 第一章论文研究概述上海师范大学硕十学位论文 使用行 开 厂程序讲青 1r 拱础软件服务 = _ 弘务 使用者 图卜1 从开发者设计到用户设计的转变 语言以书写方式分为：符号语言和图形语言两种。符号语言是所有那些课书 写的语言，例如s q l 、汉语、h t m l 、c # 等。图形语言是用几何图形、连线等作为 “单词”的语言。例女i j u m l ，概念图等。从上图我们很容易发现，实现用户设计 范型的关键问题是特定领域的建模语言。 建模语言，是针对某一专门领域设计的小语言，用来解决该领域的问题。建 模语言一般满足两个条件：( 1 ) 人可读，即用它所描述的内容可在直接被人阅读。 ( 2 ) 没有歧义，即可以被转换为某种数据结构，进而用机器处理。例如日常生 活中最常见的阿拉伯符号标记算术语言。它和自然语言一样具有递归特性，可直 接阅读，同时又不存在歧义，因此是研究建模语言计算方法的理想样本材料。因 此，本论文重点研究如何设计一个可顺序书写的符号建模语言，并且将其输入计 算机后能够自动运行，达到预期的目的。 虽然关于语言编译的研究有很长的历史1 ，但用命令式编程语言( 例如c 语 言) 实现语言引擎的难度较高，普通的应用开发人员很难掌握。本论文在大量实 践研究和学习总结的基础上，通过函数式编程语言f # ，利用函数式方法系统地阐 述符号建模语言的计算方法的设计，并在此基础上进行案例的应用研究。 云计算时代，教育信息以前所未有的速度发展，要想利用好如此大量的教育 信息为我们的教育服务，就必须对浩瀚的教育信息进行有效的管理。因此本文尝 试在教育信息管理领域，设计一种建模语言，并对其计算方法进行研究，探索出 12 0 世纪5 0 年代n o a m c h o m s l o 已经发表了生成性语法的形式化理论s y n t a c t i c s t r u c t u r e s 2 上海师范人学硕十学何论文第一章论文研究概述 套模型方法，提高教育信息管理的绩效。以前关系代数的教学大多都是通过黑 板来讲述，云计算时代，我们也可以利用时代的有利条件来改善教学，鉴于此， 本论文尝试用计算机来实现关系代数的教学，因此选取关系代数作为本论文案例 研究对象，利用教育信息管理领域语言计算方法的设计思路和模型，展开关系代 数的研究，并对提出的模型进行验证。 1 2 研究综述 在c n k i 中国优秀博硕士学位论文全文数据库中检索，选择中国期刊全文数 据库、中国博士学位论文全文数据库、中国优秀硕士学位论文全文数据库、中国 重要报纸全文数据库时，我们以建模语言为“主题 进行垮库检索，检索到4 9 0 6 篇文章；以建模语言为“关键词”进行垮库检索，检索到7 5 1 篇文章；以领域语 言为“篇名”进行垮库检索，检索到3 1 篇文章；以符号建模语言为“篇名 进 行垮库检索时，检索到0 篇文章。纵观所有检索到的文章，我们可以发现这些文 章中基本上都是统一建模语言u m l 在各方面的应用研究。另外对教育信息管理进 行搜索，发现这方面的文章不少，但经过仔细考察研究，发现目前还没有从建模 语言计算方法角度研究教育信息管理，所以，本论文尝试从建模语言计算方法角 度对教育信息管理进行研究，探索出该领域计算方法的设计模型。 1 - 3 研究的关键问题 ( 1 ) 学习与研究函数式编程语言f 髯 ( 2 ) 符号建模语言计算方法的设计 ( 3 ) 案例应用研究( 关系代数) ( 4 ) 案例应用过程中出现的问题( 优化和语法的检测) 1 4 研究的目标 用函数式编程语言f # ，开发出一套有关符号建模语言的计算方法的设计模 型，并通过案例关系代数的应用研究来证明其有效性，并找出该设计模型的 使用价值与使用范围。 3 第一章论文研究概述上海师范人学硕十学位论文 1 5 研究方法( 文献研究、案例研究、比较研究) 在具体的研究方法上，本论文采用文献研究法、案例研究法、比较研究法等 研究方法。 ( 1 ) 文献研究法：主要指搜集、鉴别、整理文献，并通过对文献的研究， 形成对事实科学认识的方法。在本论文的研究过程中，笔者搜索了大量有关计算 方法、函数式编程工具f # 、函数式方法、l a m b d ac a l c u l u s 、r e l a t i o n a la l g e b r a 方面的资料，通过对资料的研究和学习，掌握了计算方法的一般实现过程，函数 式方法的思想与实现原理以及f # 语言的使用，为论文中符号建模语言计算方法的 开发奠定了基础。 ( 2 ) 案例研究法：案例研究是对真实生活情境中的现象进行的实证调查， 是当研究者认为情境与所研究的现象极为相关，但现象与情景之间的界限并不总 是很明显时所采取的研究方法。徐碧美( a m yb m t s u i ) 本论文中采用的 案例研究，主要是通过关系代数，来验证课题中设计的计算方法，同时也通过案 例研究也分析该计算方法的使用范围和应用条件。 ( 3 ) 比较研究法：任何事物都是相比较而存在的。有比较，才有鉴别；有 鉴别，才有认识。比较研究，是研究性课程实施中常用的一种研究方法。比较研 究是确定对象间异同的一种思维方法，即根据一定的标准，对某种事物的客观现 象在不同情况下的不同表现，进行比较分析，从而找出客观事物的普遍规律及其 特殊性本质，力求得出符合客观实际结论的方法。本论文中利用“开发者主导的 设计范型”与“用户主导的设计范型 比较，发现后者是更适合于目前云计算时 代下的i t 系统的开发流程，更好的满足用户个性化需求的变动。 4 上海师范人学硕士学位论文 第二章教育信息管理领域语言计算方法基础 第二章教育信息管理领域语言计算 方法基础 2 1 教育信息管理领域语言计算方法的理论基础 2 1 1 编译原理 懂得计算机程序的人都知道，目前情况下，用户基本上都是用高级语言在计 算机上来实现他们的需求。在计算机上执行高级语言程序一般分为两步：第一步， 用一个编译程序把高级语言翻译成机器语言程序；第二步，运行所得的机器语 言程序求得计算结果。编译程序是一种翻译转换程序，它能够将高级语言( 如c 语言、c # 或j a v a 等) 程序翻译成对应的低级语言( 如汇编语言或机器语言) 程序， 或者说是由源程序编译成目标程序，编译程序又被称为编译器。2 一般情况下，编译程序的工作流程可划分为词法分析、语法分析、语义分析 与中间代码生产、代码优化、目标代码生成五个阶段( 如图2 所示) ，这是一中很 常见的划分方法。编译程序的五个阶段的功能分别由其对应的五个模块来实现， 这五个模块分别被称为词法分析器、语法分析器、语义分析器与中间代码生成器、 优化器和目标代码生成器。 图2 - 1 编译的各个阶段3 下面用c 语言作为源程序，主要介绍编译程序中的词法分析器和语法分析器 2 黄贤英王柯柯，编译原理及实践教程【m 】，北京：清华大学出版社，2 0 0 8 2 3 黄贤英王柯柯，编译原理及实践教程【m 】，北京：清华大学出版社，2 0 0 8 2 ，p 3 5 第二章教育信息管理领域语言计算方法基础上海师范人学硕士学位论文 1 词法分析器( s c a n e r ) 任何一种程序设计语言都有其允许使用的字符集合，如字母a z 、a z 、数字 0 9 、+ 、一、木、等等。高级程序设计语言中的标识符都由是允许在该语言中 使用的字符集合中的字符组成，是语言中有明确含义的最小组合，有的标识符仅 由一个符号组成，如+ 、一、木、等，而有的标识符则是由多个字符集合中的字符 组成，如+ = 、m a i n 等等。 词法分析器的功能是：按照从左到右的顺序依次对输入的源程序字符序列进 行扫描，扫描出一个个的标识符( 或者称为是单词符号) ，构造对应的内部表示 t o k e n 序列，同时检查源程序的词法错误。编译程序总是用某种程序语言书写的 程序，语言的操作对象只能是该语言规定的各种数据。因为编译程序的操作对象 是源程序中的各种语法单位，因此，必须把它们表示成某种数据结构形式。 t o k e n 表示最小的语义信息单位，即单词内部表示的数据结构形式。( 这里 讲的单词不是程序设计语言中的语法概念，而是编译程序中引进来的一个概念， 是指它是最小的语义单位，不能再分隔的。) t o k e n 中需要记录有关单词的信息： 单词的标记，标示单词的种类词法信息；单词的特征属性( 标识符名，符号 表地址等等) 语义信息。 词法分析器的分析过程通常是这样的。读当前字符序列，直至文件结束。如 果是： 标识符，则继续判断是保留字还是变量标识符，构造t o k e n 表示； 数字，则继续判断是整型还是实型，构造t o k e n 表示； 构造其他合法的符号的t o k e n 表示； 遇到非法符号则报错。4 对上例的c 源程序，词法分析器扫描出源程序中出现的t o k e n 及其类型，如 表2 - 1 所示： 4 金英编译原理课件 6 上海师范人学硕士学位论文 第二章教育信息管理领域语言计算方法基础 表2 1 上例c 语言源程序中的t o k e n 序号类型单词序号 类型 单词 1 标识符m a l n 1 7 运算符 2 界符 ( 1 8 标识符a 3 界符 ) 1 9 运算符 + 4 界符 2 0 标识符b s 标识符i n t 2 1 界符 6 标识符 a 2 2 标识符 p r i n t f 7运算符2 3界符 ( 8常量22 4 界符 9 界符 2 5 界符d 1 0 标识符b 2 6 界符 ” 1 1运算符 2 7 界符 ， 1 2常量42 8 标识符s 啪 2 9 界符 ) 1 3 界符 1 4 标识符 s u m3 0 界符 ， 1 5 运算符 3 1 界符 ) 1 6 标识符s u m 可以看到上面的t o k e n 可分为下面几类：标识符的t o k e n 、常量的t o k e n 、 界符的t o k e n 和运算符的t o k e n 。 2 语法分析器( p a r s e r ) 语法分析是词法分析的后续工作，将经过词法分析器后所得到的t o k e n 序列 组成各类语法短语( 如表达式、语句、程序等) ，经过分析，验证输入的字符串 在语法上是否正确，否则，则给出提示：语法错误。经过语法分析器得到的的语 法短语通常用语法树来表示，直观地展示各个语法短语之间的关系。语法分析用 到单词的t o k e n 表示，但是并不改变单词的t o k e n 表示。如前面c 源程序的例子 中的单词序列s u m = a + b 经过语法分析，认为其符合c 语言的语法，并且确定它 是一个赋值语句，可以表示为如图2 2 所示的语法树。 嫩值语句 标识符 l 图2 2 语句s u m = a + b 的语法树 7 、 r 第二章教育信息管理领域语言计算方法基础上海师范人学硕十学位论文 语法分析是根据该语言的语法规则来进行分析的，语言的语法规则通常是由 递归规则来定义的。如表达式和赋值语句可以由下述递归规则来定义： 任何标识符都是表达式； 任何常数都是表达式： 若表达式l 和表达式2 都是表达式，则表达式1 + 表达式2 也是表达式； 赋值语句的定义规则是：标识符= 表达式。5 图2 - 2 的语法树就是根据赋值语句和表达式的递归定义规则生成的。 2 1 2l a m b d ac a l c u l u s l a m b d a 演算刚开始以神秘的面孔出现。起初仅仅把它看做是一种命名机制， 然而，它是传统数学符号的直接扩展。早在二十世纪三十年代由a l o n z oc h u r c h 和s t e p h e nc o l ek l e e n e 发明的，是一个形式系统，被设计出来用来研究函数定 义，函数应用和递归。 我们对数字的标记最早是西方文艺复兴时期被人们提出的，例如f i b o n a c c i 。 它是以一个小的固定数字集合为为特征，值因其在数字中位置的不同而不同。表 达式标记和等号( = ) 标记直到1 7 世纪才出现，那时f r a n c o i sv i 、e r e 开始为参数 占位符和算术运算的缩写设计系统化的方法。直到那时，一个像3 x 2 这样的简单 表达式必须描述出其实际运算过程，即需要从一个x 值获得3 x 2 的值。又过了将 近2 5 0 年，a l o n z oc h u r c h 为匿名函数开发了标记，他的这种标记被成为入演算 ( “l a m b d ac a l c u l u s ) 。c h u r c h 结束了他的这一形式系统，目的是为数学提供一 种函数式基础，但是最后数学家们选择了集合论。在二十世纪6 0 年代，计算机 科学界的m c c a r t h y 、s t r a c h e y 、l a n d i n 和s c o t t 等将其作为一种通用工具对入 演算进行了重新设计与开发。早在1 9 3 6 1 9 5 0 年间，在整型和实型数值的现代标 准被广泛接受之前，计算机工程师们开始为数字代表而努力并且尝试了很多方 法。v i e t e 提出的有关表达式标记是程序语言f o r t r a n 中的主要创新点，将程序 员从编写乏味的装配指令序列中解放出来。在不久后的1 9 6 0 年，m c c a r t h y 开发 出了l i s p 语言，他了解九演算，他的l i s p 语言就是建立在九演算基础之上。 现在，并不是所有的语言都提供功能强大的九演算，一些主要的程序设计语 5 黄贤英王柯柯，编译原理及实践教程【m 】，北京：清华大学出版社，2 0 0 8 2 8 上海师范人学硕十学何论文第二章教育信息管理领域语言计算方法基础 言如j a v a 和c + + 中都对基本数据类型和对象进行了严格的区分。 l a m b d a 演算可以被称为最小的通用程序设计语言。它包括一条变换规则 ( 变量替换) 和一条函数定义方式，在l a m b d a 演算中，每个表达式都代表一个 只有单独参数的函数，这个函数的参数本身也是一个只有单一参数的函数，同时， 函数的值是又一个只有单一参数的函数。6 例如，“乘2 函数f ( x ) = x 木2 ，用 l a m b d a 演算表示为久x x 宰2 ( 灭y y 宰2 也是样的，参数的取名无关紧要) 。 l a m b d a 表达式可以递归地定义为( 1 ) 一个名字；( 2 ) 一个l a m b d a 抽象包 括字母入、一个名字、一个圆点和一个l a m b d a 表达式；( 3 ) 一个函数应用由两 个毗邻放置的l a m b d a 表达式组成；或者( 4 ) 一个加了括号的l a m b d a 表达式。 大多数作者都假定应用是从左向右结合的( 因此f ab 解释为( f a ) b 而不是f ( a b ) ) ，应用的优先级比抽象更高( 因此入x a b 将解释为入x ( a b ) ，而不是( 入 x a ) b ) 。可以用必要的括号改变默认的结组方式，特别是如果我们需要区分用作 函数的l a m b d a 表达式和用作参数的那些l a m b d a 表达式时。7 l a m b d a 演算中的表达式( e x p r s s i o n ) l a m b d a 演算是函数的一种标记，它非常简洁，但是初看上去有点让人摸不 着头脑，它来源于数理逻辑。l a m b d a 演算中的表达式有严格的书写形式，即没 有像+ 、( ) 2 2 _ 类的中缀和后缀运算符，另外，函数及其参数只是被简单的写 在一起，参数两边并没有小括号。例如数学上的表达式“s i n ( x ) ”，在l a m b d a 演 算中可以简单的记作“s i nx ”。如果一个函数有不止一个的参数，那么它们是简 单的排列在函数的后面，比如数学表达式“x + 3 在l a m b d a 演算中记为“+ x3 ”， 函数“x 2 ”在l a m b d a 演算中则变为“木xx ”。小括号只是在强调特殊部分的 时候才使用，比如表达式“s i n ( x ) + 4 在l a m b d a 演算中记作“+ ( s i nx ) 4 。 l a m b d a 演算中的函数( f u n c t i o n ) 8 如果一个表达式中包含一个变量比如x ，那么就可以形成一个考虑到具体参 数x 和结果之间的关系的表达式。在数学上，函数关系通常用等号连接，如f ( x ) = 3 x ，有时用图示x 一3 x 表示。然而，在l a m b d a 演算中有一个特殊的表记很实用， 它省去了给函数取名的必要，这种记法可扩展到更复杂函数的定义上。在前面的 6 【名词解释】入演算，h t t p ：f s h a r p g r o u p j a v a e y e c o m g r o u p t o p i c 7 1 2 8 7m i c h a e ll s c o t t 著，程序设计语言实践之路l m 】，第2 版，裘宗燕译，北京：电子工业出版社，2 0 0 7 ，6 。 8 a c h i mj u n g ，as h o r ti n t r o d u c t i o nt ot h el a m b d ac a l c u l u s j ，m a r c h1 8 ，2 0 0 4 9 第二章教育信息管理领域语言计算方法基础 上海师范人学硕十学位论文 例子中把表达式“3 x ”记作“木3x ”，把它变成函数只需在其前面加上“入x 即可，这样我们就得到“入x 木3x ”。希腊字母入( l a m b d a ) 的功能在一些程 序设计语言中类似于关键词“f u n c t i o n ”，它告诉读者入后面的变量不是表达式的 一部分，而是作为函数声明的参数。参数后面的“点( ) 引入了函数体。比如 在f # 中： f u nx一 x 术 3 iiil 入x* 3 x 如果需要使用l a m b d a 演算来计算，就需要了解和掌握l a m b d a 求值表达式的基 本规则。l a m b d a 演算的基本规则如下： ( 1 ) 0 【变换 a l p h a - 变换规则，说明的是被绑定变量的名称是不重要的，即可以用任何一 个字符表示。比如说叔x 和k z z 具有相同的含义，表示的是同一个函数。 ( 2 ) p 一消解 如果我们不知道如何计算带有九的表达式时，九术语就会让人摸不着头脑。第 二条规则就是b e t a - 消解，它涉及用实际参数代替形式参数的问题。例如： ( 奴木3x ) 4 _ p 幸34 ( 砜y5 ) ( 叔宰3x ) 一p ( 叔宰3x ) 5 _ p 奉35 我们可以看n b e t a - 消解就是在函数体中形式参数的文本被提供的实际参数 替代了。 此外，有一个算法用户计算范式，不断地把最左边的形式参数替换为实际参 数，直到无法再作任何可能的消解为止。这个算法当且仅当l a m b d a 表达式存在 一个范式时才会停止。 2 1 3 上下文无关文法c f g 文法概念的形式化，最早是由语言学家在研究自然语言的理解时完成的。当 时，他们不但关心句子( 如怎样能够准确的判断给定语言的句子) ，还关心对句 子特征的描述。因此，形式文法对语言来说是很重要的。例如，它可以帮助提取 文章的摘要、自动完成对文稿的校对与更改等等。下面，我们来研究文法可以清 1 0 上海师范人学硕十学何论文第二章教育信息管理领域语言计算方法基础 楚描述语言的哪些语法特征。 搞研究一般是从特殊到一般，从简单到复杂。首先看下面的简单巨型。 ( 1 ) 生活是平淡的。 ( 2 ) 中国是发展中国家。 ( 3 ) 上海举办2 0 1 0 年世博会。 ( 4 ) 创新引领潮流。 ( 5 ) 性格决定命运。 ( 6 ) 世界之窗是一种浏览器。 我们可以看到，这些句子暗含共同的模式。首先指出对象是什么，然后说该 对象怎么样。通常，对象是一个“名词短语”，而“对象怎么样”则是一个“动 词短语”。显然，表示“某对象”的“名词短语”和表示“怎么样”的“动词短 语”是一类字符串，此处为了区分，将它们用尖括号括起来： 、 。照这样来说，上面6 个句子的主体结构就是 另外，整个句子最后是一个句号“。”，为了统一起见，用 表示，那么6 个的句子的结构就变成： 如果把6 个句子都分成3 个部分，则这3 个部分表示的集合分别是： = 生活，中国，上海，创新，性格，世界之窗) = 是平淡的，是发展中国家，举办2 0 1 0 年世博会，引领潮流， 决定命运，是一种浏览器 = 。) 上述6 个句子都是从这三个部分的集合中各抽取一个“元素”所组成的。除 了上面6 个句子外，我们还可以从 、 和 这三个部分 所对应的集合中分别抽取不同的元素来构成其他的句子。例如，从 中抽取元素“创新 ，从 中抽取元素“是一种浏览器”，再从 集合中取出唯一的元素“。”，就可以构成下列的句子： 创新是一种浏览器。 同样可以得到： 第二章教育信息管理领域语言计算方法基础上海师范人学硕十学位论文 中国是举办2 0 1 0 年世博会。 世界之窗决定命运。 上海引领潮流。 虽然这几个句子的意义不符合常理，但是它们确实是满足句子结构要求的。 即语法合理而语义不合理。如果将 、 和 这三个部分 分别看成是语言，按照语言乘积的定义， 也是一种 语言，这个语言有i i ii i = 6 x 6 x l = 3 6 个句子。 通过上面的句子发现， 可以是 也可以是 如果加上 集合中出现的“名词短语， 可被扩充为： = 生活，中国，上海，创新，性格，世界之窗，发展中国家，潮 流，2 0 1 0 年世博会，命运，一种浏览器) = 是，举办，引领，决定) = 平淡的) 这里暂且把 整体称为 。 为了简便起见，将“a 可以是p 表示为0 【一p 则上述描述可改写为 一 一 一 一是 一引领 一决定 一举办 一平淡的 上海师范人学硕士学何论文第二章教育信息管理领域语言计算方法基础 一生活 一中国 一上海 一创新 一性格 一世界之窗 一发展中国家 一潮流 一2 0 1 0 年世博会 一命运 一一种浏览器 一。 使用上述这些“规则 ，可以得到一系列的句子。例如，可以按照如下过程， 从 开始，最后得到句子“创新引领潮流。 由于， 一 所以，用 替换 由于， 一创新 所以，可以将“ ”中的 换成“创新”， 从而得到 创新 因为， 一 所以，可以将“生活 中的 换成 从而得到 创新 因为， 一引领 第二章教育信息管理领域语言计算方法基础上海师范火学硕士学位论文 名词短毒、妄：_ 、句号名词短语动词短语 句号 创乙动手词语 上海师范人学硕十学位论文第二章教育信息管理领域语言计算方法基础 成一个句子的过程中逐步地被替换，而不在最终的句子中出现。鉴于此，可以称 这些对应于语法范畴的“符号为语法变量，或者叫做非终结符。 ( 2 ) 在形如 的“符号中， 具有特殊的意义：所有的“规 则，都是为了说明 的结构而存在，也即，所定义的就是 。 ( 3 ) 一系列“符号”( 终结符) ，它们是所定义语言的合法句子中将出现的 “符号”，仅仅表示自身，这样的符号成为终结符。 ( 4 ) 所以的“规则”都呈0 【_ b 形式，它们在产生语言的句子的过程中被使 用。这些“规则成为产生式。 其次，可以用这些规则从要定义语言的代表“符号 开始，逐步地对其中带 有“ 的“符号”进行替换，直到最终得到不带有“ ”符号的 行为止。至此，就得到了所定义语言的一个句子。9 从上面的例子中，我们可以得出文法的特点： 文法能清晰地描述程序设计语言的语法构成易于理解。 文法能自动地构造有效的语法分析器，检查源程序是否符合语言规定的语 法形式。 文法定义可以了解程序设计语言的结构，有利于将源程序转化为目标代码，