Answers.Body: <p>I wrote a relatively simple <a href="https://github.com/jarble/adaptive_parser" rel="nofollow noreferrer">adaptive parser in Prolog</a>. The parser is essentially a <a href="https://cs.stackexchange.com/a/102698/77574">string rewriting system</a> that learns new rewrite rules from its input, such as <code>"A implies that B" means "A implies B"</code>, or <code>"neither A nor B" means "not (A or B)"</code>, using a simple bottom-up parsing algorithm.</p>
  
  <p>Using the grammar rules that it has learned, the parser is able to convert English phrases such as <code>C is not less than D percent of E and R implies that Q is not true</code> into Prolog terms, such as <code>(C&lt;D/100*E)=false,(R-&gt;Q\=true)</code>.</p>
  
  <p>In addition to the parser that I described here, there is an adaptive parser generator called <a href="http://dypgen.free.fr/" rel="nofollow noreferrer">dypgen</a>. There also are several programming languages that allow user-defined syntax extensions, including <a href="https://coq.inria.fr/refman/user-extensions/syntax-extensions.html" rel="nofollow noreferrer">Coq</a> and <a href="https://agda.readthedocs.io/en/v2.6.0.1/language/syntax-declarations.html" rel="nofollow noreferrer">Agda</a>.</p>
  
  <p>The <a href="https://github.com/kach/nearley/issues/485" rel="nofollow noreferrer">Nearley</a> parser generator also allows grammar rules to be added at runtime, though this feature isn't documented yet.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-10-30T20:48:52.493Z
Answers.LastActivityDate: 2020-01-03T23:12:58.960Z
Answers.LastEditDate: 2020-01-03T23:12:58.960Z
Answers.UserDisplayName: Anderson Green
Answers.Body: <p>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.</p>
  
  <p>The later evolution of written symbol recognition from signals originating from the optic nerve is a related proof of concept.</p>
  
  <p>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.</p>
  
  <p>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.</p>
  
  <p>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.</p>
  
  <p>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.</p>
  
  <pre><code>قنبلة -&gt; dangereux -&gt; 4anlyss
  bomba -&gt; dangereux
  ambiguïté -&gt; 4anlyss -&gt; préemption -&gt; قنبلة
  </code></pre>
  
  <p>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:</p>
  
  <p>Matching the directed graphs to persisted directed graph filters representing ideas, which would mimic the idea recollection aspect of language comprehension.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-07-07T05:00:00.337Z
Answers.LastActivityDate: 2018-07-07T05:00:00.337Z
Answers.UserDisplayName: Douglas Daseeco
Answers.Body: <p>For the formats above you could write a one normal CFG parser what would extract AST tree. That actualy you want as output?</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-06-07T09:45:39.850Z
Answers.Text: The formats are unknown, they should be detected somehow. Yepp, I ended up working on a parser and pattern mining lib, so I can do this.
Answers.UserDisplayName: inf3rno
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-06-03T18:14:38.733Z
Answers.LastActivityDate: 2019-06-03T18:14:38.733Z
Answers.UserDisplayName: user8426627
Body: <p>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. </p>
  
  <p>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. </p>
  
  <p>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. </p>
  
  <ul>
  <li>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. </li>
  </ul>
  
  <p>I already have a plan how to solve this in the traditional way, but I am curious, <strong>is there any machine learning tool (probably in the topic of unsupervised learning) I could use to solve this problem?</strong></p>
  
  <p>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:</p>
  
  <p>A.)</p>
  
  <p><em>example stack string:</em></p>
  
  <pre><code>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();
  </code></pre>
  
  <p><em>stack string format (template):</em></p>
  
  <pre><code>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}
  </code></pre>
  
  <p><em>extracted information (json):</em></p>
  
  <pre><code>{
      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"]
          },
          ...
      ]
  }
  </code></pre>
  
  <p>B.)</p>
  
  <p><em>example stack string:</em></p>
  
  <pre><code>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.&lt;anonymous&gt; (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)
  </code></pre>
  
  <p><em>stack string format (template):</em></p>
  
  <pre><code>{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}
  </code></pre>
  
  <p><em>extracted information (json):</em></p>
  
  <pre><code>{
      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
              }
          },
          ...
      ]
  }
  </code></pre>
  
  <p>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.</p>
  
  <p>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...</p>
  
  <p>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.</p>
  
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2018-03-09T18:44:05.070Z
Comments.Text: Welcome to AI!  I took the liberty of editing for readability, and added a javascript tag (very happy to see a js/ML question:)  I'd suggest including the name of js library you're using because someone may have direct experience with it.
Comments.UserDisplayName: DukeZhou
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2018-03-10T09:36:00.127Z
Comments.Text: Definitions of "stack string format", "stack parser", ... should be clarified.
Comments.UserDisplayName: pasaba por aqui
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2018-03-10T12:32:41.483Z
Comments.Text: @pasabaporaqui updated
Comments.UserDisplayName: inf3rno
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2018-03-10T12:35:58.563Z
Comments.Text: @DukeZhou I haven't used any ML library yet. I need to decide first what tool I could use to complete this task. I am afraid that using some kind of hardcoded approach for the parser will be too rigid, and won't work in some of the environments, that's why I am thinking on using ML, but I have zero experience with it. What I need is some pattern recognition algorithm, which will be able to recognize the variable and constant regions of the stack string, and if the pattern does not match by a new stack string or probably by a frame string, then it will adapt to it.
Comments.UserDisplayName: inf3rno
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2018-03-10T16:47:01.880Z
Comments.Text: Interesting question. One approach is  "grammar induction". All strings you present they have the form " Header Frame ... Frame "  where "Frame" contains common parts / structures as "Line N", "of F". Grammar induction will find how to extract these items from the string.
Comments.UserDisplayName: pasaba por aqui
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2018-03-10T18:43:28.423Z
Comments.Text: @pasabaporaqui Yes, there are rules we can assume, for example every stack has a possibly multiline header (or footer) with at least the message. Every frame contains at least a path. Frame string formats can be different depending on the variables, e.g. in example B. if the called function is not set, then there are no parentheses around the location variables. I think the hardest part is separating a different frame string template from an unknown variable.
Comments.UserDisplayName: inf3rno
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2018-04-21T14:39:36.617Z
Comments.Text: What I am looking for appears to be "sequential pattern discovery". There are several algorithms so I still need to read a lot more. It is an interesting topic, because you can use the same to find temporal patterns, which means I will be able to use it for medical research too.
Comments.UserDisplayName: inf3rno
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-05-06T04:44:38.777Z
Comments.Text: @pasabaporaqui Splitting up to 1 or 2 lines based on probing with more or less known exceptions and using a modified SPADE algorithm with constraints like parameter count looks the most promising so far. I'll try to implement it. I guess it will take a week at least to figure this out. At least I have found something after 2 months... http://www.philippe-fournier-viger.com/spmf/index.php?link=algorithms.php I don't think this pattern mining is considered machine learning, but the results can be useful for learning algorithms.
Comments.UserDisplayName: inf3rno
Tags: <machine-learning><unsupervised-learning><javascript>
Title: Is it possible to write an adaptive parser?
UserDisplayName: inf3rno
ThreadText: # Is it possible to write an adaptive parser?
  
  (Asked by: username_0 on 2018-03-08)
  
  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.
  
  **Tags:** machine-learning, unsupervised-learning, javascript
  
  > **Comments:**
  > **username_1**: Welcome to AI!  I took the liberty of editing for readability, and added a javascript tag (very happy to see a js/ML question:)  I'd suggest including the name of js library you're using because someone may have direct experience with it.  
  > **username_2**: Definitions of "stack string format", "stack parser", ... should be clarified.  
  > **username_0**: @username_2 updated  
  > **username_0**: @username_1 I haven't used any ML library yet. I need to decide first what tool I could use to complete this task. I am afraid that using some kind of hardcoded approach for the parser will be too rigid, and won't work in some of the environments, that's why I am thinking on using ML, but I have zero experience with it. What I need is some pattern recognition algorithm, which will be able to recognize the variable and constant regions of the stack string, and if the pattern does not match by a new stack string or probably by a frame string, then it will adapt to it.  
  > **username_2**: Interesting question. One approach is  "grammar induction". All strings you present they have the form " Header Frame ... Frame "  where "Frame" contains common parts / structures as "Line N", "of F". Grammar induction will find how to extract these items from the string.  
  > **username_0**: @username_2 Yes, there are rules we can assume, for example every stack has a possibly multiline header (or footer) with at least the message. Every frame contains at least a path. Frame string formats can be different depending on the variables, e.g. in example B. if the called function is not set, then there are no parentheses around the location variables. I think the hardest part is separating a different frame string template from an unknown variable.  
  > **username_0**: What I am looking for appears to be "sequential pattern discovery". There are several algorithms so I still need to read a lot more. It is an interesting topic, because you can use the same to find temporal patterns, which means I will be able to use it for medical research too.  
  > **username_0**: @username_2 Splitting up to 1 or 2 lines based on probing with more or less known exceptions and using a modified SPADE algorithm with constraints like parameter count looks the most promising so far. I'll try to implement it. I guess it will take a week at least to figure this out. At least I have found something after 2 months... http://www.philippe-fournier-viger.com/spmf/index.php?link=algorithms.php I don't think this pattern mining is considered machine learning, but the results can be useful for learning algorithms.  
  
  ---
  
  ## 3 answers
  
  ### Answer by username_3 on 2018-10-30. Score: 1
  
  I wrote a relatively simple [adaptive parser in Prolog](https://github.com/jarble/adaptive_parser). The parser is essentially a [string rewriting system](https://cs.stackexchange.com/a/102698/77574) 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](http://dypgen.free.fr/). There also are several programming languages that allow user-defined syntax extensions, including [Coq](https://coq.inria.fr/refman/user-extensions/syntax-extensions.html) and [Agda](https://agda.readthedocs.io/en/v2.6.0.1/language/syntax-declarations.html).
  
  The [Nearley](https://github.com/kach/nearley/issues/485) parser generator also allows grammar rules to be added at runtime, though this feature isn't documented yet.
  
  
  ---
  
  ### Answer by username_4 on 2018-07-07. Score: 0
  
  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 by username_5 on 2019-06-03. Score: 0
  
  For the formats above you could write a one normal CFG parser what would extract AST tree. That actualy you want as output?
  
  > **Comments:**
  > **username_0**: The formats are unknown, they should be detected somehow. Yepp, I ended up working on a parser and pattern mining lib, so I can do this.  
  
  ---
  
  