A practical method for reducing sparse matrices with invariant entries

Abstract

The analysis table based on automation, such as parsing table and lexical analysis table, can be represented by a sparse matrix with invariant entries. This paper presents an efficient technique for reducing the matrix that can be applied to any analysis tables. The advantages are that a very compact form can be obtained and that the access-time from the resulting data structure is very fast. The desirable features are ascertained according to the experimental results for the parsing table and the lexical analysis table of a typical programming language, PASCL.

Keywords:

• Sparse matrix
• storage requirement
• retrieval time
• reduction method
• parsing table
• lexical analysis table

C.R. Categories:

• 3.70
• 5.22
• 5.23