Как создать грамматику для применения теоремы Де Моргана к выражению с помощью yacc?

Question

Я хотел бы применить Demorgan's theorem к вводу с использованием yacc и lex.

вход может быть любое выражение, такие как A + B, (А + В) и т.д.:!

• Выражение а + Ь должно привести к ∙ б
• Выражение (! a + b) должно привести к a + b

Я думаю, что часть lex выполнена, но у меня возникают трудности с грамматикой yacc, необходимой для применения законов к выражению.

Я пытаюсь реализовать следующий алгоритм. Рассмотрим следующее уравнение в качестве входных данных: Y = A + B

После применения закона Де Моргана он становится:! Y = (A + B)

Наконец, расширение скобок должно привести к Y = A! ∙ B

здесь Лекса код:

%{ 
#include <stdio.h> 
#include "y.tab.h" 

extern int yylval; 
int yywrap (void); 
%} 

%% 
[a-zA-Z]+ {yylval = *yytext; return ALPHABET;} 
"&&"  return AND; 
"||"  return OR; 
"="  return ('='); 
[\t]  ; 
\n  return 0; 
.  return yytext[0]; 
"0exit"  return 0; 
%% 

int yywrap (void) 
{ 
    return 1; 
} 

Вот мой Yacc код:

%{ 
#include <stdio.h> 

int yylex (void); 
void yyerror (char *); 
extern FILE* yyin; 
%} 

%token ALPHABET 
%left '+''*' 
%right '=' '!' NOT 

%left AND OR 
%start check 

%% 
check : expr {printf("%s\n",$$);} 
     ; 
expr : plus 
    |plus '+' plus {$$ = $1 + $3;} 
    ; 
plus : times 
    |times '*' times {$$ = $1 * $3;} 
    ; 
times : and_op 
     |and_op AND and_op{$$ = $1 && $3;} 
     ; 
and_op : or_op 
     |or_op OR or_op {$$ = $1 || $3;} 
     ; 
or_op : not_op 
     |'!' not_op {$$ = !$2;} 
     ; 
not_op : paren 
     |'(' paren ')' {$$ = $2;} 
     ; 
paren : 
     |ALPHABET  {$$ = $1;} 
     ; 

/* 
E: E '+' E  {$$ = $1 + $3;} 
    |E '*' E {$$ = $1 * $3;} 
    |E '=' E {$$ = $1 = $3;} 
    |E AND E {$$ = ($1 && $3);} 
    |E OR E {$$ = ($1 || $3);} 
    |'(' E ')' {$$ = $2;} 
    |'!' E %prec NOT {$$ = !$2;} 
    |ALPHABET  {$$ = $1;} 
    ;*/ 
%% 

int main() 
{ 
    char filename[30]; 
    char * line = NULL; 
    size_t len = 0; 
    printf("\nEnter filename\n"); 
    scanf("%s",filename); 
    FILE *fp = fopen(filename, "r"); 
    if(fp == NULL) 
    { 
     fprintf(stderr,"Can't read file %s\n",filename); 
     exit(EXIT_FAILURE); 
    } 
    yyin = fp; 
// while (getline(&line, &len, fp) != -1) 
// { 
//  printf("%s",line); 
// } 
// printf("Enter the expression:\n"); 
    do 
    { 
     yyparse(); 
    }while(!feof(yyin)); 

    return 0; 
} 

Answer 1

Вы пытаетесь создать систему компьютерной алгебры.

Ваша задача концептуально проста:

1. Определение лексера для атомов ваших «логических» выражений
2. Определение парсер для пропозициональной логики с точки зрения лексем
3. Построить дерево, которое хранит выражения
4. Определить процедуры, реализующие логические эквивалентности (теорема ДеМоргана - одна), которые найдут место в дереве, где оно может быть применено путем сопоставления древовидной структуры, а затем соответствующим образом модифицирует дерево.
5. Выполните эти процедуры для достижения логики переписывает вы хотите
6. Prettyprint окончательный AST как ответ

Но концептуально простой не обязательно означает, что легко сделать, и получить все это право.

(f) lex и yacc предназначены для того, чтобы помочь вам сделать шаги 1-3 относительно простым способом; их документация содержит довольно хорошее руководство. Они не помогут с этапами 4-6, и здесь происходит реальная работа. (Ваша грамматика выглядит довольно неплохо для этой части).

(Вы можете сделать 1-3 без flex и yacc by building a recursive descent parser that also happens to build the AST as it goes).

Шаг 4 может быть грязным, потому что вам нужно решить, какие логические теоремы вы хотите использовать, а затем написать процедуру для каждого, чтобы выполнить согласование дерева и разбиение дерева, чтобы достичь желаемого результата.Ты можешь это сделать; его простой процедурный код, который перемещается вверх и вниз по дереву, сравнивая типы узлов и отношения с дочерними элементами для соответствия, а затем вызывая узлы, удаляя узлы, создавая узлы и перематывая их для изменения дерева. Это всего лишь куча кода.

Подложки алгебраических переписываний теперь укусят вас: (булева) алгебра имеет ассоциативные и коммутативные операторы. Это означает, что некоторые правила алгебры будут применяться к частям дерева, которые произвольно далеко друг от друга. Рассмотрим это правило:

a*(b + !a) => a*(b) 

Что происходит, когда фактический срок разбираемый выглядит следующим образом:

q*(a + b + c + ... !q ... + z) 

«Простой» процедурный код, чтобы посмотреть на дерево теперь должен идти сколь угодно далеко вниз по поддеревьев чтобы найти, где это правило может применяться. Внезапно кодирование логики сопоставления не так просто, и это не приведет к разрушению дерева.

Если мы проигнорировать ассоциативные и коммутативные проблемы, для сложных совпадений и модификаций код может быть немного неудобным для записи и его трудно читать; после того, как вы это сделаете, это будет очевидно. Если вы хотите только сделать DeMorgan-over-or, вы можете сделать это относительно легко, просто закодировав его. Если вы хотите реализовать множество правил логических алгебр для упрощения, это станет болезненным. То, что вы хотели бы сделать, это выразить логические правила в той же нотации, что и ваша логическая логика, чтобы они были легко выражены, но теперь вам нужно что-то, что может читать и интерпретировать логические правила. Это сложный кусок кода, но если все сделано правильно, вы можете кодировать логические правила что-то вроде следующего:

rule deMorgan_for_or(t1:boolexp, t2:boolexp):boolexp->boolexp 
    " ! (\t1 + \t2) " -> " !\t1 * !\t2 "; 

Родственная проблема (шаг 5), где вы хотите применить логику правила? Просто потому, что вы можете применять закон ДеМоргана в 15 местах в очень большом логическом терминах, не означает, что вы обязательно захотите это сделать. Поэтому где-то вы должны иметь механизм контроля, который определяет, какие из ваших многочисленных правил должны применяться, и где они должны применяться. Это превращает вас в метапрограммирование, совершенно новую тему.

Если ваши правила являются «монотонными», то есть они могут применяться только один раз, вы можете просто запустить их повсюду и получить завершающий расчет, если этот монотонный ответ тот, который вы хотите. Если у вас есть правила, которые являются инверсиями (например,! (X + y) =>! X *! Y, и! A *! B =>! (A + b)), тогда ваши правила могут выполняться вечно, повторяя и отменяя переписывать. Поэтому вы должны быть осторожны, чтобы убедиться, что вы получили расторжение.

Наконец, если у вас есть модифицированное дерево, вам необходимо распечатать его обратно в удобочитаемой форме (шаг 6). См. Мой SO answer on how to build a prettyprinter.

Выполнение всего этого для одного или двух правил самостоятельно - это отличное учебное упражнение.

Выполнение этой идеи с использованием полезного инструмента - это совершенно другое животное. Там вам нужен набор инфраструктуры, который позволяет это легко выразить: a program transformation system. Вы можете увидеть полный пример этого, как он выглядит как for a system doing arithmetic rather than boolean computations с использованием правил перезаписи синтаксиса, , включая обработку ассоциативных и коммутативных проблем перезаписи. В другом примере вы можете увидеть what it looks like for boolean logic (see simplify_boolean near end of page), который показывает реальный пример правил, как я писал выше.