in reply to Perl not BNF-able??

Note that something simple as: 
sub hello();
sub hello() {print "world"}

[download]
isn't context-free (assuming the programmer is free to pick the subroutine names, and the grammer isn't going to list all possible subroutine names), and hence certainly not BNF-able.

Not even a much simpler (with respect to the language's grammar) language like C is context-free, for the same reason: forward declarations. In general, anything you have a language construct where you're forced to repeat something that wasn't matched by a terminal in the grammar (kind of like using \1 in a regex) your grammar isn't context-free - and hence, BNF will not be powerful enough.

Replies are listed 'Best First'.
Re^2: Perl not BNF-able??
by ikegami (Patriarch) on Jul 04, 2005 at 20:12 UTC

    Why do you say that snippet is not BNF-able? Parts of Perl cannot be expressed by BNF, but your snippet is not one of them as far as I can tell.

    statement : sub_proto
statement : sub_def

term      : anon_sub

sub_proto : ws? "sub" ws? sym_name proto? ws? ";"
sub_def   : ws? "sub" ws? sym_name proto? ws? block

anon_sub  : ws? "sub" block

sym_name  : ident "::" sym_name
sym_name  : ident

    [download]
[reply]
[d/l]
      So, where's the requirement that both the proto and the definition have the same signature? It's trivial to write BNF for a proto, it's trivial BNF for the definition (given the BNF for the block). It's impossible to use BNF for the requirement that the signatures (that is, name and prototype) are the same.

      Your BNF is ok if you're allowed to write: 

      sub hello($);
sub hello() {print("Hello, world");}

      [download]
      But you aren't. The signatures should be the same - and that's unexpressable with BNF.
[reply]
[d/l]

        BNF dictates syntax, and the above snippet is syntactically correct. perl -c agrees by saying "syntax OK".

        The following is syntactically correct C++:

        Type1 p;
Type2 q;
p = q;

        [download]

        Are Type1* and Type2* assignment compatible? It doesn't matter as far as BNF is concerned because it only specifies the syntax.

        The error in your Perl snippet and the error in the above C++ snippet (if any) are semantic errors. Semantic analysis is usually done independant of parsing. Semantic analysis checks things such as types, and whether forward declerations have been resolved. These are things that don't affect the compiler's understanding of the code, but affect whether the code is consistent (valid) when looking at the bigger picture. BNF does not have a role in semantic analysis.

        BNF is therefore sufficient to handle the Perl in your post.

[reply]
[d/l]
[select]
Re^2: Perl not BNF-able??
by anonymized user 468275 (Curate) on Jul 04, 2005 at 13:57 UTC
    Yes, the context-free idea isn't a logical necessity for expressing in BNF, because that alone can be conquered by expressing the different context types as alternative BNF definitions.

    Rather, the most compelling arguments that have been made in reply here come from those perl syntax elements which overpower the nearby context, such as (amongst other examples given by various people) the e-regexp modifier.

    One world, one people

[reply]
      Yes, the context-free idea isn't a logical necessity for expressing in BNF, because that alone can be conquered by expressing the different context types as alternative BNF definitions.
      How so? Could you give a BNF snippet that would express how to generate a forward declaration of a subroutine that matches the signature of the actual subroutine definition?
      Rather, the most compelling arguments that have been made in reply here come from those perl syntax elements which overpower the nearby context, such as (amongst other examples given by various people) the e-regexp modifier.
      The /e regexp modifier? In which way does that "overpower" nearby context? Couldn't that construct be parsed with the following BNF snippet: 
      non-a-slash:    # string that doesn't contain a non escaped slash
SUBSTITION:     non-eval-substition | eval-substitution
non-eval-substitution:
               's' '/' not-a-slash '/' not-a-slash '/' non-e-modifiers
+(*)
eval-substitution:
               's' '/' not-a-slash '/' slashless-code '/' e-modifiers(
+*)
non-e-modifiers: 'x' | 's' | 'm' | 'g' | 'x' | 'i'
e-modifiers:     'e' | non-e-modifiers

      [download]
      Assuming you could create BNF for Perl code (and then you can create BNF for Perl code that doesn't contain a slash).

      Grammars expressed in BNF can be parsed with recursive decent parsers (which do not have a fixed lookahead) - and if you can create a parser for all other Perl constructs, I can parse the difference between s/// and s///e.

[reply]
[d/l]
[select]

In Section Seekers of Perl Wisdom