Re: reduce/reduce conflict in CSS2?

Andreas Schlapbach wrote:


> Dear Group
>
> The CSS 2 Grammar (http://www.w3.org/TR/REC-CSS2/grammar.html) has the
> following rules:
>
..


I would like to summarize the discussion on this subject I was having on
comp.infosystems.www.authoring.stylesheet


I wrote:
| The CSS 2 specification defines the grammar as being LL(1)
| so this should work.


Arjun Ray <aray@nmds.com.invalid> wrote:


No, the CSS2 spec simply asserts that it's LL(1).


I wrote:
|The given lexical and grammar rules suggest
| that it should be straight forward.


Arjun Ray wrote:


Only in theory. With EBNF grammars, quite often you're better off
writing a recursive-descent parser by hand. Exapnding to yacc/bison
format can be problematic.


..


Yes, but the [reduce/reduce] problem is actually more subtle. It has to do
with the productions for simple_selector in the spec:


    simple_selector
        : element_name? [ HASH | class | attrib | pseudo ]* S*
        ;


Note that all the parts are separately "nullable", implying that
simple_selector itself is nullable. As combinator is also nullable,
your constructed combinator_simple_selector_0toN is nullable both by
construction from its parts and by definition! (This is a variant of
the classic nullable-list-within-nullable-list reduce/reduce conflict
in yacc grammars. See, e.g. John Levine's 'Lex and Yacc' book from
O'Reilly.)


The "fix" that I found was to undo the nullability of simple_selector.
For instance, taking away the /* empty */ branch of maybe_element_name


maybe_element_name
    : IDENT
    | '*'
    ;


eliminated all conflicts in the grammar!


So, I'd suggest doing something similar in your grammar. Basically
the rule in the CSS spec


      simple_selector
        : element_name? [ HASH | class | attrib | pseudo ]* S*
        ;


is too loose, allowing parts that are separately nullable to be both
nullable at the same time also. It needs to look something like this:


    simple_selector
        : element_name [ HASH | class | attrib | pseudo ]* S*
        | [HASH | class | attrib | pseudo ]+ S*
        ;


(Note the +)


Good luck!




I wrote as a followup:


Thanks that helped.


BTW: If anybody is interested in the flex/bison files, please let me know


EOT


Sidenote: The sample stylesheet given in the appendix A is bogus:
http://jigsaw.w3.org/css-validator/validator?uri=http%3A%2F%2Fwww.iam.unibe.ch%2F%7Eschlpbch%2Fsample.css&warning=2&warning=0
-----------------


The only problem I'm now facing is how to build up a DOM-tree like data
structure with this grammar, i.e. how to define the semantic actions so I
end up with a nice syntax tree


All the examples I found on the net don't aim to build up a complete trree,
i.e. preserve all the content of the nodes. Most within the nodes part of
the data gets processed (e.g $$=$1 + $2) and then discarded.


A nice example would be appreciated.


Andreas


--
    Andreas Schlapbach schlpbch@iam.unibe.ch
    http://iamexwiwww.unibe.ch/studenten/schlpbch
                                  "/home sweet /home."

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