Статьи

Парсер рекурсивного спуска с C # — булевыми логическими выражениями

Май 8, 2018

В предыдущем посте  мы дали краткое введение в парсеры рекурсивного спуска и реализовали парсер, который был способен анализировать и вычислять простые арифметические выражения с сложением и вычитанием.

Быть (правда) или! (Быть правдой)?

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

Примеры выражений, которые мы хотим иметь возможность анализировать и оценивать:

  • Правда и правда и ложь
  • Правда
  • !Ложь
  • (! (Ложь)) и (! (Правда) и т. Д.

Давайте соберем грамматику EBNF для этого типа выражений:

Expression      := [ "!" ] <Boolean> { BooleanOperator Boolean }
Boolean         := BooleanConstant | Expression | "(" <Expression> ")"
BooleanOperator := "And" | "Or" 
BooleanConstant := "True" | "False"

Вы можете видеть, что нашими терминальными символами являются «И», «Или» (BooleanOperator) и «Истина», «Ложь» (BooleanConstant) и, конечно же, «!» и скобки.

Выражение может иметь дополнительный символ отрицания «!» и затем Boolean (который может быть BooleanConstant или Expression или Expression в скобках).

Каждое следующее логическое выражение является необязательным, но если оно существует, ему должен предшествовать BooleanOperator, чтобы мы могли проанализировать окончательное значение, объединив его с предыдущим логическим значением. Очевидно, у нас будет некоторая рекурсия, но об этом позже, когда мы начнем реализовывать парсер.

Всегда токенизируй все!

Прежде чем заглядывать в анализатор, мы должны реализовать класс Tokenizer, который будет анализировать необработанный текст выражения, маркировать его и возвращать IEnumerable <Token>, чтобы у нашего анализатора было меньше поводов для беспокойства.

Вот класс токенизатора:

public class Tokenizer
{
    private readonly StringReader _reader;
    private string _text;

    public Tokenizer(string text)
    {
        _text = text;
        _reader = new StringReader(text);
    }

    public IEnumerable<Token> Tokenize()
    {
        var tokens = new List<Token>();
        while (_reader.Peek() != -1)
        {
            while (Char.IsWhiteSpace((char) _reader.Peek()))
            {
                _reader.Read();
            }

            if (_reader.Peek() == -1)
                break;

            var c = (char) _reader.Peek();
            switch (c)
            {
                case '!':
                    tokens.Add(new NegationToken());
                    _reader.Read();
                    break;
                case '(':
                    tokens.Add(new OpenParenthesisToken());
                    _reader.Read();
                    break;
                case ')':
                    tokens.Add(new ClosedParenthesisToken());
                    _reader.Read();
                    break;
                default:
                    if (Char.IsLetter(c))
                    {
                        var token = ParseKeyword();
                        tokens.Add(token);
                    }
                    else
                    {
                        var remainingText = _reader.ReadToEnd() ?? string.Empty;
                        throw new Exception(string.Format("Unknown grammar found at position {0} : '{1}'", _text.Length - remainingText.Length, remainingText));
                    }
                    break;
            }
        }
        return tokens;
    }

    private Token ParseKeyword()
    {
        var text = new StringBuilder();
        while (Char.IsLetter((char) _reader.Peek()))
        {
            text.Append((char) _reader.Read());
        }

        var potentialKeyword = text.ToString().ToLower();

        switch (potentialKeyword)
        {
            case "true":
                return new TrueToken();
            case "false":
                return new FalseToken();
            case "and":
                return new AndToken();
            case "or":
                return new OrToken();
            default:
                throw new Exception("Expected keyword (True, False, And, Or) but found "+ potentialKeyword);
        }
    }
}

На самом деле ничего особенного не происходит, мы просто просматриваем символы выражения, и если его отрицание или скобка, мы возвращаем надлежащие подклассы токена, и если мы обнаруживаем буквы, мы пытаемся проанализировать одно из наших ключевых слов («True», «False» , «И», «Или»).
Если мы встречаем неизвестное ключевое слово, мы бросаем исключение, чтобы быть на безопасной стороне. Я намеренно не делал много проверок выражения в этом классе, так как это делается позже в Parser — но ничто не помешает нам сделать это и здесь — я оставлю это упражнение читателю.

Парсер

Внутри нашего парсера у нас есть основной метод Parse , который запускает процесс синтаксического анализа токенов, обрабатывает отрицание и продолжает синтаксический анализ подвыражений, пока он встречает один из OperandTokens (AndToken или OrToken).

public bool Parse()
{
    while (_tokens.Current != null)
    {
        var isNegated = _tokens.Current is NegationToken;
        if (isNegated)
            _tokens.MoveNext();

        var boolean = ParseBoolean();
        if (isNegated)
            boolean = !boolean;

        while (_tokens.Current is OperandToken)
        {
            var operand = _tokens.Current;
            if (!_tokens.MoveNext())
            {
                throw new Exception("Missing expression after operand");
            }
            var nextBoolean = ParseBoolean();

            if (operand is AndToken)
                boolean = boolean && nextBoolean;
            else
                boolean = boolean || nextBoolean;

        }

        return boolean;
    }

    throw new Exception("Empty expression");
}

Разбор подвыражений обрабатывается методом ParseBoolean :

private bool ParseBoolean()
 {
     if (_tokens.Current is BooleanValueToken)
     {
         var current = _tokens.Current;
         _tokens.MoveNext();

         if (current is TrueToken)
             return true;

         return false;
     }
     if (_tokens.Current is OpenParenthesisToken)
     {
         _tokens.MoveNext();

         var expInPars = Parse();

         if (!(_tokens.Current is ClosedParenthesisToken))
             throw new Exception("Expecting Closing Parenthesis");

         _tokens.MoveNext(); 

         return expInPars;
     }
     if (_tokens.Current is ClosedParenthesisToken)
         throw new Exception("Unexpected Closed Parenthesis");

     // since its not a BooleanConstant or Expression in parenthesis, it must be a expression again
     var val = Parse();
     return val;
 }

Этот метод пытается проанализировать простейший BooleanValueToken, затем, если он сталкивается с OpenParenthesisToken, он обрабатывает выражения в круглых скобках, пропуская OpenParenthesisToken, а затем вызывает метод Parse,  чтобы получить значение выражений, а затем снова пропускает ClosedParenthesisToken после выполнения анализа внутреннего выражения.

Если он не находит BooleanValueToken или OpenParenthesisToken — метод просто предполагает, что последующее снова является выражением, поэтому он вызывает метод Parse для повторного запуска процесса синтаксического анализа.

Быть логичным значит быть простым

Как видите, мы реализовали анализатор менее чем в 90 строках кода C #. Возможно, этот код не очень полезен, но полезен для рекурсивного построения логики синтаксического анализа.

Это может быть улучшено добавлением дополнительной логики для выдачи исключений при обнаружении неожиданных токенов, но опять же — я оставляю это для читателя (например, выражение вроде «true)» должно генерировать исключение, но в этой версии кода это не будет сделано , он все равно будет правильно анализировать выражение, игнорируя закрывающую скобку).

тесты

Вот некоторые из модульных тестов, которые я создал для тестирования парсера:

[TestCase("true", ExpectedResult = true)]
[TestCase(")", ExpectedException = (typeof(Exception)))]
[TestCase("az", ExpectedException = (typeof(Exception)))]
[TestCase("", ExpectedException = (typeof(Exception)))]
[TestCase("()", ExpectedException = typeof(Exception))]
[TestCase("true and", ExpectedException = typeof(Exception))]
[TestCase("false", ExpectedResult = false)]
[TestCase("true ", ExpectedResult = true)]
[TestCase("false ", ExpectedResult = false)]
[TestCase(" true", ExpectedResult = true)]
[TestCase(" false", ExpectedResult = false)]
[TestCase(" true ", ExpectedResult = true)]
[TestCase(" false ", ExpectedResult = false)]
[TestCase("(false)", ExpectedResult = false)]
[TestCase("(true)", ExpectedResult = true)]
[TestCase("true and false", ExpectedResult = false)]
[TestCase("false and true", ExpectedResult = false)]
[TestCase("false and false", ExpectedResult = false)]
[TestCase("true and true", ExpectedResult = true)]
[TestCase("!true", ExpectedResult = false)]
[TestCase("!(true)", ExpectedResult = false)]
[TestCase("!(true", ExpectedException = typeof(Exception))]
[TestCase("!(!(true))", ExpectedResult = true)]
[TestCase("!false", ExpectedResult = true)]
[TestCase("!(false)", ExpectedResult = true)]
[TestCase("(!(false)) and (!(true))", ExpectedResult = false)]
[TestCase("!((!(false)) and (!(true)))", ExpectedResult = true)]
[TestCase("!false and !true", ExpectedResult = false)]
[TestCase("false and true and true", ExpectedResult = false)]
[TestCase("false or true or false", ExpectedResult = true)]
public bool CanParseSingleToken(string expression)
{
    var tokens = new Tokenizer(expression).Tokenize();
    var parser = new Parser(tokens);
    return parser.Parse();
}

Полный исходный код всего решения доступен в моем  репозитории BooleanLogicExpressionParser GitHub .

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

 

53
Share: