Workshop: A modern approach to parsing

(This workshop was held online on as part of CyberSaturdays of TkkrLab. The recording of the workshop. Afterwards, I was a little disappointed about the workshop, because it turned out to be more of a lecture. I also realized that I should have spend more time on preparing the workshop instead of focusing on this materials and the software. I also realized that, to make it more accessible for people who do not know anything about parsing, I should have started with the expression example, which starts around 22:22 and from their explain priorities, show the abstract syntax tree, and explain how to develop the grammar in a number of steps. And this followed by some more about the history of parsing and how I came to develop IParse. (There were also some technical issues with the sound, which forced me to use a MacBook from someone else to give the presentation, not allowing me to show some of the commands.)

Introduction and history of parsing
Tutorial on writing grammars with an online interactive parser
Presentation of IParse
Presentation of RawParser

Introduction: What is parsing

Parsing is the process of

reading a textual input
according to a formal grammar
into an abstract syntax tree

The abstract syntax tree can used:

As input for an interpreter
First step of a compiler

Parsing algorithms

In the early days parsing algorithms were designed with:

limited amount of memory
file based: reading character-by-character
⇒ No back-tracking

Two passes:

Lexical: regular grammars
Syntaxical: contex-free grammars

LL parser

LL stands for Left-to-right, Leftmost derivation.
Top-down parser

LALR parser

LALR stands for Look-Ahead, Left-to-right, Rightmost derivation in reverse.
bottom-up parser

Common tools

Yacc (GNU Bison) and Lex (Flex)

Common problems:

Lots of grammar rules
Shift/reduce conflicts
Scanner states

Modern approach

Input in memory
Memory no longer an issue
Scanner called from parser
User-friendly grammar specification
Back-tracking with memoization

Note:

Highest performance: hand-crafted parsers
Good for (interpretted) scripting languages
(MySample editor)
Spirit Parser Framework
nearley.js (playground)

Interactive parser

an online interactive parser

IParse

git clone https://github.com/FransFaase/IParse
cd IParse/software
g++ -fno-operator-names all_IParse.cpp -o IParse
cd ..
software/IParse software/c.gr others/scan.pc -p scan_pc_output
diff scan_pc_output others/scan_pc_output
software/IParse software/c.gr others/scan.pc -unparse unparse_scan.pc
diff unparse_scan.pc others/unparse_scan.pc

RawParser

git clone https://github.com/FransFaase/RawParser
cd RawParser/src
gcc RawParser.c -o RawParser
./RawParser

Author: Frans
Personal website
email address