LL: A Parser Generator Playground

/****************************************************************\
*  ebnf.ebnf: a self describing grammar for describing grammars  *
*   by codewitch honey crisis, july 2019                         *
\****************************************************************/

grammar<start>= productions;

//
// productions
//
// marking a non-terminal with collapse removes it from
// the tree and propagates its children to its parent
// marking a terminal with it similarly hides it from
// the result but not from the grammar, unlike hidden
//
productions<collapsed> = production productions | production;
production= identifier [ "<" attributes ">" ] "=" expressions ";";

//
// expressions
//
expressions<collapsed>= expression "|" expressions | expression;
expression= { symbol }+ |;
symbol= literal | regex | identifier |
    "(" expressions ")" |
    "[" expressions "]" |
    "{" expressions ("}"|"}+");

//
// attributes
//
// recognized attributes are hidden, collapsed, terminal, start,
// followsConflict (which can be "error", "first" or "last")
// and blockEnd (string)
attributes<collapsed>= attribute "," attributes | attribute;
attribute<color="red">= identifier [ "=" attrvalue ];
attrvalue<color="orange">= literal | integer | identifier;

//
// terminals
//
literal= '"([^"\\]|\\.)*"';
regex= '\'([^\'\\]|\\.)*\'';
identifier= '[A-Z_a-z][\-0-9A-Z_a-z]*';
integer= '\-?[0-9]+';

// hide comments and whitespace
//
// if you mark a production with the terminal attribute, you
// can use ebnf to define it. Anything that's text or regex
// is automatically a terminal
whitespace<hidden,terminal>= {" "|"\v"|"\f"|"\t"|"\r"|"\n"}+;
// equiv regex would be the much shorter '[ \v\f\t\r\n]+';
// otherwise they are exactly the same

// single quotes denote regex. make sure to escape single
// quotes in the regex with \'
// attributes get passed through to the parser, and you can define your own
lineComment<hidden,color="green">= '//[^\n]*[\n]';
blockComment<hidden,blockEnd="*/",color="green">= "/*";

// defining these isn't required, but gives
// us better constant names
// double quotes denote a literal. the escapes are nearly the
// same as C#. \U and \x are not supported
or="|";
lt="<";
gt=">";
eq="=";
semi=";";
comma=",";
lparen="(";
rparen=")";
lbracket="[";
rbracket="]";
lbrace="{";
rbrace="}";
rbracePlus="}+";

/// <summary>
/// Usage: lltree $grammarfile $inputfile
/// </summary>
/// <param name="args">The grammar file and the input file to parse</param>
/// <returns></returns>
static int Main(string[] args)
{
    if (2!=args.Length)
    {
        _PrintUsage();
        return 1;
    }
    // read the ebnf document from the file.
    var ebnf = EbnfDocument.ReadFrom(args[0]);
    var hasErrors = false;
    // here we validate the document and print any
    // validation errors to the console.
    foreach (var msg in ebnf.Validate(false))
    {
        if (EbnfErrorLevel.Error == msg.ErrorLevel)
        {
            hasErrors = true;
            Console.Error.WriteLine(msg);
        }
    }
    // even if we have errors, we keep going.

    // create a CFG from the EBNF document
    var cfg = ebnf.ToCfg();

    // we have to prepare a CFG to be parsable by an LL(1)
    // parser. This means removing left recursion, and
    // factoring out first-first and first-follows conflicts
    // where possible.
    // here we do that, and print any errors we encounter.
    foreach(var msg in cfg.PrepareLL1(false))
    {
        if(CfgErrorLevel.Error==msg.ErrorLevel)
        {
            hasErrors = true;
            Console.Error.WriteLine(msg);
        }
    }
    // if we don't have errors let's set up our parse.
    if(!hasErrors)
    {
        // the tokenizer is created from the EBNF document because
        // it has the terminal definitions, unlike the CFG,
        // see https://www.codeproject.com/Articles/5162249/How-to-Make-an-LL-1-Parser-Lesson-1

        // The FileReaderEnumerable takes a filename and exposes IEnumerable<char> from
        // them. Tokenizers expect IEnumerable<char> (typically a string or char array)
        var tokenizer = ebnf.ToTokenizer(cfg, new FileReaderEnumerable(args[1]));

        // now create our parser. and since the parser *might* return multiple parse trees
        // in some cases, we keep reading until the end of document, calling ParseSubtree()
        // each time to get the result back as a ParseNode tree. We then take those nodes and
        // write them to the console via an implicit call to their ToString method
        using (var parser = cfg.ToLL1Parser(tokenizer))
            while (ParserNodeType.EndDocument != parser.NodeType)
                Console.WriteLine(parser.ParseSubtree());

        return 0;

    }
    return 1;
}

var parser = new MyParser(new MyTokenizer(inputSource));