编译原理练手之撸个Json Parser

手撸个python目标还是太遥远，先从简单的json解析器开始。捣鼓了半天，似乎是ok了，现总结一下。

1.Lexer 分词器

分词器的目标是将输入的String token化，定义了以下Token种类

1. public enum FFToken {
2. Comma,Colon,LBracket,RBracket,LBrace,RBrace,Str,Number,EOF;
3. }

分词器的实现核心便是一个状态机，当一个token被识别时，便将识别出的token返回给上层调用者：parser。

分词器需要一个peek功能，即偷瞄一下下一个token，这里面我采取的是回退机制，即token获取后，parser可以调用lexer的pushBackToken方法，将token退回去；这样下次getToken时，便还是返回这个token。

分词器的代码如下：

1. public class FFLexer {
3. private String str;
5. private int pos_start;
7. private int pos_end;
9. private int last_pos_start;
11. private int last_pos_end;
13. private State state;
15. private boolean bEscape;
17. private boolean dotted;
19. private String value;
20. enum State{
21. Start,
22. InNumber,
23. InStr
24. }
26. public FFLexer(String str){
27. this.str = str;
28. this.pos_start = 0;
29. this.pos_end = 0;
30. this.last_pos_start = 0;
31. this.last_pos_end = 0;
32. this.state = State.Start;
33. this.bEscape = false;
34. this.dotted = false;
35. }
37. public FFToken getToken() throws FFParseException{
38. this.last_pos_start = this.pos_start;
39. this.last_pos_end = this.pos_end;
40. FFToken token = null;
41. while(token == null){
42. if(this.pos_start == this.str.length()){
43. return FFToken.EOF;
44. }
45. this.pos_end ++;
46. boolean ended = false;
47. if(this.pos_end > this.str.length()){
48. ended = true;
49. }
50. char c = ”;
51. if(!ended){
52. c = endChar();
53. }
54. switch (this.state){
55. case Start:
56. if(c == ‘{‘){
57. token = FFToken.LBrace;
58. }else if(c == ‘}’){
59. token = FFToken.RBrace;
60. }else if(c == ‘[‘){
61. token = FFToken.LBracket;
62. }else if(c == ‘]’){
63. token = FFToken.RBracket;
64. }else if(c == ‘,’){
65. token = FFToken.Comma;
66. }else if(c == ‘:’){
67. token = FFToken.Colon;
68. }else if(c == ‘”‘){
69. state = State.InStr;
70. this.pos_start += 1;
71. }else if(Character.isDigit(c)){
72. state = State.InNumber;
73. }else if(c == ‘ ‘|| c==’\t’||c==’\n’||c==’\r’){
74. this.pos_start += 1;
75. }else{
76. throw new FFParseException();
77. }
78. break;
79. case InStr:
80. if(ended){
81. throw new FFParseException();
82. }
83. if(c == ‘”‘){
84. if(!bEscape){
85. value = this.str.substring(this.pos_start,this.pos_end – 1);
86. token = FFToken.Str;
87. this.state = State.Start;
88. }else{
89. this.bEscape = false;
90. }
91. }else{
92. if(c == ‘\\’){
93. this.bEscape = true;
94. }
95. }
96. break;
97. case InNumber:
98. if(ended){
99. throw new FFParseException();
100. }
101. if(Character.isDigit(c)){
102. }else if(endChar() == ‘.’){
103. if(this.dotted){
104. value = this.str.substring(this.pos_start,this.pos_end – 1);
105. token = FFToken.Number;
106. this.dotted = false;
107. this.state = State.Start;
108. this.pos_end –;
109. }else{
110. this.dotted = true;
111. }
112. }else{
113. value = this.str.substring(this.pos_start,this.pos_end – 1);
114. token = FFToken.Number;
115. this.dotted = false;
116. this.state = State.Start;
117. this.pos_end –;
118. }
119. break;
120. }
121. }
122. this.pos_start = this.pos_end;
123. return token;
124. }
126. public void pushBackToken(){
127. this.pos_start = this.last_pos_start;
128. this.pos_end = this.last_pos_end;
129. }
131. public String processedStr(){
132. return this.str.substring(0,this.pos_end );
133. }
135. private char endChar(){
136. return this.str.charAt(this.pos_end – 1);
137. }
139. public String getValue(){
140. return this.value;
141. }
142. }

可见dirty work是挺多的，调了我好久才总算看上去灵光。

2.解析器 parser

parser的实现核心便是函数递归调用，如要解析一个JsonObject,那么

我们首先需要获得一个{，

1）如果下一个token不是}，

如果不是第一次匹配，需匹配一个逗号,

匹配一个key，再匹配一个：，再匹配一个value

回到1）处继续判断

否则，匹配一个}

JsonArray的匹配思路也是一样的。

当然，光解析不够，我们还得将转换后的结果保存、返回，这很类似编译器里面的代码生成。

1. public class FFParser {
3. private FFLexer ffLexer;
5. public FFParser(String str){
6. ffLexer = new FFLexer(str);
7. }
8. public FFJsonObject parseJsonObject() throws FFParseException{
9. return jsonObject();
10. }
12. public FFJsonArray parseJsonArray() throws FFParseException{
13. return jsonArray();
14. }
16. private FFJsonObject jsonObject() throws FFParseException{
17. FFJsonObject ffJsonObject = new FFJsonObject();
18. match(FFToken.LBrace);
19. FFToken token;
20. token = ffLexer.getToken();
21. ffLexer.pushBackToken();
22. if(token != FFToken.RBrace){
23. Object key = key();
24. match(FFToken.Colon);
25. Object value = value();
26. ffJsonObject.put(key,value);
27. }
28. do{
29. token = ffLexer.getToken();
30. if(token == FFToken.Comma){
31. token = ffLexer.getToken();
32. ffLexer.pushBackToken();
33. if(token != FFToken.RBrace ){
34. Object key = key();
35. match(FFToken.Colon);
36. Object value = value();
37. ffJsonObject.put(key,value);
38. token = ffLexer.getToken();
39. ffLexer.pushBackToken();
40. }
41. }else{
42. ffLexer.pushBackToken();
43. }
44. }while (token != FFToken.RBrace && token != FFToken.EOF);
45. match(FFToken.RBrace);
46. return ffJsonObject;
47. }
49. private FFJsonArray jsonArray() throws FFParseException{
50. FFJsonArray ffJsonArray = new FFJsonArray();
51. match(FFToken.LBracket);
52. FFToken token;
53. token = ffLexer.getToken();
54. ffLexer.pushBackToken();
55. if(token != FFToken.RBracket){
56. Object value = value();
57. ffJsonArray.add(value);
58. }
59. do{
60. token = ffLexer.getToken();
61. if(token == FFToken.Comma){
62. token = ffLexer.getToken();
63. ffLexer.pushBackToken();
64. if(token != FFToken.RBracket ) {
65. Object value = value();
66. ffJsonArray.add(value);
67. token = ffLexer.getToken();
68. ffLexer.pushBackToken();
69. }
70. }else{
71. ffLexer.pushBackToken();
72. }
73. }while (token != FFToken.RBracket && token != FFToken.EOF);
74. match(FFToken.RBracket);
75. return ffJsonArray;
76. }
78. private Object key() throws FFParseException{
79. FFToken token;
80. token = ffLexer.getToken();
81. if(token == FFToken.Str){
82. return ffLexer.getValue();
83. }else if(token == FFToken.Number){
84. return parseNumber(ffLexer.getValue());
85. }else{
86. System.err.println(token);
87. throw new FFParseException();
88. }
89. }
91. private Object value() throws FFParseException{
92. FFToken token;
93. token = ffLexer.getToken();
94. if(token == FFToken.Str){
95. return ffLexer.getValue();
96. }else if(token == FFToken.Number){
97. return parseNumber(ffLexer.getValue());
98. }else if(token == FFToken.LBrace){
99. ffLexer.pushBackToken();
100. return jsonObject();
101. }else if(token == FFToken.LBracket){
102. ffLexer.pushBackToken();;
103. return jsonArray();
104. }else{
105. throw new FFParseException();
106. }
107. }
109. private void match(FFToken expectedToken) throws FFParseException{
110. FFToken token = ffLexer.getToken();
111. if(token != expectedToken){
112. System.err.println(ffLexer.processedStr());
113. System.err.println(token);
114. System.err.println(expectedToken);
115. throw new FFParseException();
116. }
117. }
119. private Object parseNumber(String value){
120. if(value.contains(“.”)){
121. return Double.parseDouble(value);
122. }else{
123. return Long.parseLong(value);
124. }
125. }
126. }

最后的工作便是搞个门面类FFJson供外界调用了。代码就不贴在这儿了。

下面是测试结果：

1. public class App
2. {
3. public static void main( String[] args )
4. {
5. System.out.println(FFJson.parseObject(“{\”abc\”:123,\”dddd\”:[1,3,3],\”xxx\”:{\”a\”:1,\”b\”:\”a\”}}”));
6. System.out.println(FFJson.parseArray(“[1,2,3,4,5]”));
8. String str = “{\n” +
9. ” \”code\”: 0,\n” +
10. ” \”msg\”: \”成功\”,\n” +
11. ” \”data\”: [\n” +
12. ” {\n” +
13. ” \”name\”: \”热榜\”,\n” +
14. ” \”type\”: 1,\n” +
15. ” \”foods\”: [\n” +
16. ” {\n” +
17. ” \”id\”: \”123456\”,\n” +
18. ” \”name\”: \”皮蛋粥\”,\n” +
19. ” \”price\”: 1.2,\n” +
20. ” \”description\”: \”好吃的皮蛋粥\”,\n” +
21. ” \”icon\”: \”http://xxx.com\”,\n” +
22. ” }\n” +
23. ” ]\n” +
24. ” },\n” +
25. ” {\n” +
26. ” \”name\”: \”好吃的\”,\n” +
27. ” \”type\”: 2,\n” +
28. ” \”foods\”: [\n” +
29. ” {\n” +
30. ” \”id\”: \”123457\”,\n” +
31. ” \”name\”: \”慕斯蛋糕\”,\n” +
32. ” \”price\”: 10.9,\n” +
33. ” \”description\”: \”美味爽口\”,\n” +
34. ” \”icon\”: \”http://xxx.com\”,\n” +
35. ” }\n” +
36. ” ]\n” +
37. ” }\n” +
38. ” ]\n” +
39. “}”;
40. FFJsonObject ffJsonObject = FFJson.parseObject(str);
41. System.out.println(ffJsonObject);
42. System.out.println(ffJsonObject.getJsonArray(“data”).getJsonObject(0).getJsonArray(“foods”).getJsonObject(0).getString(“description”));
44. }
45. }

其输出为：

1. {“abc”:123,”xxx”:{“a”:1,”b”:”a”},”dddd”:[1,3,3]}
2. [1,2,3,4,5]
3. {“msg”:”成功”,”code”:0,”data”:[{“foods”:[{“price”:1.2,”name”:”皮蛋粥”,”icon”:”http://xxx.com”,”description”:”好吃的皮蛋粥”,”id”:”123456″}],”name”:”热榜”,”type”:1},{“foods”:[{“price”:10.9,”name”:”慕斯蛋糕”,”icon”:”http://xxx.com”,”description”:”美味爽口”,”id”:”123457″}],”name”:”好吃的”,”type”:2}]}
4. 好吃的皮蛋粥

okay，尤其那一长串的链式调用非常的有feel。

题外话：抛去隐藏bug、性能问题不谈，功能性上，一个完整的json类库还缺少与实体类的转换，不过这个不属于编译原理的范畴了，也就不造轮子了，或者等下次有闲情继续完善。

转载请注明：XAMPP中文组官网 » 编译原理练手之撸个Json Parser