编译原理

感谢vczh轮子叔的坑了的教程，我的编译原理第一次入了个门，词法分析写完了，今后可以看看书继续往下学了。

http://www.cppblog.com/vczh/archive/2014/03/02/206014.html

词法分析，就是对于一段代码，把他们分割成一个个的token，同时记录他们的行列号，丢掉不必要的信息，这个词法分析器很简单，简单的状态机就能胜任，用正则就没有自己造轮子的快感了，所以要自己手撸状态机拆token出来。

模仿vczh的语言，我的语言包括了以下要素

　　标识符：大小写字母和下划线构成的连续串[a-zA-Z_]

　　数字：自然书写的整数和浮点数，整数部分为0的浮点数必须要用0.开头

　　运算符：单个符号

　　注释：#开头，#或结尾的任意内容，也就是说注释最多是一整行

　　字符串：双引号"开头结尾的任意内容，支持\，两种转义字符。

这样简单的语言，用正则表达式处理也很简单，但是为了贯彻自己造轮子的原则，我们手写一波状态机

首先把状态机的图画出来，就像这样（因为没有钱买visio，所以只能用一个叫lucidchart的在线应用画图了）

虚线表示这个状态可以直接跳到End状态，而所谓End状态就是Start状态，所以到了有虚线的状态，可以看情况直接跳到Start，并且有些状态也可以直接优化掉，比如InStringEnd, InOperator等，遇到这样的状态，直接输出一个token，然后把state设为Start就好了。

这样的状态机是不是很简单，更加复杂的一些状态，也可以手动构造正则表达式，然后用vczh的另一篇教程手写出状态机来。

忘了说Token的结构了，这个很简单

struct Token
{
    int line;
    int column;
    TokenType type;
    std::wstring value;
    Token(): Token(0, 0, TokenType::Unknown, L"", 0)
    {
    }
    Token(int _line, int _column, TokenType _type, const wchar_t* str, int len)
        : line(_line)
        , column(_column)
        , type(_type)
        , value(str, len)
    {
    }
    void Reset()
    {
        line = 0;
        column = 0;
        type = TokenType::Unknown;
        value.clear();
    }
    void Push(const wchar_t ch)
    {
        value.push_back(ch);
    }
};

那个Reset和Push纯粹是因为我偷懒，把这个第一个版本的代码写得很烂，只能用这种不科学的封装来减少一下代码的重复了。

有了状态机和具体的状态：

enum class TokenType
{
    Unknown,
    Number,
    Comment,
    Operator,
    Identifier,
    String
};

enum class ParseState
{
    Begin,
    InComment,
    //InCommentEnd,
    InInteger,
    InFloat,
    InOperator,
    InIdentifier,
    InString,
    InStringEscaping,
    //InStringEnd
};

可以构造状态机了，模板是这样的：

while (*reading)
{
    switch (state)
    {
    case 某个状态:
    {
        switch (*reading)
        {
        case 某个或某几个字符:
            #根据状态机里当前状态能接受和不能接受的字符，修改新的状态，读入字符，reading++，或者直接抛异常
        break;
        }
    }
}

第一个版本的代码写得很烂，纯粹是能用的程序，放在这里纯粹是显摆一下，之后我会考虑重构什么的，然后再来更新这篇文章，而且没有写单元测试，正确性纯粹是肉眼检查，报错信息也很不友善，这一点下一个版本的代码再改。

更新，稍微优化了一下，重复代码少了不少，我很喜欢，还能接着改

下面贴代码：

TokenStream.h

  1 #pragma once
  2 #ifndef TOKEN_STREAM
  3 #define TOKEN_STREAM
  4 
  5 #include <string>
  6 #include <vector>
  7 enum class TokenType
  8 {
  9     Unknown,
 10     Number,
 11     Comment,
 12     Operator,
 13     Identifier,
 14     String
 15 };
 16 
 17 enum class ParseState
 18 {
 19     Begin,
 20     InComment,
 21     //InCommentEnd,
 22     InInteger,
 23     InFloat,
 24     InOperator,
 25     InIdentifier,
 26     InString,
 27     InStringEscaping,
 28     //InStringEnd
 29 };
 30 struct Token
 31 {
 32     int line;
 33     int column;
 34     TokenType type;
 35     std::wstring value;
 36     Token(int _line, int _column, TokenType _type, const wchar_t* begin, const wchar_t* end)
 37         : line(_line)
 38         , column(_column)
 39         , type(_type)
 40         , value(begin, end)
 41     {
 42         if (type == TokenType::String)
 43         {
 44             for (size_t i = 0; i < value.length(); i++)
 45             {
 46                 if (value[i] == '\')
 47                 {
 48                     if (i + 1 < value.length())
 49                     {
 50                         switch (value[i + 1])
 51                         {
 52                         case'\':
 53                         {
 54                             value.replace(i, 2, 1, '\');
 55                             break;
 56                         }
 57                         case'n':
 58                         {
 59                             value.replace(i, 2, 1, '
');
 60                             break;
 61                         }
 62                         case'"':
 63                         {
 64                             value.replace(i, 2, 1, '"');
 65                             break;
 66                         }
 67                         default:
 68                         {
 69                             throw std::exception("error in escaping");
 70                             break;
 71                         }
 72                         }
 73                     }
 74                     else
 75                     {
 76                         throw std::exception("error in escaping");
 77                     }
 78                 }
 79             }
 80         }
 81     }
 82 };
 83 
 84 class TokenStream
 85 {
 86 private:
 87     struct ParsingState
 88     {
 89         ParseState State;
 90         int Line;
 91         int Column;
 92         const wchar_t* TokenStart;
 93         const wchar_t* TokenEnd;
 94     };
 95     std::vector<Token> tokenList;
 96     
 97     void PushToken(ParsingState& state, TokenType type)
 98     {
 99         tokenList.push_back(Token(state.Line, state.Column, type, state.TokenStart, state.TokenEnd));
100     }
101 public:
102     std::vector<Token> Parse(std::wstring& source)
103     {
104         ParsingState state{ParseState::Begin, 0, 0, source.c_str(), source.c_str()};
105         int lineNumber = 1;
106         int columnNumber = 1;
107 
108         while (*state.TokenEnd)
109         {
110             switch (state.State)
111             {
112             case ParseState::Begin:
113             {
114                 state.TokenStart = state.TokenEnd;
115                 state.Column = columnNumber;
116                 state.Line = lineNumber;
117                 switch (*state.TokenEnd)
118                 {
119                 case'+':case'-':case'*':case'/':case'(':case')':case'<':case'>':case'=':case';':
120                 case'^':case'&':case'.':
121                 {
122                     state.TokenEnd++;
123                     PushToken(state, TokenType::Operator);
124                     state.TokenEnd--;
125                     break;
126                 }
127                 case'0':case'1':case'2':case'3':case'4':case'5':case'6':case'7':case'8':case'9':
128                 {
129                     state.State = ParseState::InInteger;
130                     break;
131                 }
132                 case'a':case'b':case'c':case'd':case'e':case'f':case'g':case'h':case'i':case'j':case'k':case'l':case'm':case'n':case'o':case'p':case'q':case'r':case's':
133                 case't':case'u':case'v':case'w':case'x':case'y':case'z':case'A':case'B':case'C':case'D':case'E':case'F':case'G':case'H':case'I':case'J':case'K':case'L':
134                 case'M':case'N':case'O':case'P':case'Q':case'R':case'S':case'T':case'U':case'V':case'W':case'X':case'Y':case'Z':case'_':
135                 {
136                     state.State = ParseState::InIdentifier;
137                     break;
138                 }
139                 case'#':
140                 {
141                     state.TokenStart++;
142                     state.State = ParseState::InComment;
143                     break;
144                 }
145                 case'"':
146                 {
147                     state.TokenStart++;
148                     state.State = ParseState::InString;
149                     break;
150                 }
151                 case'
':
152                 {
153                     lineNumber++;
154                     columnNumber = 0;
155                     break;
156                 }
157                 case' ':
158                 {
159                     break;
160                 }
161                 default:
162                 {
163                     throw std::exception("parse error");
164                     break;
165                 }
166                 }
167                 break;
168             } //case ParseState::Begin
169             case ParseState::InInteger:
170             {
171                 switch (*state.TokenEnd)
172                 {
173                 case'0':case'1':case'2':case'3':case'4':case'5':case'6':case'7':case'8':case'9':
174                 {
175                     break;
176                 }
177                 case'.':
178                 {
179                     state.State = ParseState::InFloat;
180                     break;
181                 }
182                 default:
183                 {
184                     state.State = ParseState::Begin;
185                     PushToken(state, TokenType::Number);
186                     state.TokenEnd--;
187                     columnNumber--;
188                     break;
189                 }
190                 }
191                 break;
192             } //case ParseState::InInteger
193             case ParseState::InComment:
194             {
195                 if (*state.TokenEnd == '
' || *state.TokenEnd == '#')
196                 {
197                     state.State = ParseState::Begin;
198                     if (*state.TokenEnd == '
')
199                     {
200                         lineNumber++;
201                     }
202                     columnNumber = 1;
203                     PushToken(state, TokenType::Comment);
204                 }
205                 break;
206             } //ParseState::InComment
207             case ParseState::InIdentifier:
208             {
209                 switch (*state.TokenEnd)
210                 {
211                 case'a':case'b':case'c':case'd':case'e':case'f':case'g':case'h':case'i':case'j':case'k':case'l':case'm':case'n':case'o':case'p':case'q':case'r':case's':
212                 case't':case'u':case'v':case'w':case'x':case'y':case'z':case'A':case'B':case'C':case'D':case'E':case'F':case'G':case'H':case'I':case'J':case'K':case'L':
213                 case'M':case'N':case'O':case'P':case'Q':case'R':case'S':case'T':case'U':case'V':case'W':case'X':case'Y':case'Z':case'_':
214                 {
215                     break;
216                 }
217                 default:
218                 {
219                     state.State = ParseState::Begin;
220                     PushToken(state, TokenType::Identifier);
221                     columnNumber--;
222                     state.TokenEnd--;
223                     break;
224                 }
225                 }
226                 break;
227             } //ParseState::InIdentifier
228             case ParseState::InString:
229             {
230                 switch (*state.TokenEnd)
231                 {
232                 case '\':
233                 {
234                     state.State = ParseState::InStringEscaping;
235                     break;
236                 }
237                 case '"':
238                 {
239                     state.State = ParseState::Begin;
240                     PushToken(state, TokenType::String);
241                     break;
242                 }
243                 case '
':
244                 {
245                     throw std::exception("parse error in string");
246                     break;
247                 }
248                 default:
249                 {
250                     break;
251                 }
252                 }
253                 break;
254             } // ParseState::InString
255             case ParseState::InFloat:
256             {
257                 switch (*state.TokenEnd)
258                 {
259                 case'0':case'1':case'2':case'3':case'4':case'5':case'6':case'7':case'8':case'9':
260                 {
261                     break;
262                 }
263                 default:
264                 {
265                     PushToken(state, TokenType::Number);
266                     columnNumber--;
267                     state.TokenEnd--;
268                     state.State = ParseState::Begin;
269                     break;
270                 }
271                 }
272                 break;
273             } //ParseState::InFloat
274             case ParseState::InStringEscaping:
275             {
276                 state.State = ParseState::InString;
277                 switch (*state.TokenEnd)
278                 {
279                 case'n':case'\':case'"':
280                 {
281                     break;
282                 }
283                 default:
284                 {
285                     throw std::exception("parse error in escaping");
286                     break;
287                 }
288                 }
289                 break;
290             } //ParseState::InStringEscaping
291             } //switch state
292             state.TokenEnd++;
293             columnNumber++;
294         }
295         return tokenList;
296     }
297 };
298 
299 #endif // !TOKEN_STREAM

300行的大函数，我也是醉了