I wrote a Python PEG parser generator that takes a grammar as a string, and returns a parser. The parser can parse its own syntax, and is feature complete with the original PEG paper, with some additions.I'm looking for comments on the implementation itself, and the interface it uses. I also put in effort to make sure the implementation works on both Python 2.7 and Python 3.x, and would be interested in any things I overlooked.There is no good syntax error reporting yet, but I already have an idea how to do this (by modifying Failure to contain context). But if there is some other ingenious solid way of reporting syntax errors, I'm interested.This is the implementation:from __future__ import unicode_literalsimport stringimport sys# We only use unicode in our parser, except for __repr__, which must return str.if sys.version_info.major == 2:    repr_str = lambda s: s.encode(utf-8)    str = unicodeelse:    repr_str = lambda s: speg_grammar_src = r#                        Parsing Expression Grammars# Based on:        A Recognition-Based Syntactic Foundation#                              - Bryan Ford## Modified slightly to use equals sign, simpler character escapes and fixed# - at end of character class. Added a fixed number of repeats (e.g. {3})# and starting a definition with a semicolon ensures any matched strings# are ignored.# Hierarchical syntaxgrammar    = spacing definition+ eofdefinition = semicolon? identifier equals expressionexpression = sequence (slash sequence)*sequence   = prefix*prefix     = (and / not)? suffixsuffix     = primary (question / star / plus / repeat)?repeat     = open_brace integer close_braceprimary    = identifier !equals           / open_paren expression close_paren           / literal / class / dot# Lexical syntaxinteger     = [0-9]+identifier  = ident_start ident_cont* spacingident_start = [a-zA-Z_]ident_cont  = ident_start / [0-9]literal     = ['] (!['] char)* ['] spacing            / [] (![] char)* [] spacingclass       = [ (!] range)* ] spacingrange       = char - !] char / charchar        = \\ [nrt'\[\]\\]            / \\x [0-9a-fA-F]{2}            / \\u [0-9a-fA-F]{4}            / \\U [0-9a-fA-F]{8}            / !\\ .semicolon   = ; spacingequals      = = spacingslash       = / spacingand         = & spacingnot         = ! spacingquestion    = ? spacingstar        = * spacingplus        = + spacingopen_paren  = ( spacingclose_paren = ) spacingopen_brace  = { spacingclose_brace = } spacingdot         = . spacing; spacing   = (space / comment)*comment     = # (!eol .)* eolspace       =   / \t / eoleol         = \r\n / \n / \reof         = !.class Failure(object): passclass Val(object):    Val represents a value resulting from a grammar expression.    If v is a Val object, str(v) returns the string as found in the source,    v.v is the value, v.name is the name if the value resulted from a non-    terminal, and v.ignore indicates that it's value is to be ignored for    str().    As a shorthand, you can index v directly, rather than having to write    v.v[i] to index lists of results.    def __init__(self, v, name=None, ignore=False):        self.name = name        self.v = v        self.ignore = ignore    def __str__(self):        if self.ignore: return         if type(self.v) is str: return self.v        return .join(str(v) for v in self.v)    if sys.version_info.major == 2:        __unicode__ = __str__        del __str__    def __repr__(self):        return repr_str({}({!r}).format(type(self).__name__, self.v))    def __getitem__(self, idx): return self.v[idx]    def __len__(self): return len(self.v)class AnyCharVal(Val): passclass StringVal(Val): passclass CharClassVal(Val): passclass OptionalVal(Val): passclass ZeroOrMoreVal(Val): passclass OneOrMoreVal(Val): passclass SequenceVal(Val): passclass ChoiceVal(Val):    def __init__(self, v, choice, name=None, ignore=False):        super(ChoiceVal, self).__init__(v, name, ignore)        self.choice = choiceclass Expr(object):    def __init__(self, data):        self.data = data    def parse(self, s):        m, i = self.match(s)        if m is Failure or i != len(s): return None        return m    def __repr__(self):        return repr_str({}({!r}).format(type(self).__name__, self.data))class AnyChar(Expr):    def __init__(self): pass    def __repr__(self): return repr_str(AnyChar())    def match(self, s, i=0):        if i >= len(s): return Failure, i        return AnyCharVal(s[i]), i + 1class CharClass(Expr):    def match(self, s, i=0):        if i >= len(s) or s[i] not in self.data: return Failure, i        return CharClassVal(s[i]), i + 1class String(Expr):    def match(self, s, i=0):        ss = s[i:i+len(self.data)]        if ss != self.data: return Failure, i        return StringVal(ss), i + len(self.data)class AndPredicate(Expr):    def match(self, s, i=0):        m, _ = self.data.match(s, i)        return Failure if m is Failure else None, iclass NotPredicate(Expr):    def match(self, s, i=0):        m, _ = self.data.match(s, i)        return Failure if m is not Failure else None, iclass Optional(Expr):    def match(self, s, i=0):        m, i = self.data.match(s, i)        return OptionalVal([] if m is Failure else [m]), iclass ZeroOrMore(Expr):    def match(self, s, i=0):        l = []        while True:            m, i = self.data.match(s, i)            if m is Failure: return ZeroOrMoreVal(l), i            if m is not None: l.append(m)class OneOrMore(Expr):    def match(self, s, i=0):        l = []        m, i = self.data.match(s, i)        if m is Failure: return Failure, i        while True:            if m is not None: l.append(m)            m, i = self.data.match(s, i)            if m is Failure: return OneOrMoreVal(l), iclass Sequence(Expr):    def match(self, s, i=0):        orig_i = i        l = []        for expr in self.data:            m, i = expr.match(s, i)            if m is Failure: return Failure, orig_i            if m is not None:                l.append(m)        if len(l) > 1:            return SequenceVal(l), i        return l[0] if l else None, iclass Choice(Expr):    def match(self, s, i=0):        for choice, expr in enumerate(self.data):            m, i = expr.match(s, i)            if m is not Failure:                return ChoiceVal(m, choice), i        return Failure, iclass Nonterminal(Expr):    def __init__(self, name, expr, ignore=False):        self.name = name        self.expr = expr        self.ignore = ignore    def match(self, s, i=0):        m, i = self.expr.match(s, i)        if m is not Failure:            if m is not None:                m.name = self.name                m.ignore = self.ignore            return m, i        return Failure, i    def __repr__(self):        return repr_str(Nonterminal({!r}, {!r}).format(self.name, self.expr))def compile_grammar(grammar):    definitions = peg_grammar.parse(grammar)[1]    identifiers = [str(d[1]) for d in definitions]    if len(identifiers) > len(set(identifiers)):        raise RuntimeError(duplicate definition)    nts = {ident: Nonterminal(ident, None) for ident in identifiers}  # Forward declaration.    for d in definitions:        identifier, expr = str(d[1]), d[3]        nts[identifier].expr = compile_expr(expr, nts)        if d[0]: nts[identifier].ignore = True    return nts[identifiers[0]]def compile_expr(expr, nts):    if not len(expr[1]):        return compile_seq(expr[0], nts)    return Choice([compile_seq(expr[0], nts)] + [compile_seq(s[1], nts) for s in expr[1]])def compile_seq(seq, nts):    if len(seq) == 0: return String()    if len(seq) == 1: return compile_prefix(seq[0], nts)    return Sequence([compile_prefix(p, nts) for p in seq])def compile_prefix(prefix, nts):    predicate = {&: AndPredicate,                 !: NotPredicate,                  : lambda s: s}[str(prefix[0])]    return predicate(compile_suffix(prefix[1], nts))def compile_suffix(suffix, nts):    op = str(suffix[1])    quantifier = {?: Optional,                  *: ZeroOrMore,                  +: OneOrMore,                  {: lambda p: Sequence([p] * int(op[1:-1])),                   : lambda p: p}[op[:1]]    return quantifier(compile_primary(suffix[0], nts))def compile_primary(r, nts):    if r.choice == 0:        return nts[str(r)]    elif r.choice == 1:        return compile_expr(r[1], nts)    elif r.choice == 2:        return String(.join(char_to_str(ch) for ch in r[1]))    elif r.choice == 3:        return CharClass(.join(map(compile_char_range, r[1])))    return AnyChar()def compile_char_range(char_range):    if char_range.choice == 0:        start = ord(char_to_str(char_range[0]))        stop = ord(char_to_str(char_range[2])) + 1        return .join(chr(c) for c in range(start, stop))    elif char_range.choice == 1:        return char_to_str(char_range.v)def char_to_str(ch):    if ch.choice == 0:  # Backslash.        ch = str(ch[1])        return {n: \n, r: \r, t: \t}.get(ch, ch)    elif ch.choice == 4:  # Literal.        return str(ch)    return chr(int(str(ch[1]), 16))  # Unicode escape.def bootstrap_grammar():    # Equivalent to peg_grammar_src, but directly expressed using primitives. For correctness    # this grammar was semi-automatically generated from peg_grammar_src after the first    # version was hand-written.    eof         = NotPredicate(AnyChar())    eol         = Choice([String(\r\n), String(\n), String(\r)])    space       = Choice([String( ), String(\t), eol])    comment     = Sequence([String(#), ZeroOrMore(Sequence([NotPredicate(eol), AnyChar()])), eol])    spacing     = Nonterminal(spacing, ZeroOrMore(Choice([space, comment])), ignore=True)    dot         = Sequence([String(.), spacing])    close_brace = Sequence([String(}), spacing])    open_brace  = Sequence([String({), spacing])    close_paren = Sequence([String()), spacing])    open_paren  = Sequence([String((), spacing])    plus        = Sequence([String(+), spacing])    star        = Sequence([String(*), spacing])    question    = Sequence([String(?), spacing])    not_        = Sequence([String(!), spacing])    and_        = Sequence([String(&), spacing])    slash       = Sequence([String(/), spacing])    equals      = Sequence([String(=), spacing])    semicolon   = Sequence([String(;), spacing])    hexchar     = CharClass(0123456789abcdefABCDEF)    char        = Choice([Sequence([String(\\), CharClass(nrt'\[]\\)]),                          Sequence([String(\\x), Sequence([hexchar] * 2)]),                          Sequence([String(\\u), Sequence([hexchar] * 4)]),                          Sequence([String(\\U), Sequence([hexchar] * 8)]),                          Sequence([NotPredicate(String(\\)), AnyChar()])])    range_      = Choice([Sequence([char, String(-), NotPredicate(String(])), char]), char])    delim       = (lambda start, inner, stop:                       Sequence([String(start),                                 ZeroOrMore(Sequence([NotPredicate(String(stop)), inner])),                                 String(stop), spacing]))    class_      = delim([, range_, ])    literal     = Choice([delim(', char, '), delim('', char, '')])    ident_start = CharClass(string.ascii_letters + _)    ident_cont  = Choice([ident_start, CharClass(string.digits)])    identifier  = Sequence([ident_start, ZeroOrMore(ident_cont), spacing])    integer     = OneOrMore(CharClass(string.digits))    expression      = Nonterminal(expression, None) # Forward declaration, needed for recursion.    primary         = Choice([Sequence([identifier, NotPredicate(equals)]),                              Sequence([open_paren, expression, close_paren]),                              literal, class_, dot])    repeat          = Sequence([open_brace, integer, close_brace])    suffix          = Sequence([primary, Optional(Choice([question, star, plus, repeat]))])    prefix          = Sequence([Optional(Choice([and_, not_])), suffix])    sequence        = ZeroOrMore(prefix)    expression.expr = Sequence([sequence, ZeroOrMore(Sequence([slash, sequence]))])    definition      = Sequence([Optional(semicolon), identifier, equals, expression])    grammar         = Sequence([spacing, OneOrMore(definition), eof])    return grammarpeg_grammar = bootstrap_grammar()And this is an example parser using the above parser generator (in Python 3):grammar = compile_grammar(rexpr = factor ([+-] factor)*factor = primary ([*/] primary)*# The predicate is to make sure a number doesn't match ..number = &(.? [0-9]) [0-9]* (. [0-9]*)?primary = ( expr ) / number / - primary)def eval_expr(expr):    r = eval_factor(expr[0])    for f in expr[1]:        if str(f[0]) == +: r += eval_factor(f[1])        else:                r -= eval_factor(f[1])    return rdef eval_factor(factor):    r = eval_primary(factor[0])    for p in factor[1]:        if str(p[0]) == *: r *= eval_primary(p[1])        else:                r /= eval_primary(p[1])    return rdef eval_primary(primary):    if primary.choice == 0:   return eval_expr(primary[1])    elif primary.choice == 1: return float(str(primary))    else:                     return -eval_primary(primary[1])def eval_str(s):    return eval_expr(grammar.parse(s.replace( , )))print(eval_str(.5+3*5--(6.+5)/3))
PEG parser generator
python;parsing