Re: reduce/reduce conflict in CSS2?

Andreas Schlapbach <>
4 Jan 2001 00:58:58 -0500

          From comp.compilers

Related articles
reduce/reduce conflict in CSS2? (Andreas Schlapbach) (2000-12-31)
Re: reduce/reduce conflict in CSS2? (Andreas Schlapbach) (2001-01-04)
Re: reduce/reduce conflict in CSS2? (Martin von Loewis) (2001-01-04)
Re: reduce/reduce conflict in CSS2? (Mike Dimmick) (2001-01-04)
| List of all articles for this month |

From: Andreas Schlapbach <>
Newsgroups: comp.compilers
Date: 4 Jan 2001 00:58:58 -0500
Organization: bluewin
References: 00-12-121
Keywords: parse
Posted-Date: 04 Jan 2001 00:58:58 EST

Andreas Schlapbach wrote:

> Dear Group
> The CSS 2 Grammar ( has the
> following rules:

I would like to summarize the discussion on this subject I was having on

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

Arjun Ray <> 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:

        : 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

The "fix" that I found was to undo the nullability of simple_selector.
For instance, taking away the /* empty */ branch of 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

        : 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:

        : 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


Sidenote: The sample stylesheet given in the appendix A is bogus:

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 Schlapbach
                                  "/home sweet /home."

Post a followup to this message

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