Здравствуйте, WolfHound, Вы писали:
VD>>Понял? Попробуй написать на ЯП. А я посмотрю сколько времени и сил убъёш. Ну, или в своих словах пересказать. WH>Писать не буду. Не до того сечас. А словами объяснить могу.
Вот реализация НДКА и функций Move и EpsilonMove
public class State
{
private int m_Number;
public int Number
{
get { return m_Number; }
}
public State(int number)
{
m_Number = number;
}
private StateSet m_Epsilon = new StateSet();
public StateSet Epsilon
{
get { return m_Epsilon; }
}
private Hashtable m_SignalTransitionsMap = new Hashtable();
public StateSet this[char signal]
{
get
{
StateSet set = (StateSet) m_SignalTransitionsMap[signal];
if (set == null)
{
set = new StateSet();
m_SignalTransitionsMap[signal] = set;
}
return set;
}
}
public bool CanMoveTo(char signal)
{
return m_SignalTransitionsMap.Contains(signal);
}
}
public class StateSet : IEnumerable
{
private Hashtable m_States = new Hashtable();
public StateSet Clone()
{
StateSet set = new StateSet();
foreach (State state in this)
set.Add(state);
return set;
}
public void Add(State state)
{
if (!Contains(state))
m_States.Add(state, state);
}
public void Remove(State state)
{
m_States.Remove(state);
}
public bool Contains(State state)
{
return m_States.Contains(state);
}
public IEnumerator GetEnumerator()
{
return m_States.Keys.GetEnumerator();
}
public int Count
{
get { return m_States.Count; }
}
public override bool Equals(object obj)
{
StateSet that = obj as StateSet;
if (that == null)
return false;
if (this.Count != that.Count)
return false;
foreach (State state in this)
if (!that.Contains(state))
return false;
return true;
}
public override int GetHashCode()
{
int hash = 0;
foreach (State state in this)
hash += state.GetHashCode();
return hash;
}
}
private static StateSet Move(StateSet set, char signal)
{
StateSet newSet = new StateSet();
foreach (State state in set)
if (state.CanMoveTo(signal))
foreach (State nextState in state[signal])
newSet.Add(nextState);
return newSet;
}
private static StateSet EpsilonMove(StateSet set)
{
StateSet newSet = set.Clone();
foreach (State state in set)
EpsilonMoveRec(state, newSet);
return newSet;
}
private static void EpsilonMoveRec(State state, StateSet newSet)
{
foreach (State nextState in state.Epsilon)
if (!newSet.Contains(nextState))
{
newSet.Add(nextState);
EpsilonMoveRec(nextState, newSet);
}
}
private static void Main()
{
State s1 = new State(1);
State s2 = new State(2);
State s3 = new State(3);
State s4 = new State(4);
State s5 = new State(5);
State s6 = new State(6);
State s7 = new State(7);
State s8 = new State(8);
State s9 = new State(9);
s1.Epsilon.Add(s2);
s1.Epsilon.Add(s3);
s1.Epsilon.Add(s6);
s2['b'].Add(s5);
s3['a'].Add(s4);
s4.Epsilon.Add(s6);
s5.Epsilon.Add(s6);
s6.Epsilon.Add(s1);
s6['a'].Add(s7);
s7['b'].Add(s8);
s8['b'].Add(s9);
StateSet set = new StateSet();
set.Add(s1);
set = EpsilonMove(set);
PrintSet(set);
set = Move(set, 'a');
PrintSet(set);
set = Move(set, 'b');
PrintSet(set);
set = EpsilonMove(set);
PrintSet(set);
}
private static void PrintSet(StateSet set)
{
if (set.Count == 0)
{
Console.WriteLine("Empty set.");
}
else
{
foreach (State state in set)
Console.Write(state.Number + " ");
Console.WriteLine();
}
}
}
Остальное допишу в другой раз. Сейчас времени нет.
НДКА для регулярного выражения (a|b)*abb
... << RSDN@Home 1.1.4 beta 6a rev. 436>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[28]: Theory and Techniques of Compiler Construction
Здравствуйте, WolfHound, Вы писали:
WH>Писать не буду. Не до того сечас. А словами объяснить могу.
Нашол немного времени.
Из такого (a|b)*abb регулярного выражения получается вот такой ДКА:
1
a -> 5
b -> 2
2 end
a -> 5
b -> 4
3 start
a -> 5
b -> 4
4
a -> 5
b -> 4
5
a -> 5
b -> 1
Этот автомат еще можно оптимизировать по колличеству состояний но это в другой раз.
Вот полная версия
DFSMBuilder.cs
using System.Collections;
namespace FSM
{
internal class DFSMBuilder
{
private Queue m_Queue = new Queue();
private Hashtable m_States = new Hashtable();
public Hashtable States
{
get { return m_States; }
}
public void Build(params State[] states)
{
StateSet set = new StateSet();
foreach (State state in states)
set.Add(state);
Add(EpsilonMove(set));
while (m_Queue.Count > 0)
{
StateData state = (StateData) m_Queue.Dequeue();
foreach (char signal in Signals(state.Set))
{
StateSet next = EpsilonMove(Move(state.Set, signal));
state.SetTransition(signal, next);
Add(next);
}
}
}
private IEnumerable Signals(StateSet set)
{
Hashtable signals = new Hashtable();
foreach (State state in set)
foreach (char signal in state.Signals)
signals[signal] = null;
return signals.Keys;
}
private void Add(StateSet set)
{
if (!m_States.Contains(set))
{
StateData state = new StateData(set);
m_Queue.Enqueue(state);
m_States[set] = state;
}
}
public class StateData
{
private readonly StateSet m_Set;
public StateData(StateSet set)
{
m_Set = set;
}
private Hashtable m_Transitions = new Hashtable();
public Hashtable Transitions
{
get { return m_Transitions; }
}
public StateSet Set
{
get { return m_Set; }
}
public void SetTransition(char signal, StateSet set)
{
m_Transitions.Add(signal, set);
}
}
private StateSet Move(StateSet set, char signal)
{
StateSet newSet = new StateSet();
foreach (State state in set)
foreach (State nextState in state.Get(signal))
newSet.Add(nextState);
return newSet;
}
private StateSet EpsilonMove(StateSet set)
{
StateSet newSet = set.Clone();
foreach (State state in set)
EpsilonMoveRec(state, newSet);
return newSet;
}
private void EpsilonMoveRec(State state, StateSet newSet)
{
foreach (State nextState in state.Epsilon)
if (!newSet.Contains(nextState))
{
newSet.Add(nextState);
EpsilonMoveRec(nextState, newSet);
}
}
}
}
State.cs
using System.Collections;
namespace FSM
{
public class State
{
private object m_Data;
public object Data
{
get { return m_Data; }
}
public State()
{}
public State(object data)
{
m_Data = data;
}
private StateSet m_Epsilon = new StateSet();
public StateSet Epsilon
{
get { return m_Epsilon; }
}
private Hashtable m_SignalTransitionsMap = new Hashtable();
public void Add(char signal, State state)
{
StateSet set = (StateSet) m_SignalTransitionsMap[signal];
if (set == null)
{
set = new StateSet();
m_SignalTransitionsMap[signal] = set;
}
set.Add(state);
}
public StateSet Get(char signal)
{
StateSet set = (StateSet) m_SignalTransitionsMap[signal];
if (set == null)
return new StateSet();
return set;
}
public IEnumerable Signals
{
get { return m_SignalTransitionsMap.Keys; }
}
}
}
StateSet.cs
using System.Collections;
namespace FSM
{
public class StateSet : IEnumerable
{
private Hashtable m_States = new Hashtable();
public StateSet Clone()
{
StateSet set = new StateSet();
foreach (State state in this)
set.Add(state);
return set;
}
public void Add(State state)
{
if (!Contains(state))
m_States.Add(state, state);
}
public void Remove(State state)
{
m_States.Remove(state);
}
public bool Contains(State state)
{
return m_States.Contains(state);
}
public IEnumerator GetEnumerator()
{
return m_States.Keys.GetEnumerator();
}
public int Count
{
get { return m_States.Count; }
}
public override bool Equals(object obj)
{
StateSet that = obj as StateSet;
if (that == null)
return false;
if (this.Count != that.Count)
return false;
foreach (State state in this)
if (!that.Contains(state))
return false;
return true;
}
public override int GetHashCode()
{
int hash = 0;
foreach (State state in this)
hash += state.GetHashCode();
return hash;
}
}
}
SM.cs
namespace FSM
{
public struct SM
{
public State S1;
public State S2;
public static SM Signal(char signal)
{
SM sm = new SM();
sm.S1 = new State();
sm.S2 = new State();
sm.S1.Add(signal, sm.S2);
return sm;
}
public static SM Or(params SM[] seq)
{
SM sm = new SM();
sm.S1 = new State();
sm.S2 = new State();
foreach (SM sm1 in seq)
{
sm.S1.Epsilon.Add(sm1.S1);
sm1.S2.Epsilon.Add(sm.S2);
}
return sm;
}
public static SM Seq(params SM[] seq)
{
SM sm = new SM();
sm.S1 = seq[0].S1;
sm.S2 = seq[seq.Length - 1].S2;
for (int i = 0; i < seq.Length - 1; ++i)
seq[i].S2.Epsilon.Add(seq[i + 1].S1);
return sm;
}
public static SM Star(SM sm)
{
sm.S1.Epsilon.Add(sm.S2);
sm.S2.Epsilon.Add(sm.S1);
return sm;
}
}
}
Programm.cs
using System;
using System.Collections;
namespace FSM
{
internal class Programm
{
private static void Main()
{
SM sm =
SM.Seq(
SM.Star(
SM.Or(
SM.Signal('a'),
SM.Signal('b')
)
),
SM.Signal('a'),
SM.Signal('b'),
SM.Signal('b')
);
State start = new State();
State end = new State();
sm.S2.Epsilon.Add(end);
start.Epsilon.Add(sm.S1);
DFSMBuilder builder = new DFSMBuilder();
builder.Build(start);
Hashtable dfsm = new Hashtable();
int n = 1;
foreach (DFSMBuilder.StateData data in builder.States.Values)
dfsm[data.Set] = n++;
foreach (DFSMBuilder.StateData stateData in builder.States.Values)
{
Console.Write(dfsm[stateData.Set]);
if (stateData.Set.Contains(start))
Console.Write(" start");
if (stateData.Set.Contains(end))
Console.Write(" end");
Console.WriteLine();
foreach (DictionaryEntry entry in stateData.Transitions)
{
char signal = (char) entry.Key;
StateSet stateSet = (StateSet) entry.Value;
Console.WriteLine("{0} -> {1}", signal, dfsm[stateSet]);
}
Console.WriteLine();
}
}
}
}
... << RSDN@Home 1.1.4 beta 6a rev. 436>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[29]: Theory and Techniques of Compiler Construction
Неплохо. Хотя Epsilon и EpsilonMove требует более детального описания.
Кстати, раз уж ты хорошо въехал в это дело, то может поможешь решить одну задачку?
Простой пример. C-шные комментарии:
Тестовая /*строка для эксперементов над*/ комментариями. Она /*используется для того*/ чтобы было что комментарить.
Можно создать простую грамматику чтобы распарсить комментарии:
/\*.*\*/
Для нее не составляет труда построить конечный автомат описнным тобой методом или методом построения ДКА из АСТ.
Но, к сожалению, эта грамматика найдет комментарий не верно:
Тестовая /*строка для экспериментов над*/ комментариями. Она /*используется для того*/ чтобы было что комментарить.
Грубо говоря ДКА подведет "жадность".
В МС-ных регэкспах можно уменьшить жадность выражения ".*" подставив за звездочкой вопросительный знак:
/\*.*?\*/
Этот вариант дас верный результат:
Тестовая /*строка для экспериментов над*/ комментариями. Она /*используется для того*/ чтобы было что комментарить.
Собственно вопрос в том, как подобное запихнуть в построитель ДКА?
Как варинт устроило бы нечто вроде введения контекста. Например, в КокоР данную грамматику можно описать так?
Здравствуйте, VladD2, Вы писали:
VD>Здравствуйте, Шахтер, Вы писали:
Ш>>Здравствуйте, VladD2, Вы писали:
Ш>>/\*([^*]|((\*)+[^/*]))*(\*)*\*/
VD>Здорово, но я к стыду не могу понять принцип того как это работает.
VD>Объясни, плиз.
VD>ЗЫ
VD>Ну, и все же впрос остается, так как выкидывать такие кренделя вместо простого и элегентного решения — это не задорово.
Суть дела проста. У нас есть грубое решение LongCommentsDraft = "/*" + All + "*/" , где All — класс всех строк.
Что нас не устраивает. Если задана строка из этого класса, то некоторый префикс может тоже принадлежать этому же классу. И нам нужно это дело исключить.
Данная ситуация возникает, как легко видеть, когда мы имеем дело со строкой "/*" + s + "*/" , где s -- строка, которая содержит внутри подстроку "*/".
Таким образом, правильное решение -- LongComments = "/*" + LongCommentBody + "*/" , где LongCommentBody -- класс строк, не содержащих подстрок "*/" .
Чтобы описать этот класс строк, опишем сначала дополнительный класс -- ~LongCommentBody, это класс строк, которые содержат подстроки "*/" ,
этот класс легко описать регулярным выражением All + "*/" + All . Хорошо известно, что дополнение к регулярному классу есть регулярный класс.
И это дополнение тривиально строится, если этот регулярный класс задан стейт-машиной. Таким образом, нам надо перейти от регулярного выражения к стейт-машине, инвертировать её, а затем опять построить регулярное выражение.
Будем обозначать множество всех символов через A (алфавит).
M>Для каждого токена строится минимизированный ДКА. Понятно, что в результате, при лексическом анализе, получается недетерминированный автомат. Поэтому, я на ходу произвожу моделированние ДКА делая параллельный проход по автоматам для каждого подходящего токена. Такая реализация была связана со спецификой задачи, которую я реализовывал. Необходимо было создать лексический анализатор, который оперирует на основе динамически пополняемого множества токенов. Поэтому, неудобно было создавать и потом каждый раз убивать общий ДКА, очень медленно получалось. Нет никакого ограничения на построение единого ДКА для всех токенов грамматики.
Кстати, интересный подход. Я когда лет 10 назад "додумался" до его модификации — строил несколько ДКА по грамматике. Правда, не на каждый токен, а на как бы класс похожих токенов. Это было связано со сложностью, объемностью и плохой минимизируемостью "общего" ДКА. Одна деталь беспокоила — я так и не додумался как объединять токены в группы ДКА, кроме как полным перебором вариантов с поиском минимальных. По тем временам эта была задача не решаемая в разумные сроки техникой (PC-XT), поэтому группировал вручную, строил ДКА, потом опять и т.д. итеративно пока результат не удовлетворил.
Re[29]: Theory and Techniques of Compiler Construction
Здравствуйте, Quintanar, Вы писали:
Q>Как-то больно примитивно. Фактически переложение доказательства теоремы о том, что для любого НДКА существует эквивалентный ДКА, единственная здравая мысль — строить состояния ДКА динамически, но это неизбежно, поскольку ДКА из НДКА получается невероятно большим.
Без минимизации да. Более того, не из всякого НДКА можно построить ДКА. Если к состояниям НДКА привязаны выходные сигналы и они конфликтуют при объединении состояний в процессе построения ДКА, то на этом — конец построения с неудачей.
Oberon Books
Programming in Oberon — M. Reiser and N. Wirth [PDF (21.7 MB)]
The Oberon System — M. Reiser — Out-of-print
Project Oberon — The Design of an Operating System and Compiler — N. Wirth and J. Gutknecht [PDF (4'398 KB)]
Compiler Construction — N. Wirth [PDF (597 KB)]
Programming in Oberon (2004) — A derivative of Programming in Modula-2 (1982) — N. Wirth [PDF (334 KB)]
Algorithms and Data Structures (1985) (Oberon version: August 2004) — N. Wirth [PDF (1'241 KB)]
Re[8]: Theory and Techniques of Compiler Construction
Здравствуйте, compiler-dev, Вы писали:
F>>У меня есть такая. Кому надо — вышлю по запросу в мыло. Объем 1.2 Мб в zip CD>Большое спасибо! CD>compiler-dev@narod.ru
