-
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: Parsing
Greedy grammars and Any
I only vaguely remember my first encounter with a parser generator which must by dated back to the late 1990s. I guess it was Spark by John Aycock, an Early parser. What puzzled me back then was the need to … Continue reading
Posted in Grammars, Parsing, Python
Leave a comment
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
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
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