（计算机应用技术专业论文）形式化语言在报表系统中的研究和应用(1).pdf

形式化语台在报表系统巾的研究与应用学位 毕朴论 义 r e s e a r c h a n d a p p l i c a t i o n o f f o r m a l l a n g u a g e i n r e p o r t s y s t e ms ab s t r a c t i n f o r m a t i o n s y s t e m s h a v e a n i n c r e a s i n g e f f e c t o nm a n a g e me n t o f g o v e r n m e n t s a n d e n t e r p r i s e s , i n w h i c h r e p o r t p l a y s a s i g n i fi c a n t t h e m a i n t a s k s o f i n f o r m a t i o n s y s t e m s a r e a s f o l lo w s : c o m p l e t i n g t h e t r a n s a c t i o n p r o c e s s i n g o n t h e o p e r a t i o n s a n d a f f o r d i n g c o m p r e h e n s i v e a n d t i m e l y i n f o r m a t i o n s e r v i c e s f o r t h e m a n a g e r s a n d d e c i s i o n - m a k e r s . h o w t o p u r p o s e f u l l y p r o c e s s l o t s o f d a t a i n t h e d a t a b a s e i s a h a r d n u t t o c r a c k i n t h e i n f o r m a t i o n s y s t e m s . r e p o rt i s a n i m p o r t a n t m e a n s t o s o lv e i t . r e p o r t e m b o d i e s t h e v a l u e o f i n f o r m a t i o n s y s t e ms . n o w a d a y s , r e p o rt - s y s t e m s o f d o m e s t i c a n d o v e r s e a s s t i l l h a v e s o m e p r o b l e m s in t h e a p p l i c a t i o n o f t h e i n t e rn a l r e v e n u e s y s t e m s . t o s o l v e t h o s e p r o b l e m s , t h e e l i a n k - g e n e r a l - r e p o rt - s y s t e m i s d e v e l o p e d . i t w o r k s b y s e p a r a t i n g t h e f o r m a t a n d d a t a o f r e p o rt . n a m e l y , i t p r o v i d e s t h e d e f i n i t i o n a n d m a i n t e n a n c e o f r e p o rt s f o r m a t i n o r d e r t o p r o d u c e i t s f r a m e w o r k f o r t h e u s e r s . a t t h e s a m e t i m e , i t c a n a u t o m a t i c a l l y g a t h e r a n d p r o c e s s t h e d a t a o f d a t a b a s e i n t h e li g h t o f t h e c a l c u l a t i o n r u l e s , t h e r e b y g e n e r a t e t h e d a t a o f r e p o rt . t h e n , i t p u t s t o g e t h e r t h e f r a m e w o r k a n d d a t a o f t h e r e p o rt . a t l a s t , t h e r e p o r t c o m e s i n t o b e i n g . t h e s y s t e m i s r e s e a r c h e d a n d d e v e lo p e d f o r t h e s a k e o f r e a l i z i n g t h e f u n c t i o n a n d p e r f o r m a n c e o f g e n e r a l - r e p o r t a n d f u l f i l l i n g t h e o p e r a t i o n s r e q u i r e m e n t o f a c c o u n t i n g a n d s t a t i s t i c s . i n t h i s t h e s i s , t h e f o l l o w i n g i s s u e s o f t h e e l i a n k - g e n e r a l - r e p o r t - s y s t e m a r e r e s e a r c h e d : t h e e b n f ( e x t e n d e d b a c k u s - n a u r f o r m ) d e f i n i t i o n o f t h i s s y s t e m , l e x i c a l a n a l y s i s , s y n t a x a n a l y s i s , t h e s e m a n t i c a n a l y s i s o f a s s i g n m e n t - s t a t e m e n t s a n d a u d i t i n g - s t a t e m e n t s a n d b a l a n c e - r u l e s , t h e c a l c u l a t i o n o f a s s i g n m e n t - s t a t e me n t s a n d a u d i t i n g - s t a t e m e n t s , k e e p i n g t h e r e p o rt b a l a n c e a n d e r r o r - e q u i l i b r i u m a f t e r i t i s r o u n d e d o f f . k e y w o r d s : f o r m a l l a n g u a g e s ; l e x i c a l a n a l y s i s ; s y n t a x a n a l y s i s ; i n t e r m e d i a t e l a n g u a g e ; e r r o r - e q u i l i b r i u m 形式化语言在报表系统中的研究与应用上海师范大学硕士学位论文 1 概述 1 . 1业务背景和功能需求 信息系统在政府、 企业管理中的作用越来越大， 报表在信息系统中占 有重要 地位。 会计报表、 会计分析、 统计报表、 统计分析都涉及到报表定义、 报表运行、 报表数据管理、 报表分析。 研究和开发本系统是为了: 实现通用报表的功能和性 能，满足会计、统计的业务需求。 信息系统的任务主要有: 完成业务上的事务处理， 为管理者和决策者提供全 面及时的信息服务。 如何有针对性地加工数据库中的大量数据， 是信息系统的难 题， 报表是解决这个难题的重要手段。 报表处理是信息系统的重要问题， 在技术 实现上有一定的难度。 报表体现信息系统的价值。 目 前国内外的报表系统在国内 税务系统的应用存在着一些问题。为了解决这些问题，开发了 e l i a n k通用报表 系统。其主要特性有: 提供简单高效的 报表数据抽取运算语言，该语言支持中 文对象引用。一 般情况，十至三十条语句能完成一张复杂报表。 在o r a c l e 8 数据库基础上， 提供了配套的、 成倍提高报表运行速度的 解决 方案。 系统采用三层结构，增加了它的通用性、安全性和可维护性。并提供报 表系统的网络调用接口，为报表系统嵌入到其它应用中提供了可能和方便。 解决了 其他报表系统未能完全成功处理的舍位平衡误差均衡化问题， 提 供报表手工录入、重新运算和报表审核功能. 有配套的、强大的报表管理、查询和分析功能。 报表有复杂性、 多样性。 如快报; 单栏、 多栏报表; 折半、 折三、多折报表; 定长、不定长报表;开口、不开口 报表;分页报表等多种形式。 报表数据的提取、 引用。 报表内 数据和报表间数据的平衡关系; 报表的舍位 平衡及误差均衡化;报表数据导入和导出等构成报表数据关系的各个要素。 该报表系统的目 的是在税务电 子化的背景下， 采用三层体系结构， 为o r a c l e , s 沙a s e , f o x p r o 等数据库环境提供一套完整的 报表解决方案。 第 t 页 形式化语言在报表系统中的研究与应用上海师范大学硕士学位论文 报表系统的功能需求有: 生成和展现固定报表:具有定义固定报表甲 栏、丙栏、表头、附加项、公 式 ( 计算公式、校验公式)等功能:生成的报表可转化为h t ml , e x c e l 格式， 其格式可保存，作为模板使用; 报表可以c/ s , we b 两种方式生成; 报表平台 能连接不同数据源; 报表的边框、 单元格等元素可定制; 报表内容能以图形方式 展现， 展现方式 ( 颜色、坐标等) 可定制;报表的时间跨度可定制。 生成自 定义报表: 可从不同 业务模块、 不同的表选取内 容生成报表; 可将 多张报表合并成为一张新的报表; 可通过计算生成报表新的行栏; 定义报表的操 作简单、 直观、 易懂; 报表格式保存、图形展现、 报表格式元素等的要求与固定 报表相似:可对报表中规定的字段进行数据抽取。 报表的we b发布: we b页面诸元素可定制;分离报表的发布权限和删除 权限;在报表发布的位置旁留有批示和评论空间:报表在 we b页面上的排列次 序可定制;报表以we b s e r v e r 与报表服务器分开的方式发布;报表的发布可按 部门 分类; 报表发布提供签发方式; 提供带智能卡接口的用户登陆方式。 报表校验: 表内 校验、 表间 校验: 定制舍入的粒度: 当校验条件不满足时， 有直观的报警方式; 报表内容修改后，自 动检验是否满足校验条件: 能保存和维 护校验关系;校验在报表生成之前进行，若不满足校验条件，不能生成报表。 定时按计划生成和发布报表:定时自 动生成报表;生成后自 动发布。 权限 设置: 权限 分为g r o u p 和u s e r 两组: 应用系统模块 权限 设置; 数据 源权限设置可定义到字段级; 生成报表权限设置 原始报表只能生成和发布， 不 能修改， 其他报表可以生成和修改) ; 签发权限( 有些报表需经过签发才能发布) ; 报表查询权限由生成报表的人定义。 日志: 记录生成报表的时间、 所用时间、 操作员: 报表的每次发布、 删除、 修改、签发 ( 包括签发人，时间， 报表名) ;及其报表生成成功与否 若是失败， 并记录其原因) 。 自 动平表功能。 报表平台 可扩展性: 报表有开 放的 接口 ， 与多 种数据源兼容( 由o d b c 支 持) 。 支持并行数据处理 ( 由o r a c l e支持) ;报表平台与多种操作系统、 we b 第 2页 形式化语言在报表系统中的研究与应用卜 海师范大学硕( 学位论文 s e r v e 兼容;支持数据仓库产品;支持访问 文本数据的能力:提供灵活的作业调 度:具有动态生成图形能力。 1 . 2 需求分析 1 . 2 . 1 会计报表 会计报表是用特定表达方式，以会计账簿资料为主要依据，以货币为计量单 位， 通过 1 系列指标， 集中反映会计报告期内资金活动情况的书面报告。 各核算 单位必须严格按规定时间向上级税务机关编报各种会计报表， 县级以上各级税务 机关应及时对下属单位上报的报表进行审核， 将同 类报表加以 汇总， 并编报汇总 报表。 税务会计报表根据反映内容不同， 可分为: 旬报表。又称电旬报，以 旬为 报告期， 用远程通信方式向上级税务机关上报本旬各项税款入库情况的报表。 j决报表。 又称电月报，以月为报告期， 用远程通信方式向上级税务机关上报各税 种和有关重点项目 入库情况的报表。 资金平衡表。以月为报告期， 反映资金运 动情况的报表。 应征税金明细报表。以年、 月为报告期， 反映应征税款累计情 况的报表。 入库税金明细报表。 以年、 月为报告期， 反映税款入库情况的报表。 在途税金余额明细报表。以年、月为报告期，反映期末实有在途税款的报表。 欠缴税金明细报表。以年、月为报告期，反映期末实有欠缴税款情况的报表。 减免税金明细报表。以年、月为报告期，反映期末累计减免税金情况的报表。 提退税金明细报表。以年、月为报告期，反映期末累计提退税金情况的报表。 1 . 2 . 2 会计分析 会计分析以会计核算资料为主要依据， 用科学的分析方法， 对资金运动过程 及其结果进行综合、 全面研究和评价，揭示工作成绩、问 题，分析原因，并提出 改进措施，以加强管理，是核算的延续。 积极开展会计分析， 充分发挥会计的反 映和 f 控制作用。 税务会计分析的主要内容: 应征分析。 把分析期内实现的总量，分地区、税种与 税基及应征税金总额 第 3灾 形式化语言在报表系统中的研究与应用上海师范大学硕上学位论文 对比，分析趋势。 欠缴税金分析。 把分析期内 应缴而未缴的税款， 分地区、 税种、 类型， 选 择纳税大户与税基、 欠缴税金总额及应征税金总额对比， 通过分析增长率、比重 率和应征欠款率， 掌握欠缴税金各构成部分的变动情况及它们对欠缴税金总量的 影响程度，为及时控制和清理欠税提供依据。 减免税金分析。 对分析期内的减免税款， 分地区、 税种及减免性质与税基、 减免总额及应征税金总额对比， 掌握减免税金的变动趋势和影响减免税金变动的 主要因素。 在途税金分析。按地区，比较在途税金总额与应征税金总额，并结合税金 在途时间， 对分析期内的在途税金进行分析， 了解在途税金是否正常， 是否有占 压税款现象，以便采取措施，加快税金入库速度。 提退税金分析。 分析各地区、各税种和各种不同性质的提退税金的变化情 况、 各构成部分对提退税金总量的影响程度以及提退税金占 应征税金的比重变化 情况。 入库税金分析。 入库税金是税金运动的终点， 是应征税金减税金运动过程 中发生的减免税金、欠缴税金、 待解税金、 损失税金、 在途税金和提退税金的所 得余额。 保证各项应征税款及时足额入库，是管理工作的中心任务。 所以， 对入 库税金进行分析， 实质上是对税金运动各环节的综合分析， 是税务会计分析的核 心。它在评价税务管理工作和分析税收计划完成情况等方面有极其重要的意义。 入库税金分析除按地区、 按税种进行分析外， 还需进行因素分析， 即将应征税金、 减免税金等各种税金作为影响入库税金的因素， 分别分析每个因素对入库税金影 响的方向与程度， 从而找出影响入库税金变化的主要原因. 此外， 常常把它与在 途税金比较，以分析在途税金的入库速度。 1 . 2 . 3 统计报表 税务统计报表按照统一规定的表格、 项目、口 径收集统计资料， 是税务机关 搜集和整理统计资料的主要手段。 税务统计报表的种类有: 按统计时间不同， 分 为月报、 季报和年报: 按统计范围不同， 分为税源统计报表、 收入统计报表和税 政统计报表; 按编制方式不同，分为原始统计报表 ( 即直接依据原始凭证或统计 第 a页 形式化语台 在报表系统中的研究i, 应用上 海师范人学硕 卜 学位论文 台账而产生的报表) 和汇总统计报表( 即依据各万 属单位报送的统计报表汇总编 制的报表) ;按报送方式不同，分为书面报表和电子报表。 统计 一 报表要求:资料完整:报表必须按规定的指标，全面、完整地编报 不得漏填项目。 数字准确: 报表必须依据原始资料， 按规定方法准确计算，如 实填报， 不得弄虚作假; 口径统一: 报表必须按统一规定的口径编报，不得随 意更改。 报送及时: 报表必须在规定的时间向 上级单位报送，以便上级单位统 一 汇总。 统计报表的填列依据: 各种原始统计报表应根据统计台账， 并结合统计原始 凭证或统计汇总单进行计算填列; 各汇总统计报表应根据其下属单位编报的同类 统计报表的同类项日的数据汇总填列。 1 . 2 . 4 统计分析 统计分析是运用统计资料对统计内容进行概括、评价、推断、预测的过程， 也是通过统计资料发现问题、揭示矛盾、总结原因并提出建议措施的过程。 税务统计分析的内容: 分析收入进度、 变化情况及发展趋势; 分析政策的执 行情况、实施效果及存在的问题:分析征管工作的深度、 广度、 质量以及纳税人 的态度和依法纳税程度;分析税源增减变化情况和发展趋势。 税务统计分析主要方法: 对比分析法: 将相互联系的指标进行对比， 计算 相对数。 平均分析法: 将同一性质的某类指标数据综合平均， 计算平均数， 分 析其总体情况。 状态分析法: 将某类指标按照时间序列进行分析， 研究税收在 不同时期的发展水下。 因素分析法: 计算某类指标的分项数据对指标总量的影 响程度，从而得到分项指标对总量指标的作用方向、大小，便于 抓住主要问题。 相关分析法。计算性质不同却相互联系的指标的相对值，了 解其相互关系。 统计分析步骤: 选题。 统计分析的题目 必须根据各个时 一 期工 作的重点和需 要确定， 选题要目的明确、内容清晰、 针对性强。 搜集和整理统计资料， 根据分 析的内容和目的， 确定搜集的资料的内容、口径和来源， 并对搜集的资料运用科 学方法进行分类和综合。 计算和研究。 运用统计分析方法， 对掌握的统计资料 进行计算剖析，透过表象，发现问题，抓住实质。 做出结论，提出建议。 根 据分析结果，做出实事求是的结论，并提出建议和措施。 第 5页 形式化语台 在报表系统中的研究与应用 ! 海师范大学硕 卜 学位论文 浏览方式为客户提供服务。包括: 记载报表处理日志:根据系统设置的 日志记录级别，记载报表系统的运行日志， 提供六 w ( wh o , wh e n , wh e r e , wh a t , h o w, w h y )日 志记 录，日 志记 录级别有正 常运行、系统管理、现场维护、 程序调试等 四种级别。 报表安全管理: 根据角色进行安全管 理服务，提供系统版本的安全管理。 报表计划定时生成和发布。 e l i a n k通用报表系统的逻辑架构( 如图 2 -2 所示) 图2 - 2 e l i a n k 通用报表系 统逻盯 架构 2 . 4 e l i a n k通用报表系统技术规格 环境要求: 标准t c p / i p 网络; 标准we b服务器; 标准i e 4以上浏览器。 功能指标: 任意单元格、任意行或栏及全表数据的采集定义; 表内表间的数据调用、审核及报表汇总运算: 标准的报表规则定义语合; 报表进行四舍五入后，表内单元格的误差范围小于等于1 ; 面向业务处理的属性定义方式;基础业务数据可以来自于 o r a c l e , s y b a s e , s q l s e r v e r 等数据 库; 报表 数据结果能以e x c e l , h t m l , d b f , o r a c l e 等方式输出; 开放的s d k包; 报表内容的图形处理方式; 六 w 四l e v e l 日志管理文件 第 8r , 形式化语言 在报表系统中的研究与应用上海师范大学硕士学位论文 完全基于we b浏览方式的用户界面; 自主知识产权。 2 . 5主要功能 该系统是一个通用报表系统， 适用于税务征收管理中常用的报表处理， 产生 各类统计分析报表和统计台帐。 主要功能包括报表数据的存储、 查询; 数据关系 的检查; 报表格式的定义以 及报表数据的计算等。 采用报表格式与报表数据分离 的设计思想， 即通过定义和维护报表格式为用户产生报表框架; 根据运算规则自 动采集和加工数据库中的数据， 产生报表数据; 拼装框架、 数据; 最终形成报表。 2 . 5 . 1 报表数据的数据结构 用报表代码区分不同类型的报表， 用所属期表示报表时间， 用部门代码表示 报表编报部门 ( 指税务所、业务科室和市局等数据统计单位) 。因此，报表有三 个属性: i d :报表代码 d a t e : 所属时期 d e p t :编报部门 ( 或税务局、所) 报表由数据和框架组合而成。 报表数据由若干行或栏数据组成， 每个数据元 素属于一个特定行和一个特定栏。 即每个数据元素可由 其所在的行、 栏的位置确 定。 分别对行、 栏编号， 设行、栏编号从1 开始，逐一递增。 报表单元格可用它 在报表中所处的行号、栏号表示: h行号l栏号 ( 或列号) 报表框架由上表题、栏表题、纵表题、下表题和表层注释区五个部分组成。 拼装报表框架和数据就构成一张完整的 报表。 1 ) 报表定义 报表定义部分的数据结构由报表描述、 表头表尾定义、 备注区定义、 报表行 定义、报表栏定义、报表属性定义等组成。 2 ) 报表规则定义 报表数据的抽取和引用由报表规则号、报表运算规则等组成。 第 9页 形式化语言在报表系统中的研究与 应用l 海师范人学硕 卜 学位论文 3 ) 报表数据审核定义 报表数据审核由表内审核、表间审核等组成。 4 ) 报表数据的存放 报表数据的运行和存放由 报表参数、 报表数据仓库、 报表运行缓冲区、 动态 表头、报表其他定义等组成。 2 . 5 . 2 报表系统的功能结构 报表系统在功能上主要包括: 报表定义、 报表运行、 报表数据管理和报表分 析四大部分。 i ) 报表定义 报表定义是由技术人员根据所需格式， 定义报表各部分， 得到完整的表格框 架和业务关系。包括以下几个方面: 报表定义:栏标题定义、行标题定义、表头表尾定义、备注区定义、属性定 义。 运算规则: 业务人员用产生报表数据的计算语一言 按自己的要求定义报表数据 的计算。 审核规则: 为确保产生的报表数据的正确性， 利用数据间的关系对表内或表 间的数据进行检查或调整。 动态参数:进行报表的动态参数定义。 增加:创建新的表格。 复制: 把一个表有关栏标题、 行标题、 表头、 表尾、 备注、 属性、 运算规则、 审核规则、动态参数等的定义复制到另一个表。 册 1 除:删除表中部分定义。 2 ) 报表运行 业务人员根据数据间的逻辑关系， 进行计算或检查的过程， 有: 动态参数处 理 ( 在相应的表中查询、增加、修改动态参数) 、报表运算 ( 输入编报日期和编 报部门， 根据运算规则， 产生报表数据) 及报表审核( 输入编报日期和编报部门， 根据审核规则，对报表数据进行审核) 。 3 )报表数据管理 第 1 0页 形式化语 言 1 1 报表系统中的研究i j ) ,v 用 _ 海师范大学硕 卜 学位论文 包括:列出报表清单 ( 根据报表代码查询报表) 、 删除数据 ( 根据报表代码、 编报日期及编报部门删除数据) 、数据录入和报表输出。 4 ) 报表分析 报表具有以下特征: 报表是对数据库中数据的再加工; 报表数据一般是 统计数据; 报表是用于管理和决策的; 报表是分层次的、 相互关联的; 报 表数据来源一般都很复杂; 报表体现管理。 报表数据是企业非常有价值的数据。 因此，提供对报表进行分析的功能尤其重要。 对报表数据进行分析和查询， 包括以下功能: 报表数据查询; 报表汇总: 报 表数据图形显示;报表数据分析;打印等。 第 t i k 形式化语占 在报表系统中的研究卜 。 应用 海师范人学硕 _ 学位论文 3规则定义形式化语言 3 . 1关键字 本系统的关键字如表3 - 1 所示。 表3 - 1本系统的关键字 符号表示的意义符号 表示的意义 t或 t表头标识$动态参数 h或 h行标识 = 甘 文字引用 l或 1栏标识 q t n数据抽取标记 行栏区间符 + 加号或正号 ，或，分隔符减号或负号 寿 表示下限 幸 乘号或全表标识符 表示应用字段/除号 n 字段域或强制符 ( )左、右括号 :或:属性符 【 行栏数标记 赋值符或等号 != 不等于 =# 表格引用符 大于 = = i i i i i i i 表引用语句) : := 表格引 用符) : :二 属性) ; : 二 ( i ) ; : 二 : :二 表达式 ) 表头定义语句卜: 二 ( i ) 重新计算语句) : :“ 区间定位) 表达式) : :二 1 0 l 引钊= ! 二 : :=八 : := = * 第 玲 贝 形式化语言 t i 报表系统中的研究与应用 一 海师范人学硕 ) 学位论义 : :二= := 0 川 2 13 14 15 (6 17 18 19 : : 二 受 : : = 1 12 13 14 15 16 17 18 19 : : 二 无 符号 整 数 习 行栏数) ; : 二 分隔符 ) ; :=一 ; := ， : 二 ( ) : ; : 二 字符串 ) 分隔符) i k 数字 )仁字符串 1 : :二 所有汉字 : : = a lb (c ld l . . . ix iy lz la ib ic id i . . . ix (y (z : : = 1 ( 选择语句 : : 二 s e l e c t f r o m w h e r e : : 二 * 卜 属性变量 : :二 条件语句 ) ; : - 逻辑非运算符 ( ) 第 1 4页 形式化语 言在报表系统中的研究与应用 _ 海帅范大学硕 1 _ 学位论文 ) : : = n o t in o t jn o t in o t jn o t in o t in o t in o t : : = a n d ia n d la n d la n d la n d ia n d ia n d la n d : : = o r io r io r o r : : = 笼( + 卜 ) 1( 表内 引 用 i 1 = = ( n 卜区间定位 卜右括号 ) : : = b b ib b ib b ib b := b lb : : 二 ( i ) : := r ir : : 一 ( ) : : = mim : : = $m 1 12 13 ) 一 ) 14 ) : := : := : : = t it 3 . 2 . 2 b n f 范式的示例 例如文字语句: h 1 = ! s e l e c t s u m ( s h u i e ) f r o m k u i t j w h e r e r u k r q /b 是这样 种结 构 : a 二 ( v , u v , ) 且 至 少 含 有 一 个 非 终 结 符， 而10 二 ( v ,i u v , ) ， 则 文 法g是 一个0 型文法。 1 型 文 法 : 设 g 一 ( v x v r , p , s ) ， 如 果p 的 每 个 产 生 式 a - ,8 均 满 足 a a ， 其中a 和刀 都是非终结符， a 是终结符，则文法g 是一 个3 型文法或正 规文法。 1 型文法又称 七 下文有关文法。对非终结符进行替换时务必考虑_ l 下文，月 一般不允许替换成空串 。 2 型文法又称上下文无关文法，对非终结符进行替换时不必考虑 h下 文。 第 ! 7灭 形式化语台钓报表系统中的研究与应用! 一 海师范人学硕 1 学位论文 3 型文法又称右线性文法。 由于这类文法等价于正规式， 所以也称正规文法。 对于0 型文法，己经证明其识别问题是无解的。一般情况下，不可能在有限 的步骤内判别某个输入串是否为0 型文法的句子( 某些特殊的0 型文法可能有解) ; 对于1 型文法，其句子都是可识别的，不过所有己知的分析算法是指数级的时间 复杂度: 2 型文法的句子都是可判别的， 许多2 型文法的子集可以用线性时间复杂 度的算法进行分析:3 型文法的句子可用等价的有限状态自 动机在线性时间复杂 度之内识别。 形式语言的成果为我们处理实际问题提供了普遍性的参考， 在设计 文法时，应该充分考虑到分析算法的有效实现。 本系统定义的e b n f 范式是上下文无关文法，可转换成正规文法。 3 . 4 词法分析 l司 法分析的功能是识别源输入中的单词符n5， 将其输入字符串转换成语义相 关 符号 的 序列 18 1 。 为了 有效地实 现所要 求的 功能， 词 法分析 程序需要完 成以卜 几 件 卜 作: 每个单词 预处理输入串， 滤掉空白符、 回车符、 注释等编辑性字符: 识别出 : 将单词转换成内部格式， 同时利用词法分析自 动机检查单词是否符 合词法要求;确定单词的类型。 执行词法分析的程序称为词法分析器或扫描器。 使用状态转换图是设计词法分析程序的一 种较好方法。状态转换图是有向 图。在该图中，结点表示状态， 结点之间用有向弧上 的标记 ( 符号) 表示在当前 结点状态f 可能出现的输入符号或符号类，而状态则由该结点转换到下一结点。 一张状态转换图包含若干个状态 ( 即若干个结点) ，其中至少有一个初态，若干 个终态 ( 可能是。 个。终态用双圆圈表示) 。 本系统根据面向对象的程序设计思想， 用一个类封装了词法分析自 动机的功 能。 词法分析表是该类的私有静态成员变量。 该变量是一 个结构体数组， 包括一 二 个变量:当前状态值， 输入字符， 新状态值。因此， 词法分析表记 录了整个问法 分析的状态图。 修改词法分析表的内容， 就可以构造适应不同解释程序的词法分 析自 动机，实现高效率的软件重用和扩展性。 词法分析自 动机内部数据流图如图3 - 1 所示。单词扫描模块从输入串中得到 单词; 单词内 部表达转换模块将该单词转换成内部表示的整型值数组; d f a 模块 第 1 8贞 形式化语 a fl报表系统巾的研究与应用 海师范人学硕卜 t位论义 接受单词的内部表示，得到终 态值;单词类型值求取模块以 终态值和单词的第一个符号为 依据求得单词的类型值，最后 得到单词及其类型值。 输入串 词法分析模块 1i% 刁;川州训j| 蔚i acai1diva 字祠 匕全 至 _ _ 一 串 单 . 词 类型 值求 取 单l 司 类 找 u 终态值 单词扫描 3 . 4 . 1 有限自 动机 图3 一 i词 法分析模块图 有限自 动机是一种识别装 置，能准确地识别正规集，为词法分析程序的构造提供了方法和工具。 有限自 动机是具有离散输入输出系统的数学模型。它有有限个内部状态， 系统可根据当前所处的状态和面临的输入字 符决定后继行为。 其当前状态包含已 输入处理 的信息。 有限自动机模型如图3 - 2 所示， 包括三个 状态:初始状态、中间状态和终止状态。 输入带 a 邑i 少下 一 二 状态变换 一秒， 一怪 经 卸 戒 在初始状态下 元，准备读入第一 读头指向输入带的最左单 图3 一 21 ; 限白 动机杖型 个字符。 然后每读入一个字符， 从当前状态进入下状态。当 读头读完所有字钧后， 状态进入终态， 则输入带上的输入串被接受;否则， 输入 串有错。 说明:终止状态可有若干个，而初始状态一般只有 一 个。 可用状态转换图表示状态变换。 定义2 确定有限自 动机( u f a ) 是五元组:m= ( s , e , b , s n , f ) 其中 o o s 是一个有穷集，它的每个元素为一个状态; e又 称输入符号表，是一个有穷符号表，它的每个元素为一个输入符; os 是从s k y- 到5 的映像，又称转换函数; s , e s 是唯一的 初态; of c : s，是一个终态集。 第 1 9贞 形式化语 6报表系统中的3 ia 究与 应用 几 海师范人学倾 学位论文 一个d f a 可表示成一张确定的状态转换图。若d f a m含有m 个状态结点和n 个输入字符，则状态图中有m 个状态结点，每个结点最多有n 条有向弧与其他结 点相连接， 每条弧用i中的一个不同输入字符作为标记， 图中含有唯 一 的初态结 点和若于 ( 可以是0 个)终态结点。 定义3 非确定有限自 动机( n f a ) 是五元组:n= ( s , e , 6 , s o , f ) 其中 、 中的s .艺同上; os 是一 个从s x 艺 到 s 的子集的映 像， 即5 : s x 艺 - ) . 2 ; .s , c s ， 是一个非 空初 态集; fcs，是一个终态集 ( 可空) 。 一个n f a 可以表示成如下形式的状态转换图:图中有m 个状态结点，撼个结 点有若干条有向弧与 其他结点相连接，每条弧用了 中的一个输入字符 ( 不要求 是不同的输入字符，也可以为空字符二 )作为标记，图中至少含有一个初态结点 与若 于 个 ( 可以是0 个)终态结点。 3 . 4 . 2 确定有限自 动机与非确定有限自 动机的转换 对于艺 中的仟何字符串t ，若存在一条从初态结点到某终态结点的通路 且这条通路上所有弧的标记符连接成的字符串等于t ， 则称t 可为d f a m所接受( 识 别) 。 对于艺 中的任何字符串t ，若存在一条从某一初态结点到某一终结点的通 路，且这条通路上 所有弧的标记符连接成的字符串 ( 忽略那些标记为二 的弧) 等 于t ，则称t 可为n f a n所接受 ( 识别) 。 由有限自 动机理论:设l 为一个由不确定的有限自 动机接受的集合，则存在 一个接受l 的确定的有限自 动机。因此，对于不确定有限自 动机n， 存在一个确 定的自 动机m,使得l ( n ) =l ( m ) o d f a . n f a 可用三种方法表示; 状态转换函 数法、 状态转换矩阵法、 状态转 换图法。 第 2 0贝 形式化语言在报表系统中的研究与应用上海师范大学硕 卜 学位论文 在d f a 的矩阵表示中， 表项是一个状态，而n f a 的矩阵表示中， 表项可能是 一个状态集合，因此可以用d f a 中的一个状态对应n f a 中的一个状态集合。 该算 法称为子集法，是一种将n f a 转换成接受同样语言的d f a 的算法。 状态集合i 的几个有关运算: 状态集合i 的: 一闭 包，记为二 一 c l o s u r e ( i ) ，定义为一个状态集合，表示 状态集合i 中的状态s 经任意条。 弧所能到达的状态的集合。 状态集合i 的 a 弧转换， 记为 m o v e ( i ,a ) ， 定义为 状态集合i e ， 表示所有 那 些可以从i 中的某一状态经过一条a 弧而到达的状态的集合. n f a n 一 ( k , e , f , k o , k , ) ， 若 i 是 k 的 一 个 子 集 ， 可 设 ， 一 卜 i, s 2 ， 二 ， s a , a 是 e 的一个元素， 则m o v e ( i , a ) = f ( s , , a ) v f ( s 2 , a ) v . . . v f ( s ; , a ) a 可用子集法或状态极小化算法将n f a 转换成d f a 9 。可用以 下算法为n f a n = ( k , e , 、 f , k , , k , ) 构造d f a m= ( s , e , s , s o , s , ) ， 使得 l ( n ) = l ( m ) o om的状态集合s 由 k 的一些子集组成。 用 s s 2 , . . . s . 表示s 的元素， 其中 s ; 。 k ( i = 1 ,2 . . . n ) ，并 按某种规则排列; om与n 的输入符号表都是e; 转换函 数s 如 下定 义:5(s, s 2 , . . . , s , , a ) = r , , r 2 ， 一 ， r , 其中 一 c t o s u r e ( m o v e 戈 ss 2 , . . . , s ; j , a ) ) = r , , r z 一， r ; ; .s , = c 一 c l o s u r e ( k q ) 为 m 的 初态 (5 s , = t s ; , s k ， 二 ， s n l ， 其 中 i s , , s k i 二 ， s l e s a ( s i + s , ， 二 ， s n k , ， 护 构造k 的子集的算法如下: 假定所构成的子集族为c, c二 ( t i t , t , ) ,不 i t z , . ， - , t ; 为状态k 的子集。 令: 一 c l o s u r e ( k , ) 为c 中 唯一成员， ( 2 wh i l e ( c中存在尚未被标记的 子集t ) 标记t ; f o r每个输入符号a d o 并且它是未被标记的。 第2 1 页 形式化语台 在报表系统中的研究与应用t _ 海帅范大学硕 i 学位论文 u:= 一 c l o s u r e ( m o v e ( t , a ) ) ; i f u不在c t h e n 将u作为未被标记的子集加在c中 因此， 可先构造词法分析的不确定有限自 动机， 然后通过子集法将n 队转换 成接受同样语言的d f a。 再由d f a 的状态转换图构造相应的转换知阵。 对转换矩 阵中的所有子集重新命名 形成新的转换矩阵。 这就是词法分析表， 是词法分析 的基础。 3 . 4 . 3 确定有限自 动机的化简 有限自 动机的多余状态是指从该自 动机的开始状态出发， 任何输入串也不能 达到的状态。 有限自动机两个状态a与状态b如果满足如 卜 二个条件:一致性条件: 状态a与状态b同时为可接受状态或不可接受状态: 蔓延性条件:对于所有 输入符号， 状态a与状态b必须转换到等价的状态。 则称状态a与状态b 等价。 如果有限自动机中的状态a与状态b是不等价的， 称状态a与状态b是可 区别的。 若有限自 动机中存在等价状态或多余状态， 需要对其进行化简， 去掉等价状 态和多余状态，以达到有限自 动机的最小化。 所谓的有限自 动机的最小化过程是将该自动机分割成一些不相交的子集， 使 任何不同的两个子集中的状态都是可区别的， 而p i 一子集中的任何两个状态都是 等价的。然后，在每 一 个子集中选一个状态，去掉等价状态。 d f a 的最小化的方法有多种，其本质是相同，在最小化之前，先消除多余 的状态，以减少最小化的工作量。本文介绍列表法与分割法。 1 )列表法: 画出状态转换矩阵， 把所有的状态都列举出来， 然后分别对应不同的输入列 出到达的状态， 最后把结果相同的状态合并， 可得到最小化的状态矩阵， 能画出 相应的d f a状态转换图。 第 2 2 页 形式化语 es i 钧报表系统中的研究j ; , ,;i 用 _ 海师范人学硕 学位论文 2 )分割法: 设有限自动机m， 则对m最小化的过程为， 将m的状态集s按以卜 步骤进 行划分: 把 s的终态与 非终态分为两个子集，形成基本划分rl，则i i 中两个不同 子集的状态是可区别。 设 n已 被 划 分 为n 个 子 集， 记i i = i l , 1 2 ， ， i n ， 则 分 属 于 不 同 的 子 集中的状态是可区别的。 检查i ， 能 否进 步划分， 对于i ， 令c一 伙 】 ， 9 2 + ， q 0 ， 若 存在 个 输 入符号a 使得i ; 不 全部 包 含在n的 某一 子 集中， 则 将 按照 步 骤 或 对i 进 行 分解。 设r 的状态s , 与s 2 经a 弧分别达到状态t , 与t 2 ， 而t 、 与t 2 属于n的两个 不同子集，则将r 分成两部分，其中一部分含有s , i l = i s , i s , 。 i