没有合适的资源?快使用搜索试试~ 我知道了~
理论计算机科学电子笔记253(2010)51-64www.elsevier.com/locate/entcs类型化文法的类型化变换:左角变换阿瑟·巴尔斯1InstitutoTecnolo′gicodeInforma′ticaUniversidadPolit′ecnicadeValencia,Valencia,SpainS. Doaitse Swierstra2荷兰乌得勒支大学马科斯·维埃拉3InstitutodeComputacio'nUniversidaddelaRep u'blica,Montevideo,Uruguay摘要使用嵌入式领域特定语言时出现的问题之一是在多大程度上我们可以分析和转换嵌入式程序,就像通常在更传统的编译器中所做的那样。 当宿主语言是强类型的,并且这个宿主类型系统被用来对嵌入式语言进行类型化时,会出现特殊的问题。在本文中,我们描述了如何使用一个库,这是设计用于构造类型化抽象语法的转换,从类型化语法描述中去除左递归。 我们描述的算法是左角变换,它足够小,充分解释,足够有趣,足够完整,可以作为如何在类似案件中继续进行。所描述的转换已成功地用于构建标准Haskell读取函数的组合和高效替代方案关键词:GADT,左角变换,Meta编程,类型系统,类型化抽象树,类型化变换1介绍在Haskell中,可以描述特定数据类型的值如何被序列化(即写入)和重新序列化(即写入)。读取或解析)。由于数据类型可以作为1电子邮件:abaars@iti.upv.es2电子邮件:doaitse@cs.uu.nl3电子邮件:mviera@fing.edu.uy1571-0661 © 2010 Elsevier B.V. 在CC BY-NC-ND许可下开放访问。doi:10.1016/j.entcs.2010.08.03152A. Baars等人理论计算机科学电子笔记253(2010)51→→参数到数据类型构造函数,并且定义可以分布在几个模块上,因此出现了如何动态组合单独生成的片段的问题将“读取代码”的方法添加Haskell中的标准解决方案基于自顶向下解析器的简单组合,结果显示出指数级的读取时间。此外,为了避免左递归自顶向下解析器在运行时的动态构造,需要包含比预期更多的括号在最近的一篇论文[12]中,我们提出了一个解决这个问题的方法;编译器不是生成读取某个数据类型a的值的代码,而是构造Grammar a类型的值,表示描述该数据类型值的外部表示的语法片段。这种语法类型的显著特征是它反映了所表示的值的类型。这是必要的,因为从这样一个值,最终一个类型为String a的read函数必须由Haskell库代码构造。我们的目的是将解析过程分为两部分,在运行时处理可能的左递归语法。与每次解析时都必须分析语法的左角解析器不同,语法被转换一次以去除左递归,然后可以使用传统的高效解析技术。该解决方案基于三个或多或少独立的层(从上到下):(i) 一个模板Haskell库,它生成类型Grammar a的值和库代码,库代码在运行时组合这些值以形成一个完整的grammar。在这个组合值之外,再次通过库Haskell代码构造用于组合数据类型的所需读取函数。整个过程在上述论文[12]中有所描述。(ii) 这段代码调用了一个库函数,该函数从组合语法中删除了潜在的左递归。为此,我们使用左角变换(LCT)[7]。 这段代码产生一个Grammar类型的函数,语法a,是如何表达包含引用的类型化抽象语法的转换的一个很好的例子;在语法中,这些转换源于产生式右侧出现的非终结符。(iii) LCT和左因子分解代码利用了一个复杂的Haskell库,它利用了Haskell类型系统及其扩展的每一个角落,例如广义代数数据类型,存在和多态类型,以及类型级别的惰性求值。 设计方案和最终设计这个库,因为它已经提供给Haskell世界,值得一个自己的论文[1]。在本文中,我们将重点放在上述三个层的中间;我们从通过结合非类型化的Haskell实现来呈现LCT的优雅公式,接下来我们介绍底层实现的API,最后我们将非类型化的版本重新公式化为类型化的版本, 这个API。LCT [6]比直接左递归移除更复杂,A. Baars等人理论计算机科学电子笔记253(2010)5153[2],但也更有效(O(n2),其中n是文法中的终结符和非终结符的数量)。在这里,我们将从罗伯特C. [7],我们以更直观的形式呈现。他的测试(使用几个大型语法进行自然语言处理)和我们的测试(使用几个非常大的数据类型描述)都表明该算法在实践中表现得非常好。从类型化抽象语法的角度来看,这种转换的有趣之处在于,文法由包含对其他定义的引用的文法规则(每个非终结符对应一个)的集合组成;因此,我们转换的不是树,而是完整的绑定结构。在这个转变过程中,我们引入了许多新的定义。在这些定义的右边,我们再次引用这些新引入的符号。在我们的设置中,转换必须是类型保持的,因此我们必须确保环境的类型 参考文献保持一致,同时进行修改。以前关于有类型程序转换的工作[3,8,2]不能处理新定义和绑定器的引入。我们以Haskell代码的形式呈现算法,因此需要读者了解Haskell知识。但是请记住,Haskell目前是少数几个可以解决我们所描述的问题的通用语言之一。2左角变换在本节中,我们将LCT [6]作为一组构造规则进行介绍,然后在Haskell 98中给出一个无类型的实现。请注意,尽管被称为转换,但该过程实际上是在检查输入语法的同时构造新语法。 我们假设只有起始符号可以导出- 是的我们说一个符号X是一个非终结符A的直接左角,如果存在A的产生式,其符号X作为其最左边的符号在该产生式的右手边。 我们将左角关系定义为传递闭包的直接左角关系。注意,一个非终结符是左递归的等价于它本身的一个左角LCT被定义为三个令人惊讶的简单规则的应用我们用小写字母表示终端符号,低阶大写字母(A,B等) 表示来自语法的非终结符,以及高阶大写字母(X,Y,Z)表示可以是终结符或非终结符的符号。希腊符号表示终端和非终端的序列。对于原始文法的非终结符A,该算法为A构造新的产生式,并为形式为AX的非终结符构造一组新的定义。一个新的非终结符AX代表A的一部分,它在看到一个X之后仍然被识别出来。 对每个非终结符应用以下规则,直到没有获得进一步的结果:规则1对于原始文法的每个产生式A→Xβ,54A. Baars等人理论计算机科学电子笔记253(2010)51→→→转换后的语法,并将X添加到A的左角。规则2对于每个新找到的A的左角X:a 如果X是一个终结符,则在新语法中添加A X A X。b 如果X是非终结符,则对于每个原始产品X XJβ,添加产品A XJ将βAX添加到新文法中,并将XJ添加到A的左角。作为一个例子,考虑语法:A→a A| BB→A b|C将规则1应用于A的产生式会产生两个新的产生式和两个新遇到的左角:A a→AA B→n个左角=[a,B]规则2a,其中X绑定到左角aA→a A a leftcorners=[a,B]规则2b,其中X绑定到左角BA A→b A BA c→A B leftcorners=[a,B,A,c]规则2b,其中X绑定到左角AA a→A A AA B→A A左角=[a,B,A,c]规则2a,其中X绑定到左角cA→c A c leftcorners=[a,B,A,c]因为现在A的所有左角都已经处理过了,所以我们完成了A。对于非终端B,该过程产生以下新产品:B A→b-规则1B c→B-规则1B a→A B A-- 规 则 2b , A BB→B A--规则2b 、A、B→c B c- 第 2a 、 c 、 B 条→a B a-- 规 则 2a , a BA→b B B-- 规 则 2b , B Bc→B B--规则2b,B注意,通过构造,这个新文法不是左递归的。2.1无类型的左角变换在介绍我们的类型化LCT之前,我们先介绍一个非类型化的实现。Gram- mars由以下类型表示类型语法=映射NT[生产]typeNT=StringtypeProd=[Symbol]typeSymbol= StringisNonterminal = isUpper. 头isTerminal= isLower。头因此,语法是一个映射,它将每个非终结符名称与其产生式集合相关联。每个产品(Prod)由一系列符号(Symbol)组成。因此,我们的示例语法可以编码为:语法=地图。fromList[(“A”,[[“a”,“A”],[“B”]]),(“B”,[[“A”,“b”],[“c”]])]在转换过程中,我们使用Control。单子。状态-monad存储迄今为止构造的新语法。对于每个非终结符,我们遍历传递性A. Baars等人理论计算机科学电子笔记253(2010)5155→←∈→→→→→ →→→ →→→ → →→→ → →→由深度优先顺序的产生式引起的左角关系,同时将迄今为止遇到的左角符号的集合缓存在列表中typeLeftCorner=SymboltypeStep State=(Grammar,[LeftCorner])typeTrafo a=状态步骤状态a函数leftcorner接受一个语法,并通过运行transformationrules1返回一个转换后的语法,这会产生一元类型Trafo的值。该状态用一个空语法和一个空的遇到的左角符号列表初始化。final状态包含新构造的文法:leftcorner::Grammar语法左角g = fst。 snd. runState(rules1 g g)$(Map. 空,[])对于每个(mapM)非终结符(A),函数rules 1访问它的每个(mapM)结果;每次访问都会使用rule 2a和rule 2b产生新的结果。它们通过函数insert添加到转换后的语法中。从rule2a得到的结果返回(ps),并一起从原始非终结符A的新结果返回(concat)。 当从下一个非终结符开始时,左角缓存被重置:rules1::Grammar语法Trafo()rules1 gram nts=mapM nt(Map. 列出nts)其中nt(a,prods)=dops←mapM(rule 1 gram a)prodsmodify(λ(g,)→(Map. 插入a(concat ps)g,[ ]))对于给定的每个规则,我们定义一个函数:rule2b为原始语法的非终结符生成新的产生式,rule1和rule2b为非终结符生成形式为AX的产生式:规则1::语法NT Prod Trafo[Prod]rule1 grammar a(x:beta)=insert grammar a x betarule2a::NT Symbol Prod规则2a a b b=[b,a b]rule 2b::Grammar NT NT Prod Trafo[Prod]规则2bgrammaraab(y:beta)=insertgrammaray(beta++[ab])函数insert为非终结符A X添加了一个新的产生式:如果我们以前遇到过A X,则扩展已经存在的条目,否则添加了用于AX的新条目。在后一种情况下,我们应用规则2来找到更多的左角符号:插入::语法NT符号Prod Trafo[Prod]插入语法a x p=设ax=a++“_”++x(gram,lcs)getifxlcsthen doput(Map. 调整(p:)x克,lcs)返回[]其他 doput(地图。插入x[p]gram,x:lcs)规则2语法a x在规则2中,从规则2b的应用中产生的新的产生式被直接插入到转换后的语法中,而从规则2a产生的产生式被收集并作为Trafomonad的结果返回。当新找到的左角符号是终端时,应用规则2a,并简单地返回结果新的产生式规则。如果它是非终结符,则其对应的产生式位于原始语法中,并且规则2b适用于它们中的每rule 2::语法NT符号Trafo[Prod]规则2语法a b| isTerminal b = return [rule2a a b b]56A. Baars等人理论计算机科学电子笔记253(2010)51←否则= do let Just prods = Map。查找B文法rs mapM(rule 2b grammar a a b)prodsreturn(concat rs)其中ab=a++“_”++b注意,函数rule2和insert是相互递归的。 他们应用规则2a和2b,直到没有新的左角符号被发现。我们在第4节中提出的类型化实现的结构与上面的非类型化解决方案非常相似。3类型转换LC变换的类型化版本是通过使用我们在一篇配套论文[1]中描述的库(TTTAS4)来实现的,以执行类型化抽象语法(在我们的情况下是类型化语法)的类型化变换。在下面的小节中,我们将介绍用于表示类型化抽象语法的基本构造和用于操作它的库接口。3.1类型化引用和环境Pasalic和Linger [8]引入了一种类型化引用的编码Ref,指向包含不同类型值的环境。Ref实际上是一个索引,标记有引用值的类型和环境的类型 (一个嵌套的笛卡尔乘积,向右增长)值存在于:数据引用环境,其中Zero::Ref a(envJ,a)Suc::Ref a envJ→Ref a(envJ,b)类型Ref是一种广义代数数据类型[10]。构造函数Zero表示环境的第一个元素必须是类型a。Suc不关心环境中第一个元素的类型(它在b中是多态的),并记住环境中其他元素的位置我们扩展了这个想法,使环境不包含混合类型的值,而是包含描述这些值的术语(表达式);这些术语采用一个额外的类型参数来描述环境,其中对术语中出现的其他术语的引用可能指向该环境。通过这种方式,我们可以描述包含对其他术语的类型化引用的类型化术语。因此,一个Env可以用来表示一个环境,由一组可能相互递归的定义组成。环境存储了一个使用类型的术语的异构列表,这些术语是定义的右手表达式。对元素的引用由列表中的索引data Env term use def其中Empty::Env t use()Ext::Env t use defJ→t a use→Env t use(defJ,a)类型参数def包含在环境中使用的类型ta的术语的所有类型标签a当使用Ext将术语添加到环境中时,其类型标签将作为def的第一个组件包含在内。类型使用描述了4http://hackage.haskell.org/cgi-bin/hackage-scripts/package/TTTAS。|A. Baars等人理论计算机科学电子笔记253(2010)5157→→可以使用Ref a usevalues从typet a use中引用的类型。当类型def和use重合时,类型系统确保术语中的引用不会指向环境之外的值函数lookupEnv接受一个引用和引用所指向的环境。在lookupEnv类型中出现两个lookupEnv::Ref a env Env t s env t a slookupEnv零(外部t)= tlookupEnv(Suc r)(Ext ts)=lookupEnv r ts3.2转换库该库基于Trafo类型,它表示类型化的转换步骤。每个转换步骤(可能)都扩展了一个隐式维护的环境Env。dataTrafo m t s a b = Trafo(traffenv1. menv1→TrafoE m t s env1 a b)参数m代表变换的可观测状态的类型。Trafo接受这样一个状态值,它依赖于到目前为止构建的环境,作为输入,并产生一个对应于(可能扩展的)环境的新状态。类型t是存储在环境中的术语的类型。 类型变量s表示最终结果的类型,它在嵌入引用中作为use参数传递。我们以箭头样式组合转换。参数a和b分别是ArrowArrow库[5]包含一组函数,用于构造和组合Arrow类的实例值。此外,还有一个方便的符号[9]用于使用Arrows编程。这个符号的灵感来自Monads的do符号。类ArrowLoop被实例化以能够构造反馈循环。TTTAS库包括一个组合子,类似于Monads的序列组合子,它将一系列转换组合成一个单一的大转换:序列A::[Trafo m t s a b]→Trafo m t s a[b]每个单独的变换都将输入a映射到值b上。按顺序应用各个转换所产生的组合结果b以列表[b]的形式返回。构造器Trafo包含一个函数,它将当前环境中的状态映射到实际的转换,由TrafoE类型表示。因为TrafoE类型的内部细节在这里无关紧要,所以我们不给出它的定义;我们只给出它的构造函数:extEnv::m(e,a)→TrafoE m t s e(t a s)(Ref as ) castSRef : : m e→Ref a e→TrafoE m t s e i( Ref a s )updateSRef::m e→Ref a e→(i→t a s→t a s)→ TrafoE m t s e i(参考文献)函数extEnv构建一个TrafoE,它接受一个类型化的术语(类型为t a s)作为输入,将其添加到环境中,并在最后的环境(S)。extEnv的参数是一个依赖于58A. Baars等人理论计算机科学电子笔记253(2010)51→→∀扩展环境(e,a)。因此,例如,可以实现扩展环境而不保留任何内部状态dataUnit env=UnitnewSRef::Trafo Unit t s(t a s)(Ref as)newSRef=Trafo(λ→extEnv Unit)函数castSRef构建一个TrafoE,它返回作为参数传递的引用(在当前环境中),并转换到最终环境。函数updateSRef构建一个TrafoE,更新传递的引用所指向的值请注意,更新函数(类型it a st a s)可以使用绿箭侠类型(TrafoE m ts e a)是类Functor的实例,因此函数fmap::(b→c)→TrafoE m t s e a b→TrafoE m t s e a c提升一个类型为(b→c)的函数,并将其应用于Arrow的输出。当我们运行一个转换时,我们从一个空的环境和一个初始值开始。由于这个参数类型被标记为final environment,我们还不知道,它必须是一个多态值。runTrafo::(运行。Trafom t s a(b s))→m()→a→结果m t b结果包含最终状态(m s)、输出值(b s)和最终环境(Env t s s)。因为一般来说我们不知道有多少新的定义和哪些类型是由变换引入的,所以结果在最终环境s中是存在的。 尽管如此,我们可以强制环境 待关闭:data结果m t b = 0 s。 结果(m s)(b s)(环境t s s)4类型化的左角变换对于LCT的类型化版本,我们需要语法的类型化表示。一个语法由一个开始符号和一个Env组成,开始符号表示为一个引用,引用的类型作为成功解析的见证值,Env包含每个非终结符的产生式列表。 实际的env类型,描述了与非终结符相关联的类型,使用存在量化隐藏:dataGrammar a = env. 语法(参考环境)(Env Productions env env)newtypeProductionsaenv=PS{unPS::[Prodaenv]}由于在我们的LCT中,我们希望能够轻松访问生产的第一个符号,因此我们选择了一种便于实现这一点的表示法。因此,顺序构图中元素的类型与通常的构图略有不同[11],这样Seq就可以被选择为右关联。 类型的选择是这样的,如果我们用Endf元素关闭右边的符号序列,那么这个f是一个函数,它接受前面元素的结果(右边的解析结果)作为参数,并构建 左侧非终结符的解析结果。在我们的例子中,产生式是一个符号序列,而符号要么是一个以String作为见证的终结符,要么是一个非终结符(引用):dataSymbol::→→其中Nont::Ref a env→Symbol aenvTerm::String→Symbol String envA. Baars等人理论计算机科学电子笔记253(2010)5159dataProd::→→其中序列::符号b env→生产(b→a)env→生产a env结束::a→生产a env为了使我们的文法类似于普通文法,我们引入了一些额外的运算符:在fixr5' cons '中,. - 是的consprods g = Ext g(PSprods)(. - 是的)=Seq我们现在有了编码示例语法的机器A=Nont ZeroB=Nont(SucZero)a=术语“a”b=术语“b”c=术语“c”假设我们希望非终结符A的见证类型为String,非终结符B的见证类型为Int:语法::语法字符串grammar=Grammar零生产type类型nts=(),Int),String)productions::Env Productions Types nts Typesntsp roductions=[a. -是的 A. -是的结束(++)、B. -是的 结束表演]' cons'[A. - 是的 B. - 是的结束(λy x→长度x+长度y),c. -是的 End(const 1)]'cons'Empty在深入研究LCT本身之前,我们介绍一些我们需要的语法相关函数:append::(a→b→c)→Prod a env→Symbol b env→Prod c envmatchSym::Symbol a env→Symbol b env→Maybe(Equal ab)mapProd::T env1 env2→Prod a env1→Prod a env2函数append在LCT中用于构建形式为βX A的产生式。基本上它对应于列表上的snoc操作;我们只需要确保所有类型都匹配。函数matchSym比较两个符号,如果它们相等,则返回证明类型a和b相等的证明(Equal函数mapProd系统地更改生产中出现的所有对非终结符的引用。它使用Ref-Transformer(T env 1 env 2)将环境env 1中的引用转换为环境env 2中的引用。newtypeT env1 env2 = T {unT::numx. 参考x环境1 →参考x环境2}4.1类型化转换LCT依次应用于原始语法的每个非终结符(A)。该算法对左角符号执行深度优先搜索。对于每个左角X,引入一个新的非终结符A X。 此外,A本身的新定义被添加到转换后的文法中。在无类型实现中,我们简单地使用字符串来表示非终结符。但是,在类型化解决方案中,非终结符表示为类型化引用。第一次生成一个非终结符A X的产生式时,我们必须为这个非终结符创建一个新条目,并记住它的位置。当生成这样一个A X的下一个产生式时,我们必须将它添加到这个A X的已经生成的产生式中:因此,我们维护了一个从遇到的左角符号(X)到对应于非终结符(A X)的引用的这60A. Baars等人理论计算机科学电子笔记253(2010)51→finite map再次缓存已经遇到的左上角符号:newtypeMapA X env a env2=MapA X(x. 符号x env →可能(Ref(x → a)env2))类型变量env来自原始文法,并且env2是迄今为止构造的新文法的类型。类型变量a是当前非终结符的类型。标记为x类型的左角符号映射到对新语法中非终结符A X定义的引用,前提是它是在前面插入的。与形式A X的非终结符相关联的类型是(x a),即当传递符号X的语义时,返回A的语义的函数。空映射定义为:emptyMap::MapA X env a env2emptyMap=MapA X(const Nothing)我们引入了类型同义词LCTrafo,这是LCT的变换步骤的类型。我们的术语的类型是Productions,内部状态是一个MapAX类型的表,包含遇到的左上角符号。typeLCTrafo env a=Trafo(MapA X env a)制作接下来我们定义函数newNontR,它是函数newSRef的一个特殊版本,使用MapA X作为内部状态而不是Unit。它以左上角的符号X作为参数,并产生一个LCTrafo,引入一个新的非终结符AX。LCTrafo的输入是A X的第一个生产(Productions),输出是对这个新添加的非终端的引用newNontR::nextx env s a. Symbol x env→LCTrafo env a s(Productions(x →a)s)(Ref(x →a)s)newNontR x=Trafo$λm →extEnv(extendMap x m)符号X通过函数extendMap添加到A的左角映射中,该函数记录了新发现的左角是环境的第一个元素(零),而之前添加的元素必须移动一个位置(Suc)。extendMap::Symbol x env→MapA X env a envJ→MapA X env a(envJ,x→a)extendMap x(MapA X m)=MapA X(λs→casematchSym s xofJust Eq→Just Zero Nothing→fmap Suc(m s))存储A的新定义的索引通常与原始语法中A的索引不同。 这是一个问题,因为我们需要将原始语法的部分(规则中的β)复制到新语法中。这些部分中的非终结符引用必须调整为新索引。为了实现这一点,我们首先将原始语法的非终结符的所有新引用收集到一个有限映射中,然后使用该映射计算Ref-Transformer 其随后被传递并用于将引用从原始语法转换为新语法中的对应引用。这个有限图的类型是:newtypeMapping o n=Mapping(Env Ref n o)映射被表示为Env,并且对于旧语法的每个非终结符,包含新语法中的对应引用。该映射可以很容易地转换为Ref-Transformer:map2transs::映射env s→Tenv smap2transs(Mapping env)=T(λr→(lookupEnv r env))A. Baars等人理论计算机科学电子笔记253(2010)5161→→∀→→→→→→≺→→→现在剩下要做的就是把上面定义的所有部分粘在一起。 每个以下函数中的一个对应于具有相同名称的非类型化版本。我们从函数insert开始:插入::env s a x. Env Productions env env Symbol x envLCTrafo env a s(Tenv s,Prod(x a)s)(生产a s)插入旧克x=Trafo(λ(MapA X m)案例mx只是r→extendA X(MapA X m)r无→insNewA X(MapA X m))哪里Trafo insNewAX=proc(tenv s,p)→dor←newNontR xPwps[p]规则2旧克x(tenv s,r)该函数接受原始语法和左上角符号x作为输入。它产生一个转换,该转换将Ref-Transformer作为从原始语法到新(转换后的)语法的输入和非终结符A X的产生,并将该产生存储在转换后的语法中。如果符号x是新的(m x返回Nothing),则将结果存储在新的索引中(使用newNontR),并应用函数rule2,以继续对左角进行深度优先搜索。 如果我们已经知道x是a的左角,那么我们得到一个索引r到先前添加到非终结符A X的,并在这个位置添加新的产生式。函数extendA X将执行此更新的TrafoE返回到环境中:extendA X::m env1 Ref(x a)env1TrafoE m Productions s env1(T env s,Prod(x a)s)(Productions a s)extendA X m r=fmap(const$PS[])$updateSRef m r addProd其中addProd(,p)(PS ps)=PS(p:ps)如果在函数rule 2中,左上角是一个终端符号,则应用rule 2a,并将新的产生式规则作为Arrow-output返回。如果左角是非终结符,则在原始语法中查找对应的产生式,并且将规则2b应用于所有产生式,从而扩展正在构造的语法:rule 2::Env Productions env env Symbol x envLCTrafo env a s(T env s,Ref(xa)s)(生产a s)规则2(术语a)= proc( ,a x) return A PS[rule2a a a x]rule2old gram(Nont b)=caselookupEnv b oldgramPS ps→proc(tenv s,a x)→dopss←sequenceA(map(rule2b old gram)ps)(tenv s,a x)returnAPS(concatMap unPS pss)我们现在定义函数rule2a和rule2b,它们实现了LCT的相应规则。首先,规则2a,它不引入新的非终结符,而是简单地为所考虑的非终结符(A)提供新的产生式。规则2a的执行情况如下:rule2a::String→Ref(String→a)s→Prod a s rule2aa refA a=Term a. - 是的不参考a. - 是的 结束(美元)函数rule 2b将原始语法和来自原始语法的产生式作为自变量,并且产生将Ref-Transformer和非终结符A-B的引用作为输入的转换,并且构造随后插入的新产生式。请注意,Ref-Transformertenv s应用于beta中的非终结符引用,以将它们映射到相应的→62A. Baars等人理论计算机科学电子笔记253(2010)51≺→→→→→→∀→新语法中的引用。rule2b::Env Productions env env Prod b envLCTrafo env a s(T env s,Ref(b a)s)(生产a s)规则2b旧gram(Seq x beta)=proc(tenv s,a b)插入旧的gram x(tenv s,ap pend(. ))(mapProdtenvsbeta)(Nontab))函数rule 1与rule 2b几乎相同;唯一的区别是它处理直接的左角,因此不涉及rule 1::Env Productions env env生产环境LCTrafo env a s(T env s)(Productions as)rule 1 old gram(Seq x beta)=proctenv s→插入旧的gram xxgram(tenv s,mapProd tenv s beta)函数rules1是通过对原始语法的归纳来定义的(即它迭代非终结符),第二个参数作为归纳参数。它是多态递归的:类型变量envJ在归纳过程中发生变化,从原始语法的类型(即env)开始,以空语法的类型()结束。第一个参数是原始文法的副本,这是查找原始非终结符的结果所必需的rules1::Env Productions env env→Env Productions envJenvJ→Trafo Unit Productions % s(T env % s)(映射env % s)rules1空=进程→returnAMappingEmpty rules 1 oldgram(Ext ps(PS prods))= proctenv s→ dop←initMap nt初始化r←newSRef文件Mapping e←rules1 old gramps tenvs return映射(Ext e r)哪里nt=proctenv s→dopss←sequenceA(map(rule 1 old gram)prods)返回的序列APS(concatMap unPS pss)rules1的结果是表示为Trafo类型的值的完整转换。 在顶层,转换不使用任何状态,因此类型为Unit。当处理一个非终结符(nt)时,规则1被应用于它的每个产生式,新的产生式被收集以插入到新的语法中。函数initMap初始化转换nt的状态信息,其中包含一个空的左角表。initMap::LCTrafo env a s c d→Trafo Unit Productions s c dinitMap(Trafo st)=Trafo(λ→casest empty映射TrafoE f→TrafoE Unit f)作为输入,rules 1返回的转换需要Ref-Transformer将旧语法的非终结符重新映射到新语法。在转换过程中,rules 1插入原始语法的非终结符的新定义,并记住这些非终结符在Mapping中的新位置。这个映射可以被转换成所需的参考-Transformer,它必须被反馈作为箭头输入.这个反馈循环是在函数leftcorner中使用mdo-notation进行的:leftcorner::a. Grammar a Grammaraleftcorner(Grammar startproductions)=caserunTrafo lctrafo单位数A. Baars等人理论计算机科学电子笔记253(2010)5163→→⊥结果(T tt)gram语法(tt start)gram哪里lctrafo=proc mdolettenv s=map2transmenv smenv s←(rules1 productions productions)menv sreturnAmenv s生成的转换使用作为输入运行;这是完全安全的,因为它根本不使用输入:结果是一个新的开始符号和转换后的产生式规则,它们组合在一起形成新的语法。5结论我们已经展示了如何在运行时完成复杂的转换,同时通过类型系统进行部分静态验证。这样做,我们使用了各种类型系统概念,如GADT和存在类型和多态类型,这些概念在Haskell之外的其他通用语言中无法找到。这允许我们使用依赖类型系统的典型技术,同时保持类型和值之间的完全分离。除此之外,我们还使用了惰性计算,以便将计算信息提供给 正确的地方可以使用。实现像左角变换这样的变换意味着引入对可能相互递归定义的集合的新引用。先前关于嵌入式DSL的有类型转换的工作表示为类型化抽象语法[3,2,4]并没有处理这种复杂性。 因此,据我们所知,这是运行时类型转换的第一个描述,它将引用修改为表示为图而不是树的抽象语法我们已经展示了如何将转换的非类型化版本转换为类型化版本;在研究了这个示例之后,使用TTTAS库实现类似的转换应该相对简单。尽管这种转变是相当系统的,但它仍然是一个主题,未来的研究,看看如何自动完成这种转换引用[1] Arthur Baars,S. Doaitse Swierstra和Marcos Viera。类型化抽象语法的类型化转换。 在TLDIACM。[2] 阿瑟岛Baars和S.多艾兹·斯维尔斯特拉类型安全,自检代码。 HaskellPress.[3] 陈炽炎和Xi宏伟。实现有类型的程序转换。在PEPM[4] 路易斯-朱利安·吉耶梅特和斯特凡·莫尼耶。haskell中的类型安全代码转换。 电子笔记理论Comput.Sci. ,174(7):23[5] 约翰·休斯。把单子推广到箭头。Science of Computer Programming,37(1-3):67-111,2000.[6] M.约翰逊使用左角文法转换的约束文法的最佳状态近似。在COLING-ACL 98,蒙特利尔,魁北克,加拿大,第619-623页中。计算机语言学协会,1998年。64A. Baars等人理论计算机科学电子笔记253(2010)51[7] Robert C.摩尔从上下文无关文法中移除左递归。在计算语言学协会北美分会第一次会议的会议记录中,第249-255页摩根·考夫曼出版公司[8] 埃米尔·帕萨里克和内森·林格使用类型化对象语言表示的元编程。在生成式编程和组件工程(GPCE[9] 罗斯·帕特森箭头的新符号。函数式编程国际会议,第229ACM Press,2001.[10
下载后可阅读完整内容,剩余1页未读,立即下载
![application/msword](https://img-home.csdnimg.cn/images/20210720083327.png)
![application/msword](https://img-home.csdnimg.cn/images/20210720083327.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://profile-avatar.csdnimg.cn/default.jpg!1)
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
我的内容管理 收起
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
会员权益专享
最新资源
- 京瓷TASKalfa系列维修手册:安全与操作指南
- 小波变换在视频压缩中的应用
- Microsoft OfficeXP详解:WordXP、ExcelXP和PowerPointXP
- 雀巢在线媒介投放策划:门户网站与广告效果分析
- 用友NC-V56供应链功能升级详解(84页)
- 计算机病毒与防御策略探索
- 企业网NAT技术实践:2022年部署互联网出口策略
- 软件测试面试必备:概念、原则与常见问题解析
- 2022年Windows IIS服务器内外网配置详解与Serv-U FTP服务器安装
- 中国联通:企业级ICT转型与创新实践
- C#图形图像编程深入解析:GDI+与多媒体应用
- Xilinx AXI Interconnect v2.1用户指南
- DIY编程电缆全攻略:接口类型与自制指南
- 电脑维护与硬盘数据恢复指南
- 计算机网络技术专业剖析:人才培养与改革
- 量化多因子指数增强策略:微观视角的实证分析
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)