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

Тема в разделе "Общие вопросы по С и С++", создана пользователем AlexandraKr, 10 окт 2010.

  1. AlexandraKr

    AlexandraKr Гость

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

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

    Разработать язык описания логических выражений , позволяющий :
    описывать сложные логические выражения, учитывая приоритет логических операций и используя скобочную форму записи;
    допустимыми логическими операциями являются И, ИЛИ, НЕ и ИМПЛИКАЦИЯ;
    операндами логических операций могут быть константы (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);
    }

    Вопрос:
    Каким образом реализовать эти все логические преобразования с учетом того, что транслятор должен преобразовывать выражение в ДНФ за один запуск программы?
     
Загрузка...
Похожие Темы - Проблема Lex Yacc
  1. c0de3r
    Ответов:
    4
    Просмотров:
    109
  2. DobermannTT
    Ответов:
    10
    Просмотров:
    130
  3. SoulPaladin
    Ответов:
    3
    Просмотров:
    119
  4. Artael
    Ответов:
    1
    Просмотров:
    107
  5. ENSLER
    Ответов:
    0
    Просмотров:
    100

Поделиться этой страницей