Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.arch.embedded > #18900 > unrolled thread

Parsers for extensible grammars?

Back to article view | Back to comp.arch.embedded

Contents

  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

Page 1 of 3  [1] 2 3  Next page →

#18900 — Parsers for extensible grammars?

Hi,

[I probably should direct this at George...  :> ]

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]

A naive approach (?) might be for my code to take a crack at
a particular "statement"/command and, in case of FAIL, invoke
some bolt-on parser to give it a chance to make sense out of
the input.  If *it* FAILs, then the input is invalid, etc.

This sounds like an incredible kluge.  Any better suggestions?

[toc] | [next] | [standalone]

#18901

On 10/22/2014 12:14 PM, Don Y wrote:

> 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).

By that, I mean:  having folks augment a lex/yacc grammar definition
that I've developed as the basis of these "common" commands is
probably ill-advised.  *I* can choose such an implementation for
the common commands but should probably not impose that solution
on the extensions (and risk folks breaking the common stuff!)

[toc] | [prev] | [next] | [standalone]

#18903

On Wed, 22 Oct 2014 12:14:06 -0700, Don Y wrote:

> Hi,
> 
> [I probably should direct this at George...  :> ]
> 
> 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]
> 
> A naive approach (?) might be for my code to take a crack at a
> particular "statement"/command and, in case of FAIL, invoke some bolt-on
> parser to give it a chance to make sense out of the input.  If *it*
> FAILs, then the input is invalid, etc.
> 
> This sounds like an incredible kluge.  Any better suggestions?

If it's always something simple like

<command> <argument> <argument> <argument>

and the only thing that's changing is the command and (possibly) the 
argument types (text, numerical, etc.) that are bound to it, then a parser 
should be pretty easy -- I wouldn't even bother with Lex and Yacc.

-- 

Tim Wescott
Wescott Design Services
http://www.wescottdesign.com

[toc] | [prev] | [next] | [standalone]

#18910

On 10/22/2014 1:13 PM, Tim Wescott wrote:
> On Wed, 22 Oct 2014 12:14:06 -0700, Don Y wrote:
>
>> Hi,
>>
>> [I probably should direct this at George...  :> ]
>>
>> 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]
>>
>> A naive approach (?) might be for my code to take a crack at a
>> particular "statement"/command and, in case of FAIL, invoke some bolt-on
>> parser to give it a chance to make sense out of the input.  If *it*
>> FAILs, then the input is invalid, etc.
>>
>> This sounds like an incredible kluge.  Any better suggestions?
>
> If it's always something simple like
>
> <command> <argument> <argument> <argument>
>
> and the only thing that's changing is the command and (possibly) the
> argument types (text, numerical, etc.) that are bound to it, then a parser
> should be pretty easy -- I wouldn't even bother with Lex and Yacc.

The problem I'm stuck with is not knowing what is likely to be added.
While I suspect most will be similarly trivial, I can also imagine
some esoteric additions!

The "common" commands are trivial enough that, if I knew ALL would be
of similar form, I would almost adopt an approach of sequentially
attempting to parse a command with individual templates -- until one
"fit".  Extensions would just be tacked onto the end of a (short) series
of conditionals:

     if (parse(string, template1))
          command1();
     else if (parse(string, template2))
          command2();
     else if ...

Performance isn't an issue (though footprint may be).  This would allow
extensions to *simply* focus on what they needed to do for *those*
individual commands (without fear of extensions mucking up the common
commands!)

I wouldn't run the risk of someone buggering a "shared grammar" definition
(and failing to add appropriate regression tests to detect that).

But, if the extensions get more esoteric (than this trivial approach),
this starts to look toy-ish; there's very little to *leverage*, here... :<

[toc] | [prev] | [next] | [standalone]

#18918

Don Y wrote:
> On 10/22/2014 1:13 PM, Tim Wescott wrote:
>> If it's always something simple like
>>
>> <command> <argument> <argument> <argument>
>>
>> and the only thing that's changing is the command and (possibly) the
>> argument types (text, numerical, etc.) that are bound to it, then a
>> parser
>> should be pretty easy -- I wouldn't even bother with Lex and Yacc.
> 
> The problem I'm stuck with is not knowing what is likely to be added.
> While I suspect most will be similarly trivial, I can also imagine
> some esoteric additions!

You could try to bring every command into the <command> <argument>...
form with some clever syntax. I'm tempted to say "Lisp", but that
probably doesn't enjoy universal love :-) However, you can easily bring
    if (foo) { bar(); baz(); } else { fred(); }
into "<command> <argument>..." form by making "{}" string delimiters.
This makes this a command 'if' with four parameters: an expression
'(foo)', a string for the 'if' command, an unquoted word 'else', and a
string for the 'else' command.

I recently built a command shell like that, and I believe Tcl does it
the same way. So all you would need to give your users would be a
possiblity to register a command verb, and a way to evaluate strings as
command sequences.


  Stefan

[toc] | [prev] | [next] | [standalone]

#18921

On 10/23/2014 9:36 AM, Stefan Reuther wrote:
> Don Y wrote:
>> On 10/22/2014 1:13 PM, Tim Wescott wrote:
>>> If it's always something simple like
>>>
>>> <command> <argument> <argument> <argument>
>>>
>>> and the only thing that's changing is the command and (possibly) the
>>> argument types (text, numerical, etc.) that are bound to it, then a
>>> parser
>>> should be pretty easy -- I wouldn't even bother with Lex and Yacc.
>>
>> The problem I'm stuck with is not knowing what is likely to be added.
>> While I suspect most will be similarly trivial, I can also imagine
>> some esoteric additions!
>
> You could try to bring every command into the <command> <argument>...
> form with some clever syntax. I'm tempted to say "Lisp", but that
> probably doesn't enjoy universal love :-) However, you can easily bring
>      if (foo) { bar(); baz(); } else { fred(); }
> into "<command> <argument>..." form by making "{}" string delimiters.
> This makes this a command 'if' with four parameters: an expression
> '(foo)', a string for the 'if' command, an unquoted word 'else', and a
> string for the 'else' command.

Note the (contrived) example I posted (elsewhere this thread) attempts
to do that -- by decomposing what might otherwise be "complex" (multivalued)
commands into a series of trivial (single parameter) commands.

E.g., easier to accept an 8 digit HEX value for an IP address (and another
for a mask) than to accept four dotted decimal values (for each).

But, I can't assume others will take a similar approach.  Nor can I
imagine the variety of things that they might need/want to address via
this interface.

(sigh)

> I recently built a command shell like that, and I believe Tcl does it
> the same way. So all you would need to give your users would be a
> possiblity to register a command verb, and a way to evaluate strings as
> command sequences.

I suspect I will end up with a set of routines that parse specific types
of tokens (number, hex number, word, etc.) that the DEVELOPER could call
upon in fashioning an ad hoc parser.  Perhaps I'm too jaded but I bet
that's how additions will end up being implemented -- past observations
suggest this.

I think it's probably easier for folks to think in terms of:  "OK, now I'll
expect an integer in the range of XXX to YYY".  Rather than let them
naively do something like read the characters into a fixed size buffer
(buffer overrun potential!), I can handle SAFELY scanning the next token
AS AN INTEGER and report a value that they can just test (plus an error
code if the token isn't an integer).

That, at least, gives something that can be leveraged safely.

[toc] | [prev] | [next] | [standalone]

#18919

On Wed, 22 Oct 2014 22:54:13 -0700, Don Y wrote:

> On 10/22/2014 1:13 PM, Tim Wescott wrote:
>> On Wed, 22 Oct 2014 12:14:06 -0700, Don Y wrote:
>>
>>> Hi,
>>>
>>> [I probably should direct this at George...  :> ]
>>>
>>> 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]
>>>
>>> A naive approach (?) might be for my code to take a crack at a
>>> particular "statement"/command and, in case of FAIL, invoke some
>>> bolt-on parser to give it a chance to make sense out of the input.  If
>>> *it* FAILs, then the input is invalid, etc.
>>>
>>> This sounds like an incredible kluge.  Any better suggestions?
>>
>> If it's always something simple like
>>
>> <command> <argument> <argument> <argument>
>>
>> and the only thing that's changing is the command and (possibly) the
>> argument types (text, numerical, etc.) that are bound to it, then a
>> parser should be pretty easy -- I wouldn't even bother with Lex and
>> Yacc.
> 
> The problem I'm stuck with is not knowing what is likely to be added.
> While I suspect most will be similarly trivial, I can also imagine some
> esoteric additions!

Who's going to be adding stuff, why, and why won't you have control over 
the process?

> The "common" commands are trivial enough that, if I knew ALL would be of
> similar form, I would almost adopt an approach of sequentially
> attempting to parse a command with individual templates -- until one
> "fit".  Extensions would just be tacked onto the end of a (short) series
> of conditionals:
> 
>      if (parse(string, template1))
>           command1();
>      else if (parse(string, template2))
>           command2();
>      else if ...

I have an in-house parser that I use for debugging and service on a number 
of projects.  It's OO in C++, but it basically supports a syntax of

<keyword> <anything else>

You create an object and give it the keyword, which automagically 
registers it with the first-layer parser.  When someone types something in 
the first-layer parser looks for the keyword, and if its found, hands it 
to the object for further parsing.

It's crude but effective.  I keep telling myself that I'll make more 
library-ish functionality for parsing the <anything else> bit, but so far 
that's all ad-hoc.

-- 

Tim Wescott
Wescott Design Services
http://www.wescottdesign.com

[toc] | [prev] | [next] | [standalone]

#18922

On 10/23/2014 11:45 AM, Tim Wescott wrote:
> On Wed, 22 Oct 2014 22:54:13 -0700, Don Y wrote:

>>>> 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]

>> The problem I'm stuck with is not knowing what is likely to be added.
>> While I suspect most will be similarly trivial, I can also imagine some
>> esoteric additions!
>
> Who's going to be adding stuff, why, and why won't you have control over
> the process?

Other developers.
To address the needs of their environments.
Because its not my codebase.

>> The "common" commands are trivial enough that, if I knew ALL would be of
>> similar form, I would almost adopt an approach of sequentially
>> attempting to parse a command with individual templates -- until one
>> "fit".  Extensions would just be tacked onto the end of a (short) series
>> of conditionals:
>>
>>       if (parse(string, template1))
>>            command1();
>>       else if (parse(string, template2))
>>            command2();
>>       else if ...
>
> I have an in-house parser that I use for debugging and service on a number
> of projects.  It's OO in C++, but it basically supports a syntax of
>
> <keyword> <anything else>
>
> You create an object and give it the keyword, which automagically
> registers it with the first-layer parser.  When someone types something in
> the first-layer parser looks for the keyword, and if its found, hands it
> to the object for further parsing.
>
> It's crude but effective.  I keep telling myself that I'll make more
> library-ish functionality for parsing the <anything else> bit, but so far
> that's all ad-hoc.

I actually think a viable solution might be as above.  I.e., write something
that parses for *just* one particular command.  If no match, try invoking
the thing that parses for the *next* particular command.  Lather, rinse, repeat
until a match is found (successful parse) *or* no more possibilities (FAIL).

Again, this gets used with very low frequency so it doesn't have to be
super efficient.  With subroutines/functions that the developer can invoke
(because I had to write them to parse the commands that *I* implemented),
it could be just a few lines of code extracting parameters from syntactic
sugar, etc.

I *don't* want to intimidate a developer into having to embrace some more
formal framework with which he may not be comfortable.  That way lies bugs.

[toc] | [prev] | [next] | [standalone]

#18933

On Thursday, October 23, 2014 12:54:03 AM UTC-5, Don Y wrote:
> On 10/22/2014 1:13 PM, Tim Wescott wrote:
> > On Wed, 22 Oct 2014 12:14:06 -0700, Don Y wrote:
> 
> The problem I'm stuck with is not knowing what is likely to be added.
> While I suspect most will be similarly trivial, I can also imagine
> some esoteric additions!
> 
Once upon a time, realized that if one uses distinct left and right operator precedence values one can include brackets as operators (high outside precedence and matching low inside precedence).  Never figured out how to parse an operator that had simultaneous infix, prefix and suffix versions.
The appeal is that the parser is table driven and that the table is simple and easy to amend.
Am told that this approach has limitations and has been tried.

[toc] | [prev] | [next] | [standalone]

#18938

On 10/24/2014 7:05 AM, jim.brakefield@ieee.org wrote:
> On Thursday, October 23, 2014 12:54:03 AM UTC-5, Don Y wrote:
>> On 10/22/2014 1:13 PM, Tim Wescott wrote:
>>> On Wed, 22 Oct 2014 12:14:06 -0700, Don Y wrote:
>>
>> The problem I'm stuck with is not knowing what is likely to be added.
>> While I suspect most will be similarly trivial, I can also imagine some
>> esoteric additions!
>>
> Once upon a time, realized that if one uses distinct left and right operator
> precedence values one can include brackets as operators (high outside
> precedence and matching low inside precedence).  Never figured out how to
> parse an operator that had simultaneous infix, prefix and suffix versions.
> The appeal is that the parser is table driven and that the table is simple
> and easy to amend. Am told that this approach has limitations and has been
> tried.

The ideal would be to write a usage() for each command -- to be displayed
when "help" is invoked.  Then, algorithmically extract the parse information
from the example syntax present in that usage() presentation.

But, I think that's too lofty a goal.  It would, by necessity, make the usage()
very verbose -- to qualify all the restrictions on the tokens in the example
syntax (unless the code was smart enough to recognize common constructs
and document them elsewhere).

"Small" tends to preclude much of that added smarts.

[toc] | [prev] | [next] | [standalone]

#18905

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]
>
> A naive approach (?) might be for my code to take a crack at
> a particular "statement"/command and, in case of FAIL, invoke
> some bolt-on parser to give it a chance to make sense out of
> the input.  If *it* FAILs, then the input is invalid, etc.
>
> This sounds like an incredible kluge.  Any better suggestions?

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.

Clifford Heath.

[toc] | [prev] | [next] | [standalone]

#18911

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.

[toc] | [prev] | [next] | [standalone]

#18913

On Thu, 23 Oct 2014 08:22:24 +1100, Clifford Heath
<no.spam@please.net> 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]
>>
>> A naive approach (?) might be for my code to take a crack at
>> a particular "statement"/command and, in case of FAIL, invoke
>> some bolt-on parser to give it a chance to make sense out of
>> the input.  If *it* FAILs, then the input is invalid, etc.
>>
>> This sounds like an incredible kluge.  Any better suggestions?
>
>You want composable grammars. 

Or just parallel parsers.  

Don said "bolt onto" and "harmonious", but it isn't clear to me
whether what he wants is to provide some kind of macro facility in
which new commands are fully expressible in *his* language, or whether
he wants to allow development of a parallel language that remains
interoperable with his but also is separate from it.

The first is [relatively] easy, the second not so much.

In either case, the additional parser should get the first crack at
input with Don's own parser as a fallback.


>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.
                                            ^^^^^^^^

You mean _much_ less powerful.  AFAIK, LR has not been shown to be a
proper superset of LL, but it is known to be a vastly larger space.
The LR(1) subset provably contains LL(1) and also many LL(>1)
languages.

That said, a large number of useful languages can be expressed in LL
with computationally reasonable lookahead.  And it is true in general
that LL parsers are easier to understand and debug.


>When an LL parser has unlimited lookahead, they're very powerful but can 
>have horrible performance due to the extensive backtracking required.

Not really. "Ungetting" tokens - even a large number of them - is not
very costly as long as 1) trying a parse produces no side effects
[i.e. the predication is purely syntactic], or 2) side effects are
implemented "functionally" and can be simply thrown away.

Syntactic predication and quite a lot of useful semantic predication
can be implemented using stack or region allocation strategies, but
there are some hard spaghetti cases where it's nice to have GC
available in your development language.


>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.

PEG (and GLR also) replicates the parser state to deal with ambiguous
input by following the different paths independently.  But the fact is
that most language constructs are unambiguous and thus do not cause
forking, and *unavoidable* ambiguity in the language tends to be
resolved quickly when the ambiguous constructs actually are used.

The problem with PEG (and GLR also) grammars is that there still are
no really useful tools for finding/debugging *unintended* ambiguity.
The generator tool won't give reduce/reduce errors ... warnings maybe,
but not errors ... and will create a parser that just forks on
ambiguous input, wanders off into the hills and gets lost.

Most useful program/control languages do not need PEG (or even GLR).
If your language really is that complicated, you probably should
rethink it.


>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.

Yes.


>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.

The trie would be part of the tokenizer, so it would be compatible
with any parse strategy.


>Clifford Heath.
George

[toc] | [prev] | [next] | [standalone]

#18915

Hi George,

On 10/23/2014 1:45 AM, George Neuner wrote:

> Or just parallel parsers.
>
> Don said "bolt onto" and "harmonious", but it isn't clear to me
> whether what he wants is to provide some kind of macro facility in
> which new commands are fully expressible in *his* language, or whether
> he wants to allow development of a parallel language that remains
> interoperable with his but also is separate from it.

I hadn't considered the idea of expressing "new" commands in terms
of "old"/common commands.

What I am looking for is the ability to define a set of commands
that will "always" be used/useful.  Then, allow others to add
to that set of commands to address specific needs that are
necessary/unique to their environment.  (i.e., the environment
in which these common commands are deployed)

Contrived example:

MESSAGE <text>
PAUSE <delay>
STDIN <device>
STDOUT <device>

Deploy this in a context where stdin/stdout might want to also support
a serial port ("<device> = TTY") would probably necessitate adding:

BITRATE <speed>
CHARACTER <width>
PARITY <odd/even/off/ignore>

In the presence of multiple TTY's, it might then require:

PORT <address>
IRQ <number>

Deploy it where stdin/stdout are a VDT and, perhaps:

BACKGROUND <color>
FOREGROUND <color>
CURSOR <blink/solid/off>

Deploy it where stdin/stdout are a telnet connection, and perhaps:

IP <address>
MASK <dotted_quad>
GATEWAY <address>

I.e., the "arguments" can't be easily foreseen from the perspective
of the first/common commands.

Note that I've presented these in a somewhat "harmonious"/consistent
manner.  Another implementer could have adopted a syntax like:

FORMAT <bitrate><parity><width>

Or:

display WHITE on field of BLUE

Or:

SET IP X.X.X.X/24 VIA Y.Y.Y.Y

I.e., I can't assume he'll consider the <setting> <value> form to be
appropriate to his/her future needs.

> The first is [relatively] easy, the second not so much.
>
> In either case, the additional parser should get the first crack at
> input with Don's own parser as a fallback.

Hmmm... I had considered the opposite approach:  let me verify the
input is/isn't a "common command" before exposing the input to the
"other" parser.  The thought being:  common commands are then
implicitly invariant (you can't change the syntax of them) AND
they "always work" (even if the additional parser has bugs in its
implementation).

[toc] | [prev] | [next] | [standalone]

#18926

Hi Don,

On Thu, 23 Oct 2014 04:14:09 -0700, Don Y <this@is.not.me.com> wrote:

>On 10/23/2014 1:45 AM, George Neuner wrote:
>
>> Or just parallel parsers.
>>
>> Don said "bolt onto" and "harmonious", but it isn't clear to me
>> whether what he wants is to provide some kind of macro facility in
>> which new commands are fully expressible in *his* language, or whether
>> he wants to allow development of a parallel language that remains
>> interoperable with his but also is separate from it.
>
>I hadn't considered the idea of expressing "new" commands in terms
>of "old"/common commands.

You and I have talked about this before: it doesn't really matter how
simple the interface - the way to think about it is as if you are
creating a scripting language in which "operators" are the control
functions exposed by the device.  


>What I am looking for is the ability to define a set of commands
>that will "always" be used/useful.  Then, allow others to add
>to that set of commands to address specific needs that are
>necessary/unique to their environment.  (i.e., the environment
>in which these common commands are deployed)
>
>Contrived example:
>
> :
>
>I.e., the "arguments" can't be easily foreseen from the perspective
>of the first/common commands.

The problem is, that also means the complete set of *functionality*
can't be foreseen ... else you would have provided for it already.

Your "core" can be operated with it's provided command set, but you
can't easily provide for new commands targeting an environment you
know nothing about.

You may want to look up our (ancient) exchange about runtime parser
generators.  You don't need that here, but the discussion about
providing for JIT generated code to link to your device API is
relevant.


>> In either case, the additional parser should get the first crack at
>> input with Don's own parser as a fallback.
>
>Hmmm... I had considered the opposite approach:  let me verify the
>input is/isn't a "common command" before exposing the input to the
>"other" parser.  The thought being:  common commands are then
>implicitly invariant (you can't change the syntax of them) AND
>they "always work" (even if the additional parser has bugs in its
>implementation).

You don't want to "front end" the extensions ... if one of your
commands is redefined, it won't work if you grab it first.

George

[toc] | [prev] | [next] | [standalone]

#18934

Hi George,

On 10/23/2014 1:49 PM, George Neuner wrote:
> On Thu, 23 Oct 2014 04:14:09 -0700, Don Y <this@is.not.me.com> wrote:

>> What I am looking for is the ability to define a set of commands
>> that will "always" be used/useful.  Then, allow others to add
>> to that set of commands to address specific needs that are
>> necessary/unique to their environment.  (i.e., the environment
>> in which these common commands are deployed)
>>
>> Contrived example:
>>
>> :
>>
>> I.e., the "arguments" can't be easily foreseen from the perspective
>> of the first/common commands.
>
> The problem is, that also means the complete set of *functionality*
> can't be foreseen ... else you would have provided for it already.

Exactly.  Because I can't anticipate the functionality that will
be needed in the future.  E.g., the contrived example.

> Your "core" can be operated with it's provided command set, but you
> can't easily provide for new commands targeting an environment you
> know nothing about.

Yes.  And, I can't "guess" to the types of data/actions that may
need to be "encoded" in that command set.

Nor can I ensure the next guy will have the same approach to the
problem -- half the commands may "feel like mine" while the other
half "feel like his/hers".  And, neither group "feels consistent"
with the other.

Like me using infix operators and he using RPN.

> You may want to look up our (ancient) exchange about runtime parser
> generators.  You don't need that here, but the discussion about
> providing for JIT generated code to link to your device API is
> relevant.

Can't.  The (forced) "computer upgrade" cost me my mail archive
(I don't leave mail stored on server  :< )

>>> In either case, the additional parser should get the first crack at
>>> input with Don's own parser as a fallback.
>>
>> Hmmm... I had considered the opposite approach:  let me verify the
>> input is/isn't a "common command" before exposing the input to the
>> "other" parser.  The thought being:  common commands are then
>> implicitly invariant (you can't change the syntax of them) AND
>> they "always work" (even if the additional parser has bugs in its
>> implementation).
>
> You don't want to "front end" the extensions ... if one of your
> commands is redefined, it won't work if you grab it first.

That was exactly the point:  that the common commands are *common*
and always behave exactly the same.  (as well as "always working"
regardless of how much the other guy mucks with the interface).

E.g., if "run" was a common command and he wanted to "overload"
it to add/alter functionality, he'd have to create a new command
("walk_very_very_quickly") to bind to the actions he desires.
Perhaps he wants to turn on a big red light prior to activating
the mechanism ("run"-ing).  If I let him redefine "run" to do this,
I risk him forgetting to verify safety mechanisms are in place
(which other users would ASSUME when invoking "run").

It's a tough call -- assume competence in EVERYTHING?  Or, just
assume competence in their knowledge of their "extensions"??

[toc] | [prev] | [next] | [standalone]

#18959

On Fri, 24 Oct 2014 07:38:12 -0700, Don Y <this@is.not.me.com> wrote:

>On 10/23/2014 1:49 PM, George Neuner wrote:
>
>> Your "core" can be operated with it's provided command set, but you
>> can't easily provide for new commands targeting an environment you
>> know nothing about.
>
>Yes.  And, I can't "guess" to the types of data/actions that may
>need to be "encoded" in that command set.
>
>Nor can I ensure the next guy will have the same approach to the
>problem -- half the commands may "feel like mine" while the other
>half "feel like his/hers".  And, neither group "feels consistent"
>with the other.

I like Simon's idea re: DCL.  I only used VMS briefly in school and I
wasn't aware that DCL could be extended in that way.  It's a nice way
to regularize at least the argument input.

If all you want is to regularize input, another way might be to borrow
from the HTML fast-cgi interface.  It doesn't guarantee anything about
interoperability per se, but it does arrange that programs get their
arguments in recognizable key:value pairs.


>The (forced) "computer upgrade" cost me my mail archive
>(I don't leave mail stored on server  :< )

Ouch. I don't leave anything on provider servers either, but my own
IMAP server is backed up regularly.

What I was thinking about is less important given compile time parser
generation ... we were talking about providing API object and entry
point addresses to runtime generated code.

The relevance (if any) depends on whether you want to allow grammar
extensions direct access to your device API:  i.e. whether the
extensions should be allowed to manipulate your (part of the) device
or whether they have to go through your provided language to do it.


>>>> In either case, the additional parser should get the first crack at
>>>> input with Don's own parser as a fallback.
>>>
>>> Hmmm... I had considered the opposite approach:  let me verify the
>>> input is/isn't a "common command" before exposing the input to the
>>> "other" parser.  The thought being:  common commands are then
>>> implicitly invariant (you can't change the syntax of them) AND
>>> they "always work" (even if the additional parser has bugs in its
>>> implementation).
>>
>> You don't want to "front end" the extensions ... if one of your
>> commands is redefined, it won't work if you grab it first.
>
>That was exactly the point:  that the common commands are *common*
>and always behave exactly the same.  (as well as "always working"
>regardless of how much the other guy mucks with the interface).

That's the safe approach, but it's not terribly friendly ...
particularly in the case of a reusable component where you don't have
any say in the use.  A new developer may want to completely change the
approach to the command set.


>It's a tough call -- assume competence in EVERYTHING?  Or, just
>assume competence in their knowledge of their "extensions"??

It's reasonable to expect that many developers will have little
experience with _formal_ parsing methods and tools ... quite a lot of
applications can get by with RegEx or even just separator tokenization
and have no need of any formal grammar.

George

[toc] | [prev] | [next] | [standalone]

#18962

Hi George,

On 10/26/2014 12:47 AM, George Neuner wrote:
> On Fri, 24 Oct 2014 07:38:12 -0700, Don Y <this@is.not.me.com> wrote:
>> On 10/23/2014 1:49 PM, George Neuner wrote:
>>
>>> Your "core" can be operated with it's provided command set, but you
>>> can't easily provide for new commands targeting an environment you
>>> know nothing about.
>>
>> Yes.  And, I can't "guess" to the types of data/actions that may
>> need to be "encoded" in that command set.
>>
>> Nor can I ensure the next guy will have the same approach to the
>> problem -- half the commands may "feel like mine" while the other
>> half "feel like his/hers".  And, neither group "feels consistent"
>> with the other.
>
> I like Simon's idea re: DCL.  I only used VMS briefly in school and I
> wasn't aware that DCL could be extended in that way.  It's a nice way
> to regularize at least the argument input.

I'm looking into the implementation to see which ideas I can borrow.
I think I have a "prettier" way of creating the syntax.

> If all you want is to regularize input, another way might be to borrow
> from the HTML fast-cgi interface.  It doesn't guarantee anything about
> interoperability per se, but it does arrange that programs get their
> arguments in recognizable key:value pairs.
>
>> The (forced) "computer upgrade" cost me my mail archive
>> (I don't leave mail stored on server  :< )
>
> Ouch. I don't leave anything on provider servers either, but my own
> IMAP server is backed up regularly.

I move my mail archive to a little server that does my DNS, TFTP,
font, DHCP, etc. services periodically.  Lets me view it as mail
(instead of as a raw "mailbox").  That box is the only thing
that runs 24/7/365, here so it's the destination for just about
everything!

[It's more of an appliance than a server]

In my eagerness to get rid of kit before the annual equipment
upgrade cycle, I opted to replace that box -- it had been running for
several years (uptime was over 1000 days) so I felt it "deserved"
to be replaced.

I moved everything onto a *smaller*, faster, less power-hungry box.
Life was good.  Another bit of kit into the bin!  :>

Unfortunately, the box only lasted a few weeks before the disk
(apparently) spun a bearing.  Current thinking is it wasn't a
suitable orientation to *mount* the disk and/or too close to
the main heatsink (the box is REALLY small!  had to shoehorn the
2.5" disk in there just to get it to fit!).

Anyway, easy to recreate everything for which I had sources -- even
my databases!  Mail archive has never been something I considered
"precious" so that was *the* backup (aside from what was on my
MUA at the time).

Rather than risk another disk in the "new" appliance (which was never
intended to have a physical disk drive within), I replaced *that*
with another appliance that *does* accommodate a disk drive (even
having a fan just for the drive).

<shrug>  Moral:  "If it ain't broke, don't fix it!"

When the box that hosts the MUA went down, I took the opportunity
to replace it (preserving the mail that *was* on it at the time).

So, I managed to get rid of some kit -- and the most recent chunk of
my mail archive in the process.  <frown>

> What I was thinking about is less important given compile time parser
> generation ... we were talking about providing API object and entry
> point addresses to runtime generated code.
>
> The relevance (if any) depends on whether you want to allow grammar
> extensions direct access to your device API:  i.e. whether the
> extensions should be allowed to manipulate your (part of the) device
> or whether they have to go through your provided language to do it.

The goal is for people to be able to extend the "system" -- in whichever
directions THEY choose -- and provide a simple way of configuring those
enhancements (software/hardware/systems).  It's a "low value" operation
and, as such, doesn't merit lots of resources.  OTOH, it shouldn't
require "surgery" to tweek variables deep in the sources (these sorts
of "selections" should be very visible without detailed inspection).

I've considered it in the context of "settings" -- almost like twiddling
envars -- except it need not be.  I.e., the "commands" could initiate
*actions* if so desired.

I *hadn't* considered it as a "programming/scripting language" (which
is why I called it a "command parser" and presented command line
argument parsing and configuration file parsing as the examples to
illustrate its intent.

There *could* be some value to a real procedural language, there.
But, when I conveyed the "Forth" suggestion to colleagues, it didn't
fare well (I suspect that had more to do with "Forth" than the
"programming language aspect" of the idea -- almost provincial!

[No desire to take on THAT fight, thankyouverymuch!]

>>>>> In either case, the additional parser should get the first crack at
>>>>> input with Don's own parser as a fallback.
>>>>
>>>> Hmmm... I had considered the opposite approach:  let me verify the
>>>> input is/isn't a "common command" before exposing the input to the
>>>> "other" parser.  The thought being:  common commands are then
>>>> implicitly invariant (you can't change the syntax of them) AND
>>>> they "always work" (even if the additional parser has bugs in its
>>>> implementation).
>>>
>>> You don't want to "front end" the extensions ... if one of your
>>> commands is redefined, it won't work if you grab it first.
>>
>> That was exactly the point:  that the common commands are *common*
>> and always behave exactly the same.  (as well as "always working"
>> regardless of how much the other guy mucks with the interface).
>
> That's the safe approach, but it's not terribly friendly ...

That's why they were called "common commands" -- things that you can
*rely* upon regardless of implementation.

> particularly in the case of a reusable component where you don't have
> any say in the use.  A new developer may want to completely change the
> approach to the command set.

Well, he can always rewrite the subsystem!  :>  I doubt it will take
me more than a week or two to put it in place (though in this first
instance, there are two other subsystems that I want to add/modify
in the process for a more integrated experience)

>> It's a tough call -- assume competence in EVERYTHING?  Or, just
>> assume competence in their knowledge of their "extensions"??
>
> It's reasonable to expect that many developers will have little
> experience with _formal_ parsing methods and tools ... quite a lot of
> applications can get by with RegEx or even just separator tokenization
> and have no need of any formal grammar.

Exactly.  That was my (upthread) observation of what I've encountered
in config file parsers, command line option parsing, etc.  When you
consider how "rich" some of those environments are (options, etc.),
it's a wonder that so much ad hoc parsing is done!  I can see
"evolution"/feeping creaturism explaining some of it (i.e., "it wasn't
this complex when we started") but I doubt that's the real cause.

I suspect it's more one of familiarity:  you write "generic code"
everyday.  So, writing something to extract a numeric value from
the "second whitespace-delimited field" in a statement is trivial.
OTOH, writing a formal grammar so that a *tool* can do this for
you AUTOMATICALLY probably means you spend more time relearning the
tool than you would have spent writing the code!

<shrug>

[toc] | [prev] | [next] | [standalone]

#18969

Hi Don,

On Sun, 26 Oct 2014 08:41:42 -0700, Don Y <this@is.not.me.com> wrote:

>On 10/26/2014 12:47 AM, George Neuner wrote:
>
>> What I was thinking about is less important given compile time parser
>> generation ... we were talking about providing API object and entry
>> point addresses to runtime generated code.
>>
>> The relevance (if any) depends on whether you want to allow grammar
>> extensions direct access to your device API:  i.e. whether the
>> extensions should be allowed to manipulate your (part of the) device
>> or whether they have to go through your provided language to do it.
>
>The goal is for people to be able to extend the "system" -- in whichever
>directions THEY choose -- and provide a simple way of configuring those
>enhancements (software/hardware/systems).  It's a "low value" operation
>and, as such, doesn't merit lots of resources.  OTOH, it shouldn't
>require "surgery" to tweek variables deep in the sources (these sorts
>of "selections" should be very visible without detailed inspection).

I guess the real question is why *you* should be providing that?
You've already given them a way to control your gizmo and they have
the gizmo's API with which to construct a different command set if
they want.


>I've considered it in the context of "settings" -- almost like twiddling
>envars -- except it need not be.  I.e., the "commands" could initiate
>*actions* if so desired.
>
>I *hadn't* considered it as a "programming/scripting language" (which
>is why I called it a "command parser" and presented command line
>argument parsing and configuration file parsing as the examples to
>illustrate its intent.
>
>There *could* be some value to a real procedural language, there.
>But, when I conveyed the "Forth" suggestion to colleagues, it didn't
>fare well (I suspect that had more to do with "Forth" than the
>"programming language aspect" of the idea -- almost provincial!

Forth - and Lisp, too - has a bad rep in many circles ... which is
unfortunate because sometimes it may be the simplest answer to the
problem.

From what I've read I don't think you're really needing a programming
language.  But then I'm still trying to figure out how sophisticated
the commands are likely to be ... they don't look like much from your
examples, but the discussion hints at more complexity.


>>> It's a tough call -- assume competence in EVERYTHING?  Or, just
>>> assume competence in their knowledge of their "extensions"??
>>
>> It's reasonable to expect that many developers will have little
>> experience with _formal_ parsing methods and tools ... quite a lot of
>> applications can get by with RegEx or even just separator tokenization
>> and have no need of any formal grammar.
>
>Exactly.  That was my (upthread) observation of what I've encountered
>in config file parsers, command line option parsing, etc.  When you
>consider how "rich" some of those environments are (options, etc.),
>it's a wonder that so much ad hoc parsing is done!  I can see
>"evolution"/feeping creaturism explaining some of it (i.e., "it wasn't
>this complex when we started") but I doubt that's the real cause.
>
>I suspect it's more one of familiarity:  you write "generic code"
>everyday.  So, writing something to extract a numeric value from
>the "second whitespace-delimited field" in a statement is trivial.
>OTOH, writing a formal grammar so that a *tool* can do this for
>you AUTOMATICALLY probably means you spend more time relearning the
>tool than you would have spent writing the code!

I think it's more panic upon seeing the manual's introduction to the
method theory.  The vast majority of programmers today have little or
no formal schooling, and language theory waters (doesn't matter
syntactic or semantic) get deep very fast.

As with most things, deep understanding isn't necessary to use the
tools, but a programmer does need at least a passing familiarity with
the tool's method to understand what it is trying to do and why it is
failing.  In this regard parser generators are less forgiving than the
average compiler and it doesn't much matter which method(s) the tool
uses - you can make as big a mess with LL(n) as with (LA|S)?LR(1) and
quite easily hang yourself using PEG or GLR.

Learning to use a parser generator isn't really any harder than
learning any other programming language, but the documentation tends
to be scarier.  This isn't helped by the tendency of tool developers
to minimally document and to relate their wares to existing tools that
the user is presumed already to be familiar with.

><shrug>

Nothing to be done about it except try to convince people that it
really isn't that hard and that, for most purposes, they really should
be using a generator tool rather than rolling their own.

The only really valid exceptions are very simple interface "languages"
and very tiny systems 8-) that can't afford the overhead of a
generated parser.  The constant overhead of a generated parser is
fairly large: with care using Bison you can shoehorn a fairly complex
language into ~10KB ... but even the simplest VERB NOUN command parser
is difficult to bring in under ~3KB.  And Bison actually is pretty
good at making small parsers - there are a few tools that are better,
but many more are worse.

However, I think even the parser size argument is losing weight as the
average "small" system keeps getting bigger (32-bit ARM running Linux
toasting bread, etc.).  Moreover, many small system developers are
comfortable using (some form of) RegEx to handle interfaces and
probably most have no clue about its intrinsic overhead.

George

[toc] | [prev] | [next] | [standalone]

#18972

Hi George,

On 10/26/2014 11:36 AM, George Neuner wrote:

>>> The relevance (if any) depends on whether you want to allow grammar
>>> extensions direct access to your device API:  i.e. whether the
>>> extensions should be allowed to manipulate your (part of the) device
>>> or whether they have to go through your provided language to do it.
>>
>> The goal is for people to be able to extend the "system" -- in whichever
>> directions THEY choose -- and provide a simple way of configuring those
>> enhancements (software/hardware/systems).  It's a "low value" operation
>> and, as such, doesn't merit lots of resources.  OTOH, it shouldn't
>> require "surgery" to tweek variables deep in the sources (these sorts
>> of "selections" should be very visible without detailed inspection).
>
> I guess the real question is why *you* should be providing that?
> You've already given them a way to control your gizmo and they have
> the gizmo's API with which to construct a different command set if
> they want.

I have to provide some of these features to get ANY system configured, etc.
I can do this as a completely independant "service" and require others
to invent their own solution to THEIR problems (the customizations that
they may implement).

*Or*, I can put facilities in place that encourage them to "do as I have
done" in the hopes of a tighter, more consistent implementation.  I
expect people to be inherently lazy and opt to *modify* something
that is proven as "working" rather than trying to create something
new, from scratch.

But, in doing so, I have to make a decent attempt at anticipating the sorts
of things they *may* want/need to do.

(e.g., expecting everything to be VERB NOUN pairs might rub some folks
the wrong way)

>> I've considered it in the context of "settings" -- almost like twiddling
>> envars -- except it need not be.  I.e., the "commands" could initiate
>> *actions* if so desired.
>>
>> I *hadn't* considered it as a "programming/scripting language" (which
>> is why I called it a "command parser" and presented command line
>> argument parsing and configuration file parsing as the examples to
>> illustrate its intent.
>>
>> There *could* be some value to a real procedural language, there.
>> But, when I conveyed the "Forth" suggestion to colleagues, it didn't
>> fare well (I suspect that had more to do with "Forth" than the
>> "programming language aspect" of the idea -- almost provincial!
>
> Forth - and Lisp, too - has a bad rep in many circles ... which is
> unfortunate because sometimes it may be the simplest answer to the
> problem.

That's true of all tools.  How many folks avoid dynamic memory allocation
in the belief that it is (inherently!) unsafe?  Or, recursive implementations
("what happens if the recursion never stops?"  "Well, same thing if your
iteration never stops!")

> From what I've read I don't think you're really needing a programming
> language.  But then I'm still trying to figure out how sophisticated
> the commands are likely to be ... they don't look like much from your
> examples, but the discussion hints at more complexity.

I don't know as I can't envision the varieties of hardware (and software)
that will be globbed on.  E.g., I had not envisioned the need for a
conditional operation -- yet, in hindsight, it seems like it could be
extremely useful!  ("Do this -- unless you CAN'T!  In which case, do this
OTHER thing!")

But, how far do you take this before you begin to delve into the realm
of "just add it to the executable directly"?

[When I offered the "C interpreter" as an alternative to Forth -- to see
if the resistance was due to the language or the mechanism -- this was
the reply!  "If you're going to write code, then why create another
means of writing code OUTSIDE the system??"]

>>>> It's a tough call -- assume competence in EVERYTHING?  Or, just
>>>> assume competence in their knowledge of their "extensions"??
>>>
>>> It's reasonable to expect that many developers will have little
>>> experience with _formal_ parsing methods and tools ... quite a lot of
>>> applications can get by with RegEx or even just separator tokenization
>>> and have no need of any formal grammar.
>>
>> Exactly.  That was my (upthread) observation of what I've encountered
>> in config file parsers, command line option parsing, etc.  When you
>> consider how "rich" some of those environments are (options, etc.),
>> it's a wonder that so much ad hoc parsing is done!  I can see
>> "evolution"/feeping creaturism explaining some of it (i.e., "it wasn't
>> this complex when we started") but I doubt that's the real cause.
>>
>> I suspect it's more one of familiarity:  you write "generic code"
>> everyday.  So, writing something to extract a numeric value from
>> the "second whitespace-delimited field" in a statement is trivial.
>> OTOH, writing a formal grammar so that a *tool* can do this for
>> you AUTOMATICALLY probably means you spend more time relearning the
>> tool than you would have spent writing the code!
>
> I think it's more panic upon seeing the manual's introduction to the
> method theory.  The vast majority of programmers today have little or
> no formal schooling, and language theory waters (doesn't matter
> syntactic or semantic) get deep very fast.

Or, a lack of patience -- as exemplified by wanting to write code
"on day one" (before they even know where that code is *headed*).

> As with most things, deep understanding isn't necessary to use the
> tools, but a programmer does need at least a passing familiarity with
> the tool's method to understand what it is trying to do and why it is
> failing.  In this regard parser generators are less forgiving than the
> average compiler and it doesn't much matter which method(s) the tool
> uses - you can make as big a mess with LL(n) as with (LA|S)?LR(1) and
> quite easily hang yourself using PEG or GLR.

My experiences with lex/yacc were far less "pleasant" than writing
arbitrarily complex code in a procedural/object language!  Too much
head scratching as there were interactions "across" the grammar
that were only apparent in hindsight.  The way I thought of the various
constructs "as a human being" was very different from the way the tools
NEEDED me to think of them.  This doesn't appear in *most* languages
(aside from unfortunate issues like "foo =- 2;")

> Learning to use a parser generator isn't really any harder than
> learning any other programming language, but the documentation tends
> to be scarier.  This isn't helped by the tendency of tool developers
> to minimally document and to relate their wares to existing tools that
> the user is presumed already to be familiar with.

There tends to be far more abstraction involved.  People seem to have
a problem with abstraction -- always wanting to know "why do you want
to do that" or "what are you trying to do".

    "Timmy has three apples.  Mary has one.  How many apples would Timmy have
    to give to Mary in order for them to each have the same number of apples?"

    "Why should Timmy have to give her ANY?  Why couldn't *Mary* bring the
    right number of apples to school??"

[Of course, the correct answer is that Timmy should quickly EAT two of his
apples and the problem then disappears!  :> ]

>> <shrug>
>
> Nothing to be done about it except try to convince people that it
> really isn't that hard and that, for most purposes, they really should
> be using a generator tool rather than rolling their own.

Check your mail.  I think the solution I proposed will be *so* tempting
to others that they'll just "cut and paste; edit to taste".  I figured
easier to take this offlist than deal with the inevitable complaints about
"lengthy posts"...  :>

> The only really valid exceptions are very simple interface "languages"
> and very tiny systems 8-) that can't afford the overhead of a
> generated parser.  The constant overhead of a generated parser is
> fairly large: with care using Bison you can shoehorn a fairly complex
> language into ~10KB ... but even the simplest VERB NOUN command parser
> is difficult to bring in under ~3KB.  And Bison actually is pretty
> good at making small parsers - there are a few tools that are better,
> but many more are worse.
>
> However, I think even the parser size argument is losing weight as the
> average "small" system keeps getting bigger (32-bit ARM running Linux
> toasting bread, etc.).  Moreover, many small system developers are
> comfortable using (some form of) RegEx to handle interfaces and
> probably most have no clue about its intrinsic overhead.

But even big systems often have "regions" in which severe constraints
are placed on the implementation.  E.g., many of those "big Linux
implementation" compress the kernel to economize on FLASH/ROM -- this
suggests an unwillingness to add "unnecessary resources" for a one-time
event (decompressing the kernel/system on IPL).  The same sorts of
arguments can apply to "setting configuration options" ("Can't we just
set some bitmaps in a hidden corner of FLASH?")

Or, things like delivering options in BOOTP packets, etc.  Sometimes
you just can't "do what you want" (or what would be "ideal")

[toc] | [prev] | [next] | [standalone]

Page 1 of 3  [1] 2 3  Next page →

Back to top | Article view | comp.arch.embedded

csiph-web