Recursive Descent Parsers

From Progzoo
Revision as of 14:53, 7 March 2011 by Andr3w (Talk | contribs) (JSON Data Format)

Jump to: navigation, search

A Recursive Descent Parser takes a stream of tokens and builds a syntax tree.

JSON Data Format

As an example we will take the JSON data format. This is simple, but it does have the recursive structure that shows off the technique. JSON is used to represent data. There are two primitive type: string and number.

  • "one"
  • 123

There are lists For example:

  • [123, "one" ]

There are hash arrays For example:

  • {num:123, str: "one" }

You can have a list inside a list of course:

  • [1, 2, [3, 4]]

Similarly you can have a hash array of lists, and in JavaScript you can mix types:

  • {a:1, b:[1,2,3], c:{x:2}}

Production Rules

N -> number
N -> [ N Z ]
N -> { word : N Y }
Z -> , N Z
Z -> ε
Y -> , word : N Y
Y -> ε