Mercurial > pub > ImplabNet

comparison Implab/Automaton/RegularExpressions/Grammar.cs @ 165:e227e78d72e4 ref20160224

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