Automata play important roles in wide area of computing and the growth of multicores calls for their efficient parallel implementation. Though it is known in theory that we can perform the computation of a finite automaton in parallel by simulating transitions, its implementation has a large overhead due to the simulation. In this paper we propose a new automaton called simultaneous finite automaton (SFA) for efficient parallel computation of an automaton. The key idea is to extend an automaton so that it involves the simulation of transitions. Since an SFA itself has a good property of parallelism, we can develop easily a parallel implementation without overheads. We have implemented a regular expression matcher based on SFA, and it has achieved over 10-times speedups on an environment with dual hexa-core CPUs in a typical case.

Abstract We herein describe a compiler generator, Rie, which is based on a one‐pass‐type attribute grammar. LR‐attributed grammars are one class of attribute grammars in which attribute evaluation can be performed in one pass during LR parsing without creating a parse tree. Rie was developed based on a variant of an LR‐attributed grammar called ECLR‐attributed grammar (equivalence class LR‐attributed grammar), in which equivalence relations are introduced into the LR‐attributed grammar. Rie generates a one‐pass compiler from a compiler description given in attribute grammar form. Many language processors have been developed using Rie. The generated compiler is only about 1.8 times slower than a handwritten compiler, which is fairly efficient for a compiler generated from formal descriptions.

A description is given of features which were added to a conventional programming language that will manipulate streams of values. A stream is a sequence of values of a certain fixed type. The number of elements of a stream may be determined at execution time, and evaluation of each element can be postponed until its value is actually needed. Many programs can be expressed naturally and clearly as networks of processes communicating by means of streams. The network is called a composite function and consists of several component functions. Since component functions are connected solely by streams, they greatly increase the flexibility of combinations and the reusability of programs. Loop statements can be considered as iterative statements over streams. One general problem in these networks is the mechanism of terminating each process of the network. A practical solution for this problem is presented. Comparisons to other programming styles, such as coroutines, Lisp, functional programming, and dataflow languages, are described. Three modes of execution are considered for the implementation of composite functions: parallel mode, coroutine mode, and inline mode. In the inline mode, a composite function is expanded and transformed into a single function, realizing maximum run-time efficiency. Algorithms for this expansion are given.>