Q1. reducing grammar redundancy

"valentin tihomirov" <spam@abelectron.com>
20 Feb 2005 16:50:32 -0500

          From comp.compilers

Related articles
Q1. reducing grammar redundancy spam@abelectron.com (valentin tihomirov) (2005-02-20)
Re: Q1. reducing grammar redundancy wyrmwif@tsoft.org (SM Ryan) (2005-02-28)
RE: Q1. reducing grammar redundancy ralfla@microsoft.com (Ralf Lammel) (2005-02-28)
Re: Q1. reducing grammar redundancy vidar@hokstad.name (Vidar Hokstad) (2005-02-28)
Re: Q1. reducing grammar redundancy branco.medeiros@gmail.com (2005-02-28)
Re: Q1. reducing grammar redundancy spam@abelectron.com (valentin tihomirov) (2005-02-28)
| List of all articles for this month |

From: "valentin tihomirov" <spam@abelectron.com>
Newsgroups: comp.compilers
Date: 20 Feb 2005 16:50:32 -0500
Organization: Compilers Central
Keywords: parse
Posted-Date: 20 Feb 2005 16:50:32 EST

Call me an optimization paranoid but...I have a question regarding the issue
of grammar generalization to be used in language tools.

[1] I'm familiar with several compiler compilers. The issue is in grammar
rules organization. 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.

[2] The issue conserning SGML redundancies. Please consider a basic XML
        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? How can it be written in a more optimal form acceptable by parser?
[Bottom up parsers' speed doesn't depend on the number of rules in the grammar. There's
no reason to try to shrink them. -John]

Post a followup to this message

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