Теория языков программирования

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Лабораторные работы №1-4

по дисциплине

Теория языков программирования

Выполнил:

Студент группы 4382

Мухамадеев М.М.

Проверила: Бикмуллина И.И.

Казань 2023

Лабораторная работа № 1. Разработка транслитератора

программа транслитератор исходный текст

Текст задания

1. Спроектировать и отладить экранную форму для ввода исходных данных, вывода сообщений программы и управления программой.

2. Разработать и отладить транслитератор voidGetSymbol(), пример имеется в модуле uLexicalAnalizer из папки «Программы».

3. Для отладки транслитератора временно включить в обработчик нажатия кнопки цикл чтения с помощью функции GetSymbol() символов исходного текста и вывода результатов анализа в поле диагностических сообщений.

Теория

Транслятор (translator) - это служебная программа, которая преобразует программы, представленные на одном из языков программирования, в эквивалентные программы на другом языке; или исполняет программу. Например, входом транслятора может быть программа, написанная на традиционном языке программирования высокого уровня (Паскаль или С) или специализированном языке (PHP). Выходом транслятора может быть программа на языке ассемблера, промежуточном языке или машинном языке, либо просто выполненная последовательность некоторых действий, предписанных входным предложением.

Транслитератор - это обработчик литер. Основное назначение транслитератора заключается в посимвольном чтении исходного текста и отнесение прочитанной литеры к отному из классов: буква, цифра, спецсимвол и др. Таким образом, на выходе транслитератора получается последовательность классифицированных литер - литералов.

Алгоритм транслитерации:

Шаг 1. Продвинуть номер текущей литеры в строке.

Шаг 2. Если номер текущей литеры вышел за пределы строки, то перейти к очередной строке, установить номер текущей литеры в начало новой строки. Переход к новой строке осуществляется продвижением номера текущей строки и сопровождается проверкой на выход за пределы текста.

Шаг 3. Классифицировать текущую литеру по таблице кодов символов.

Выдаваемые сообщения:

- литера не принадлежит алфавиту;

- попытка чтения за пределами текста.

Код программы:

Form1.cs

using System;

using System.Windows.Forms;

namespace Translater

{

public partial class Form1 : Form

{

public Form1()

{

InitializeComponent();

tbFSource.AppendText("01ab!" + "\r\n");

tbFSource.AppendText("c1a");

int n = tbFSource.Lines.Length;

}

private void btnFStart_Click(object sender, EventArgs e)

{

CLex Lex = new CLex();

Lex.strPSource = tbFSource.Lines;

Lex.strPMessage = tbFMessage.Lines;

int x = tbFSource.TextLength;

int y = tbFSource.Lines.Length;

tbFMessage.Text = "";

try

{

while (Lex.enumPState != TState.Finish)

{

Lex.GetSymbol(); // Выводятся литеры и классификация

Lex.NextToken();

String s = "";

String s1 = "";

switch (Lex.enumFSelectionCharType)

{

case TCharType.Letter: { s1 = "Letter"; break; }

case TCharType.Digit: { s1 = "Digit"; break; }

case TCharType.Space: { s1 = "Space"; break; }

case TCharType.EndRow: { s = "KC"; s1 = "EndRow"; break; }

case TCharType.EndText: { s = "KT"; s1 = "EndText"; break; }

case TCharType.ExlamationMark: { s1 = "ExlamationMark"; break; }

}

String m = "(" + s + "," + s1 + ")"; //литера и ее тип

tbFMessage.Text += m; //добавляется в строку сообщение

}

}

catch (Exception exc)

{

tbFMessage.Text += exc.Message;

tbFSource.Select();

tbFSource.SelectionStart = 0;

int n = 0;

for (int i = 0; i < Lex.intPSourceRowSelection; i++) n += tbFSource.Lines[i].Length + 2;

n += Lex.intPSourceColSelection;

tbFSource.SelectionLength = n;

}

}

}

}

uLex.cs

using System;

namespace Translater

{

public enum TState

{

Start, Continue, Finish

}; //типсостояния

public enum TCharType

{ Letter, Digit, EndRow, EndText, Space, ReservedSymbol, ExlamationMark }; // типсимвола

public enum TToken

{ lxmIdentifier, lxmNumber, lxmUnknown, lxmEmpty, lxmLeftParenth, lxmRightParenth, lxmIs, lxmDot, lxmComma };

public class CLex//класс лексический анализатор

{

private String[] strFSource; // указатель на массив строк

private String[] strFMessage; // указатель намассивстрок

public TCharType enumFSelectionCharType;

public char chrFSelection;

private TState enumFState;

private int intFSourceRowSelection;

private int intFSourceColSelection;

private String strFLexicalUnit;

private TToken enumFToken;

public String[] strPSource { set { strFSource = value; } get { return strFSource; } }

public String[] strPMessage { set { strFMessage = value; } get { return strFMessage; } }

public TState enumPState { set { enumFState = value; } get { return enumFState; } }

public String strPLexicalUnit { set { strFLexicalUnit = value; } get { return strFLexicalUnit; } }

public TToken enumPToken { set { enumFToken = value; } get { return enumFToken; } }

public int intPSourceRowSelection { get { return intFSourceRowSelection; } set { intFSourceRowSelection = value; } }

public int intPSourceColSelection { get { return intFSourceColSelection; } set { intFSourceColSelection = value; } }

public CLex()

{

}

public void GetSymbol() //методклассалексическийанализатор

{

if (intFSourceColSelection > strFSource[intFSourceRowSelection].Length - 1)

{

intFSourceRowSelection++;

if (intFSourceRowSelection <= strFSource.Length - 1)

{

intFSourceColSelection = -1;

chrFSelection = '\0';

enumFSelectionCharType = TCharType.EndRow;

enumFState = TState.Continue;

}

else

{

chrFSelection = '\0';

enumFSelectionCharType = TCharType.EndText;

enumFState = TState.Finish;

}

}

else

{

chrFSelection = strFSource[intFSourceRowSelection][intFSourceColSelection]; //классификацияпрочитаннойлитеры

if (chrFSelection == ' ') enumFSelectionCharType = TCharType.Space;

else if (chrFSelection >= 'a' && chrFSelection <= 'd') enumFSelectionCharType = TCharType.Letter;

else if (chrFSelection == '0' || chrFSelection == '1') enumFSelectionCharType = TCharType.Digit;

else if (chrFSelection == '/') enumFSelectionCharType = TCharType.ReservedSymbol;

else if (chrFSelection == '*') enumFSelectionCharType = TCharType.ReservedSymbol;

else if (chrFSelection == '!') enumFSelectionCharType = TCharType.ExlamationMark;

else if (chrFSelection == '(' || chrFSelection == ')' || chrFSelection == ':' || chrFSelection == '-' || chrFSelection == ',' || chrFSelection == '.') enumFSelectionCharType = TCharType.ReservedSymbol;

else throw new System.Exception("Cимвол не алфавита");

enumFState = TState.Continue;

}

intFSourceColSelection++; // продвигаем номер колонки

}

private void TakeSymbol()

{

char[] c = { chrFSelection };

String s = new string(c);

strFLexicalUnit += s;

GetSymbol();

}

public void NextToken()

{

strFLexicalUnit = "";

if (enumFState == TState.Start)

{

intFSourceRowSelection = 0;

intFSourceColSelection = -1;

GetSymbol();

}

if (chrFSelection == '/')

{

GetSymbol();

if (chrFSelection == '/')

while (enumFSelectionCharType != TCharType.EndRow)

{

GetSymbol();

}

GetSymbol();

}

}

}

}

Результаты тестирования:

Лабораторная работа № 2. Разработка лексического анализатора

программа транслитератор исходный текст

Текст задания

Спроектировать и отладить экранную форму для ввода исходных данных, вывода сообщений программы и управления программой.

Включить из лабораторной работы № 1 транслитератор voidGetSymbol().

Составить регулярную грамматику для каждого вида слов.

Построить конечные автоматы для каждого вида слов, как правило, они будут недетерминированными.

Построить детерминированные конечные автоматы для каждого вида слов.

Составить объединенный конечный автомат.

Написать и отладить модуль лексического анализатора по алгоритму объединенного конечного автомата. Для чтения исходного текста использовать транслитератор. Предусмотреть обработчик лексических ошибок исходного текста, используется конструкция try … catch.

Для отладки лексического анализатора временно включить в обработчик нажатия кнопки цикл чтения слов исходного текста и вывода результатов лексического анализа.

Теория:

Лексический анализ (токенизация от англ. tokenizing) в информатике прелставляет собой процесс аналитического разбора входной последовательности символов на распознанные группы -- лексемы, с целью получения на выходе идентифицированных последовательностей, называемых токенами. В простых случаях понятия «лексема» и «токен» идентичны, но более сложные токенизаторы дополнительно классифицируют лексемы по различным типам (идентификатор, число, служебное слово и т. п.). Лексический анализ используется в трансляторах исходного текста языков программирования и в различных анализаторах слов естественного языка.

Лексема представляет собой последовательность символов исходной программы. На самом деле лексический анализатор работает с последовательностью литералов в случае, если в составе транслятора выделяется в отдельную единицу транслитератор.

Токен это объект, создающийся из лексемы в процессе лексического анализа. представляет собой классифицированную лексему, т.е. лексему, которой сопоставлено значение ее классификации. Токеном также называют класс однородных лексем. Имя токена - это абстрактный символ, с помощью которого токен обозначается в программе. Например, токен Number - число может обозначать множество слов, которые представляют собой запись числа. Таким образом, поток литералов превращается в лексическом анализаторе в поток токенов. Цель такой конвертации обычно состоит в том, чтобы подготовить входную последовательность для грамматического (синтаксического) анализатора, и избавить его от определения лексических подробностей в контекстно-свободной грамматике (что привело бы к усложнению грамматики).

Базовые элементы, из которых конструируются строки и предложения определяемого формальной грамматикой языка, называются терминальными символами языка. Название понятия «терминальный» (конечный) возникло вследствие использования для получения предложений языка процедуры вывода. На завершающем шаге вывода мы должны получить строку, которая состоит из терминального алфавита, т.е. алфавита определяемого грамматикой языка. Такие строки получили в формальных грамматиках название предложение.

Нетерминальные символы грамматики представляют у нас синтаксические переменные. Синтаксические переменные - это символы, которые не присутствуют в построенном с помощью вывода предложении, но они принимают участие в определении грамматики и построении промежуточных в выводе строк.

Конечный автомат, у которого возможно более одного перехода под управлением некоторого символа, получил название недетерминированного конечного автомата. Признаком недетерминированности диаграммного представления автомата является выход из состояния двух и более стрелок, помеченных одним и тем же символом. Для табличного представления автомата таким признаком является наличие хотя бы в одной клетке более одного состояния.

У детерминированного конечного автомата для каждого входного символа имеется единственный переход в новое состояние.

Вариант 21

(011)*001(010)*	(a|b|c|d)+	Вторые два символа всегда aс

Первое слово:

(011)*001(010)*

A > 0B | 0C

B > 1D

C > 0Е

D > 1А

E > 1 | 1F

F > 0G

G > 1H

H > 0 | 0F

Граф:



Недетерминированная матрица

	0	1
A	B,C
B		D
C	E
D		A
E		F,Fin
F	G
G		H
H	F,Fin
Fin

Граф

Детерминированная матрица

	0	1
A	BC
BС	E	D
D		A
E		FFin
FFin	G
G		H
H	FFin

Граф

Второе слово:

(a|b|c|d)⁺

Вторые два символа всегда aс

A > aB | bB | cB | dB

B > aС

C > c | cD

D > a | b | c | d | aD | bD | cD | dD

Недетерминированная матрица

	a	b	c	d
A	B	B	B	B
B	C
C			D,Fin
D	D,Fin	D,Fin	D,Fin	D,Fin
Fin

Граф

Детерминированная матрица

	a	b	c	d
A	B	B	B	B
B	C
C			D,Fin
DFin	D,Fin	D,Fin	D,Fin	D,Fin

Граф

Код программы:

Form1.cs

using System;

using System.Windows.Forms;

namespace Translater

{

public partial class Form1 : Form

{

public Form1()

{

InitializeComponent();

tbFSource.AppendText("011011001010010" + "\r\n");

tbFSource.AppendText("aacdb");

int n = tbFSource.Lines.Length;

}

private void btnFStart_Click(object sender, EventArgs e)

{

CLex Lex = new CLex();

Lex.strPSource = tbFSource.Lines;

Lex.strPMessage = tbFMessage.Lines;

Lex.intPSourceColSelection = -1;

Lex.intPSourceRowSelection = 0;

int x = tbFSource.TextLength;

int y = tbFSource.Lines.Length;

tbFMessage.Text = "";

try

{

Lex.GetSymbol(); // Выводятся литеры и классификация

while (Lex.enumPState != TState.Finish)

{

Lex.NextToken();

String s = "";

String s1 = "";

switch (Lex.enumPToken)

{

case TToken.lxmNumber: { s = "LxmNumber"; s1 = Lex.strPLexicalUnit; break; }

case TToken.lxmIdentifier: { s = "lxmId"; s1 = Lex.strPLexicalUnit; break; }

}

String m = "(" + s + "," + s1 + ")"; //литера и ее тип

tbFMessage.Text += m; //добавляется в строку сообщение

}

}

catch (Exception exc)

{

tbFMessage.Text += exc.Message;

tbFSource.Select();

tbFSource.SelectionStart = 0;

int n = 0;

for (int i = 0; i < Lex.intPSourceRowSelection; i++) n += tbFSource.Lines[i].Length + 2;

n += Lex.intPSourceColSelection;

tbFSource.SelectionLength = n;

}

}

}

}

uLex.cs

using System;

namespace Translater

{

public enum TState

{

Start, Continue, Finish

}; //типсостояния

public enum TCharType

{ Letter, Digit, EndRow, EndText, Space, ReservedSymbol }; // типсимвола

public enum TToken

{ lxmIdentifier, lxmNumber, lxmUnknown, lxmEmpty, lxmLeftParenth, lxmRightParenth, lxmIs, lxmDot, lxmComma, lxmText };

public class CLex//класс лексический анализатор

{

private String[] strFSource; // указатель на массив строк

private String[] strFMessage; // указательнамассивстрок

public TCharType enumFSelectionCharType;

public char chrFSelection;

private TState enumFState;

private int intFSourceRowSelection;

private int intFSourceColSelection;

private String strFLexicalUnit;

private TToken enumFToken;

public String[] strPSource { set { strFSource = value; } get { return strFSource; } }

public String[] strPMessage { set { strFMessage = value; } get { return strFMessage; } }

public TState enumPState { set { enumFState = value; } get { return enumFState; } }

public String strPLexicalUnit { set { strFLexicalUnit = value; } get { return strFLexicalUnit; } }

public TToken enumPToken { set { enumFToken = value; } get { return enumFToken; } }

public int intPSourceRowSelection { get { return intFSourceRowSelection; } set { intFSourceRowSelection = value; } }

public int intPSourceColSelection { get { return intFSourceColSelection; } set { intFSourceColSelection = value; } }

public void GetSymbol() //метод класса лексический анализатор

{

intFSourceColSelection++; // продвигаемномерколонки

if (intFSourceColSelection > strFSource[intFSourceRowSelection].Length - 1)

{

intFSourceRowSelection++;

if (intFSourceRowSelection <= strFSource.Length - 1)

{

intFSourceColSelection = -1;

chrFSelection = '\0';

enumFSelectionCharType = TCharType.EndRow;

enumFState = TState.Continue;

}

else

{

chrFSelection = '\0';

enumFSelectionCharType = TCharType.EndText;

enumFState = TState.Finish;

}

}

else

{

chrFSelection = strFSource[intFSourceRowSelection][intFSourceColSelection]; //классификацияпрочитаннойлитеры

if (chrFSelection == ' ') enumFSelectionCharType = TCharType.Space;

else if (chrFSelection >= 'a' && chrFSelection <= 'd') enumFSelectionCharType = TCharType.Letter;

else if (chrFSelection == '0' || chrFSelection == '1') enumFSelectionCharType = TCharType.Digit;

else if (chrFSelection == '/') enumFSelectionCharType = TCharType.ReservedSymbol;

else if (chrFSelection == '*') enumFSelectionCharType = TCharType.ReservedSymbol;

else if (chrFSelection == '(' || chrFSelection == ')' || chrFSelection == ':' || chrFSelection == '-' || chrFSelection == ',' || chrFSelection == '.') enumFSelectionCharType = TCharType.ReservedSymbol;

else throw new System.Exception("Cимволв не алфавита");

enumFState = TState.Continue;

}

}

private void TakeSymbol()

{

char[] c = { chrFSelection };

String s = new string(c);

strFLexicalUnit += s;

GetSymbol();

}

public void NextToken()

{

strFLexicalUnit = "";

if (enumFState == TState.Start)

{

intFSourceRowSelection = 0;

intFSourceColSelection = -1;

GetSymbol();

}

while (enumFSelectionCharType == TCharType.Space || enumFSelectionCharType == TCharType.EndRow)

{

GetSymbol();

}

if (chrFSelection == '/')

{

GetSymbol();

if (chrFSelection == '/')

while (enumFSelectionCharType != TCharType.EndRow)

{

GetSymbol();

}

GetSymbol();

}

// Вариант 21

switch (enumFSelectionCharType)

{

case TCharType.Letter:

{

// a b c d

// A | B | B | B | B |

// B | C | | | |

// C | | |DFin| |

// D |DFin|DFin|DFin|DFin|

A:

{

if (chrFSelection == 'a' || chrFSelection == 'b' || chrFSelection == 'c' || chrFSelection == 'd')

{

TakeSymbol();

goto B;

}

}

B:

{

if (chrFSelection == 'a')

{

TakeSymbol();

goto C;

}

else throw new Exception("Вторые два символа должны быть 'ac'");

}

C:

{

if (chrFSelection == 'c')

{

TakeSymbol();

goto DFin;

}

else throw new Exception("Вторые два символа должны быть 'ac'");

}

DFin:

{

if (chrFSelection == 'a' || chrFSelection == 'b' || chrFSelection == 'c' || chrFSelection == 'd')

{

TakeSymbol();

goto DFin;

}

else

{

enumFToken = TToken.lxmIdentifier;

return;

}

}

}

case TCharType.Digit:

{

// 0 1

// A | BC | |

// BC | E | D |

// D | | A |

// E | |FFin |

// FFin | G | |

// G | | H |

// H |FFin | |

A:

if (chrFSelection == '0')

{

TakeSymbol();

goto BC;

}

else throw new Exception("Ожидался 0");

BC:

if (chrFSelection == '0')

{

TakeSymbol();

goto E;

}

else if (chrFSelection == '1')

{

TakeSymbol();

goto D;

}

else throw new Exception("Ожидался 0 или 1");

E:

if (chrFSelection == '1')

{

TakeSymbol();

goto FFin;

}

else throw new Exception("Ожидался 1");

D:

if (chrFSelection == '1')

{

TakeSymbol();

goto A;

}

else throw new Exception("Ожидался 1");

FFin:

if (chrFSelection == '0')

{

TakeSymbol();

goto G;

}

else if (enumFSelectionCharType != TCharType.Digit) { enumFToken = TToken.lxmNumber; return; }

else throw new Exception("Ожидалась 0");

G:

if (chrFSelection == '1')

{

TakeSymbol();

goto H;

}

else throw new Exception("Ожидался 1");

H:

if (chrFSelection == '0')

{

TakeSymbol();

goto FFin;

}

else throw new Exception("Ожидался 0");

}

case TCharType.ReservedSymbol:

{

if (chrFSelection == '/')

{

GetSymbol();

if (chrFSelection == '/')

{

while (enumFSelectionCharType != TCharType.EndRow)

GetSymbol();

}

GetSymbol();

}

if (chrFSelection == '(')

{

enumFToken = TToken.lxmLeftParenth;

GetSymbol();

return;

}

if (chrFSelection == ')')

{

enumFToken = TToken.lxmRightParenth;

GetSymbol();

return;

}

break;

}

case TCharType.EndText:

{

enumFToken = TToken.lxmEmpty;

break;

}

}

}

}

}

Результаты тестирования:

Лабораторная работа № 3. Разработка контекстно-свободного (КС) синтаксического анализатора

Текст задания

Для предложенного преподавателем варианта КС-грамматики разработать методом рекурсивного спуска синтаксический анализатор.

Теория:

Синтаксимческий анамлиз или разбор, памрсинг (от англ. parsing) - в лингвистике и информатике представляет собой процесс сопоставления линейной последовательности лексем (слов, токенов) естественного или формального языка его синтаксической структуры в соответствии с контекстно-свободной грамматикой. Синтаксическая структура, как правило, задается деревом разбора (синтаксическим деревом). Синтаксический анализ обычно выполняется одновременно с лексическим анализом.

Синтаксическим анализатором называется программа, решающая задачу разбора предложения с помощью контекстно-свободной грамматики, т.е. выделение в тексте контекстно-свободной составляющей (структуры) предложения.

Основные функции синтаксического анализатора:

чтение с помощью лексического анализатора исходного текста;

распознавание структуры или контекстно-свободного синтаксиса исходного текста;

построение синтаксического дерева (если это необходимо);

диагностика ошибок и информирование пользователя.

Правило устранения левой рекурсии в описании грамматики. Рассмотрим в самом общем виде систему леворекурсивных определений нетерминального символа:

A Aб₁ | … | A б_n | в₁ | … | в_m, где (*)

A - нетерминальный символ; б_i (i = 1 … n), в_j (j = 1 … m) - произвольные последовательности терминальных и нетерминальных символов, цепочки в_j (j = 1 … m) не начинаются с символа A.

Преобразуем систему (*) к виду:

A в₁ | … | в_m | в₁ B | … | в_m B

B б₁ | … | б_n | б₁ B | … | б_n B,

где В введенный новый нетерминальный символ.

Как видим, левая рекурсия устранена.

Грамматика

М> М + П | П

П> П * А | А

А> [ ] | [ S ]

S> <1>, S | <2> , S | <1> | <2> | [ A ]

Освобождение от левой рекурсии

М> П | ПB

B> + П | + ПB

П > А | АC

C> * А | * АC

А> [ ] | [ S ]

S> <1> | <2> | <1>, S | <2> , S | [ A ]

Form1.cs

using System;

using System.Windows.Forms;

namespace Translater

{

public partial class Form1 : Form

{

public Form1()

{

InitializeComponent();

tbFSource.AppendText("[]+[001]*[001,aac]+[aac]");

int n = tbFSource.Lines.Length;

}

private void btnFStart_Click(object sender, EventArgs e)

{

tbFMessage.Clear();

uSyntAnalyzer synt = new uSyntAnalyzer();

synt.Lex.strPSource = tbFSource.Lines;

synt.Lex.strPMessage = tbFMessage.Lines;

synt.Lex.enumPState = TState.Start;

try

{

synt.Lex.NextToken();

synt.Begin();

throw new Exception("Текст верный");

}

catch (Exception exc)

{

tbFMessage.Text += exc.Message;

tbFSource.Select();

tbFSource.SelectionStart = 0;

int n = 0;

for (int i = 0; i < synt.Lex.intPSourceRowSelection; i++) n += tbFSource.Lines[i].Length + 2;

n += synt.Lex.intPSourceColSelection;

tbFSource.SelectionLength = n;

}

}

}

}

uLex.cs

using System;

namespace Translater

{

public enum TState

{

Start, Continue, Finish

}; //типсостояния

public enum TCharType

{ Letter, Digit, EndRow, EndText, Space, ReservedSymbol }; // типсимвола

public enum TToken

{ lxmIdentifier, lxmNumber, lxmUnknown, lxmEmpty, lxmLeftParenth, lxmRightParenth, lxmStar, lxmPlus, lxmComma, lxmText };

public class CLex//класс лексический анализатор

{

private String[] strFSource; // указатель на массив строк

private String[] strFMessage; // указательнамассивстрок

public TCharType enumFSelectionCharType;

public char chrFSelection;

private TState enumFState;

private int intFSourceRowSelection;

private int intFSourceColSelection;

private String strFLexicalUnit;

private TToken enumFToken;

public String[] strPSource { set { strFSource = value; } get { return strFSource; } }

public String[] strPMessage { set { strFMessage = value; } get { return strFMessage; } }

public TState enumPState { set { enumFState = value; } get { return enumFState; } }

public String strPLexicalUnit { set { strFLexicalUnit = value; } get { return strFLexicalUnit; } }

public TToken enumPToken { set { enumFToken = value; } get { return enumFToken; } }

public int intPSourceRowSelection { get { return intFSourceRowSelection; } set { intFSourceRowSelection = value; } }

public int intPSourceColSelection { get { return intFSourceColSelection; } set { intFSourceColSelection = value; } }

public void GetSymbol() //метод класса лексический анализатор

{

intFSourceColSelection++; // продвигаемномерколонки

if (intFSourceColSelection > strFSource[intFSourceRowSelection].Length - 1)

{

intFSourceRowSelection++;

if (intFSourceRowSelection <= strFSource.Length - 1)

{

intFSourceColSelection = -1;

chrFSelection = '\0';

enumFSelectionCharType = TCharType.EndRow;

enumFState = TState.Continue;

}

else

{

chrFSelection = '\0';

enumFSelectionCharType = TCharType.EndText;

enumFState = TState.Finish;

}

}

else

{

chrFSelection = strFSource[intFSourceRowSelection][intFSourceColSelection]; //классификацияпрочитаннойлитеры

if (chrFSelection == ' ') enumFSelectionCharType = TCharType.Space;

else if (chrFSelection >= 'a' && chrFSelection <= 'd') enumFSelectionCharType = TCharType.Letter;

else if (chrFSelection == '0' || chrFSelection == '1') enumFSelectionCharType = TCharType.Digit;

else if (chrFSelection == '/') enumFSelectionCharType = TCharType.ReservedSymbol;

else if (chrFSelection == '*') enumFSelectionCharType = TCharType.ReservedSymbol;

else if (chrFSelection == '+') enumFSelectionCharType = TCharType.ReservedSymbol;

else if (chrFSelection == ',') enumFSelectionCharType = TCharType.ReservedSymbol;

else if (chrFSelection == '[' || chrFSelection == ']' || chrFSelection == ':' || chrFSelection == '-' || chrFSelection == ',' || chrFSelection == '.') enumFSelectionCharType = TCharType.ReservedSymbol;

else throw new System.Exception("Cимволв не алфавита");

enumFState = TState.Continue;

}

}

private void TakeSymbol()

{

char[] c = { chrFSelection };

String s = new string(c);

strFLexicalUnit += s;

GetSymbol();

}

public void NextToken()

{

strFLexicalUnit = "";

if (enumFState == TState.Start)

{

intFSourceRowSelection = 0;

intFSourceColSelection = -1;

GetSymbol();

}

while (enumFSelectionCharType == TCharType.Space || enumFSelectionCharType == TCharType.EndRow)

{

GetSymbol();

}

if (chrFSelection == '/')

{

GetSymbol();

if (chrFSelection == '/')

while (enumFSelectionCharType != TCharType.EndRow)

{

GetSymbol();

}

GetSymbol();

}

// Вариант 21

switch (enumFSelectionCharType)

{

case TCharType.Letter:

{

// a b c d

// A | B | B | B | B |

// B | C | | | |

// C | | |DFin| |

// D |DFin|DFin|DFin|DFin|

A:

{

if (chrFSelection == 'a' || chrFSelection == 'b' || chrFSelection == 'c' || chrFSelection == 'd')

{

TakeSymbol();

goto B;

}

}

B:

{

if (chrFSelection == 'a')

{

TakeSymbol();

goto C;

}

else throw new Exception("Вторые два символа должны быть 'ac'");

}

C:

{

if (chrFSelection == 'c')

{

TakeSymbol();

goto DFin;

}

else throw new Exception("Вторые два символа должны быть 'ac'");

}

DFin:

{

if (chrFSelection == 'a' || chrFSelection == 'b' || chrFSelection == 'c' || chrFSelection == 'd')

{

TakeSymbol();

goto DFin;

}

else

{

enumFToken = TToken.lxmIdentifier;

return;

}

}

}

case TCharType.Digit:

{

// 0 1

// A | BC | |

// BC | E | D |

// D | | A |

// E | |FFin |

// FFin | G | |

// G | | H |

// H |FFin | |

A:

if (chrFSelection == '0')

{

TakeSymbol();

goto BC;

}

else throw new Exception("Ожидался 0");

BC:

if (chrFSelection == '0')

{

TakeSymbol();

goto E;

}

else if (chrFSelection == '1')

{

TakeSymbol();

goto D;

}

else throw new Exception("Ожидался 0 или 1");

E:

if (chrFSelection == '1')

{

TakeSymbol();

goto FFin;

}

else throw new Exception("Ожидался 1");

D:

if (chrFSelection == '1')

{

TakeSymbol();

goto A;

}

else throw new Exception("Ожидался 1");

FFin:

if (chrFSelection == '0')

{

TakeSymbol();

goto G;

}

else if (enumFSelectionCharType != TCharType.Digit) { enumFToken = TToken.lxmNumber; return; }

else throw new Exception("Ожидалась 0");

G:

if (chrFSelection == '1')

{

TakeSymbol();

goto H;

}

else throw new Exception("Ожидался 1");

H:

if (chrFSelection == '0')

{

TakeSymbol();

goto FFin;

}

else throw new Exception("Ожидался 0");

}

case TCharType.ReservedSymbol:

{

if (chrFSelection == '/')

{

GetSymbol();

if (chrFSelection == '/')

{

while (enumFSelectionCharType != TCharType.EndRow)

GetSymbol();

}

GetSymbol();

}

if (chrFSelection == ',')

{

enumFToken = TToken.lxmComma;

GetSymbol();

return;

}

if (chrFSelection == '*')

{

enumFToken = TToken.lxmStar;

GetSymbol();

return;

}

if (chrFSelection == '+')

{

enumFToken = TToken.lxmPlus;

GetSymbol();

return;

}

if (chrFSelection == '[')

{

enumFToken = TToken.lxmLeftParenth;

GetSymbol();

return;

}

if (chrFSelection == ']')

{

enumFToken = TToken.lxmRightParenth;

GetSymbol();

return;

}

break;

}

case TCharType.EndText:

{

enumFToken = TToken.lxmEmpty;

break;

}

}

}

}

}

uSyntAnalyser

using System;

namespace Translater

{

public class uSyntAnalyzer

{

public CLex Lex = new CLex();

public void Begin()

{

M();

}

void M()

{

P();

if(Lex.enumPToken == TToken.lxmPlus) B();

}

void B()

{

if (Lex.enumPToken == TToken.lxmPlus)

{

Lex.NextToken();

P();

if (Lex.enumPToken == TToken.lxmPlus)

{

B();

}

}

else

{

throw new Exception("Ожидался +");

}

}

void P()

{

A();

if(Lex.enumPToken == TToken.lxmStar) C();

}

void C()

{

if (Lex.enumPToken == TToken.lxmStar)

{

Lex.NextToken();

A();

if (Lex.enumPToken == TToken.lxmStar)

{

C();

}

}

else

{

throw new Exception("Ожидался *");

}

}

void A()

{

if (Lex.enumPToken == TToken.lxmLeftParenth)

{

Lex.NextToken();

}

else

{

throw new Exception("Ожидался [");

}

if (Lex.enumPToken == TToken.lxmRightParenth)

{

Lex.NextToken();

}

else

{

S();

if (Lex.enumPToken == TToken.lxmRightParenth)

{

Lex.NextToken();

}

else

{

throw new Exception("Ожидался ]");

}

}

}

void S()

{

if (Lex.enumPToken == TToken.lxmNumber || Lex.enumPToken == TToken.lxmIdentifier)

{

Lex.NextToken();

if (Lex.enumPToken == TToken.lxmComma)

{

Lex.NextToken();

S();

}

}

else if (Lex.enumPToken == TToken.lxmLeftParenth)

{

Lex.NextToken();

A();

if (Lex.enumPToken == TToken.lxmRightParenth)

{

Lex.NextToken();

}

else

{

throw new Exception("Ожидался ]");

}

}

else

{

throw new Exception("Ожидался число или идентификатор или [ или ,");

}

}

}

}

Результаты:

[]+[001]*[001,aac]+[aac]

[[[]]]*[011011001,[[]]]+[001010]*[bacda]+[dacb,001]*[011001010,cacd]

[[[011001,dac,bac,011001010]]]

Ошибка

Лабораторная работа № 4. Введение табличного способа хранения слов

Теоретический материал

Для решения задачи поиска необходимого элемента среди данных большого объема был предложен алгоритм хеширования (hashing - перемешивание), при котором создаются ключи, определяющие данные массива и на их основании данные записываются в таблицу, названную хеш-таблицей. Ключи для записи определяются при помощи функции i = h(key), называемой хеш-функцией. Алгоритм хеширования определяет положение искомого элемента в хеш-таблице по значению его ключа, полученного хеш-функцией.

Понятие хеширования - это разбиение общего (базового) набора уникальных ключей элементов данных на непересекающиеся наборы с определенным свойством.

Возьмем, например, словарь или энциклопедию. В этом случае буквы алфавита могут быть приняты за ключи поиска, т.е. основным элементом алгоритма хеширования является ключ (key). В большинстве приложений ключ обеспечивает косвенную ссылку на данные.

Фактически хеширование - это специальный метод адресации данных для быстрого поиска нужной информации по ключам.

Если базовый набор содержит N элементов, то его можно разбить на 2^N различных подмножеств.

Хеш-таблица и хеш-функции

Функция, отображающая ключи элементов данных во множество целых чисел (индексы в таблице - хеш-таблица), называется функцией хеширования, или хеш-функцией:

i = h(key)

где key - преобразуемый ключ, i - получаемый индекс таблицы, т.е. ключ отображается во множество целых чисел (хеш-адреса), которые впоследствии используются для доступа к данным.

Однако хеш-функция для нескольких значений ключа может давать одинаковое значение позиции i в таблице. Ситуация, при которой два или более ключа получают один и тот же индекс (хеш-адрес), называется коллизией при хешировании.

Хорошей хеш-функцией считается такая функция, которая минимизирует коллизии и распределяет данные равномерно по всей таблице, а совершенной хеш-функцией - функция, которая не порождает коллизий:

Разрешить коллизии при хешировании можно двумя методами:

- методом открытой адресации с линейным опробыванием;

- методом цепочек.

Хеш-таблица

Хеш-таблица представляет собой обычный массив с необычной адресацией, задаваемой хеш-функцией.

Хеш-структуру считают обобщением массива, который обеспечивает быстрый прямой доступ к данным по индексу.

Имеется множество схем хеширования, различающихся как выбором удачной функции h(key), так и алгоритма разрешения конфликтов. Эффективность решения реальной практической задачи будет существенно зависеть от выбираемой стратегии.

Примеры хеш-функций

Выбираемая хеш-функция должна легко вычисляться и создавать как можно меньше коллизий, т.е. должна равномерно распределять ключи на имеющиеся индексы в таблице. Конечно, нельзя определить, будет ли некоторая конкретная хеш-функция распределять ключи правильно, если эти ключи заранее не известны. Однако, хотя до выбора хеш-функции редко известны сами ключи, некоторые свойства этих ключей, которые влияют на их распределение, обычно известны. Рассмотрим наиболее распространенные методы задания хеш-функции.

Метод деления. Исходными данными являются - некоторый целый ключ key и размер таблицы m. Результатом данной функции является остаток от деления этого ключа на размер таблицы. Общий вид функции:

int h(int key, int m) {

return key % m; // Значения

}

Для m = 10 хеш-функция возвращает младшую цифру ключа.

Для m = 100 хеш-функция возвращает две младшие цифры ключа.

Аддитивный метод, в котором ключом является символьная строка. В хеш-функции строка преобразуется в целое суммированием всех символов и возвращается остаток от деления на m (обычно размер таблицы m = 256).

int h(char *key, int m) {

int s = 0;

while(*key)

s += *key++;

return s % m;

}

Коллизии возникают в строках, состоящих из одинакового набора символов, например, abc и cab.

Данный метод можно несколько модифицировать, получая результат, суммируя только первый и последний символы строки-ключа.

int h(char *key, int m) {

int len = strlen(key), s = 0;

if(len < 2)// Если длина ключа равна 0 или 1,

s = key[0];// возвратить key[0]

else

s = key[0] + key[len-1];

return s % m;

}

В этом случае коллизии будут возникать только в строках, например, abc и amc.

Метод середины квадрата, в котором ключ возводится в квадрат (умножается сам на себя) и в качестве индекса используются несколько средних цифр полученного значения.

Например, ключом является целое 32-битное число, а хеш-функция возвращает средние 10 бит его квадрата:

int h(int key) {

key *= key;

key >>= 11;// Отбрасываем 11 младших бит

return key % 1024;// Возвращаем 10 младших бит

}

Метод исключающего ИЛИ для ключей-строк (обычно размер таблицы m=256). Этот метод аналогичен аддитивному, но в нем различаются схожие слова. Метод заключается в том, что к элементам строки последовательно применяется операция «исключающее ИЛИ».

В мультипликативном методе дополнительно используется случайное действительное число r из интервала [0,1), тогда дробная часть произведения r*key будет находиться в интервале [0,1]. Если это произведение умножить на размер таблицы m, то целая часть полученного произведения даст значение в диапазоне от 0 до m-1.

int h(int key, int m) {

double r = key * rnd();

r = r - (int)r;// Выделили дробную часть

return r * m;

}

В общем случае при больших значениях m индексы, формируемые хеш-функцией, имеют большой разброс. Более того, математическая теория утверждает, что распределение получается более равномерным, если m является простым числом.

В рассмотренных примерах хеш-функция i = h(key) только определяет позицию, начиная с которой нужно искать (или первоначально - поместить в таблицу) запись с ключом key. Поэтому схема хеширования должна включать алгоритм решения конфликтов, определяющий порядок действий, если позиция i = h(key) оказывается уже занятой записью с другим ключом.

Схемы хеширования

В большинстве задач два и более ключей хешируются одинаково, но они не могут занимать в хеш-таблице одну и ту же ячейку. Существуют два возможных варианта: либо найти для нового ключа другую позицию, либо создать для каждого индекса хеш-таблицы отдельный список, в который помещаются все ключи, преобразованные в этот индекс.

Эти варианты и представляют собой две классические схемы:

- хеширование методом цепочек (со списками), или так называемое многомерное хеширование - chaining with separate lists;

- хеширование методом открытой адресации с линейным опробыванием - linear probe open addressing.

Метод открытой адресации с линейным опробыванием. Изначально все ячейки хеш-таблицы, которая является обычным одномерным массивом, помечены как не занятые. Поэтому при добавлении нового ключа проверяется, занята ли данная ячейка. Если ячейка занята, то алгоритм осуществляет осмотр по кругу до тех пор, пока не найдется свободное место («открытый адрес»), т.е. либо элементы с однородными ключами размещают вблизи полученного индекса, либо осуществляют двойное хеширование, используя для этого разные, но взаимосвязанные хеш-функции.

В дальнейшем, осуществляя поиск, сначала находят по ключу позицию i в таблице, и, если ключ не совпадает, то последующий поиск осуществляется в соответствии с алгоритмом разрешения конфликтов, начиная с позиции i по списку.

Метод цепочек используется чаще предыдущего. В этом случае полученный хеш-функцией индекс i трактуется как индекс в хеш-таблице списков, т.е. ключ key очередной записи отображается на позицию i = h(key) таблицы. Если позиция свободна, то в нее помещается элемент с ключом key, если же она занята, то отрабатывается алгоритм разрешения конфликтов, в результате которого такие ключи добавляются в список, начинающийся в i-й ячейке хеш-таблицы. Например, обозачив N -NULL:



В итоге имеем таблицу массива связных списков или деревьев.

Процесс заполнения (считывания) хеш-таблицы прост, но доступ к элементам требует выполнения следующих операций:

- вычисление индекса i;

- поиск в соответствующей цепочке.

Для улучшения поиска при добавлении нового элемента можно использовать алгоритма вставки не в конец списка, а - с упорядочиванием, т.е. добавлять элемент в нужное место.

При решении задач на практике необходимо подобрать хеш-функцию i = h(key), которая по возможности равномерно отображает значения ключа key на интервал [0, m-1], m - размер хеш-таблицы. И чаще всего, если нет информации о вероятности распределения ключей по записям, используя метод деления, берут хеш-функцию i = h(key) = key%m.

При решении обратной задачи - доступ (поиск) к определенному подмножеству возможен из хеш-таблицы (хеш-структуры), которая обеспечивает по хеш-адресу (индексу) быстрый доступ к нужному элементу.

Размещено на Allbest.ru