现在的位置: 首页 > 综合 > 正文

自制编译器：词法分析器

2019年05月27日 ⁄ 综合 ⁄ 共 10078字 ⁄ 字号 小 中 大 ⁄ 评论关闭

词法分析器代码已上传到个人资源中。

当我们的程序源文件进入编译器，首先遇到的就是词法分析器。

词法分析器的作用就是解析源文件，分析出其中的词素，并把这个词素的顺序集输入给语法分析器。

接上篇把所谓的词素也就是终结符号列出来：

if else while ( ) { } cpreop bitop logiop armtcop number literal id NUL new [ ] basetype class private public static return break continue . this

其中cprop包括 > < >= <= == != 即比较运算符

bitop 为位运算符，包括<< >> & | ^

logiop 逻辑运算符 包括 && ||

armtcop 算数运算符 包括 + - * /

number 数字常量 例如12345整形火 1.2345小数

id 标识符 按java规则

literal 字符串常量 如"ROgerwong"

NUL 空串

basetype 基本类型 包括 int char double 三种

当然，为了简单，在这里并不打算讨论非确定有穷自动机和确定有穷自动机的理论以及其之间的转换算法，只是用最朴素的方法，不断的将字符读入缓冲区，然后和这些词素进行比较，然后把这个词素加入到一个ArrayList中。

按着这个方法定义几个数据结构：

定义词素数据结构，共含两个域，1个表示类型，一个表示具体的值，类型的取值也已经标出。

[java] view
plaincopy

  1. <p>package ravaComplier.lexer;</p><p>public class Lexeme {  
  2.  public int type;  
  3.  public Object value;  
  4.  public Lexeme(int t,Object v)  
  5.  {  
  6.   type=t;  
  7.   value=v;  
  8.  }  
  9.  @Override  
  10.  public String toString()  
  11.  {  
  12.   return new String("<"+type+":"+value.toString()+">");  
  13.  }  
  14.    
  15.  public static int IF=0;//if  
  16.  public static int ELSE=1;//else  
  17.  public static int WHILE=2;//while  
  18.  public static int BRACKET=3;//各种括号  
  19.  public static int CPREOP=4;//比较符号  
  20.  public static int BITOP=5;//位操作符  
  21.  public static int LOGIOP=6;//逻辑运算符  
  22.  public static int ARMTOP=7;//算术运算符  
  23.  public static int NUMBER=8;//立即数  
  24.  public static int LITERAL=9;//字符串  
  25.  public static int ID=10;//id  
  26.  public static int NUL=11;//空  
  27.  public static int NEW=12;//new 操作符  
  28.  public static int BASETYPE=13;//基本数据类型  
  29.  public static int CLASS=14;//关键字class  
  30.  public static int ACCESSFLAG=15;//public 或者private  
  31.  public static int STATIC=16;//关键字static  
  32.  public static int RETURN=17;//关键字return  
  33.  public static int BREAK=18;//break  
  34.  public static int CONTINUE=19;//continue  
  35.  public static int DOT=20;//.  
  36.  public static int THIS=21;//关键字this  
  37.  public static int SEMI=22;//分号  
  38.  public static int EQUAL=23;//等号  
  39. }  
  40. </p>  

其次，因为是用朴素的笨办法，所以我们需要构造规则：

定义分隔符：空格、制表符、换行符、+、-、*、/、.、；、各种括号运算符等。

若遇到分隔符，则分隔符前面的缓冲区为一个词素，分隔符为一个词素（空格、制表符、换行符）除外。

但注意特殊情况，若遇到>和>=，&和&& 之类的，需要多向前看一个字符来确定词素。

然后再把分割出的词素实例化成Lexeme类型，并加入到返回结果中。

代码很简单，但写起来比较费事：

[java] view
plaincopy

  1.   
[java] view
plaincopy

  1. package ravaComplier.lexer;  
  2.   
  3. import java.io.*;  
  4. import java.util.*;  
  5.   
  6. public class Lexer {  
  7.     private static ArrayList<Lexeme> result;//返回的结果  
  8.     private static BufferedReader br;  
  9.     private static StringBuffer buffer;//缓冲区  
  10.   
  11.     public static ArrayList<Lexeme> getLexerOutput(InputStream is)  
  12.     {  
  13.         result=new ArrayList<Lexeme>();  
  14.         br=new BufferedReader(new InputStreamReader(is));  
  15.         buffer=new StringBuffer();  
  16.         while(Read())  
  17.         {  
  18.             addLexeme();  
  19.         }  
  20.         return result;  
  21.     }  
  22.     //尝试将缓冲区分解出词素并加入词素集合  
  23.     private static void addLexeme()  
  24.     {  
  25.         String str=buffer.toString();  
  26.         String endstr=str.substring(str.length()-1,str.length());  
  27.         //判断单字符的分割符号  
  28.         if(endstr.equals(" ") || endstr.equals("\t")  || endstr.equals(";") || endstr.equals("{") || endstr.equals("}") || endstr.equals("(") || endstr.equals(")") || endstr.equals("[") || endstr.equals("]") || endstr.equals("+") || endstr.equals("-") || endstr.equals("*") || endstr.equals("/") )  
  29.         {  
  30.             Lexeme lex=getLexeme(str.substring(0,str.length()-1));  
  31.             if(lex!=null)  
  32.             {  
  33.                 result.add(lex);  
  34.             }  
  35.             lex=getLexeme(endstr);  
  36.             if(lex!=null)  
  37.             {  
  38.                 result.add(lex);  
  39.             }  
  40.               
  41.             buffer=new StringBuffer();  
  42.         }  
  43.         //判断双字符的分割符号  
  44.         if(str.length()>=2)  
  45.         {  
  46.             endstr=str.substring(str.length()-2,str.length());  
  47.             if(endstr.equals(">=") ||endstr.equals("<=") ||endstr.equals("==") || endstr.equals("||") ||endstr.equals("&&") || endstr.equals("!=") ||endstr.equals("\r\n"))  
  48.             {  
  49.                 Lexeme lex=getLexeme(str.substring(0,str.length()-2));  
  50.                 if(lex!=null)  
  51.                 {  
  52.                     result.add(lex);  
  53.                 }  
  54.                 lex=getLexeme(endstr);  
  55.                 if(lex!=null)  
  56.                 {  
  57.                     result.add(lex);  
  58.                 }  
  59.                   
  60.                 buffer=new StringBuffer();  
  61.             }  
  62.             else if(endstr.charAt(0)=='=' || endstr.charAt(0)=='>' || endstr.charAt(0)=='<' || endstr.charAt(0)=='&' || endstr.charAt(0)=='|' )  
  63.             {  
  64.                 Lexeme lex=getLexeme(str.substring(0,str.length()-2));  
  65.                 if(lex!=null)  
  66.                 {  
  67.                     result.add(lex);  
  68.                 }  
  69.                 lex=getLexeme(endstr.substring(0,1));  
  70.                 if(lex!=null)  
  71.                 {  
  72.                     result.add(lex);  
  73.                 }  
  74.                   
  75.                 buffer=new StringBuffer();  
  76.                 buffer.append(endstr.charAt(1));  
  77.             }  
  78.         }  
  79.     }  
  80.     //根据一个字符串获取词素  
  81.     private static Lexeme getLexeme(String lex)  
  82.     {  
  83.         Lexeme result=null;  
  84.         if(lex.equals(" ") || lex.equals("\t") || lex.equals("\r\n") || lex==null|| lex.length()==0)  
  85.         {  
  86.             return null;  
  87.         }  
  88.         if(lex.equals("if"))  
  89.         {  
  90.             result=new Lexeme(Lexeme.IF,lex);  
  91.         }  
  92.         else if(lex.equals("else"))  
  93.         {  
  94.             result=new Lexeme(Lexeme.ELSE,lex);  
  95.         }  
  96.         else if(lex.equals("while"))  
  97.         {  
  98.             result=new Lexeme(Lexeme.WHILE,lex);  
  99.         }  
  100.         else if(lex.equals("{") || lex.equals("}")|| lex.equals("[") || lex.equals("]") || lex.equals("(") || lex.equals(")"))  
  101.         {  
  102.             result=new Lexeme(Lexeme.BRACKET,lex);  
  103.         }  
  104.         else if(lex.equals(">") || lex.equals("<") || lex.equals("==") || lex.equals(">=") || lex.equals("<=") || lex.equals("!="))  
  105.         {  
  106.             result=new Lexeme(Lexeme.CPREOP,lex);  
  107.         }  
  108.         else if(lex.equals("&") || lex.equals("|") || lex.equals("^"))  
  109.         {  
  110.             result=new Lexeme(Lexeme.BITOP,lex);  
  111.         }  
  112.         else if(lex.equals("&&") || lex.equals("||"))  
  113.         {  
  114.             result=new Lexeme(Lexeme.LOGIOP,lex);  
  115.         }  
  116.         else if(lex.equals("+") || lex.equals("-") || lex.equals("*") || lex.equals("/"))  
  117.         {  
  118.             result=new Lexeme(Lexeme.ARMTOP,lex);  
  119.         }  
  120.         else if(isNumber(lex))  
  121.         {  
  122.             result=new Lexeme(Lexeme.NUMBER,lex);  
  123.         }  
  124.         else if(isStr(lex))  
  125.         {  
  126.             result=new Lexeme(Lexeme.LITERAL,lex);  
  127.         }  
  128.         else if(lex.equals("new"))  
  129.         {  
  130.             result=new Lexeme(Lexeme.NEW,lex);  
  131.         }  
  132.         else if(lex.equals("int") || lex.equals("char") || lex.equals("double"))  
  133.         {  
  134.             result=new Lexeme(Lexeme.BASETYPE,lex);  
  135.         }  
  136.         else if(lex.equals("class"))  
  137.         {  
  138.             result=new Lexeme(Lexeme.CLASS,lex);  
  139.         }  
  140.         else if(lex.equals("private") || lex.equals("public"))  
  141.         {  
  142.             result=new Lexeme(Lexeme.ACCESSFLAG,lex);  
  143.         }  
  144.         else if(lex.equals("static"))  
  145.         {  
  146.             result=new Lexeme(Lexeme.STATIC,lex);  
  147.         }  
  148.         else if(lex.equals("return"))  
  149.         {  
  150.             result=new Lexeme(Lexeme.RETURN,lex);  
  151.         }  
  152.         else if(lex.equals("break"))  
  153.         {  
  154.             result=new Lexeme(Lexeme.BREAK,lex);  
  155.         }  
  156.         else if(lex.equals("continue"))  
  157.         {  
  158.             result=new Lexeme(Lexeme.CONTINUE,lex);  
  159.         }  
  160.         else if(lex.equals("."))  
  161.         {  
  162.             result=new Lexeme(Lexeme.DOT,lex);  
  163.         }  
  164.         else if(lex.equals("this"))  
  165.         {  
  166.             result=new Lexeme(Lexeme.THIS,lex);  
  167.         }  
  168.         else if(lex.equals(";"))  
  169.         {  
  170.             result=new Lexeme(Lexeme.SEMI,lex);  
  171.         }  
  172.         else if(lex.equals("="))  
  173.         {  
  174.             result=new Lexeme(Lexeme.EQUAL,lex);  
  175.         }  
  176.         else  
  177.         {  
  178.             result=new Lexeme(Lexeme.ID,lex);  
  179.         }  
  180.         return result;  
  181.     }  
  182.     private static boolean isStr(String lex)  
  183.     {  
  184.         if(lex.charAt(0)!='\"' || lex.charAt(lex.length()-1)!='\"')  
  185.             return false;  
  186.         for(int i=1;i<=lex.length()-2;i++)  
  187.         {  
  188.             if(lex.charAt(i)=='\"')  
  189.             {  
  190.                 return false;  
  191.             }  
  192.         }  
  193.         return true;  
  194.     }  
  195.     private static boolean isNumber(String str)  
  196.     {  
  197.         try  
  198.         {  
  199.             int i=Integer.valueOf(str);  
  200.             return true;  
  201.         }  
  202.         catch(Exception e)  
  203.         {}  
  204.         try  
  205.         {  
  206.             double j=Double.valueOf(str);  
  207.             return true;  
  208.         }  
  209.         catch(Exception e)  
  210.         {}  
  211.         return false;  
  212.     }  
  213.     //从流中读取一个字符  
  214.     private static boolean Read()  
  215.     {  
  216.         int d;  
  217.         try {  
  218.             d = br.read();  
  219.             if(d==-1)  
  220.             {  
  221.                 return false;  
  222.             }  
  223.             buffer.append((char)d);  
  224.         } catch (IOException e) {  
  225.             e.printStackTrace();  
  226.             return false;  
  227.         }  
  228.           
  229.           
  230.         return true;  
  231.     }  
  232. }  


然后自己写一段程序，试一试能不能正确的解析：

[java] view
plaincopy

  1. class testclass{  
  2.    private static int j=0;  
  3.    public int i=1;  
  4.    public testclass()  
  5.   {  
  6.      double c=1;  
  7.      char[] d="123456";  
  8.         
  9.   }  
  10.   private static double func1()  
  11.   {  
  12.      if(j==0)  
  13.      {  
  14.      return 1.5  
  15.      }  
  16.      else  
  17.      {  
  18.        while(i<=10)  
  19.        {  
  20.          i=i+1;  
  21.        }  
  22.        return i;  
  23.      }    
  24.    }  
  25. }  


然后看一看输出的结果：

[java] view
plaincopy

  1. <14:class>  
  2. <10:testclass>  
  3. <3:{>  
  4. <15:private>  
  5. <16:static>  
  6. <13:int>  
  7. <10:j>  
  8. <23:=>  
  9. <8:0>  
  10. <22:;>  
  11. <15:public>  
  12. <13:int>  
  13. <10:i>  
  14. <23:=>  
  15. <8:1>  
  16. <22:;>  
  17. <15:public>  
  18. <10:testclass>  
  19. <3:(>  
  20. <3:)>  
  21. <3:{>  
  22. <13:double>  
  23. <10:c>  
  24. <23:=>  
  25. <8:1>  
  26. <22:;>  
  27. <13:char>  
  28. <3:[>  
  29. <3:]>  
  30. <10:d>  
  31. <23:=>  
  32. <9:"123456">  
  33. <22:;>  
  34. <3:}>  
  35. <15:private>  
  36. <16:static>  
  37. <13:double>  
  38. <10:func1>  
  39. <3:(>  
  40. <3:)>  
  41. <3:{>  
  42. <0:if>  
  43. <3:(>  
  44. <10:j>  
  45. <4:==>  
  46. <8:0>  
  47. <3:)>  
  48. <3:{>  
  49. <17:return>  
  50. <8:1.5>  
  51. <3:}>  
  52. <1:else>  
  53. <3:{>  
  54. <2:while>  
  55. <3:(>  
  56. <10:i>  
  57. <4:<=>  
  58. <8:10>  
  59. <3:)>  
  60. <3:{>  
  61. <10:i>  
  62. <23:=>  
  63. <10:i>  
  64. <7:+>  
  65. <8:1>  
  66. <22:;>  
  67. <3:}>  
  68. <17:return>  
  69. <10:i>  
  70. <22:;>  
  71. <3:}>  
  72. <3:}>  
  73. <3:}>  


貌似比较正确

返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞