Разбор действительно состоит из двух фаз. Первый - это «лексизм», который преобразует необработанные строки символов во что-то, что программа может более легко понять (обычно называемые токенами).
Простой пример: 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> "XYZ"), то
Это "хорошо разбирает" (выражение слева, строковая константа справа). Судя по этому, мы не знаем, является ли это правильным выражением или нет. Мы не знаем, ссылаются ли "a" или "b" на строки или числа в этой точке. Итак, это то, что парсер не может решить для нас, не может пометить как ошибку, поскольку он просто не знает. Это произойдет, когда мы вычислим (выполняем или пытаемся скомпилировать в код) оператор IF.
Если бы мы сделали:
если [a> b), то
Синтаксический анализатор может легко увидеть эту синтаксическую ошибку как проблему и выдаст ошибку. Эта строка токенов не похожа ни на что известное.
Итак, суть в том, что когда вы получаете полное дерево разбора, у вас есть некоторая уверенность, что сначала вырежете «код выглядит хорошо». Теперь во время выполнения могут появиться другие ошибки.
Чтобы оценить дерево разбора, вы просто гуляете по дереву. У вас будет некоторый код, связанный с основными узлами дерева разбора во время компиляции или оценки. Давайте предположим, что у нас есть переводчик.
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' "), в противном случае мы вернемся к левой / правой стороне.
Надеюсь, вы увидите, как может работать простой оценщик, если у вас есть поток токенов от анализатора. Обратите внимание, что во время оценки основные элементы языка присутствуют, в противном случае мы получили бы синтаксическую ошибку и никогда бы не добрались до этой фазы. Мы можем просто ожидать, что «узнаем», что когда у нас есть, например, оператор PLUS, у нас будет 2 выражения, левое и правое. Или когда мы выполняем оператор IF, у нас уже есть логическое выражение для оценки. Разбор это то, что делает эту тяжелую работу для нас.
Начало работы с новым языком может быть непростой задачей, но, как только вы начнете кататься, вы обнаружите, что все остальное становится довольно простым, и это почти "волшебство", что все это работает в конце.
Заметьте, простите за форматирование, но подчеркивание все портит - надеюсь, все еще понятно.