形式语法的模块化生成奥尔良大学（University ofOrleans）MIPTIS博士学校数学、计算机科学、理论物理和系统工程奥尔良基础计算机科学实验室论文提交人：西蒙·佩蒂让2014年12月11日支持获得以下学位：奥尔良大学博士学位学科/专业：计算机科学这是由IRIGeEpaR：Denys Duchier奥尔良大学教授ET-CCCREPAR：Yannick PARMENTIER奥尔良大学讲师RPORTEUR S：Laura KALLMEYER杜塞尔多夫大学教授Kim Mens鲁汶天主教大学教授考试主持人：Claire GARDENT，CNRS研究总监，LORIA，评审团主席Olivier BONAMI巴黎索邦大学讲师Ericde laClergerieINRIA RocquencourtAnn Copestake剑桥大学教授谢谢你J’aimerais为了意识到与丹尼斯和雅尼克一起工作是多么令人羡慕，我在每次旅行中都能提到他们的名字，并看到我的对话者的眼睛亮起来我特别感谢他们在过去几个月的写作中表现出极大的耐心，并在我提出要求时随时待命。能在这样的评审团面前展示我的作品是我莫大的荣幸感谢评审团成员我要感谢我的合作者，与他们一起工作是一种巨大的乐趣：布鲁内尔，埃姆-曼努埃尔，尼古拉，蒂姆，亚历山大，博贾纳。我和他们的讨论实际上是我论文的娱乐。当面对如此规模的挑战时，感到孤独和迷失并不罕见。我在暑期学校或会议上遇到的人在LIFO工作的这些年过得太快了，主要是因为这个实验室里有很多很棒的人。感谢所有欢迎我的人我特别感谢朱利安、海伦、尼科、西尔万、安东尼、巴斯蒂安、马蒂厄、马蒂厄、马克西姆、大卫、弗洛朗、纪尧姆、艾哈迈德、约汉、伊万、阿里。我认为唯一的方法，使这个名单不那么不完整的是发送还要感谢Florence、Isabelle和Brigitte感谢那些没有他们生活在奥尔良往往会非常悲伤：拉波特，本尼迪克特，大卫，弗朗索瓦，弗吉尼亚，其他J’ai notamment passé de très bons 那些被遗忘的日子变成了美好的回忆，感谢那些从未抛弃过我的朋友J’aimerais également remercier Leila, sans qui jen’aurais probablement jamais eu l’idée ni le courage de me lancer dans une aventure aussi最后，我显然要感谢我所有的家庭成员，感谢他们的持续支持和坚定的信念。没有任何迹象表明我的命运是有一天成为一名这是一条漫长的道路，但我的父母给了一切，使它不那么迪fficile，特别是让我画一个我想要的。这篇论文自然是献给他们的西蒙总结导言九I最新技术水平第1章：专用于自动语言31.1研究对象 . . . . . . . . . . . . . . . . . . . . . ... ...31.2用于描述语言的正式工具。 . . . . . . . . . . . . . . . . . . ... ...41.2.1多层次 . . . . . . . . . . . . . . . . . . . . . ... ...41.2.2各层之间的接口。 . . . . . . . . . . . . . . . . . . ... ...81.3对专用语言13第二章： 描述形态152.1导言152.2通过统一进行形态学分析162.2.1PFA162.2.2网络形态172.3有限状态自动机的形态学分析182.3.1两级形态学192.3.2PARSLI202.4结论21第三章： 描述语法233.1导言233.2通过重写字符串243.2.1断章取义的语法243.2.2功能词汇语法293.2.3由头部313.3通过树重写的生成语法3.3.1伴随树的语法3.3.2基于元规则的383.3.3元语法方法393.3.4可扩展元语法413.4基于50种模式理论的语法3.4.1可扩展依赖语法503.4.2属性语法54ii摘要3.5结论55第四章： 编译器的构建574.1导言574.2编译器的编译器584.2.1 CDL3584.3编译器特定组件的生成604.3.1使用Yacc 60生成4.3.2使用Parsec 61生成4.4DSL62的模块化结构4.4.1梦幻岛624.5第64章II模块化编译器65导言67第五章： 不同的模块化级别695.1导言695.2需要模块化695.3不同类型5.4模块化架构715.5语言模块化725.6模块化5.7编译器和执行器的模块化5.7.1编译器755.7.2执行者755.8结论76第六章： 专用语言的模块化汇编776.1导言776.2使用专用语言776.3丰富语言786.4语言的砖块806.4.1创建80块砖6.4.2连接81块砖6.4.3DSL 84的组装6.5结论85第七章： 编译器的模块化组件877.1第88章7.1.1汇编的步骤887.1.2将规则分成89块7.1.3EDCG90摘要iii7.1.4属性变量91iv摘要7.2阶段 分析中 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ...937.2.1句法分析。 . . . . . . . . . . . . . . . . . . . . . . . . . . ...937.2.2词汇分析。 . . . . . . . . . . . . . . . . . . . . . . . . . . . . ...957.2.3连接砖块。 . . . . . . . . . . . . . . . . . . . . . . . . . ...957.3阶段 和打字。 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ...977.3.1原则。 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ...977.3.2数据的类型。 . . . . . . . . . . . . . . . . . . . . . . . . . . ...987.3.3控制语言的类型。 . . . . . . . . . . . . . . . . . . . . ... 1007.3.4类的类型。 . . . . . . . . . . . . . . . . . . . . . . . . . . ... 1017.3.5维度的类型。 . . . . . . . . . . . . . . . . . . . . . . . . ... 1027.3.6类型化算法。 . . . . . . . . . . . . . . . . . . . . . . . . . ... 1047.3.7植入。 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ... 1067.4阶段从展开 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ... 1077.4.1原则。 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ... 1077.4.2展开的形式化。 . . . . . . . . . . . . . . . . . . . . . . ... 1087.4.3示例 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ... 1117.4.4植入。 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ... 1137.4.5可扩展性。 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ... 1137.5阶段一代人。 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ... 1147.5.1原则。 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ... 1147.5.2形式化和实施。 . . . . . . . . . . . . . . . . . . . . . ... 1157.5.3可扩展性。 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ... 1187.5.4特定于类的代码。 . . . . . . . . . . . . . . . . . . . . . . ... 1197.6砖制造商1217.7执行的入口点7.7.1启动7.7.2定义累加器1237.7.3生成的代码1247.8XMG-1125的示例7.9结论127第八章： 发电机的模块化组件1318.1导言1318.1.1131发生器的结构8.1.2示例1328.2执行步骤8.3解决步骤1348.3.1求解器和原理1348.3.2解决方案1358.3.3原则和插件1358.3.4求解器块1358.3.5将求解器与维度136关联8.4序列化步骤137摘要v8.4.1功能1378.4.2可扩展性1388.5结论138第九章： 比较和结论1419.1导言1419.2比较1419.2.1结构相似性1419.2.2比较1439.3结论145模块化DSL汇编在语言资源描述中的应用导言149第10章语法的应用15110.1 联接树语法10.1.1 语言问题15110.1.2 砖的建造15210.1.3 编译器的组装15410.2 交互语法10.2.1 语言问题15410.2.2 砖的建造15610.2.3 编译器的组装15710.3 结论158第十一章形态学的应用16111.1 语言学问题：Ikota161中的言语形态学11.1.1 基本块16311.1.2 衍生物示例16411.1.3 表面语音学16511.2 砖的创建16511.2.1 用于描述有序字段16511.2.2 用于形态描述的16611.3 编译器的组装16811.4 结论169第十二章语义学的应用17112.1 语言问题17112.1.1 树骨架和框架的因式分解12.1.2 一个新的框架尺寸>173vi摘要12.2 砖的建造17312.2.1 用于定义类型17312.2.2 用于描述帧的17412.3 编译器的组装17512.4 结论176一般结论179第179章前景181附件183附录A. 扩展工具185导言185订单185编译器185创建捐款186附录B.音乐应用187导言187编译器188音乐维度>188原则189维度之间的相互作用190号出口音乐和弦的元语法190直觉190说明注释190描述间隔192协议的描述193协议的进展参考书目197摘要vii图表1.1法语片段的断章取义的语法。 . . . . . . . . . . ... ...61.2短语"猫吃老鼠"的。 . . . . . . ... ...61.3短语"猫吃老鼠"的依赖关系图。 . . . . . ... ...71.4图形形式的语义表示 . . . . . . . . . . . ... ...81.5标称组的表示1.6标称组"一只老鼠"102.1传统网络2.2HFST19语法2.3用PARSLI20描述动词Balayer的弯曲3.1PATR II规则示例283.2PATR II28词典示例3.3句子"John Loves Mary"3.431个名称的继承层次结构3.5TAG35中的替换3.6L’adjonction en TAG3.8带规范主语和规范宾语的动词或摘录363.7 TAG37中的一个助动词族3.9MGCHP类示例（来自[Thomasset和Clergerie，2005]）403.10 具有规范主语和相对宾语的413.11 规范主语、关系宾语和主动动词形态的TAG树片段3.12 规范主语和规范宾语的423.13 无约束的组合463.14 颜色的统一规则。..........................................................................................................463.15 彩色元素树473.16 按颜色过滤的组合473.17 用等级48原则装饰的碎片3.18 按48级原则筛选后的唯一模型3.19 依赖性分析示例3.20 词汇输入示例3.21 "wants"的词汇输入（摘自[DebUsmann，2006]）523.22 XDG52形式体系中单词wants的词汇输入3.23 法语属性语法片段基本）554.1Neverlang切片的定义图表vii4.2Neverlang 64语言的定义5.1L’architecture modulaire de XMG5.2L’architecture du compilateur5.3L’architecture de l’exécuteur6.1树片段的示例6.2用特征结构装饰的树碎片的示例6.3一种断章取义的语法，用于用树装饰树的描述第79章第一次见面6.4通过外部非端子816.5使用同一框的多个实例的程序集6.6递归结构的砖连接836.7用于描述包含原子双结的特征结构的砖的组装837.1编译器887.2L’architecture du compilateur7.3L’architecture du compilateur et les langages manipulés7.4特性结构的赋值变量库927.5从类型代码（syn）107中提取7.6从解文件夹（avm）114中提取的代码7.7为语法描述1187.8包含语法描述1197.9为类1207.10 为类生成的代码（在解释GCED之后）1207.11 生成的edcg.yap文件示例1247.12 L’assemblage d’un compilateur recréant le XMG existant7.13 砖块之间的连接1267.14 L’architecture d’une brique (avm)7.15 L’architecture d’une brique (syn)7.16 装配砖（synsem）的结构8.1L’exécuteur8.2L’architecture du générateur8.3L’architecture du générateur de XMG-18.4第136号决议的步骤8.5使用插件解决问题的步骤1368.6求解器块（树）的结构8.7L’architecture d’une brique (syn)8.8装配砖（synsem）的结构9.1L’architecture modulaire de XMG9.2L’architecture modulaire de Neverlang10.1 彩色元素树15210.2 彩色初等树的XMG代码15310.3 用于编译synsem 155的compiler.yaml文件10.4 交互语法156的摘录八、图表10.5 交互语法摘录10.6 交互语法分析10.7 交互语法中树描述的XMG代码10.8 polAvm159砖的lang.def文件10.9 用于组装ig 160编译器的.yaml文件11.1 Ikota 164的语言形态的元语法11.2 一个成功的16511.3 一个失败的衍生：时间冲突和prog16511.4 fields166砖的lang.conf文件11.5 有序字段序列的示例定义11.6 对变形维度的贡献示例>16711.7 来自morph167砖的lang.def文件11.8 用于编译morphtf 168的编译器.yaml文件12.1 与组合词、其语义对应物和层次结构相关联的树模式相关类型17212.2 图12.1中树模式和框架的元语法分解12.3 POConstr175框架规范12.4 特性结构类型约束的示例规范17512.5 类型176层次结构的lang.def文件12.6 框架尺寸>177的lang.def文件12.7 用于编译SynFrame 178的编译器.yaml文件1XMG180的模块化点2和弦序列的树表示3在XMG190中组合和弦的片段4生成的21个注释192517个大三度产生193618个小三度产生193717个大三和弦和小三和弦产生194815个降七和弦生成195个9C大调及其相对小调195简介围绕软件开发的社区是其发展的决定性因素。在自由软件的世界里尤其如此，在自由软件的世界里，在编程语言的情况下，不同的社区可以根据编程范例形成，然后根据实现这些副数字的语言形成。根据用户的需要他们还可能不得不在几种语言之间交替使用，或者在表达方式不再合适时将它们组合在一起L’objectif这个想法的主要问题是，开发新的编译器是一项需要专业知识的复杂我们的假设是模块化是这个问题的关键因此，我们提出的方法是基于将编译器切割如果我们依赖于这种模块化，那么基于自己组装的语言构建一个适应其需求的编译器就相当于组合砖块。编译过程的编码完全位于构建块中，这意味着L’objectif这种方法还促进了编译器的可扩展性。编写新的编译器功能（例如，支持新指令）类似于创建一块砖。实现砖之间的完全独立性意味着可以设计新的砖，而不必考虑其与现有砖的接口。L’assemblage de cette nouvelle brique à un compilateur existant constitueune编译器生成方法通常针对特定类型的编译器。在本文中，我们提出了一个编译器的编译器作为语言资源生成的一部分这项任务意味着能够描述结构，有时是复杂的或众多的，允许自然语言的建模。因此，这些编译器识别的语言是专用语言（或DSL，域特定LAN语言）。我们将详细介绍将X简介基本部件。我们还提供了对这个编译器有贡献的方法，解释了砖块是如何组成的。本论文的主要目的是为语言资源的生成领域做出贡献。我们将组装的专用语言特定于对组成语言的规则的描述。因此，由我们的方法组装的编译器所处理的指令的数量在第一部分中，我们将介绍最新的技术水平，以及激发模块化需求的背景。在第二部分中，我们将详细介绍贡献，即描述语言和编译链的划分方法。最后，在第三部分中，我们将通过模块化地组合几个专用于不同语言资源生成任务的编译器来集中验证该第一部分最新技术水平用于自动语言总结1.1研究主题1.2描述语言的41.2.1多层次1.2.28级之间的接口1.3对专用语言13本章介绍在自动语言处理中使用专用语言所涉及的问题首先，我们将定义在第二步中，我们将强调使语言资源描述成为一项复杂任务的各个方面，这需要专用的工具。1.1研究对象本文的框架是自动语言处理（TAL，见[Clark et al. [2010]），其最终目标是使机器能够操纵与人类相同的语言。这涉及到大量为了能够成功地执行这些任务，可以考虑两种主要方法第一种方法（自下而上）从例子开始，通过学习在第二种情况下，我们给出了语言知识的描述，例如，由专家制定的语法规则（例如，见[Mitkov，2003，ch. 4、8、12、18、26）。对于自下而上例如，在机器翻译的上下文中，这种类型的方法相当普遍，特别是自20世纪90年代以来（与[Brownet al. [1993]。它们通常依赖于从两个对齐的语料库中学习，即源语言的短语库及其到目标语言的翻译。尽管基于学习的方法很简单，但它仍然是有限的，特别是因为它对语料库的1第一章专用于自动处理的语言，语言4在自上而下的情况下，语言的表示是可用的，但它必须首先被形式化，以便在本文件的其余部分描述语言是什么？这 个 问题的答案取决于一个人选择把自己放在什么样的语言表征水平上。可以提到的第一个层次是形态学（例如， 例如，would follow是动词follow的一种形式，它的语气是虚拟语气，它的时态是现在时态，它对应于第三人称复数。相反的任务是生成弯曲的形状。专门用于此任务的程序将单词描述作为输入，并构建执行此任务的所有单词。例如，我们可能希望生成动词"follow"的所有复数形式（即所有模式、所有时态、所有人）。L’étude 它在广泛的应用中尤其重要，如机器翻译（[Koehn，2010]）、对话系统（[Wupkowski和Purver，2010]）、问答系统（[Harabagiu和Moldovan，2003]）和语法更正。. ...语义学是研究句子或单词意义的学科。它是在 此外，该响应可以为了能够操作自然语言，计算机必须使用语言元素的表示。例如，对于给定的输入短语，它必须能够提取任务所需的信息，例如，该任务可以是将该短语翻译成另一种语言。所提取的信息通常是句子的句法分析（识别句子的各种成分的功能）和/或句子的意义的表示。1.2描述语言为了实现对语言的描述，我们已经提到了语言的不同层次的表示，有必要我们将看到，这些结构是异质的，这不仅是因为研究水平的多样性最后，我们将讨论不同学习层次之间的相互作用问题。1.2.1多个级别即使在选择了语言表示级别之后，也有几种工具可以用来描述它。我们将用两个语法和语义表示的例子来说明这一点，然后我们将分析表示级别之间的划分。
我的内容管理
展开
