I don't want to sound pedantic, but the very fact that a thing such as perly.y exists actually proves that Perl is a CFL. Tools such as YACC, Bison and the like are used to create parsers for context free languages. This means that Perl's grammar defines a CFL.

With all due respect this is utterly and completely wrong. Please review Red Dragon for a thorough explanation.

A CFL/CFG cannot express the requirement that a variable must be declared before it is used. Furthermore a CFL/CFG cannot express the issue of arbitrarily nested constructs. All of these can be definitively proved using proper regular expressions (not perls irregular expressions) which are actually context free.

A YACC BISON grammer express the context free components of a language specification. The symbol table manipulation and extraneous such code that are attached to the various grammatical rules handle the non context free part of the language.

The fact is that most languages are primarily context free, but that they almost always have some aspect of context involved. Tools like Bison / YACC are used to simplify (and optimise) the process of constructing the context free part of the grammar. (And to be honest hand constucting LR parsers is very very difficult. LR parsers are preffered because they dont suffer from the problem that most recursive descent parsers do, that of not being able to handle left recursion.)

To the OP: There are very few useful GPPL languages (general purpose programming langauges) that are truly context free. In fact to my knowledge there are none. But I expect that im wrong on that. Nevertheless ANY language that uses arbitrarily nested parenthesis (as in to any level of nesting), or that requires that identifiers are declared before being used (both of which Perl requires) is NOT context free. Thus all of the following are not context free: Perl, C, C++, Java, Turing, Ada, Pascal, Fortran, Cobol, Modula-2...

UPDATED:As thraxil and thelenm corrected me, the struck out text is wrong. I got carried away and mixed up proper regular expressions and context free grammars. Thanks and sorry.

--- demerphq
my friends call me, usually because I'm late....
I think I need a vacation

In reply to Re: Re: Re: original definition vs final language by demerphq
in thread original definition vs final language by dystrophy

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.