Grammars and Parsers

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[1]:

“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].

Example of Parsing
Image via Wikipedia

“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:

Continue reading “Grammars and Parsers”

Advertisements