A
A
alex_ak12016-02-05 15:04:24
Parsing
alex_ak1, 2016-02-05 15:04:24

How is token parsing implemented through DMPA?

Hello.
I am writing a term paper in which it is necessary to implement a deterministic push-pull automaton (DMPA) and I don’t understand how it works (even on paper).
Let me have a language like this:
num := [0-9]+
op := [+-*/]
id := [a-z_][a-z0-9_]*
stmt := stmt op stmt
stmt := ( stmt )
stmt := id | num
prog := id [=] stmt
To begin with, I don't understand how to construct a state graph based on the usual grammar.
Secondly, I don’t understand how it will collapse the store into nodes if only the top node is available - that is, for example, "stmt op stmt" will be broken into several states, for example like this:
"-> if stmt -> (2) - > if op -> (3) -> if stmt -> success, collapse"
and after that a new stmt is pushed into the store? Or how it should look right?
If you make it regexps or just as a state machine, then I did everything, everything works.
As far as I understand, this automaton produces as a result one token - prog, that is, it performs 2 phases of compilation - turning a string into tokens and turning all tokens into syntactic elements, folded in the right order, unlike the same regexps that give out only tokens , and already in the next phase, the lexemes are folded into syntactic nodes.
Or at least poke me into a book, where it is better to read. Now I'm studying the compilers of Aho, Lime and others and Hopcroft's Introduction to the Theory of Automata and Computation, but it's still somehow tight.

Answer the question

In order to leave comments, you need to log in

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question