表压缩技术研究及其应用

《表压缩技术研究及其应用》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、湖南大学毕业设计(论文)第4页HUNANUNIVERSITY毕业设计(论文)设计论文题目：表压缩技术研究及其应用学生姓名：赵斌学生学号：20060810626专业班级：计算机科学与技术06班学院名称：计算机与通信学院指导老师：杨晓波学院院长：李仁发2010年5月26日湖南大学毕业设计(论文)第II页湖南大学毕业设计(论文)第II页表压缩技术研究及其应用摘要随着软件、多媒体和网络等技术迅猛发展，系统数据量越来越大，给数据的存储、传输以及有效获取带来了严重阻碍。在现代编译器构造过程中，词法分析和语法分析都是表驱动的。为提高软件生成率，编译器的构造通常采用自动工具

2、辅助开发，所产生的表通常为大稀疏矩阵，造成了存储空间的大量浪费，Ada/CS的LL(1)文法为例，其数组形式分析表大约有10000个条目，但其中只有10％左右的非出错条目[1]。本文首先简要地介绍了编译器构造中的两个常用工具Flex与Bison的使用，然后探讨了数据压缩的原理及其应用，接着研究了稀疏矩阵的几种压缩存储算法，详细介绍了词法分析和语法分析的过程，再分别采用三元组和哈希表的方法对词法分析和语法分析过程中生成的表进行了压缩存储，并实验了几组不同的数据，得出了稀疏因子与压缩比的关系。关键词：压缩；稀疏矩阵；词法分析；语法分析；三元组；哈希表湖南大学毕业

3、设计(论文)第II页ThestudyandapplicationofthetablecompressiontechnologyAbstractWiththerapiddevelopmentoftechnologyofsoftware,multimediaandnetwork,theamountofdatainsystemshasbeenincreasing,whichbringsaboutaseriousprobleminstorage,transmission,andeffectiveacquisitionofdata.Inthecourseofmoder

4、ncompilerconstruction,Lexicalanalysisandsyntaxanalysisaretable-driven.Toimprovethesoftwareproductivity,compilersareusuallybuiltupbyautomatictools.Tablesgeneratedbytoolsaretypicallylargesparsematrices,resultinginsubstantialwasteofstoragespace.TaketheAda/CSLL(1)grammarasanexample,the

5、reareabout10000entriesinitstable,amongwhichonly10%arenon-errorentries.ThispaperbrieflyintroducestwocommontoolsFlexandBisonanddemonstrateshowtousethemtoconstructcompilers.Thendatacompressionanditsapplicationarediscussed.Afterthat,severalsparsematrixcompressionalgorithmsarepresented.

6、Itgivesthedetailedintroductionabouttheprocessoflexicalanalysisandsyntaxanalysisandrealizesthecompressionstorageofthetablegeneratedintheprocessoflexicalanalysisandsyntaxanalysisbyusingthetriplesandthehashtable,andwegetseveralsetsofexperimentaldata,obtainedtherelationshipbetweenspars

7、efactorandcompressionratio.Keywords:compression;sparsematrix；lexicalanalysis；syntaxanalysis；triples；hashtable湖南大学毕业设计(论文)第II页目录1绪论11.1概述11.2国内外研究状况11.3课题研究方法21.4论文构成及研究内容32Flex和Bison简介及应用42.1Flex介绍42.1.1正则表达式的Lex约定42.1.2Flex输入文件的格式52.2Bison62.2.1Bison介绍62.2.2Bison和Flex的结合73数据压缩83.1

8、数据压缩的基本原理83.2数据压缩技术的应用94稀疏