8
$\begingroup$

I was reading the paper Fundamental Concepts in Programming Languages by C. Strachey the other day, wherein I read something that was quite strange to me. Quoting directly (with the strange part highlighted by me):

Faced with the situation as it exists today, where there is a generally known method of describing a certain class of grammars (known as BNF or context-free), the first instinct of these mathematicians seems to be to investigate the limits of BNF—what can you express in BNF even at the cost of very cumbersome and artificial constructions? This may be a question of some mathematical interest (whatever that means), but it has very little relevance to programming languages where it is more important to discover better methods of describing the syntax than BNF (which is already both inconvenient and inadequate for ALGOL) than it is to examine the possible limits of what we already know to be an unsatisfactory technique.

Is there a specific reason the author considers the BNF to be an unsatisfactory technique for describing languages? Could it be because you can only describe syntax and not semantics with a single BNF grammar (though, you can extend it to describe operational semantics via turning it into an attribute grammar)?

Improve this question
$\endgroup$
1

2 Answers 2

Reset to default
3
$\begingroup$

You mention one reason.

The other reason is that the syntax of programming languages isn't context-free, unless you define syntax to be that which can be, or is, described by a context-free grammar.

When Strachey's paper was written, the syntax of a new language, Algol 68, was being defined in a new formalism, two-level grammars, that was used to describe syntactic validity in full, including many things that, brainwashed by the "BNF is the syntax" meme, many of us do not consider part of syntax at all, such as all variables needing to be declared before use.

Most of us won't go that far, but will still agree that non-context-free syntactic features in programming languages exist.

Improve this answer
$\endgroup$
3
$\begingroup$

I do not think that the semantics play a role. Your quote asks for "discover better methods of describing the syntax than BNF." Of course, things like function and variable names form part of the syntax. With BNF you cannot, for example, distinguish a language where variables must be decalred before usage from one where you can use undeclared variables. These things must be explained in accompanying text usually, which is not perfect.

Improve this answer
$\endgroup$
3
  • $\begingroup$ "These things must be explained in accompanying text usually" -- there are formal semantics, though. $\endgroup$
    – Raphael ♦
    May 29, 2016 at 8:30
  • 1
    $\begingroup$ The question whether a program with a certain identifier at a certain position is legal or not for me is syntax, not semantics. Semantics is the meaning, syntax is describing the formal language of legal programmes. Therefore I think my example describes a part of syntax usually describred in text form. $\endgroup$
    – Peter Leupold
    May 29, 2016 at 10:53
  • 1
    $\begingroup$ Programming language terminology aside, the branch of TCS called formal semantics is what you can use there. You can call is syntax afterwards, if you wish (though I'd consider that silly); the point is that natural language is not the only alternative to specify these things. $\endgroup$
    – Raphael ♦
    May 29, 2016 at 11:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.