One-pass greedy-pattern-matching finite-state-machine code generation

Abstract

A one-pass, greedy-pattern-matching, finite-state-machine code generator is disclosed. The code generator generates local code (such as processor-native code) from intermediate code (such as Java byte code). In one embodiment of the invention, a computer-implemented method for generating local code from intermediate code first includes receiving a current element of a post-fix-notated intermediate code. The method receives a current element of a postfix-notated intermediate code, and matches the current element to a base rule within a predetermined intermediate code-to-local code grammar. The method then selects and applies a matching base rule based on a predetermined criteria. A local code is then generated according to the matching base rule applied to the current element. A next element of the intermediate code is then advanced to as the current element. In another embodiment, the method matches the current element to a base rule, includes matching a most recent element to one or more chain rule(s) within the grammar and applies the chain rule(s) to the most recent element to enable the current element to match a given base rule. In still another embodiment, a code-generator generator is disclosed that constructs a code generator according to a machine specification.