Re: nested alts and EBNF/BNF conversion (pull request #146)

"C. M. Sperberg-McQueen" <cmsmcq@blackmesatech.com> writes:
> Two points occur to me which may be worth mentioning in connection with
> PR #146:
>
> First: Neither the spec nor the draft paper seem to mention nested sets
> of alternatives.  As I understand the term 'BNF', the grammar
>
>     S = 'a', ('b' | 'c'+), 'd'.
>
> is not in BNF.  And it is certainly not handled directly by Earley's
> description of his parsing algorithm.
>
> Perhaps it should be mentioned?

The document does say that EBNF notations provide a number of syntactic
conveniences including to “make … subexpressions optional, repeatable,
or both”. I think that covers nested sets of alternatives.

But if you think it should be called out more explicitly, I’m happy to
do that.

> Second: I have found it informative to try to make a compact list of the
> various rewrite rules proposed.  Perhaps others will also find it
> useful.

I struggled for a long time, on a couple of different days, to understand
the tabular presentation you suggested. It just didn’t work for me.
Perhaps I just didn’t understand the notation. I think I was especially
confused by the omission of some rows. For example,

{ABCDEF} f? => f-option

  {A} f-option = f | . 
  {B} f-option = f | (). 
  {E} f-option = () | f. 
  {F} f-option =  | f. 

It’s true that C and D don’t provide a *different* definition of this
rule than B, but leaving out the row entirely made it feel like those
sets don’t *have* that rule, which isn’t the case.

I don’t want to suggest the table isn’t valuable, but I think you’re
going to have to explain it to me more slowly.

                                        Be seeing you,
                                          norm

--
Norm Tovey-Walsh
Saxonica

Received on Sunday, 8 January 2023 09:46:42 UTC