Well, a Context Free Grammar (CFG) is a mechanism commonly used to
express aspects of programming language syntax. A grammar consists of a
set of terminals (actual symbols like '+' or '93') and non-terminals
(statement, expression term, etc.) and productions or re-write rules.
Finally, one non-terminal will be the goal symbol. A common syntax
known as Extended Backus-Naur form allows multiple productions to be
collapsed into a single rule using metasymbols like '|' (or), '{ }'
(repetition zero or more times) and '[ ]' (optional item). Finally, the
symbols '::=' (also '-->') is used to separate the symbole being
rewritten from what it is being rewritten as.
In this case, the grammar is
E ::= T | E + T | E - T
T ::= N | N * T | N / T
where the significance of the non-terminals is
E - expression
T - term
N - number
In our case, the goal symbol is E. Can we parse 2 + 3 * 4. The answer
is yes, and it can be done as follows:
2 + 3 * 4
N + 3 * 4 (rewriting 2 as N)
N + N * 4 (rewriting 3 as N)
N + N * N (rewriting 4 as N)
T + N * N (rewriting N as T)
E + N * N (rewriting T as E)
E + N * T (rewriting N as T)
E + T (rewriting N * T as T)
E (rewriting E + T as E)
The resulting structure can be represented using a linear notation such
as [2 + [3 * 4]] or as a tree (which won't come out right if you're not
using a fixed width font):
+
/ \
/ \
2 *
/ \
/ \
3 4
Incidentally, context free grammars were introduced by Noam Chomsky as
a way of describing grammars of natural languages, where the
productions (there called phrase structure rules) will be rules like
S ::= NP VP
VP ::= V | V NP
etc.
--- James Gray <[EMAIL PROTECTED]> wrote:
> Greg, Most of your philosophical posts are fascinating, but I am
> completely
> lost on this one. Am I the only one you have lost here. Comment
> below.
>
> ----- Original Message -----
> From: "Greg Woodhouse" <[EMAIL PROTECTED]>
> To: <hardhats-members@lists.sourceforge.net>
> Sent: Tuesday, August 16, 2005 5:15 PM
> Subject: RE: [Hardhats-members] MUMPS features
>
>
> > There's a more basic issue, too. If your expression grammar is
> > something like
> >
> I have no idea what these next two lines mean.
> > E ::= T | E + T | E - T
> > T ::= N | N * T | N / T
> >
> >
> > where N is a number, then
> >
> > [2 + [3 * 4]]
> >
> > is a valid parse, but
> >
> > [[2 + 3] * 4]
> >
> > is not (because '2 + 3' is not an N).
> >
> > Basically, you just take the CFG everyone knows by heart and toss
> it
> > out. And why? To make the expression easier to parse? Well, maybe
> > marginally so, but parsing an expression grammar is a virtual
> > no-brainer.
> >
> > --- Greg Woodhouse <[EMAIL PROTECTED]> wrote:
> >
> >> In every single language using infix notation (except MUMPS) that
> I'm
> >> familiar with 2 + 3 * 4 = 16, and it is a longstanding convention
> in
> >> mathematics that 2 + 3 * 4 is 2 + (3 * 4) not (2 + 3) * 4.
> >>
> >> It's not that I can't live with strict left to right evaluation,
> it's
> >> just that it's annoying...really annoying. It's as if someone
> decided
> >> that they would violate a well established convention just for
> >> <insert
> >> your favorite expletive> of it.
> >>
> >> --- Cameron Schlehuber <[EMAIL PROTECTED]> wrote:
> >>
> >> > Greg, follow these instructions:
> >> >
> >> > First, add 3 to 2.
> >> > Next, multiply your result times 4.
> >> > What is your answer?
> >> >
> >> > -----Original Message-----
> >> > From: [EMAIL PROTECTED]
> >> > [mailto:[EMAIL PROTECTED] On Behalf
> Of
> >> > Greg
> >> > Woodhouse
> >> > Sent: Tuesday, August 16, 2005 1:51 PM
> >> > To: hardhats-members@lists.sourceforge.net
> >> > Subject: Re: [Hardhats-members] MUMPS features
> >> >
> >> > Hmm...I hesitate to do this, for fear of forgetting something,
> but
> >> my
> >> > MUMPS "greatest hits" list, includes at least
> >> >
> >> > 1. Global arrays
> >> > 2. Hierarchical arrays in general, and especially the ability to
> >> > store
> >> > values at non-leaf nodes.
> >> > 3. An integrated JOB command and the $J special variable
> >> > 4. Patterns
> >> > 5. The MERGE command
> >> > 6. Built in string handling functions
> >> > 7. Incremental locks (but see below)
> >> > 8. Indirection and the XECUTE command (again with some caveats)
> >> > 9. Simplicity
> >> >
> >> > By contrast, my "biggest gripes" list includes
> >> >
> >> > 1. Default global scope for variables
> >> > 2. No static scoping
> >> > 3. No interprocess communication or asynchronous signaling
> >> > 4. Weak support for I/O
> >> > 5. I'm sorry, but 2 + 3 * 4 is NOT 20
> >> > 6. Unintuitive (and not clearly useful) semantics for reference
> >> > parameters
> >> > 7. Incremental locks don't block (like semaphores)
> >> > 8. No distinction between read and write locks
> >> > 9. No support for namespaces or packages
> >> > 10. No flexibility with regard to character sets
> >> >
> >> >
> >> > --- Chris Richardson <[EMAIL PROTECTED]> wrote:
> >> >
> >> > > I don't have much easy association with baseball, but;
> >> > >
> >> > > 1) the polymorphic Data Representation (for SET X="12
> Cats");
> >> > > A) a string, WRITE X
> >> > > B) an expression, WRITE X+"15 Dogs"
> >> > > C) a Truth Value, IF X WRITE "True"
> >> > > D) has properties, WRITE
> >> > > %DATA(X)_":"_$LENGTH(X)_":"_$LENGTH(X," ")
> >> > > (and a lot more)
> >> > > E) has substrings, WRITE $PIECE(X," ",2)
> >> > > F) extensible, SET X=X_" and kittens"
> >> > > G) malible, FOR I=$LENGTH(X):-1:1 WRITE $EXTRACT(X,I)
> >> > > H thru ZZZ) Lots more
> >> > > 2) data clustering, for the data created by FOR I=1:1:10 SET
> >> > > X($R(100))=I
> >> > > A) Evaluated, WRITE $DATA(X)
> >> > > B) Walked, SET Y="" FOR S J=$ORDER(X($G(J)) QUIT:J=""
> >> WRITE
> >> > > X(J)_":"_J,!
> >> > > C) Copied, MERGE Z=X
> >> > > D) Trimmed, SET J=$ORDER(X("")) KILL:J X(J)
> >> > > E) Killed, KILL X
> >> > >
> >> > > More later.
> >> > >
> >> > > ----- Original Message -----
> >> > > From: "Gregory Woodhouse" <[EMAIL PROTECTED]>
> >> > > To: <hardhats-members@lists.sourceforge.net>
> >> > > Sent: Tuesday, August 16, 2005 7:09 AM
> >> > > Subject: [Hardhats-members] MUMPS features
> >> > >
> >> > >
> >> > > > I've been thinking about the use of strings as a uniform
> data
> >> > > > representation in MUMPS and, to draw an analogy with
> baseball,
> >> it
> >> > > is
> >> > > > easy to come up with a hit (such as the ability to use the
> same
> >> > > > idioms, e.g., $G(X)="" for different kinds of data), or a
> >> double
> >> > > > (such as being able to intermix numbers and strings as
> >> subscripts
> >> > > to
> >> > > > the same array), but I can't think of a real home run.
> >> Thoughts?
> >> > > >
> >> > > > ===
> >> > > > Gregory Woodhouse
> >> > > > [EMAIL PROTECTED]
> >> > > >
> >> > > > "Perfection is achieved, not when there is nothing more to
> add,
> >> > but
> >> > > > when there is nothing left to take away."
> >> > > > -- Antoine de Saint-Exupery
> >> > > >
> >> > > >
> >> > > >
> >> > > > -------------------------------------------------------
> >> > > > SF.Net email is Sponsored by the Better Software Conference
> &
> >> > EXPO
> >> > > > September 19-22, 2005 * San Francisco, CA * Development
> >> Lifecycle
> >> > > Practices
> >> > > > Agile & Plan-Driven Development * Managing Projects & Teams
> *
> >> > > Testing & QA
> >> > > > Security * Process Improvement & Measurement *
> >> > > http://www.sqe.com/bsce5sf
> >> > > > _______________________________________________
> >> > > > Hardhats-members mailing list
> >> > > > Hardhats-members@lists.sourceforge.net
> >> > > >
> https://lists.sourceforge.net/lists/listinfo/hardhats-members
> >> > > >
> >> > > >
> >> > >
> >> > >
> >> > >
> >> > >
> >> > > -------------------------------------------------------
> >> > > SF.Net email is Sponsored by the Better Software Conference &
> >> EXPO
> >> > > September 19-22, 2005 * San Francisco, CA * Development
> Lifecycle
> >> > > Practices
> >> > > Agile & Plan-Driven Development * Managing Projects & Teams *
> >> > Testing
> >> > > & QA
> >> > > Security * Process Improvement & Measurement *
> >> > > http://www.sqe.com/bsce5sf
> >> > > _______________________________________________
> >> > > Hardhats-members mailing list
> >> > > Hardhats-members@lists.sourceforge.net
> >> > > https://lists.sourceforge.net/lists/listinfo/hardhats-members
> >> > >
> >> >
> >> >
> >> >
> >> > ===
> >> > Gregory Woodhouse <[EMAIL PROTECTED]>
> >> >
> >> > "Design quality doesn't ensure success, but design failure can
> >> ensure
> >> > failure."
> >> >
> >> > --Kent Beck
> >> >
> >> >
> >> >
> >> >
> >> >
> >> >
> >> >
> >> >
> >> > -------------------------------------------------------
> >> > SF.Net email is Sponsored by the Better Software Conference &
> EXPO
> >> > September 19-22, 2005 * San Francisco, CA * Development
> Lifecycle
> >> > Practices
> >> > Agile & Plan-Driven Development * Managing Projects & Teams *
> >> Testing
> >> > & QA
> >> > Security * Process Improvement & Measurement *
> >> > http://www.sqe.com/bsce5sf
> >> > _______________________________________________
> >> > Hardhats-members mailing list
> >> > Hardhats-members@lists.sourceforge.net
> >> > https://lists.sourceforge.net/lists/listinfo/hardhats-members
> >> >
> >> >
> >> >
> >> > -------------------------------------------------------
> >> > SF.Net email is Sponsored by the Better Software Conference &
> EXPO
> >> > September 19-22, 2005 * San Francisco, CA * Development
> Lifecycle
> >> > Practices
> >> > Agile & Plan-Driven Development * Managing Projects & Teams *
> >> Testing
> >> > & QA
> >> > Security * Process Improvement & Measurement *
> >> > http://www.sqe.com/bsce5sf
> >> > _______________________________________________
> >> > Hardhats-members mailing list
> >> > Hardhats-members@lists.sourceforge.net
> >> > https://lists.sourceforge.net/lists/listinfo/hardhats-members
> >> >
> >>
> >>
> >>
> >> ===
> >> Gregory Woodhouse <[EMAIL PROTECTED]>
> >>
> >> "Design quality doesn't ensure success, but design failure can
> ensure
> >> failure."
> >>
> >> --Kent Beck
> >>
> >>
> >>
> >>
> >>
> >>
> >>
> >>
> >> -------------------------------------------------------
> >> SF.Net email is Sponsored by the Better Software Conference & EXPO
> >> September 19-22, 2005 * San Francisco, CA * Development Lifecycle
> >> Practices
> >> Agile & Plan-Driven Development * Managing Projects & Teams *
> Testing
> >> & QA
> >> Security * Process Improvement & Measurement *
> >> http://www.sqe.com/bsce5sf
> >> _______________________________________________
> >> Hardhats-members mailing list
> >> Hardhats-members@lists.sourceforge.net
> >> https://lists.sourceforge.net/lists/listinfo/hardhats-members
> >>
> >
> >
> >
> > ===
> > Gregory Woodhouse <[EMAIL PROTECTED]>
> >
> > "Design quality doesn't ensure success, but design failure can
> ensure
> > failure."
> >
> > --Kent Beck
> >
> >
> >
> >
> >
> >
> >
> >
> > -------------------------------------------------------
> > SF.Net email is Sponsored by the Better Software Conference & EXPO
> > September 19-22, 2005 * San Francisco, CA * Development Lifecycle
> > Practices
> > Agile & Plan-Driven Development * Managing Projects & Teams *
> Testing & QA
> > Security * Process Improvement & Measurement *
> http://www.sqe.com/bsce5sf
> > _______________________________________________
> > Hardhats-members mailing list
> > Hardhats-members@lists.sourceforge.net
> > https://lists.sourceforge.net/lists/listinfo/hardhats-members
>
>
>
> -------------------------------------------------------
> SF.Net email is Sponsored by the Better Software Conference & EXPO
> September 19-22, 2005 * San Francisco, CA * Development Lifecycle
> Practices
> Agile & Plan-Driven Development * Managing Projects & Teams * Testing
> & QA
> Security * Process Improvement & Measurement *
> http://www.sqe.com/bsce5sf
> _______________________________________________
> Hardhats-members mailing list
> Hardhats-members@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/hardhats-members
>
===
Gregory Woodhouse <[EMAIL PROTECTED]>
"Design quality doesn't ensure success, but design failure can ensure failure."
--Kent Beck
-------------------------------------------------------
SF.Net email is Sponsored by the Better Software Conference & EXPO
September 19-22, 2005 * San Francisco, CA * Development Lifecycle Practices
Agile & Plan-Driven Development * Managing Projects & Teams * Testing & QA
Security * Process Improvement & Measurement * http://www.sqe.com/bsce5sf
_______________________________________________
Hardhats-members mailing list
Hardhats-members@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/hardhats-members
