Читайте также:
|
Класс Grammar.
class Grammar
{ // KC-Grammar (T,V,P,S)
ArrayList T = null; // множество вcех терминалов
ArrayList V = null; // множество всех нетерминалов
ArrayList P = new ArrayList(); // множество вcех правил порождения
string S = null; // начальный символ
// атрибутное программирование на C#
public ArrayList t { get { return T; } set { T = value; } }
public ArrayList v { get { return V; } set { V = value; } }
public ArrayList p
{
get { return P; }
set { P = value; }
}
public string s { get { return S; } set { S = value; } }
public Grammar()
{
Init();
}
public void Init()
{ // задание правил
T = new ArrayList() { "i", "*", ":", "(", ")" };
V = new ArrayList() { "S", "F", "L", "A" };
S = "S";
Rule rule = null;
// 1. transition
rule = new Rule("S", new ArrayList() { "(", "F", ":", "L", ")" });
P.Add(rule);
// 2. transition
rule = new Rule("F", new ArrayList() { "L", "*", });
P.Add(rule);
// 3. transition
rule = new Rule("F", new ArrayList() { "i" });
P.Add(rule);
// 4. transition
rule = new Rule("L", new ArrayList() { "i" });
P.Add(rule);
rule = new Rule("L", new ArrayList() { "i", "A" });
P.Add(rule);
rule = new Rule("A", new ArrayList() { "*", "A" });
P.Add(rule);
rule = new Rule("A", new ArrayList() { "*" });
P.Add(rule);
} // end
public void lrecdel() // устранение левой рекурсии
{
ArrayList P1; // новые правила
ArrayList V1 = new ArrayList(); // новые символы A`
foreach (string A in V) // i=1,..,n
{
P1 = new ArrayList();
foreach (Rule r in P) P1.Add(r);
foreach (string B in V) // j=1,..,i-1
{
if (B == A) break; // j=i
foreach (Rule r in P)
if (r.right.Count!= 0 && r.left.ToString() == A && r.right[0].ToString() == B)
{ // замена правил для j<i-1
P1.Remove(r);
foreach (Rule r1 in P)
if (r1.left.ToString() == B)
{
ArrayList rulright = new ArrayList();
foreach (string q in r1.right) rulright.Add(q);
Rule rul = new Rule(A, rulright);
for (int i = 1; i < r.right.Count; i++) rul.right.Add(r.right[i]);
P1.Add(rul);
}
}
P = new ArrayList();
foreach (Rule r in P1) P.Add(r);
}
bool inc = false; // есть ли непосредственная левая рекурсия
foreach (Rule r in P) // определение inc
if (r.right.Count!= 0 && r.left.ToString() == A && r.right[0].ToString() == A) { inc = true; V1.Add(A + "`"); }
if (inc) // если есть - замена правил, добавление символа A`
{
foreach (Rule r in P)
{
if (r.right.Count!= 0 && r.left.ToString() == A && r.right[0].ToString() == A)
{
P1.Remove(r);
Rule rul = new Rule(A + "`", new ArrayList() { "" });
for (int i = 1; i < r.right.Count; i++) rul.right.Add(r.right[i]);
rul.right.Add(A + "`");
P1.Add(rul);
}
else if (r.left.ToString() == A)
{
P1.Remove(r);
Rule rul = new Rule(A, r.right);
rul.right.Add(A + "`");
P1.Add(rul);
}
}
Rule rul1 = new Rule(A + "`", new ArrayList() { "e" });
P1.Add(rul1);
}
P = new ArrayList();
foreach (Rule r in P1) P.Add(r);
} // замена и добавление новых правил и символов, упорядочивание
foreach (string A in V1) if (!V.Contains(A)) V.Add(A);
P1 = new ArrayList();
foreach (string A in V)
foreach (Rule r in P)
if (r.left.ToString() == A) P1.Add(r);
P = new ArrayList();
foreach (Rule r in P1) P.Add(r);
}
public void prout() // вывод на экран
{
Console.WriteLine("\n Сформирована грамматика G");
Console.WriteLine("Начальное состояние: " + S);
Console.Write("Множество терминальных символов: ");
foreach (string t in T) Console.Write(t);
Console.Write("\n");
Console.Write("Множество нетерминальных символов: ");
foreach (string v in V) Console.Write(v);
Console.Write("\n");
Console.WriteLine("Множество правил порождения:");
foreach (Rule r in P)
{
Console.Write(r.left.ToString() + " -> ");
foreach (string rr in r.right)
{
Console.Write(rr);
}
Console.WriteLine("\n");
}
}
}
Класс Rule.
class Rule
{ // структура Rule правил порождения
private string Left = null;
private ArrayList Right = null;
public string left { get { return Left; } set { Left = value; } }
public ArrayList right { get { return Right; } set { Right = value; } }
// Rule A => {a}
// Left Right
public Rule(string Left, ArrayList Right)
{
this.Left = Left;
this.Right = Right;
}
public void DebugRuleRight()
{
int i = 0;
for (; i < this.right.Count; i++)
{
if (i == 0)
System.Console.Write(" (" + this.right[i]);
else
System.Console.Write("," + this.right[i]);
}
if (i == 0)
System.Console.WriteLine();
else
System.Console.WriteLine(") ");
}
} // end class Rule
Класс MPAutomate.
class MPAutomate
{ // MP-Automate (Q,T,G,D,Q0,Z,F)
ArrayList Q = null; // множество состояний
ArrayList T = null; // входной алфавит
ArrayList G = new ArrayList(); // алфавит магазинных символов
ArrayList D = new ArrayList(); // отображения delta
string Q0 = null; // начальное состояние
Stack Z = new Stack(); // магазин
ArrayList F = null; // множество заключительных состояний
// атрибутное программирование на C#
public ArrayList t { get { return T; } set { T = value; } }
public ArrayList q { get { return Q; } set { Q = value; } }
public ArrayList g { get { return G; } set { G = value; } }
public ArrayList d
{
get { return D; }
set { D = value; }
}
public string q0 { get { return Q0; } set { Q0 = value; } }
public Stack z { get { return Z; } set { Z = value; } }
public ArrayList f { get { return F; } set { F = value; } }
public MPAutomate() { }
public MPAutomate(Grammar gramm)
{
Init(gramm); // иницинализация по данной КС-грамматике
}
class Delta
{ // структура Delta отображения
private string LeftQ = null; // исходное состояние
private string LeftT = null; // символ входной цепочки
private string LeftZ = null; // верхний символ магазин
private ArrayList RightQ = null; // множество следующих состояний
private ArrayList RightZ = null; // множество символов магазина
public string leftQ { get { return LeftQ; } set { LeftQ = value; } }
public string leftT { get { return LeftT; } set { LeftT = value; } }
public string leftZ { get { return LeftZ; } set { LeftZ = value; } }
public ArrayList rightQ { get { return RightQ; } set { RightQ = value; } }
public ArrayList rightZ { get { return RightZ; } set { RightZ = value; } }
// Delta (q1, a, z) = { {q}, {z1z2...} }
// LeftQ LeftT LeftZ RightQ RightZ
public Delta(string LeftQ, string LeftT, string LeftZ, ArrayList RightQ, ArrayList RightZ)
{
this.LeftQ = LeftQ;
this.LeftT = LeftT;
this.LeftZ = LeftZ;
this.RightQ = RightQ;
this.RightZ = RightZ;
}
} // end class Delta
public void Init(Grammar gramm)
{ // задание отображения D
Q = new ArrayList() { "q" }; // состояние
T = gramm.t; // входной алфавит
foreach (string v1 in gramm.v) // магазинные символы
G.Add(v1);
foreach (string t1 in gramm.t)
G.Add(t1);
Q0 = Q[0].ToString(); // начальное состояние
Z.Push(gramm.s); // начальный символ в магазине
F = new ArrayList(); // пустое множество заключительных состояний
Delta delta = null;
foreach (string v1 in gramm.v)
{ // сопоставление правил с отображениями
ArrayList q1 = new ArrayList();
ArrayList z1 = new ArrayList();
foreach (Rule rule in gramm.p)
{
if (rule.left == v1)
{
Stack zb = new Stack();
ArrayList rr = new ArrayList(rule.right);
rr.Reverse();
foreach (string s in rr)
zb.Push(s);
z1.Add(zb);
q1.Add(Q0);
}
}
delta = new Delta(Q0, "e", v1, q1, z1);
D.Add(delta);
}
foreach (string t1 in gramm.t)
{
Stack e = new Stack();
e.Push("e");
delta = new Delta(Q0, t1, t1, new ArrayList() { Q0 }, new ArrayList() { e });
D.Add(delta);
}
} // end
string printstack(Stack s) // печать текущего состояния магазина
{
string p = "|";
Stack s1 = new Stack();
while (s.Count!= 0)
{
s1.Push(s.Pop());
p = p + s1.Peek().ToString();
}
while (s1.Count!= 0) s.Push(s1.Pop());
return p;
}
int c = 1; // нумерация шагов в log
public bool check(string s, int i, int j, Stack z0) // проверка на допустимость
{ // рекурсивный метод (i-текущий символ в строке, j-текущее состояние, z0-текущие символы в магазине)
if (z0.Count!= 0 && z0.Peek().ToString() == "S") c = 1;
if (i == s.Length) // если конец строки
{
if (z0.Count == 0) // если магазин пуст
{
if (F.Count == 0) return true; // множество заключительных состояний пусто
else if (F.Contains(Q[j])) return true; // или автомат дошел до заключительного состояния
else return false;
}
else return false;
}
bool k = false; // успех/неуспех работы
string a = s[i].ToString();
string cq = Q[j].ToString();
foreach (Delta delta in D)
{
if (delta.leftQ == cq && (delta.leftT == a || delta.leftT == "e") && delta.leftZ == z0.Peek().ToString()) // подходящее правило для текущей конфигурации
{
Stack zz1 = new Stack(); // здесь и далее - создание дополнительных стеков для магазина (предотвращение потери данных)
Stack zz2 = new Stack();
Console.Write(c.ToString() + ")"); // оформление отчета
c++;
Console.Write("Входная цепочка: ");
for (int l = i; l < s.Length; l++) Console.Write(s[l].ToString());
Console.Write("\n");
Console.Write("Магазин: ");
while (z0.Count!= 0) { Console.Write(z0.Peek().ToString()); zz2.Push(z0.Pop()); }
Console.Write("\n");
string zz;
while (zz2.Count!= 0)
{
zz = zz2.Pop().ToString();
if (zz!= "e")
{
zz1.Push(zz);
z0.Push(zz);
}
}
if (zz1.Count!= 0) zz1.Pop();
foreach (string q1 in delta.rightQ)
{
j = Q.IndexOf(q1); // переход в новое состояние
foreach (Stack z2 in delta.rightZ)
{
if (delta.rightQ[delta.rightZ.IndexOf(z2)].ToString() == q1) // замена верхнего символа на цепочку
{
// стек со снятой вершиной zz1 запоминаем в zz10
Stack zz10 = new Stack();
Stack zz20 = new Stack();
while (zz1.Count!= 0) zz20.Push(zz1.Pop());
string zzz;
while (zz20.Count!= 0)
{
zzz = zz20.Pop().ToString();
if (zzz!= "e")
{
zz10.Push(zzz);
zz1.Push(zzz);
}
}
// замена в стеке zz10
Stack z1 = new Stack();
while (z2.Count!= 0)
{
z1.Push(z2.Pop());
}
string z3;
while (z1.Count!= 0)
{
z3 = z1.Pop().ToString();
if (z3!= "e")
{
zz10.Push(z3);
z2.Push(z3);
}
}
// формирование стека z02 для нового такта
Stack z01 = new Stack();
Stack z02 = new Stack();
while (zz10.Count!= 0) z01.Push(zz10.Pop());
string z00;
while (z01.Count!= 0)
{
z00 = z01.Pop().ToString();
if (z00!= "e")
{
z02.Push(z00);
zz10.Push(z00);
}
}
if (delta.leftT == "e") i--;
if (check(s, i + 1, j, z02)) { k = true; return true; } // рекурсивный вызов
if (delta.leftT == "e") i++;
}
}
}
}
if (k) break;
}
if (k) return true;
else return false;
}
public void Debug()
{
Console.WriteLine("\n Сформирован МП-автомат");
Console.Write("Множество состояний: ");
foreach (string q in Q) Console.Write(q);
Console.Write("\n");
Console.Write("Алфавит входных символов: ");
foreach (string t in T) Console.Write(t);
Console.Write("\n");
Console.Write("Алфавит магазинных символов: ");
foreach (string g in G) Console.Write(g);
Console.Write("\n");
Console.Write("Начальное состояние: ");
Console.Write(Q0 + "\n");
Console.Write("Начальный символ в магазине: ");
Console.Write(Z.Peek().ToString() + "\n");
Console.Write("Множество заключительных состояний: ");
foreach (string f in F) Console.Write(f);
if (F.Count == 0) Console.Write("(пустое множество)");
Console.Write("\n");
Console.Write("Отображение:\n");
foreach (Delta delta in D)
{
Console.Write("(" + delta.leftQ + ", " + delta.leftT + ", " + delta.leftZ + ")= (" + delta.rightQ[0].ToString() + ", ");
foreach (Stack s in delta.rightZ)
Console.Write(printstack(s));
Console.Write(") \n");
}
}
}
Main.
Grammar G = new Grammar();
G.lrecdel();
G.prout();
MPAutomate MP = new MPAutomate(G);
MP.Debug();
Console.WriteLine("Сформирован МП-автомат, введите строчку для проверки на допустимость.");
string s = Console.ReadLine();
if (MP.check(s, 0, 0, MP.z) == true) Console.WriteLine("Цепочка допускается");
else Console.WriteLine("Цепочка не допускается");
Дата добавления: 2015-10-31; просмотров: 92 | Нарушение авторских прав
| <== предыдущая страница | | | следующая страница ==> |
| Определить свойства КА. Построить НДКА. Реализовать преобразование НДКА в ДКА. | | | Реализовать управляющую таблицу M для LL(k) анализатора. |