F# 程式設計/詞法分析和語法分析
| F# : 詞法分析和語法分析 |
詞法分析和語法分析是一種非常實用的方法，可以將原始碼（或其他具有明確定義的語法的可讀輸入）轉換為表示原始碼的抽象語法樹 (AST)。F# 附帶了兩個工具，FsLex 和 FsYacc，用於將輸入轉換為 AST。
FsLex 和 FsYacc 的規範與OCamlLex 和 OCamlYacc基本相同，後者又基於Lex 和 Yacc詞法分析器/解析器生成器系列。幾乎所有與 OCamlLex/OCamlYacc 相關的資料都可以無縫地遷移到 FsLex/FsYacc。考慮到這一點，SooHyoung Oh 的OCamlYacc 教程及其配套的OCamlLex 教程是學習如何使用 F#（以及 OCaml）附帶的詞法分析和語法分析工具的最佳線上資源！
將輸入轉換為定義明確的抽象語法樹需要（至少）兩個轉換
- 詞法分析器使用正則表示式將輸入中的每個語法元素轉換為標記，本質上是將輸入對映到標記流。
- 解析器讀取標記流並嘗試將標記與一組規則匹配，其中最終結果將標記流對映到抽象語法樹。
當然可以編寫一個直接生成抽象語法樹的詞法分析器，但這僅適用於最簡單的語法。如果語法包含平衡的括號或其他遞迴結構、可選標記、重複的標記組、運算子優先順序或無法用正則表示式捕獲的任何內容，那麼最好除了詞法分析器之外還編寫一個解析器。
使用 F#，可以編寫自定義檔案格式、領域特定語言，甚至為您的新語言編寫完整的編譯器。
以下程式碼將逐步演示如何為 SQL 的子集定義一個簡單的詞法分析器/解析器。如果您使用的是 Visual Studio，則應將對 FSharp.PowerPack.dll 的引用新增到您的專案中。如果您在命令列上進行編譯，請使用 -r 標誌引用上述 F# PowerPack 程式集。
我們想解析以下 SQL 語句
SELECT x, y, z
FROM t1
LEFT JOIN t2
INNER JOIN t3 ON t3.ID = t2.ID
WHERE x = 50 AND y = 20
ORDER BY x ASC, y DESC, z
這是一個非常簡單的查詢，雖然它沒有演示您可以使用該語言執行的所有操作，但這是一個良好的開端。我們可以使用以下 F# 定義對該查詢中的所有內容進行建模
// Sql.fs
type value =
| Int of int
| Float of float
| String of string
type dir = Asc | Desc
type op = Eq | Gt | Ge | Lt | Le // =, >, >=, <, <=
type order = string * dir
type where =
| Cond of (value * op * value)
| And of where * where
| Or of where * where
type joinType = Inner | Left | Right
type join = string * joinType * where option // table name, join, optional "on" clause
type sqlStatement =
{ Table : string;
Columns : string list;
Joins : join list;
Where : where option;
OrderBy : order list }
記錄型別將我們所有相關的值整齊地分組到一個物件中。解析器完成時，它應該能夠將字串轉換為 sqlStatement 型別的物件。
標記是語法中任何一個可識別的元素。讓我們看看我們要解析的字串
SELECT x, y, z
FROM t1
LEFT JOIN t2
INNER JOIN t3 ON t3.ID = t2.ID
WHERE x = 50 AND y = 20
ORDER BY x ASC, y DESC, z
到目前為止，我們有幾個關鍵字（按照慣例，所有關鍵字都大寫）：SELECT、FROM、LEFT、INNER、RIGHT、JOIN、ON、WHERE、AND、OR、ORDER、BY、ASC、DESC 和 COMMA。
還有一些比較運算子：EQ、GT、GE、LT、LE。
我們還有由字串和數字字面量組成的非關鍵字識別符號，我們將使用關鍵字 ID、INT、FLOAT 來表示它們。
最後，還有一個標記 EOF，表示輸入流的結尾。
現在我們可以為 FsYacc 建立一個基本的解析器檔案，將檔案命名為 SqlParser.fsp
%{
open Sql
%}
%token <string> ID
%token <int> INT
%token <float> FLOAT
%token AND OR
%token COMMA
%token EQ LT LE GT GE
%token JOIN INNER LEFT RIGHT ON
%token SELECT FROM WHERE ORDER BY
%token ASC DESC
%token EOF
// start
%start start
%type <string> start
%%
start:
| { "Nothing to see here" }
%%
這是模板程式碼，其中包含標記部分。
使用以下命令列編譯解析器：fsyacc SqlParser.fsp
- 提示
- 如果您還沒有這樣做，您應該將 F# bin 目錄新增到您的 PATH 環境變數中.
- 如果您使用的是 Visual Studio，您可以在每次編譯時自動生成解析器程式碼。右鍵單擊您的專案檔案並選擇“屬性”。導航到“生成事件”選項卡，並將以下內容新增到“預生成事件命令列”中，並使用以下內容：
fsyacc "$(ProjectDir)SqlParser.fsp"。還要記得將此檔案從構建過程中排除：右鍵單擊該檔案，選擇“屬性”，然後針對“構建操作”選擇“無”。
如果一切正常，FsYacc 將生成兩個檔案，SqlParser.fsi 和 SqlParser.fs。如果您在專案中不存在這些檔案，則需要將它們新增到專案中。如果您開啟 SqlParser.fsi 檔案，您會注意到在 .fsl 檔案中定義的標記已轉換為聯合型別。
詞法分析器將文字輸入轉換為標記流。我們可以從以下模板程式碼開始
{
// header: any valid F# can appear here.
open Lexing
}
// regex macros
let char = ['a'-'z' 'A'-'Z']
let digit = ['0'-'9']
let int = '-'?digit+
let float = '-'?digit+ '.' digit+
let whitespace = [' ' '\t']
let newline = "\n\r" | '\n' | '\r'
// rules
rule tokenize = parse
| whitespace { tokenize lexbuf }
| newline { lexbuf.EndPos <- lexbuf.EndPos.NextLine; tokenize lexbuf; }
| eof { () }
這不是“真正的”F# 程式碼，而是一種由 FsLex 使用的特殊語言。
檔案開頭的 let 繫結用於定義正則表示式宏。eof 是一個特殊標記，用於識別字符串緩衝區輸入的結尾。
rule ... = parse ... 定義了我們的詞法分析函式，在上面稱為 tokenize。我們的詞法分析函式由一系列規則組成，這些規則有兩個部分：1) 正則表示式，2) 如果正則表示式匹配要執行的表示式，例如返回標記。文字從標記流中逐個字元地讀取，直到它匹配正則表示式並返回標記。
我們可以透過新增更多匹配表示式來填寫詞法分析器的剩餘部分
{
open Lexing
// opening the SqlParser module to give us access to the tokens it defines
open SqlParser
}
let char = ['a'-'z' 'A'-'Z']
let digit = ['0'-'9']
let int = '-'?digit+
let float = '-'?digit+ '.' digit+
let identifier = char(char|digit|['-' '_' '.'])*
let whitespace = [' ' '\t']
let newline = "\n\r" | '\n' | '\r'
rule tokenize = parse
| whitespace { tokenize lexbuf }
| newline { lexbuf.EndPos <- lexbuf.EndPos.NextLine; tokenize lexbuf; }
| int { INT(Int32.Parse(lexeme lexbuf)) }
| float { FLOAT(Double.Parse(lexeme lexbuf)) }
| ',' { COMMA }
| eof { EOF }
注意 { 和 } 之間的程式碼由純 F# 程式碼組成。還要注意我們正在返回與在 SqlParser.fsp 中定義的相同的標記（INT、FLOAT、COMMA 和 EOF）。正如您可能推斷的那樣，程式碼 lexeme lexbuf 返回解析器匹配的字串。tokenize 函式將被轉換為返回型別為 SqlParser.token 的函式。
我們可以很容易地填寫詞法分析器的其餘規則
{
open System
open SqlParser
open Lexing
let keywords =
[
"SELECT", SELECT;
"FROM", FROM;
"WHERE", WHERE;
"ORDER", ORDER;
"BY", BY;
"JOIN", JOIN;
"INNER", INNER;
"LEFT", LEFT;
"RIGHT", RIGHT;
"ASC", ASC;
"DESC", DESC;
"AND", AND;
"OR", OR;
"ON", ON;
] |> Map.ofList
let ops =
[
"=", EQ;
"<", LT;
"<=", LE;
">", GT;
">=", GE;
] |> Map.ofList
}
let char = ['a'-'z' 'A'-'Z']
let digit = ['0'-'9']
let int = '-'?digit+
let float = '-'?digit+ '.' digit+
let identifier = char(char|digit|['-' '_' '.'])*
let whitespace = [' ' '\t']
let newline = "\n\r" | '\n' | '\r'
let operator = ">" | ">=" | "<" | "<=" | "="
rule tokenize = parse
| whitespace { tokenize lexbuf }
| newline { lexbuf.EndPos <- lexbuf.EndPos.NextLine; tokenize lexbuf; }
| int { INT(Int32.Parse(lexeme lexbuf)) }
| float { FLOAT(Double.Parse(lexeme lexbuf)) }
| operator { ops.[lexeme lexbuf] }
| identifier { match keywords.TryFind(lexeme lexbuf) with
| Some(token) -> token
| None -> ID(lexeme lexbuf) }
| ',' { COMMA }
| eof { EOF }
注意，我們建立了一些對映，一個用於關鍵字，一個用於運算子。雖然我們當然可以將它們定義為詞法分析器中的規則，但通常建議只使用少量規則，以避免“狀態爆炸”。
要編譯此詞法分析器，請在命令列上執行以下程式碼：fslex SqlLexer.fsl。（嘗試將此檔案新增到您的專案構建事件中。）然後，將 SqlLexer.fs 檔案新增到專案中。我們現在可以使用一些示例輸入來試驗詞法分析器
open System
open Sql
let x = "
SELECT x, y, z
FROM t1
LEFT JOIN t2
INNER JOIN t3 ON t3.ID = t2.ID
WHERE x = 50 AND y = 20
ORDER BY x ASC, y DESC, z
"
let lexbuf = Lexing.from_string x
while not lexbuf.IsPastEndOfStream do
printfn "%A" (SqlLexer.tokenize lexbuf)
Console.WriteLine("(press any key)")
Console.ReadKey(true) |> ignore
此程式將打印出上述字串匹配的標記列表。
解析器將標記流轉換為抽象語法樹。我們可以修改模板解析器如下（無法編譯）
%{
open Sql
%}
%token <string> ID
%token <int> INT
%token <float> FLOAT
%token AND OR
%token COMMA
%token EQ LT LE GT GE
%token JOIN INNER LEFT RIGHT ON
%token SELECT FROM WHERE ORDER BY
%token ASC DESC
%token EOF
// start
%start start
%type <Sql.sqlStatement> start
%%
start: SELECT columnList
FROM ID
joinList
whereClause
orderByClause
EOF {
{ Table = $4;
Columns = $2;
Joins = $5;
Where = $6;
OrderBy = $7 }
}
value:
| INT { Int($1) }
| FLOAT { Float($1) }
| ID { String($1) }
%%
讓我們檢查一下 start: 函式。您可以立即看到我們有一個標記列表，它給出了 select 語句的粗略概要。此外，您可以看到包含在 { 和 } 之間的 F# 程式碼，當代碼成功匹配時，它將被執行 - 在這種情況下，它將返回 Sql.sqlStatement 記錄的例項。
F# 程式碼包含 "$1"、"$2"、:$3" 等，它與正則表示式替換語法有點類似。每個 "$#" 對應於匹配規則中標記的索引（從 1 開始）。當標記如下注釋時，這些索引會變得很明顯
(* $1 $2 *)
start: SELECT columnList
(* $3 $4 *)
FROM ID
(* $5 *)
joinList
(* $6 *)
whereClause
(* $7 *)
orderByClause
(* $8 *)
EOF {
{ Table = $4;
Columns = $2;
Joins = $5;
Where = $6;
OrderBy = $7 }
}
因此，start 規則將我們的標記分解為一個基本形狀，然後我們使用該形狀將其對映到 sqlStatement 記錄。您可能想知道 columnList、joinList、whereClause 和 orderByClause 來自哪裡 - 這些不是標記，而是我們必須定義的其他解析規則。讓我們從第一個規則開始
columnList:
| ID { [$1]}
| ID COMMA columnList { $1 :: $3 }
columnList 匹配 "a, b, c, ... z" 樣式的文字，並將結果作為列表返回。注意此規則是遞迴定義的（還要注意規則的順序並不重要）。FsYacc 的匹配演算法是“貪婪的”，這意味著它將嘗試匹配儘可能多的標記。當 FsYacc 接收到 ID 標記時，它將匹配第一個規則，但它也匹配第二個規則的一部分。然後，FsYacc 執行一次標記的預讀：如果下一個標記是 COMMA，那麼它將嘗試匹配其他標記，直到完全滿足該規則。
- 注意： 上面的 columnList 定義不是尾遞迴的，因此對於特別大的輸入可能會丟擲堆疊溢位異常。尾遞迴版本的規則可以定義如下
start: ... EOF { { Table = $4; Columns = List.rev $2; Joins = $5; Where = $6; OrderBy = $7 } } columnList: | ID { [$1]} | columnList COMMA ID { $3 :: $1 }
- 尾遞迴版本反向建立列表，因此我們在從解析器返回最終輸出時必須反轉。
我們可以用相同的方式處理 JOIN 子句，但它稍微複雜一些
// join clause
joinList:
| { [] } // empty rule, matches 0 tokens
| joinClause { [$1] }
| joinClause joinList { $1 :: $2 }
joinClause:
| INNER JOIN ID joinOnClause { $3, Inner, $4 }
| LEFT JOIN ID joinOnClause { $3, Left, $4 }
| RIGHT JOIN ID joinOnClause { $3, Right, $4 }
joinOnClause:
| { None }
| ON conditionList { Some($2) }
conditionList:
| value op value { Cond($1, $2, $3) }
| value op value AND conditionList { And(Cond($1, $2, $3), $5) }
| value op value OR conditionList { Or(Cond($1, $2, $3), $5) }
joinList 是用幾個函式定義的。這是因為存在重複的標記組（例如多個連線的表）和可選標記（可選的“ON”子句）。您已經看到我們使用遞迴規則處理重複的標記組。要處理可選標記，我們只需將可選語法分解成一個單獨的函式，並建立一個空規則來表示 0 個標記。
牢記這種策略，我們可以編寫其餘的解析器規則
%{
open Sql
%}
%token <string> ID
%token <int> INT
%token <float> FLOAT
%token AND OR
%token COMMA
%token EQ LT LE GT GE
%token JOIN INNER LEFT RIGHT ON
%token SELECT FROM WHERE ORDER BY
%token ASC DESC
%token EOF
// start
%start start
%type <Sql.sqlStatement> start
%%
start: SELECT columnList
FROM ID
joinList
whereClause
orderByClause
EOF {
{ Table = $4;
Columns = List.rev $2;
Joins = $5;
Where = $6;
OrderBy = $7 }
}
columnList:
| ID { [$1]}
| columnList COMMA ID { $3 :: $1 }
// join clause
joinList:
| { [] }
| joinClause { [$1] }
| joinClause joinList { $1 :: $2 }
joinClause:
| INNER JOIN ID joinOnClause { $3, Inner, $4 }
| LEFT JOIN ID joinOnClause { $3, Left, $4 }
| RIGHT JOIN ID joinOnClause { $3, Right, $4 }
joinOnClause:
| { None }
| ON conditionList { Some($2) }
conditionList:
| value op value { Cond($1, $2, $3) }
| value op value AND conditionList { And(Cond($1, $2, $3), $5) }
| value op value OR conditionList { Or(Cond($1, $2, $3), $5) }
// where clause
whereClause:
| { None }
| WHERE conditionList { Some($2) }
op: EQ { Eq } | LT { Lt } | LE { Le } | GT { Gt } | GE { Ge }
value:
| INT { Int($1) }
| FLOAT { Float($1) }
| ID { String($1) }
// order by clause
orderByClause:
| { [] }
| ORDER BY orderByList { $3 }
orderByList:
| orderBy { [$1] }
| orderBy COMMA orderByList { $1 :: $3 }
orderBy:
| ID { $1, Asc }
| ID ASC { $1, Asc }
| ID DESC { $1, Desc}
%%
以下是我們的詞法分析器/解析器的完整程式碼
SqlParser.fsp
%{
open Sql
%}
%token <string> ID
%token <int> INT
%token <float> FLOAT
%token AND OR
%token COMMA
%token EQ LT LE GT GE
%token JOIN INNER LEFT RIGHT ON
%token SELECT FROM WHERE ORDER BY
%token ASC DESC
%token EOF
// start
%start start
%type <Sql.sqlStatement> start
%%
start: SELECT columnList
FROM ID
joinList
whereClause
orderByClause
EOF {
{ Table = $4;
Columns = List.rev $2;
Joins = $5;
Where = $6;
OrderBy = $7 }
}
columnList:
| ID { [$1]}
| columnList COMMA ID { $3 :: $1 }
// join clause
joinList:
| { [] }
| joinClause { [$1] }
| joinClause joinList { $1 :: $2 }
joinClause:
| INNER JOIN ID joinOnClause { $3, Inner, $4 }
| LEFT JOIN ID joinOnClause { $3, Left, $4 }
| RIGHT JOIN ID joinOnClause { $3, Right, $4 }
joinOnClause:
| { None }
| ON conditionList { Some($2) }
conditionList:
| value op value { Cond($1, $2, $3) }
| value op value AND conditionList { And(Cond($1, $2, $3), $5) }
| value op value OR conditionList { Or(Cond($1, $2, $3), $5) }
// where clause
whereClause:
| { None }
| WHERE conditionList { Some($2) }
op: EQ { Eq } | LT { Lt } | LE { Le } | GT { Gt } | GE { Ge }
value:
| INT { Int($1) }
| FLOAT { Float($1) }
| ID { String($1) }
// order by clause
orderByClause:
| { [] }
| ORDER BY orderByList { $3 }
orderByList:
| orderBy { [$1] }
| orderBy COMMA orderByList { $1 :: $3 }
orderBy:
| ID { $1, Asc }
| ID ASC { $1, Asc }
| ID DESC { $1, Desc}
%%
SqlLexer.fsl
{
open System
open SqlParser
open Lexing
let keywords =
[
"SELECT", SELECT;
"FROM", FROM;
"WHERE", WHERE;
"ORDER", ORDER;
"BY", BY;
"JOIN", JOIN;
"INNER", INNER;
"LEFT", LEFT;
"RIGHT", RIGHT;
"ASC", ASC;
"DESC", DESC;
"AND", AND;
"OR", OR;
"ON", ON;
] |> Map.of_list
let ops =
[
"=", EQ;
"<", LT;
"<=", LE;
">", GT;
">=", GE;
] |> Map.of_list
}
let char = ['a'-'z' 'A'-'Z']
let digit = ['0'-'9']
let int = '-'?digit+
let float = '-'?digit+ '.' digit+
let identifier = char(char|digit|['-' '_' '.'])*
let whitespace = [' ' '\t']
let newline = "\n\r" | '\n' | '\r'
let operator = ">" | ">=" | "<" | "<=" | "="
rule tokenize = parse
| whitespace { tokenize lexbuf }
| newline { lexbuf.EndPos <- lexbuf.EndPos.NextLine; tokenize lexbuf; }
| int { INT(Int32.Parse(lexeme lexbuf)) }
| float { FLOAT(Double.Parse(lexeme lexbuf)) }
| operator { ops.[lexeme lexbuf] }
| identifier { match keywords.TryFind(lexeme lexbuf) with
| Some(token) -> token
| None -> ID(lexeme lexbuf) }
| ',' { COMMA }
| eof { EOF }
Program.fs
open System
open Sql
let x = "
SELECT x, y, z
FROM t1
LEFT JOIN t2
INNER JOIN t3 ON t3.ID = t2.ID
WHERE x = 50 AND y = 20
ORDER BY x ASC, y DESC, z
"
let lexbuf = Lexing.from_string x
let y = SqlParser.start SqlLexer.tokenize lexbuf
printfn "%A" y
Console.WriteLine("(press any key)")
Console.ReadKey(true) |> ignore
總而言之，我們最小的 SQL 詞法分析器/解析器大約有 150 行程式碼（包括非平凡的程式碼行和空白）。我將把實現剩餘的 SQL 語言規範留作讀者練習。
2011-03-06：我在 VS2010、F# 2.0 和 PowerPack 2.0 中嘗試了上述說明。我必須進行一些更改
- 在 SqlLexer.fsl 的第 2 行新增“module SqlLexer”
- 將 Map.of_list 更改為 Map.ofList
- 在 fsyacc 的命令列中新增“--module SqlParser”
- 新增 FSharp.PowerPack 以獲取 Lexing 模組
2011-07-06： (Sjuul Janssen) 為了使這正常工作，我必須採取這些步驟。
如果您收到訊息“期望 LexBuffer<char> 但給定 LexBuffer<byte> 型別 'char' 與型別 'byte' 不匹配”
- 在預構建中新增“fslex.exe "$(ProjectDir)SqlLexer.fsl" --unicode”
- 在 program.fs 中將“let lexbuf = Lexing.from_string x”更改為“let lexbuf = Lexing.LexBuffer<_>.FromString x”
- 在 SqlLexer.fsi 中將“lexeme lexbuf”更改為“LexBuffer<_>.LexemeString lexbuf”
如果您收到一些模組不存在或某些模組被多次宣告的訊息。確保在解決方案資源管理器中檔案按以下順序排列
- Sql.fs
- SqlParser.fsp
- SqlLexer.fsl
- SqlParser.fsi
- SqlParser.fs
- SqlLexer.fs
- Program.fs
如果您收到訊息“找不到方法：'System.Object Microsoft.FSharp.Text.Parsing.Tables`1.Interpret(Microsoft.FSharp.Core.FSharpFunc`2<Microsoft.FSharp.Text.Lexing.LexBuffer`1<Byte>,!0>, …” 請訪問 http://www.microsoft.com/download/en/details.aspx?id=15834 並重新安裝 Visual Studio 2010 F# 2.0 執行時 SP1（選擇“修復”）。
2011-07-06： (mkduffi) 有人可以提供一個示例專案嗎？我已經按照您的所有更改操作了，但仍然無法構建。謝謝。
https://github.com/obeleh/FsYacc-Example
2011-07-07 (mkduffi) 謝謝您釋出示例。以下是我對 Program.fs 檔案所做的操作
namespace FS
module Parser =
open System
open Sql
let x = "
SELECT x, y, z
FROM t1
LEFT JOIN t2
INNER JOIN t3 ON t3.ID = t2.ID
WHERE x = 50 AND y = 20
ORDER BY x ASC, y DESC, z
"
let ParseSql x =
let lexbuf = Lexing.LexBuffer<_>.FromString x
let y = SqlParser.start SqlLexer.tokenize lexbuf
y
let y = (ParseSql x)
printfn "%A" y
Console.WriteLine("(press any key)")
Console.ReadKey(true) |> ignore
我添加了一個 C# 控制檯專案用於測試，這是 Program.cs 檔案的內容
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
string query =
@"SELECT x, y, z
FROM t1
LEFT JOIN t2
INNER JOIN t3 ON t3.ID = t2.ID
WHERE x = 50 AND y = 20
ORDER BY x ASC, y DESC, z";
Sql.sqlStatement stmnt = FS.Parser.ParseSql(query);
}
};
}
我必須新增 YaccSample 專案引用以及對 FSharp.Core 程式集的引用才能使其正常工作。
如果有誰能幫助我弄清楚如何支援表別名，那將非常棒。
謝謝
2011-07-08 (Sjuul Janssen) 請透過我的 github 帳戶與我聯絡。我正在處理這個問題以及其他一些事情。