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 帐户与我联系。我正在处理这个问题以及其他一些事情。