Mercury library 1.0 Translation of CFG grammars into an object model (Bachelor's thesis).

- Main Page
- Packages
- Classes
- Files

- File List

All Classes Namespaces Files Functions Variables Enumerations Enumerator Properties
GrammarBuilder.cs
Go to the documentation of this file.
1 using Mercury.Exceptions;
2 using Mercury.Nucleus.Collections;
3 using System.Collections.Generic;
4 using System.Linq;
5
6 namespace Mercury.Syntax
7 {
8 //=============================================================================
9 // GrammarBuilder
10 //=============================================================================
11
13 public class GrammarBuilder
14 {
15 //--[ Private fields ]-----------------------------------------------
16
17 protected HashSet<Symbol> nonterminals = new HashSet<Symbol>();
18 protected HashSet<Symbol> terminals = new HashSet<Symbol>();
19 protected HashSet<Rule> rules = new HashSet<Rule>();
20
21 //--[ Constructors ]-------------------------------------------------
22
27 public GrammarBuilder()
28 : this(new Symbol(Defaults.Root), new Symbol(Defaults.Epsilon, SymbolType.Epsilon))
29 { }
30
36 public GrammarBuilder(Symbol root, Symbol epsilon)
37 {
38 if (root.Type != SymbolType.Nonterminal)
39 throw new SyntaxException("Root must be a nonterminal");
40
41 if (epsilon.Type != SymbolType.Epsilon)
42 throw new SyntaxException("Invalid epsilon symbol");
43
44 nonterminals.Add(root);
45
46 Root = root;
47 Epsilon = epsilon;
48 }
49
50 //--[ Properties ]---------------------------------------------------
51
53 public Symbol Root { get; private set; }
54
56 public Symbol Epsilon { get; private set; }
57
58 //--[ Methods ]------------------------------------------------------
59
67 public GrammarBuilder AddSymbol(Symbol newSymbol)
68 {
69 if (newSymbol.Name == Epsilon.Name)
70 return this;
71
72 switch (newSymbol.Type)
73 {
74 case SymbolType.Terminal:
75 terminals.Add(newSymbol);
76 break;
77
78 case SymbolType.Nonterminal:
79 nonterminals.Add(newSymbol);
80 break;
81 }
82
83 return this;
84 }
85
93 public virtual GrammarBuilder AddRule(Rule rule)
94 {
95 AddSymbol(rule.LHS);
96
97 if (rule.RHS.Any(x => (x.Name == Epsilon.Name) && (!x.IsEpsilon)))
98 rule = new Rule(rule.LHS, rule.RHS
99 .Select(x => x.Name != Epsilon.Name ? x : new Symbol(x.Name, SymbolType.Epsilon)));
100
101 foreach (var s in rule.RHS.Where(x => !x.IsEpsilon))
102 AddSymbol(s);
103
104 rules.Add(rule);
105 return this;
106 }
107
111 public GrammarBuilder AddRules(IEnumerable<Rule> rules)
112 { foreach (var rule in rules) AddRule(rule); return this; }
113
117 public GrammarBuilder Include(GrammarBuilder other)
118 { foreach (var rule in other.rules) AddRule(rule); return this; }
119
121 public Grammar GetGrammar()
122 {
123 return new Grammar()
124 {
125 Nonterminals = nonterminals.ToList(),
126 Terminals = terminals.ToList(),
127 Rules = rules.ToList(),
128 Root = this.Root,
129 Epsilon = this.Epsilon,
130 };
131 }
132 }
133
134 //=============================================================================
135 // ExtendedGrammarBuilder
136 //=============================================================================
137
138 internal class ExtendedGrammarBuilder : GrammarBuilder
139 {
140 //--[ Private fields ]-----------------------------------------------
141
142 private List<Rule> epsilonRules;
143 private List<Rule> terminalRules;
144
145 private ListMultiDictionary<Symbol, Rule> rulemap;
146
147 //--[ Constructors ]-------------------------------------------------
148
149 public ExtendedGrammarBuilder(Symbol root, Symbol epsilon)
150 : base(root, epsilon)
151 {
152 epsilonRules = new List<Rule>();
153 terminalRules = new List<Rule>();
154
155 rulemap = new ListMultiDictionary<Symbol, Rule>();
156 }
157
158 public ExtendedGrammarBuilder(Grammar source)
159 : this(source.Root, source.Epsilon)
160 {
161 for(int ix = 0; ix < source.Rules.Count; ++ix)
162 {
163 Rule r = source.Rules[ix];
164 if (r.IsEpsilon) epsilonRules.Add(r);
165 else
166 {
167 if (r.RHS[0].Type == SymbolType.Terminal) terminalRules.Add(r);
168 rulemap.Add(r.RHS[0], r);
169 }
170
171 base.AddRule(r);
172 }
173 }
174
175 public ExtendedGrammarBuilder(ExtendedGrammar source)
176 : this(source.Root, source.Epsilon)
177 {
178 epsilonRules.AddRange(source.EpsilonRules);
179 terminalRules.AddRange(source.TerminalRules);
180 rulemap = new ListMultiDictionary<Symbol, Rule>(source.rulemap);
181 }
182
183 //--[ Methods ]------------------------------------------------------
184
185 public static ExtendedGrammar ExtendGrammar(Grammar grammar)
186 { return new ExtendedGrammarBuilder(grammar).GetExtendedGrammar(); }
187
188 public ExtendedGrammar GetExtendedGrammar()
189 {
190 return new ExtendedGrammar()
191 {
192 Nonterminals = nonterminals.ToList(),
193 Terminals = terminals.ToList(),
194 Rules = rules.ToList(),
195 Root = this.Root,
196 Epsilon = this.Epsilon,
197
198 EpsilonRules = epsilonRules.ToList(),
199 TerminalRules = terminalRules.ToList(),
200 rulemap = this.rulemap
201 };
202 }
203
204 //--[ Overriden methods ]--------------------------------------------
205
206 #region [ GrammarBuilder ]
207
208 public new ExtendedGrammarBuilder AddRule(Rule rule)
209 {
210 int cntx = rules.Count;
211 base.AddRule(rule);
212
213 if (cntx != rules.Count)
214 {
215 if (rule.IsEpsilon) epsilonRules.Add(rule);
216 else rulemap.Add(rule.RHS[0], rule);
217
218 if (rule.RHS[0].Type == SymbolType.Terminal)
219 terminalRules.Add(rule);
220 }
221
222 return this;
223 }
224
225 #endregion
226
227 }
228 }
Mercury.Syntax.Rule.RHS
IReadOnlyList< Symbol > RHS
The Right-Hand Side (RHS) of the rule.
Definition: Rule.cs:70
Mercury.Syntax.GrammarBuilder.AddRule
virtual GrammarBuilder AddRule(Rule rule)
Adds a new rule to the grammar. If the rule contains symbols that are not in the grammar, they will be added. Rules that are already in the grammar will be ignored.
Definition: GrammarBuilder.cs:93
Mercury.Defaults
Global class containing cool static / convenience stuff.
Definition: Defaults.cs:15
Mercury.Syntax.GrammarBuilder
Class that creates grammars.
Definition: GrammarBuilder.cs:13
Mercury.Syntax.SymbolType
SymbolType
Represents a type of symbol. Implemented as Flags since Symbol type inference is ambiguous.
Definition: Symbol.cs:16
Mercury.Syntax.GrammarBuilder.GrammarBuilder
GrammarBuilder(Symbol root, Symbol epsilon)
Creates a GrammarBuilder with custom Root and Epsilon symbols.
Definition: GrammarBuilder.cs:36
Mercury.Syntax.Symbol.Name
string Name
Symbol name
Definition: Symbol.cs:183
Mercury.Syntax.GrammarBuilder.AddSymbol
GrammarBuilder AddSymbol(Symbol newSymbol)
Adds a new symbol to the grammar. The destination set is determined by the symbol type...
Definition: GrammarBuilder.cs:67
Mercury.Syntax.GrammarBuilder.GetGrammar
Grammar GetGrammar()
A grammar from the builder.
Definition: GrammarBuilder.cs:121
Mercury.Syntax.Rule.LHS
Symbol LHS
The Left-Hand Side (LHS) of the rule.
Definition: Rule.cs:66
Mercury.Syntax.Epsilon
The epsilon symbol.
Mercury.Syntax.GrammarBuilder.AddRules
GrammarBuilder AddRules(IEnumerable< Rule > rules)
Adds the collection of rules to the builder.
Definition: GrammarBuilder.cs:111
Mercury.Syntax.Rule
Represents a Context-Free Grammar rule. This is an immutable class.
Definition: Rule.cs:23
Mercury.Syntax.GrammarBuilder.GrammarBuilder
GrammarBuilder()
Default constructor. Uses Root and Epsilon symbols that are specified in the configuration.
Definition: GrammarBuilder.cs:27
Mercury.Syntax.GrammarBuilder.Include
GrammarBuilder Include(GrammarBuilder other)
Includes the other builder.
Definition: GrammarBuilder.cs:117
Mercury.Syntax.Symbol
Represents a single symbol of the grammar. This is an immutable class. For a symbol name to be val...
Definition: Symbol.cs:51
Mercury.Syntax.Grammar
Represents a Context-Free Grammar. This is an immutable class, to create a grammar use Mercury...
Definition: Grammar.cs:18
Mercury.Exceptions.SyntaxException
An exception thrown when something wrong happens in the Mercury.Syntax
Definition: SyntaxExceptions.cs:14
Mercury.Syntax.Symbol.Type
SymbolType Type
Symbol type
Definition: Symbol.cs:187