annotate Implab/Automaton/RegularExpressions/Grammar.cs @ 176:0c3c69fe225b ref20160224

rewritten the text scanner
author cin
date Tue, 22 Mar 2016 18:58:40 +0300
parents 92d5278d1b10
children
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
176
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
69 protected abstract IndexedAlphabetBase<TSymbol> CreateAlphabet();
164
ec35731ae299 Almost complete DFA refactoring
cin
parents: 163
diff changeset
70
176
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
71 protected ScannerContext<TTag> BuildScannerContext(Token<TTag> regexp) {
172
92d5278d1b10 Working on text scanner
cin
parents: 165
diff changeset
72
92d5278d1b10 Working on text scanner
cin
parents: 165
diff changeset
73 var dfa = new RegularDFA<TSymbol, TTag>(AlphabetBuilder);
162
0526412bbb26 DFA refactoring
cin
parents:
diff changeset
74
172
92d5278d1b10 Working on text scanner
cin
parents: 165
diff changeset
75 var visitor = new RegularExpressionVisitor<TTag>();
92d5278d1b10 Working on text scanner
cin
parents: 165
diff changeset
76 regexp.Accept( visitor );
162
0526412bbb26 DFA refactoring
cin
parents:
diff changeset
77
172
92d5278d1b10 Working on text scanner
cin
parents: 165
diff changeset
78 visitor.BuildDFA(dfa);
165
e227e78d72e4 DFA refactoring
cin
parents: 164
diff changeset
79
e227e78d72e4 DFA refactoring
cin
parents: 164
diff changeset
80 if (dfa.IsFinalState(dfa.InitialState))
162
0526412bbb26 DFA refactoring
cin
parents:
diff changeset
81 throw new ApplicationException("The specified language contains empty token");
0526412bbb26 DFA refactoring
cin
parents:
diff changeset
82
176
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
83 var ab = CreateAlphabet();
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
84 var optimal = dfa.Optimize(ab);
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
85
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
86 return new ScannerContext<TTag>(
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
87 optimal.CreateTransitionTable(),
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
88 optimal.CreateFinalStateTable(),
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
89 optimal.CreateTagTable(),
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
90 optimal.InitialState,
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
91 ab.GetTranslationMap()
0c3c69fe225b rewritten the text scanner
cin
parents: 172
diff changeset
92 );
162
0526412bbb26 DFA refactoring
cin
parents:
diff changeset
93 }
0526412bbb26 DFA refactoring
cin
parents:
diff changeset
94
0526412bbb26 DFA refactoring
cin
parents:
diff changeset
95 }
0526412bbb26 DFA refactoring
cin
parents:
diff changeset
96
0526412bbb26 DFA refactoring
cin
parents:
diff changeset
97
0526412bbb26 DFA refactoring
cin
parents:
diff changeset
98 }