CodeNet / Языки программирования / C / C++ / Borland C++ Builder / Работа с текстом и строками
Разрабатываем парсер математических выражений
Автор: Meander
Дата: 5 апреля 2012 года
Как-то меня заинтересовала тема интерпретации строки символов, вводимой пользователем во время выполнения программы, как математического выражения. Порывшись в сети, нашел несколько книг по теории, несколько примеров исходников калькуляторов и т.д. Было обнаружено несколько фактов. Во-первых, все парсеры были рекурсивны, во-вторых, большинство реализовано на плохо знакомом мне Паскале и, наконец, представляли собой весьма необозримый код.
Тогда мной небыли обнаружены примеры простых парсеров Страуструпа и Шилдта, хотя и они достаточно громоздки. Однако, на сайте emaxx я наткнулся на простой и компактный парсер строки. Этот парсер работал с двумя стеками, осуществлял преобразование в обратную польскую нотацию и одновременно вычислял значение за время пропорциональное длине строки.
Мы будем искать в строке зарегистрированные последовательности символов. Зарегистрированные последовательности это, вообще говоря, единственно возможные под последовательности, которые априори можно встретить в строке. Числовые константы, ввиду их огромного разнообразия, нет смысла предопределять. Их достаточно просто обнаружить и определить, так как они состоят из цифр и символа разделителя целой и дробной частей. Поэтому, если мы не обнаружили вначале строки зарегистрированную лексему, возможно здесь число. Ну, а если и не число, значит в этом месте неизвестный символ.
Та строка, которую мы написали в окне редактирования, осмыслена с точки зрения синтаксиса, т.е. с нашей точки зрения. С точки зрения компьютера это случайный набор символов. С нашей точки зрения строка осмыслена, т.к. содержит последовательность лексем, а не символов. Поэтому и компьютер должен искать не символы, а лексемы.
Поиск лексем следует начинать с самых длинных в порядке уменьшения длины. Сначала ищем самую длинную, потом – на один символ короче и т.д. Это необходимо, чтобы избежать двусмысленной ситуации, когда некоторая последовательность символов, соответствующая короткой лексеме, входит целиком в начальный фрагмент длинной лексемы. Например, мы можем ввести символьную константу или переменную с именемsinus, но если вести поиск произвольно, или, начиная с коротких последовательностей, то возникнет ошибка: неизвестный аргументusфункцииsin.
Теперь следует определиться со способом поиска лексем входящих в состав строки. Если упорядочить набор библиотечных лексем в порядке уменьшения длины последовательности символов. Затем сравнивать последовательно наборы символов библиотечных лексем с начальным фрагментом строки той же длины. Но можно не упорядочивать совокупность библиотечных лексем по длине. Достаточно знать число символов в самой длинной лексеме, брать фрагмент строки соответствующей длины и сравнивать с последовательностями, имеющимися в библиотеке. В этом случае, если фрагмент не найден, берем последовательность на один символ короче (или убираем последний символ из, уже, набранной на предыдущем этапе) и повторяем поиск. Так дойдя до одного символа, и не найдя его, предполагаем, что вначале находится число. Если фрагмент обнаружен, то добавляем соответствующий элемент в виртуальную строку, а реальную строку укорачиваем на n первых символов (где n – это длина обнаруженного фрагмента). Затем повторяем все рекурсивно, пока не исчерпаем строку, либо не встретим ошибку.
Мы завершили рассмотрение вопроса о разборе строки на лексемы и формировании некоторого вектора (виртуальной строки) заполненного структурами, содержащими необходимые в дальнейшем атрибуты лексем.
Широкую группу синтаксических ошибок можно предупредить, рассмотрев случаи возможного и не возможного положения лексем в выражении.
Введем обозначения:
- “NVC” – числа, переменные, константы;
- “)” – закрывающие скобки;
- “(” – открывающие скобки;
- “BU” – операции бывающие либо унарными, либо бинарными;
- “B” – всегда бинарные операции;
- “U” – всегда унарные операции.
| Начало строки | Конец строки | ||
|---|---|---|---|
| Могут быть | Не могут быть | Могут быть | Не могут быть |
| “NVC” | “)” | “NVC” | “(” |
| “(” | “B” | “)” | “B” |
| “BU” | “U” | ||
| “U” | “BU” | ||
Теперь случаи промежуточного положения элементов перед текущей лексемой.
| Текущая лексема | “…” - может быть | “…” – не может быть |
|---|---|---|
| “…”“(” | “(”,“BU”,“U”,“B” | “NVC”,“)” |
| “…”“NVC” | “(”,“BU”,“U”,“B” | “NVC”,“)” |
| “…”“BU” | “(”,“BU”,“U”,“B”,“NVC” | любая допустима |
| “…”“B” | “NVC”,“)” | “(”,“BU”,“U”,“B” |
| “…”“U” | “(”,“BU”,“U”,“B” | “NVC”,“)” |
| “…”“)” | “NVC”,“)” | “(”,“BU”,“U”,“B” |
Оставить комментарий
Комментарии
