F#中DSL原型设计:语法检查和语义分析

行云间 2009-08-27

大致来讲,领域特定语言的工作方式有两种――你可以通过对以源DSL编写的源文本进行转译来实施,或者通过将源文本编译为可执行代码。这两种方式都有着独特的优点和缺点。对于解释器和编译器的实施阶段,很多都是类似的,甚至一模一样;例如,语法和语义检查在两种方式中是共同的。在获得合适的内部重现(inner representation)之后,编译器实施包括几个阶段,逐步将这种重现分解为低等级的指令,生成汇编语言原生码,或管理代码(取决于目标平台)。解释器与之相反,很少执行这些阶段。作为替代,你可以实施所谓的DSL 的“操作语义”(operational semantic);例如,为内部重现编写一个评估器。

F#中DSL原型设计:语法检查和语义分析

图1. 运行中的Simply

你可以在Simply上进行构建,来创建新的DSL并将其嵌入到你自己定制的开发外科中。此处演示的应用程序 SimplyLogo从零开始构建,F# 代码少于500 行。

在本文介绍的F#中DSL原型设计,我们将为一个小型的DSL(由于其类似 C 语言的语法和简洁,我将其称为“Simply”)编写一个解释器,然后使用与Logo 那种语言类似的内置函数将其实例化。你可以通过在表达式语法器上来构建以完成实例化。之前我们已经在相关文章中进行讲述,在这篇文章中,你可以看到活跃模式(active pattern)提供了一个完美的机制(虽然付出了一点速度的小代价),能够用于构建符合类型安全规则的语法器,它与用户语法中的正规的 BNF 句法非常相似;并且能够在增强的AST 重现上实施语言检查(本文)和评估器(下一篇文章)。使用这种语言,你可以快速生成图像,这些图像能够使用简单的画图命令来定义――并且你可以在所有你需要的语境中使用这个核心评估器。在图 1 中所示为该 DSL 的一种可能的嵌入。在本文中,我们主要关心的是构建 Simply 的语法器和检查源程序以确认语法的正确性。

Simply 概述

Simply 是本文的DSL,它是一个具有静态作用域、嵌套变量(nested variable)和函数声明,以及简单循环构造的小型编程语言。下面是一个很短的 Simply 程序:

var x = 2   


fun x(a b) { a + b + x }   


fun x(y) { y + x(1 2) }   


repeat 100 as i { x(i) } 

这段程序很容易读懂,它包含四条命令,定义了一个变量、两个函数和一个循环。为了分析这些命令的语法,你需要对上文中讲述的语法器进行扩展。

对具有循环构造、变量和函数的Simply进行扩展

前文中实施的语法器使用函数调用对算术表达式进行语法分析并将其翻译为定制的 AST 类型。对于 Simply,你需要一个稍微更为高级的内部重现来对表达式进行语法分析,这些表达式包含了简单变量以及与其密切关联的少量语言扩展,用于定义变量和函数,以及用简单的循环构造(循环区块)来表达循环。

如果你已经将AST 定义放在其自身模块中,下面你可以看到新的扩展版本:

namespace IntelliFactory.Simply   



module Ast =  




    type var = string   




    type Expr =  



 


 | Number of float   



 | BinOp of (float -> float -> float) * Expr * Expr  



 | Var of var  


 | FunApply of var * Expr list  


 


 static member Sum (e1, e2) = BinOp (( + ), e1, e2)  


 static member Diff (e1, e2) = BinOp (( - ), e1, e2)  


 static member Prod (e1, e2) = BinOp (( * ), e1, e2)  


 static member Ratio (e1, e2) = BinOp (( / ), e1, e2) 

你可能已经注意到,我对这个模块的代码格式进行了细小的调整,以便符合 F# 编码语法指南。我们的理想是用最少的代码实现最多的功能,同时在需要增加代码以及所表达的功能时仍然能够进行快速建模(prototyping)并且修改最小化。现在,你可以在代码中添加 AST 增强,其指向不再是那些普通的算术表达式:

   type Command =  


| VarDef of var * Expr  


| FunDef of var * var list * Command  


| Repeat of Expr * var * Command  


| Sequence of Command list  



| Yield of Expr type Prog = Program of Command list 

这些F#中DSL原型设计的代码定义了:

一个 Command 类型,可以对变量定义继续编码(利用一个值进行初始化) 函数定义(具有函数名称、常规的参数列表和一个体现函数主体的 Command 值) 循环区块(具有控制变量、循环程度表达式和一个用于体现循环区块主体的 Command 变量) Command 排序(对于定义需多个简单表达式的函数主体或循环区块非常有用) 简单表达式执行。一列这样的表达构成了一个程序。利用这些类型,你现在可以扩展你支持创建的表达式语法器。为了更加方便,你可以再次使用 Listing 1 中代码,然后对其进行稍微的增强:

这个核心语法器中唯一的更改(格式更改除外)位于(|Factor|_|)活跃模式在:这个版本添加了简单的变量变量引用(第三条规则),以满足增强的 AST 表达式语言中的相应的附加规则。

到这里,你就可以真正地开始加速,快速写下 DSl 语法器的其余部分。首先添加关键字和特定字符的规则:

let (|LBRACE|_|) s = "{" |> MatchSymbol s  



let (|RBRACE|_|) s = "}" |> MatchSymbol s  




let (|EQ|_|) s = "=" |> MatchSymbol s  




let (|VAR|_|) s = "var" |> MatchSymbol s  




let (|FUN|_|) s = "fun" |> MatchSymbol s  




let (|REPEAT|_|) s = "repeat" |> MatchSymbol s  




let (|AS|_|) s = "as" |> MatchSymbol s 

语法分析命令的规则是语法规则转换为之前地定义的活跃模式的一种简单的翻译。

let rec (|Command|_|) = function 


| VAR (ID (v, EQ (Expression (expr, rest)))) 


-> (Ast.Command.VarDef (v, expr), rest) 


|> Some | FUN (ID (f, LPAREN (Star (|ID|_|) [] ( pars, RPAREN (Command (body, rest)))))) 


-> (Ast.Command.FunDef (f, pars, body), rest)


 |> Some | REPEAT (Expression (i, AS (ID (v, Command (body, rest))))) 


-> (Ast.Command.Repeat (i, v, body), rest) 


|> Some | LBRACE (Star (|Command|_|) [] (commands, RBRACE rest)) 


-> (Ast.Command.Sequence commands, rest)


 |> Some | Expression (e, rest) 


-> (Ast.Command.Yield e, rest) |> Some | _ -> None 

例如,让我们看看上面(|Command|_|)活跃模式中的第一条规则。它字母的意思是:

“批评‘var’关键字,然后是标识符并将其与‘v’捆绑,然后是等于符号,然后是一个绑定到‘expr’的表达式;然后返回带有变量及其初始值的 Command.VarDef 值,还有其余的输入字符串,作为一个成功的匹配。”

其他规则一样易于理解和构造。有一个细节需要进一步解释,在函数定义或排序规则中如何使用(|Star|_|)活跃模式。记住,这是一个参数化(parameterized)的活跃模式,在它被应用到你再次匹配的值之前,它具有了两个变量。第一个变量是一个活跃模式,你可以“运行”零次或多次(名称 Star,它反映了常规语言如 BNF 或常规表达式中的 star 操作符),第二变量是初始累加器,用于收集请求结果。由于该累加器的初始值通常是一个空列表,因此你可能会选择以一种不需要初始值的方式重写这个活跃模式;因此这就给了你一直更为紧凑的方式来指定“零次或多次”这种类型的规则。

最后,你可以编写定义了这个程序语法的规则:

let (|Prog|_|) = function   



| Star (|Command|_|) [] (commands, rest) -> (Ast.Prog.Program commands, rest)   




|> Some | _ ->             None 

或者,编写一个格式稍微有点冗长的规则:

   let (|Prog|_|) s = match s with   



| Star (|Command|_|) [] (commands, rest) -> (Ast.Prog.Program commands, rest)   




|> Some | _ ->             None 

你可以在 Simply 程序上快速检验你的语法器――只需通过选取代码并按 Alt+Enter 键将 AST 和语言模块载入到 F# Interactive 中,然后测试一个 Simply 小程序:

open Language " var x=1 var x=2 var x=3 fun foo(y)   



{ fun bar(foo) { var xx=x+1 foo+x } bar(y*2)   



}   



repeat 1000 as x { foo(x) }" |> (|Prog|_|) |> printf "Result=%A\n";;  




 > Result=Some (Program [VarDef ("x",Number 1.0);   



VarDef ("x",Number 2.0); VarDef ("x",Number 3.0);  


FunDef ("foo",["y"], Sequence [FunDef ("bar",["foo"], Sequence [VarDef ("x",BinOp (,Var "x",Number 1.0));   


Yield (BinOp (,Var "foo",Var "x"))]);   


Yield (FunApply ("bar",[BinOp (,Var "y",Number 2.0)]))]);   



Repeat (Number 1000.0,"x",Sequence [Yield (FunApply ("foo",[Var "x"]))])], "") > 

你将看到,对于送入到识别 Simply 程序的主活跃模式中这个程序,输出结果是 AST 值的转存。

F#中DSL原型设计:语法检查和语义分析就到这里

相关推荐