Система синтаксического анализа Gold - для чего ее можно использовать в программировании?

StackOverflow https://stackoverflow.com/questions/212228

  •  03-07-2019
  •  | 
  •  

Вопрос

Я прочитал Домашнюю страницу GOLD ( http://www.devincook.com/goldparser/ ) документы, часто задаваемые вопросы и Википедию, чтобы узнать, какое практическое применение может быть у ЗОЛОТА.Я думал о том, чтобы иметь язык программирования (легкий), доступный для моих систем, таких как ABAP в SAP или X ++ в Axapta, но мне это кажется неосуществимым, по крайней мере нелегким, даже если вы используете GOLD.

Окончательное использование обработанного результата, полученного GOLD, ускользает от меня - что вы делаете с результатом синтаксического анализа?

Редактировать:Было бы здорово привести практический пример (описание).

Это было полезно?

Решение

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

Простой пример, lex будет конвертировать:

если (a + b > 2), то

В к: 

IF_TOKEN LEFT_PAREN IDENTIFIER(a) PLUS_SIGN IDENTIFIER(b) GREATER_THAN NUMBER(2) RIGHT_PAREN THEN_TOKEN

Анализ разбирает этот поток токенов и пытается извлечь из них еще больше смысла. В этом случае он попытается сопоставить эти токены с IF_STATEMENT. С точки зрения синтаксиса, IF _STATEMENT вполне может выглядеть так: 

 IF ( BOOLEAN_EXPRESSION ) THEN

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

Таким образом, синтаксический анализатор может преобразовать вышеупомянутое в: 

    if_statement
        |
        v
    boolean_expression.operator = GREATER_THAN
       |          |
       |          v
       V       numeric_constant.string="2" 
    expression.operator = PLUS_SIGN
     |     |
     |     v
     v   identifier.string = "b"
   identifier.string = "a"

Здесь вы видите, что у нас есть IF_STATEMENT. IF_STATEMENT имеет единственный аргумент, который является BOOLEAN_EXPRESSION. Это было каким-то образом объяснено парсеру. Когда синтаксический анализатор преобразует поток токенов, он "знает" как выглядит IF и знает, как выглядит BOOLEAN_EXPRESSION, поэтому он может делать правильные назначения, когда видит код.

Например, если у вас есть только

если (a + b), то

Парсер может знать, что это не логическое выражение (потому что + - это арифметика, а не логический оператор), и в этом случае синтаксический анализ может вызвать ошибку.

Далее мы видим, что BOOLEAN_EXPRESSION имеет 3 компонента, оператор (GREATER_THAN) и две стороны, левую и правую стороны.

С левой стороны он указывает на еще одно выражение, "a + b", а справа - на NUMERIC_CONSTANT, в данном случае на строку "2". Опять же, синтаксический анализатор "знает" это числовая константа, потому что мы рассказали о строках чисел. Если бы это были не числа, это был бы ИДЕНТИФИКАТОР (например, «a» и «b»).

Обратите внимание, что если бы у нас было что-то вроде:

если (a + b > "XYZ"), то

Это " анализирует " просто отлично (выражение слева, строковая константа справа). Судя по этому, мы не знаем, является ли это правильным выражением или нет. Мы не знаем, является ли " a " или "b" ссылки на строки или числа в этой точке. Итак, это то, что парсер не может решить для нас, не может пометить как ошибку, поскольку он просто не знает. Это произойдет, когда мы вычислим (выполняем или пытаемся скомпилировать в код) оператор IF.

Если бы мы сделали:

if [a > б) затем

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

Итак, суть в том, что когда вы получаете полное дерево разбора, у вас есть некоторая уверенность в том, что сначала вырежьте "код выглядит хорошо". Теперь во время выполнения могут возникать другие ошибки.

Чтобы оценить дерево разбора, вам нужно просто пройтись по дереву. У вас будет некоторый код, связанный с основными узлами дерева разбора во время компиляции или оценки. Давайте предположим, что у нас есть переводчик. 

public void execute_if_statment(ParseTreeNode node) {
    // We already know we have a IF_STATEMENT node
    Value value = evaluate_expression(node.getBooleanExpression());
    if (value.getBooleanResult() == true) {
        // we do the "then" part of the code
    }
}

public Value evaluate_expression(ParseTreeNode node) {
    Value result = null;
    if (node.isConstant()) {
        result = evaluate_constant(node);
        return result;
    }
    if (node.isIdentifier()) {
        result = lookupIdentifier(node);
        return result;
    }
    Value leftSide = evaluate_expression(node.getLeftSide());
    Value rightSide = evaluate_expression(node.getRightSide());
    if (node.getOperator() == '+') {
        if (!leftSide.isNumber() || !rightSide.isNumber()) {
            throw new RuntimeError("Must have numbers for adding");
        }
        int l = leftSide.getIntValue();
        int r = rightSide.getIntValue();
        int sum = l + r;
        return new Value(sum);
    }
    if (node.getOperator() == '>') {
        if (leftSide.getType() != rightSide.getType()) {
            throw new RuntimeError("You can only compare values of the same type");
        }
        if (leftSide.isNumber()) {
            int l = leftSide.getIntValue();
            int r = rightSide.getIntValue();
            boolean greater = l > r;
            return new Value(greater);
        } else {
            // do string compare instead
        }
    }
}

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

Что произойдет, так это execute_if_statement оценит его основное выражение. Несмотря на то, что мы хотели только BOOLEAN_EXPRESION при разборе, все выражения в большинстве случаев одинаковы для наших целей. Таким образом, execute_if_statement вызывает expression_expression.

В нашей системе все выражения имеют оператор, а также левую и правую стороны. Каждая сторона выражения также является выражением, так что вы можете видеть, как мы сразу же пытаемся оценить их, чтобы получить их реальную ценность. Следует отметить, что если выражение состоит из CONSTANT, то мы просто возвращаем значение константы, если это идентификатор, мы рассматриваем его как переменную (и это было бы хорошим местом для выброса " я не могу найти переменную 'a' " сообщение), иначе мы вернемся

Другие советы

Я бы порекомендовал antlr.org для информации и «бесплатный» инструмент, который я бы использовал для любого парсера.

GOLD можно использовать для любого приложения, где вам необходимо применять контекстно-свободные грамматики для ввода.

разработка:

По сути, CFG применимы ко всем языкам программирования.Итак, если вы хотите разработать скриптовый язык для своей компании, вам нужно будет написать синтаксический анализатор - или получить программу синтаксического анализа.В качестве альтернативы, если вы хотите иметь полуестественный язык для ввода для непрограммистов в компании, вы могли бы использовать синтаксический анализатор для чтения этих входных данных и выдачи большего количества "машиночитаемых" данных.По сути, контекстно-свободная грамматика позволяет вам описывать гораздо больше входных данных, чем регулярное выражение.Система GOLD, по-видимому, несколько упрощает задачу синтаксического анализа, чем lex / yacc (стандартные программы UNIX для синтаксического анализа).

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top