LR-анализатор. LR(k)-грамматики. Замечание о пополненной грамматике. LR-разборщик. Принцип переноса-свёртки, страница 3

{-1,-1,-1},

{-1,-1,-1},

{-1,-1,-1},

{-1,-1,-1},

{-1,-1,-1},

{-1,-1,-1},

{-1,-1,-1},

{15,11,3},

{-1,-1,-1},

{-1,-1,-1},

{-1,-1,-1},

{-1,-1,-1}

};

lr.Make("abccba$");

}

}

class LR_analize

{

Stack<char> stack = new Stack<char>();

public char[] term = new char[] { 'i', '+', '*', '$' }, //массив терминалов

neterm = new char[] { 'e', 'E', 'T', 'F' }; //массив нетерминалов

public int[,] netermPrav = new int[,] {

{ 0, -1,},

{ 1, 2 }, //массив правил

{ 3, 4 }, //соответствующих нетерминалу

{ 5, -1 }

};

//массив правил грамматики

public char[][] pravila = new char[][] {

new char[] { 'E', '|', '|' },

new char[] {'E', '+', 'T' },

new char[] { 'T', '|', '|' },

new char[] { 'T', '*', 'F' },

new char[] { 'F', '|', '|' },

new char[] { 'i', '|', '|' }

};

//таблица действий обозначающих тип действия

public string[,] stAction = new string[,] {

{ "s", "-", "-", "-" },

{ "-", "s", "-", "A" },

{ "-", "r", "s", "r" },

{ "-", "r", "r", "r" },

{ "s", "-", "-", "-" },

{ "-", "r", "s", "r" },

{ "-", "r", "r", "r" },

{ "s", "-", "-", "-" },

{ "-", "r", "r", "r" }

};

//таблица переходов

public int[,] tGoto = new int[,] {

{ 1, 2, 3 },

{ -1, -1, -1 },

{ -1, -1, -1 },

{ -1, -1, -1 },

{ -1, 5, 3 },

{ -1, -1, -1 },

{ -1, -1, -1 },

{ -1, -1, 8 },

{ -1, -1, -1 }

},

//таблица действий обозначающих нужное состояние

itAction = new int[,] {

{6,-1,-1,-1},

{-1,4,-1,0},

{-1,2,7,2},

{-1,4,4,4},

{6,-1,-1,-1},

{-1,1,7,1},

{-1,5,5,5},

{6,-1,-1,-1},

{-1,3,3,3}

};

char[] inString;

public void Make(string input)

{

int i=0;

inString = input.ToArray();

Console.WriteLine("Input string: {0}", input);

char inSym = inString[i];

stack.Push('0'); //помещаем в стек начальное состояние

while (inSym != '$' || !stack.Peek().Equals('e') ) // пока входной символ не $ или верхний символ стека не "е"

{

int inSymInd = FindIndexBySym(inSym), //находим индекс входного символа

indS = stack.Peek() - 48; //индекс состояния наверху стека

if (stAction[indS, inSymInd].Equals("s")) //если Shift, то

{

stack.Push(term[inSymInd]); //помещаем терминал на вершину стека

stack.Push((char)(itAction[indS, inSymInd] + 48)); //помещаем соответствующее состояние на вершину стека

inSym = inString[++i]; //переходим к следующеиму входному символу

}

else if (stAction[indS, inSymInd].Equals("r")) //если Reduce, то

{

for (int j = 0; j < 2*countMass(itAction[indS, inSymInd]); j++)

stack.Pop(); //удаляем с вершины стека элементы количеством 2*|w|

int prevS = stack.Peek() - 48;

stack.Push((char)(neterm[findPrav(itAction[indS, inSymInd])])); //помещаем на вершину стека правило из таблицы itAction

if (!inSym.Equals('i')) { inSym = stack.Peek(); inSymInd = FindIndexBySym(inSym)-1; }

stack.Push((char)(tGoto[prevS, inSymInd] + 48)); //помещаем на вершину стека состояние соответствующее текущему правилу

inSym = inString[i];

inSymInd = FindIndexBySym(inSym);

char str1 = neterm[findPrav(itAction[indS, inSymInd])];

int fp = itAction[indS, inSymInd];

string str2 = printPrav(fp);

Console.WriteLine("{0}->{1}", str1, str2); //вывод правила для свертки

}

else if (stAction[indS, inSymInd] == "A") //если Accept, то

{

return; //завершаем программу

}

else { error(); return; }

}

}

int FindIndexBySym(char input) //нахождение индекса териминала или нетерминала

{

for (int j = 0; j < term.Length; j++) if (input == term[j]) return j;

for (int j = 0; j < neterm.Length; j++) if (input == neterm[j]) return j;

return -1;

}

string printPrav(int prav)

{

string str = "";

foreach (char x in pravila[prav])

if (x != '|') str += x;

str += " (" + prav + ")";

return str;

}

int findPrav(int input)

{

int width = 3, height = 4;

for(int i=0;i<height;i++)

for (int j = 0; j < width; j++)

{

if (netermPrav[i, j] == input) return i;

}

return -1;

}

int countMass(int prav)

{

int count = 0;

foreach (char x in pravila[prav])

if (x != '|') count++;

return count;

}

void error()

{

Console.WriteLine("ERROR!!!!!");

}

}

Приложение В

Скриншот работы программы