реализация условных выражений в оболочке (&& и ||) - PullRequest
Новая
       3

реализация условных выражений в оболочке (&& и ||)

1 голос
/ 27 ноября 2011

Я пытаюсь реализовать && и ||операторы оболочки bash для назначения - в C. Для такого ввода, как:

a && b && c

мой анализатор создает связанный список с «символом» и «соединителем», т. е.:

a - &&

b - &&

c - END

, поэтому я могу оценить символ, чтобы определить, проверять следующее условие или нет.Я знаю основную идею, но есть ли общий алгоритм для реализации условных выражений?Главным образом, если кто-то передает что-то вроде a && (b | c) || d && e || f, то я просто не знаю, как можно это атаковать.Я попытался оценить первый символ и сохранить статус, чтобы проверить, что читать дальше, но это не очень хороший подход.

Есть предложения?

Ответы [ 2 ]

3 голосов
/ 27 ноября 2011

Общий метод реализации этого приводит к синтаксическому дереву, а не списку.Вам необходимо проанализировать список токенов (который вы создали) в AST (абстрактное синтаксическое дерево), описывающее выражение.

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

Вот пример кода на Python, который создаст вашу древовидную структуру.Это немного уродливо, и я бы написал более красивый парсер, если бы действительно делал это.Это просто для того, чтобы дать вам общее представление: 

def parsellst(lst):
    stack = []
    for tok in lst:
        if tok == '(':
            if (len(stack) > 0) and (stack[-1] not in ('&&', '||')):
                raise RuntimeError("Malformed expression")
            stack.append(tok)
        elif tok == ')':
            while (len(stack) >= 4) and (stack[-2] != '('):
                if stack[-2] not in ('&&', '||'):
                    raise RuntimeError("Malformed expression")
                node = (stack[-2], stack[-3], stack[-1])
                stack[-3:] = [node]
            if (len(stack) <= 1) or (stack[-2] != '(') or \
                    (stack[-1] in ('&&', '||')):
                raise RuntimeError("Malformed expression")
            stack.pop(-2)
        elif tok == '||':
            if len(stack) <= 0:
                raise RuntimeError("Malformed expression")
            elif stack[-1] in ('&&', '||', '('):
                raise RuntimeError("Malformed expression")
            while (len(stack) >= 3) and (stack[-2] != '('):
                node = (stack[-2], stack[-3], stack[-1])
                stack[-3:] = [node]
            stack.append(tok)
        elif tok == '&&':
            if len(stack) <= 0:
                raise RuntimeError("Malformed expression")
            elif stack[-1] in ('&&', '||', '('):
                raise RuntimeError("Malformed expression")
            if (len(stack) > 1) and (len(stack) < 3):
                raise RuntimeError("Malformed expression")
            while (len(stack) >= 3) and (stack[-2] not in ('(', '||')):
                node = (stack[-2], stack[-3], stack[-1])
                stack[-3:] = [node]
            stack.append(tok)
        else:
            stack.append(tok)
    while len(stack) > 1:
        if len(stack) < 3:
            raise RuntimeError("Malformed expression")
        if stack[-2] == '(':
            raise RuntimeError("Malformed expression: missing )")
        else:
            node = (stack[-2], stack[-3], stack[-1])
            stack[-3:] = [node]
    if len(stack) > 0:
        return stack[-1]
    else:
        return ()

Древовидная структура, которую строит этот код, очень неэффективна.Каждый узел вашего дерева состоит из «кортежа» (вроде списка списков) в Python, который выглядит как (operator, arg1, arg2).Вам решать, как его использовать.Как подсказка, вам нужно написать оценщик, который обработал дерево в определенном порядке.

Кроме того, этот синтаксический анализатор удаляет круглые скобки, потому что он обрабатывает круглые скобки как просто группирующую конструкцию.Но для bash это не разумно, потому что скобки имеют значение, выходящее за рамки простой группировки.Таким образом, вещь должна быть изменена (что относительно тривиально), чтобы поместить «оператор круглых скобок» обратно в результирующее дерево.

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

>>> parsellst(['a', '&&', '(', 'b', '||', 'c', ')', '||', 'd', '&&', 'e', '||', 'f'])
('||', ('||', ('&&', 'a', ('||', 'b', 'c')), ('&&', 'd', 'e')), 'f')
1 голос
/ 27 ноября 2011

Используйте дерево синтаксического анализа: http://en.wikipedia.org/wiki/Parse_tree

Я сделал пример дерева, которое вы можете использовать здесь: http://csclub.uwaterloo.ca/~mtahmed/parse.txt

В этом текстовом файле символ \ссылка, - символы составляют ветви, буквы составляют переменные, а все остальное - операторы, такие как && и | и || и т. д.

Кроме того, обратите внимание, что поскольку существуеткороткое замыкание, вы можете добавить проверки внутри вашей функции синтаксического анализа, чтобы увидеть, было ли что-то короткое замыкание и остановить.Например, если вы видите, что a равно false, а следующий оператор - &&, прекратите синтаксический анализ и верните false.

...