Создание лексера на C

Question

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

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

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

Answer 1

Добрый день,

Предполагая, что вы имеете в виду книгу «Дракон» по проектированию компилятора, я бы рекомендовал осмотреться. эта страница об инструментах компилятора.

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

ХТХ

ваше здоровье,

Answer 2

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

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 3

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

// regular expression
digit* [.digit*]

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

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

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

Answer 4

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

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

Посмотрите на Оглавление

Answer 5

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

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

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