Context-sensitive graph grammars have been intuitive and rigorous formalisms for specifying visual programming languages, as they are sufficient expressive and equipped with parsing mechanisms. parsing has been a fund...
详细信息
Context-sensitive graph grammars have been intuitive and rigorous formalisms for specifying visual programming languages, as they are sufficient expressive and equipped with parsing mechanisms. parsing has been a fundamental issue in the research of context-sensitive graph grammars. However, the existent parsing algorithms are either inefficient or confined to a minority of graph grammars. This paper proposes a general parsing algorithm with two embedded strategies, context matching and production-set partitioning. The two strategies can greatly narrow down the search space of redexes and thus significantly improve parsing efficiency, even though the worst-case time complexity is not theoretically reduced. Moreover, a detailed case study and an experiment are provided accordingly to demonstrate the paring process and performance of the proposed algorithm.
This article aims to advance semantic analysis models, particularly in visualization, by proposing a novel semantic representation method utilizing the semantic Meta Network (MNet). MNet is a complex framework compris...
详细信息
This article aims to advance semantic analysis models, particularly in visualization, by proposing a novel semantic representation method utilizing the semantic Meta Network (MNet). MNet is a complex framework comprising semantic elements, internal and external relationships, and feature attributes, defined hierarchically through recursive processes, aiming to depict the comprehensive semantic space from phrase-level components to complete texts. The methodology involves the development of a general construction algorithm for MNet, encompassing meta relationships, tree structures, and network structures, and a parsing method for specific semantic analysis problems, including a bottom-up specification-based MNet semantic dependency tree construction algorithm and a network construction algorithm tailored for natural language interface parsing. Empirical experiments confirm the effectiveness of these algorithms, particularly in parsing natural language control interface instructions in Supervisory Control and Data Acquisition (SCADA) systems, bridging specific semantic analysis problems with the general construction and parsing processes of MNet, accounting for internal semantics concerning language unit structures and foreign language meanings in the linguistic context, thereby contributing significantly to the field of natural language semantic analysis.
A parsing algorithm visualizer is a tool that visualizes the construction of a parser for a given context-free grammar and then illustrates the use of that parser to parse a given string. parsing algorithm visualizers...
详细信息
A parsing algorithm visualizer is a tool that visualizes the construction of a parser for a given context-free grammar and then illustrates the use of that parser to parse a given string. parsing algorithm visualizers are used to teach the course on compiler construction which in invariably included in all undergraduate computer science curricula. This paper presents a new parsing algorithm visualizer that can visualize six parsing algorithms, viz. predictive parsing, simple LR parsing, canonical LR parsing, look-ahead LR parsing, Earley parsing and CYK parsing. The tool logically explains the process of parsing showing the calculations involved in each step. The output of the tool has been structured to maximize the learning outcomes and contains important constructs like FIRST and FOLLOW sets, item sets, parsing table, parse tree and leftmost or rightmost derivation depending on the algorithm being visualized. The tool has been used to teach the course on compiler construction at both undergraduate and graduate levels. An overall positive feedback was received from the students with 89% of them saying that the tool helped them in understanding the parsing algorithms. The tool is capable of visualizing multiple parsing algorithms and 88% students used it to compare the algorithms.
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.
Context-sensitive graph grammars have been suitable formalisms for specifying visual programming languages, as they are intuitive, sufficient expressive and equipped with parsing mechanisms. parsing has been a fundame...
详细信息
ISBN:
(纸本)9781450376266
Context-sensitive graph grammars have been suitable formalisms for specifying visual programming languages, as they are intuitive, sufficient expressive and equipped with parsing mechanisms. parsing has been a fundamental issue in the research of context-sensitive graph grammars. However, the existent parsing algorithms are either inefficient or confined to a minority of graph grammars. This paper presents two strategies for general parsing algorithms, one is context matching, and the other is partitioning of productions. Through narrowing down the searching space of potential redexex, the two strategies can considerably improve the parsing performance.
As a useful formalism tool, graph grammars provide a rigorous but intuitive way to specify visual languages. This paper, based on the existing Edge-based Graph Grammar (EGG), proposes a new context-sensitive graph gra...
详细信息
As a useful formalism tool, graph grammars provide a rigorous but intuitive way to specify visual languages. This paper, based on the existing Edge-based Graph Grammar (EGG), proposes a new context-sensitive graph grammar formalism called the Temporal Edge-based Graph Grammar, or TEGG. TEGG introduces some temporal mechanisms to grammatical specifications, productions, operations and so on in order to tackle time-related issues. In the paper, formal definitions of TEGG are provided first. Then, a new parsing algorithm with a decidability proof is proposed to check the correctness of a given graph's structure, to analyze operations' timing when needed, and to make the computer simulation of the temporal sequence in the graph available. Next, the complexity of the parsing algorithm is analyzed. Finally, a case study on an application with temporal requirements is provided to show how the parsing algorithm of TEGG works.
Graph grammars are a rigorous but intuitive way to define and handle graph languages. To tackle time-related issues, this paper proposes a new extension of temporal mechanism based on the existing Edge-based Graph Gra...
详细信息
ISBN:
(纸本)9781538649916
Graph grammars are a rigorous but intuitive way to define and handle graph languages. To tackle time-related issues, this paper proposes a new extension of temporal mechanism based on the existing Edge-based Graph Grammar (EGG), which includes grammatical specifications, productions, operations and so on. In the paper, formal definitions of temporal mechanism are provided first. Then, a new parsing algorithm is presented to check the correctness of a given graph's structure, and to analyze operations' timing when needed.
This paper proposes a method for speeding up parsing process for recognizing online handwritten mathematical expressions (OHME). We prune infeasible partitions in the parsing table to reduce the time for the parsing p...
详细信息
ISBN:
(纸本)9781538635865
This paper proposes a method for speeding up parsing process for recognizing online handwritten mathematical expressions (OHME). We prune infeasible partitions in the parsing table to reduce the time for the parsing process. Low score partitions are candidates for pruning. Our method can be applied for any parsing algorithms that use score functions. In this paper, we use a stroke order free system as a baseline system. The method is as follows. First, we analyze the scores of partitions in each row of the parsing table. Then, we determine a threshold for each row to prune low score partitions. Finally, we employ these thresholds to prune low score partitions on the baseline recognition system. The results of evaluations of our method on the CROHME 2014 database show that the recognition process is speeded up by 3.46 times and 4.97 times while recognition rate is reduced only 0.31 point and 0.71 point, respectively.
A graph grammar is a formal tool for providing rigorous but intuitive ways to define visual languages. Based on an existing graph grammar, this paper proposes new context-sensitive graph grammar formalism called the E...
详细信息
A graph grammar is a formal tool for providing rigorous but intuitive ways to define visual languages. Based on an existing graph grammar, this paper proposes new context-sensitive graph grammar formalism called the Extension of Edge-based Graph Grammar, or E-EGG. The E-EGG introduces new mechanisms into grammatical specifications, productions, operations and so on in order to conveniently treat the bidirectional transformation between the Business Process Modeling Notation (BPMN) and the Business Process Execution Language (BPEL). Besides formal definitions of the E-EGG are provided, steps and algorithms to achieve the bidirectional transformation and to check the correctness of BPMN models' structure are presented. Finally, a case study on transformation from BPMN models to BPEL codes is provided to show how the parsing algorithm of the E-EGG works. (C) 2016 Elsevier Ltd. All rights reserved.
暂无评论