Re: Parsers for extensible grammars?

From	Don Y <this@is.not.me.com>
Newsgroups	comp.arch.embedded
Subject	Re: Parsers for extensible grammars?
Date	2014-10-22 23:25 -0700
Organization	Aioe.org NNTP Server
Message-ID	<m2a6vl$act$1@speranza.aioe.org> (permalink)
References	<m28vlb$lum$1@speranza.aioe.org> <dcV1w.320229$Hb3.258607@fx03.iad>

Show all headers | View raw

On 10/22/2014 2:22 PM, Clifford Heath wrote:
> On 23/10/14 06:14, Don Y wrote:
>> I'm writing a command parser.  Some set of commands are "common".
>> But, other instances of the parser are augmented with additional
>> commands/syntax.
>>
>> [These additions are known at compile time, not "dynamic"]
>>
>> Ideally, I want a solution that allows folks developing those
>> "other" commands to just "bolt onto" what I have done.  E.g.,
>> creating a single "grammar definition" (lex/yacc) is probably
>> not a good way to go (IME, most small parsers tend to be ad hoc).
>>
>> [Note:  I can't even guarantee that the extensions will be
>> consistent or "harmonious" with the grammar that I implement]

> You want composable grammars. This is right in a core area of my expertise.
> Lex/Yacc (and all other forms of bottom-up LR parsing) are the wrong way to go,
> because the tools must do deep analysis of the entire grammar before producing
> a parser, and the errors that occur require significant expertise to understand.
>
> Top-down parsers (also known as LL or recursive descent) are much easier to
> write and debug. They're typically implemented using limited look-ahead (often
> one token, LL-1) and are slightly less powerful than LR parsers with the same
> look-ahead.
>
> When an LL parser has unlimited lookahead, they're very powerful but can have
> horrible performance due to the extensive backtracking required.
>
> However, so-called packrat parsers trade memory for performance, while
> retaining almost all the power of unlimited backtracking. For a grammar of N
> rules, the memory usage for an input of size M is O(N*M), that is, linear in
> the size of the input. Because the CPU performance is so good,there's no need
> for a separate lexer - the parse performance is the same as the DFAs used for
> lexing so there's no advantage to be had.
>
> Packrat parsers are generally created from PEGs (Parsing Expression Grammars).
> There are plenty of PEG parser generators; I maintain the most widely used one
> for Ruby, but they exist for dozens of languages.
>
> The really nice thing about LL parsers is they're composable. You can take two
> grammars with different rules, and simply layer one on top of the other. Often
> it's helpful to allow a rule in one grammar to call the same rule (by name) in
> the other grammar - this works very like O-O inheritance.
>
> Note that none of this will help you if you want "minimum abbreviation" support
> for your keywords. That is best implemented using a trie. It's all compatible
> with the use of a PEG parser though; the keyword matcher won't be written using
> a PEG, is all.

This sounds like an *ideal* approach!  But...

I'm concerned that too many folks would find a "formal" grammar tool to be
intimidating.

I'm thinking about the *hundreds* of different "configuration files" I've
encountered, "argument handling", etc. and how *few* of these were implemented
with any sort of formal tools.  Rather, almost as a RULE, they all seemed to
be jumbles of spaghetti code (though they "got the job done", more or less).

Cases where "space" was accepted as whitespace -- but "tab", not.
Or, vice versa.

Cases where comments HAD to begin in column one and others where leading
whitespace was ignored.

Or, where comments could not coexist with preceding "content" on the same
line.

Or, where groups of statements had to be co-located on the same line (with
some formal delimiter) instead of being allowed to span lines (couple
this with a maximum line length constraint and you can see one potential
issue!)

And, in each case, no compelling REASON for the restrictions (as if "it was
too much work" to provide a cleaner/more consistent implementation).

I'm left with the impression that these folks either underestimated the
complexity of the tasks they set out for themselves; or, were intimidated
by more "structured" approaches to SUCH A COMMON PROBLEM!

[Or, the structured approaches were harder to comprehend/debug than the
ad hoc spaghetti-code implementations!]

So, I figure decoupling my portion of the implementation (common commands)
from these potential extensions might be A Wise Choice.

Thread

Parsers for extensible grammars? Don Y <this@is.not.me.com> - 2014-10-22 12:14 -0700
  Re: Parsers for extensible grammars? Don Y <this@is.not.me.com> - 2014-10-22 12:17 -0700
  Re: Parsers for extensible grammars? Tim Wescott <seemywebsite@myfooter.really> - 2014-10-22 15:13 -0500
    Re: Parsers for extensible grammars? Don Y <this@is.not.me.com> - 2014-10-22 22:54 -0700
      Re: Parsers for extensible grammars? Stefan Reuther <stefan.news@arcor.de> - 2014-10-23 18:36 +0200
        Re: Parsers for extensible grammars? Don Y <this@is.not.me.com> - 2014-10-23 12:10 -0700
      Re: Parsers for extensible grammars? Tim Wescott <seemywebsite@myfooter.really> - 2014-10-23 13:45 -0500
        Re: Parsers for extensible grammars? Don Y <this@is.not.me.com> - 2014-10-23 12:15 -0700
      Re: Parsers for extensible grammars? jim.brakefield@ieee.org - 2014-10-24 07:05 -0700
        Re: Parsers for extensible grammars? Don Y <this@is.not.me.com> - 2014-10-24 08:04 -0700
  Re: Parsers for extensible grammars? Clifford Heath <no.spam@please.net> - 2014-10-23 08:22 +1100
    Re: Parsers for extensible grammars? Don Y <this@is.not.me.com> - 2014-10-22 23:25 -0700
    Re: Parsers for extensible grammars? George Neuner <gneuner2@comcast.net> - 2014-10-23 04:45 -0400
      Re: Parsers for extensible grammars? Don Y <this@is.not.me.com> - 2014-10-23 04:14 -0700
        Re: Parsers for extensible grammars? George Neuner <gneuner2@comcast.net> - 2014-10-23 16:49 -0400
          Re: Parsers for extensible grammars? Don Y <this@is.not.me.com> - 2014-10-24 07:38 -0700
            Re: Parsers for extensible grammars? George Neuner <gneuner2@comcast.net> - 2014-10-26 03:47 -0400
              Re: Parsers for extensible grammars? Don Y <this@is.not.me.com> - 2014-10-26 08:41 -0700
                Re: Parsers for extensible grammars? George Neuner <gneuner2@comcast.net> - 2014-10-26 14:36 -0400
                Re: Parsers for extensible grammars? Don Y <this@is.not.me.com> - 2014-10-26 12:37 -0700
                Re: Parsers for extensible grammars? George Neuner <gneuner2@comcast.net> - 2014-10-26 18:54 -0400
        Re: Parsers for extensible grammars? Simon Clubley <clubley@remove_me.eisner.decus.org-Earth.UFP> - 2014-10-25 02:02 +0000
          Re: Parsers for extensible grammars? Don Y <this@is.not.me.com> - 2014-10-25 01:56 -0700
            Re: Parsers for extensible grammars? Simon Clubley <clubley@remove_me.eisner.decus.org-Earth.UFP> - 2014-10-25 11:15 +0000
              Re: Parsers for extensible grammars? Don Y <this@is.not.me.com> - 2014-10-25 10:21 -0700
                Re: Parsers for extensible grammars? Simon Clubley <clubley@remove_me.eisner.decus.org-Earth.UFP> - 2014-10-26 01:05 +0000
                Re: Parsers for extensible grammars? Don Y <this@is.not.me.com> - 2014-10-25 19:37 -0700
  Re: Parsers for extensible grammars? Andrew Smallshaw <andrews@sdf.lonestar.org> - 2014-10-23 20:04 +0000
  Re: Parsers for extensible grammars? Les Cargill <lcargill99@comcast.com> - 2014-10-23 22:30 -0500
    Re: Parsers for extensible grammars? rickman <gnuarm@gmail.com> - 2014-10-25 13:36 -0400
      Re: Parsers for extensible grammars? Les Cargill <lcargill99@comcast.com> - 2014-10-25 13:14 -0500
        Re: Parsers for extensible grammars? rickman <gnuarm@gmail.com> - 2014-10-25 14:23 -0400
          Re: Parsers for extensible grammars? Les Cargill <lcargill99@comcast.com> - 2014-10-26 00:50 -0500
          Re: Parsers for extensible grammars? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2014-10-26 19:21 +0000
            Re: Parsers for extensible grammars? rickman <gnuarm@gmail.com> - 2014-10-26 15:29 -0400
  Re: Parsers for extensible grammars? Paul E Bennett <Paul_E.Bennett@topmail.co.uk> - 2014-10-24 09:56 +0100
    Re: Parsers for extensible grammars? Don Y <this@is.not.me.com> - 2014-10-24 07:46 -0700
      Re: Parsers for extensible grammars? Don Y <this@is.not.me.com> - 2014-10-25 19:54 -0700
        Re: Parsers for extensible grammars? Simon Clubley <clubley@remove_me.eisner.decus.org-Earth.UFP> - 2014-10-26 12:15 +0000
          Re: Parsers for extensible grammars? Don Y <this@is.not.me.com> - 2014-10-26 09:02 -0700
            Re: Parsers for extensible grammars? rickman <gnuarm@gmail.com> - 2014-10-26 12:13 -0400
    Re: Parsers for extensible grammars? rickman <gnuarm@gmail.com> - 2014-10-25 13:35 -0400
      Re: Parsers for extensible grammars? Paul E Bennett <Paul_E.Bennett@topmail.co.uk> - 2014-10-26 01:29 +0100
        Re: Parsers for extensible grammars? rickman <gnuarm@gmail.com> - 2014-10-25 21:11 -0400

csiph-web