2

Написать программу, использующую механизм управления при помощи таблиц (управление осуществляется данными!). Нужно выделить следующие типы лексем:

  • Целое число со знаком
  • Вещественное число со знаком
  • Скобка

Ориентировочная схема работы главного цикла программы:

  1. Ввод символа из файла
  2. Переход автомата в новое состояние в зависимости от введенного символа и текущего состояния
  3. Вывод символа в выходной файл, либо другое действие (в зависимости от задания)

Перевод автомата в новое состояние (п. 2) и выбор действия для выполнения (п. 3) могут быть реализованы несколькими способами. От способа реализации зависит максимальный балл за выполнение работы: 1. Выбор действия и состояния с помощью ветвлений (if, switch) – 60% 2. Выбор состояния с помощью таблицы (массива), а действия с помощью ветвления – 80% 3. Выбор состояния и действия с помощью таблиц (для действий используются указатели на функции) – 100%

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

После ограничений пришлось удалить весь код и набросать этот: http://pastebin.ru/NlYjOVPg

Помогите разобраться, как мне полностью выделить лексему, например, несколько 123 - как целое со знаком, а не по отдельности, как 1 - целое со знаком, 2 - целое со знаком, 3 - целое со знаком.

Таблица переходов

4 ответа 4

4

@T2skler, IMHO плодотворной идеей будет сделать для каждого состояния свою таблицу переходов. Причем, ячейка таблицы представляет собой два поля: действие (указатель на функцию) и новое состояние (указатель на соответствующую таблицу).

И для полноты картины введите еще один символ -- EOF.

Тогда достаточно следующих состояний:

  • Start

  • Sign

  • Int

  • Real

и действия:

  • ERR

  • ERR_AND_BRACKET

  • BRACKET

  • INT

  • INT_AND_BRACKET

  • REAL

  • INT_AND_BRACKET

  • NONE

Например, знак в состоянии Start вызывает NONE и переход к Sign, цифра в Sign вызывает NONE и переход в Int, знак в Int вызывает INT и переход в Sign, ... знак в Sign вызывает ERR и переход опять в Sign и т.п.

Теперь о загадочных XXX_AND_BRACKET.

Очевидно, что скобка в Start вызывает BRACKET и переход в Start.

Скобка в Sign с одной стороны должна вызвать ошибку, а с другой -- это ведь просто лексема скобка. Поэтому вызовем ERR_AND_BRACKET, которая сначала вызовет ERR и затем BRACKET, а потом сразу перейдем в Start.

Похожим образом обработаем скобку в состояниях Int и Real. Только вместо ERR вызываем INT или REAL.

EOF в любом состоянии завершает программу (вероятно в состоянии Sign нужно вызвать ERR(?) или добавить действия XXX_AND_EOF, аналогичные XXX_AND_BRACKET)

Наверняка что-то упустил, но Вы уж сами додумайте... Попробуйте, думаю у Вас все получится.

7
  • Все условия продумали) Уже получилось написать код, только у меня просто добавлено новое состояние NEW_STATE. В него переходят, когда происходит было, например, число, а потом появилась скобка. Выводятся накопившиеся символы (к примеру 123) и сразу же повторно запрашивается состояние для текущего символа и обрабатывается далее.
    – Tas
    4 дек 2014 в 22:25
  • @T2skler, код на 100%? Т.е. только с таблицами и указателями на функции?
    – avp
    4 дек 2014 в 23:41
  • Нет, я не совсем понял, как это нужно реализовывать
    – Tas
    5 дек 2014 в 5:41
  • как называется состояние, когда мы находимся в середине лексемы (например, в середине числа)? Я не вижу, как можно, используя только Start, Sign, Int, Real состояния, распознать ввод, если хранить только текущее состояние (допустим, номер от 0 до 3 включительно) и последний введенный символ (один байт для простоты). Для сравнения, конечный автомат из моего ответа использует 8 состояний.
    – jfs
    16 дек 2014 в 17:49
  • В середине целого -- в состоянии Int, действительного -- Real, естественно. Дело ведь в том, что требуется только распознавать лексемы, а не получить сами числа. Скажем, все входные символы можно сразу печатать, а при распознании лексемы (или ошибки) вставлять сообщение в выходной поток. Только с балансировкой скобок при заданных условиях будут проблемы. По крайней мере сейчас (без детальной проработки) мне это так видится. -- При случае (время, желание) черкану программульку.
    – avp
    16 дек 2014 в 19:58
4

Если кол-во состояний конечно и можно запоминать только номер текущего состояния и последний введённый символ, то узнать что мы прочитали 123, а не 213 нельзя. В противном случае кол-во состояний было бы пропорционально вводу или сам ввод (или позиции в нём) необходимо отдельно хранить.

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

Например, ragel позволяет создать конечный автомат из регулярного выражения:

%%{
    machine number_fsm;

    integer = ('+' | '-')? digit+;
    float = ('+' | '-')? (digit+ ('.' digit*)? | '.' digit+)
            (('e' | 'E') ('+' | '-')? digit+)?;
    paren = '(' | ')';
    token = integer | float | paren;

    main := token**;

}%%

картинка c конечным автоматом . Чтобы получить эту картинку, необходимо сохранить вышеприведённый код в number_fsm.rl файл и выполнить команды:

$ ragel -F1 -p -V -o number_fsm.dot number_fsm.rl
$ dot -Tpng -o number_fsm.png number_fsm.dot
$ display number_fsm.png

ragel также умеет генерировать таблицы перехода для состояний и исполнять действия в любом месте на выбранном языке (например, С, Go).

12
  • @jfs: Почему же невозможно? Пусть количество состояний будет равно MAXINT :-) Для целых чисел хватит, для действительных придётся подкинуть ещё. --- Чтобы упростить программирование, можно под номер состояния выделить double.
    – VladD
    4 дек 2014 в 14:57
  • Поскольку требуется только распознавать целые, действительные числа и скобки, но не требуется выводить конкретное число (для этого потребовалась бы дополнительная переменная для сосояний INT и REAL), то число состояний резко уменьшается и задача, безусловно, решается без lex/flex/ragel и т.п. (просто сейчас лень расписывать таблицу переходов).
    – avp
    4 дек 2014 в 16:05
  • @VladD: невозможно. Кол-во натуральных чисел бесконечно. Если ограничить ввод, то все алгоритмы O(1), что не очень интересно или полезно. @avp: верно (в этом смысл 2-го параграфа в ответе). Но таблицы всё-таки лучше компьютерам оставить составлять (легче изменять регулярные выражения чем таблицы переходов, меньше ошибок).
    – jfs
    5 дек 2014 в 10:09
  • @jfs, Вы же наверняка понимаете, что задача у @T2skler, состоит не в создании рабочего лексера, а в написании учебной машины состояний (просто входные данные для нее ассоциируются с языками программирования). Если продолжить аналогии, то дана задача -- "написать вычисления по формуле ... на ассемблере", а ему все дружно в ответ -- не дури, пиши на ... (у кого какой язык любимый). Конечно, если речь идет о проекте (который предположительно еще и будет развиваться), включающим какой-либо язык (или язык не простой), то надо потратить пару неделек и освоить lex/yacc (или аналоги).
    – avp
    5 дек 2014 в 11:02
  • @jfs: Количество «натуральных» чисел MAXINT + 1, с точки зрения языка. Если брать «правильные» натуральные числа, бесконечное множество, то имея конечную память очевидно невозможно распарсить строку в такое число. (Если, конечно, нам не нужно само число, то DFA на [+|-] \d+ совсем уж тривиален.)
    – VladD
    5 дек 2014 в 11:09
2

Я года три назад писал небольшой скриптовой язык и интересовался вопросом. Как выше написал @VladD, не стоит изобретать велосипед. Проще всего воспользоваться Flex. Ему задаешь определенные правила, а на выходе он генерирует C'шный код, который уже легко встраиваешь под задачу.

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

P.S. Если не ошибаюсь он умеет и в C++.

1

Не стройте велосипед, воспользуйтесь lex/flex.

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.