Справочник по C# Герберт Шилдт ббк 32. 973. 26018 75 Ш57 удк 681 07 Издательский дом "Вильямс" Зав редакцией
 Скачать 5.05 Mb.
|
|
Глава 26 Синтаксический анализ методом рекурсивного спуска 708 Часть III. Применение языка C# ак бы вы написали программу, которая в качестве входных данных должна принять строку, содержащую числовое выражение, например (10 — 5) * 3, а затем вычислить правильный ответ? Как правило, когда задаешь этот вопрос, только немногие знают, как это сделать. Для подавляющего большинства программистов кажется очень трудной задачей с помощью языка высокого уровня преобразовать алгебраические выражения в инструкции, которые мог бы выполнить компьютер. Эта процедура называется анализом выражений (expression parsing), и именно она лежит в основе всех компиляторов и интерпретаторов, программ табличных вычислений и прочих программ, в которых требуется преобразование числовых выражений в форму, приемлемую для использования компьютером. Несмотря на то что поставленная выше задача для непосвященных может показаться тайной за семью печатями, анализ выражений представляет собой хорошо структурированную задачу, для которой существует элегантное решение. Решение возможно благодаря тому, что анализ выражений работает в соответствии со строгими алгебраическими правилами. В этой главе предлагается разработка того, что обычно именуется синтаксическим анализом методом рекурсивного спуска (recursive-descent parser), а также всех необходимых подпрограмм, которые позволят вычислять числовые выражения. Освоив механизм действия этого анализатора, вы сможете легко усовершенствовать его или модифицировать под свои потребности. Помимо того, что предлагаемая программа полезна сама по себе, разрабатываемый здесь анализатор также иллюстрирует мощь и диапазон применения языка C#. Наш анализатор — это приложение “чистого кода”. Оно не взаимодействует с сетью, не использует GUI-интерфейс или какие-нибудь ограниченные системные ресурсы. В прошлом код такого типа обычно писали на языке C++. Тот факт, что анализатор можно легко создать с помощью языка C#, еще раз доказывает, что C# способен справиться с любой задачей программирования. Выражения Поскольку анализатор предназначен для вычисления алгебраических выражений, важно, чтобы вы понимали составляющие их части. Хотя выражения могут состоять из данных всех типов, в этой главе используются лишь числовые. Итак, допустим, в состав числовых выражений входят следующие элементы: ■ числа; ■ операторы +, -, /, *, ^, % и =; ■ круглые скобки; ■ переменные. Здесь знак вставки ( ^ ) означает операцию возведения в степень (а не операцию “исключающее ИЛИ”, как в C#), а знак “равно” ( = ) — оператор присвоения. Эти элементы могут объединяться в выражениях в соответствии с правилами алгебры. Вот несколько примеров: 10-8 (100 - 5) * 14 / 6 a + b - c 10 ^ 5 а = 10 - b Предположим, приоритет упомянутых выше операторов можно представить следующим образом: К Глава 26. Синтаксический анализ методом рекурсивного спуска 709 наивысший + - (унарный) ^ * / % + - самый низкий = Операторы с одинаковым приоритетом выполняются слева направо. На анализатор, представленный в этой главе, налагается ряд ограничений. Во-первых, имена всех переменных должны состоять из одной буквы (другими словами, можно использовать 26 переменных, от A до Z ). При этом анализатор не должен отличать прописное написание буквы от строчного ( a и A воспринимаются как одна и та же переменная). Во-вторых, предполагается, что все числовые значения имеют тип double , хотя анализатор нетрудно модифицировать для обработки других типов значений. Наконец, чтобы программа была логически ясной и понятной, в ней предусмотрен отсев только элементарных ошибок. Анализ выражений: постановка задачи На первый взгляд может показаться, что анализ выражений — довольно простая задача, но это не совсем так. Чтобы лучше понять проблему, попробуем вычислить это простое выражение: 10 - 2 * 3 Вы знаете, что это выражение равно 4. И хотя можно легко создать программу, которая вычислит это выражение, проблемой становится создание программы, которая бы давала правильный ответ для любого выражения. Для начала представим нашу будущую программу в виде следующего эскизного варианта: а = получаем первый операнд while(операнды имеются) { ор = получаем оператор b = получаем второй операнд а = a op b } Согласно этому алгоритму, мы получаем первый операнд, оператор и второй операнд для выполнения первой операции; затем получаем следующий оператор и операнд для выполнения следующей операции и т.д. Но если использовать наш алгоритм, то вычисленное с его помощью выражение 10 — 2 * 3 даст в результате 24 (т.е. 8 * 3), а не 4, поскольку в этой процедуре не учитывается приоритет операторов. Ведь нельзя же просто выполнять операции слева направо, поскольку правила алгебры предписывают, что умножение должно быть выполнено до вычитания. Начинающим программистам может показаться, что эту проблему легко преодолеть, и действительно, в очень редких случаях это возможно. Но проблема еще усложняется, если добавить возможность использования круглых скобок, операции возведения в степень, переменных, унарных операторов и т.п. Хотя известно несколько способов написания программы вычисления выражений, мы рассмотрим здесь самый простой вариант. Этот вариант называется синтаксическим анализом методом рекурсивного спуска, и в ходе разработки вы поймете, откуда у этой программы такое название. (В других методах, используемых для написания анализаторов выражений, применяются сложные таблицы, которые должны быть сгенерированы другой программой. Такие программы получили название анализаторов с табличным управлением.) 710 Часть III. Применение языка C# Анализ выражения Анализировать и вычислять выражения можно различными способами. Что касается синтаксического анализатора, использующего метод рекурсивного спуска, то представим себе выражения в виде рекурсивных структур данных (recursive data structures), т.е. выражений, которые определяются на основе самих себя. Если предположить, что такие выражения могут использовать только операторы + , - , * , / и круглые скобки, то все выражения могут быть определены с использованием следующих правил: выражение -> член[+ член][- член] член -> множитель[* множитель][/ множитель] множитель -> переменная, число или (выражение) Квадратные скобки означают необязательный элемент, а символ -> заменяет словосочетание “представляет собой”. В действительности эти правила называются порождающими правилами выражения. Следовательно, относительно определения понятия член можно сказать: член представляет собой множитель, умноженный на множитель, или множитель, разделенный на множитель. Обратите внимание на то, что приоритет выполнения операторов неявно выражен самим способом определения выражения. Выражение 10 + 5 * В имеет два члена: 10 и 5 * B . Второй член состоит из двух множителей: 5 и B . Эти множители состоят из числа и из переменной, соответственно. А выражение 14 * (7 - С) имеет два множителя: 14 и (7 - С) . Множители состоят из одного числа и одного выражения, заключенного в круглые скобки. Выражение в круглых скобках состоит из двух членов: числа и переменной. Этот процесс составляет основу для разработки рекурсивного анализатора, который представляет собой набор взаимно рекурсивных методов, работающих в цепеобразном стиле и реализующих порождающие правила. На каждом этапе анализатор выполняет определенные операции в алгебраически корректной последовательности. Чтобы понять, как эти порождающие правила используются для анализа выражения, рассмотрим следующий пример: 9/3 - (100 + 56) Для анализа этого выражения мы должны выполнить следующие действия. 1. Получить первый член, 9/3 2. Получить каждый множитель и выполнить операцию деления целых чисел. Результат равен числу 3 3. Получить второй член, (100 + 56) . На этом этапе необходимо начать с рекурсивного анализа второго выражения. 4. Получить каждый член и сложить их. Результат равен числу 156 5. Вернуться из рекурсивного вызова и вычесть число 156 из числа 3 . Ответ равен - 153 Если вы почувствовали, что сбиты с толку, не расстраивайтесь. Это довольно сложная концепция, которая требует определенных навыков. При рассмотрении выражений с “рекурсивной” точки зрения необходимо помнить два основных принципа. Во-первых, приоритет операторов неявно выражен в самом характере определения Глава 26. Синтаксический анализ методом рекурсивного спуска 711 порождающих правил. Во-вторых, этот метод анализа и вычисления выражений очень близок тому, как математические выражения вычисляются человеком. В этой главе мы разработаем два анализатора. Первый предназначен для анализа и вычисления выражений с плавающей точкой (типа double ), которые состоят только из литеральных значений. Этот анализатор иллюстрирует основы анализа выражений методом рекурсивного спуска. Второй строится на базе первого, но позволяет также использовать переменные. Разбор выражения Чтобы вычислить выражение, необходимо предоставить анализатору отдельные компоненты этого выражения. Например, выражение А * В - (W + 10) содержит такие отдельные компоненты: А , * , B , - , ( , W , + , 10 и ). На языке грамматического разбора каждый компонент выражения называется лексемой, а лексема представляет собой неделимый элемент выражения. Поскольку разбиение выражения на лексемы имеет принципиальное значение для процесса анализа, ему следует уделить особое внимание, а затем уже заняться самим анализатором. Чтобы представить выражение в виде лексем, необходимо иметь метод, который бы последовательно возвращал каждую лексему выражения в направлении от начала к концу. Этот метод должен “уметь перескакивать” через пробелы и обнаруживать конец выражения. В нашем анализаторе метод, который выполняет эту задачу, именуется GetToken() Оба анализатора, представленные в этой главе, инкапсулированы в классе Parser Хотя этот класс подробно описан ниже, нам уже теперь необходимо познакомиться с его первой частью, чтобы понять работу метода GetToken() . Итак, класс Parser начинается с определения следующих перечислений и полей: class Parser { // Перечисляем типы лексем. enum Types { NONE, DELIMITER, VARIABLE, NUMBER }; // Перечисляем типы ошибок, enum Errors { SYNTAX, UNBALPARENS, NOEXP, DIVBYZERO }; string exp; // Ссылка на строку выражения. int expIdx; // Текущий индекс в выражении. string token; // Текущая лексема. Types tokType; // Тип лексемы. Первое перечисление названо именем Types . При анализе выражения имеет значение тип лексемы. В разработанных здесь анализаторах мы имеем дело только с тремя типами лексем: переменная, число и разделитель. Они представлены значениями variable , number и delimiter , которые определены в перечислении Types . Категория delimiter используется как для операторов, так и для круглых скобок. Тип none служит в качестве специального значения для неопределенной лексемы. Перечисление Errors представляет различные ошибки, которые могут возникнуть в процессе анализа. Ссылка на строку, которая содержит анализируемое выражение, хранится в переменной exp . Таким образом, exp будет ссылаться на такую строку, как “ 10+4 ”. Индекс следующей лексемы этой строки содержится в поле expIdx и первоначально равен нулю. Выделенная из строки лексема будет храниться в переменной token , а ее тип — в переменной tokType , 712 Часть III. Применение языка C# Ниже приведен метод GetToken() . При каждом вызове он получает следующую лексему из выражения, содержащегося в строке, адресуемой ссылкой exp , начиная с индекса expIdx , т.е. следующая лексема начинается с элемента exp[expIdx] . Эта лексема помещается в поле token , а ее тип — в поле tokType . Метод GetToken() использует метод IsDelim() , который определяет, является ли заданный символ разделителем. // Получаем следующую лексему. 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; } } // Метод возвращает значение true, если // символ с является разделителем. bool IsDelim(char с) { if((" +-/*%A=()".IndexOf(c) != -1)) return true; return false; } Рассмотрим подробно код метода GetToken() . После выполнения первых инструкций инициализации метод проверяет, не достигнут ли конец выражения, сравнивая значение переменной expIdx со значением свойства exp.Length . Поскольку Глава 26. Синтаксический анализ методом рекурсивного спуска 713 expIdx — индекс строки, содержащей анализируемое выражение, то если он равен длине строки, значит, выражение полностью проанализировано (разбито на лексемы). Если из выражения еще можно извлечь очередную лексему, метод GetToken() опускает все начальные пробелы. После этого элемент exp[expIdx] будет содержать либо цифру, либо переменную, либо оператор, либо пробел (если анализируемое выражение завершают хвостовые пробелы). Если следующим символом является оператор, то он возвращается в виде строки, сохраненной в переменной token , а в поле tokType сохраняется значение DELIMITER . Если следующим символом является буква, то предполагается, что это одна из переменных выражения. Она возвращается в виде строки, сохраненной в переменной token , а в поле tokType сохраняется значение VARIABLE Если следующим символом является цифра, то считывается число, которое возвращается в виде строки, сохраненной в переменной token , а в поле tokType сохраняется значение NUMBER . Наконец, если следующий символ не попадает ни под одну из предыдущих категорий, переменная token будет содержать нулевую строку. Чтобы не загромождать деталями код метода GetToken() , здесь упрощена проверка наличия ошибок и принят ряд допущений. Например, выражение может завершаться нераспознаваемым символом, если ему предшествует пробел. В этой версии имена переменных могут иметь любую длину, но значимой является только первая буква имени. При необходимости вы можете расширить диапазон распознаваемых ошибок самостоятельно. Чтобы лучше понять, как работает метод GetToken() , рассмотрим это выражение: А + 100 - (В * С) /2 При разбиении выражения на лексемы метод GetToken() получает следующие результаты (лексема и ее тип): Лексема Тип лексемы А VARIABLE + DELIMITER 100 NUMBER - DELIMITER ( DELIMITER в VARIABLE * DELIMITER с VARIABLE ) DELIMITER / DELIMITER 2 NUMBER Вспомните, что лексема всегда содержит строку, даже если она состоит из одного символа Простой анализатор выражений Ниже приведена первая версия анализатора. Она может вычислять выражения, которые состоят исключительно из литералов, операторов и круглых скобок. И хотя метод GetToken() может обрабатывать переменные, этот анализатор их не воспринимает. 714 Часть III. Применение языка C# Если вы поймете работу такого упрошенного анализатора, мы расширим его возможности, “научив” обрабатывать переменные. /* Этот модуль содержит рекурсивный нисходящий синтаксический анализатор, который не использует переменных. */ 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; // Текущая лексема. Types tokType; // Тип лексемы. // Входная точка анализатора. public double Evaluate(string expstr) { double result; exp = expstr; expIdx =0; try { GetToken(); if(token == "") { SyntaxErr(Errors.NOEXP); // Выражение // отсутствует. return 0.0; } EvalExp2(out result); if(token != "") // Последняя лексема должна // быть null-значением. SyntaxErr(Errors.SYNTAX); return result; } catch(ParserException exc) { // При необходимости добавьте сюда обработку // других ошибок. Console.WriteLine(exc); Глава 26. Синтаксический анализ методом рекурсивного спуска 715 return 0.0; } } // Сложение или вычитание двух членов выражения. 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); 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; |