Можно ли использовать синтаксический анализатор JavaCC для синтаксического анализа String и применить к нему дистрибутивный закон?

Question

Например, в моем случае,

Учитывая Строка keyword1 AND (keyword2 OR keyword3) должна быть расширена до (keyword1 AND Keyword2) OR (keyword1 AND keyword3).

Если возможно, предложите мне способ, которым я могу достичь этого. Я новичок в JavaCC.

Answer 1

Чтобы сделать вашу задачу, вам нужно:

• Грамматика для логических выражений
• синтаксический анализатор для булевой языка
• Устройство AST сборки из разборе шаги
• Некоторые машины (дерево совпадение/взлом) для реализации ваших правил перезаписи.

JavaCC предоставляет вам только парсер; вы должны предоставить грамматику. Сам JavaCC не предоставляет никакой конкретной помощи при построении деревьев, но связанный пакет JJTree упрощает это. Он обеспечивает нулевую помощь с шагом перезаписи; вам нужно будет реализовать это процедурно, что означает восхождение вверх и вниз по дереву, чтобы оно соответствовало И внутри OR (ваше основное исходное место для закона о дистрибутиве, а затем взломало дерево, чтобы преобразовать дерево). Наконец, вы хотите распечатать отредактированное дерево назад, JavaCC также не дает никакой помощи.

ANTLR4 немного ближе. Вы предоставляете ему грамматику, автоматически создавая дерево. Он не будет печатать отредактированное дерево сам по себе, но это так называемые StringTemplates, которые помогают с задачей.

В общем, вы действительно хотите, чтобы program transformation system, что позволяет выполнять все эти задачи организованным образом .

Наш DMS является одним из них и может легко решить эту проблему. Вы предоставляете DMS с грамматикой. Он автоматически строит деревья при его анализе. Вы предоставляете DMS с шаблонами правил перезаписи, изложенными в терминах языка вашей грамматики; DMS будет применять их и пересматривать деревья. В качестве части определения парсера вы также указываете (легко) правила правильной печати, таким образом, легко вернуть исправленный результат.

С этой грамматикой DMS (это пропускает шаг лексического анализатора, но это очень легко):

BOOLEXP = disjunction ; 
    disjunction = conjunction ; 
    [associative-commutative] disjunction = disjunction 'OR' conjunction ; 
    conjunction = term ; 
    [associative-commutative] conjunction = conjunction 'AND' term ; 
    term = VARIABLENAME ; 
    term = '(' disjunction ')' ; 
    term = 'NOT' term ; 

экрана «[ассоциативно-коммутативный]» часть говорит DMS, что эти правила имеют те алгебраические свойства («AC»).

Тогда это правило переписывание DMS реализует ваш запрос напрямую:

 rule apply_distributive_law(t1:term,t2:disjunction,t3:conjunction):disjunction->disjunctions 
      = "\t1 AND (\t2 OR \t3) " -> " \t1 AND \t2 OR \t1 AND \t3 "; 

Обратите внимание, как мы почти не разговаривали о деревьях, не говоря уже манипулировать ими. Что не очевидно, так это не только соответствие конкретной модели, но и любая перестановка АС этих терминов. Это очень сложно кодировать процедурно.

Поскольку переписывает легко, мы также можем выбрать тот случай, когда кто-то написало свое состояние в инверсной форме:

 rule apply_demorgan(t1:term, t2: conjunction): disjunction -> disjunction 
      = " NOT (\t1 AND \t2) " -> " NOT \t1 OR NOT (\t2) "; 

Это должно быть легко понять, как писать закон де Морган для НЕ-ИЛИ от этого.DMS по умолчанию применяет все правила, которые вы ему даете, пока не будет применено никаких дополнительных правил. Если вы передадите оба вышеуказанных правила, он преобразует отмененную форму, используя apply_demorgan, а затем дистрибутивный закон. Когда вы добавляете больше правил, эффекты могут быть замечательными и очень сложно воспроизвести с помощью процедурного кода.

Вы можете видеть a fully worked example on conventional algebra (а не булеву алгебру). Все те же проблемы возникают.