|
162
|
1 using Implab;
|
|
|
2 using System;
|
|
|
3 using System.Collections.Generic;
|
|
|
4 using System.Linq;
|
|
|
5
|
|
|
6 namespace Implab.Automaton.RegularExpressions {
|
|
|
7 /// <summary>
|
|
|
8 /// Базовый абстрактный класс. Грамматика, позволяет формулировать выражения над алфавитом типа <c>char</c>.
|
|
|
9 /// </summary>
|
|
165
|
10 public abstract class Grammar<TSymbol, TTag> {
|
|
162
|
11
|
|
165
|
12 protected abstract IAlphabetBuilder<TSymbol> AlphabetBuilder {
|
|
163
|
13 get;
|
|
162
|
14 }
|
|
|
15
|
|
165
|
16 protected SymbolToken<TTag> UnclassifiedToken() {
|
|
163
|
17 return new SymbolToken<TTag>(DFAConst.UNCLASSIFIED_INPUT);
|
|
162
|
18 }
|
|
|
19
|
|
165
|
20 protected void DefineAlphabet(IEnumerable<TSymbol> alphabet) {
|
|
162
|
21 Safe.ArgumentNotNull(alphabet, "alphabet");
|
|
|
22
|
|
|
23 foreach (var ch in alphabet)
|
|
165
|
24 AlphabetBuilder.DefineSymbol(ch);
|
|
162
|
25 }
|
|
163
|
26
|
|
165
|
27 protected Token<TTag> SymbolToken(TSymbol symbol) {
|
|
163
|
28 return Token<TTag>.New(TranslateOrAdd(symbol));
|
|
162
|
29 }
|
|
|
30
|
|
165
|
31 protected Token<TTag> SymbolToken(IEnumerable<TSymbol> symbols) {
|
|
163
|
32 Safe.ArgumentNotNull(symbols, "symbols");
|
|
|
33
|
|
|
34 return Token<TTag>.New(TranslateOrAdd(symbols).ToArray());
|
|
162
|
35 }
|
|
|
36
|
|
165
|
37 protected Token<TTag> SymbolSetToken(params TSymbol[] set) {
|
|
162
|
38 return SymbolToken(set);
|
|
|
39 }
|
|
|
40
|
|
163
|
41 int TranslateOrAdd(TSymbol ch) {
|
|
165
|
42 var t = AlphabetBuilder.Translate(ch);
|
|
163
|
43 if (t == DFAConst.UNCLASSIFIED_INPUT)
|
|
165
|
44 t = AlphabetBuilder.DefineSymbol(ch);
|
|
162
|
45 return t;
|
|
|
46 }
|
|
|
47
|
|
163
|
48 IEnumerable<int> TranslateOrAdd(IEnumerable<TSymbol> symbols) {
|
|
162
|
49 return symbols.Distinct().Select(TranslateOrAdd);
|
|
|
50 }
|
|
|
51
|
|
163
|
52 int TranslateOrDie(TSymbol ch) {
|
|
165
|
53 var t = AlphabetBuilder.Translate(ch);
|
|
163
|
54 if (t == DFAConst.UNCLASSIFIED_INPUT)
|
|
162
|
55 throw new ApplicationException(String.Format("Symbol '{0}' is UNCLASSIFIED", ch));
|
|
|
56 return t;
|
|
|
57 }
|
|
|
58
|
|
163
|
59 IEnumerable<int> TranslateOrDie(IEnumerable<TSymbol> symbols) {
|
|
162
|
60 return symbols.Distinct().Select(TranslateOrDie);
|
|
|
61 }
|
|
|
62
|
|
165
|
63 protected Token<TTag> SymbolTokenExcept(IEnumerable<TSymbol> symbols) {
|
|
162
|
64 Safe.ArgumentNotNull(symbols, "symbols");
|
|
|
65
|
|
165
|
66 return Token<TTag>.New( Enumerable.Range(0, AlphabetBuilder.Count).Except(TranslateOrDie(symbols)).ToArray() );
|
|
162
|
67 }
|
|
|
68
|
|
165
|
69 protected void BuildDFA(Token<TTag> lang, IDFATableBuilder<TTag> dfaTable, IAlphabetBuilder<TSymbol> dfaAlphabet) {
|
|
162
|
70 Safe.ArgumentNotNull(lang, "lang");
|
|
165
|
71 Safe.ArgumentNotNull(dfaAlphabet, "dfaAlphabet");
|
|
162
|
72
|
|
165
|
73 var dfa = new RegularDFADefinition<TSymbol, TTag>(AlphabetBuilder);
|
|
164
|
74
|
|
163
|
75 var builder = new RegularDFABuilder<TTag>();
|
|
162
|
76
|
|
|
77 lang.Accept( builder );
|
|
|
78
|
|
165
|
79 builder.BuildDFA(dfa);
|
|
|
80
|
|
|
81 if (dfa.IsFinalState(dfa.InitialState))
|
|
162
|
82 throw new ApplicationException("The specified language contains empty token");
|
|
|
83
|
|
165
|
84 dfa.Optimize(dfaTable, dfaAlphabet);
|
|
|
85
|
|
162
|
86 }
|
|
|
87
|
|
|
88 }
|
|
|
89
|
|
|
90
|
|
|
91 }
|
