Home > Archive > AWK > March 2008 > Can awk easily simulate an AFSM
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
Can awk easily simulate an AFSM
|
|
| problems@gmail 2008-03-16, 10:01 pm |
| Hi,
I've just looked at awk's docos for the first time and it seems
suitable for implememting an augumented-finite-state-machine.
Imagine those syntax-diagrams for pascal from the 70s - like
railway-maps, where the tracks loop around/back from
different stations/nodes.
Now stretch it out down the left side of the page, so that
the nodes are all below each other on separate lines, where the
action corresponding to the node/token is listed on the line.
The main track is going down, and any loop-back tracks are
going up behind/to-the-left-of the main-track.
At each/most node there's an action to be performed.
Some nodes are not terminals/leaves and just lead to
another nested syntax-diagram via push & return via pop.
I've built several p-code compilers like this.
From what I see from awks docos, it's very suitable for
doing the [token,action] task, as the source-code is
scanned into tokens and passed to awk.
As I remember, at the branch-points a one token look ahead
only was needed for the pascal-like syntax.
Can awk handle this ?
How would it handle the branching, eg. the sub-diagram for
statement would be like:
Case TOKEN
'IF': next state := IF-node;
'WHILE: next state := WHILE-node;
....
Of course FSMs are also very usefull for eg. ppp implementation,
because the spec. is even given as a FSM .........
==crg.
| |
| Jürgen Kahrs 2008-03-16, 10:01 pm |
| problems@gmail schrieb:
> I've just looked at awk's docos for the first time and it seems
> suitable for implememting an augumented-finite-state-machine.
Right.
> At each/most node there's an action to be performed.
> Some nodes are not terminals/leaves and just lead to
> another nested syntax-diagram via push & return via pop.
What you describe is a recursive-descent compiler.
Terminals are consumed by the scanner.
Non-terminals are handled by a dedicated function.
> I've built several p-code compilers like this.
Me too, with AWK.
> From what I see from awks docos, it's very suitable for
> doing the [token,action] task, as the source-code is
> scanned into tokens and passed to awk.
Right, but remember that the traditional distinction
between a low-level "scanner" (with regular expressions)
and a high-level "parser" (doing recursive-descent parsing)
should be made.
> As I remember, at the branch-points a one token look ahead
> only was needed for the pascal-like syntax.
Yes, it was called the LL(1). Wirth always designed
his languages so that they can be parsed with a
lookahead of one symbol.
> Can awk handle this ?
>
> How would it handle the branching, eg. the sub-diagram for
> statement would be like:
> Case TOKEN
> 'IF': next state := IF-node;
> 'WHILE: next state := WHILE-node;
> ...
I have implemented a compiler for PL/0 and I
did it this way:
http://en.wikipedia.org/wiki/PL/0
function Statement( m, n) {
if (EatSym("ident", -1)) {
n = FindIdent(tokenprev, "variable")
EatSym(":=", 14)
Expression()
Encode(0xb3, n, 2)
} else if (EatSym("CALL", -1)) {
EatSym("ident", 12)
Encode(0xb8, FindIdent(tokenprev, "procedure"), 2)
} else if (EatSym("BEGIN", -1)) {
do { Statement() } while (EatSym(";", -1))
EatSym("END", 9)
} else if (EatSym("IF", -1)) {
Condition()
EatSym("THEN", 10)
n = pc
Encode(0xa0, 0, 2)
Statement()
PatchAddr(n, pc)
} else if (EatSym("WHILE", -1)) {
n = pc
Condition()
EatSym("DO", 1)
m = pc
Encode(0xa0, 0, 2)
Statement()
Encode(0xa7, n-pc, 2) # goto
PatchAddr(m, pc)
}
}
| |
| Janis Papanagnou 2008-03-18, 3:58 am |
| Jürgen Kahrs wrote:
> problems@gmail schrieb:
>
>
> Yes, it was called the LL(1). Wirth always designed
> his languages so that they can be parsed with a
> lookahead of one symbol.
Not sure what you are referring to when saying "it" (since that is a
parser type I assume the one that Wirth predominantly used? - as done
in his little booklet about compiler construction), but note that a
(more powerful) LR(1) parser has also a lookahead of one (and can be
used to parse a larger set of grammers than with the LL(1) parsers).
The LL(1) grammar allows to use a primitive recursive descent parser;
that was primarily the simplifying part of the approach, not so much
the lookahead per se.
Janis
|
|
|
|
|