Syntaxes one can describe using BNF?

171 Views Asked by At

How can one tell if certain syntax is describable by BNF? Is it anything i can describe with a context free grammar?

So are programming languages like C,java.. describable by BNF? or does it depend on the language?

What about something like the language of all polynomials described as follows: (2x +x3 -4 + x3) is x^2+ x^3 -4 +x^3?

1

There are 1 best solutions below

0
On BEST ANSWER

Since the BNF is just a way to illustrate a context-free grammar you can describe all context-free grammars using BNF.

A BNF that can produce polynomials could look like this

\begin{align} &<\operatorname{expr}> &::= &(<\operatorname{expr}><\operatorname{op}><\operatorname{expr}>) \; |\; <var> \\ &<\operatorname{op}> &::= &+ \; | \; - | \; * \\ &<\operatorname{var}> &::= &0 \; | \;1 \; | \; X \\ \end{align}

Languages like C++ are not context-free, thus they can't be represented by a BNF. Here's a very good explanation why on Stackoverflow.