Re: Q1. reducing grammar redundancy

valentin tihomirov wrote:


<snip>
> [1]


<snip>
> In the desrcribing languages like LISP and XML it is appealing
> not to mention they have some general "element" pattern. How can I
> benefit from this fact eliminating the redundancy:
> sqrt-> LPAREN "sqrt" NUM RPAREN; // LISP element synthax
> plus -> LPAREN "plus" NUM NUM RPAREN;
>
> Is there a known technique to define a basic "element" rule and
> derive all the remaining rules by tuning this one? I mean, the
> endless parenthesis and enforcing the tag name presence.


<snip>
> [2] The issue conserning SGML redundancies. Please consider a basic
> XML element:
> element -> OPEN_PAREN "element" CLOSE_PAREN // opening tag
                              element // body
                          OPEN_PAREN SLASH "element" CLOSE_PAREN; // closing tag


> As you see, the closing tag duplicates the appearance of "element"
> keyword. I may mistake easily here, looks like a context-sensetive
> rule is needed here in order to avoid the repetition. How can it be
> written in more compact way?
<snip>


Although (as far as I know) there's no parser providing such
"facility", both issues can be resolved by pre-parsing the grammar, in
a way that an extended syntax could be used to eliminate
redundancy. Although, as our esteemed moderator says, such redundancy
is inexpensive to the parser, it may hinder clarity to the developer.


A possible construct to eliminate redundancy such as shown in the
first example could be a template-like production:


element(content) -> LPAREN content RPAREN; // the template
sqrt -> element("sqrt" NUM);
plus -> element("plus" NUM NUM);


In the second example of redundancy (contextual elements that
appear in the same production), a local-production element can
be specified:


element -> OPEN_PAREN the_tag:"element" CLOSE_PAREN
                      element
                      OPEN_PAREN SLASH the_tag CLOSE_PAREN;


As can be seen, the local-production gives meaning to the element(s)
it introduces, but, better still, the pre-parser can detect its
misuse.


The pre-parser would convert such constructs to the redundant ones we
know and love. Of course, such mutations may introduce more problems
than the ones they supposedly solve. An issue that comes to mind is
the abuse of automatically generated productions, which may make it
difficult to debug the grammar later on (although it seems that
auto-generated-internal productions are relatively common. Even yacc
uses them, I guess).


Best regards,


Branco.

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