My blog about programming and other stuff

Parser nomenclature

My systematic way to parser theory

Parsers and compilers have always fascinated me. In the very beginning they were just buzzwords standing for the magical black boxes that turn the code of your favourite programming language into something that your computer can execute.

Generating machine executable code sure is amongst the most important use cases for parsers and compilers. But this is not the whole story. Basically every occasion very structured input of some sort has to be transformed into structured output, a parser/compiler setup is needed.

At first I was willing to accept the black box view and didn’t bother too much to dig deeper. As of lately I feel more and more interested in the topic. Over the last months I caught myself reading some articles or tutorials about parsers. The frequency of those occasions is increasing. In the next time I want to devote a couple of posts to parser. I’ll focus on parsers. Compilers are an even more complicated topic and I feel that it would overwhelm me to tackle it now.

I plan to have a more systematic approach to the topic. A first step is to gain an overview of the terminology landscape. When you read about parsers certain words will come up over and over again and it is mandatory to know them. In the following I’ll list some of them, mainly as a reference for myself.

Terminology

General

Word	Meaning
Backtracking	The parser moves back (rewinds) the token stream
LL(k) grammar	If a LL(k) parser exists that can parse this grammar without backtracking

Parser types

Acronym	Description
LL(k) parser	Left to right parser with leftmost derivation that uses k tokens for lookahead
LR(k) parser	Left to right parser with righmost derivation in reverse with k peek tokens
Recursive descent parser	A parser that is made out of mutually recursive procedures calling each other as they consume the tokens
Top-down parser	Parser starting with the smallest details first
Bottom-up parser	Parser starting with the overal structure first
Shift reduce parsers	Table-driven bottom-up parsing
Precedence parsers	Bottom-up parser for context-free grammars that can be used only by simple precedence grammars
Deterministic parser	A parser that does not require backtracking

Grammars

Word	Meaning
Formal grammar	A set of production rules for strings in a formal language
Context free grammar	A set of production rules that describe all possible strings in a given formal language

Closing words

I know that this article is stil fairly incomplete. The area of parser and their theory is a pretty vast one. As a first go I was throwing everything in that I have heart about or I stumbled upon while reading about parsers. I plan to come back to hear and update this article while I learn more about parsers.