Нужны советы по проекту. Разбор логического выражения

Question

Я ищу несколько советов по моему школьному проекту. Я должен создать программу, которая принимает логическое выражение и выводит для него таблицу истинности. На самом деле создание таблицы истинности для меня совсем не сложно, и я уже написал для нее методы на Java. Я хотел бы знать, есть ли какие-либо классы в Java, которые я мог бы использовать, чтобы разобрать выражение для меня и положить его в стек. Если нет, то я ищу помощь в разборе выражения. Это скобки, которые получают меня всякий раз, когда я пытаюсь обдумать это. Также, если бы это было проще на любом другом языке, я был бы готов сделать это в этом. Perl, вероятно, мой следующий лучший язык.

Некоторые примеры (P && Q) -> R

(P || Q || R) && ((P -> R) -> Q)

Answer 1

Если вам разрешено использовать инструмент генератора синтаксических анализаторов, такой как ANTLR, вот как вы можете начать. Грамматика для простого логического языка может выглядеть так:

grammar Logic;

parse
  :  expression EOF
  ;

expression
  :  implication
  ;

implication
  :  or ('->' or)*
  ;

or
  :  and ('||' and)*
  ;

and
  :  not ('&&' not)*
  ;

not
  :  '~' atom
  |  atom
  ;

atom
  :  ID
  |  '(' expression ')'
  ;

ID    : ('a'..'z' | 'A'..'Z')+;
Space : (' ' | '\t' | '\r' | '\n')+ {$channel=HIDDEN;};

Однако, если вы проанализируете ввод, например (P || Q || R) && ((P -> R) -> Q), с помощью синтаксического анализатора, сгенерированного из приведенной выше грамматики, дерево синтаксического анализа будет содержать круглые скобки (что вас не заинтересует после анализа выражения), и операторы не будут корень каждого поддерева, который не облегчает вашу жизнь, если вы заинтересованы в оценке выражения.

Вам нужно будет указать ANTLR, что нужно исключить определенные токены из AST (это можно сделать, поместив ! после токена / правила) и сделать определенные токены / правила корнем их (под) дерево (это можно сделать, поместив ^ после него). Наконец, вам необходимо указать в разделе options вашей грамматики, что вы хотите создать правильное AST вместо простого дерева разбора.

Итак, приведенная выше грамматика будет выглядеть так:

// save it in a file called Logic.g
grammar Logic;

options {
  output=AST;
}

// parser/production rules start with a lower case letter
parse
  :  expression EOF!    // omit the EOF token
  ;

expression
  :  implication
  ;

implication
  :  or ('->'^ or)*    // make `->` the root
  ;

or
  :  and ('||'^ and)*    // make `||` the root
  ;

and
  :  not ('&&'^ not)*      // make `&&` the root
  ;

not
  :  '~'^ atom    // make `~` the root
  |  atom
  ;

atom
  :  ID
  |  '('! expression ')'!    // omit both `(` and `)`
  ;

// lexer/terminal rules start with an upper case letter
ID    : ('a'..'z' | 'A'..'Z')+;
Space : (' ' | '\t' | '\r' | '\n')+ {$channel=HIDDEN;};

Вы можете протестировать анализатор с помощью следующего класса:

import org.antlr.runtime.*;
import org.antlr.runtime.tree.*;
import org.antlr.stringtemplate.*;

public class Main {
  public static void main(String[] args) throws Exception {

    // the expression
    String src = "(P || Q || R) && ((P -> R) -> Q)";

    // create a lexer & parser
    LogicLexer lexer = new LogicLexer(new ANTLRStringStream(src));
    LogicParser parser = new LogicParser(new CommonTokenStream(lexer));

    // invoke the entry point of the parser (the parse() method) and get the AST
    CommonTree tree = (CommonTree)parser.parse().getTree();

    // print the DOT representation of the AST 
    DOTTreeGenerator gen = new DOTTreeGenerator();
    StringTemplate st = gen.toDOT(tree);
    System.out.println(st);
  }
}

Теперь, чтобы запустить класс Main, выполните:

* NIX / MacOS

java -cp antlr-3.3.jar org.antlr.Tool Logic.g 
javac -cp antlr-3.3.jar *.java
java -cp .:antlr-3.3.jar Main

Windows

java -cp antlr-3.3.jar org.antlr.Tool Logic.g 
javac -cp antlr-3.3.jar *.java
java -cp .;antlr-3.3.jar Main

, который будет печатать DOT источник следующего AST:

(изображение, полученное с помощью graphviz-dev.appspot.com )

Теперь все вам нужно оценить это AST! :)

Answer 2

В Perl вы можете использовать Regexp::Grammars для анализа.Это может быть немного на стороне «гранаты, чтобы убить муравья», но это должно сработать.

Редактировать: Вот (очень быстрый) пример, который может помочь вам.

#!/usr/bin/env perl

use strict;
use warnings;

use Regexp::Grammars;
use Data::Dumper;

my $parser = qr/
  <nocontext:>

  <Logic>

  <rule: Logic>     <[Element]>*

  <rule: Element>   <Group> | <Operator> | <Item>

  <rule: Group>     \( <[Element]>* \)

  <rule: Operator>  (?:&&) | (?:\|\|) | (?:\-\>)

  <rule: Item>      \w+
/xms;                    #/ #Fix Syntax Highlight

my $text = '(P && Q) -> R';

print Dumper \%/ if $text =~ $parser; #/ #Fix Syntax Highlight

Answer 3

Если вы хотите написать собственный синтаксический анализатор, используйте алгоритм Shunting-yard , чтобы избавиться от скобок, преобразовав выражение из инфикса в постфиксную запись или непосредственно в дерево.

Answer 4

Создать анализатор выражений легко.Присоединение действий для вычисления значения при разборе также очень просто.

Я предполагаю, что вы можете написать BNF для вашего языка выражений.

Этот ответ показывает, как легко создать анализатор,если у вас есть БНФ.

Есть ли альтернатива flex / bison, которую можно использовать в 8-битных встроенных системах?

Answer 5

Посмотрите в JavaCC или ANTLR. Регулярные выражения не будут работать

Возможно, вы также можете запустить свой собственный анализатор с помощью StreamTokenizer.

Answer 6

Другой генератор синтаксических анализаторов для Java - CUP .