Subject: "extensible" grammar

From: Tim Showalter <[email-masked]>
Date: 21 Jan 1998 03:51:38 -0500

Out of curiosity, I put together a grammar for the "extensible" grammar
being discussed.  If there are any conflicts, let me know.  I didn't run
this through an ABNF parser because I just wanted to get an idea as to what
it looked like.  I'll stare at it more when we figure out what we're going
to do with it.

This cuts over 30 lines off the formal grammar.  Anyone claiming this
reduces complexity is wrong; it merely moves it out of the parser and up a
level to where the script can't be essentially validated by the parser.

Note that this also adds a couple lines for "tags", which are intended for
optional LISP-style tagged arguments.

	vacation :days 6 "I'm on vacation until Oct. 19th; bye.";

(This is all that's required since the syntax is so liberal.)  I want these
regardless as it would seriously clean up size, vacation, and the
comparator stuff (which is currently broken).

I'm not sure what my opinion is on this.  At some level, trying to prevent
people from doing arbitrarily stupid things is a nice idea, but they're
going to do them anyway.  At the same time, giving someone an unlimited
supply of rope is probably not exactly the greatest thing in the world.

Should probably be a 31-character limit on identifiers (replace the * with
*30).

-- 
                                          Tim Showalter [email-masked]

--- cut here ---

action = identifier WSP *(argument WSP) [WSP] ";"

argument = string / string-list / number / tag

block = "{" [WSP] commands [WSP] "}"
        ;; C-style block

CHAR-NOT-DOT = (%x01-2d / %x2f-%xff)
	;; all the characters that aren't "."

control-structure = identifier WSP
                        *(argument /
                          "(" [WSP] test [WSP] ")")
                        block

command = ( action ";" ) / block / control-structure

commands = *([WSP] command [WSP])

comment = "#" *VCHAR CRLF

identifier = (ALPHA / "_") *(ALPHA DIGIT "_")

multi-line = "text:" [WSP] CRLF
	*((1*CHAR-NOT-DOT *CHAR CRLF) / ("." 1*CHAR-NOT-DOT *CHAR CRLF) /
	  (".." *CHAR CRLF) / CRLF)
	"." CRLF
        ;; Note when used,
        ;; a leading ".." on a line is mapped to ".".

number = 1*DIGIT [QUANTIFIER]
        ;; quantifier is a multiplier (or bit shift)

QUANTIFIER = "K" / "M" / "G"
        ;; K == 2^10; M == 2^20; G = 2^30

quoted-string = DQUOTE *CHAR DQUOTE
        ;; \e" inside a string maps to "
        ;; \e\e inside a string maps to \e
	;; All other characters map to themselves.
        ;; Note that newlines and other weird characters
        ;; are all allowed strings.

string = quoted-string / multi-line

string-list = "(" [WSP] *(string [WSP] "," [WSP]) string [WSP] ")" / string
	;; if there is only a single string, the parens are optional

tag = ":" identifier

test = identifier *(WSP argument) [WSP test-list]

test-list = [WSP] "(" [WSP] *(test [WSP] "," [WSP])
    test [WSP] ")" [WSP]

WSP = 1*(SP / CRLF / HTAB) / comment
        ;; just whitespace.  anyplace this is allowed, a comment is
        ;; as well

---

From: Ned Freed <[email-masked]>
Date: Wed, 21 Jan 1998 01:10:02 -0800 (PST)

> being discussed.  If there are any conflicts, let me know.

How do you do an if-then-else in this grammar?

				Ned

---

From: Tim Showalter <[email-masked]>
Date: 21 Jan 1998 05:04:07 -0500

> Date: Wed, 21 Jan 1998 01:10:02 -0800 (PST)
> From: Ned Freed <[email-masked]>
> Cc: [email-masked]
> 

if is a control-structure that takes a test and a block, evaluating only if
the block is true.

else is a control-structure that takes a block.  It is only valid If the
preceeding command was an if control-structure AND it was in the same
block.  (Error if not.)  If the preceeding if was false, the else's block
is evaluated.

... I'm not sure I like this at all.  It took me more than one try to
explain that, and if/else can be done too easily in the parser to be
messing around with this.

I think the limitation is one block per control-structure.  This is
problematic at best; I believe it has problems again when I consider the
right way to do a cond (without having lots of bogus crap like I've just
suggested for else).

I still sort of like this grammar, but the control-structure rule seems to
be a lose.

---

From: Rob Earhart <[email-masked]>
Date: Wed, 21 Jan 1998 10:13:56 -0500 (EST)

> level to where the script can't be essentially validated by the parser.

  It reduces complexity; it seperates command/argument checking from
syntactic analysis (making both simpler) while maintaining
extensibility.  (You've still got the same amount of *work*, it's just
simpler. :-)

  (Look at it this way: a C parser *could* check the useage of all of
one's function calls to standard library routines, but it'd be ugly;
it's better for it to just worry about syntax, build an abstract
syntax tree, and let some higher level check the tree and deal with
function call checking.)

  This does mean that (assuming the way I write interpreters :-), in
semantic analysis, a control-structure implementation module needs to
be passed a pointer to the previous control-structure (if the prior
element was a control-structure) so that, for example, "else" can
check that it's preceeded by an "if".  That's not a big deal at all,
though, and I love the flexiblity of being able to dynamically add
more control-structures...

>         vacation :days 6 "I'm on vacation until Oct. 19th; bye.";

  I like this...

> How do you do an if-then-else in this grammar?

  if (test) { commands } else { commands }

  (As Tim noted, trying to explain it in terms of the syntax elements
is a lose - but this should be familiar enough to people.)

  The only grammar suggestion I have is that tests in
control-structure look a lot like string-list elements, at least when
you first hit them - is there any chance we could use a different
pair of characters to bracket string-list?  Say, '[' and ']'?

  (It'd be nice if actions could take the results of tests in their
arguments; then the distinction between control-structure and action
could vanish... but as is, it's only a few extra states in one's
parser DFA to keep track of whether the current command's been
restricted to being a control-structure or not; it's not a big deal.)

  )Rob

---

From: Tim Showalter <[email-masked]>
Date: 21 Jan 1998 12:17:35 -0500

> Date: Wed, 21 Jan 1998 10:13:56 -0500 (EST)
> From: Rob Earhart <[email-masked]>
> X-Face: ,IWr.&S`]#R'C+7U:UE~"}g?Zq|OE%6.\}jCwGUO)]|?34%u!8RT_@0"_qA\@g8N:'pK!bM
>  tSE)?S,#@MK1$o(69wQT2L'j)8tP5QfHdYlh`k}:tA"%dG?9z~>
> 

No, this is wrong.  Where before I had a parser that could check the types
of my arguments, I now have to write another layer.

> more control-structures...

It's not that simple.

if (...) { ... }
fileinto ...
else { ... }

Real languages just make the else part of the control structure.  I want
that.

> is a lose - but this should be familiar enough to people.)

Actually, what I meant is that it took me more than five seconds to explain
to *myself* how I expected this to work.  This is bad.

I object to the way control-structures are specified.  There are two
solutions: first, come up with the four control structures deemed
absolutely necessary (if, while, cond, for), and require full-blown
grammar-changing extensions for anything anyone else might want to do;
second, figure out a delimiter so that a control structure can essentially
take multiple blocks.

> pair of characters to bracket string-list?  Say, '[' and ']'?

I considered that; I'm sort of apathetic towards it.

> restricted to being a control-structure or not; it's not a big deal.)

There's an important difference between control-structures and actions.
Since you no longer know how many arguments any given thing takes, the
end-of-statement token is either a block or a semicolon.

To be completely pedantic, however, there's no way to take results of tests
in your arguments because we never state if things are call-by-name or
call-by-value.

---

From: Rob Earhart <[email-masked]>
Date: Wed, 21 Jan 1998 12:51:37 -0500 (EST)

> of my arguments, I now have to write another layer.

  Nope - you *can* do your semantic checking in your parser, even
under this scheme.  I'd argue that this makes your parser needlessly
complex and hard to maintain, when the work's better split up and done
at a higher level, but that's just my opinion.

> else { ... }

  True - you need to keep track of the previous action, not just the
previous control-structure.

> Real languages just make the else part of the control structure.  I want

  Why do they have to be joined at the syntax level, though?  (Real
languages have a fixed set of control structures, which is suboptimal
for Sieve).

> end-of-statement token is either a block or a semicolon.

  Here's how I'd write it:

  argument = token / "(" [WSP] test [WSP] ")"

  command = identifier WSP [argument *(WSP argument)] [WSP] (block / ";")

  token = string / number / tag / token-list

  token-list = "[" [WSP] [token *([WSP] "," [WSP] token)] [WSP] "]"

  (That's also making "lists" a generic container, not only used for
strings; I'm not sure it's useful or not, but some extension may want
it someday.)

  )Rob

---

From: Chris Newman <[email-masked]>
Date: Fri, 23 Jan 1998 16:40:48 -0800 (PST)

> at a higher level, but that's just my opinion.

Functional separation is good.  Layers are bad.  I've never been a fan of
multi-level grammars -- in my experience they make things less reliable
and harder to understand.  Every time you introduce a layer you partition
part of the problem into very complex cross-layer communication issues
(your if-then-else example is one case).  Even a layer as necessary and
delinated as TCP has these problems (think IP security, urgent data,
SIGPIPE).

Parsers are cheap -- I wrote a parser to convert an RFC from text to html
in C in a few days and that's full of ugly heuristic rules.  Even if we
have a single-level grammer and have each Sieve command designed by a
separate individual who's not communicating with others, Sieve will still
be an order of magnitude or two simpler. 

So I see this as a proposal to constrain the human readability of the
script for all time in order to save a few programmer hours.  This seems
like a really bad tradeoff to me.

If we want to compromise on this issue, I suggest we define the rules for
skipping a command (look for unquoted ";"), and let extensions which add
new control structures do whatever they wish.  New control structures will
be rare.  I also don't object to suggestions for what the syntax of
extensions should look like -- just don't make them recommendations or
requirements.

		- Chris