Построение лексера в C

Question

Я хочу построить лексер в C, и я слежу за книгой драконов , я могу понять переходы состояний, но как их реализовать?

Есть ли лучшая книга?

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

Answer 1

Вы можете реализовать простые переходы состояний с помощью одной переменной состояния, например, если вы хотите циклически переключаться между состояниями start-> part1-> part2-> end, вы можете использовать enum для отслеживания текущего состояния и оператор switch для кода, который вы хотите запустить в каждом состоянии.

enum state { start=1, part1, part2, end} mystate;

// ...
mystate = start;
do {
  switch (mystate) {
    case start:
      // ...
    case part1:
      // ...
    case part2:
      // ...
      if (part2_end_condition) mystate = end; // state++ will also work
      // Note you could also set the state back to part1 on some condition here
      // which creates a loop
      break;
  }
} while (mystate != end);

Для более сложных переходов состояний, которые зависят от нескольких переменных, вы должны использовать таблицы / массивы следующим образом:

var1    var2    var_end    next_state
0       0       0          state1
0       1       0          state2
1       0       0          state3
1       1       0          state4
-1      -1      1          state_end // -1 represents "doesn't matter" here

Answer 2

G'day,

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

Сама страница довольно мала, но содержит ссылки на различные превосходные ресурсы по лексическим анализаторам.

НТН

ура

Answer 3

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

// regular expression
digit* [.digit*]

и соответствующий код C будет:

// corresponding code
while(DIGIT(*pc)) pc++;
if (*pc=='.'){
    pc++;
    while(DIGIT(*pc)) pc++;
}

Способ построения лексеров в таблице переходов, на мой взгляд, излишне сложен и, очевидно, работает медленнее.

Answer 4

Если вы ищете более современное лечение, чем книги о драконах: Эндрю У. Аппель и Майя Гинзбург, Modern Реализация компилятора в C , Cambridge University Press, 2008.

Глава 2 посвящена лексическому анализу: лексические токены, регулярные выражения, конечные автоматы; Недетерминированные конечные автоматы; Генераторы лексического анализатора

Посмотрите на Содержание

Answer 5

Программа flex (клон lex) создаст для вас лексер.

Учитывая входной файл с правилами лексера, он создаст файл C с реализацией лексера для этих правил.

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