Пояснительная записка к курсовой работе по курсу «Теория языков программирования и методы трансляции» Выполнил студент гр. 230661




НазваниеПояснительная записка к курсовой работе по курсу «Теория языков программирования и методы трансляции» Выполнил студент гр. 230661
страница1/2
Дата публикации09.05.2013
Размер0.51 Mb.
ТипПояснительная записка
www.vbibl.ru > Информатика > Пояснительная записка
  1   2
Федеральное агентство по образованию

Государственное общеобразовательное учреждение высшего образования

Тульский государственный университет

Кафедра АТМ

Пояснительная записка к курсовой работе

по курсу «Теория языков программирования и методы трансляции»

Выполнил студент гр. 230661

Хиндикайнен А.С.
Проверил профессор кафедры АТМ доктор ф.- м. наук Двоенко С. Д.

Тула 2010

Содержание
Введение 4

  1. Постановка задачи 5

  2. Теоретическая справка 6

  3. Решение поставленной задачи 6

    1. Создание сканера 6

    2. Создание синтаксического анализатора 8

    3. Текст программы 9

    4. Инструкция пользователю 22

    5. Инструкция программисту 23

    6. Тестовый пример 25

Заключение 26

Список использованных источников 27

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

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

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



  1. Постановка задачи


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


    1. Описание условного языка программирования


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


Ключевые слова

Операторы

Идентификаторы

Логические операции

Комментарии

WHILE

WEND

FOR

TO

NEXT

SQRT

DOUBLE

LONG

BEGIN

END

+, -, *, /, (, ),

=, !=, <, >, :=

(лат.буква)

(лат.буква| _ |

цифра)*

&& (И)

| | (ИЛИ)

! (НЕ)

{*…*}

{{ - до конца

строки


Грамматика языка:

::=
"" |

::= "BEGIN" “END”

::= "" |

::= "&&" | "||" | "!" |

">" | "<" | "="

| "!=" | "+" | "-" |

::= "*" | "/" |

::= | | "(" ")"

::= "+" |

::= ":=" | ":="

::= "" |

::=^ "DOUBLE" | "LONG"

::= | "CONST"| "SQRT"

| "WHILE" "(" ")" "WEND"

| "FOR" "=" "TO" "NEXT"


    1. Описание вычислительной задачи


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



  1. Теоретические сведения


Текст на исходном ЯП не может быть непосредственно выполнен на вычислительной машине и должен быть сперва преобразован в некоторое внутренне представление. Этот процесс носит название трансляции. Общая схема трансляции (рисунок 1) состоит из следующих этапов:

  1. Лексический анализ. На этом этапе последовательность символов исходного файла преобразуется в последовательность лексем.

  2. Синтаксический (грамматический) анализ. Последовательность лексем преобразуется в дерево разбора.

  3. Семантический анализ. Дерево разбора обрабатывается с целью установления его семантики (смысла) — например, привязка идентификаторов к их декларациям, типам, проверка совместимости, определение типов выражений и т. д. Результат обычно называется «промежуточным представлением/кодом», и может быть дополненным деревом разбора, новым деревом, абстрактным набором команд или чем-то ещё, удобным для дальнейшей обработки.

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

  5. Генерация кода. Из промежуточного представления порождается код на целевом языке.



  1. Выполнение поставленной задачи


Разработку транслятора для решения поставленной задачи будем вести последовательно реализуя вышеописанные этапы трансляции. Т.е. необходимо создать анализатор, состоящий из сканера и синтаксического анализатора, и генератора исполняемого кода для абстрактной стековой машины.
3.1 Создание сканера
Логика работы сканера очень хорошо описывается с помощью конечного автомата, который выполняет распознавание символьных цепочек – лексем исходного языка. Распознав очередной токен, сканер добавляет его в последовательность символов представляющих собой промежуточное представление исходной программы. На рисунке 1 приведена схема такого автомата.
“=”

“!”

Not(“\n” || “\0”)

digit ||letter||’_’

Not“N”

Not“D”

Not“E”

“E”

“W”

Not(digit || letter||’_’)

letter

digit ||letter||’_’

letter

Not(digit || letter)

digit

digit

“=”

“:”

“+”,”-”,”*”,”(”,”)”…

Not“}”

“\0”

n” || “\0”

“{”

“*”

Not (“*” || “\0”)

“*”

“{”

WhiteSpace

ε

“\0”

comment

“}”

error

operator

number

identifier

“N”

“D”

Not(digit || letter||’_’)

keyword


Рисунок 1 – Конечный автомат

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

Приведём исходную леворекурсивную грамматику к праворекурсивному виду.


::=
"" |

::="BEGIN" “END”

::= ""

::= | “”

::= "!" |

::= "&&" | "||" |

">" | "<" | "="

| "!=" | "+" | "-" | “”

::=

::= "*" | "/" | “”

::= | | "(" ")"

::=

::="+" | “”

::= ":=" | ":="

::= ""

::= | ””

::=^ "DOUBLE" | "LONG"

::= | "CONST"| "SQRT"

| "WHILE" "(" ")" "WEND"

| "FOR" "=" "TO" "NEXT"

На следующем шаге определим значения функции First для каждого нетерминального символа грамматики.

FIRST(program) = {“”}

FIRST(compound_statement) = {“”}

FIRST(statement_sequence) = {“”}

FIRST(statement_sequence|) = {“CONST”, “SQRT”, “WHILE”, “FOR”, id, “”}

FIRST(expression) = {“!”, id, num, “(“}

FIRST(expression’) = {&&, ||, >, <, =, !=, +, -, “”}
FIRST(term) = {id, num, “(“}

FIRST(term’) = {“*”, “/”, “”}

FIRST(factor) = {id, num, “(“}

FIRST(string_e) = {string}

FIRST(string_e’) = {+, “”}

FIRST(assume) = {id}

FIRST(declarations) = {“”}

FIRST(declarations’) = {“DOUBLE”, “LONG”, “”}

FIRST (standard_type) = {Float, Long}

FIRST (statement) = {id, “CONST”, “SQRT”, “WHILE”, “FOR”}

3.3 Текст программы
Ниже представлен текст программы-транслятора с условного языка программирования, написанной на языке C#.
Листинг 1 – класс ArithmeticStackMachine
public class ArithmeticStackMachine {

delegate double Operation(double first, double second);
PostfixTokenList list;

public ArithmeticStackMachine(PostfixTokenList list) {

this.list = list;

}
public object Calculate(VariablesTable variablesTable) {

PostfixTokenStack stack = new PostfixTokenStack(list);

try {

CalculateCore(stack, variablesTable);

return GetTokenValue(stack.Pop(), variablesTable);

} finally {

if (stack.Count != 0)

throw new InvalidProgramException();

}

}
void CalculateCore(PostfixTokenStack stack, VariablesTable variablesTable) {

if (stack.Count == 1)

return;
Operation operation = null;

Token top = stack.Pop();

if (top.TokenString == "+") {

operation = (x, y) => y + x;

}

if (top.TokenString == "-") {

operation = (x, y) => y - x;

}

if (top.TokenString == "*") {

operation = (x, y) => y * x;

}

if (top.TokenString == "/") {

operation = (x, y) => y / x;

}

if (top.TokenString == "=") {

operation = (x, y) => x == y ? 1 : 0;

}

if (top.TokenString == "!=") {

operation = (x, y) => x != y ? 1 : 0;

}

if (top.TokenString == ">") {

operation = (x, y) => y > x ? 1 : 0;

}

if (top.TokenString == "<") {

operation = (x, y) => y < x ? 1 : 0;

}

if (top.TokenString == "&&") {

operation = (x, y) => (x != 0 && y!=0) ? 1 : 0;

}

if (top.TokenString == "||") {

operation = (x, y) => (x != 0 || y !=0) ? 1 : 0;

}

Token first = stack.Peek();

if (first.Type == TokenType.Operator) {

CalculateCore(stack, variablesTable);

first = stack.Pop();

} else {

stack.Pop();

}

Token second = stack.Peek();

if (second.Type == TokenType.Operator) {

CalculateCore(stack, variablesTable);

second = stack.Pop();

} else {

stack.Pop();

}

stack.Push(new Token(TokenType.Number,

(operation(GetTokenValue(first, variablesTable), GetTokenValue(second, variablesTable))).ToString(CultureInfo.InvariantCulture)));

}
double GetTokenValue(Token token, VariablesTable variablesTable) {

if (token.Type == TokenType.Number)

return double.Parse(token.TokenString, CultureInfo.InvariantCulture);
if (token.Type == TokenType.Identifier)

return (double)variablesTable.GetValue(token);
throw new NotImplementedException();

}

}
Листинг 2 – класс GrammarAnalizer
public static class GrammarAnalyzer {

public static PostfixTokenList Analyze(TokenCollection tokens, out Program program) {

if (tokens == null)

throw new ArgumentNullException("tokens");

TokenQueue queue = new TokenQueue(tokens);

program = new Program();

return AnalyzeCore(queue, ref program);

}
static PostfixTokenList AnalyzeCore(TokenQueue queue, ref Program program) {

try {

PostfixTokenList list = new PostfixTokenList();

list.AddRange(Program(queue, ref program));

return list;

} finally {

if (queue.Count != 0) {

throw new Exception(string.Format("Expected: \"{0}\" but was: \"{1}\"", "end of token stream", GetTokenString(queue)));

}

}

}

static string GetTokenString(TokenQueue tokensQueue) {

return tokensQueue.Count == 0 ? "End of tokens stream" : tokensQueue.Peek().InternalString;

}

static Token NextToken(TokenQueue tokensQueue, string exprected) {

string currentTokenString = GetTokenString(tokensQueue);

if (currentTokenString == exprected) {

return tokensQueue.Dequeue();

} else throw new Exception(string.Format("Expected: \"{0}\" but was: \"{1}\"", exprected, currentTokenString));

}

//
::= “” |

static PostfixTokenList Program(TokenQueue tokensQueue, ref Program program) {

PostfixTokenList list = new PostfixTokenList();

list.AddRange(_Declarations(tokensQueue, ref program));

list.AddRange(CompoundStatement(tokensQueue, program.Statements));

return list;

}

// ::=

static PostfixTokenList CompoundStatement(TokenQueue tokensQueue, List statements) {

PostfixTokenList list = new PostfixTokenList();

list.Add(NextToken(tokensQueue, "BEGIN"));

list.AddRange(_StatementSequence(tokensQueue, statements));

list.Add(NextToken(tokensQueue, "END"));

return list;

}

// ::= “”

// ::= | “”

static PostfixTokenList _StatementSequence(TokenQueue tokensQueue, List statements) {

PostfixTokenList list = new PostfixTokenList();

string tokenString = GetTokenString(tokensQueue);

if (tokenString == "Identifier" || tokenString == "CONST" || tokenString == "SQRT" || tokenString == "WHILE" || tokenString == "FOR") {

list.AddRange(Statement(tokensQueue, statements));

list.AddRange(_StatementSequence(tokensQueue, statements));

}

return list;

}
//::= | "CONST"| "SQRT"

// | "WHILE" "(" ")" "WEND"

// | "FOR" "=" "TO" "NEXT"
static PostfixTokenList Statement(TokenQueue tokensQueue, List statements) {

PostfixTokenList list = new PostfixTokenList();

string tokenString = GetTokenString(tokensQueue);

if (tokenString == "Identifier") {

list.AddRange(Assume(tokensQueue, statements));

return list;

} else if (tokenString == "CONST") {

list.Add(NextToken(tokensQueue, tokenString));

return list;

} else if (tokenString == "SQRT") {

Token postfix = NextToken(tokensQueue, tokenString);

list.AddRange(Expression(tokensQueue));

list.Add(postfix);

return list;

} else if (tokenString == "WHILE") {

Token postfix = NextToken(tokensQueue, tokenString);

NextToken(tokensQueue, "(");

PostfixTokenList expression = Expression(tokensQueue);

list.AddRange(expression);

NextToken(tokensQueue, ")");

list.Add(postfix);

CycleWhileStatement cycle = new CycleWhileStatement(new ArithmeticStackMachine(expression));

list.AddRange(CompoundStatement(tokensQueue, cycle.InnerStatements));

statements.Add(cycle);

list.Add(NextToken(tokensQueue, "WEND"));

return list;

} else if (tokenString == "FOR") {

Token forPostfix = NextToken(tokensQueue, tokenString);

Token controlVariable = Identifier(tokensQueue);

list.Add(controlVariable);

Token equalsPostfix = NextToken(tokensQueue, "=");

PostfixTokenList initialValue = Expression(tokensQueue);

list.AddRange(initialValue);

list.Add(equalsPostfix);

list.Add(forPostfix);

Token toPostfix = NextToken(tokensQueue, "TO");

PostfixTokenList lastValue = Expression(tokensQueue);

list.AddRange(lastValue);

list.Add(toPostfix);

CycleForStatement cycle = new CycleForStatement(controlVariable, new ArithmeticStackMachine(initialValue), new ArithmeticStackMachine(lastValue));

statements.Add(cycle);

list.AddRange(CompoundStatement(tokensQueue, cycle.InnerStatements));

list.Add(NextToken(tokensQueue, "NEXT"));

return list;

} else throw new Exception(string.Format("Statement expected, but was: \"{0}\"", tokenString));

}

// ::= “!” |

static PostfixTokenList Expression(TokenQueue tokensQueue) {

PostfixTokenList list = new PostfixTokenList();

string tokenString = GetTokenString(tokensQueue);

if (tokenString == "!") {

list.Add(NextToken(tokensQueue, tokenString));

list.AddRange(Factor(tokensQueue));

list.AddRange(_Expression(tokensQueue));

return list;

} else if (tokenString == "Identifier" || tokenString == "Number" || tokenString == "(") {

list.AddRange(Term(tokensQueue));

list.AddRange(_Expression(tokensQueue));

return list;

} else

throw new Exception(string.Format("Expression expected, but was: \"{0}\"", tokenString));

}

// ::= “&&” | “||” |

// “>” | “<” |

// “=” | “!=” |

// “+” | “-” | “”

static PostfixTokenList _Expression(TokenQueue tokensQueue) {

PostfixTokenList list = new PostfixTokenList();

string tokenString = GetTokenString(tokensQueue);

if (tokenString == "&&" || tokenString == "||" || tokenString == ">" ||

tokenString == "<" || tokenString == "=" || tokenString == "!=" ||

tokenString == "+" || tokenString == "-") {

Token postfix = NextToken(tokensQueue, tokenString);

list.AddRange(Term(tokensQueue));

list.AddRange(_Expression(tokensQueue));

list.Add(postfix);

}

return list;

}

// ::=

static PostfixTokenList Term(TokenQueue tokensQueue) {

PostfixTokenList list = new PostfixTokenList();

string tokenString = GetTokenString(tokensQueue);

if (tokenString == "Identifier" || tokenString == "Number" || tokenString == "(") {

list.AddRange(Factor(tokensQueue));

list.AddRange(_Term(tokensQueue));

return list;

} else

throw new Exception(string.Format("Identifier, number, or ( expected, but was: \"{0}\"", tokenString));

}

// ::= “*” | “/” | “”

static PostfixTokenList _Term(TokenQueue tokensQueue) {

PostfixTokenList list = new PostfixTokenList();

string tokenString = GetTokenString(tokensQueue);

if (tokenString == "*" || tokenString == "/") {

Token postfix = NextToken(tokensQueue, tokenString);

list.AddRange(Factor(tokensQueue));

list.AddRange(_Term(tokensQueue));

list.Add(postfix);

}

return list;

}

// ::= | | “(“ “)”

static PostfixTokenList Factor(TokenQueue tokensQueue) {

PostfixTokenList list = new PostfixTokenList();

string tokenString = GetTokenString(tokensQueue);

if (tokenString == "Identifier") {

Token identifier = Identifier(tokensQueue);

list.Add(identifier);

return list;

} else if (tokenString == "Number") {

list.AddRange(Num(tokensQueue));

return list;

} else if (tokenString == "(") {

NextToken(tokensQueue, tokenString);

list.AddRange(Expression(tokensQueue));

NextToken(tokensQueue, ")");

return list;

} else

throw new Exception(string.Format("Identifier, number, or ( expected, but was: \"{0}\"", tokenString));

}

static PostfixTokenList Num(TokenQueue tokensQueue) {

PostfixTokenList list = new PostfixTokenList();

string tokenString = GetTokenString(tokensQueue);

if (tokenString == "Number") {

list.Add(NextToken(tokensQueue, tokenString));

return list;

} else throw new Exception(string.Format("Number expected, but was: \"{0}\"", tokenString));

}

// ::= “:=” | “:=”

static PostfixTokenList Assume(TokenQueue tokensQueue, List statements) {

PostfixTokenList list = new PostfixTokenList();

string tokenString = GetTokenString(tokensQueue);

if (tokenString == "Identifier") {

Token identifier = Identifier(tokensQueue);

list.Add(identifier);

Token postfix = NextToken(tokensQueue, ":=");

tokenString = GetTokenString(tokensQueue);

if (tokenString == "!" || tokenString == "Identifier" ||

tokenString == "Number" || tokenString == "(") {

PostfixTokenList expression = Expression(tokensQueue);

list.AddRange(expression);

statements.Add(new AssumeStatement(identifier, new ArithmeticStackMachine(expression)));

list.Add(postfix);

return list;

} else if (tokenString == "String") {

list.AddRange(String(tokensQueue));

list.Add(postfix);

return list;

} else

throw new Exception(string.Format("Expected string or expression but was \"{0}\"", tokenString));

} else

throw new Exception(string.Format("Identifier type expected, but was: \"{0}\"", tokenString));

}

// ::=

static void String_e(TokenQueue tokensQueue) {

string tokenString = GetTokenString(tokensQueue);

if (tokenString == "String") {

String(tokensQueue);

_String_e(tokensQueue);

} else

throw new Exception(string.Format("String expected, but was: \"{0}\"", tokenString));

}

// ::= “+” | “”

static void _String_e(TokenQueue tokensQueue) {

string tokenString = GetTokenString(tokensQueue);

if (tokenString == "+") {

NextToken(tokensQueue, tokenString);

String(tokensQueue);

_String_e(tokensQueue);

}

}

static PostfixTokenList String(TokenQueue tokensQueue) {

PostfixTokenList list = new PostfixTokenList();

string tokenString = GetTokenString(tokensQueue);

if (GetTokenString(tokensQueue) == "String") {

list.Add(NextToken(tokensQueue, "String"));

return list;

} else

throw new Exception(string.Format("String expected, but was: \"{0}\"", tokenString));

}

// ::= “”

// ::= | “”

static PostfixTokenList _Declarations(TokenQueue tokensQueue, ref Program program) {

PostfixTokenList list = new PostfixTokenList();

string tokenString = GetTokenString(tokensQueue);

if (tokenString == "DOUBLE" || tokenString == "LONG") {

program.Declarations.Add(new Declaration(StandartType(tokensQueue), Identifier(tokensQueue)));

list.AddRange(_Declarations(tokensQueue, ref program));

}

return list;

}

static Token Identifier(TokenQueue tokensQueue) {

string tokenString = GetTokenString(tokensQueue);

if (tokenString == "Identifier") {

return NextToken(tokensQueue, tokenString);

} else

throw new Exception(string.Format("Identifier expected, but was: \"{0}\"", tokenString));

}

// ::= Float | Long

static Token StandartType(TokenQueue tokensQueue) {

string tokenString = GetTokenString(tokensQueue);

if (tokenString == "DOUBLE" || tokenString == "LONG") {

return NextToken(tokensQueue, tokenString);

} else

throw new Exception(string.Format("Standart type expected, but was: \"{0}\"", tokenString));

}

}

Листинг 3 – класс Statement

public abstract class Statement {

public abstract void Run(VariablesTable variablesTable, ref string runTrace);

}
Листинг 4 – класс AssumeStatement

public class AssumeStatement : Statement {

Token left;

ArithmeticStackMachine right;
public Token Left { get { return left; } }

public ArithmeticStackMachine Right { get { return right; } }
public AssumeStatement(Token left, ArithmeticStackMachine right) {

this.left = left;

this.right = right;

}

public override void Run(VariablesTable variablesTable, ref string runTrace) {

object value = Right.Calculate(variablesTable);

runTrace += string.Format("{0} <- {1}\n", left.TokenString, value);

variablesTable.SetValue(left, value);

}

}
Листинг 5 – класс CycleForStatement

public class CycleForStatement : Statement {

List innerStatements = new List();
public Token ControlVariable { get; private set; }

public ArithmeticStackMachine InitialValue { get; private set; }

public ArithmeticStackMachine LastValue { get; private set; }

public List InnerStatements { get { return innerStatements; } }
public CycleForStatement(Token controlVariable, ArithmeticStackMachine initialValue, ArithmeticStackMachine lastValue) {

this.ControlVariable = controlVariable;

this.InitialValue = initialValue;

this.LastValue = lastValue;

}
public override void Run(VariablesTable variablesTable, ref string runTrace) {

new AssumeStatement(ControlVariable, InitialValue).Run(variablesTable, ref runTrace);

double lastValue = (double)LastValue.Calculate(variablesTable);

while ((double)variablesTable.GetValue(ControlVariable) <= lastValue) {

foreach (Statement statement in InnerStatements) {

statement.Run(variablesTable, ref runTrace);

}

variablesTable.SetValue(ControlVariable, (double)variablesTable.GetValue(ControlVariable) + 1);

}

}

}
Листинг 6 – класс CycleWhileStatement

public class CycleWhileStatement : Statement {

List innerStatements = new List();
public ArithmeticStackMachine ControlExpression { get; private set; }

public List InnerStatements { get { return innerStatements; } }
public CycleWhileStatement(ArithmeticStackMachine controlExpression) {

this.ControlExpression = controlExpression;

}
public override void Run(VariablesTable variablesTable, ref string runTrace) {

while ((double)ControlExpression.Calculate(variablesTable) != 0) {

foreach (Statement statement in InnerStatements) {

statement.Run(variablesTable, ref runTrace);

}

}

}

}

Листинг 7 – класс Declaration

public class Declaration {

public Token Identifier { get; private set; }

public IdentifierType Type { get; private set; }
public Declaration(Token type, Token identifier) {

if (identifier.Type != TokenType.Identifier)

throw new ArgumentException("identifier");
this.Identifier = identifier;

this.Type = MapTokenToIdentifierType(type);

}
IdentifierType MapTokenToIdentifierType(Token type) {

if (type.Type != TokenType.Keyword)

throw new ArgumentException("type");
if (type.TokenString == "DOUBLE")

return IdentifierType.DOUBLE;

if (type.TokenString == "LONG")

return IdentifierType.LONG;
throw new ArgumentException("type");

}

}
Листинг 8 – класс VariablesTable
public class VariablesTable {

Dictionary> table = new Dictionary>();
public void RegisterVariable(Declaration declaration) {

table.Add(declaration.Identifier, new Pair(declaration.Type, null));

}
public void SetValue(Token variable, object value) {

if (!table.ContainsKey(variable))

throw new UndeclaredVariableException(variable.TokenString);
table[variable].Second = value;

}
public object GetValue(Token variable) {

if (!table.ContainsKey(variable))

throw new UndeclaredVariableException(variable.TokenString);

if (table[variable].Second == null)

throw new NotInitializedVariableException(variable.TokenString);
return table[variable].Second;

}
public override string ToString() {

string result = string.Empty;

foreach (Token key in table.Keys) {

result += string.Format("Name: {0}, Type: {1}, Value: {2}\n", key.TokenString, table[key].First, table[key].Second);

}

return result;

}

}

Листинг 9 – класс LinearAnalyzer
public static class LinearAnalyzer {

static Collection OperatorSymbols = new Collection(new char[] {

'+','-','*','/','=','!','=','<','>',':', '='

});
const char NewLineSymb = '\n';
public static TokenCollection Analize(string str, List exceptions,

bool initializeTokenTablePreviously, out TokenTable tokenTable) {

tokenTable = new TokenTable();

if (initializeTokenTablePreviously)

InitializeTokenTable(tokenTable);

TokenCollection tokens = new TokenCollection();

StringReader reader = new StringReader(str);

while (!reader.EOS) {

reader.SkipWhiteSpaces();

if (reader.EOS)

break;

Token token = FindToken(reader, exceptions);

if (!tokenTable.ContainsValue(token))

tokenTable.Add(Guid.NewGuid(), token);

tokens.Add(token);

}

return tokens;

}
static void InitializeTokenTable(TokenTable tokenTable) {

Array.ForEach(

TokenFactory.GetPredefinedTokens().ToArray(),

t => tokenTable.Add(Guid.NewGuid(), t)

);

}
static Token FindToken(StringReader reader, List exceptions) {

if (reader.EOS)

throw new ArgumentOutOfRangeException();

char firstSymb = reader.Read();
string tokenStr = string.Empty + firstSymb;
if (!reader.EOS) {

if (CanBeCommentStart(firstSymb)) {

if (reader.CheckNextSymbol('{'))

return new Token(TokenType.Comment, firstSymb + reader.ReadTo((c) => c == NewLineSymb || reader.EOS));

if (reader.CheckNextSymbol('*')) {

try {

return new Token(TokenType.Comment, firstSymb + reader.ReadTo((c) => c == '*' && reader.CheckNextSymbol('}')) + reader.Read() + reader.Read());

} catch(ArgumentOutOfRangeException) {

exceptions.Add(new EndOfCommentNotFoundException());

}

}

}
if (firstSymb == '"') {

try {

tokenStr += reader.ReadTo((c) => c == '"' || reader.EOS) + reader.Read();

return new Token(TokenType.String, tokenStr);

} catch (ArgumentOutOfRangeException) {

exceptions.Add(new EndOfStringNotFoundException());

}

}
if (char.IsLetter(firstSymb)) {

tokenStr += reader.ReadTo((c) => !char.IsLetterOrDigit(c) && !(c == '_') || reader.EOS);

}

if (char.IsDigit(firstSymb)) {

tokenStr += reader.ReadTo((c) => !(char.IsLetterOrDigit(c) || c == '.') || reader.EOS);

}

if (!(firstSymb == '!' && !reader.CheckNextSymbol('='))) {

if (IsOperatorSymbol(firstSymb)) {

tokenStr += reader.ReadTo((c) => !IsOperatorSymbol(c) || c == '(' || c == ')' || reader.EOS);

}

}

if (firstSymb == '&' && reader.CheckNextSymbol('&')) {

tokenStr += reader.Read();

}

if (firstSymb == '|' && reader.CheckNextSymbol('|')) {

tokenStr += reader.Read();

}

}
return TokenFactory.Create(tokenStr, exceptions);

}
static bool IsOperatorSymbol(char c) {

return OperatorSymbols.Contains(c);

}
static bool CanBeCommentStart(char c) {

return c == '{';

}

}

Листинг 9 – класс TokenFactory
public static class TokenFactory {

static Collection Keywords {

get {

return new Collection(new string[] {

"WHILE",

"WEND",

"FOR",

"TO",

"NEXT",

"SQRT",

"DOUBLE",

"LONG",

"BEGIN",

"END"

});

}

}
static Collection Operators {

get {

return new Collection(new string[] {

"+", "-", "*", "/", "(", ")", "=", "!=", "<", ">", ":="

});

}

}
static Collection LogicOperators {

get {

return new Collection(new string[] {

"!",

"&&",

"||"

});

}

}
public static Token Create(string tokenString, List exceptions) {

tokenString = tokenString.Trim();

if (Keywords.Contains(tokenString))

return new Token(TokenType.Keyword, tokenString);

if (Operators.Contains(tokenString))

return new Token(TokenType.Operator, tokenString);

if (LogicOperators.Contains(tokenString))

return new Token(TokenType.LogicOperator, tokenString);

if (IsIdentifier(tokenString))

return new Token(TokenType.Identifier, tokenString);

if (IsNumber(tokenString))

return new Token(TokenType.Number, tokenString);
exceptions.Add(new UnknownTokenException(tokenString));
return new Token(TokenType.Unknown, tokenString);

}
public static TokenCollection GetPredefinedTokens() {

TokenCollection predefinedTokens = new TokenCollection();

Array.ForEach(Keywords.ToArray(), e => predefinedTokens.Add(Create(e, null)));

Array.ForEach(Operators.ToArray(), e => predefinedTokens.Add(Create(e, null)));

Array.ForEach(LogicOperators.ToArray(), e => predefinedTokens.Add(Create(e, null)));

return predefinedTokens;

}
static bool IsIdentifier(string tokenString) {

if (!char.IsLetter(tokenString[0]))

return false;

for (int i = 1; i < tokenString.Length; i++)

if (!(char.IsLetterOrDigit(tokenString[i]) || tokenString[i] == '_'))

return false;

return true;

}
static bool IsNumber(string tokenString) {

if (!(char.IsDigit(tokenString[0]) || (tokenString[0] == '-' && tokenString.Length > 1)))

return false;

for (int i = 1; i < tokenString.Length; i++)

if (!(char.IsDigit(tokenString[i]) || tokenString[i] == '.'))

return false;

return true;

}

}
Листинг 10 – класс Program
public class Program {

List declarations = new List();

List statements = new List();
public List Declarations { get { return declarations; } }

public List Statements { get { return statements; } }
public VariablesTable Run(out string runTrace) {

runTrace = string.Empty;

VariablesTable variableTable = new VariablesTable();

foreach (Declaration declaration in Declarations) {

variableTable.RegisterVariable(declaration);

}

foreach (Statement statement in Statements) {

statement.Run(variableTable, ref runTrace);

}

return variableTable;

}

}

Листинг 11 – класс StringReader
public class StringReader {

const char EOSSymb = '\0';

int pos = 0;

readonly string str;

bool eos;
public bool EOS { get { return eos; } }
public StringReader(string str) {

this.str = str + EOSSymb;

}
public char Read() {

if (EOS)

throw new ArgumentOutOfRangeException();

char c = str[pos];

if(c == EOSSymb)

eos = true;

pos++;

return c;

}
public string ReadTo(Predicate predicate) {

string result = string.Empty;

char c = Read();
while (!predicate(c)) {

result += c;

c = Read();

}
pos--;
return result;

}
public void SkipWhiteSpaces() {

char c = Read();

while (char.IsWhiteSpace(c)) {

c = Read();

}

pos--;

}
public bool CheckNextSymbol(char expected) {

if (EOS)

throw new ArgumentOutOfRangeException();

return str[pos] == expected;

}

}
Листинг 12 – класс Token
public class Token {

public TokenType Type { get; private set; }
public string TokenString { get; private set; }
public Token(TokenType type, string tokenString) {

this.Type = type;

this.TokenString = tokenString;

}
public override bool Equals(object obj) {

Token other = obj as Token;

return Type == other.Type && TokenString == other.TokenString;

}
public override int GetHashCode() {

return (int)Type ^ TokenString.GetHashCode();

}
public override string ToString() {

return string.Format("{0} : {1}", Type, TokenString);

}
internal string InternalString {

get {

return Type == TokenType.Identifier ? "Identifier" : Type == TokenType.Number ? "Number" : Type == TokenType.String ? "String" : TokenString;

}

}

}
Листинг 13 – класс MainWindow
public partial class MainWindow : Window {

public MainWindow() {

InitializeComponent();

}
private void ScanButtonClick(object sender, RoutedEventArgs e) {

List exceptions = new List();

try {

tokenOutput.Inlines.Clear();

tokenTable.Inlines.Clear();

TokenTable table = null;

TokenCollection tokens = LinearAnalyzer.Analize(CodeEditor.Text, exceptions, false, out table);

if (exceptions.Count == 0) {

try {

Program program;

PostfixTokenList list = GrammarAnalyzer.Analyze(RemoveComments(tokens), out program);

if (list != null && list.Count != 0) {

tokenOutput.Inlines.Add(new Run("Grammar analyzing succeeded.\n") { Foreground = Brushes.Blue });

foreach (Token token in list) {

tokenOutput.Inlines.Add(new Run(token.Type.ToString()) { Foreground = Brushes.Red });

tokenOutput.Inlines.Add(string.Format(": {0}\n", token.TokenString));

}

string runTrace;

VariablesTable varTable = program.Run(out runTrace);

tokenTable.Inlines.Add(new Run("Table of variables: \n") { Foreground = Brushes.Red });

tokenTable.Inlines.Add(varTable.ToString());

tokenTable.Inlines.Add(new Run("Run trace: \n") { Foreground = Brushes.Red });

tokenTable.Inlines.Add(runTrace);

}

} catch (NotInitializedVariableException exception) {

MessageBox.Show(string.Format("Variable {0} has not been initialized.", exception.VariableName));

} catch(UndeclaredVariableException exception){

MessageBox.Show(string.Format("Variable {0} has not been declared.", exception.VariableName));

} catch (Exception exception) {

tokenOutput.Inlines.Add(new Run("Grammar analyzing failed.") { Foreground = Brushes.Red });

exceptions.Add(exception);

}

}

} finally {

if (exceptions.Count > 0) {

string error = CollectErrors(exceptions);

MessageBox.Show(this, error, "Error", MessageBoxButton.OK, MessageBoxImage.Error);

}

}

}
TokenCollection RemoveComments(TokenCollection tokens) {

TokenCollection result = new TokenCollection();

foreach (Token token in tokens) {

if (token.Type == TokenType.Comment)

continue;

result.Add(token);

}

return result;

}
private string CollectErrors(List exceptions) {

string result = string.Empty;

foreach (Exception exception in exceptions) {

if (exception is UnknownTokenException) {

result += string.Format("\nUnknown token: {0}", (exception as UnknownTokenException).Token);

} else if (exception is EndOfCommentNotFoundException) {

result += "\nEnd of comment not found";

} else if (exception is EndOfStringNotFoundException) {

result += "\nEnd of string not found";

} else {

result += exception.Message;

}

}

return result;

}
private void OpenButtonClick(object sender, RoutedEventArgs e) {

OpenFileDialog dialog = new OpenFileDialog();

if (dialog.ShowDialog() == true) {

using (FileStream stream = new FileStream(dialog.FileName, FileMode.Open)) {

using (StreamReader reader = new StreamReader(stream)) {

CodeEditor.Text = reader.ReadToEnd();

}

}

}

}

}

  1   2

Добавить документ в свой блог или на сайт

Похожие:

Пояснительная записка к курсовой работе по курсу «Теория языков программирования и методы трансляции» Выполнил студент гр. 230661 iconПояснительная записка к курсовой работе по курсу «Теория языков программирования...
В тоже время ни одна программа написанная на яп не может быть непосредственно выполнена машиной – перед этим необходимо выполнить...

Пояснительная записка к курсовой работе по курсу «Теория языков программирования и методы трансляции» Выполнил студент гр. 230661 iconПояснительная записка к курсовой работе по дисциплине «Теория языков...
Представление основных операторов(описанных в разделе семантики) с помощью тетрад 34

Пояснительная записка к курсовой работе по курсу «Теория языков программирования и методы трансляции» Выполнил студент гр. 230661 iconПояснительная записка к курсовой работе по дисциплине «Интеллектуальные подсистемы сапр»
Пояснительная записка к курсовой работе 10 страниц, 2 рисунка, 1 таблица, 3 источника

Пояснительная записка к курсовой работе по курсу «Теория языков программирования и методы трансляции» Выполнил студент гр. 230661 iconПояснительная записка к курсовой работе по дисциплине «Алгоритмизация...
Сеть книжных магазинов. – Челябинск: юурГУ, ЭиП-208, 2012. – 50 с., 13 ил., 1 прил

Пояснительная записка к курсовой работе по курсу «Теория языков программирования и методы трансляции» Выполнил студент гр. 230661 iconПояснительная записка к курсовой работе по дисциплине «технологии программирования»
Государственного образовательного учреждения высшего профессионального образования Российский химико-технологический университет

Пояснительная записка к курсовой работе по курсу «Теория языков программирования и методы трансляции» Выполнил студент гр. 230661 iconПояснительная записка к курсовой работе по дисциплине «Теория электрической связи»
Целью курсовой работы является получение навыков по вычислению параметров системы связи, анализу полученных результатов, а также...

Пояснительная записка к курсовой работе по курсу «Теория языков программирования и методы трансляции» Выполнил студент гр. 230661 iconОтчет по лабораторной работе №2 по курсу «Моделирование систем» студент гр. 230661
Изучение объектно-ориентированного моделирования и исследование процесса построения диаграмм использования и диаграмм взаимодействий...

Пояснительная записка к курсовой работе по курсу «Теория языков программирования и методы трансляции» Выполнил студент гр. 230661 iconПояснительная записка к контрольно-курсовой работе по курсу «Человеко-машинное взаимодействие»
...

Пояснительная записка к курсовой работе по курсу «Теория языков программирования и методы трансляции» Выполнил студент гр. 230661 iconПояснительная записка к курсовой работе по дисциплине «Теория автоматов»
Курсовая работа по теории автоматов выполняется с целью закрепления ранее полученных знаний, приобретения навыков и умений самостоятельного...

Пояснительная записка к курсовой работе по курсу «Теория языков программирования и методы трансляции» Выполнил студент гр. 230661 iconПояснительная записка к курсовой работе по дисциплине «Теория автоматов»
Ученик может исправить полученную оценку. Завуч может добавить информацию о новом учителе или ученике, а также удалить о выбывших....

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
www.vbibl.ru
Главная страница