Разделитель, Сравнение, Типы токенов оператора

Из "Принципы, методы и инструменты компиляторов, 2-е изд." ("Фиолетовая книга") Ахо, Лама, Сетхи и Уллмана:

Рисунок 3.2: Примеры токенов Стр. 112

[Token]       [Informal Description]                  [Sample Lexemes]
if            characters i, f                         if
else          characters e, l, s, e                   else
comparison    < or > or <= or >= or == or !=          <=, !=
id            letter followed by letters and digits   pi, score, D2
number        any numeric constant                    3.14159, 0, 6.02e23
literal       anything but ", surrounded by "'s       "core dumped"

Выше они разделяют if а также else в свои собственные типы токенов. В большинстве примеров, которые я видел, это будет один keyword тип токена и значения токенов будут if или же else, В чем преимущество наличия отдельных типов токенов для каждого ключевого слова, а не keyword тип токена?

В чем преимущество наличия токенов типа comparison? Почему бы не иметь тип токена для каждого вида сравнения, подобного следующему?

[Token]       [Informal Description]                  [Sample Lexemes]
lt            <                                       <
gt            >                                       >
lte           <=                                      <=
gte           >=                                      >=
eq            ==                                      ==
neq           !=                                      !=
Источник

2 ответа

Решение

Различные мнения о том, как отдельные операторы представлены, когда операторы синтаксически идентичны. Многие люди пишут отдельные произведения для разных операторов, даже если нет реальной синтаксической разницы и семантическая разница ограничена.

Сказав это, есть языки, на которых ==, >= а также <= синтаксически различны. В C (и его семействе) приоритет этих операторов отличается, что позволяет записать a <= b == b <= c без скобок, хотя код, содержащий это выражение, вряд ли выдержит проверку кода. (Даже с круглыми скобками выражение сомнительно.) В Python a <= b <= c является действительным каскадным сравнением, но a <= b >= c не является. И т.п.

Общее правило заключается в том, что если токен играет особую роль в синтаксисе языка, различие должно быть видимым для синтаксического анализатора, и синтаксический анализатор учитывает только тип токена, а не его значение. По этой причине, if, then а также else должны быть разные типы токенов в любой практической грамматике.

Источник

Зачем использовать разные типы токенов для ключевых слов

При написании парсера вы обычно switch по типу токена. Если тип токена недостаточен для принятия решения, это означает, что вам также необходимо проверить значение токена внутри case, Если значение токена представлено в виде строки, сравнение также будет более затратным (даже если строка является интернированной, последовательность if-else-if все равно будет менее эффективной, чем ключ). Во многих генераторах синтаксических анализаторов принятие решений на основе значения токена либо невозможно, либо сложнее, чем просто использование типа токена.

Чтобы проиллюстрировать это, вот отрывок рукописного парсера, в котором разные ключевые слова имеют разные типы токенов:

parse_statement() {
  switch(current_token.type) {
    case IF:
      parse_if_statement(); break;
    case WHILE:
      parse_while_statement(); break;
    //...
    case ID: case NUMBER: case LITERAL:
      parse_expression_statement(); break;
    default:
      syntax_error(); break;
  }
}

И тот же код, где это не так:

parse_statement() {
  switch(current_token.type) {
    case KEYWORD:
      if (current_token.value == "if") {
        parse_if_statement();
      } else if (current_token.value == "while") {
        parse_while_statement();
      // '}  else if(...) {'s for other valid keywords go here
      } else {
        syntax_error();
      }
    // Other statement types that don't start with a keyword go here
    case ID: case NUMBER: case LITERAL:
      parse_expression_statement(); break;
    default:
      syntax_error(); break;
  }
}

Обратите внимание на дополнительное вложение и что теперь есть два места, где syntax_error называется.

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

statement
  : IF condition body (ELSE body)?
  | WHILE condition body
  | ... | expression ';' ;

Или вот так, если был только тип ключевого слова:

statement
  : if condition body (else body)?
  | while condition body
  | ... | expression ';' ;

if: {current_token.value == "if"} KEYWORD ;
else: {current_token.value == "else"} KEYWORD ;
while: {current_token.value == "while"} KEYWORD ;

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

Зачем использовать один и тот же тип токена для операторов сравнения

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

comparison_exp: additive_exp COMPARISON additive_exp ;

И с отдельными типами:

comparison_exp: additive_exp comparison additive_exp ;
comparison: LT | GT | LTE | GTE | EQ | NEQ;

Поэтому, если у вас есть только один тип токена, вам не нужно прописывать все параметры в грамматике.

По сравнению с первым вопросом, это более незначительная и субъективная вещь.

Источник
Другие вопросы по тегам