Проблема с Lex и Yacc

  • Автор темы AlexandraKr
  • Дата начала
A

AlexandraKr

#1
Дано задание:

Транслятор произвольных логических выражений в ДНФ

Разработать язык описания логических выражений , позволяющий :
описывать сложные логические выражения, учитывая приоритет логических операций и используя скобочную форму записи;
допустимыми логическими операциями являются И, ИЛИ, НЕ и ИМПЛИКАЦИЯ;
операндами логических операций могут быть константы (0 или 1) и переменные.
При конструировании имен логических переменных использовать правила для аналогичных объектов языка СИ.
Разработать программу-транслятор вводимых пользователем (на предложенном языке) логических выражений в дизъюнктивную нормальную форму (ДНФ). При этом должны производиться исключение констант и минимизация элементарных конъюнкций. Обязательно должен проверяться синтаксис вводимых выражений.


Программа должна быть написана на Lex и Yacc.
Грамматика языка: буквы, цифры 1 0, НЕ=!, И=+, ИЛИ=-. ИМПЛИКАЦИЯ=->
Алгоритм преобразований следующий:
сначала с помощью правила !!x=x и правил Де Моргана: !(x1*x2)=!x1+!x2 и !(x1+x2)=!x1*!x2 все отрицания спускаются до переменных, затем раскрываются скобки, с помощью x*x=x и x+x=x, x*!x=0 и x+!x=1 удаляются лишние конъюнкции и повторения переменных в конъюнкциях, а с помощью свойств констант (x*1=x, x*0=0 и т.д.) удаляются константы.

Lex-файл:

C++:
%{
#define OP_IMP 258
#define OP_PLUS 259
#define OP_MUL 260
#define OP_OTR 261
#define L_BR 262
#define R_BR 263
#define ID 264
#define NUM 265

extern int line;
char* lex;
typedef union
{
int iValue;
char* nPtr;
} YYSTYPE;
extern YYSTYPE yylval;


%};

a [aA]
b [bB]
c [cC]
d [dD]
e [eE]
f [fF]
g [gG]
j [jJ]
h [hH]
k [kK]
m [mM]
n [nN]
o [oO]
p [pP]
r [rR]
s [sS]
q [qQ]
t [tT]
y [yY]
x [xX]
z [zZ]
u [uU]
v [vV]
w [wW]
i [iI]
l [lL]
VAR [a-zA-Z_][a-zA-Z_0-9]*
NUM [01]

%%
{VAR} {ECHO;yyset(yytext); return ID;}
{NUM} {ECHO;yyset(yytext); return NUM;}
"->" {ECHO;yyset(yytext); return OP_IMP;}
"+" {ECHO;yyset(yytext); return OP_PLUS;}
"*" {ECHO;yyset(yytext); return OP_MUL;}
"!" {ECHO;yyset(yytext); return OP_OTR;}
\( {printf("%s",yytext);yyset("("); return L_BR;}
\) {printf("%s",yytext);yyset(")"); return R_BR;}
" " {};
[ \r\t] {};
"\n" {line++;}; 
. {};


%%
int yyset(char* str)
{
lex=(char*)malloc(yyleng);
memcpy((char*)lex,yytext,yyleng+1);
yylval.nPtr=lex;
}

Yacc-файл:

C++:
%start expr
%union {
int iValue;
char* nPtr; };
%token <nPtr> OP_IMP OP_PLUS OP_MUL OP_OTR L_BR R_BR ID NUM 
%left OP_PLUS
%left OP_MUL
%left OP_OTR

%{
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char *result;
int num=0;
int line=1;
extern void res(char*);
%}

%%
expr: expr OP_MUL expr 
|expr OP_PLUS expr
|expr OP_IMP expr 
|OP_OTR expr
|L_BR expr R_BR
|NUM
|ID
;


%%
yyerror(char* s)
{ 
printf("Syntax error at line %d\n",line);
exit(line);
}
main()
{
yyparse();
printf("%s\n",result);
}

Вопрос:
Каким образом реализовать эти все логические преобразования с учетом того, что транслятор должен преобразовывать выражение в ДНФ за один запуск программы?