diff options
author | thebusytypist <ounanding@gmail.com> | 2014-07-19 09:12:13 +0400 |
---|---|---|
committer | thebusytypist <ounanding@gmail.com> | 2014-07-19 09:12:13 +0400 |
commit | 5b549f1dce72308ac3e00525ce1897d9b99df6f1 (patch) | |
tree | 0a2e8a6f4fcc6925f91632d2140dfb75b62912b2 | |
parent | 03ecc2e4f8ca419c1df7dd1f111a83500a18e493 (diff) |
Elaborate the construction of state machine; add states diagram.
-rw-r--r-- | doc/diagram/iterative-parser-states-diagram.dot | 37 | ||||
-rw-r--r-- | doc/diagram/iterative-parser-states-diagram.png | bin | 0 -> 175899 bytes | |||
-rw-r--r-- | doc/internals.md | 8 |
3 files changed, 44 insertions, 1 deletions
diff --git a/doc/diagram/iterative-parser-states-diagram.dot b/doc/diagram/iterative-parser-states-diagram.dot new file mode 100644 index 00000000..57daa0db --- /dev/null +++ b/doc/diagram/iterative-parser-states-diagram.dot @@ -0,0 +1,37 @@ +digraph { + splines=true; + node [shape = doublecircle]; Start; Finish; + node [shape = circle]; + + Start -> ArrayInitial [label="["]; + Start -> ObjectInitial [label="{"]; + + ObjectInitial -> ObjectFinish [label="}"]; + ObjectInitial -> MemberKey [label="string"]; + + MemberKey -> KeyValueDelimiter [label=":"]; + + KeyValueDelimiter -> ArrayInitial [label="[ (push MemberValue)"]; + KeyValueDelimiter -> ObjectInitial [label="{ (push MemberValue)"]; + KeyValueDelimiter -> MemberValue [label="string|false|true|null|number"]; + + MemberValue -> ObjectFinish [label="}"]; + MemberValue -> MemberDelimiter [label=","]; + + MemberDelimiter -> MemberKey [label="string"]; + + ArrayInitial -> ArrayInitial [label="[ (push Element)"]; + ArrayInitial -> ArrayFinish [label="]"]; + ArrayInitial -> ObjectInitial [label="{ (push Element)"]; + ArrayInitial -> Element [label="string|flase|true|null|number"]; + + Element -> ArrayFinish [label="]"]; + Element -> ElementDelimiter [label=","]; + + ElementDelimiter -> ArrayInitial [label="[ (push Element)"]; + ElementDelimiter -> ObjectInitial [label="{ (push Element)"]; + ElementDelimiter -> Element [label="string|false|true|null|number"]; + + ArrayFinish -> Finish; + ObjectFinish -> Finish; +} diff --git a/doc/diagram/iterative-parser-states-diagram.png b/doc/diagram/iterative-parser-states-diagram.png Binary files differnew file mode 100644 index 00000000..d209514a --- /dev/null +++ b/doc/diagram/iterative-parser-states-diagram.png diff --git a/doc/internals.md b/doc/internals.md index 85fcf338..fd68b1f2 100644 --- a/doc/internals.md +++ b/doc/internals.md @@ -112,10 +112,16 @@ while generating a production could work. In RapidJSON, several modifications(or adaptations to current design) are made to a direct implementation. First, the parsing table is encoded in a state machine in RapidJSON. -Extra states are added for productions involved with `array` and `object`. +States are constructed by the head and body of production. +State transitions are constructed by production rules. +Besides, extra states are added for productions involved with `array` and `object`. In this way the generation of array values or object members would be a single state transition, rather than several pop/push operations in the direct implementation. This also makes the estimation of stack size more easier. +The final states diagram is shown below: + +![States Diagram](diagram/iterative-parser-states-diagram.png) + Second, the iterative parser also keeps track of array's value count and object's member count in its internal stack, which may be different from a conventional implementation. |