最新消息:XAMPP默认安装之后是很不安全的,我们只需要点击左方菜单的 "安全"选项,按照向导操作即可完成安全设置。

编译原理练手之撸个Json Parser

XAMPP下载 admin 717浏览 0评论

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

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

2.解析器 parser

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

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

1)如果下一个token不是},

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

匹配一个key,再匹配一个:,再匹配一个value

回到1)处继续判断

否则,匹配一个}

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

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

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

 

 

最后的工作便是搞个门面类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]”));
  7. String str = “{\n” +
  8. ” \”code\”: 0,\n” +
  9. ” \”msg\”: \”成功\”,\n” +
  10. ” \”data\”: [\n” +
  11. ” {\n” +
  12. ” \”name\”: \”热榜\”,\n” +
  13. ” \”type\”: 1,\n” +
  14. ” \”foods\”: [\n” +
  15. ” {\n” +
  16. ” \”id\”: \”123456\”,\n” +
  17. ” \”name\”: \”皮蛋粥\”,\n” +
  18. ” \”price\”: 1.2,\n” +
  19. ” \”description\”: \”好吃的皮蛋粥\”,\n” +
  20. ” \”icon\”: \”http://xxx.com\”,\n” +
  21. ” }\n” +
  22. ” ]\n” +
  23. ” },\n” +
  24. ” {\n” +
  25. ” \”name\”: \”好吃的\”,\n” +
  26. ” \”type\”: 2,\n” +
  27. ” \”foods\”: [\n” +
  28. ” {\n” +
  29. ” \”id\”: \”123457\”,\n” +
  30. ” \”name\”: \”慕斯蛋糕\”,\n” +
  31. ” \”price\”: 10.9,\n” +
  32. ” \”description\”: \”美味爽口\”,\n” +
  33. ” \”icon\”: \”http://xxx.com\”,\n” +
  34. ” }\n” +
  35. ” ]\n” +
  36. ” }\n” +
  37. ” ]\n” +
  38. “}”;
  39. FFJsonObject ffJsonObject = FFJson.parseObject(str);
  40. System.out.println(ffJsonObject);
  41. System.out.println(ffJsonObject.getJsonArray(“data”).getJsonObject(0).getJsonArray(“foods”).getJsonObject(0).getString(“description”));
  42. }
  43. }

其输出为:

  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

您必须 登录 才能发表评论!