Building efficient incremental LL parsers by augmenting LL tables and threading parse trees

Incremental parsing is widely used in language-based editors and incremental compiling and interpreting environments. Re-parsing of modified input strings is the most frequently performed operation in these environments. Its efficiency can greatly affect the success of these environments. This paper describes the introduction of a threaded link in parse trees and an additional distance entry in LL parse tables to support minimal LL(1) re-parsing. These enhancements are then used to produce an efficient incremental LL parser.     

Incremental parsing without a parser

This article describes an algorithm for incremental parsing of expressions in the context of syntax-directed editors for programming languages. Since a syntax-directed editor represents programs as trees and statements and expressions as nodes in trees, making minor modifications in an expression can be difficult. Consider, for example, changing a “ + ” operator to a “1” operator or adding a short subexpression at a syntactically but not structurally correct position, such as inserting “) 1 (d“ at the # mark in” (a + b # + c)”. To make these changes in a typical syntax-directed editor, the user must understand the tree structure and type a number of tree-oriented construction and manipulation commands. This article describes an algorithm that allows the user to think in terms of the syntax of the expression as it is displayed on the screen (in infix notation) rather than in terms of its internal representation (which is effectively prefix), while maintaining the benefits of syntax-directed editing. This algorithm is significantly different from other incremental parsing algorithms in that it does not involve modifications to a traditional parsing algorithm or the overhead of maintaining a parser stack or any data structure other than the syntax tree. Instead, the algorithm applies tree transformations, in real-time as each token is inserted or deleted, to maintain a correct syntax tree.     

文件系统增量备份策略的形式化描述及实现

文件系统备份和恢复过程中,需根据当前备份资源树和历史备份资源树进行合并等操作,这种操作在物理上表现为对目录树和资源树的处理.特别是增量备份时,它指明备份资源.恢复过程中,用户可以利用该策略根据时间点进行完全恢复和部分恢复.给出一种对备份资源树的解析算法,并进行分析,在算法的基础上对备份资源树进行了形式化描述.     

Towards Syntax-Aware Editors for Visual Languages

Editors for visual languages should provide a user-friendly environment supporting end users in the composition of visual sentences in an effective way. Syntax-aware editors are a class of editors that prompt users into writing syntactically correct programs by exploiting information on the visual language syntax. In particular, they do not constrain users to enter only correct syntactic states in a visual sentence. They merely inform the user when visual objects are syntactically correct. This means detecting both syntax and potential semantic errors as early as possible and providing feedback on such errors in a non-intrusive way during editing. As a consequence, error handling strategies are an essential part of such editing style of visual sentences.In this work, we develop a strategy for the construction of syntax-aware visual language editors by integrating incremental subsentence parsers into free-hand editors. The parser combines the LR-based techniques for parsing visual languages with the more general incremental Generalized LR parsing techniques developed for string languages. Such approach has been profitably exploited for introducing a noncorrecting error recovery strategy, and for prompting during the editing the continuation of what the user is drawing.     

Incremental parsing in language‐based editors: user needs and how to meet them

Incremental parsing has long been recognized as a technique of great utility in the construction of language‐based editors, and correspondingly, the area currently enjoys a mature theory. Unfortunately, many practical considerations have been largely overlooked in previously published algorithms. Many user requirements for an editing system necessarily impact on the design of its incremental parser, but most approaches focus only on one: response time. This paper details an incremental parser based on LR parsing techniques and designed for use in a modeless syntax recognition editor. The nature of this editor places significant demands on the structure and quality of the document representation it uses, and hence, on the parser. The strategy presented here is novel in that both the parser and the representation it constructs are tolerant of the inevitable and frequent syntax errors that arise during editing. This is achieved by a method that differs from conventional error repair techniques, and that is more appropriate for use in an interactive context. Furthermore, the parser aims to minimize disturbance to this representation, not only to ensure other system components can operate incrementally, but also to avoid unfortunate consequences for certain user‐oriented services. The algorithm is augmented with a limited form of predictive tree‐building, and a technique is presented for the determination of valid symbols for menu‐based insertion. Copyright © 2001 John Wiley & Sons, Ltd.     

增强图元文件的解析及交互编辑

介绍增强图元文件EMF(Enhanced Metafile)的结构,建立了EMF记录与对象模型的映射关系,并基于映射关系实现了EMF的解析流程,解析的结果以对象形式表示。采用图形选定算法,实现了基于图形对象的交互编辑技术。通过对一个EMF实例的解析显示及交互编辑结果,证明该方法具有良好的可行性。     

Incremental semantic evaluation in language-based editors

We present an incremental semantic analysis strategy for use in language-based editors. Its advantage is the low storage cost involved in achieving incremental semantic operation with a relatively small loss in response. The scheme, which involves limiting identifier attribute flow, is first described for a simple block-structured language like Pascal, and then extended to more modern modular languages.     

基于统计和浅层语言分析的维吾尔文语义串快速抽取

该文提出了一种基于统计和浅层语言分析的维吾尔文语义串快速抽取方法,采用一种多层动态索引结构为大规模文本建词索引,结合维吾尔文词间关联规则采用一种改进的n元递增算法进行词串扩展并发现文本中的可信频繁模式,最终依次判断频繁模式串结构完整性从而得到语义串。通过在不同规模的语料上实验发现,该方法可行有效, 能够应用到维吾尔文文本挖掘多个领域。     

编译原理算法的形象教学

本文探讨如何在"编译原理"教学过程中形象地演示复杂的算法过程,提出了一个演示算法步骤的方案,展示算法步骤的进行以及步骤进行时的数据联动,对于不同的动作、不同意义的数据,用图形元素和颜色加以区分,并以LR分析算法为例说明了如何分解复杂步骤,如何用图形和颜色展示移进、归约、接受、出错等分析动作以及相关数据的变化。     

Incremental learning of context free grammars based on bottom-up parsing and search

This paper describes approaches for machine learning of context free grammars (CFGs) from positive and negative sample strings, which are implemented in Synapse system. The grammatical inference consists of a rule generation by “inductive CYK algorithm,” mechanisms for incremental learning, and search. Inductive CYK algorithm generates minimum production rules required for parsing positive samples, when the bottom-up parsing by CYK algorithm does not succeed. The incremental learning is used not only for synthesizing grammars by giving the system positive strings in the order of their length but also for learning grammars from other similar grammars. Synapse can synthesize fundamental ambiguous and unambiguous CFGs including nontrivial grammars such as the set of strings not of the form ww with w∈{a,b}⁺.     

一种有效的概率上下文无关文法分析算法*

句法分析的研究是自然语言处理领域的一个重要组成部分。该提出并实现了一种有效的概率上下无关法ＳＣＦＧ（ｓｔｏｃｈａｓｔｉｃ ｃｏｎｔｅｘｔ－ｆｒｅｅ ｇｒａｍｍｅｒ）的分析算法。首先对原有的ＧＬＲ分析有加以改造，以便能够利用分析过程的控制结构来计算有关的概率；然后对分析过程中的每个状态增设了下标，以区分不同的归约路径。通过上述手段，成功地引入了状态的前向（Ｆｏｒｗａｒｄ）概率和内（Ｉｎｎｅｒ）     

Incremental LR parsers

Summary The concept of incremental parsing is briefly introduced. An algorithm which augments an LR parser with the capability of reanalyzing a limited part of a modified program is illustrated. The algorithm operates on a sequence of configurations representing the parse of the old input and finds the smallest part of the sequence which must be recomputed to obtain the parse of the new input.The implementation is discussed: a suitable data structure and a version of the algorithm which operates upon it are introduced; finally the problem of realizing efficient incremental parsers is faced, showing a modification to the basic algorithm which enable the reanalysis to be performed in linear time.Work supported by C.N.R., Italy     

ΦDM-Dialog: an experimental speech-to-speech dialog translationsystem

ΦDM-Dialog, one of the first experimental speech-to-speech systems and the first to demonstrate simultaneous interpretation possibilities, is described. An overview is given of the model behind ΦDM-Dialog. It consists of a memory network for representing various knowledge levels and markers for inferencing. The markers have rich information content. The integration of speech and natural language processing in ΦDM-Dialog and its cost-based scheme of ambiguity resolution are discussed. Its simultaneous interpretation capability, which is made possible by an incremental parsing and generation algorithm, is examined. Prototype system results are reported     

哈萨克语句法分析辅助特征提取研究

在哈萨克语句法分析中,该文用平均感知器算法训练句法分析模型,用柱搜索算法进行解码,可以快速准确地对哈萨克语句子进行短语结构句法分析。在解析句子过程中,构建了一个双向LSTM模型,利用它提取句子中每个单词之间组成结构的信息,以预测每个单词在句法树中的句法组成部分,然后将结果作为辅助前瞻特征传递给句法分析过程。实验证明,此方法与基线模型相比,在准确率和召回率上均有提高。     

A new approach for recognizing handwritten mathematics using relational grammars and fuzzy sets

We present a new approach for parsing two-dimensional input using relational grammars and fuzzy sets. A fast, incremental parsing algorithm is developed, motivated by the two-dimensional structure of written mathematics. The approach reports all identifiable parses of the input. The parses are represented as a fuzzy set, in which the membership grade of a parse measures the similarity between it and the handwritten input. To identify and report parses efficiently, we adapt and apply existing techniques such as rectangular partitions and shared parse forests, and introduce new ideas such as relational classes and interchangeability. We also present a correction mechanism that allows users to navigate parse results and choose the correct interpretation in case of recognition errors or ambiguity. Such corrections are incorporated into subsequent incremental recognition results. Finally, we include two empirical evaluations of our recognizer. One uses a novel user-oriented correction count metric, while the other replicates the CROHME 2011 math recognition contest. Both evaluations demonstrate the effectiveness of our proposed approach.     

A design rationale for a language-based editor

This paper reviews the design issues that arise in the construction of effective language-based editors for the preparation of syntactically and static semantically correct language sentences, typically computer programs. The need for such editors to support a pluralistic view of program structure is identified, together with the need to observe the constraints on performance and storage consumption if such editors are to be accepted by professional programmers. From these basic needs, more specific requirements for the display, parsing and semantic checking components of such an editor are derived.     

Building syntax-aware editors for visual languages

Syntax-aware editors are a class of editors prompting users into writing syntactically correct programs by exploiting visual language syntax. They are particularly useful in those application domains where the way a visual symbol spatially relates to others depends from the context. This does not mean constraining users to enter only correct syntactic states in a visual sentence, rather it means detecting both syntax and potential semantic errors as early as possible, and providing error feedbacks in a non-intrusive way during editing. As a consequence, error handling strategies are an essential part of this editing style.In this work, we present a strategy for the automatic generation of syntax-aware visual language editors integrating incremental subsentence parsers into freehand editors. The proposed parsing strategy has turned out to be useful in many application domains involving spatial information systems, thanks to the possibility of interactively prompting feasible visual sentence extensions, and to the presence of a non-correcting error recovery strategy. A first experimental prototype implementing the whole approach has been embedded into the VLDesk system, and empirical studies have been performed in order to verify the performance and the effectiveness of the proposed approach.     

Visual Language Parsing in GenGEd

GenGEd supports the visual specification of visual languages and the generation of syntax-directed editors. However, syntax-directed editing is not always desired by the user. Therefore we extended GenGEd by parsing facilities which allow for free editing as well.