Справочник по C# Герберт Шилдт ббк 32. 973. 26018 75 Ш57 удк 681 07 Издательский дом "Вильямс" Зав редакцией
 Скачать 5.05 Mb.
|
|
716 Часть III. Применение языка C# int t; EvalExp5(out result); if(token == "^") { GetToken(); EvalExp4(out partialResult); ex = result; if(partialResult == 0.0) { result = 1.0; return; } for(t=(int)partialResult-1; t > 0; t--) result = result * (double)ex; } } // Выполнение операции унарного + или -. void EvalExp5(out double result) { string op; op = ""; if((tokType == Types.DELIMITER) && token == "+" || token == "-") { op = token; GetToken(); } EvalExp6(out result); if(op == "-") result = -result; } // Обработка выражения в круглых скобках. void EvalExp6(out double result) { if((token == "(")) { GetToken(); EvalExp2(out result); if(token != ")") SyntaxErr(Errors.UNBALPARENS); GetToken(); } else Atom(out result); } // Получаем значение числа. void Atom(out double result) { switch(tokType) { case Types.NUMBER: try { result = Double.Parse(token); } catch(FormatException) { result = 0.0; SyntaxErr(Errors.SYNTAX); } GetToken(); return; default: Глава 26. Синтаксический анализ методом рекурсивного спуска 717 result = 0.0; SyntaxErr(Errors.SYNTAX); break; } } // обрабатываем синтаксическую ошибку. void SyntaxErr(Errors error) { string[] err = { "Синтаксическая ошибка", "Дисбаланс скобок", "Выражение отсутствует", "Деление на нуль" }; throw new ParserException(err[(int)error]); } // Получаем следующую лексему. void GetToken() { tokType = Types.NONE; token = ""; if(expIdx == exp.Length) return; // конец выражения // Пропускаем пробелы. while(expIdx < exp.Length && Char.IsWhiteSpace(exp[expIdx])) ++expIdx; // Хвостовой пробел завершает выражение. if(expIdx == exp.Length) return; if(IsDelim(exp[expIdx])) { // Это оператор? token += exp[expIdx]; expIdx++; tokType = Types.DELIMITER; } else if(Char.IsLetter(exp[expIdx])) { // Это // переменная? while(!IsDelim(exp[expIdx])) { token += exp[expIdx]; expIdx++; if(expIdx >= exp.Length) break; } tokType = Types.VARIABLE; } else if(Char.IsDigit(exp[expIdx])) { // Это число? while(!IsDelim(exp[expIdx])) { token += exp[expIdx]; expIdx++; if(expIdx >= exp.Length) break; } tokType = Types.NUMBER; } } 718 Часть III. Применение языка C# // Метод возвращает значение true, если // символ с является разделителем. bool IsDelim(char c) { if((" +-/*%^=()".IndexOf(c) != -1)) return true; return false; } } Приведенный здесь анализатор может обрабатывать следующие операторы: + , - , * , / и % . Кроме того, он может выполнить операцию возведения в степень ( ^ ) при использовании целочисленного показателя степени, а также корректно обработать оператор “унарный минус” и выражение в круглых скобках. Чтобы использовать анализатор, сначала создайте объект типа Parser. Затем вызовите метод Evaluate() , передав ему в качестве аргумента подлежащее вычислению выражение, представленное в строковом виде. Вам останется лишь получить результат, возвращаемый методом Evaluate() . Использование анализатора демонстрируется в следующей программе: // Демонстрация использования анализатора выражений. using System; class ParserDemo { public static void Main() { string expr; Parser p = new Parser(); Console.WriteLine( "Для выхода из программы введите пустое выражение."); for(;;) { Console.Write("Введите выражение: "); expr = Console.ReadLine(); if(expr == "") break; Console.WriteLine("Результат: " + p.Evaluate(expr)); } } } Вот пример использования анализатора: Для выхода из программы введите пустое выражение. Введите выражение: 10-2*3 Результат: 4 Введите выражение: (10-2)*3 Результат: 24 Введите выражение: 10/3 Результат: 3.33333333333333 Введите выражение: 10/3.5 Результат: 2.85714285714286 Введите выражение: Глава 26. Синтаксический анализ методом рекурсивного спуска 719 Осмысление механизма анализа Рассмотрим детально класс Parser . Как упоминалось при рассмотрении метода GetToken() , класс Parser содержит четыре закрытых поля. Вычисляемое выражение хранится в строке exp . Это поле устанавливается при каждом вызове метода Evaluate() Важно помнить, что анализатор вычисляет выражения, которые запоминаются в стандартной C#-строке. Например, следующие строки содержат выражения, которые способен вычислить наш анализатор: "10 - 5" "2 * 3.3 / (3.1416 * 3.3)" Текущий индекс символа в строке exp хранится в поле expIdx . В начале анализа переменная expIdx устанавливается равной нулю. Значение expIdx инкрементируется по мере “перемещения” по анализируемому выражению. Поле token содержит текущую лексему, а поле tokType — ее тип. Входной точкой анализатора является метод Evaluate() , которому при вызове необходимо передать строку, содержащую выражение, предназначенное для анализа. Методы EvalExp2() — EvalExp6() вместе с методом Atom() и составляют рекурсивный нисходящий синтаксический анализатор. Они реализуют расширенный набор описанных выше порождающих правил. Комментарии, приведенные в начале каждого метода, описывают выполняемые ими функции. В следующую версию анализатора будет добавлен метод EvalExpl() Метод SyntaxErr() обрабатывает синтаксические ошибки в задаваемых пользователем выражениях. Методы GetToken() и IsDelim() , как описано выше, разбивают выражение на составные части. В нашем анализаторе метод GetToken() используется для выделения из выражения лексем. На основе типа лексемы принимается решение о том, какие действия предпримет анализатор. Чтобы понять, как анализатор вычисляет выражение, возьмем для примера следующее выражение: 10 - 3 * 2 При первом вызове метод Evaluate() возвращает первую лексему. Если она представляет собой пустую строку ( "" ), на экране отобразится сообщение “Выражение отсутствует”, и метод Evaluate() возвратит значение 0.0 . Но в данном случае лексема содержит число 10. Затем вызывается метод EvalExp2() . Метод EvalExp2() вызывает метод EvalExp3() , который вызывает метод EvalExp4(), а он — метод EvalExp5() После этого метод EvalExp5() определяет, является ли лексема унарным плюсом или унарным минусом. В нашем случае это не так, поэтому вызывается метод EvalExp6() . В этой точке программы метод EvalExp6() либо рекурсивно вызывает метод EvalExp2() (в том случае, если выражение заключено в круглые скобки), либо метод Atom() для получения значения числа. Поскольку лексема не является левой скобкой, выполняется метод Atom() и переменной result присваивается значение 10. Затем считывается следующая лексема, и выполнение этого метода завершается. Управление передается вызвавшему методу, который, завершаясь (в свою очередь), передает управление “вверх” по цепочке вызовов, т.е. происходит последовательный возврат из методов, входящих в состав цепочки. Так как новая лексема представляет собой оператор “ - “, цепочка возвращает нас к методу EvalЕхр2() Следующий шаг очень важен. Поскольку текущая лексема оказалась оператором “ - “, она сохраняется в переменной ор. Затем анализатор получает очередную лексему, которая является числом 3, и снова начинает “спуск” по цепочке методов. После вызова метода Atom() возвращаемое им число 3 записывается в поле result и считывается лексема “ * ”. Тип лексемы заставляет вернуться по цепочке к методу 720 Часть III. Применение языка C# EvalExp3() , в котором считывается последняя лексема, 2. Здесь выполняется первая арифметическая операция, а именно умножение 2 на 3. Результат возвращается методу EvalExp2() , который выполняет операцию вычитания. В результате вычитания получаем 4. Хотя описанный процесс на первый взгляд может показаться сложным, “пройдите” его вручную на различных примерах; это поможет понять его работу, а главное, вы убедитесь в том, что он функционирует корректно для разных исходных выражений. При обнаружении ошибки в процессе анализа вызывается метод SyntaxErr() , который генерирует исключение типа ParserException , позволяющее установить причину ошибки. Исключение ParserException — не встроенное; оно определено в начале файла, содержащего определение класса Parser . Этот анализатор выражений, как проиллюстрировано предыдущей программой, можно использовать для простого настольного калькулятора. Но прежде чем пытаться встроить его в базу данных или в более усовершенствованный калькулятор, необходимо наделить его способностью обрабатывать переменные. Это и является предметом обсуждения следующего раздела. Добавление в анализатор переменных Во всех языках программирования, многих калькуляторах и программах табличных вычислений переменные служат для хранения значений, которые будут задействованы позже. Чтобы наш анализатор можно было использовать для таких приложений, необходимо расширить его возможности в направлении обработки переменных. Для этого прежде всего нужно добавить сами переменные. Как упоминалось выше, в качестве имен переменных мы будем использовать буквы от А до Z . Выделим для хранения переменных массив в классе Parser . Каждая переменная может претендовать только на одну позицию в 26-элементном массиве типа double . Итак, добавим в класс Parser следующее поле: double[] vars = new double[26]; В класс Parser необходимо также добавить следующий конструктор, который инициализирует переменные: public Parser() { // Инициализируем переменные нулевыми значениями. for(int i=0; i < vars.Length; i++) vars[i] = 0.0; } “Из любезности” к пользователю переменные теперь инициализированы значениями 0.0 Нам также потребуется метод поиска значения заданной переменной. Поскольку переменные носят имена от А до Z , их легко использовать для индексации массива vars путем вычитания ASCII-значения буквы А из имени переменной. Этим занимается метод FindVar() . Вот его код: // Метод возвращает значение переменной. double FindVar(string vname) { if(IChar.IsLetter(vname[0])){ SyntaxErr(Errors.SYNTAX); return 0.0; } return vars[Char.ToUpper(vname[0])-'A']; } Глава 26. Синтаксический анализ методом рекурсивного спуска 721 Как видно из кода, метод действительно принимает длинные (т.е. не однобуквенные) имена переменных, например А12 или test , но значимой является только первая буква имени. При необходимости эту ситуацию можно изменить в соответствии с конкретными требованиями. Мы должны также модифицировать метод Atom() , чтобы он мог обрабатывать как числа, так и переменные. Вот как выглядит его новая версия: // Получаем значение числа или переменной. void Atom(out double result) { switch(tokType) { case Types.NUMBER: try { result = Double.Parse(token); } catch(FormatException) { result = 0.0; SyntaxErr(Errors.SYNTAX); } GetToken(); return; case Types.VARIABLE: result = FindVar(token); GetToken(); return; default: result = 0.0; SyntaxErr(Errors.SYNTAX); break; } } По сути, этих дополнений вполне достаточно для того, чтобы анализатор корректно использовал переменные, но пока не реализован способ присвоения этим переменным значений. Чтобы переменной можно было придать некоторое значение, анализатор должен “уметь” обрабатывать оператор присвоения ( = ). Для реализации присвоения добавим в класс Parser еще один метод — EvalExp1() . Теперь именно этот метод будет начинать рекурсивную нисходящую цепочку. Это означает, что для того, чтобы начать анализ выражения, из метода Evaluate() теперь должен вызываться метод EvalExp1() , а не метод EvalExp2() . Вот как выглядит код метода EvalExp1() : // Обработка операции присвоения. void EvalExp1(out double result) { int varIdx; Types ttokType; string temptoken; if(tokType == Types.VARIABLE) { // Сохраняем старую лексему. temptoken = String.Copy(token); ttokType = tokType; // Вычисляем индекс переменной. varIdx = Char.ToUpper(token[0]) - 'A'; GetToken(); if(token != "=") { 722 Часть III. Применение языка C# PutBack(); // Возвращаем текущую лексему в поток // и восстанавливаем старую, // поскольку у нас не присвоение. token = String.Copy(temptoken); tokType = ttokType; } else { GetToken(); // Получаем следующую часть exp.EvalExp2(out result); vars[varIdx] = result; return; } } EvalExp2(out result); } В методе EvalExp1() необходимо узнать, имеет ли место присвоение. Дело в том, что оператору присвоения всегда предшествует имя переменной, но наличие “одинокого” имени переменной еще не гарантирует, что за ним обязательно следует выражение присвоения. Другими словами, анализатор воспримет выражение А = 100 как присвоение, но он достаточно интеллектуален, чтобы “сообразить”, что выражение А/10 не является присвоением. Для этого метод EvalExp1() считывает следующую лексему из входного потока. Если она не содержит знак равенства, эта лексема возвращается во входной поток для последующего вызова метода PutBack() , код которого приводится ниже: // Возвращаем лексему во входной поток. void PutBack() { for(int i=0; i < token.Length; i++) expIdx—; } После внесения необходимых изменений анализатор примет следующий вид: /* Этот модуль содержит рекурсивный нисходящий анализатор, который распознает переменные. */ using System; // Класс исключений для ошибок анализатора. class ParserException : ApplicationException { public ParserException(string str) : base(str) { } public override string ToString() { return Message; } } class Parser { // Перечисляем типы лексем. enum Types { NONE, DELIMITER, VARIABLE, NUMBER }; // Перечисляем типы ошибок. enum Errors { SYNTAX, UNBALPARENS, NOEXP, DIVBYZERO }; string exp; // Ссылка на строку выражения. int expIdx; // Текущий индекс в выражении. string token; // Текущая лексема. Глава 26. Синтаксический анализ методом рекурсивного спуска 723 Types tokType; // Тип лексемы. // Массив для переменных. Double[] vars = new double[26]; public Parser() { // Инициализируем переменные нулевыми значениями. for(int i=0; i < vars.Length; i++) vars[i] = 0.0; } // Входная точка анализатора. public double Evaluate(string expstr) { double result; exp = expstr; expIdx = 0; try { GetToken(); if(token == "") { SyntaxErr(Errors.NOEXP); // Выражение отсутствует. return 0.0; } EvalExp1(out result); // В этом варианте анализатора // сначала вызывается // метод EvalExp1(). if(token != "") // Последняя лексема должна // быть нулевой. SyntaxErr(Errors.SYNTAX); return result; } catch(ParserException exc) { // При желании добавляем здесь обработку ошибок. Console.WriteLine(exc); return 0.0; } } // Обрабатываем присвоение. void EvalExp1(out double result) { int varIdx; Types ttokType; string temptoken; if(tokType == Types.VARIABLE) { // Сохраняем старую лексему. temptoken = String.Copy(token); ttokType = tokType; // Вычисляем индекс переменной. varIdx = Char.ToUpper(token[0]) - 'A'; GetToken(); 724 Часть III. Применение языка C# if(token != "-") { PutBack(); // Возвращаем текущую лексему в поток //и восстанавливаем старую, // поскольку отсутствует присвоение. token = String.Copy(temptoken); tokType = ttokType; } else { GetToken(); // Получаем следующую часть // выражения exp. EvalExp2(out result); vars[varIdx] = result; return; } } EvalExp2(out result); } // Складываем или вычитаем два члена выражения. void EvalExp2(out double result) { string op; double partialResult; EvalExp3(out result); while((op = token) == "+" || op == "-") { GetToken(); EvalExp3(out partialResult); switch(op) { case "-": result = result - partialResult; break; case "+": result = result + partialResult; break; } } } // Выполняем умножение или деление двух множителей. void EvalExp3(out double result) { string op; double partialResult = 0.0; EvalExp4(out result); while((op = token) == "*" || op == "/" || op == "%") { GetToken(); EvalExp4(out partialResult); switch(op) { case "*": result = result * partialResult; break; case "/": if(partialResult == 0.0) SyntaxErr(Errors.DIVBYZERO); Глава 26. Синтаксический анализ методом рекурсивного спуска 725 result = result / partialResult; break; case "%": if(partialResult ==0.0) SyntaxErr(Errors.DIVBYZERO); result = (int) result % (int) partialResult; break; } } } // Выполняем возведение в степень. void EvalExp4(out double result) { double partialResult, ex; int t; EvalExp5(out result); if(token == "^") { GetToken(); EvalExp4(out partialResult); ex = result; if(partialResult ==0.0) { result =1.0; return; } for(t=(int)partialResult-1; t > 0; t--) result = result * (double)ex; } } // Выполняем операцию унарного + или -. void EvalExp5(out double result) { string op; op = ""; if((tokType == Types.DELIMITER) && token == "+" || token == "-") { op = token; GetToken(); } EvalExp6(out result); if(op == "-") result = -result; } // Обрабатываем выражение в круглых скобках. void EvalExp6(out double result) { if((token =="(")) { GetToken(); EvalExp2(out result); if(token != ")") SyntaxErr(Errors.UNBALPARENS); GetToken(); } else Atom(out result); } |