GRAMMAR-BASED GENERATION OF TYPES AND EXTENSIONS
Parsing functionality is automatically generated. In particular, abstract syntax tree types and/or other programmatic constructs are created automatically from a grammar specification in a manner that resembles hand-written code. An abstract syntax tree can subsequently be constructed as a function of the generated types. Further, a plurality of supporting functionality can be generated to consume or produce abstract syntax tree types, among other things.
1 . An automatic parser generator system, comprising:
an interface component to afford access to a grammatical specification; and
a type generation component that automatically generates types from the grammatical specification in a manner that resembles human generation to facilitate construction of an abstract syntax tree.
2 . The system of claim 1 , further comprising a component that automatically generates an abstract syntax tree for a given input based at least in part of the generated types.
3 . The system of claim 1 , further comprising a component that detects grammatical design patterns in the grammatical specification and encodes the patterns.
4 . The system of claim 1 , further comprising a component that generates a canonical representation of one or more tokens.
5 . The system of claim 1 , further comprising a component that generates a canonical representation for a tree node.
6 . The system of claim 1 , further comprising a component that produces one or more visitors to facilitate access to tree nodes and optional performance of an action.
7 . The system of claim 1 , further comprising a component that constructs one or more factories that facilitate generation of abstract syntax trees, sub-trees, nodes, and/or tokens.
8 . The system of claim 1 , further comprises a component that generates one or more rewriters that perform minimal rewrites of tree nodes.
9 . The system of claim 1 , further comprising a component that generates one or helper methods or functions that aid debugging of abstract syntax tree types.
10 . An object-oriented method of automatic parser generation, comprising:
constructing types for an abstract syntax tree from a grammar including concrete data types and interfaces automatically in a manner that resembles hand-written specification; and
generating an abstract syntax tree as a function of the constructed types.
11 . The method of claim 10 , further comprising:
generating an interface for each non-terminal and token type;
constructing a concrete data type for each token type and non-unit production;
encoding unit productions utilizing inheritance amongst interfaces; and
removing interfaces that inherit from exactly one other interface.
12 . The method of claim 10 , further comprising automatically generating common grammatical design patterns including at least one of optionality, lists, and zippered lists.
13 . The method of claim 10 , further comprising generating a canonical representation of tokens.
14 . The method of claim 10 , further comprising generating a canonical representation of abstract syntax tree nodes.
15 . The method of claim 10 , further comprising generating one of more visitors to access the abstract syntax tree and optionally perform an action.
16 . The method of claim 10 , further comprising constructing one or more factories that employ type information to produce synthesized or real nodes and tokens.
17 . The method of claim 10 , further comprising generating one or more rewriters that enable rewriting of parent nodes of the abstract syntax tree upon override or replacement of a node in an immutable system.
18 . The method of claim 10 , further comprising generating a visualizer and/or type proxy to facilitate at least one of tree visualization or debugging.
19 . A parser generation method employing automatic grammar-based generation of types, comprising:
generating an interface for each non-terminal and token of a grammar;
generating a concrete data type for each production and token of the grammar;
removing the concrete data types for unit productions;
encoding a unit production by way of inheritance amongst interfaces; and
removing interfaces that inherit from exactly one other interface.
20 . The method of claim 10 , further comprising automatically constructing an abstract syntax tree as a function of resultant interfaces and concrete types.