LINUX.ORG.RU

GNU Bison - преобразование в обратную польскую запись.

 , ,


0

1

Ранее я уже просил помощи по Bison, и мне таки здорово помогли, за что большое спасибо всем, кто написал в тот тред. Теперь возникла новая проблема - мне надо сделать преобразование грамматики из прошлого примера в обратную польскую запись. Я нашёл пример RPN Calc на gnu.org, но от него пользы мало. Так и не понял, как же работать со строками в бизоне. Вот код:

%{
	#define YYSTYPE char *
	#include <stdio.h>
	#include <ctype.h>
	#include <cstring>
	#include «bison.tab.hh»

	int yyparse(void); 

	int yyerror (const char *s){}

	void yylex_reinitialize(void) {
		int c;
		while ( c != EOF && c != '\n' )
			c = getchar();
	}

	int yylex(void) {
		int c;
		while ( (c = getchar()) == ' ' || c == '\t' );
		if (c == EOF || c == '\n')
			return 0;
		return c; 
	}

	int main (void) {
		while (1) {
			if (!yyparse()) {
				printf(«Правильная строка\n»);
			}
			else {
				printf(«Ошибка: неправильная строка\n»);
				yylex_reinitialize();
			}
		}
	}
%}

%token 'c' 'e' 'd'

%%
S: E { printf(«%s», $$); };
E: E'+'T { $$ = strcat($1, $3); $$ = strcat($$, $2); };
E: T;
T: T'*'F { $$ = strcat($1, $3); $$ = strcat($$, $2); };
T: F;
F: 'c'|'e'|'d'|'('E')';
%%
Собственно, он компилируется, но выдаёт Segmentation fault. Подозреваю, что я где-то должен выделить память для $$ сначала.


Ответ на: комментарий от olibjerd

Ну там про то, как будет работать парсер, сгенерированый бизоном, как я понял. Скорректировать Bison-код это никак не помогает.
Sorcerer, бро, ты в прошлый раз больше всех помог, может, и сейчас поможешь?

kosc ()
Ответ на: комментарий от kosc

У вас тут много ошибок.

Главная ошибка в том, что вы задали тип для всех объектов (char *), но нигде не создаёте объекты указанного типа. В вашем случае yylex() должен заполнять значение в глобальной переменной yylval. При этом нужно не забыть освобождать память от ненужных объектов (см. %destructor).

Лучше вводить тип данных при помощи %union (а не #define YYSTYPE), потом задать тип для требуемых нетерминальных символов, используя %type. Так вы отловите ошибки с несовпадением типов. Токены-переменные 'c', 'e' и 'd' теперь потребуется заменить на символьный токен, в yylex() возвращать для них этот токен с заполнением в yylval значения (для токена-переменной пока достаточно типа данных char, без звездочки, этот тип данных нужно указать и в %union, и в %token).

Приоритет операций вы не задали (см. %left).

Операции типа $$ = strcat($1, $3) можно использовать только тогда, когда вы точно понимаете, что делаете. Вот вы тут изменили объект $1 (про выход за границы выделенной памяти я даже не говорю), а этот объект может быть использован бизоном, если он начнёт пробовать альтернативное правило.

Sorcerer ★★★★★ ()
Ответ на: комментарий от Sorcerer

Я слегка погорячился насчет переиспользования объекта бизоном: этого не будет происходить. Но всё равно надо знать, что за объекты у вас. Простой вариант, с перевыделением памяти:

E: E'+'T
    {
        $$ = malloc(strlen($1) + strlen($3) + 2);
        sprintf($$, "%s%s+", $1, $3);
        free($1);
        free($3);
    };

Sorcerer ★★★★★ ()
Ответ на: комментарий от Sorcerer

$$ = malloc(strlen($1) + strlen($3) + 2);

Но что тогда будет со строкой, которая уже есть в $$?

не задали приоритет операторов

Это да, потому что, как выяснилось, считать результат всё равно не надо, буквы останутся буквами.

А вообще, большое спасибо, хоть немного продвинулся вперёд.

kosc ()
Ответ на: комментарий от kosc

Но что тогда будет со строкой, которая уже есть в $$?

Её там нет. Вы должны её задать.

Это да, потому что, как выяснилось, считать результат всё равно не надо, буквы останутся буквами.

Это в предыдущей теме было не важно, а здесь результат - обратная польская запись - зависит от приоритета операций.

Sorcerer ★★★★★ ()
Ответ на: комментарий от Sorcerer

Прошу прощения, что снова беспокою, но у меня тупняк и отчаяние :(
Нынешний код выглядит примерно так: http://paste.pztrn.name/1299/
Ругается на создание массива char в yylval (строка 18). В принципе, много ещё на что ругается, но вот именно работа с динамической памятью меня беспокоит сейчас больше всего. В обычном C, и, тем более, в C++, у меня с этим особых проблем нет, а вот в бизоне...
Ах да, весь код из {} я убрал до тех пор, пока не научусь нормально работать со всем остальным. Ещё, почему-то нигде не удалось в интернете найти примеров того, как из одной грамматики перевести выражение (бизоном) в другую. Наш преподаватель называет это «синтаксически управляемая трансляция», если я правильно понял.

kosc ()
Ответ на: комментарий от kosc

Для начала вам лучше преобразовать код к такому виду, чтобы компилятор хоть что-то начал понимать из того, что вы сделали: http://paste.pztrn.name/1300/

Sorcerer ★★★★★ ()
Ответ на: комментарий от kosc

Ругается на создание массива char в yylval (строка 18).

Логично. yylval - это же юнион. А вы зачем-то присваиваете к нему строку.

Тип в %type - это имя поля из юниона выше. Но %type - это для нетерминальных символов, а вам надо %token. Т.е. надо так:

%token <variable> 'c' 'e' 'd'

Но при этом вы решили в yylex() возвращать VAR. Это правильней, но раз так так, тогда и в %token вместо 'c' 'e' 'd' нужно задавать VAR:

%token <variable> VAR

и без всяких маллоков в yylex(), но перед возвратом VAR нужно задать yylval:

yylval.variable = c;

А память для строк надо выделять уже в обработчиках нетерминальных символов (F, E и т.д.). Для всех этих символов нужно также задать типы, как и для терминальных.

С деструктором, выполняющим free() для всего вы явно погорячились. Вообще попробуйте сначала без деструктора, а когда всё заработает более-менее, то начните устранять утечки valgrind'ом, тогда и поймёте на практике, когда нужен деструктор.

И с грамматикой у вас как-то всё сложно. Операции '+' и '*' должны же быть на одном уровне. А приоритет для скобки указывать нет смысла.

Sorcerer ★★★★★ ()
Ответ на: комментарий от Sorcerer

Спасибо большущее, хоть как-то с мёртвой точки сдвинулся.
Ругался на деструктор, решил на время его убрать.
Теперь ругается на то, что у $1, $2 и $3 у S, E, и T не объявлен тип. Я догадываюсь, что надо там как-то обозначить %type для них, но не знаю, как я буду обозначать тип для нетерминалов (тем более, что там допустима рекурсия).
Вот текущая версия кода: http://paste.pztrn.name/1303/
А ошибки при сборке такие: http://paste.pztrn.name/1304/

kosc ()
Ответ на: комментарий от kosc

Предлагаю таки прочитать документацию по bison, она очень хорошая. В ней написано, что тип для нетерминалов обозначается при помощи %type, а для терминалов - при помощи %token. И, кстати, объявлять тип для 'c', 'e', 'd' вам не нужно ни через %type, ни через %token, и вообще их теперь в парсере использовать не надо, а надо использовать введенный вами VAR.

Sorcerer ★★★★★ ()
Ответ на: комментарий от Sorcerer

Да я читал...
Во всяком случае, пытался. То ли «мой инглиш очень кровать», то ли я просто идиот, потому что по докам видно, что они вполне адекватные.
Кстати, попытки сделать

%type <char> S E T F
или
%type <char *> S E T F
(что более логично), я тоже предпринимал, но результат был аналогичный.
Разумеется, я сделаю ещё не одну попытку таки осилить документацию по бизону (сроки-то поджимают, а вариантов всё меньше).

kosc ()
Ответ на: комментарий от kosc

У вас есть %union, который определяет YYSTYPE. В %type и %token нужно использовать имена элементов этой структуры в качестве типов. Т.е. должно быть примерно так:

%union {
    char variable;
    char *string;
}

%token <variable> VAR
%type <string> S E T F
Sorcerer ★★★★★ ()
Ответ на: комментарий от Sorcerer

В общем, я опять с поклоном. Надеюсь, с последним, а то самому неловко, что так достаю. Тут проблема вроде бы даже не с самим Bison, а с Си.
Компилирую - компилируется, запускаю - запускается, а дальше не любую строку выдаёт бред, причём на одинаковые строки выдаёт разный бред (как будто тыкает в случайную область памяти). Строка e+c превращаяется в [бред]+, а строка e*d - в [бред]*, так что операторы таки ставятся, куда надо. Пробовал разные варианты собирать итоговую строку - ничего.
Текущий пример кода вот: http://paste.pztrn.name/1313/.

kosc ()
Ответ на: комментарий от rogerw

СПбГУАП, 231000 - Программная инженерия.
Сам предмет, с которым такая жесть, называется «Теория языков программирования и методы трансляции».

kosc ()
Ответ на: комментарий от kosc

Мне больно на это смотреть ... :( Вот тебе примитивный RPN калькулятор:

%{
#include <err.h>
#include <ctype.h>
#include <stdio.h>
#define YYSTYPE int
%}

%token NUMBER

%%
stmt
	:			/* empty */
	| stmt expr '\n'	{ printf("\t%d\n", $2); }
	| stmt error '\n'	{ yyerrok; }
	;

expr
	: number		{ $$ = $1; }
	| expr number '+'	{ $$ = $1 + $2; }
	| expr number '-'	{ $$ = $1 - $2; }
	| expr number '*'	{ $$ = $1 * $2; }
	| expr number '/'	{ $$ = $1 / $2; }
	;

number
	: NUMBER		{ $$ = $1; }
	| '-' NUMBER		{ $$ = -$2; }
	;
%%

int
yyerror(char *s) 
{
	warnx(s);
}

int
yylex()
{
	int c;

	while ((c = getchar()) == ' ' || c == '\t')
		;

	if (c == EOF)
		return 0;
	
	if (isdigit(c)) {
		ungetc(c, stdin);
		scanf("%li", &yylval);
		return NUMBER;
	}
	
	return c;
}

int
main ()
{
	yyparse();
}
beastie ★★★★★ ()
Последнее исправление: beastie (всего исправлений: 2)
Ответ на: комментарий от kosc

Значит, прохо читал. Смотри тут: http://dinosaur.compilertools.net/yacc/

Ещё: http://www.gnu.org/software/bison/manual/html_node/Rpcalc-Rules.html#Rpcalc-R...

Какая вообще задача?

PS: от твоего примера глаза кровятся... :( (один #include <cstring> чего стоит)

beastie ★★★★★ ()
Последнее исправление: beastie (всего исправлений: 2)
Ответ на: комментарий от kosc

У вас там неправильная обработка F. Для F нужно выделять память, а вы только указатель на временные данные присваиваете. Нужно так:

F: VAR
        {
                $$ = (char *)malloc(2);
                $$[0] = $1;
                $$[1] = 0;
        };

И уже что-то станет выдаваться. :)

Но ещё несколько проблем у вас осталось:
- При обработке F: '('E')' память выделять не нужно, достаточно присвоения $$ = $2
- Куча утечек памяти, потому что вы почти ничего не освобождаете. Прогоните под valgrind. Фактически, вам нужно освобождать то, что вам больше не нужно, в коде обработки. Т.е. по паре free() после каждого printf().
- Приоритет для '(' задавать нет смысла
- Приоритеты для '+' и '*' у вас перевернуты
- Чтобы приоритеты для '+' и '*' заработали, да и вообще для упрощения, нужно переписать грамматику на что-то типа этого, без T и F:

S: E
E: VAR
 | E '+' E
 | E '*' E
 | '(' E ')'

Sorcerer ★★★★★ ()
Ответ на: комментарий от beastie

PS: от твоего примера глаза кровятся... :(

Вообще-то уже гораздо лучше, чем в предыдущие попытки. Ещё усилие, и лаба будет сдана!

Sorcerer ★★★★★ ()
Ответ на: комментарий от beastie

Переводит из простой нотации в RPN (за правильнось поведения со скобками не ручаюсь — это тебе на домашнее задание, но `dc' говорит, что верно):

%{
#include <ctype.h>
#include <stdio.h>
%}

%union {
	int  i;
	char s[1024];
}

%token <i> NUMBER
%type <s> expr
%left '+' '-'
%left '*' '/'
%left NEG

%%
stmt
	:			/* empty */
	| stmt expr '\n'	{ puts($2); }
	| stmt error '\n'	{ yyerrok; }
	;

expr
	: NUMBER		{ snprintf($$, sizeof($$), "%d", $1); }
	| expr '+' expr		{ snprintf($$, sizeof($$), "%s %s +", $3, $1); }
	| expr '-' expr		{ snprintf($$, sizeof($$), "%s %s -", $3, $1); }
	| expr '*' expr		{ snprintf($$, sizeof($$), "%s %s *", $3, $1); }
	| expr '/' expr		{ snprintf($$, sizeof($$), "%s %s /", $3, $1); }
	| '-' expr %prec NEG	{ snprintf($$, sizeof($$), "-%s", $2); }
	| '(' expr ')'		{ snprintf($$, sizeof($$), "%s", $2); }
	;
%%

int
yyerror(char *s) 
{
	fprintf(stderr, "Error: %s\n", s);
}

int
yylex()
{
	int c;

	while ((c = getchar()) == ' ' || c == '\t')
		;

	if (c == EOF)
		return 0;
	
	if (isdigit(c)) {
		ungetc(c, stdin);
		scanf("%li", &yylval.i);
		return NUMBER;
	}
	
	return c;
}

int
main ()
{
	yyparse();
}

С тебя большой пирожок. ;)

beastie ★★★★★ ()
Последнее исправление: beastie (всего исправлений: 2)
Ответ на: комментарий от beastie
bison -d bison.yy
gcc bison.tab.cc -lm -g -ggdb -O0
bison.tab.cc: In function ‘int yyparse()’:
bison.tab.cc:1135:23: error: ‘yylex’ was not declared in this scope
       yychar = yylex ();
                       ^
bison.tab.cc:1318:35: error: ‘yyerror’ was not declared in this scope
       yyerror (YY_("syntax error"));
                                   ^
bison.tab.cc:1462:35: error: ‘yyerror’ was not declared in this scope
   yyerror (YY_("memory exhausted"));
                                   ^
bison.yy: In function ‘int yylex()’:
bison.yy:54:25: warning: format ‘%li’ expects argument of type ‘long int*’, but argument 2 has type ‘int*’ [-Wformat=]
   scanf("%li", &yylval.i);
                         ^
Makefile:2: recipe for target 'all' failed
make: *** [all] Error 1

Пирожком тут и не пахнет, но спасибо за попытку.

kosc ()
Ответ на: комментарий от kosc
--- lor16.y.orig        2015-04-16 15:06:06.539588662 +0200
+++ lor16.y     2015-04-16 15:06:47.411605710 +0200
@@ -1,6 +1,9 @@
 %{
 #include <ctype.h>
 #include <stdio.h>
+
+void yyerror(const char *);
+int yylex(void);
 %}
 
 %union {
@@ -32,8 +35,8 @@
        ;
 %%
 
-int
-yyerror(char *s) 
+void
+yyerror(const char *s) 
 {
        fprintf(stderr, "Error: %s\n", s);
 }
@@ -51,7 +54,7 @@
 
        if (isdigit(c)) {
                ungetc(c, stdin);
-               scanf("%li", &yylval.i);
+               scanf("%i", &yylval.i);
                return NUMBER;
        }
 
@@ -62,4 +65,5 @@
 main ()
 {
        yyparse();
+       return 0;
 }

Пирожком тут и не пахнет, но спасибо за попытку.

Не отлынивай. Я тебе и так уже 99% твоей работы выполнил. ;) А ты даже домашнее задание, по причёсыванию кода сделать не хочешь.

beastie ★★★★★ ()
Последнее исправление: beastie (всего исправлений: 1)
Ответ на: комментарий от Sorcerer

Уважаемый Sorcerer, считаю должным отчитаться - лаба сдана на десять баллов из десяти, следующая уже будет без flex/bison (по сути сделать тоже самое, но через голые Си), и думаю (надеюсь), что там справлюсь сам.
Если будешь (или уже) в ДС-2 - могу угостить пивом/мороженым или ещё чем-то равноценным на твой выбор. А пока просто большое, человеческое спасибо!

kosc ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.