一种特殊的上下文无关文法及其语法分析

SAQ系统是一个进行软件规约获取、检验和复用的实验系统，其中以上下文无关文法表示的概念是规约的一部分.SAQ要求将概念的词法和句法定义结合在一个上下文无关文法中.如果用常规的上下文无关文法描述诸如程序设计语言和自然语言等一些复杂概念的语法，则需要把诸如空格和回车等没有实质意义的分隔符包含到语法中去(这种描述方法称为朴素表示法),使得语法描述很累赘.为此，作者设计了一种特殊的上下文无关文法,它把通常上下文无关文法定义中的非终极符集合和终极符集合进行细化.用这种文法可以相对简洁地描述程序语言和自然语言等复杂概     

国标BASIC语言实现中的集成化编程支持环境

本文介绍了在国家“七五”科技攻关项目“国标BASIC语言的实现”中所设计实现的一个集成化编程支持环境。它以语法树作为环境内部的唯一存贮形式,使环境中各部分共享这一统一的内部表示。本文介绍了该环境的结构、功能特点及实现,着重介绍了语法制导的编辑器以及程序的正文表示形式和语法树表示形式之间的相互转换,同时阐述了该环境对自顶向下逐步求精的程序设计方法学的支持。     

结合结构下文及词汇信息的汉语句法分析方法

针对句法分析中上下文无关语法模型对句子信息利用的不足,通过融入结构下文和部分词汇信息,提出两种基于概率上下文无关语法模型的短语结构消歧方法,以达到消解结构歧义的目的;引入分层分析的算法,通过损失一定的时间效率使得在提高分析准确率的同时保证分析结果的全面性。实验结果表明,融入结构下文及词汇信息的汉语句法分析方法,利用了更多的句子信息,与上下文无关语法相比有着更强的消歧能力。     

一种建立控制依赖子图的方法

提出一种基于GCC(GNU Compiler Collection)抽象语法树文本建立控制依赖子图的方法,消除抽象语法树文本中与分析控制流无关的信息,将消除冗余后的抽象语法树文本转化为以邻接表为存储结构的抽象语法树的算法,从而高效地完成了抽象语法树的解析。基于以邻接表为存储结构的抽象语法树建立了控制依赖子图。通过实验证明了该方法的正确性和适用性。     

上下文无关语言句子的反向自然枚举

在测试基于复杂数据结构的程序时,需要用到上下文无关语言句子的枚举.基于上下文无关语言按推导树高度的分层构造,提出了句子的反向自然枚举算法.通过堆、层、簇和长方体将句子划分为有穷集合序列,该算法的时间效率为O(n),n是被枚举句子的长度.实验数据表明,该算法是高效的,且应用更加便利.     

数据结构图的语法

本文给出了一种数据结构图语法的描述方法。数据结构图的抽象结构是一片有序森林。我们首先使用上下文无关文法描述了有序森林的语法，然后以此为基础，描述了每一种数据类型的具体图形表示的语法。     

RAISE语言的语法制导编辑器设计

RSDE 是RAISE 语言的语法制导编辑器在MAC 机上的实现系统。该系统采用多窗口、下拉式菜单、鼠标、键盘四位一体的操作方式,可以同时显示程序的正文形式和内部形式(即语法树的图形显示)。本文介绍了RSDE 的设计与实现,最后给出了RSDE 系统的总体结构和功能描述。     

基于交互注意力图卷积网络的方面情感分类

基于方面的情感分类任务旨在识别句子中给定方面词的情感倾向性.以往的方法大多基于长短时记忆网络和注意力机制,这种做法在很大程度上仅依赖于建模句子中的方面词与其上下文的语义相关性,但忽略了句中的语法信息.针对这种缺陷,提出了一种交互注意力的图卷积网络,同时建模了句中单词的语义相关性和语法相关性.首先使用双向长短时记忆网络来...     

基于最小序句子的上下文无关语言句子枚举

形式规约获取系统SAQ和一些形式化验证系统中常常需要枚举上下文无关语言的句子，现有的枚举方法较少且效率较低，以上下文无关语言L(G)的最小序句子和最大序句子为基础，从最小序句子开始按照一定的顺序扫描字符串，直至扫描到最大序句子为止，对被扫描的字符串进行判断取舍，在扫描的过程中采用削减和前瞻策略，很大程度上减少了被扫描的字符串个数，可以取得较好的时空性能，实验数据表明，基于最小序句子的枚举方法比其他上下文无关语言句子枚举方法具有更高的效率。     

格值树自动机与格值上下文无关树文法的等价性

本文将模糊树自动机和模糊上下文无关树文法的概念推广到格半群上。证明了在接受语言和生成语言的意义下,树自动机和上下文无关树文法是等价的。同时给出了构造正规形式的等价文法的方法。     

On regular tree languages and deterministic pushdown automata

The theory of formal string languages and of formal tree languages are both important parts of the theory of formal languages. Regular tree languages are recognized by finite tree automata. Trees in their postfix notation can be seen as strings. This paper presents a simple transformation from any given (bottom-up) finite tree automaton recognizing a regular tree language to a deterministic pushdown automaton accepting the same tree language in postfix notation. The resulting deterministic pushdown automaton can be implemented easily by an existing parser generator because it is constructed for an LR(0) grammar, and its size directly corresponds to the size of the deterministic finite tree automaton. The class of regular tree languages in postfix notation is a proper subclass of deterministic context-free string languages. Moreover, the class of tree languages which are in their postfix notation deterministic context-free string languages is a proper superclass of the class of regular tree languages.     

基于FUG的藏语句法形式化描述

针对藏语自然语言形式化的实际需求,分析了用复杂特征描述藏语句子的必要性,引入了复杂特征集和合一运算的概念。以形式化为出发点,以现代语言学理论为后盾,以实例举证的方式对藏语词汇、句法、语义的规则及句子合一运算提出了探索性的研究思路,并且采用框式表示的方法,力求从形式化的角度为藏语自然语言处理提供便利。     

基于源语言句法增强解码的神经机器翻译方法

当前性能最优的机器翻译模型之一Transformer基于标准的端到端结构,仅依赖于平行句对,默认模型能够自动学习语料中的知识;但这种建模方式缺乏显式的引导,不能有效挖掘深层语言知识,特别是在语料规模和质量受限的低资源环境下,句子解码缺乏先验约束,从而造成译文质量下降。为了缓解上述问题,提出了基于源语言句法增强解码的神经机器翻译（SSED）方法,显式地引入源语句句法信息指导解码。所提方法首先利用源语句句法信息构造句法感知的遮挡机制,引导编码自注意力生成一个额外的句法相关表征;然后将句法相关表征作为原句表征的补充,通过注意力机制融入解码,共同指导目标语言的生成,实现对模型的先验句法增强。在多个IWSLT及WMT标准机器翻译评测任务测试集上的实验结果显示,与Transformer基线模型相比,所提方法的BLEU值提高了0.84~3.41,达到了句法相关研究的最先进水平。句法信息与自注意力机制融合是有效的,利用源语言句法可指导神经机器翻译系统的解码过程,显著提高译文质量。     

Facet Grammars: Towards static semantic analysis by context-free parsing

Use of executable declarative metalanguages has simplified programming language syntax specification and implementation, whereas existing formalisms for static semantics are still relatively procedural. A working hypothesis is that the context-sensitivity of languages (under static semantic rules) is derived in significant part from the interleaved presences therein of sentences in implicitly-defined and effectively invisible context-free languages. Procedures by which these sentences and context-free grammars for their languages can be respectively derived from the original sentence and the combination of the original language's grammar and semantic rules, lead to the possibility of automatic generation of static semantic analysers from the purely context-free specifications of “Facet Grammars” (FG)!

We show that the utility of FG for static semantic analysis has a non-trivial lower bound, by specifying the relatively complicated identifier scope and accessibility rules for Dijkstra's Guarded Commands Language.     

A representation of trees by languages I

A tree can be represented by a language consisting of a suitable coding of its finite branches. We investigate this representation and derive a number of reductions between certain equivalence problems for context-free tree grammars and recursive program schemes and the (open) equivalence problem for DPDA's. This is the first part of this work: it is devoted to technical results on prefix-free languages and strict deterministic grammars. Application to context-free tree grammars will be published in the second part.     

Formal syntax methods for natural language

This paper describes on-going research into the applications of some techniques normally used to formally specify and analyze the context-sensitive syntax of programming languages to the specification and analysis of the syntax of a natural language, namely English. The specific formal methods presently being investigated are two-level grammar (2LG) and the Vienna Definition Language (VDL). A preliminary subset of English has been established consisting of fifteen basic sentence patterns. 2LG and VDL specifications are given for one of these sentence types and the syntactic analysis of an English sentence using each of the two specifications is illustrated through an example.     

可视化空间数据库查询语言CQL

本文着重从语法、语义及语用三方面介绍了我们所开发的一个可视化空间数据库查询语言ＣＱＬ。该语言允许用户借助于可视化基本元素－－－卡片进行编程,实现对窨数据库的检索。用户查询语句是这些卡片的空间组合。该语言对查询结果的表示提供了多种形式：图形表示形式、正文表示形式、临时文件或三者的组合形式。     

上下文无关语言分析树的一种表示形式

介绍了上下文无关语言（ＣＦＬ）的句子的一种分析树表示,它适用用于一类与以往不同的ＣＦＬ的应用,即对分析树空间效率要求较高且不需标记分析树的应用,典型的就是把ＣＦＬ的句子用作算法加工对象,这种表示比传统分析树不仅空间较小,而且进行结构匹配的快速快,还介绍了这种分析树表示的实现技术。