Re: How to construct a BNF for a language mechanically and incrementally?

[Hans Aberg]

On 29 Dec 2009, at 03:54, Peng Yu wrote:

> It seems to me that to use bison I have to have a BNF first. I'm
> reading Programming Language Pragmatics 3rd Ed (PLP3). What is not
> clear to me is that how to construct the BNF for a language? Based on
> my reading of PLP3, I haven't found a formal way to construct BNF.
> What I understand is that, to construct a BNF, I'll have to think
> about some examples written in the language and write the BNF based on
> my experience.
>
> A language definition is usually evolving. It is not clear to me
> whether it always affects the BNF incrementally if the language is
> changed little by little.

Much depends on what you want to do, and the methods are largely  
empirical.

If you want to implement an already existing language, there is a  
chance there already is a grammar, if such can be done. Search on the  
net for "<language> Yaccable (LALR) grammar" and such. Check out the  
Usenet newsgroup comp.compilers and its FAQ published there monthly.

I can still be difficult to produce a LALR(1) grammar. For C++/C see
 http://www.parashift.com/c++-faq-lite/compiler-dependencies.html#faq-38.11
 http://www.quut.com/c/ANSI-C-grammar-y.html
For some languages, like Fortran, Bison/Flex are not a good at all.

If you want to design your own language, it may suffice with starting  
with a small example, such as the calculator in the Bison manual, and  
then expand. Ideas can be input from sources like the grammar-like  
appendix in the C++ standard, and other sources of the type of  
language you want to design.

 Hans