|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Alexander Krotoff 2:5020/400 28 Jun 2001 21:21:30
To : "Andrew Ezhguroff"
Subject : Re: Синтаксический анализатор
--------------------------------------------------------------------------------
Andrew Ezhguroff <eandr@com2com.ru> wrote:
>> > Есть же банальнейший алгоритм с
>> использованием
>> > > стека (сам сейчас делаю, как доведу до ума, поделюсь)
>> > Только вот стек и рекурсия эквивалентны: "занесение в стек" ==
>> "рекурсивный
>> > вызов", "удаление из стека" == "возврат из подпрограммы". А что
>> > оптимальнее - это вопрос реализации.
>> Хм. Интересный взгляд :) Я думал, здесь используется преобразование
AE> формулы
>> в дерево (там рекурсия нужна для работы со скобками).
AE> Скорее уж преобразование в обратную польскую запись (тоже дерево, но
AE> неявное). А стек (или рекурсия) нужен не только для обработки скобок, но и
AE> для учета приоритета операций.
Учесть приоритеты можно и без рекурсии (используя стек и сравнение
приоритетов). Вообще использовать рекурсивный или какой другой
нисходящий разборщик просто для выражений (для простых выражений)
не очень хорошо. Вот примерчик (парсер + примитивная обвязка) того
как можно разбирать выражения написанный както по случаю и в эхе
уже побывавший.
В принципе можно и от рекурсии при разборе выражений
в скобках (и круглых и квадратных) избавиться тем же приемом.
-ank
----
From: krotoff@such.srcc.msu.su (Alexander Krotoff)
Subject: Парсер выражений
Newsgroups: fido7.ru.pccts
Organization: Он знал Сашу Бло.
Привет!
Hаписался недавно следующий парсер выражений.
Восходящий, произвольное число приоритетов,
приоритет префиксных и постфиксных выражений
над бинарными, произвольная ассоциативность бинарных
операторов.
Теперь терзаюсь: зачем я его написал ?
Идеи по модификации и совершенствованию
приветствуются.
--
Успехов,
Саша.
#include <algorithm>
#include <stack>
#include <memory>
#include <stdio.h>
#include <ctype.h>
struct Node {
int op;
Node *left, *right;
Node (int op, Node *left=0, Node *right=0):
op(op), left(left), right(right) {};
};
const int ID = 255;
inline int
bin_precedence (int op)
{
switch (op) {
case ',': return 0;
case '=': return 1;
case '-':
case '+': return 2;
case '*':
case '/': return 3;
default: throw "Incorrect binary operator.";
}
}
inline bool left_associative (int op) { return op!='='; }
inline bool unary_op (int op) { return op=='-' || op=='+'; }
inline bool primary (int op) { return op>ID; }
static Node *parse_expr (int term);
int lex ();
static Node *
unary_expr ()
{
int l=lex();
if (unary_op( l ))
return new Node( l, unary_expr() );
else if (l=='(')
return parse_expr( ')' );
else if (primary( l ))
return new Node( l );
else
throw "Unexpected operator";
}
typedef stack< Node* > ExprStack;
static Node *
reduce (ExprStack &expr_stack, Node *last_arg, int op)
{
int prec = op==EOF ? -1: bin_precedence( op );
while (!expr_stack.empty()) {
Node *prev = expr_stack.top();
if (prec > bin_precedence( prev->op )
|| prec == bin_precedence( prev->op )
&& !left_associative( op ))
break;
expr_stack.pop();
prev->right = last_arg;
last_arg = prev;
}
return last_arg;
}
static Node *
parse_expr (int term)
{
ExprStack expr_stack;
try {
Node *last_arg = unary_expr();
int op;
while ((op=lex())!=term) {
if (op==EOF)
throw "Unexpected end of expression.";
if (op=='[')
last_arg = new Node(
op, last_arg, parse_expr( ']' )
);
else {
last_arg = reduce( expr_stack, last_arg, op );
expr_stack.push( new Node( op, last_arg ));
last_arg = unary_expr();
}
}
return reduce( expr_stack, last_arg, EOF );
} catch (...) {
while (!expr_stack.empty()) {
delete expr_stack.top();
expr_stack.pop();
}
throw;
}
}
Node *
parse_expr()
{
try {
return parse_expr( EOF );
} catch (const char *msg) {
fprintf( stderr, "%s\n", msg );
return 0;
}
}
int
lex()
{
int c;
do { c = getchar(); } while (c != EOF && isspace( c ));
if (c==EOF)
return c;
else if (isalpha( c ))
return ID+c;
else
return c;
}
void
print_tree (Node *p, int n=0)
{
for (int i=0; i<n; i++)
putchar( '\t' );
if (p->op > ID)
putchar( p->op-ID );
else
putchar( p->op );
putchar( '\n' );
if (p->left)
print_tree( p->left, n+1 );
if (p->right)
print_tree( p->right, n+1 );
}
int
main ()
{
Node *tree = parse_expr();
if (tree)
print_tree( tree );
}
--- ifmail v.2.15dev5
* Origin: Он знал Сашу Бло. (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
