Skip to content

Instantly share code, notes, and snippets.

@DmitrySoshnikov
Last active December 16, 2015 09:01
Show Gist options
  • Save DmitrySoshnikov/80751a7179ac8e0ff2d9 to your computer and use it in GitHub Desktop.
Save DmitrySoshnikov/80751a7179ac8e0ff2d9 to your computer and use it in GitHub Desktop.
{
"lex": {
"macros": {
"digit": "[0-9]",
"esc": "\\\\",
"int": "-?(?:[0-9]|[1-9][0-9]+)",
"exp": "(?:[eE][-+]?[0-9]+)",
"frac": "(?:\\.[0-9]+)"
},
"rules": [
["\\s+", "/* skip whitespace */"],
["{int}{frac}?{exp}?\\b", "return 'NUMBER';"],
["\"(?:{esc}[\"bfnrt/{esc}]|{esc}u[a-fA-F0-9]{4}|[^\"{esc}])*\"", "return 'STRING';"],
["\\{", "return '{'"],
["\\}", "return '}'"],
["\\[", "return '['"],
["\\]", "return ']'"],
[",", "return ','"],
[":", "return ':'"],
["true\\b", "return 'TRUE'"],
["false\\b", "return 'FALSE'"],
["null\\b", "return 'NULL'"]
]
},
"tokens": "STRING NUMBER { } [ ] , : TRUE FALSE NULL",
"start": "JSONText",
"bnf": {
"JSONString": [ "STRING" ],
"JSONNullLiteral": [ "NULL" ],
"JSONNumber": [ "NUMBER" ],
"JSONBooleanLiteral": [ "TRUE", "FALSE" ],
"JSONText": [ "JSONValue" ],
"JSONValue": [ "JSONNullLiteral",
"JSONBooleanLiteral",
"JSONString",
"JSONNumber",
"JSONObject",
"JSONArray" ],
"JSONObject": [ "{ }",
"{ JSONMemberList }" ],
"JSONMember": [ "JSONString : JSONValue" ],
"JSONMemberList": [ "JSONMember",
"JSONMemberList , JSONMember" ],
"JSONArray": [ "[ ]",
"[ JSONElementList ]" ],
"JSONElementList": [ "JSONValue",
"JSONElementList , JSONValue" ]
}
}
Parsing mode: SLR1.
Canonical collection of LR items:
State 0
- JSONText' -> • JSONText (kernel, goes to state 9)
- JSONText -> • JSONValue (goes to state 10)
- JSONValue -> • JSONNullLiteral (goes to state 11)
- JSONNullLiteral -> • NULL (goes to state 12)
- JSONValue -> • JSONBooleanLiteral (goes to state 13)
- JSONBooleanLiteral -> • TRUE (goes to state 14)
- JSONBooleanLiteral -> • FALSE (goes to state 15)
- JSONValue -> • JSONString (goes to state 16)
- JSONString -> • STRING (goes to state 17)
- JSONValue -> • JSONNumber (goes to state 18)
- JSONNumber -> • NUMBER (goes to state 19)
- JSONValue -> • JSONObject (goes to state 20)
- JSONObject -> • { } (goes to state 1)
- JSONObject -> • { JSONMemberList } (goes to state 1)
- JSONValue -> • JSONArray (goes to state 21)
- JSONArray -> • [ ] (goes to state 2)
- JSONArray -> • [ JSONElementList ] (goes to state 2)
State 1
- JSONObject -> { • } (kernel, goes to state 22)
- JSONObject -> { • JSONMemberList } (kernel, goes to state 3)
- JSONMemberList -> • JSONMember (goes to state 23)
- JSONMember -> • JSONString : JSONValue (goes to state 4)
- JSONString -> • STRING (goes to state 17)
- JSONMemberList -> • JSONMemberList , JSONMember (goes to state 3)
State 2
- JSONArray -> [ • ] (kernel, goes to state 27)
- JSONArray -> [ • JSONElementList ] (kernel, goes to state 7)
- JSONElementList -> • JSONValue (goes to state 28)
- JSONValue -> • JSONNullLiteral (goes to state 11)
- JSONNullLiteral -> • NULL (goes to state 12)
- JSONValue -> • JSONBooleanLiteral (goes to state 13)
- JSONBooleanLiteral -> • TRUE (goes to state 14)
- JSONBooleanLiteral -> • FALSE (goes to state 15)
- JSONValue -> • JSONString (goes to state 16)
- JSONString -> • STRING (goes to state 17)
- JSONValue -> • JSONNumber (goes to state 18)
- JSONNumber -> • NUMBER (goes to state 19)
- JSONValue -> • JSONObject (goes to state 20)
- JSONObject -> • { } (goes to state 1)
- JSONObject -> • { JSONMemberList } (goes to state 1)
- JSONValue -> • JSONArray (goes to state 21)
- JSONArray -> • [ ] (goes to state 2)
- JSONArray -> • [ JSONElementList ] (goes to state 2)
- JSONElementList -> • JSONElementList , JSONValue (goes to state 7)
State 3
- JSONObject -> { JSONMemberList • } (kernel, goes to state 24)
- JSONMemberList -> JSONMemberList • , JSONMember (kernel, goes to state 5)
State 4
- JSONMember -> JSONString • : JSONValue (kernel, goes to state 6)
State 5
- JSONMemberList -> JSONMemberList , • JSONMember (kernel, goes to state 25)
- JSONMember -> • JSONString : JSONValue (goes to state 4)
- JSONString -> • STRING (goes to state 17)
State 6
- JSONMember -> JSONString : • JSONValue (kernel, goes to state 26)
- JSONValue -> • JSONNullLiteral (goes to state 11)
- JSONNullLiteral -> • NULL (goes to state 12)
- JSONValue -> • JSONBooleanLiteral (goes to state 13)
- JSONBooleanLiteral -> • TRUE (goes to state 14)
- JSONBooleanLiteral -> • FALSE (goes to state 15)
- JSONValue -> • JSONString (goes to state 16)
- JSONString -> • STRING (goes to state 17)
- JSONValue -> • JSONNumber (goes to state 18)
- JSONNumber -> • NUMBER (goes to state 19)
- JSONValue -> • JSONObject (goes to state 20)
- JSONObject -> • { } (goes to state 1)
- JSONObject -> • { JSONMemberList } (goes to state 1)
- JSONValue -> • JSONArray (goes to state 21)
- JSONArray -> • [ ] (goes to state 2)
- JSONArray -> • [ JSONElementList ] (goes to state 2)
State 7
- JSONArray -> [ JSONElementList • ] (kernel, goes to state 29)
- JSONElementList -> JSONElementList • , JSONValue (kernel, goes to state 8)
State 8
- JSONElementList -> JSONElementList , • JSONValue (kernel, goes to state 30)
- JSONValue -> • JSONNullLiteral (goes to state 11)
- JSONNullLiteral -> • NULL (goes to state 12)
- JSONValue -> • JSONBooleanLiteral (goes to state 13)
- JSONBooleanLiteral -> • TRUE (goes to state 14)
- JSONBooleanLiteral -> • FALSE (goes to state 15)
- JSONValue -> • JSONString (goes to state 16)
- JSONString -> • STRING (goes to state 17)
- JSONValue -> • JSONNumber (goes to state 18)
- JSONNumber -> • NUMBER (goes to state 19)
- JSONValue -> • JSONObject (goes to state 20)
- JSONObject -> • { } (goes to state 1)
- JSONObject -> • { JSONMemberList } (goes to state 1)
- JSONValue -> • JSONArray (goes to state 21)
- JSONArray -> • [ ] (goes to state 2)
- JSONArray -> • [ JSONElementList ] (goes to state 2)
State 9 (final, accept)
- JSONText' -> JSONText • (kernel, accept)
State 10 (final)
- JSONText -> JSONValue • (kernel, reduce by production 6)
State 11 (final)
- JSONValue -> JSONNullLiteral • (kernel, reduce by production 7)
State 12 (final)
- JSONNullLiteral -> NULL • (kernel, reduce by production 2)
State 13 (final)
- JSONValue -> JSONBooleanLiteral • (kernel, reduce by production 8)
State 14 (final)
- JSONBooleanLiteral -> TRUE • (kernel, reduce by production 4)
State 15 (final)
- JSONBooleanLiteral -> FALSE • (kernel, reduce by production 5)
State 16 (final)
- JSONValue -> JSONString • (kernel, reduce by production 9)
State 17 (final)
- JSONString -> STRING • (kernel, reduce by production 1)
State 18 (final)
- JSONValue -> JSONNumber • (kernel, reduce by production 10)
State 19 (final)
- JSONNumber -> NUMBER • (kernel, reduce by production 3)
State 20 (final)
- JSONValue -> JSONObject • (kernel, reduce by production 11)
State 21 (final)
- JSONValue -> JSONArray • (kernel, reduce by production 12)
State 22 (final)
- JSONObject -> { } • (kernel, reduce by production 13)
State 23 (final)
- JSONMemberList -> JSONMember • (kernel, reduce by production 16)
State 24 (final)
- JSONObject -> { JSONMemberList } • (kernel, reduce by production 14)
State 25 (final)
- JSONMemberList -> JSONMemberList , JSONMember • (kernel, reduce by production 17)
State 26 (final)
- JSONMember -> JSONString : JSONValue • (kernel, reduce by production 15)
State 27 (final)
- JSONArray -> [ ] • (kernel, reduce by production 18)
State 28 (final)
- JSONElementList -> JSONValue • (kernel, reduce by production 20)
State 29 (final)
- JSONArray -> [ JSONElementList ] • (kernel, reduce by production 19)
State 30 (final)
- JSONElementList -> JSONElementList , JSONValue • (kernel, reduce by production 21)
Grammar:
0. JSONText' -> JSONText
--------------------------
1. JSONString -> STRING
2. JSONNullLiteral -> NULL
3. JSONNumber -> NUMBER
4. JSONBooleanLiteral -> TRUE
5. | FALSE
6. JSONText -> JSONValue
7. JSONValue -> JSONNullLiteral
8. | JSONBooleanLiteral
9. | JSONString
10. | JSONNumber
11. | JSONObject
12. | JSONArray
13. JSONObject -> { }
14. | { JSONMemberList }
15. JSONMember -> JSONString : JSONValue
16. JSONMemberList -> JSONMember
17. | JSONMemberList , JSONMember
18. JSONArray -> [ ]
19. | [ JSONElementList ]
20. JSONElementList -> JSONValue
21. | JSONElementList , JSONValue
SLR(1) parsing table:
┌────┬────────┬────────┬────┬─────┬────┬─────┬─────┬────┬──────┬───────┬──────┬─────┬────────────┬─────────────────┬────────────┬────────────────────┬──────────┬───────────┬────────────┬────────────┬────────────────┬───────────┬─────────────────┐
│ │ STRING │ NUMBER │ { │ } │ [ │ ] │ , │ : │ TRUE │ FALSE │ NULL │ $ │ JSONString │ JSONNullLiteral │ JSONNumber │ JSONBooleanLiteral │ JSONText │ JSONValue │ JSONObject │ JSONMember │ JSONMemberList │ JSONArray │ JSONElementList │
├────┼────────┼────────┼────┼─────┼────┼─────┼─────┼────┼──────┼───────┼──────┼─────┼────────────┼─────────────────┼────────────┼────────────────────┼──────────┼───────────┼────────────┼────────────┼────────────────┼───────────┼─────────────────┤
│ 0 │ s17 │ s19 │ s1 │ │ s2 │ │ │ │ s14 │ s15 │ s12 │ │ 16 │ 11 │ 18 │ 13 │ 9 │ 10 │ 20 │ │ │ 21 │ │
├────┼────────┼────────┼────┼─────┼────┼─────┼─────┼────┼──────┼───────┼──────┼─────┼────────────┼─────────────────┼────────────┼────────────────────┼──────────┼───────────┼────────────┼────────────┼────────────────┼───────────┼─────────────────┤
│ 1 │ s17 │ │ │ s22 │ │ │ │ │ │ │ │ │ 4 │ │ │ │ │ │ │ 23 │ 3 │ │ │
├────┼────────┼────────┼────┼─────┼────┼─────┼─────┼────┼──────┼───────┼──────┼─────┼────────────┼─────────────────┼────────────┼────────────────────┼──────────┼───────────┼────────────┼────────────┼────────────────┼───────────┼─────────────────┤
│ 2 │ s17 │ s19 │ s1 │ │ s2 │ s27 │ │ │ s14 │ s15 │ s12 │ │ 16 │ 11 │ 18 │ 13 │ │ 28 │ 20 │ │ │ 21 │ 7 │
├────┼────────┼────────┼────┼─────┼────┼─────┼─────┼────┼──────┼───────┼──────┼─────┼────────────┼─────────────────┼────────────┼────────────────────┼──────────┼───────────┼────────────┼────────────┼────────────────┼───────────┼─────────────────┤
│ 3 │ │ │ │ s24 │ │ │ s5 │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │
├────┼────────┼────────┼────┼─────┼────┼─────┼─────┼────┼──────┼───────┼──────┼─────┼────────────┼─────────────────┼────────────┼────────────────────┼──────────┼───────────┼────────────┼────────────┼────────────────┼───────────┼─────────────────┤
│ 4 │ │ │ │ │ │ │ │ s6 │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │
├────┼────────┼────────┼────┼─────┼────┼─────┼─────┼────┼──────┼───────┼──────┼─────┼────────────┼─────────────────┼────────────┼────────────────────┼──────────┼───────────┼────────────┼────────────┼────────────────┼───────────┼─────────────────┤
│ 5 │ s17 │ │ │ │ │ │ │ │ │ │ │ │ 4 │ │ │ │ │ │ │ 25 │ │ │ │
├────┼────────┼────────┼────┼─────┼────┼─────┼─────┼────┼──────┼───────┼──────┼─────┼────────────┼─────────────────┼────────────┼────────────────────┼──────────┼───────────┼────────────┼────────────┼────────────────┼───────────┼─────────────────┤
│ 6 │ s17 │ s19 │ s1 │ │ s2 │ │ │ │ s14 │ s15 │ s12 │ │ 16 │ 11 │ 18 │ 13 │ │ 26 │ 20 │ │ │ 21 │ │
├────┼────────┼────────┼────┼─────┼────┼─────┼─────┼────┼──────┼───────┼──────┼─────┼────────────┼─────────────────┼────────────┼────────────────────┼──────────┼───────────┼────────────┼────────────┼────────────────┼───────────┼─────────────────┤
│ 7 │ │ │ │ │ │ s29 │ s8 │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │
├────┼────────┼────────┼────┼─────┼────┼─────┼─────┼────┼──────┼───────┼──────┼─────┼────────────┼─────────────────┼────────────┼────────────────────┼──────────┼───────────┼────────────┼────────────┼────────────────┼───────────┼─────────────────┤
│ 8 │ s17 │ s19 │ s1 │ │ s2 │ │ │ │ s14 │ s15 │ s12 │ │ 16 │ 11 │ 18 │ 13 │ │ 30 │ 20 │ │ │ 21 │ │
├────┼────────┼────────┼────┼─────┼────┼─────┼─────┼────┼──────┼───────┼──────┼─────┼────────────┼─────────────────┼────────────┼────────────────────┼──────────┼───────────┼────────────┼────────────┼────────────────┼───────────┼─────────────────┤
│ 9 │ │ │ │ │ │ │ │ │ │ │ │ acc │ │ │ │ │ │ │ │ │ │ │ │
├────┼────────┼────────┼────┼─────┼────┼─────┼─────┼────┼──────┼───────┼──────┼─────┼────────────┼─────────────────┼────────────┼────────────────────┼──────────┼───────────┼────────────┼────────────┼────────────────┼───────────┼─────────────────┤
│ 10 │ │ │ │ │ │ │ │ │ │ │ │ r6 │ │ │ │ │ │ │ │ │ │ │ │
├────┼────────┼────────┼────┼─────┼────┼─────┼─────┼────┼──────┼───────┼──────┼─────┼────────────┼─────────────────┼────────────┼────────────────────┼──────────┼───────────┼────────────┼────────────┼────────────────┼───────────┼─────────────────┤
│ 11 │ │ │ │ r7 │ │ r7 │ r7 │ │ │ │ │ r7 │ │ │ │ │ │ │ │ │ │ │ │
├────┼────────┼────────┼────┼─────┼────┼─────┼─────┼────┼──────┼───────┼──────┼─────┼────────────┼─────────────────┼────────────┼────────────────────┼──────────┼───────────┼────────────┼────────────┼────────────────┼───────────┼─────────────────┤
│ 12 │ │ │ │ r2 │ │ r2 │ r2 │ │ │ │ │ r2 │ │ │ │ │ │ │ │ │ │ │ │
├────┼────────┼────────┼────┼─────┼────┼─────┼─────┼────┼──────┼───────┼──────┼─────┼────────────┼─────────────────┼────────────┼────────────────────┼──────────┼───────────┼────────────┼────────────┼────────────────┼───────────┼─────────────────┤
│ 13 │ │ │ │ r8 │ │ r8 │ r8 │ │ │ │ │ r8 │ │ │ │ │ │ │ │ │ │ │ │
├────┼────────┼────────┼────┼─────┼────┼─────┼─────┼────┼──────┼───────┼──────┼─────┼────────────┼─────────────────┼────────────┼────────────────────┼──────────┼───────────┼────────────┼────────────┼────────────────┼───────────┼─────────────────┤
│ 14 │ │ │ │ r4 │ │ r4 │ r4 │ │ │ │ │ r4 │ │ │ │ │ │ │ │ │ │ │ │
├────┼────────┼────────┼────┼─────┼────┼─────┼─────┼────┼──────┼───────┼──────┼─────┼────────────┼─────────────────┼────────────┼────────────────────┼──────────┼───────────┼────────────┼────────────┼────────────────┼───────────┼─────────────────┤
│ 15 │ │ │ │ r5 │ │ r5 │ r5 │ │ │ │ │ r5 │ │ │ │ │ │ │ │ │ │ │ │
├────┼────────┼────────┼────┼─────┼────┼─────┼─────┼────┼──────┼───────┼──────┼─────┼────────────┼─────────────────┼────────────┼────────────────────┼──────────┼───────────┼────────────┼────────────┼────────────────┼───────────┼─────────────────┤
│ 16 │ │ │ │ r9 │ │ r9 │ r9 │ │ │ │ │ r9 │ │ │ │ │ │ │ │ │ │ │ │
├────┼────────┼────────┼────┼─────┼────┼─────┼─────┼────┼──────┼───────┼──────┼─────┼────────────┼─────────────────┼────────────┼────────────────────┼──────────┼───────────┼────────────┼────────────┼────────────────┼───────────┼─────────────────┤
│ 17 │ │ │ │ r1 │ │ r1 │ r1 │ r1 │ │ │ │ r1 │ │ │ │ │ │ │ │ │ │ │ │
├────┼────────┼────────┼────┼─────┼────┼─────┼─────┼────┼──────┼───────┼──────┼─────┼────────────┼─────────────────┼────────────┼────────────────────┼──────────┼───────────┼────────────┼────────────┼────────────────┼───────────┼─────────────────┤
│ 18 │ │ │ │ r10 │ │ r10 │ r10 │ │ │ │ │ r10 │ │ │ │ │ │ │ │ │ │ │ │
├────┼────────┼────────┼────┼─────┼────┼─────┼─────┼────┼──────┼───────┼──────┼─────┼────────────┼─────────────────┼────────────┼────────────────────┼──────────┼───────────┼────────────┼────────────┼────────────────┼───────────┼─────────────────┤
│ 19 │ │ │ │ r3 │ │ r3 │ r3 │ │ │ │ │ r3 │ │ │ │ │ │ │ │ │ │ │ │
├────┼────────┼────────┼────┼─────┼────┼─────┼─────┼────┼──────┼───────┼──────┼─────┼────────────┼─────────────────┼────────────┼────────────────────┼──────────┼───────────┼────────────┼────────────┼────────────────┼───────────┼─────────────────┤
│ 20 │ │ │ │ r11 │ │ r11 │ r11 │ │ │ │ │ r11 │ │ │ │ │ │ │ │ │ │ │ │
├────┼────────┼────────┼────┼─────┼────┼─────┼─────┼────┼──────┼───────┼──────┼─────┼────────────┼─────────────────┼────────────┼────────────────────┼──────────┼───────────┼────────────┼────────────┼────────────────┼───────────┼─────────────────┤
│ 21 │ │ │ │ r12 │ │ r12 │ r12 │ │ │ │ │ r12 │ │ │ │ │ │ │ │ │ │ │ │
├────┼────────┼────────┼────┼─────┼────┼─────┼─────┼────┼──────┼───────┼──────┼─────┼────────────┼─────────────────┼────────────┼────────────────────┼──────────┼───────────┼────────────┼────────────┼────────────────┼───────────┼─────────────────┤
│ 22 │ │ │ │ r13 │ │ r13 │ r13 │ │ │ │ │ r13 │ │ │ │ │ │ │ │ │ │ │ │
├────┼────────┼────────┼────┼─────┼────┼─────┼─────┼────┼──────┼───────┼──────┼─────┼────────────┼─────────────────┼────────────┼────────────────────┼──────────┼───────────┼────────────┼────────────┼────────────────┼───────────┼─────────────────┤
│ 23 │ │ │ │ r16 │ │ │ r16 │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │
├────┼────────┼────────┼────┼─────┼────┼─────┼─────┼────┼──────┼───────┼──────┼─────┼────────────┼─────────────────┼────────────┼────────────────────┼──────────┼───────────┼────────────┼────────────┼────────────────┼───────────┼─────────────────┤
│ 24 │ │ │ │ r14 │ │ r14 │ r14 │ │ │ │ │ r14 │ │ │ │ │ │ │ │ │ │ │ │
├────┼────────┼────────┼────┼─────┼────┼─────┼─────┼────┼──────┼───────┼──────┼─────┼────────────┼─────────────────┼────────────┼────────────────────┼──────────┼───────────┼────────────┼────────────┼────────────────┼───────────┼─────────────────┤
│ 25 │ │ │ │ r17 │ │ │ r17 │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │
├────┼────────┼────────┼────┼─────┼────┼─────┼─────┼────┼──────┼───────┼──────┼─────┼────────────┼─────────────────┼────────────┼────────────────────┼──────────┼───────────┼────────────┼────────────┼────────────────┼───────────┼─────────────────┤
│ 26 │ │ │ │ r15 │ │ │ r15 │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │
├────┼────────┼────────┼────┼─────┼────┼─────┼─────┼────┼──────┼───────┼──────┼─────┼────────────┼─────────────────┼────────────┼────────────────────┼──────────┼───────────┼────────────┼────────────┼────────────────┼───────────┼─────────────────┤
│ 27 │ │ │ │ r18 │ │ r18 │ r18 │ │ │ │ │ r18 │ │ │ │ │ │ │ │ │ │ │ │
├────┼────────┼────────┼────┼─────┼────┼─────┼─────┼────┼──────┼───────┼──────┼─────┼────────────┼─────────────────┼────────────┼────────────────────┼──────────┼───────────┼────────────┼────────────┼────────────────┼───────────┼─────────────────┤
│ 28 │ │ │ │ │ │ r20 │ r20 │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │
├────┼────────┼────────┼────┼─────┼────┼─────┼─────┼────┼──────┼───────┼──────┼─────┼────────────┼─────────────────┼────────────┼────────────────────┼──────────┼───────────┼────────────┼────────────┼────────────────┼───────────┼─────────────────┤
│ 29 │ │ │ │ r19 │ │ r19 │ r19 │ │ │ │ │ r19 │ │ │ │ │ │ │ │ │ │ │ │
├────┼────────┼────────┼────┼─────┼────┼─────┼─────┼────┼──────┼───────┼──────┼─────┼────────────┼─────────────────┼────────────┼────────────────────┼──────────┼───────────┼────────────┼────────────┼────────────────┼───────────┼─────────────────┤
│ 30 │ │ │ │ │ │ r21 │ r21 │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │
└────┴────────┴────────┴────┴─────┴────┴─────┴─────┴────┴──────┴───────┴──────┴─────┴────────────┴─────────────────┴────────────┴────────────────────┴──────────┴───────────┴────────────┴────────────┴────────────────┴───────────┴─────────────────┘
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment