lfs-book/appendixa/bison-desc.sgml

<sect2>
<title>Contents</title>

<para>
The Bison package contains the bison program.
</para>

</sect2>

<sect2><title>Description</title>

<para>
Bison is a parser generator, a replacement for YACC. YACC stands for Yet
Another Compiler Compiler. What is Bison then? It is a program that
generates a program that analyses the structure of a textfile. Instead
of
writing the actual program you specify how things should be connected
and with
those rules a program is constructed that analyses the textfile.
</para>

<para>
There are alot of examples where structure is needed and one of them is
the
calculator.
</para>

<para>
Given the string :
</para>

<blockquote><literallayout>
        1 + 2 * 3
</literallayout></blockquote>

<para>
You can easily come to the result 7. Why ? Because of the structure. You
know
how to interpretet the string. The computer doesn't know that and Bison
is a
tool to help it understand by presenting the string in the following way
to the compiler:
</para>

<blockquote><literallayout>

            +
           / \
          *   1
         / \
        2   3
</literallayout></blockquote>

<para>
You start at the bottom of a tree and you come across the numbers 2 and
3 which are joined by the multiplication symbol, so the computers
multiplies 2 and 3. The result of that multiplication is remembered and
the next thing that the computer sees is the result of 2*3 and the
number 1 which are joined by the add symbol. Adding 1 to the previous
result makes 7. In calculating the most complex calculations can be
broken down in this tree format and the computer just starts at the
bottom and works it's way up to the top and comes with the correct
answer. Of course, Bison isn't only used for calculators alone.
</para>

</sect2>