Category Archives: Grammars

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

Python26 expressions

When you look at the following listing you might think it’s just a sequence of nonsense statements in Python 26,maybe created for testing purposes: raise a, b, c import d from e import* import f from .g import(a) from b … Continue reading

Posted in Grammars, Langscape, Python | Leave a comment

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 `` module. One of … Continue reading

Posted in Algorithms, Grammars | Leave a comment

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

VHDL grammars and the parser sandwich

Eli Bendersky has mentioned some problems of parsing VHDL. I was quite pleased though finding the Postlexer idea being discussed in the following paper which provides a more thorough treatment of VHDL parsing issues. They call it “Auxiliary Terminal Generator” … Continue reading

Posted in Grammars | 4 Comments

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/` 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