Category Archives: TBP

Trace Based Parsing

The state of the Trail parser generator

White Easter Snow came back, if only for a brief moment, to remind me laying Trail to rest until next winter… x + + + + + + + + + – – – – – – – – – … Continue reading

Posted in Algorithms, Grammars, Langscape, Parsing, TBP, Trail | Leave a comment

LL(*) faster than LL(1)?

No jumps When I began to work on EasyExtend in 2006 I grabbed a Python parser from the web, written by Jonathan Riehl ( it doesn’t seem to be available anymore ). It was a pure Python parser following closely … Continue reading

Posted in Algorithms, Grammars, Parsing, Python, TBP | 4 Comments

Token Tracers

When I started programming EasyExtend in 2006 one of the major problems was the correct grammar -> NFA translation. I used big grammars and testing for correctness required lots of source code. The first heuristics I used was ugly and … Continue reading

Posted in EasyExtend, Parsing, TBP | Leave a comment

Restricted backmatching

In practice we often encounter situations when our preferred approach to problem solving breaks down. Just look at the recent Google implementation of  a regexp engine RE2, created by Russ Cox who has written a revival paper for Thompson NFAs  … Continue reading

Posted in TBP | Leave a comment

About CST interpolation

Eli Bendersky has written a short overview article about Pythons _ast module which is supposed to make working with parse trees simpler by transforming them into other trees i.e. abstract syntax trees. In this article I want to talk a … Continue reading

Posted in Algorithms, Parsing, TBP | 3 Comments

CodeTemplates – a fresh look on code transformations

This is the first part of a two part article series about CodeTemplates. CodeTemplates are a code transformation technique that suggests an alternative to common syntactic as well as lexical macros for whole language transformations. Syntactic macros About three years … Continue reading

Posted in DSL, Grammars, TBP | Leave a comment

Trace Based Parsing (Part V) – From Grammars to NFAs

In this article I will demonstrate the translation process by which an EBNF grammar will be translated into a Trail NFA. There are several different notations for EBNF that differ only in minor details. I’ve chosen the one of Pythons … Continue reading

Posted in EasyExtend, Grammars, TBP | Leave a comment

Trace Based Parsing ( Part IV ) – Recursive NFAs

Not long ago I inserted the following piece of code in the `EasyExtend/trail/nfatracing.py` module which defines NFA tracers and cursors and deals with the reconstruction of parse trees from state set sequences. class NFAInterpreter(object): def __init__(self, nfa): for state in … Continue reading

Posted in EasyExtend, Grammars, TBP | Leave a comment

Trace Based Parsing ( Part III ) – NFALexer

The NFALexer gives me an uneasy feeling. It is the most questionable of Trails components – one that cannot decide whether it wants to be a lexer that produces a token stream or a parser that produces parse trees. Continue reading

Posted in EasyExtend, Grammars, TBP | Leave a comment