【Parser系列】Lexer III
寫在前面
bajdcc/CParser
趕了一天工，把Lexer完成了，現在，Lexer可以毫不羞澀地解析dropbox/json11了。雖然json11是C++的程式碼，Lexer還是可以解析的。部分結果如題圖。
執行的話，用VS2015編譯（Release快一點），然後執行即可，它會讀取工程目錄下的text/json11。cpp，然後解析。
初始的解析非常簡單，因而忽略了錯誤處理、速度最佳化等方面。
比上一篇內容多了些改進，json11作為一個大的測試用例，讓我看到了先前程式碼中的一些缺陷，好在全都改正了。
那麼Lexer部分的最後，完成下列匹配功能：
匹配註釋
匹配關鍵詞
匹配運算子
顯而易見，如果都匹配不到，就skip一個字元，並將其標記為error。
完善的正則表示式
smatch_t
sm
；
regex_t
r_string
{
R
“（（［^
\\
］）|（？：
\\
（？：（［bfnrtv‘”
\\
］）
|
（
？：
0
（
\
d
{
1
，
2
}））
|
（
\
d
）
|
（
？：
x
（
［［：xdigit：］］
{
1
，
2
}）））））
“， std：：regex：：ECMAScript | std：：regex：：optimize }；
regex_t
r_char
{
R
”（’（？：（［^‘“
\\
］）
|
（
？：
\\
（
？：
（［
bfnrtv
’
”
\\
］）|（？：0（\d{1，2}））|（\d）|（？：x（［［：xdigit：］］{1，2}）））））‘）“
，
std
：：
regex
：：
ECMAScript
|
std
：：
regex
：：
optimize
}；
regex_t
r_digit
{
R
”（（（？：\d+（\。）？\d*）（？：［eE］［+-］？\d+）？）（［uU］）？（［fFdDiIlL］）？）“
，
std
：：
regex
：：
ECMAScript
|
std
：：
regex
：：
optimize
}；
regex_t
r_alpha
{
R
”（［［：alpha：］_］\w*）“
，
std
：：
regex
：：
ECMAScript
|
std
：：
regex
：：
optimize
}；
regex_t
r_space
{
R
”（（［ ］+）|（（？：
\r\n
）+）|（
\n
+））“
，
std
：：
regex
：：
ECMAScript
|
std
：：
regex
：：
optimize
}；
regex_t
r_comment
{
R
”（（？：//（［^
\r\n
］*））|（？：/\*（［［：print：］
\n
］*？）\*/））“
，
std
：：
regex
：：
ECMAScript
|
std
：：
regex
：：
optimize
}；
regex_t
r_hex
{
R
”（^0x（［［：xdigit：］］{1，8}））“
，
std
：：
regex
：：
ECMAScript
|
std
：：
regex
：：
optimize
}；
regex_t
r_keyword
{
lexer_keyword_regex
（），
std
：：
regex
：：
ECMAScript
|
std
：：
regex
：：
optimize
}；
regex_t
r_operator
［
3
］
=
{
regex_t
{
lexer_operator_regex
（
1
），
std
：：
regex
：：
ECMAScript
|
std
：：
regex
：：
optimize
}，
regex_t
{
lexer_operator_regex
（
2
），
std
：：
regex
：：
ECMAScript
|
std
：：
regex
：：
optimize
}，
regex_t
{
lexer_operator_regex
（
3
），
std
：：
regex
：：
ECMAScript
|
std
：：
regex
：：
optimize
}
}；
匹配註釋
lexer_t
CLexer
：：
next_comment
（）
{
if
（
std
：：
regex_search
（
str
。
cbegin
（）
+
index
，
str
。
cend
（），
sm
，
r_comment
））
{
auto
ms
=
sm
［
0
］。
str
（）；
auto
ml
=
ms
。
length
（）；
if
（
sm
［
1
］。
matched
）
// comment like ’// 。。。‘
{
bags
。
_comment
=
sm
［
1
］。
str
（）；
move
（
ml
）；
return
l_comment
；
}
else
if
（
sm
［
2
］。
matched
）
// comment like ’/* 。。。 */‘
{
bags
。
_comment
=
sm
［
2
］。
str
（）；
move
（
ml
，
std
：：
count
（
bags
。
_comment
。
begin
（），
bags
。
_comment
。
end
（），
’\n‘
），
true
）；
// check new line
return
l_comment
；
}
}
assert
（
！
”comment not match“
）；
return
l_error
；
}
這裡有個小細節：雖然註釋都以“/”打頭，但是假如是“4/2”呢？這就不是註釋了，所以必須接著判斷“/”或者“*”，如果不是的話，就將“/”識別成除號。
匹配關鍵字
關鍵字的部分其實是屬於“變數名”範圍的，所以拿到變數名字串str，用正則表示式去匹配它即可。正則表示式有capture group即捕獲組的功能，所以構造一個“（^auto$）|（^bool$）|（^break$）|。。。”去匹配。如果匹配到是bool，那麼group［2］就有值，這個編號2同時也是k_bool的值，都是相對應的。
如何生成這個regex就是用說了，用string去拼接，這裡懶得用stringstream等東西了。
生成正則表示式：
string_t
lexer_keyword_regex
（）
{
string_t
str
；
for
（
auto
i
=
k__start
+
1
；
i
<
k__end
；
i
++
）
{
str
+=
”（^“
；
str
+=
keyword_string_list
［
i
］；
str
+=
”$）|“
；
}
str
。
erase
（
str
。
length
（）
-
1
）；
return
str
；
}
識別出變數名後匹配看是否是關鍵字：
lexer_t
CLexer
：：
next_alpha
（）
{
if
（
std
：：
regex_search
（
str
。
cbegin
（）
+
index
，
str
。
cend
（），
sm
，
r_alpha
））
{
auto
s
=
sm
［
0
］。
str
（）；
if
（
std
：：
regex_search
（
s
。
cbegin
（），
s
。
cend
（），
sm
，
r_keyword
））
{
auto
b
=
sm
。
begin
（）
+
1
；
auto
i
=
std
：：
distance
（
b
，
std
：：
find_if
（
b
，
sm
。
end
（），
match_pred
））；
bags
。
_keyword
=
（
keyword_t
）（
i
+
1
）；
move
（
s
。
length
（））；
return
l_keyword
；
}
else
{
bags
。
_identifier
=
s
。
c_str
（）；
move
（
s
。
length
（））；
return
l_identifier
；
}
}
assert
（
！
”alpha not match“
）；
return
l_error
；
}
匹配運算子
匹配運算子和匹配關鍵字的過程殊途同歸，不過區別在於不能將運算子原封不動填進正則表示式裡，這裡需要轉義。
string_t
operator_esc_string_list
［］
=
{
”@START“
，
”=“
，
”
\\
+“
，
”-“
，
”
\\
*“
，
”/“
，
”
\\\\
“
，
”
\\
？“
，
”%“
，
”&“
，
”
\\
|“
，
”~“
，
”
\\
^“
，
”！“
，
”<“
，
”>“
，
”
\\
（“
，
”
\\
）“
，
”
\\
{“
，
”
\\
}“
，
”
\\
［“
，
”
\\
］“
，
”，“
，
”
\\
。“
，
”；“
，
”：“
，
”==“
，
”！=“
，
”
\\
+
\\
+“
，
”——“
，
”
\\
+=“
，
”-=“
，
”
\\
*=“
，
”/=“
，
”&=“
，
”
\\
|=“
，
”
\\
^=“
，
”%=“
，
”
\\
<=“
，
”
\\
>=“
，
”&&“
，
”
\\
|
\\
|“
，
”->“
，
”<<“
，
”>>“
，
”<<=“
，
”>>=“
，
”
\\
。
\\
。
\\
。“
，
”@END“
，
}；
const
string_t
&
lexer_opstr
（
operator_t
type
）
{
assert
（
type
>
op__start
&&
type
<
op__end
）；
return
operator_string_list
［
type
］；
}
const
string_t
&
lexer_opnamestr
（
operator_t
type
）
{
assert
（
type
>
op__start
&&
type
<
op__end
）；
return
opname_string_list
［
type
］；
}
int
op_len_start_idx
［］
=
{
op__start
，
op_assign
，
op_equal
，
op_left_shift_assign
，
op__end
}；
int
lexer_operator_start_idx
（
int
len
）
{
assert
（
len
>=
0
&&
len
<=
4
）；
return
op_len_start_idx
［
len
］；
}
string_t
lexer_operator_regex
（
int
len
）
{
assert
（
len
>=
1
&&
len
<=
3
）；
string_t
str
；
for
（
auto
i
=
op_len_start_idx
［
len
］；
i
<
op_len_start_idx
［
len
+
1
］；
i
++
）
{
str
+=
”（^“
；
str
+=
operator_esc_string_list
［
i
］；
str
+=
”$）|“
；
}
str
。
erase
（
str
。
length
（）
-
1
）；
return
str
；
}
由於某種原因，遇到“a|aa”這樣的正則表示式後，std：：regex只會識別出a，它是非貪婪的，這個問題沒法解決，所以只能按運算子長度對所有的運算子進行分類，確保同類中沒有重複字首。
構造完運算子的正則表示式後，用來解析：
lexer_t
CLexer
：：
next_operator
（）
{
for
（
auto
i
=
2
；
i
>=
0
；
i
——
）
{
if
（
index
+
i
>=
length
）
continue
；
if
（
std
：：
regex_search
（
str
。
cbegin
（）
+
index
，
str
。
cbegin
（）
+
index
+
i
+
1
，
sm
，
r_operator
［
i
］））
{
auto
s
=
sm
［
0
］。
str
（）；
auto
b
=
sm
。
begin
（）
+
1
；
auto
j
=
std
：：
distance
（
b
，
std
：：
find_if
（
b
，
sm
。
end
（），
match_pred
））；
j
+=
lexer_operator_start_idx
（
i
+
1
）
-
1
；
bags
。
_operator
=
（
operator_t
）（
j
+
1
）；
move
（
s
。
length
（））；
return
l_operator
；
}
}
// ignore error
// assert（！”operator not match“）；
move
（
1
）；
return
l_error
；
}
識別運算子是Lexer的最後一環節，如果還不透過的話，就無視它，標記為error。後面會將這些錯誤儲存在list中。
階段性總結
那麼經過兩週的努力，一個萌萌噠Lexer就大功告成了~
這個Lexer是與眾不同的，因為它比較懶，用regex去匹配原串了，讓程式碼更精簡。藉助LL（1）的解析，讓層次更清晰。
後面的話，需要做parser以便解析C語言的語法，不過由於本人水平較渣，像指標這類變態語法還未曾思考過如何去解析，看來這注定是一場LL與LR的妥協。不過這個專案於我的突破就是LL以及解析指標/強制轉換的語法問題，後者是因為解析後的語法樹可以有歧義，需要選擇正確的一個，所以——回溯看來是不可避免的。
後面的指令集我就自己設計去了，然後執行程式的時候，我想再增加個分頁機制和用於記憶體申請的記憶體池，把先前學習的內容再用上一遍，想起來就美滋滋的。雖然這樣導致程式執行速度變慢，不過無所謂，直譯器嘛。