1

I read the context free grammar of JSON(http://www.json.org/) and the parser: how to parse a JSON text to produce an object or array(https://github.com/douglascrockford/JSON-js/blob/master/json_parse_state.js).

But I don't know how to convert JSON cfg to state machine.

Anyone can describe in more detail?

zhao6
  • 11
  • 2
  • Can you tell us what the plan is you are trying to achieve when you compiled it? Maybe somebody has a alternative. – Randy Sep 11 '16 at 10:47
  • 2
    What "state machine" do you need? Notice that JSON cannot be described by a DFA. – Bergi Sep 11 '16 at 11:37
  • But the [lib](https://github.com/douglascrockford/JSON-js/blob/master/json_parse_state.js) indeed use a state machine. How dit it do that? Use a bottom up parser? I sitll can't get the state machine. – zhao6 Sep 13 '16 at 15:01

1 Answers1

3

You can't build a state machine that "parses" json, because state machines technically cannot match nested parentheses.

You can build a push-down automaton (PDA), using a stack to track the parentheses. If you do that by hand, you'll be building something like an LR(0) parser. If you are going to do that, it is easier to use an LALR parser generator which will take the grammar and build the PDA for you.

You can also write your own recursive descent parser by "compiling" the grammar rules in a recognizer. For JSON, this is a pretty reasonable thing to do; the langauge isn't that complicated. See my SO answer on how to build a recursive descent parser.

Community
  • 1
  • 1
Ira Baxter
  • 93,541
  • 22
  • 172
  • 341
  • But the lib(https://github.com/douglascrockford/JSON-js/blob/master/json_parse_state.js) indeed use a state machine. Have you readed the source code? Is It a bottom up parser? – zhao6 Sep 13 '16 at 14:53
  • You can implement a PDA with an FSA and a stack. I haven't looked at the code. I'll bet there's a stack to keep track of nested constructs. – Ira Baxter Sep 14 '16 at 05:36