Re: [css3-syntax][css3-page] The mixed declaration/at-rule syntax is not LL(k)

On Sun, Feb 3, 2013 at 3:48 PM, Simon Sapin <simon.sapin@kozea.fr> wrote:
> Le 03/02/2013 14:41, Tab Atkins Jr. a écrit :
>> Technically, the parser is a deterministic pushdown automata, so it
>> is, by definition, possible to represent with a context-free grammar.
>> Can you elaborate on what problems you've been having with the
>> declaration branches?
>
>
> My knowledge of parsing theory is weak, but "not all context-free languages
> are LL(k) languages."
>
> Source: https://en.wikipedia.org/wiki/LL%28k%29

Ah yes, you're right.  Sorry.


> I’m talking about the "page" production of the grammar in css3-page:
> http://dev.w3.org/csswg/css3-page/#syntax-page-selector
>
> The interesting part is:
>
>     '{' S*
>     [ [ declaration? ';' S* ] | page_margin_box ]*
>     [ declaration ]?
>     '}'
>
> So for example after you’ve consumed '{' based on the next token you can
> know if what you have next is an at-rule or a declaration. But for
> declarations at this point, you need unbounded look-ahead to decide whether
> to go into the second line’s branch (a declaration ending with ';') or the
> third line’s branch (declaration ending with '}')
>
> The trick is, it doesn’t matter because what you do with a declaration is
> the same in either case. But I don’t know how to express that in a grammar.

I think this would work without unbounded lookahead:

page-block-body = '' | at-rule page-block-body | page-declaration;
page-declaration= declaration [ ';' page-block-body? ]?

It captures that after a list of declarations, you can either end the
rule immediately, add a trailing semicolon, or add a semicolon and
continue from there, and requires finite, small lookahead.

> Then again: should we care? I’d like to have feedback from other
> implementers.

I don't care all that much, because WebKit uses a state-machine
parser.  But I'm not sure what other browsers think.

~TJ

Received on Monday, 4 February 2013 00:18:27 UTC