Search

Strings are prevalent in real-world data sets. They often occupy a large fraction of the data and are slow to process. In this work, we present Fast Static Symbol Table (FSST), a lightweight compression scheme for strings. On text data, FSST offers decompression and compression speed similar to or better than the best speed-optimized compression methods, such as LZ4, yet offers significantly better compression factors. Moreover, its use of a static symbol table allows random access to individual, compressed strings, enabling lazy decompression and query processing on compressed data. We believe these features will make FSST a valuable piece in the standard compression toolbox.

The runtime system of dynamic languages such as Prolog or Lisp and their derivatives contain a symbol table, in Prolog often called the atom table. A simple dynamically resizing hash-table used to be an adequate way to implement this table. As Prolog becomes fashionable for 24x7 server processes we need to deal with atom garbage collection and concurrent access to the atom table. Classical lock-based implementations to ensure consistency of the atom table scale poorly and a stop-the-world approach to implement atom garbage collection quickly becomes a bottle-neck, making Prolog unsuitable for soft real-time applications. In this article we describe a novel implementation for the atom table using lock-free techniques where the atom-table remains accessible even during atom garbage collection. Relying only on CAS (Compare And Swap) and not on external libraries, the implementation is straightforward and portable. Under consideration for acceptance in TPLP., Paper presented at the 32nd International Conference on Logic Programming (ICLP 2016), New York City, USA, 16-21 October 2016, 14 pages, LaTeX, 4 PDF figures

Many textual software languages share common concepts such as defining and referencing elements, hierarchical structures constraining the visibility of names, and allowing for identical names for different element kinds. Symbol tables are useful to handle those reference and visibility concepts. However, developing a symbol table can be a tedious task that leads to an additional effort for the language engineer. This paper presents a symbol table meta model usable to define languagespecific symbol tables. Furthermore, we integrate this symbol table meta model with a meta model of a grammar-based language definition. This enables the language engineer to switch between the model structure and the symbol table as needed. Finally, based on a grammarannotation mechanism, our approach is able to generate a symbol table infrastructure that can be used as is or serve as a basis for custom symbol tables., 8 pages, 9 figures, Domain-Specific Modeling Workshop 2015 (DSM 2015)

The security of the web-browser and JavaScript is pivotal in today's world. The potency of information flow control in the context of JavaScript is quite appealing. In this paper, we propose a new secure information flow control model specifically designed for JavaScript. In our approach, we augment the standard symbol table with a mechanism that replaces the reference address for secret values based on the current execution stack. This mechanism also ensures that the secret is stored in a dedicated memory location that can only be accessed by the internal JIT compiler thereby protecting the variable from any unintended leakage or modification by a malicious JavaScript.

In this paper, a multiple-symbol parallel variable length decoding (VLD) scheme is introduced. The scheme is capable of decoding all the codewords in an N-bit block of encoded input data stream. The proposed method partially breaks the recursive dependency related to the VLD. First, all possible codewords in the block are detected in parallel and lengths are returned. The procedure results redundant number of codeword lengths from which incorrect values are removed by recursive selection. Next, the index for each symbol corresponding the detected codeword is generated from the length determining the page and the partial codeword defining the offset in symbol table. The symbol lookup can be performed independently from symbol table. Finally, the sum of the valid codeword lengths is provided to an external shifter aligning the encoded input stream for a new decoding cycle. In order to prove feasibility and determine the limiting factors of our proposal, the variable length decoder has been implemented on an field-programmable gate-array (FPGA) technology. When applied to MPEG-2 standard benchmark scenes, on average 4.8 codewords are decoded per cycle resulting in the throughput of 106 million symbols per second.

A method for quickly producing compilers for high level languages is described. The technique consists of feeding a description of the language to be translated to a general-purpose macro processor. Used in this way, the macro processor functions as a compiler-compiler, providing automatic parsing, lexical scanning, symbol table operations, and handling of syntactic errors. A complete syntactic and semantic description of a WHILE statement (except for Boolean expression processing) is given in only seven lines, as an example. A system programming language implemented by this method is discussed in order to illustrate the main ideas. The compiler produced for this language is compared to other compilers produced by conventional methods. Copyright © 1976 by The Institute of Electrical and Electronics Engineers, Inc.