LINUX.ORG.RU

Синтаксический анализ на конечных автоматах

 ,


2

5

Добрый день!

Помогите пожалуйста разобраться с конечными автоматами. Нужно сделать разбор текста формата json. Да, знаю, есть инструменты flex и bison, которые могут делать парсеры по описанию грамматики, но мне нужно разобраться как реализовать конечный автомат на C++ без применения этих инструментов. Я нарисовал следующую диаграмму состояний: здесь. Такой автомат не может работать с вложенными конструкциями: объектами и массивами, только с последовательностью пар «name»:value.

Вопросы в следующем:

1. Допустим такой автомат будет переключаться из состояния в состояние по мере чтения символов, но как на практике можно это использовать? Была идея при переходе в нужные состояния генерировать события: например перешли в состояние ожидания кавычки, сработал обработчик и записал положение начала строки, считали другую кавычку - другой обработчик, записали конец строки. Все бы хорошо, но значения могут быть строками (в кавычках), числами и литералами (без кавычек), и не получается единообразно получать начала и концы строк. Или может нужно как-то по-другому перерисовать диаграмму? Вообще как применяются конечные автоматы на практике в плане архитектуры?

2. Я читал, что для обработки вложенных конструкций применяются Магазинные автоматы. Как можно нарисовать диаграмму такого автомата? Что должно храниться в стеке? Как реализовать в плане архитектуры такой автомат? Когда считывается фигурная скобка, по идее, нужно сохранить в стек текущее состояние. Какой состояние будет при этом у нового автомата? Init? Хорошо, а когда будет закрывающая скобка, нужно вернуть из стека прежнее состояние. А какое оно должно быть? Мы сохраняли состояние ожидания фигурной скобки. Куда дальше переходить из этого состояния? Ведь на этом уровне автомат не должен знать что там внутри скобок.

А какая должна быть архитектура? Как представить автомат? В виде класса? Что пихать в стек? В общем, много вопросов. Подскажите пожалуйста как решаются подобные задачи с конечными автоматами.


Синтаксический анализ на конечных автоматах
json

Нельзя.

invy ★★★★★ ()
Ответ на: комментарий от invy

Как можно нарисовать такую диаграмму состояний? Как при этом записать таблицу переходов? Простые конечные автоматы позволяют, по диаграмме быстро нарисовать таблицу переходов и забить ее в код и быть уверенным, что автомат перейдет в нужное состояние при таком-то событии. Все это упрощает систему. С Магазинными автоматами я не понимаю как такое сделать. Гугл выдает в основном только такие как у вас строгие математические описания. Практического примера работы такого автомата, без всех этих множеств и отображений, я не нашел.

silart ()

Продвинутая модель конечных автоматов очень подробно описана в UML.

Sorcerer ★★★★★ ()

но мне нужно разобраться как реализовать конечный автомат на C++ без применения этих инструментов.

Зачем?

1. Допустим такой автомат будет переключаться из состояния в состояние по мере чтения символов, но как на практике можно это использовать?

Это на практике используется если надо парсить всякие вложенные друг в друга конструкции. Например если нам надо распарсить штуку {x,y} где в качестве x может быть какая-то буква или {x,y} или [a,b,c] где a,b,c это какие-то числа, например [1234,5534,1234] и нам на входе такая штука

{a, {[342,55,1],{c,{[134,55,1],d}}}}
И надо уметь внутри {x,y} находить конструкции {x,y} вложенные сколько угодно раз внутрь, то надо в стеке отмечать, что вот там уровнем выше тоже находится {x,y} а под ним еще одна {x,y}, стек нужен чтобы эту информацию как-нибудь хранить.

А какая должна быть архитектура?

Эффективнее всего (в плане скорости работы) получится, если реализовывать это в виде кучи меток и if(условие) goto состояниеавтомата; т.к. будет меньше оверхеда, к тому же переписывать блоксхему в подобный код из goto очень легко.

SZT ★★★★★ ()
Ответ на: комментарий от silart

по диаграмме быстро нарисовать таблицу переходов и забить ее в код

Да их вручную набивают редко. Разве что для совсем простых автоматов. В книге с драконом вроде неплохо про все это написано. Там и теория и практика.

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

Классики предлагали использовать два типа автоматов, один для лексического анализа, второй для синтаксического. Генерируются автоматы flex-ом и bison-ом соответственно (или аналогами, вроде re2c и lemon).

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

Выход лексического анализатора идет на вход синтаксического. Тот уже анализирует синтаксис, все эти вложенности, парные скобки и прочее

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

Deleted ()

fsm удобно применять в отдельных слоях абстракций, например, когда появляется скобка или кавычка: автомат в состоянии скобка открыта, далее, если скобка еще - увеличить счетчик

вообще, на json.org опубликован алгоритм разбора, ну и примеры посмотреть известных реализаций

anonymous ()
Ответ на: комментарий от SZT

то надо в стеке отмечать

п.ж. надо использовать tail recursion and accumulator

anonymous ()
Ответ на: комментарий от Deleted

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

Автомат на рисунке поддерживает только значения без кавычек и объекты. Массивы и значения-строки я не стал рисовать чтобы не загромождать картину. Лексемы показаны в левой нижней части рисунка.

И вот что получается: этот автомат является простым конечным (без магазинной памяти). Да, там есть стек, но управление им осуществляется при попадании в состояния Push и Pop. То есть попали мы в состояние Push, сохранили токен в стек, пришел следующий символ, мы перешли в другое состояние. Само состояние автомата в стек не сохраняется. Правильно ли это?

И еще. Как быть с архитектурой? Переход в каждое состояние будет сопровождаться вызовом своей функции. Данные при этом остаются общими. Получается много состояний - много функций. Инкапсуляция при таком подходе страдает. К тому же данный метод конечных автоматов не показался мне таким уж простым. То есть чтобы поменять грамматику придется менять количество состояний, количество функций, и возможно данные. Код получится довольно муторный, логика размазана по всему коду. Стоит ли вообще использовать этот метод? Не проще будет реализовать парсер с помощью рекурсии? Там тоже логика размазана по всему коду.

silart ()
Ответ на: комментарий от silart

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

Да это идея 60-х годов прошлого века.

Лексемы показаны в левой нижней части рисунка

Обычно строки не делят на кавычку и собственно строку. Хотя, дело ваше, конечно

Непонятно, что вы хотите получить в итоге, но в любом случае лучше почитать теорию. Большинство вопросов прояснятся. Форумными постами все равно не получится пересказать книги или объемные статьи.

Попробую ответить на некоторые вопросы, но какой-то глубины в ответах не ждите.

Само состояние автомата в стек не сохраняется. Правильно ли это?

Что такое «состояние автомата»? Вообще хоть что-то должно сохраняться. Как парсить конструкции типа "a" { "b" { "c" { 0 } } }? В генераторах анализаторов обычно есть директивы для выставления максимальной глубины стека.

Переход в каждое состояние будет сопровождаться вызовом своей функции

Обычно «свои функции» вызываются только при переходе в определенные состояния

Не проще будет реализовать парсер с помощью рекурсии?

Имеется в виду метод рекурсивного спуска? Ну, в некоторых случаях он удобнее, а в некоторых не очень.

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

Deleted ()
Ответ на: комментарий от silart

Ну в табличку еще добавляются символы на стоке.

invy ★★★★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.