-
Recent Posts
Archives
- July 2019
- June 2012
- May 2012
- April 2012
- September 2011
- April 2011
- January 2011
- December 2010
- November 2010
- August 2010
- July 2010
- June 2010
- April 2010
- March 2010
- February 2010
- January 2010
- December 2009
- October 2009
- September 2009
- August 2009
- July 2009
- June 2009
- May 2009
- April 2009
- March 2009
- February 2009
Categories
Meta
Category Archives: Algorithms
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
Comments Off on Restricted backmatching
Syntax algebra – first steps
Principle of relativity I started to revisit syntactic mappings defined in EasyExtend 3 which are closely tied to the Python grammar being in use. Those are functions like `varargs2arglist`, `normalize`, `split_file_input` or `exprlist2testlist` defined in the `csttools.py` module. One of … Continue reading
Posted in Algorithms, Grammars
Comments Off on Syntax algebra – first steps
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
Choosers and ChooserMixins in C++ and Python
Chooser Objects From time to time I’m amazed to find a simple algorithm which seemed to be a low hanging fruit which was just overlooked. In this particular case it is about generating and utilizing test data in a both … Continue reading
Posted in Chooser, CPP, Python, Testing
2 Comments
Linear bounds for backtracking parsers with memoization
On the comp.compilers mailing list I asked for a confirmation of the O(n) complexity claim for packrat parsers. A packrat parser is a particular top down recursive descendant parser which applies backtracking on failure of consuming a token by application … Continue reading
Posted in Parsing
2 Comments
Is parsing Perl really impossible?
I just read this article about the apparent inability to parse Perl 5. There is an underlying assumption that a parser has to resolve all ambiguities and derive a single parse tree from an expression ( giving a unique interpretation … Continue reading
Posted in Grammars, Parsing
5 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
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
Comments Off on Trace Based Parsing (Part V) – From Grammars to NFAs
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
Comments Off on Trace Based Parsing ( Part IV ) – Recursive NFAs
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
Comments Off on Trace Based Parsing ( Part III ) – NFALexer