A graph grammar is a formal tool for providing rigorous but intuitive ways to define visual languages. However, the description and implementation difficulties of graph grammars hinder their wide applications. This pa...
详细信息
ISBN:
(纸本)9781479979837
A graph grammar is a formal tool for providing rigorous but intuitive ways to define visual languages. However, the description and implementation difficulties of graph grammars hinder their wide applications. This paper, first of all introduces a description mechanism for specifying the existing Edge-based Graph Grammar (EGG) by using the XML techniques. Then, based on the mechanism, a new parsing algorithm is proposed, which is easily designed and implemented by using the XML technique.
Model-based software architecture verification and test scenarios generation are becoming more and more important in the software industry. Based on the existing temporal graph grammar, this paper proposes a new forma...
详细信息
Model-based software architecture verification and test scenarios generation are becoming more and more important in the software industry. Based on the existing temporal graph grammar, this paper proposes a new formalization method of the context-sensitive graph grammar for aiming at UML activity diagrams, which is called the UML Activity Graph Grammar, or UAGG. In the UAGG, there are new definitions and parsing algorithms. The proposed mechanisms are able to not only check the structural correctness of the UML activity diagram but also automatically generate the test scenario according to user constraints. Finally, a case study is discussed to illustrate how the UAGG and its algorithms work.
Software tools are developed for computer realization of syntactic, semantic, and morphological models of natural language texts, using rule based programming. The tools are efficient for a language, which has free or...
详细信息
Software tools are developed for computer realization of syntactic, semantic, and morphological models of natural language texts, using rule based programming. The tools are efficient for a language, which has free order of words and developed morphological structure like Georgian. For instance, a Georgian verb has several thousand verb-forms. It is very difficult to express rules of morphological analysis by finite automaton and it will be inefficient as well. Resolution of some problems of full morphological analysis of Georgian words is impossible by finite automaton. Splitting of some Georgian verb-forms into morphemes requires non-deterministic search algorithm, which needs many backtrackings. To minimize backtrackings, it is necessary to put constraints, which exist among morphemes and verify them as soon as possible to avoid false directions of search. Software tool for syntactic analysis has means to reduce rules, which have the same members in different order. The authors used the tool for semantic analysis as well. Thus, proposed software tools have many means to construct efficient parser, test and correct it. The authors realized morphological and syntactic analysis of Georgian texts by these tools. In the presented paper, the authors describe the software tools and its application for Georgian language.
The graph structure is a strong formalism for representing pictures in syntactic pattern recognition. Many models for graph grammars have been proposed as a kind of hyper-dimensional generating systems, whereas the us...
详细信息
The graph structure is a strong formalism for representing pictures in syntactic pattern recognition. Many models for graph grammars have been proposed as a kind of hyper-dimensional generating systems, whereas the use of such grammars for pattern recognition is relatively infrequent. One of the reasons is the difficulty of building a syntax analyzer for such graph grammars. In this paper, we define a subclass of nPCE graph grammars and present a parsing algorithm of O(n) for both sequential and parallel cases.
Defines a class of context-free grammars called the simple LR(k) or SLR(k) grammars. Inclusion of weak precedence and simple precedence grammars as proper subsets in SLR(k) grammars; Construction and implementations o...
详细信息
Defines a class of context-free grammars called the simple LR(k) or SLR(k) grammars. Inclusion of weak precedence and simple precedence grammars as proper subsets in SLR(k) grammars; Construction and implementations of parsers for the SLR(k) grammars; Superiority over precedence techniques in terms of the speed of parser construction and in size and speed of resulting parsers.
An improved chart parser based on active edges sharing the leftmost common elements is presented. After analyzing the mechanism of avoiding redundant work in the traditional chart parsing algorithm, the inefficient tr...
详细信息
An improved chart parser based on active edges sharing the leftmost common elements is presented. After analyzing the mechanism of avoiding redundant work in the traditional chart parsing algorithm, the inefficient treatment on active edges possessing the same leftmost common elements was discovered. Then a new presentation of the active edge was proposed to share the same leftmost elements, and thus an improved chart parser was realized with great decrease of generated active edges. The experimental results on Chinese Treebank show that the improved chart parser significantly outperforms the packed chart parser in terms of both speed (about 10 times faster) and space consumption.
暂无评论