Здравствуйте.
Пишу курсовик, в котором надо реализовать детерминированный автомат с магазинной памятью (ДМПА) и не пойму, как он работает (даже на бумаге).
Пусть у меня есть язык к примеру такой:
num := [0-9]+
op := [+-*/]
id := [a-z_][a-z0-9_]*
stmt := stmt op stmt
stmt := ( stmt )
stmt := id | num
prog := id [=] stmt
Для начала я не пойму, как составить граф состояний исходя из обычной грамматики.
Во вторых, не понимаю, как он будет сворачивать магазин в узлы, если доступен только верхний узел - то есть к примеру "stmt op stmt" будет разбито на несколько состояний, к примеру так:
"-> если stmt -> (2) -> если op -> (3) -> если stmt -> успех, сворачиваем"
и после этого в магазин запихивается новый stmt? Или как это должно выглядеть правильно?
Если сделать его регэкспами или просто как конечный автомат, то я все сделал, все работает.
Насколько я понимаю, этот автомат выдает в результате одну лексему - prog, то есть выполняет 2 фазы компиляции - превращение строки в лексемы и превращение всех лексем в синтаксические элементы, свернутые в нужном порядке, в отличие от тех-же регэкспов, которые выдают только лексемы, а уже в следующей фазе происходит сворачивание лексем в синтаксические узлы.
Или хотя-бы в книжку ткните меня, куда лучше читать. Сейчас штудирую компиляторы Ахо, Лайма и прочих и Введение в теорию автоматов и вычислений хопкрофта, но все равно как-то туго идет.
Простой
