To use the words of M. Forsberg and A. Ranta from [2]:
Well, at first you have to rename the file "formula.bnf" to "formula.cf" since the BNF Converter seems to work only with *.cf files. I prefer it to be suffixed as *.bnf since it is more descriptive.
$ mv formula.bnf formula.cf
Now with the following command, you will create the lexer, parser, printer and skeleton in the C++ language for our arithmetic expressions:
$ bnfc -m -cpp formula.cf
The "-m" options ensures that a make file is created; after the command the following files should be in your directory:
$ ls
In the "Absyn.*" files the AST classes are given; "formula.l" is the required by the lexer generator; similarly, "formula.y" is required by the parser generator. The "Printer.*" files are responsible to traverse the AST, whereas "Test.C" encapsulates a main function and handles file input. At the moment, we do not need the "Skeleton.*" files, but leave them in place.
Now, please compile the sources with the "make" utility:
$ make
To make this step work flawlessly please ensure, that the following tools are installed correctly: g++, flex, bison, latex and dvips. The latter two are not strictly necessary, but it is imperative to have the "g++" compiler, the "flex" lexical analyzer generator and the "bison" parser generator tools to have installed correctly!
Now, your directory should look like this:
$ ls
The executable "testformula" expects an input file with our arithmetic expressions in it; please prepare such a file, e.g.:
$ echo "(a+b) * sin(-c)" > formula.inp
Now, feed to the executable the input file containing our test formula; if everything goes well, you should get the following output:
$ ./testformula
Bravo! You have created a parser which can interpret arithmetic expressions correctly and which produces the appropriate abstract syntax tree; further this tree is traversed such that a "linearized" version of it is printed, which produces the original input.
Now, it is up to us (you!) to make the necessary modifications in "Printer.C" such that instead of the "linearized" AST a "postfixed" AST is produced. By doing this, we will achieve our primary goal, of creating a first rough version of our infix to postfix converter.
We will demonstrate BNFC (the BNF Converter), a multi-lingual compiler tool. BNFC takes as its input a grammar written in LBNF (Labelled BNF) notation, and generates a compiler front-end (an abstract syntax, a lexer, and a parser). Furthermore, it generates a case skeleton usable as the starting point of back-end construction, a pretty printer, a test bench, and a Latex document usable as language specification.Now, the real fun starts: Prepare an empty directory, where you should copy the "formula.bnf" grammar into. Further ensure that the BNF Converter tool is installed on your Unix-like system; see [5] for further details.
Well, at first you have to rename the file "formula.bnf" to "formula.cf" since the BNF Converter seems to work only with *.cf files. I prefer it to be suffixed as *.bnf since it is more descriptive.
$ mv formula.bnf formula.cf
Now with the following command, you will create the lexer, parser, printer and skeleton in the C++ language for our arithmetic expressions:
$ bnfc -m -cpp formula.cf
The "-m" options ensures that a make file is created; after the command the following files should be in your directory:
$ ls
» Absyn.C formula.cf formula.tex Makefile Printer.C Skeleton.C Test.C Absyn.H formula.l formula.y Parser.H Printer.H Skeleton.H
In the "Absyn.*" files the AST classes are given; "formula.l" is the required by the lexer generator; similarly, "formula.y" is required by the parser generator. The "Printer.*" files are responsible to traverse the AST, whereas "Test.C" encapsulates a main function and handles file input. At the moment, we do not need the "Skeleton.*" files, but leave them in place.
Now, please compile the sources with the "make" utility:
$ make
To make this step work flawlessly please ensure, that the following tools are installed correctly: g++, flex, bison, latex and dvips. The latter two are not strictly necessary, but it is imperative to have the "g++" compiler, the "flex" lexical analyzer generator and the "bison" parser generator tools to have installed correctly!
Now, your directory should look like this:
$ ls
» Absyn.C formula.cf formula.ps Lexer.o Parser.o Skeleton.C Test.o Absyn.H formula.dvi formula.tex Makefile Printer.C Skeleton.H Absyn.o formula.l formula.y Parser.C Printer.H Test.C formula.aux formula.log Lexer.C Parser.H Printer.o testformula
The executable "testformula" expects an input file with our arithmetic expressions in it; please prepare such a file, e.g.:
$ echo "(a+b) * sin(-c)" > formula.inp
Now, feed to the executable the input file containing our test formula; if everything goes well, you should get the following output:
$ ./testformula
» Parse Succesful!
»
» [Abstract Syntax]
» (Program [(Formula [(Fact (Term (Var "a") [AddOp] (Var "b")) [MulOp] (Func "sin" [(NVar "c")] ))])])
»
» [Linearized Tree]
» (a + b) * sin (- c)
»
» [Abstract Syntax]
» (Program [(Formula [(Fact (Term (Var "a") [AddOp] (Var "b")) [MulOp] (Func "sin" [(NVar "c")] ))])])
»
» [Linearized Tree]
» (a + b) * sin (- c)
Bravo! You have created a parser which can interpret arithmetic expressions correctly and which produces the appropriate abstract syntax tree; further this tree is traversed such that a "linearized" version of it is printed, which produces the original input.
Now, it is up to us (you!) to make the necessary modifications in "Printer.C" such that instead of the "linearized" AST a "postfixed" AST is produced. By doing this, we will achieve our primary goal, of creating a first rough version of our infix to postfix converter.
No comments:
Post a Comment