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
Parser.cs
Go to the documentation of this file.
1 using Mercury.Nucleus.Collections;
2 using Mercury.Nucleus.Trees;
3 using Mercury.Scanning;
4 using System;
5 using System.Collections.Generic;
6 using System.Linq;
7
8 namespace Mercury.Syntax
9 {
10 //=============================================================================
11 // IParser
12 //=============================================================================
13
15 public interface IParser
16 {
18 Grammar Grammar { get; }
19
25 ParserResult Parse(IList<Token> tokens);
26
34 ParserResult Parse(IList<Token> tokens, IList<Rule> scanresult);
35 }
36
37 //=============================================================================
38 // ChartParserInternal
39 //=============================================================================
40
44 internal class ChartParserInternal
45 {
46 //--[ Private classes ]----------------------------------------------
47
48 #region [ ReferenceComparer ]
49
50 private class ReferenceComparer : IEqualityComparer<object>
51 {
52 public new bool Equals(object x, object y)
53 { return object.ReferenceEquals(x, y); }
54
55 public int GetHashCode(object obj)
56 { return obj.GetHashCode(); }
57 }
58
59 #endregion
60
61 //--[ Private fields ]-----------------------------------------------
62
63 private UniqueListMultiDictionary<Edge, EdgeDerivation> edges = null;
64 private UniqueListMultiDictionary<Edge, Tree<Symbol>> allTrees = null;
65
66 private List<Edge> chart = null;
67 private Queue<Edge> agenda = null;
68
69 private List<Edge> activeEdges = null; // cache
70 private List<Edge> passiveEdges = null; // cache
71 private List<Tree<Symbol>> finalTrees = null; // cache
72 private List<Tree<Symbol>> terminalTrees = null; // cache
73
74 private List<Token> input = null;
75 private List<Symbol> data = null;
76
77 private HashSet<EdgeDerivation> explored = null;
78 private HashSet<EdgeDerivation> locked = null;
79
80 //--[ Private methods ]----------------------------------------------
81
82 private void AddEdge(Edge edge, EdgeDerivation eder)
83 {
84 if (!edges.ContainsKey(edge)) agenda.Enqueue(edge);
85 edges.Add(edge, eder);
86 }
87
88 private bool IsFinalEdge(Edge edge)
89 {
90 return edge.IsPassive
91 && (edge.Left == 0)
92 && (edge.Right == input.Count)
93 && (edge.Rule.LHS.Equals(Grammar.Root));
94 }
95
96 #region [ Chart Parsing Methods ]
97
98 private void Initialize()
99 {
100 edges = new UniqueListMultiDictionary<Edge, EdgeDerivation>();
101 chart = new List<Edge>();
102 agenda = new Queue<Edge>();
103
104 activeEdges = new List<Edge>();
105 passiveEdges = new List<Edge>();
106
107 for (int rix = 0; rix < Grammar.EpsilonRules.Count; ++rix)
108 for (int ix = 0; ix <= input.Count; ++ix)
109 AddEdge(new Edge(Grammar.EpsilonRules[rix], 0, ix, ix), EdgeDerivation.Initial());
110
111 for (int rix = 0; rix < Grammar.TerminalRules.Count; ++rix)
112 {
113 Rule rule = Grammar.TerminalRules[rix];
114
115 for (int ix = 0; ix < input.Count; ++ix)
116 if (data[ix].Name == rule.RHS[0].Name)
117 AddEdge(new Edge(rule, 0, ix, ix), EdgeDerivation.Initial());
118 }
119 }
120
121 private void CombineEdges(Edge source, Edge additional)
122 {
123 if ((source.Right == additional.Left) && (source.NextSymbol.Equals(additional.Rule.LHS)))
124 AddEdge(new Edge(source.Rule, source.Dot + 1, source.Left, additional.Right),
125 EdgeDerivation.Fundamental(source, additional));
126 }
127
128 private void FundamentalA(Edge agendaEdge)
129 {
130 if (agendaEdge.IsActive) return;
131
132 for (int ix = 0; ix < activeEdges.Count; ++ix)
133 CombineEdges(activeEdges[ix], agendaEdge);
134 }
135
136 private void FundamentalB(Edge agendaEdge)
137 {
138 if (agendaEdge.IsPassive) return;
139
140 for (int ix = 0; ix < passiveEdges.Count; ++ix)
141 CombineEdges(agendaEdge, passiveEdges[ix]);
142 }
143
144 private void ScanInput(Edge agendaEdge)
145 {
146 if (agendaEdge.IsPassive
147 || (agendaEdge.NextSymbol.Type != SymbolType.Terminal)
148 || (data.Count <= agendaEdge.Right)
149 || !(data[agendaEdge.Right].Name == agendaEdge.NextSymbol.Name))
150 return;
151
152 AddEdge(new Edge(agendaEdge.Rule, agendaEdge.Dot + 1, agendaEdge.Left, agendaEdge.Right + 1),
153 EdgeDerivation.Scanning(agendaEdge));
154 }
155
156 private void Prediction(Edge agendaEdge)
157 {
158 if (agendaEdge.IsActive) return;
159
160 foreach(Rule rule in Grammar.RulesWithInitial(agendaEdge.Rule.LHS))
161 AddEdge(new Edge(rule, 0, agendaEdge.Left, agendaEdge.Left), EdgeDerivation.Prediction());
162 }
163
164 #endregion
165
166 #region [ Derivation Tree Generators ]
167
168 private void CreateTrees(Edge edge)
169 {
170 foreach(var derivation in edges[edge])
171 {
172 if (explored.Contains(derivation) || !locked.Add(derivation)) continue;
173
174 var temp = new List<Tree<Symbol>>();
175 switch(derivation.Derivation)
176 {
177 case DerivationType.Initial:
178 case DerivationType.Prediction:
179 Tree<Symbol> newTree = edge.Rule.IsEpsilon
180 ? new Tree<Symbol>(edge.Rule.LHS, new [] { terminalTrees[terminalTrees.Count - 1] })
181 : new Tree<Symbol>(edge.Rule.LHS);
182
183 allTrees.Add(edge, newTree);
184 break;
185
186 case DerivationType.Scanning:
187 CreateTrees(derivation.Source);
188 for (int ix = 0; ix < allTrees.GetValuesCount(derivation.Source); ++ix)
189 allTrees.Add(edge, new Tree<Symbol>(allTrees.GetValue(derivation.Source, ix),
190 new[] { terminalTrees[edge.Right - 1] }));
191 break;
192
193 case DerivationType.Fundamental:
194 CreateTrees(derivation.Source);
195 CreateTrees(derivation.Additional);
196 for (int src = 0; src < allTrees.GetValuesCount(derivation.Source); ++src)
197 for (int add = 0; add < allTrees.GetValuesCount(derivation.Additional); ++add)
198 allTrees.Add(edge, new Tree<Symbol>(allTrees.GetValue(derivation.Source, src),
199 new[] { allTrees.GetValue(derivation.Additional, add) }));
200 break;
201 }
202
203 explored.Add(derivation);
204 locked.Remove(derivation);
205 }
206 }
207
208 private void CreateDerivationTrees()
209 {
210 allTrees = new UniqueListMultiDictionary<Edge, Tree<Symbol>>();
211 terminalTrees = new List<Tree<Symbol>>();
212 finalTrees = new List<Tree<Symbol>>();
213
214 locked = new HashSet<EdgeDerivation>(new ReferenceComparer());
215 explored = new HashSet<EdgeDerivation>(new ReferenceComparer());
216
217 input.ForEach(x => terminalTrees.Add(new Tree<Symbol>(new Symbol(x))));
218 terminalTrees.Add(new Tree<Symbol>(Grammar.Epsilon));
219
220 foreach (var edge in chart.Where(e => IsFinalEdge(e)))
221 {
222 CreateTrees(edge);
223 finalTrees.AddRange(allTrees[edge]);
224 }
225 }
226
227 #endregion
228
229 //--[ Constructors ]-------------------------------------------------
230
238 public ChartParserInternal(ExtendedGrammar grammar)
239 {
240 if (grammar == null) throw new ArgumentNullException("grammar");
241
242 Grammar = grammar;
243 }
244
245 //--[ Properties ]---------------------------------------------------
246
248 public ExtendedGrammar Grammar { get; private set; }
249
250 //--[ Methods ]------------------------------------------------------
251
259 public ParserResult Parse(IList<Token> tokens)
260 {
261 input = new List<Token>(tokens);
262 data = input.Select(x => new Symbol(x)).ToList();
263
264 Initialize();
265
266 while (agenda.Count != 0)
267 {
268 Edge a_edge = agenda.Dequeue();
269
270 FundamentalA(a_edge);
271 FundamentalB(a_edge);
272 ScanInput(a_edge);
273 Prediction(a_edge);
274
275 chart.Add(a_edge);
276
277 if (a_edge.IsActive) activeEdges.Add(a_edge);
278 else passiveEdges.Add(a_edge);
279 }
280
281 CreateDerivationTrees();
282
283 return new ParserResult()
284 {
285 Accepted = finalTrees.Count > 0,
286 InputTokens = input,
287 Chart = chart,
288 Trees = finalTrees
289 };
290 }
291 }
292
293 //=============================================================================
294 // ChartParser
295 //=============================================================================
296
298 public class ChartParser : IParser
299 {
300 //--[ Private fields ]-----------------------------------------------
301
302 private ExtendedGrammar extgrammar;
303
304 //--[ Constructors ]-------------------------------------------------
305
308 public ChartParser(Grammar grammar)
309 {
310 Grammar = grammar;
311 extgrammar = ExtendedGrammarBuilder.ExtendGrammar(grammar);
312 }
313
314 //--[ Properties ]---------------------------------------------------
315
317 public Grammar Grammar { get; private set; }
318
319 //--[ Interface implementation ]-------------------------------------
320
321 #region [ IParser ]
322
323 public ParserResult Parse(IList<Token> tokens)
324 { return (new ChartParserInternal(extgrammar)).Parse(tokens); }
325
326 public ParserResult Parse(IList<Token> tokens, IList<Rule> scanresult)
327 {
328 var gb = new ExtendedGrammarBuilder(extgrammar);
329
330 for (int ix = 0; ix < scanresult.Count; ++ix)
331 gb.AddRule(scanresult[ix]);
332
333 return (new ChartParserInternal(gb.GetExtendedGrammar())).Parse(tokens);
334 }
335
336 #endregion
337
338 }
339 }
Mercury.Syntax.ChartParser
Thread-safe wrapper for ChartParserInternal class.
Definition: Parser.cs:298
Mercury.Syntax.IParser
Creates a derivation tree from the list of input tokens
Definition: Parser.cs:15
Mercury.Interpreting.Symbol
A single symbol
Mercury.Syntax.SymbolType
SymbolType
Represents a type of symbol. Implemented as Flags since Symbol type inference is ambiguous.
Definition: Symbol.cs:16
Mercury.Syntax.ChartParser.Parse
ParserResult Parse(IList< Token > tokens)
Creates a trees (in Mercury.Syntax.ParserResult) from the tokens
Definition: Parser.cs:323
Mercury.Syntax.ChartParser.ChartParser
ChartParser(Grammar grammar)
Chart Parser constructor
Definition: Parser.cs:308
Mercury.Syntax.ParserResult
Represents the result returned by the parser.
Definition: ParserResult.cs:14
Mercury.Syntax.Prediction
Edge created by prediction
Mercury.Syntax.Grammar
Represents a Context-Free Grammar. This is an immutable class, to create a grammar use Mercury...
Definition: Grammar.cs:18
Mercury.Syntax.ChartParser.Parse
ParserResult Parse(IList< Token > tokens, IList< Rule > scanresult)
Creates a trees (in Mercury.Syntax.ParserResult) from the tokens with the support of Mercury...
Definition: Parser.cs:326