Monthly Archives: May 2009

VHDL grammars and the parser sandwich

Posted on 20. May 2009 by kay

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

Pattern matching with TupleTrees

Posted on 14. May 2009 by kay

As it seems advanced dispatch schemes are discussed right now under the pattern matching label. In this article I want to discuss another solution using a data-structure called the `TupleTree` ( also known as prefix tree or trie ). The … Continue reading →

Posted in Python | Leave a comment

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 | Leave a comment

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 | Leave a comment

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 | Leave a comment

Trace Based Parsing ( Part II ) – NFA Expansion

Posted on 2. May 2009 by kay

In the previous article about trace based parsing (TBP) I explained the basic concepts of TBP. I motivated TBP by parse tree validators that check the correctness of parse trees against grammars and I derived a trace based LL(1) parser. … Continue reading →

Posted in EasyExtend, Grammars | Leave a comment

Trace Based Parsing (Part I) – Introduction

Posted on 1. May 2009 by kay

This is the first in a series of articles about Trace Based Parsing ( TBP ). Trace based parsing is a powerful top down, table driven parsing style. TBP is the technique underlying Trail which is the parser generator of … Continue reading →

Posted in EasyExtend, Grammars | Leave a comment