Is it possible to write an adaptive parser?

Question

I am working on a js library which focuses on error handling. A part of the lib is a stack parser which I'd like to work in most of the environments.

The hard part that there is no standard way to represent the stack, so every environment has its own stack string format. The variable parts are message, type and frames. A frame usually consists of called function, file, line, column.

In some of the environments there are additional variable regions on the string, in others some of the variables are not present. I can run automated tests only in the 5 most common environments, but there are a lot more environments I'd like the parser to work in.

• My goal is to write an adaptive parser, which learns the stack string format of the actual environment on the fly, and after that it can parse the stack of any exception of that environment.

I already have a plan how to solve this in the traditional way, but I am curious, is there any machine learning tool (probably in the topic of unsupervised learning) I could use to solve this problem?

According to the comments I need to clarify the terms "stack string format" and "stack parser". I think it is better to write 2 examples from different environments:

A.)

example stack string:

Statement on line 44: Type mismatch (usually a non-object value used where an object is required)
Backtrace:
  Line 44 of linked script file://localhost/G:/js/stacktrace.js
    this.undef();
  Line 31 of linked script file://localhost/G:/js/stacktrace.js
    ex = ex || this.createException();
  Line 18 of linked script file://localhost/G:/js/stacktrace.js
    var p = new printStackTrace.implementation(), result = p.run(ex);
  Line 4 of inline#1 script in file://localhost/G:/js/test/functional/testcase1.html
    printTrace(printStackTrace());
  Line 7 of inline#1 script in file://localhost/G:/js/test/functional/testcase1.html
    bar(n - 1);
  Line 11 of inline#1 script in file://localhost/G:/js/test/functional/testcase1.html
    bar(2);
  Line 15 of inline#1 script in file://localhost/G:/js/test/functional/testcase1.html
    foo();

stack string format (template):

Statement on line {frames[0].location.line}: {message}
Backtrace:
{foreach frames as frame}
  Line {frame.location.line} of {frame.unknown[0]} {frame.location.path}
    {frame.calledFunction}
{/foreach}

extracted information (json):

{
    message: "Type mismatch (usually a non-object value used where an object is required)",
    frames: [
        {
            calledFunction: "this.undef();",
            location: {
                path: "file://localhost/G:/js/stacktrace.js",
                line: 44
            },
            unknown: ["linked script"]
        },
        {
            calledFunction: "ex = ex || this.createException();",
            location: {
                path: "file://localhost/G:/js/stacktrace.js",
                line: 31
            },
            unknown: ["inline#1 script in"]
        },
        ...
    ]
}

B.)

example stack string:

ReferenceError: x is not defined
    at repl:1:5
    at REPLServer.self.eval (repl.js:110:21)
    at repl.js:249:20
    at REPLServer.self.eval (repl.js:122:7)
    at Interface.<anonymous> (repl.js:239:12)
    at Interface.EventEmitter.emit (events.js:95:17)
    at Interface._onLine (readline.js:202:10)
    at Interface._line (readline.js:531:8)
    at Interface._ttyWrite (readline.js:760:14)
    at ReadStream.onkeypress (readline.js:99:10)

stack string format (template):

{type}: {message}
{foreach frames as frame}
{if frame.calledFunction is undefined}
    at {frame.location.path}:{frame.location.line}:{frame.location.column}
{else}
    at {frame.calledFunction} ({frame.location.path}:{frame.location.line}:{frame.location.column})
{/if}
{/foreach}

extracted information (json):

{
    message: "x is not defined",
    type: "ReferenceError",
    frames: [
        {
            location: {
                path: "repl",
                line: 1,
                column: 5
            }
        },
        {
            calledFunction: "REPLServer.self.eval",
            location: {
                path: "repl.js",
                line: 110,
                column: 21
            }
        },
        ...
    ]
}

The parser should process the stack strings and return the extracted information. The stack string format and the variables are environment dependent, the library should figure out on the fly how to parse the stack strings of the actual environment.

I can probe the actual environment by throwing exceptions with well known stacks and check the differences of the stack strings. For example if I add a whitespace indentation to the line that throws the exception, then the column and probably the called function variables will change. If I detect a number change somewhere, then I can be sure that we are talking about the column variable. I can add line breaks too, which will cause line number change and so on...

I can probe for every important variables, but I cannot be sure that the actual string does not contain additional unknown variables and I cannot be sure that all of the known variables will be added to it. For example the frame strings of the "A" example contain an unknown variable and do not contain the column variable, while the frame strings of the "B" example do not always contain the called function variable.

Answer 1

I wrote a relatively simple adaptive parser in Prolog. The parser is essentially a string rewriting system that learns new rewrite rules from its input, such as "A implies that B" means "A implies B", or "neither A nor B" means "not (A or B)", using a simple bottom-up parsing algorithm.

Using the grammar rules that it has learned, the parser is able to convert English phrases such as C is not less than D percent of E and R implies that Q is not true into Prolog terms, such as (C<D/100*E)=false,(R->Q\=true).

In addition to the parser that I described here, there is an adaptive parser generator called dypgen. There also are several programming languages that allow user-defined syntax extensions, including Coq and Agda.

The Nearley parser generator also allows grammar rules to be added at runtime, though this feature isn't documented yet.

Answer 2

The parsing of linguistic units from streams of speech by the human brain is an existing system that can be studied, and it is a legitimate proof of concept. A working brain adapts to changes in volume, tone frequency, information rate, rhythm, accent, dialect, and background sound as it parses sequences of vocal sounds originating from the initial tone and transient processing of signals from the vestibulocochlear nerve.

The later evolution of written symbol recognition from signals originating from the optic nerve is a related proof of concept.

Simple adaptive parsing is running in the lab as a part of social networking automation, but only for limited sets of symbols and sequential patterns. It does scale without reconfiguration to an arbitrarily large base linguistic units, prefixes, endings, and suffixes, limited only by our hardware capacities and throughput.

The existence of regular expression libraries was helpful to keep the design simple. We use the PCRE version 8 series library fed by a ansiotropic form of DCNN for feature extraction from a window moving through the input text with a configurable windows size and move increment size. Heuristics applied to input text statistics gathered in a first pass produce a set of hypothetical PCREs arranged in two layers.

Optimization occurs to apply higher probabilistic weights to the best PCREs in a chaotically perturbed text search. It uses the same gradient descent convergence strategies used in NN back propagation in training. It is a naive approach that does not make assumptions like the existence of backtraces, files, or errors. It would adapt equally to Arabic messages and Spanish ones.

The output is an arbitrary directed graph in memory, which is similar to a dump of an object oriented database. JSON hierarchies were too restrictive four our purposes, since the directed graphs we were parsing from a serial text stream had cases of multiple incoming directed edges into vertices and some circular edge sequences.

قنبلة -> dangereux -> 4anlyss
bomba -> dangereux
ambiguïté -> 4anlyss -> préemption -> قنبلة

Although a re-entrant algorithm for a reinforcement version is stubbed out and the wellness signal is already available, other work preempted furthering the adaptive parser or working toward the next step to use the work for natural language:

Matching the directed graphs to persisted directed graph filters representing ideas, which would mimic the idea recollection aspect of language comprehension.

Answer 3

For the formats above you could write a one normal CFG parser what would extract AST tree. That actualy you want as output?