annotate Implab/Automaton/RegularExpressions/Grammar.cs @ 169:54270c2f29f2 ref20160224

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