Back to results
US 2003/0191847 A1Published application
Symmetrical structural pattern matching
AssigneeXerox Corporation
InventorsJean-Yves Vion-Dury, Emmanuel Pietriga
Life of this patent
Estimating the term…
Loading patent…
Loading patent…
AssigneeXerox Corporation
InventorsJean-Yves Vion-Dury, Emmanuel Pietriga
Estimating the term…
The invention provides a pattern matching technique based on the symmetrical construction of the code structures representing the matching expression and the filter to be matched. The method of the invention is for determining whether a computer-storable expression matches a filter. A first code structure representing the expression is evaluated for determining a value of the expression. A second code structure representing the filter is analyzed for determining the characteristics of the filter. Then, the value is filtered according to the filter characteristics. The first code structure is constructed from a plurality of first programming language code structure elements and the second code structure is constructed from a plurality of second programming language code structure elements. Each second structure element corresponds to one of the first structure elements. This symmetrical construction of both code structures enables an arbitrary level of structural complexity. The matching operation may be invoked explicitly.
A method of operating a computer system for determining whether a computer-storable expression matches a filter, the method comprising the steps of:
An article of manufacture for use in a computer system comprising:
A system for determining whether a computer storable expression matches a filter, the system comprising:
Dependencies are inferred from the claim text.
Drawings are temporarily unavailable. Open the PDF at USPTO
From the US filing history. Foreign family members aren’t listed.
Backward citations are indexed for grants only.
Creation or generation of source code: programming languages or programming paradigms
Syntactic analysis: parsing
Abstract machines for program code execution, e.g. Java virtual machine [JVM], interpreters or emulators: runtime interpretation or emulation, e…
Computing and data processing
Term end not estimated
Cross-reference is made to U.S. patent applications Ser. No. 09/______, entitled “Bi-Valuation Of Programming Statements” (Attorney Docket No. D/A0858Q), which is assigned to the same assignee as the present invention and incorporated herein by reference.
1. Field of the Invention
The invention generally relates to pattern matching techniques in programming languages and in particular to a method and system for determining whether a computer-storable expression matches a filter.
The accompanying drawings are incorporated into and form a part of the specification to illustrate several embodiments of the present invention. These drawings, together with the description, serve to explain the principles of the invention. The drawings are only for the purpose of illustrating alternative examples of how the invention can be made and used and are not to be construed as limiting the invention to only the illustrated and described embodiments. Further features and advantages will become apparent from the following and more particular description on the various embodiments of the invention as illustrated in the accompanying drawings, wherein:
FIG. 1 illustrates a computer system according to the invention;
FIG. 2 is a general flow chart illustrating the pattern-matching technique of the invention;
Referring now to the drawings and particularly to FIG. 1, which illustrates a computer system of the present invention, processing means 100 is provided that is connected to an input section 110 and an output section 120. The processing means 100 can be of any type and has access to a program code storage 130 that stores the programming language statements and expressions that are operated on by the invention. The system further comprises in the example shown in FIG. 1, a statement evaluation section 140 and a pattern matching section 150 including instructions that allow the processing means 100 to operate as discussed in more detail below.
General Syntax and Operational Semantics
Before going into the details of the invention, an example of a general abstract syntax for terms of the underlying language is provided, where the notation of e encompasses imperative and declarative statements. Operational semantics is described by using the SOS style described in G. D. Plotkin's article “A structural approach to operational semantics”, Technical Report DAIMI-FN-19, Computer Sciences Dept., Århus university, Denmark, 1981, considering “small step” transition in order to cover an eventual extension to concurrent languages with interleaving semantics.