Category Archives: TBP

Trace Based Parsing

The state of the Trail parser generator

Posted on 10. April 2012 by kay

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 | Comments Off on The state of the Trail parser generator

LL(*) faster than LL(1)?

Posted on 12. September 2011 by kay

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 | 2 Comments

Token Tracers

Posted on 3. June 2010 by kay

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 | Comments Off on Token Tracers

Restricted backmatching

Posted on 13. March 2010 by kay

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 | Comments Off on Restricted backmatching

About CST interpolation

Posted on 7. December 2009 by kay

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

Posted on 7. June 2009 by kay

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 | Comments Off on CodeTemplates – a fresh look on code transformations

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

Posted on 7. May 2009 by kay

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 | Comments Off on Trace Based Parsing (Part V) – From Grammars to NFAs

Trace Based Parsing ( Part IV ) – Recursive NFAs

Posted on 6. May 2009 by kay

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 | Comments Off on Trace Based Parsing ( Part IV ) – Recursive NFAs

Trace Based Parsing ( Part III ) – NFALexer

Posted on 4. May 2009 by kay

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 | Comments Off on Trace Based Parsing ( Part III ) – NFALexer