Алгоритм парсенья выражения.
Допустим есть выражение
1+(2+3+sin(9+10)+pi)*(4+5*6+(-7*8))
Задача сделать из него вычислитеьлную иерархию.
1. Разбиваем его на простейшие конструкции: число, оператор, скобки, слово. И создаём из них иерархию из одного уровня. Представление строковое. Мы не задумываемся о значении конструкций, это просто составные блоки.
1 + ( 2 + 3 + sin ( 9 + 10 ) + pi ) * ( 4 + 5 * 6 + ( - 7 * 8 ) )
2. Заменяем константы на числа.
1 + ( 2 + 3 + sin ( 9 + 10 ) + 3.14 ) * ( 4 + 5 * 6 + ( - 7 * 8 ) )
3. Рекурсивное сканирование скобок.
Мы сканируем единственный уровень на скобки и переводим в двухуровневую иерархию, перенося высшие скобки на второй уровень, который в свою очередь тоже может содержать скобки. Представление строковое. Мы ещё не знаем что * это умножение.
1 + *
2 + 3 + sin ( 9 + 10 ) + 3.14 4 + 5 * 6 + ( - 7 * 8 )После сканирования скобок уже каждой строки второго уровня иерархии будет
1 + *
2 + 3 + sin + 3.14 4 + 5 * 6 +
9 + 10 - 7 * 8Потом сканируем на скобки третий уровень, там их нет и прекращаем сканирование на скобки.
4. Рекурсивное сканирование функций. Представление функций логическое.
1 + *
2 + 3 + + 3.14 4 + 5 * 6 +
sin - 7 * 8
9 + 10 5. Рекурсивное сканирование унарных функций. Представление унарных +- логичесткое.
1 + *
2 + 3 + + 3.14 4 + 5 * 6 +
sin - * 8
9 + 10 76. Рекурсивное сканирование */. Представление */ логическое.
1 +
*
2 + 3 + + 3.14 4 + +
sin 5 * 6 - * 8
9 + 10 77. Сканирование без преобразования иерархии бинарных +- для предания им логического представления.
В итоге мы получим набор типичных конструкций, которые можно вычислить снизу.
Детали реализации.
Сложности со сканированием \* и унарных функций.
Сложность /* в том что надо захватить ещё и 2 операнда, которые могут быть числом или выражением. Что вообще-то не так уж сложно.
Сложность унарных функций в том что надо отличать их от бинарных +-. Для этого перед унарной функцией не должно быть числа или выражения.
Часть ошибок синтаксиса проверяется парсером, часть считальщиком.
Вроде чуть прояснилось, хотя похоже это не окончательный вариант. Псевдокод напишу завтра.
Омг... Что это?!
А не проще ли задать грамматику соответствующую и построить в конечном итоге дерево синтаксического разбора. Можно готовый софт взять даже, кажется yacc.
>А не проще ли задать грамматику соответствующую и построить в конечном итоге дерево синтаксического разбора.
То есть сделать синтраксис ввода другой, чтоб мне парсить легче было? Но тогда пользователям не удобно будет. Не подходит. По этой же причине не подходит обратная польская запись. Я хочу чтоб выражение было обычным. Тут был конкурс калькуляторов именно таких.
Переводить в польскую нотацию (типа как алгоритм Дейкстры) не хочу, мне нравится и иерархия.
>Можно готовый софт взять даже, кажется yacc.
Я например думал для парсенья чисел задействовать регулярки. Или даже без них обойтись. Чем yacc лучше?
Есть какие-то притензии к моему алгоритму, кроме того что он необычный или необычно описан?
Псевдокод парсера
функция парсить (строка)
иерархия указывает на
превратить строку в последовательность простых элементов (строка)
заменить константы на числа (иерархия)
сканировать скобки (иерархия)
сканировать функции (иерархия)
сканировать унарные функции (иерархия)
сканировать умножение (иерархия)
сканировать сложение (иерархия)
вернуть иерархию
конец функции
Типы простых элементов
скобка
оператор
слово
число
функция превратить строку в последовательность простых элементов (строка)
корень неоределён
последний элемент неопределён
элемент неопределён
длинна строки равна узнать длинну строки
позиция равна 0
пока позиция меньше длинны
символ равен символу из строки в позиции
если символ проблел то
перейти к продолжение
конец если
элемент равен попытаться создать скобу (строка, позиция, длинна)
если элемент определён то
перейти к элемент определён
конец если
элемент равен попытаться создать оператор (строка, позиция, длинна)
если элемент определён то
перейти к элемент определён
конец если
элемент равен попытаться создать слово (строка, позиция, длинна)
если элемент определён то
перейти к элемент определён
конец если
элемент равен попытаться создать число (строка, позиция, длинна)
если элемент определён то
перейти к элемент определён
конец если
перейти к продолжение
элемент определён
добавить элемент (корень, последний элемент, элемент)
продолжение
увеличить позицию
продолжить
конец пока
вернуть корень
конец функции
функция добавить элемент (корень, последний элемент, элемент)
если элемент не определён то
вернуть провал
конец если
если корень не определён то
корень указывает на элемент
последний элемент указывает на корень
вернуть успех
конец если
добавить элемент к последнему элементу
последний элемент указывает на элемент
вернуть успех
конец функции
функция попытаться создать символьный элемент (строка, позиция, символы, тип)
символ равен символ из строки в позиции
если символ не равен одному из набора символов то
вернуть неудачу
конец если
создать элемент
присвоить элемену тип тип
присвоить элементу строчку символ
увеличить позицию
вернуть элемент
конец функции
функция попытаться создать скобу (строка, позиция, длинна)
вернуть попытаться создать символьный элемент(строка, позиция,
символы скобок, тип скобка)
конец функции
функция попытаться создать оператор (строка, позиция, длинна)
вернуть попытаться создать символьный элемент(строка, позиция,
символы операторов, тип оператор)
конец функции
функция попытаться создать слово (строка, позиция, длинна)
символ равен символу из строки в позиции
если символ не буква то
вернуть провал
конец если
слово равно пустая строка
пока символ буква
добавить к слову символ
увеличить позицию
если позиция больше или равна длине то
выйти из цикла
конец цикла
символ равен символу из строки в позиции
конец пока
создать элемент
присвоить элементу тип слово
присвоить элементу строчку слово
вернуть элемент
конец функции
функция попытаться создать число (строка, позиция, длинна)
символ равен символу из строки в позиции
если символ не цифра то
вернуть провал
конец если
число равно пустая строка
уже есть точка равно нет
пока правда
добавить символ к числу
увеличить позицию
если позиция больше длинны то
выйти из цикла
конец если
символ равен символу из строки в позиции
если символ не цифра
если не проверка единственной точки (символ, уже есть точка) то
выйти из цикла
конец если
конец если
конец пока
создать элемент
присвоить элементу тип число
присвоить элементу строчку число
вернцть элемент
конец функции
функция проверка единственоной точки(символ, уже есть точка)
если символ не точка то
вернуть провал
конец если
если уже есть точка то
вернуть провал
конец если
уже есть точка равно да
вернуть успех
конец функции
функция заменить константы на числа (корень)
элемент равен корню
число
пока элемент определён
если тип элемента не слово то
перейти к продолжение
конец если
если не поиск константы (число, строчка элемента) то
перейти к продолжение
конец если
число элемента равно число
тип элемента равно число
продолжение
элемент равен следующему
конец пока
конец функции
функция сканировать скобки (корень)
открытые скобки равно получить открытые скобки
закрытые скобки равно получить закрытые скобки
элемент равно корень
открытых скобок равно ноль
тип скобки
первый элемент неопределено
последний элемент неопределено
пока элемент определён
если тип элемент не скобка то
перейти к продолжение
конец если
тип скобки равно получить тип скобки (строчка элемента,
открытые скобки, закрытые скобки)
если тип скобки равно открытые скобки то
открытых скобок увеличить
если открытых скобок равно один то
первый элемент равно элемент
конец если
иначе // закрытые скобки
открытых скобок уменьшить
если открытых скобок равно ноль то
последний элемент равно элемент
выделить скобки на подуровень(первый элемент, последний элемент)
открытых скобок равно ноль
первый элемент не определён
последний элемент не определён
конец если
конец если
продолжение
элемент равен следущюему
конец пока
конец функции
/*
Получаем
4+ пустышка - +3
|
1+2 пустышка
*/
функция выделить скобки на подуровень(первый элемент, последний элемент)
первый элемент тип равно пустышка
последний элемент тип равно пустышка
// опускаем нижнюю цепочку
первый элемент нижний равно первый элемент следующий
// связывам следующую высшую цепочку
первый элемент следующий равно последний элемент следующий
// замыкаем нижнюю цепочку
последний элемент следующий не определён
конец функции
остальное допишу завтра
C2Architector
Как ты сделаешь ассоциативность и приоритет операций?
Вот, для общего развития
http://dinosaur.compilertools.net/bison/bison_5.html#SEC15
(Там сначала описывается как построить калькулятор для обратной польской нотации, а затем рассказано как его модифицировать, чтобы работать с "нормальной" /инфиксной/ нотацией. Если нет опыта работы с flex/bison, лучше читать подряд, понятнее будет. Да, наверно надо пояснить - bison генерирует код парсера по спецификации в виде грамматики. Грамматика - это формальное определение того, какая последовательность лексем является валидным выражением языка. Например BNF - это тоже своего рода грамматика. Сейчас парсеры вручную обычно не пишут, а пользуются либо bison-ом либо другими подобными тулзами.)
Посмотрите Страуструпа, там очень хороший пример создания калькулятора. Очень простой код на 200 строчек, операции +, -, /, *, (), а син-кос добавить туда легко. Кста, тот калькулятор поддерживает переменные. Как я понял, он разбирает строчку на лексемы в рекурсивной функции.
Красный дракон!
Не стоит изобретать велосипед!
Тема в архиве.