Re: Syntax diagram driven parser

Eric O'Dell in the thread about syntax diagrams v. BNF wrote:


> I'd say BNF is good enough, but I wouldn't mind having a visual tool
> that could take syntax diagrams and produce the corresponding BNF,
> just as a convenience. (Going the other way is a trivial exercise, but
> I can't think of any tools off the top of my head that do it.)


I have a disk somewhere with a copy of Mira, a circa 1990 tool that
generated syntax diagrams from ELL grammars (LL grammars + regular
expressions). I think Visual Parse++ will do the same with ELR
grammars. (The general class is often called EBNF. BTW, the E
(regular expressions) in EBNF doesn't buy one any "power" in grammar
theory, it just makes the grammars easier to write.)


For syntax diagrams that correspond to "structured programs" (i.e. no
multi-entry cycles only true loops)--the precise term is (forests of)
reducible graphs, it is possible to trivially transform a syntax
diagram into an EBNF textual representation.


As I recall, irreducible graphs can also be transformed, but it is
more work. Essentially, you have to compute all the path expressions
from the head (start points) of the graph to its tail(s) (end points).
The fact that any finite labelled graph is merely a representation of
a fsm, proves that the set of all paths (from head to tail) is simply
a regular expression.


However, if you allow your graphs to merge (share heads or tails), you
might be able to create syntax diagrams that correspond to no normal
grammar. There the question depends upon the labelling. The heads of
the graphs are generally labelled with the name of the production
which the parser is trying to match. The tail of the graph (the point
where the fsm accepts), is the point where the parser reduces.


Now, there are two conventions that can be followed. One is that the
tail is unlabelled (other than being marked as a reduction point) and
the parser simply reduces to the production it was trying to match at
the head of the graph. In that case, merging graphs buys one nothing.
One can split the merged portion of the graph into multiple copies,
one for each head that share the merged tail. That reduces the
problem to the previous case of a forest of singly labelled
(ir)reducible graphs.


Alternately, the tail can be labelled with the rule the parser will
reduce at that point. In that case, you could have a parser that is
looking for a non-terminal "x" and upon matching a regular expression
decides to reduce a different non-terminal "y". I have no idea what
class of languages that corresponds to, my guess is linear bounded
automata, but that is only a hunch. (I guess you could apply this
bizarre labelling even with unmerged graphs and achieve the same
result.)


However, this is probably much more than most readers will want to
consider, so I will stop.


Hope this helps,
-Chris


*****************************************************************************
Chris Clark Internet : compres@world.std.com
Compiler Resources, Inc. Web Site : http://world.std.com/~compres
3 Proctor Street voice : (508) 435-5016
Hopkinton, MA 01748 USA fax : (508) 435-4847 (24 hours)

Return to the comp.compilers page.
Search the comp.compilers archives again.