表压缩技术研究分析其应用.doc

HUNAN UNIVERSITY 毕业设计(论文) 设计论文题目： 表压缩技术应用 表压缩技术研究及其应用 摘 要 随着软件、多媒体和网络等技术迅猛发展，系统数据量越来越大，给数据的存储、传输以及有效获取带来了严重阻碍。在现代编译器构造过程中，词法分析和语法分析都是表驱动的。为提高软件生成率，编译器的构造通常采用自动工具辅助开发，所产生的表通常为大稀疏矩阵，造成了存储空间的大量浪费，Ada/CS的LL(1)文法为例，其数组形式分析表大约有10000个条目，但其中只有10％左右的非出错条目[1]。 本文首先简要地介绍了编译器构造中的两个常用工具Flex与Bison的使用，然后探讨了数据压缩的原理及其应用，接着研究了稀疏矩阵的几种压缩存储算法，详细介绍了词法分析和语法分析的过程，再分别采用三元组和哈希表的方法对词法分析和语法分析过程中生成的表进行了压缩存储，并实验了几组不同的数据，得出了稀疏因子与压缩比的关系。 关键词：压缩；稀疏矩阵；词法分析；语法分析；三元组；哈希表 The study and application of the table compression technology Abstract With the rapid development of technology of software, multimedia and network, the amount of data in systems has been increasing, which brings about a serious problem in storage, transmission, and effective acquisition of data. In the course of modern compiler construction, Lexical analysis and syntax analysis are table-driven. To improve the software productivity, compilers are usually built up by automatic tools. Tables generated by tools are typically large sparse matrices, resulting in substantial waste of storage space. Take the Ada/CS LL (1) grammar as an example, there are about 10000 entries in its table, among which only 10% are non-error entries. This paper briefly introduces two common tools Flex and Bison and demonstrates how to use them to construct compilers. Then data compression and its application are discussed. After that, several sparse matrix compression algorithms are presented. It gives the detailed introduction about the process of lexical analysis and syntax analysis and realizes the compression storage of the table generated in the process of lexical analysis and syntax analysis by using the triples and the hash table, and we get several sets of experimental data, obtained the relationship between sparse factor and compression ratio. Key words: compression; sparse matrix；lexical analysis；syntax analysis； triples ； 目 录 1 绪 论 1 1.1概述 1 1.2国内外研究状况 1 1.3课题研究方法 2 1.4论文构成及研究内容 3 2 Flex和Bison简介及应用 4 2.1Flex介绍 4 2.1.1