Let’s build a parser to math expressions. It’s better start the job in very a simple way: process addition expressions like ‘1 + 1’.
Well… As the old Chinese saying goes, “a journey of one thousand miles begins with one tiny step”.
A Little Bit About Parsers
According to Grune and Jacobs:
“Parsing is the process of structuring a linear representation in accordance with a given grammar. [..] This ‘linear representation’ may be a sentence, a computer program, [..] in short any linear sequence in which the preceding elements in some way restrict the next element”[1, p. 3].
“To a computer scientist ‘1 + 2 * 3’ is a sentence in the language of ‘arithmetics on single digits’ [..], its structure can be shown, for instance, by inserting parentheses: (1 + (2 * 3)) and its semantics [i.e. its meaning] is probably 7”[1, p. 7].
We use a parser to build an expression tree. This tree contains the elements of a sentence according with the structure of a given grammar and in the correct order (afterwards we will need an interpreter that uses the tree to extract the semantic of the sentence).
And in order to implement a parser, we have to: