Click here to Skip to main content
11,636,889 members (73,965 online)
Click here to Skip to main content
Add your own
alternative version

a Tiny Parser Generator v1.2

, 21 Sep 2010 CPOL 292.2K 11.8K 437
@TinyPG is a utility that makes it easier to write and try out your own parser/compiler.
TinyPG_v1.0_binaries.zip
Release
Examples
BNFGrammar v1.0.tpg
simple expression1.tpg
simple expression2.tpg
Templates
TinyPG.exe
TinyPG_v1.0_sources.zip
TinyPG v1.0
bin
Debug
Release
TinyPG.vshost.exe
TinyPG.vshost.exe.manifest
Compiler
backup
vssver2.scc
vssver2.scc
Controls
DockExtender
vssver2.scc
vssver2.scc
Debug
vssver2.scc
Examples
BNFGrammar v0.2.tpg
BNFGrammar v1.0.tpg
simple expression1.tpg
simple expression2.tpg
test.tpg
vssver2.scc
mssccprj.scc
obj
Debug
TempPE
Release
TempPE
Properties.Resources.Designer.cs.dll
Properties
vssver2.scc
Templates
vssver2.scc
TinyPG.csproj.user
TinyPG.suo
vssver2.scc
TinyPG_v1.1_sources.zip
TinyPG v1.1
bin
Release
Examples
BNFGrammar v1.0.tpg
BNFGrammar v1.1.tpg
simple expression1.tpg
simple expression2.tpg
Templates
TinyPG.exe
Compiler
vssver2.scc
Controls
DockExtender
vssver2.scc
vssver2.scc
Debug
vssver2.scc
Examples
BNFGrammar v0.2.tpg
BNFGrammar v1.0.tpg
BNFGrammar v1.1.tpg
simple expression1.tpg
simple expression2.tpg
vssver2.scc
Highlighter
vssver2.scc
mssccprj.scc
Properties
vssver2.scc
Templates
vssver2.scc
TinyPG.csproj.user
TinyPG.suo
vssver2.scc
TinyPG_v1.2_binaries.zip
BNFGrammar v1.0.tpg
BNFGrammar v1.1.tpg
GrammarHighlighter.tpg
simple expression1.tpg
simple expression2.tpg
C#
VB
TinyPG.exe
TinyPG_v1.2_sources.zip
TinyPG v1.2
bin
Release
Examples
BNFGrammar v1.0.tpg
BNFGrammar v1.1.tpg
GrammarHighlighter.tpg
simple expression1.tpg
simple expression2.tpg
Templates
C#
VB
TinyPG.exe
CodeGenerators
CSharp
vssver2.scc
VBNet
vssver2.scc
vssver2.scc
Compiler
BNFGrammar.tpg
vssver2.scc
Controls
DockExtender
vssver2.scc
vssver2.scc
Debug
vssver2.scc
Examples
BNFGrammar v0.2.tpg
BNFGrammar v1.0.tpg
BNFGrammar v1.1.tpg
BNFGrammar_vb v1.1.tpg
GrammarHighlighter.tpg
GrammarHighlighter_vb.tpg
simple expression1.tpg
simple expression1_vb.tpg
simple expression2.tpg
simple expression2_vb.tpg
vssver2.scc
Highlighter
GrammarHighlighter v1.2.tpg
vssver2.scc
mssccprj.scc
Properties
vssver2.scc
Templates
C#
vssver2.scc
VB
vssver2.scc
vssver2.scc
TinyPG.csproj.user
TinyPG.suo
vssver2.scc
TinyPG_v1_3_binaries.zip
BNFGrammar 1.3.tpg
BNFGrammar_vb 1.3.tpg
GrammarHighlighter v1.3.tpg
GrammarHighlighter_vb.tpg
simple expression1.tpg
simple expression2.tpg
TinyPG.exe
TinyPG.vshost.exe
TinyPG.vshost.exe.manifest
TinyPG_v1_3_sources.zip
TinyPG v1.3
TinyPG
bin
Debug
Examples
BNFGrammar 1.3.tpg
BNFGrammar v1.0.tpg
BNFGrammar v1.1.tpg
BNFGrammar_vb 1.3.tpg
GrammarHighlighter v1.3.tpg
GrammarHighlighter.tpg
GrammarHighlighter_vb.tpg
simple expression1.tpg
simple expression2.tpg
Templates
C#
VB
TinyPG.exe
TinyPG.pdb
TinyPG.vshost.exe
Release
Examples
BNFGrammar 1.3.tpg
BNFGrammar_vb 1.3.tpg
GrammarHighlighter v1.3.tpg
GrammarHighlighter_vb.tpg
simple expression1.tpg
simple expression2.tpg
Templates
C#
VB
TinyPG.exe
TinyPG.pdb
TinyPG.vshost.exe
TinyPG.vshost.exe.manifest
CodeGenerators
CSharp
vssver2.scc
VBNet
vssver2.scc
vssver2.scc
Compiler
BNFGrammar 1.3.tpg
vssver2.scc
Controls
DockExtender
vssver2.scc
vssver2.scc
Debug
vssver2.scc
Examples
BNFGrammar 1.3.tpg
BNFGrammar_vb 1.3.tpg
csharpstruct.tpg
GrammarHighlighter v1.3.tpg
GrammarHighlighter_vb.tpg
simple expression1.tpg
simple expression1_vb.tpg
simple expression2.tpg
simple expression2_vb.tpg
vssver2.scc
Highlighter
GrammarHighlighter v1.3.tpg
vssver2.scc
mssccprj.scc
obj
Debug
TempPE
Properties.Resources.Designer.cs.dll
TinyPG.Controls.AutoComplete.resources
TinyPG.Controls.RegExControl.resources
TinyPG.csproj.GenerateResource.Cache
TinyPG.exe
TinyPG.MainForm.resources
TinyPG.pdb
TinyPG.Properties.Resources.resources
Release
TempPE
Properties.Resources.Designer.cs.dll
TinyPG.Controls.AutoComplete.resources
TinyPG.Controls.RegExControl.resources
TinyPG.csproj.GenerateResource.Cache
TinyPG.exe
TinyPG.MainForm.resources
TinyPG.pdb
TinyPG.Properties.Resources.resources
Properties
vssver2.scc
Templates
C#
vssver2.scc
VB
vssver2.scc
vssver2.scc
TinyPG.csproj.user
TinyPG.suo
vssver2.scc
TinyPG.UnitTests
bin
Release
Examples
BNFGrammar 1.3.tpg
BNFGrammar v1.0.tpg
BNFGrammar v1.1.tpg
BNFGrammar_vb 1.3.tpg
GrammarHighlighter v1.3.tpg
GrammarHighlighter_vb.tpg
simple expression1.tpg
simple expression2.tpg
Templates
C#
VB
TinyPG.exe
TinyPG.UnitTests.dll
localtestrun.testrunconfig
mssccprj.scc
Properties
Testfiles
BNFGrammar v1.1.tpg
BNFGrammar_vb v1.1.tpg
GrammarHighlighter.tpg
GrammarHighlighter_vb.tpg
simple expression1.tpg
simple expression1_vb.tpg
simple expression2.tpg
simple expression2_vb.tpg
vssver2.scc
Testfiles
BNFGrammar v1.1.tpg
BNFGrammar_vb v1.1.tpg
GrammarHighlighter.tpg
GrammarHighlighter_vb.tpg
simple expression1.tpg
simple expression1_vb.tpg
simple expression2.tpg
simple expression2_vb.tpg
vssver2.scc
TestResults
TinyPG.testrunconfig
TinyPG.UnitTests.csproj.user
vssver2.scc
// Copyright 2008 - 2010 Herre Kuijpers - <herre.kuijpers@gmail.com>
//
// This source file(s) may be redistributed, altered and customized
// by any means PROVIDING the authors name and all copyright
// notices remain intact.
// THIS SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
// EXPRESS OR IMPLIED. USE IT AT YOUR OWN RISK. THE AUTHOR ACCEPTS NO
// LIABILITY FOR ANY DATA DAMAGE/LOSS THAT THIS PRODUCT MAY CAUSE.
//-----------------------------------------------------------------------
using System;
using System.Collections.Generic;
using System.Text;
using System.Text.RegularExpressions;

namespace TinyPG.Compiler
{
    #region RuleType
    public enum RuleType
    {
        //Production = 0, // production rule
        /// <summary>
        /// represents a terminal symbol
        /// </summary>
        Terminal = 1,
        /// <summary>
        /// represents a non terminal symbol
        /// </summary>
        NonTerminal = 2,
        /// <summary>
        /// represents the | symbol, choose between one or the other symbol or subrule (OR)
        /// </summary>
        Choice = 3, // |
        /// <summary>
        /// puts two symbols or subrules in sequental order (AND)
        /// </summary>
        Concat = 4, // <whitespace>
        /// <summary>
        /// represents the ? symbol
        /// </summary>
        Option = 5, // ?
        /// <summary>
        /// represents the * symbol
        /// </summary>
        ZeroOrMore = 6, // *
        /// <summary>
        /// represents the + symbol
        /// </summary>
        OneOrMore = 7 // +
    }
    #endregion RuleType

    public class Rules : List<Rule>
    {
    }

    public class Rule
    {
        public Symbol Symbol;
        public Rules Rules;
        public RuleType Type;

        public Rule()
            : this(null, RuleType.Choice)
        {
        }
        
        public Rule(Symbol s) : this(s, s is TerminalSymbol ? RuleType.Terminal : RuleType.NonTerminal)
        {
        }
        
        public Rule(RuleType type) : this(null, type)
        {
        }
        
        public Rule(Symbol s, RuleType type)
        {
            Type = type; 
            Symbol = s;
            Rules = new Rules();
        }
        public Symbols GetFirstTerminals()
        {
            Symbols visited = new Symbols();
            Symbols FirstTerminals = new Symbols();
            DetermineFirstTerminals(FirstTerminals);
            return FirstTerminals;
        }


        public void DetermineProductionSymbols(Symbols symbols)
        {
            if (Type == RuleType.Terminal || Type == RuleType.NonTerminal)
            {
                symbols.Add(Symbol);
            }
            else
            {
                foreach (Rule rule in Rules)
                    rule.DetermineProductionSymbols(symbols);
            }

        }

        /*
        internal void DetermineLookAheadTree(LookAheadNode node)
        {
            switch (Type)
            {
                case RuleType.Terminal:
                    LookAheadNode f = node.Nodes.Find(Symbol.Name);
                    if (f == null)
                    {
                        LookAheadNode n = new LookAheadNode();
                        n.LookAheadTerminal = (TerminalSymbol) Symbol;
                        node.Nodes.Add(n);
                    }
                    else
                        Console.WriteLine("throw new Exception(\"Terminal already exists\");");
                    break;
                case RuleType.NonTerminal:
                    NonTerminalSymbol nts = Symbol as NonTerminalSymbol;

                    break;
                //case RuleType.Production:
                case RuleType.Concat:
                    break;
                case RuleType.OneOrMore:
                    break;
                case RuleType.Option:
                case RuleType.Choice:
                case RuleType.ZeroOrMore:
                    break;
                default:
                    throw new NotImplementedException();
            }
        }
        */

        internal bool DetermineFirstTerminals(Symbols FirstTerminals)
        {
            return DetermineFirstTerminals(FirstTerminals, 0);
        }

        internal bool DetermineFirstTerminals(Symbols FirstTerminals, int index)
        {

            // indicates if Nonterminal can evaluate to an empty terminal (e.g. in case T -> a? or T -> a*)
            // in which case the parent rule should continue scanning after this nonterminal for Firsts.
            bool containsEmpty = false; // assume terminal is found
            switch (Type)
            {
                case RuleType.Terminal:
                    if (Symbol == null)
                        return true;

                        if (!FirstTerminals.Exists(Symbol))
                        FirstTerminals.Add(Symbol);
                    else
                        Console.WriteLine("throw new Exception(\"Terminal already exists\");");
                    break;
                case RuleType.NonTerminal:
                    if (Symbol == null)
                        return true;
                    
                    NonTerminalSymbol nts = Symbol as NonTerminalSymbol;                    
                    containsEmpty = nts.DetermineFirstTerminals();

                    // add first symbols of the nonterminal if not already added
                    foreach (TerminalSymbol t in nts.FirstTerminals)
                    {
                        if (!FirstTerminals.Exists(t))
                            FirstTerminals.Add(t);
                        else
                            Console.WriteLine("throw new Exception(\"Terminal already exists\");");
                    }
                    break;
                case RuleType.Choice:
                    {
                        // all subrules must be evaluated to determine if they contain first terminals
                        // if any subrule contains an empty, then this rule also contains an empty
                        foreach (Rule r in Rules)
                        {
                            containsEmpty |= r.DetermineFirstTerminals(FirstTerminals);
                        }
                        break;
                    }
                case RuleType.OneOrMore:
                    {
                        // if a non-empty subrule was found, then stop further parsing.
                        foreach (Rule r in Rules)
                        {
                            containsEmpty = r.DetermineFirstTerminals(FirstTerminals);
                            if (!containsEmpty) // found the final set of first terminals
                                break;
                        }
                        break;
                    }
                case RuleType.Concat:
                    {
                        // if a non-empty subrule was found, then stop further parsing.
                        // start scanning from Index

                        for (int i = index; i < Rules.Count; i++)
                        {
                            containsEmpty = Rules[i].DetermineFirstTerminals(FirstTerminals);
                            if (!containsEmpty) // found the final set of first terminals
                                break;
                        }

                        // assign this concat rule to each terminal
                        foreach (TerminalSymbol t in FirstTerminals)
                            t.Rule = this;

                        break;
                    }
                case RuleType.Option: 
                case RuleType.ZeroOrMore:
                    {
                        // empty due to the nature of this rule (A? or A* can always be empty)
                        containsEmpty = true;
                        
                        // if a non-empty subrule was found, then stop further parsing.
                        foreach (Rule r in Rules)
                        {
                            containsEmpty |= r.DetermineFirstTerminals(FirstTerminals);
                            if (!containsEmpty) // found the final set of first terminals
                                break;
                        }
                        break;
                    }
                default:
                    throw new NotImplementedException();
            }
            return containsEmpty;
        }

        public string PrintRule()
        {
            string r = "";

            switch (Type)
            {
                case RuleType.Terminal:
                case RuleType.NonTerminal:
                    if (Symbol != null)
                        r = Symbol.Name;
                    break;
                case RuleType.Concat:
                    foreach (Rule rule in Rules)
                    {
                        // continue recursively parsing all subrules
                        r += rule.PrintRule() + " ";
                    }
                    if (Rules.Count < 1)
                        r += " <- WARNING: ConcatRule contains no subrules";
                    break;
                case RuleType.Choice:
                    r += "(";
                    foreach (Rule rule in Rules)
                    {
                        if (r.Length > 1)
                            r += " | ";
                        // continue recursively parsing all subrules
                        r += rule.PrintRule();
                    }
                    r += ")";
                    if (Rules.Count < 1)
                        r += " <- WARNING: ChoiceRule contains no subrules";
                    break;
                case RuleType.ZeroOrMore:
                    if (Rules.Count >= 1)
                        r += "(" + Rules[0].PrintRule() + ")*";
                    if (Rules.Count > 1)
                        r += " <- WARNING: ZeroOrMoreRule contains more than 1 subrule";
                    if (Rules.Count < 1)
                        r += " <- WARNING: ZeroOrMoreRule contains no subrule";
                    break;
                case RuleType.OneOrMore:
                    if (Rules.Count >= 1)
                        r += "(" + Rules[0].PrintRule() + ")+";
                    if (Rules.Count > 1)
                        r += " <- WARNING: OneOrMoreRule contains more than 1 subrule";
                    if (Rules.Count < 1)
                        r += " <- WARNING: OneOrMoreRule contains no subrule";
                    break;
                case RuleType.Option:
                    if (Rules.Count >= 1)
                        r += "(" + Rules[0].PrintRule() + ")?";
                    if (Rules.Count > 1)
                        r += " <- WARNING: OptionRule contains more than 1 subrule";
                    if (Rules.Count < 1)
                        r += " <- WARNING: OptionRule contains no subrule";

                    break;
                default:
                    r = Symbol.Name;
                    break;
            }
            return r;
        }
    }
}

By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.

If a file you wish to view isn't highlighted, and is a text file (not binary), please let us know and we'll add colourisation support for it.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Herre Kuijpers
Architect Capgemini
Netherlands Netherlands
Currently Herre Kuijpers is employed at Capgemini Netherlands for over 10 years, where he developed skills with all kinds of technologies, methodologies and programming languages such as c#, ASP.Net, Silverlight, VC++, Javascript, SQL, UML, RUP, WCF. Currently he fulfills the role of software architect in various projects.

Herre Kuijpers is a very experienced software architect with deep knowledge of software design and development on the Microsoft .Net platform. He has a broad knowledge of Microsoft products and knows how these, in combination with custom software, can be optimally implemented in the often complex environment of the customer.

You may also be interested in...

| Advertise | Privacy | Terms of Use | Mobile
Web04 | 2.8.150728.1 | Last Updated 21 Sep 2010
Article Copyright 2008 by Herre Kuijpers
Everything else Copyright © CodeProject, 1999-2015
Layout: fixed | fluid