Search

Approaches based on the idea generically called distributional learning have been making great success in the algorithmic learning of several rich subclasses of context-free languages and their extensions. Those language classes are defined by properties concerning string-context relation. In this paper, we present a distributional learning algorithm for conjunctive grammars with the k-finite context property (k- fcp ) for each natural number k. We also compare our result with the closely related work by Clark et al. (JMLR 2010) [5] on learning some context-free grammars using contextual binary feature grammars ( cbfg s). We prove that the context-free grammars targeted by their algorithm have the k- fcp . Moreover, we show that every exact cbfg has the k- fcp , too, while not all of them are learnable by their algorithm. Clark et al. conjectured a learning algorithm for exact cbfg s should exist. This paper answers their conjecture in a positive way.

You’ve probably seen .ini files before; they are quite common as configuration files on the Microsoft Windows platform, but are also found in many other places such as ODBC configuration files, Ansible’s inventory files, and so on.

Grammars with contexts are an extension of context-free grammars equipped with operators for referring to the left and the right contexts of a substring being defined. These grammars are notable for still having a cubic-time parsing algorithm, as well as for being able to describe some useful syntactic constructs, such as declaration before use. It is proved in this paper that every language described by a grammar with contexts can be recognized in deterministic linear space.

We explore the concept of hybrid grammars, which formalize and generalize a range of existing frameworks for dealing with discontinuous syntactic structures. Covered are both discontinuous phrase structures and non-projective dependency structures. Technically, hybrid grammars are related to synchronous grammars, where one grammar component generates linear structures and another generates hierarchical structures. By coupling lexical elements of both components together, discontinuous structures result. Several types of hybrid grammars are characterized. We also discuss grammar induction from treebanks. The main advantage over existing frameworks is the ability of hybrid grammars to separate discontinuity of the desired structures from time complexity of parsing. This permits exploration of a large variety of parsing algorithms for discontinuous structures, with different properties. This is confirmed by the reported experimental results, which show a wide variety of running time, accuracy and frequency of parse failures. Publisher PDF

We consider d-dimensional contextual array grammars and investigate their computational power when using various control mechanisms – matrices, regular control languages, and tissue P systems, which work like regular control languages, but may end up with a final check for the non-applicability of some rules. For d≥2, d-dimensional contextual array grammars are less powerful than matrix contextual array grammars, which themselves are less powerful than contextual array grammars with regular control languages. The use of tissue P systems with their final non-applicability check even yields some additional computational power. In the 1-dimensional case, the family of 1-dimensional array languages generated by contextual array grammars with regular control languages can be characterized as the family of array images of the linear languages, which for a one-letter alphabet means that it coincides with the family of regular 1-dimensional array languages.

Compilers, amongst other programs, often work with data that (slowly) changes over time. When the changes between subsequent runs of the compiler are small, one would hope the compiler to incrementally update its results, resulting in much lower rebuilding times. However, the manual construction of an incremental compiler is very hard and error prone and therefore usually not an option. Attribute grammars provide an attractive way of constructing compilers, as they are compositional in nature and allow for aspect oriented programming. In this paper we describe work on the automatic generation of incremental attribute grammar evaluators, with the purpose of (semi-)automatically generating an incremental compiler from a regular attribute grammar definition. The paper includes an informal introduction into attribute grammars, describes how to implement incremental evaluation for a simple example without higher-order attributes as well as for a larger example with higher-order attributes. Higher-order attributes are a well known extension to classical attribute grammars which for example is used to model different compiler phases or iterative transformations of an abstract syntax tree. Incrementality for attribute evaluation is achieved by maintaining additional bookkeeping about which attribute values have changed. We show benchmarks for the implementation technique dealing with higher-order attributes. The benchmarks indicate that the bookkeeping overhead in our prototype implementation comes with a serious hit on performance, further investigation into the reasons and possible remedies for this falls outside the scope of this paper.

Learnability has traditionally been considered to be a crucial constraint on theoretical syntax; however, the issues involved have been poorly understood, partly as a result of the lack of simple learning algorithms for various types of formal grammars. Here I discuss the computational issues involved in learning hierarchically structured grammars from strings of symbols alone. The methods involved are based on an abstract notion of the derivational context of a syntactic category, which in the most elementary case of context-free grammars leads to learning algorithms based on a form of traditional distributional analysis. Crucially, these techniques can be extended to work with mildly context-sensitive grammars (and beyond), thus leading to learning methods that can in principle learn classes of grammars that are powerful enough to represent all natural languages. These learning methods require that the syntactic categories of the grammars be visible in a certain technical sense: They must be well characterized either by the sets of symbols that they generate or by the sets of contexts in which they can appear. However, there are still significant gaps between these theoretical results and their direct implementation as models of language acquisition; I discuss how these remaining problems can be overcome.

Parsing Expression Grammars (PEGs) describe top-down parsers. Unfortunately, the error-reporting techniques used in conventional top-down parsers do not directly apply to parsers based on Parsing Expression Grammars (PEGs), so they have to be somehow simulated. While the PEG formalism has no account of semantic actions, actual PEG implementations add them, and we show how to simulate an error-reporting heuristic through these semantic actions. We also propose a complementary error reporting strategy that may lead to better error messages: labeled failures. This approach is inspired by exception handling of programming languages, and lets a PEG define different kinds of failure, with each ordered choice operator specifying which kinds it catches. Labeled failures give a way to annotate grammars for better error reporting, to express some of the error reporting strategies used by deterministic parser combinators, and to encode predictive top-down parsing in a PEG., Comment: Preprint (plus appendix) submitted to Science of Computer Programming

Attribute grammars are a suitable formalism to express complex software language analysis and manipulation algorithms, which rely on multiple traversals of the underlying syntax tree. Attribute grammars have been extended with mechanisms such as reference, higher order and circular attributes. Such extensions provide a powerful modular mechanism and allow the specification of complex computations. This paper studies an elegant and simple, zipper-based embedding of attribute grammars and their extensions as first class citizens. In this setting, language specifications are defined as a set of independent, off-the-shelf components that can easily be composed into a powerful, executable language processor. Techniques to describe automatic bidirectional transformations between grammars in this setting are also described. Several real examples of language specification and processing programs have been implemented. (C) 2016 Elsevier B.V. All rights reserved., This author is supported by ERDF - European Regional Development Fund through the COMPETE Programme (operational programme for competitiveness) and by National Funds through the FCT - Fundacao para a Ciencia e a Tecnologia (Portuguese Foundation for Science and Technology) within project ON.2 IC&DT Programa Integrado "BEST CASE - Better Science Through Cooperative Advanced Synergetic Efforts (Ref. BIM-2013_BestCase_RL3.2_UMINHO) and project FATBIT - Foundations, Applications and Tools for Bidirectional Transformation (Ref. FCOMP-01-0124-FEDER-020532).This author is partially supported by NSF Award #1047961.

Grammars might be used for various other aspects, than just to represent a language. Grammar inference is a large field which main goal is the construction of grammars from various sources. Written text might be analysed indirectly with the use of such inferred grammars. Grammars acquired from processed text might grow into large structures as the inference process could be continuous. We present a method to decompose and store grammars into a non-redundant set of lambda calculus supercombinators. Grammars decomposition is based on their structure and each distinct element is stored only once in such a structure. We present a method that can create such a set from any context-free grammar. To prove this and to show the possible applications in the field of natural language processing we present a case study performed on samples from two books. Those samples are the entire Book of Genesis from The King James Bible and the first 24 chapters of War and peace by Tolstoy. We obtain context-free grammars with the Sequitur algorithm and then we process them with our method. The results show significant decline in the number of grammar elements in all cases.

While there is a growing body of work proposing grammars for music, there is little work testing analytical grammars in a generative setting. We explore the process of learning production probabili...

GLL (Generalised LL) parsing algorithms provide a sequentialisation of recursive-descent style parsing that yields efficient, compiled parsers which admit any context free grammar, including left recursive and non-left-factored rules. The resulting parsers retain the 'recursively decent' property that the structure of the parser closely follows the structure of the grammar; as such it is feasible to debug grammars by tracing the corresponding GLL parser using a conventional code debugger.In this paper we develop two variants of the GLL algorithm called FGLL and RGLL which respectively support (i) efficient parsing of factorised grammars and (ii) parsing using a reduced set of descriptors. Both techniques yield significant speed up on programming language grammars compared to the base GLL algorithm. We also discuss the ordering of descriptor processing and its effects on performance. Two new variants of the GLL algorithm.FGLL for efficient parsing of factorised grammars.RGLL for parsing using a reduced set of descriptors.Both techniques yield significant speed up on programming language grammars compared and can be used together.The modifications are all at algorithm level and do not depend on inplementation details of the GLL data structures.

We present theoretical foundations, and a practical implementation, that makes the method of Algebraic Dynamic Programming available for Multiple Context-Free Grammars. This allows to formulate optimization problems, where the search space can be described by such grammars, in a concise manner and solutions may be obtained efficiently. This improves on the previous state of the art which required complex code based on hand-written dynamic programming recursions. We apply our method to the RNA pseudoknotted secondary structure prediction problem from computational biology.Appendix and supporting files available at: http://www.bioinf.uni-leipzig.de/Software/gADP/

A class of canonical separated grammars capable of generating the same languages as general-type separated grammars is considered. The main properties and two criteria of canonical grammars are described. A way of unifying nonterminal symbols and proving the uniqueness of the canonical representation for separated grammars is proposed.

The Generalized LR parsing algorithm for context-free grammars is notable for having a decent worst-case running time (cubic in the length of the input string, if implemented efficiently), as well as much better performance on “good” grammars. This paper extends the Generalized LR algorithm to the case of “grammars with left contexts” (M. Barash, A. Okhotin, “An extension of context-free grammars with one-sided context specifications”, Inform. Comput., 2014), which augment the context-free grammars with special operators for referring to the left context of the current substring, along with a conjunction operator (as in conjunctive grammars) for combining syntactical conditions. All usual components of the LR algorithm, such as the parsing table, shift and reduce actions, etc., are extended to handle the context operators. The resulting algorithm is applicable to any grammar with left contexts and has the same worst-case cubic-time performance as in the case of context-free grammars.

This paper presents an algorithm for learning the construction grammar of a language from a large corpus. This grammar induction algorithm has two goals: first, to show that construction grammars are learnable without highly specified innate structure; second, to develop a model of which units do or do not constitute constructions in a given dataset. The basic task of construction grammar induction is to identify the minimum set of constructions that represents the language in question with maximum descriptive adequacy. These constructions must (1) generalize across an unspecified number of units while (2) containing mixed levels of representation internally (e.g., both item-specific and schematized representations), and (3) allowing for unfilled and partially filled slots. Additionally, these constructions may (4) contain recursive structure within a given slot that needs to be reduced in order to produce a sufficiently schematic representation. In other words, these constructions are multi-length, multi-level, possibly discontinuous co-occurrences which generalize across internal recursive structures. These co-occurrences are modeled using frequency and the ΔP measure of association, expanded in novel ways to cover multi-unit sequences. This work provides important new evidence for the learnability of construction grammars as well as a tool for the automated corpus analysis of constructions.

In essence, simple matrix grammars can be seen as sequences of context-free grammars, referred to as their components, which work in parallel. The present paper demonstrates that two-component simple matrix grammars are as powerful as ordinary matrix grammars. Then, it places three leftmost derivation restrictions upon these grammars and demonstrates that under two of these restrictions, simple matrix grammars are computational complete — that is, they are equivalent with Turing machines. From a historical perspective, concerning simple matrix grammars, the paper also makes several remarks that correct false statements published about them in the past.

Dynamic reconfigurations can modify the architecture of component-based systems without incurring any system downtime. In this context, the main contribution of the present article is the establishment of correctness results proving component-based systems reconfigurations using graph grammars. New guarded reconfigurations allow us to build reconfigurations based on primitive reconfiguration operations using sequences of reconfigurations and the alternative and the repetitive constructs, while preserving configuration consistency. A practical contribution consists of the implementation of a component-based model using the GROOVE graph transformation tool. Then, after enriching the model with interpreted configurations and reconfigurations in a consistency compatible manner, a simulation relation is exploited to validate component systems’ implementations. This sound implementation is illustrated on a cloud-based multitier application hosting environment managed as a component-based system.

Shape schema grammars generalize parametric shape grammars so that both rules and the objects to which they apply are expressed with shape schemata. This paper defines shape schema grammars. It starts with a notation for schemata in general and shape schemata in particular. Schema equality is shown to have at least three possible definitions, of which schema consistency is the most useful. A limited notion of shape schema maximality potentially reduces the size and redundancy of a given schema. Shape schema subpart is a multifunction returning all of the possible ways that one shape schema can be embedded in another. Shape schema difference and addition complete the basic mathematical operations over shape schemata required to define shape schema rules, grammars and languages.

Reading and writing are easy for humans. The automatic reading of handwritten characters has been studied for several decades. Machine learning algorithms for reading tasks often require a huge amount of data to perform with similar accuracy to humans, yet it is also difficult to gain sufficient meaningful data. Automatic writing tasks have not been studied as extensively. In this paper, we teach machines to write like teaching a child by telling the machine the method for writing each character using L-attributed grammar. With the aid of the proposed TMTW (Teaching Machines To Write) interacting system, a human as a teacher only needs to provide the writing sequence of parts and control lines. The proposed system automatically perceives the relationships between control lines and parts, and constructs the grammars. Top-down derivation and the stroke generation method are applied to generate varying characters based on the learned grammars. For as long as a machine can write, it can be applied in robot control or training sample generation for automatic reading tasks. The MNIST and CASIA datasets are used to demonstrate the effectiveness of the proposed system on different languages. The machine written samples are used to train a network, which is evaluated on the MNIST test set. A test error rate of 1.23% is achieved using only approximately 20 grammars on average for each digit. Using the generated and handwritten samples together as a training set can reduce the test error rate to 0.61%. Similar experiments are conducted using the CASIA data set, and the results demonstrated that the proposed method is effective in generating characters with a complex structure. The source codes and grammars used in this paper have been made publicly available in https://github.com/step123456789/TMTW .

Probabilistic grammars define joint probability distributions over sentences and their grammatical structures. They have been used in many areas, such as natural language processing, bioinformatics and pattern recognition, mainly for the purpose of deriving grammatical structures from data (sentences). Unsupervised approaches to learning probabilistic grammars induce a grammar from unannotated sentences, which eliminates the need for manual annotation of grammatical structures that can be laborious and error-prone. In this thesis we study unsupervised learning of probabilistic context-free grammars and probabilistic dependency grammars, both of which are expressive enough for many real-world languages but remain tractable in inference. We investigate three different approaches. The first approach is a structure search approach for learning probabilistic context-free grammars. It acquires rules of an unknown probabilistic context-free grammar through iterative coherent biclustering of the bigrams in the training corpus. A greedy procedure is used in our approach to add rules from biclusters such that each set of rules being added into the grammar results in the largest increase in the posterior of the grammar given the training corpus. Our experiments on several benchmark datasets show that this approach is competitive with existing methods for unsupervised learning of context-free grammars. The second approach is a parameter learning approach for learning natural language grammars based on the idea of unambiguity regularization . We make the observation that natural language is remarkably unambiguous in the sense that each natural language sentence has a large number of possible parses but only a few of the parses are syntactically valid. We incorporate this prior information into parameter learning by means of posterior regularization. The resulting algorithm family contains classic EM and Viterbi EM, as well as a novel softmax-EM algorithm that can be implemented with a simple and efficient extension to classic EM. Our experiments show that unambiguity regularization improves natural language grammar learning, and when combined with other techniques our approach achieves the state-of-the-art grammar learning results. The third approach is grammar learning with a curriculum. A curriculum is a means of presenting training samples in a meaningful order. We introduce the incremental construction hypothesis that explains the benefits of a curriculum in learning grammars and offers some useful insights into the design of curricula as well as learning algorithms. We present results of experiments with (a) carefully crafted synthetic data that provide support for our hypothesis and (b) natural language corpus that demonstrate the utility of curricula in unsupervised learning of real-world probabilistic grammars.

Pregroup grammars are a recent descendant of the original categorial grammars of Bar-Hillel [1] and Lambek [10] in which types take the form of strings of basic types and left and right adjoints, as opposed to the non-commutative functional types of categorial grammars. Whereas semantic extraction is possible in other categorial grammars through the λ-calculus, this approach will not be feasible for pregroup grammars. In this paper, we show how to build a term calculus that could be used to fill this void. This system is inspired by the λ-calculus but differs in crucial aspects: it uses function composition as its main reduction strategy instead of function application and is bidirectional, i.e. the direction arguments are applied to terms matters. We show how this term calculus is one- to-one with a proper subset of pregroup types and give multiple examples to show how this system could be used to do semantic analysis in parallel to doing grammaticality checks with pregroup grammars.

This paper shows some fuzzy generalizations of the concepts of derivation and computation with shape grammars. Fuzzy definitions are provided for both rule application and shape matching. The paper also describes a software prototype developed to test these ideas.

Reference attribute grammars (RAGs) provide a practical declarative means to implement programming language compilers and other tools. RAGs have previously been extended to support nonterminal attributes (also known as higher-order attributes), circular attributes, and context-dependent declarative rewrites of the abstract syntax tree. In this previous work, interdependencies between these extensions are not considered. In this article, we investigate how these extensions can interact, and still be well defined. We introduce a generalized evaluation algorithm that can handle grammars where circular attributes and rewrites are interdependent. To this end, we introduce circular nonterminal attributes, and show how RAG rewrites are equivalent to such attributes. HighlightsA definition of circular NTAs, together with an evaluation algorithm.The introduction of the notion of computed children in an AST.Mappings between circular NTAs and rewrites, showing they are equivalent.An evaluation of the presented algorithm.

Model transformation is a key concept in model-driven software engineering. The definition of model transformations is usually based on meta-models describing the abstract syntax of languages. While meta-models are thereby able to abstract from superfluous details of concrete syntax, they often loose structural information inherent in languages, like information on model elements always occurring together in particular shapes. As a consequence, model transformations cannot naturally re-use language structures, thus leading to unnecessary complexity in their development as well as in quality assurance.In this paper, we propose a new approach to model transformation development which allows to simplify the developed transformations and improve their quality via the exploitation of the languages' structures. The approach is based on context-free graph grammars and transformations defined by pairing productions of source and target grammars. We show that such transformations have important properties: they terminate and are sound, complete, and deterministic. HighlightsApproach uses grammar-based definition of languages to create quality transformations.It simplifies transformation development using structural mappings between languages.We define sufficient conditions on grammar-based transformations for their quality.Such transformations are by-construction terminating, sound, complete and deterministic.

This paper presents a novel abstraction framework for heap data structures. It employs graph grammars, more precisely context-free hyperedge replacement grammars. We will show that this is a very natural formalism for modelling dynamic data structures in an intuitive way. Our approach aims at extending finite-state verification techniques to handle pointer-manipulating programs operating on complex dynamic data structures that are potentially unbounded in their size. The theoretical foundations of our approach and its correctness are the main focus of this paper. In addition, we present a prototypical tool entitled Juggrnaut that realizes our approach and show encouraging experimental verification results for three case studies: a doubly-linked list reversal, the flattening of binary trees, and the Deutsch---Schorr---Waite tree traversal algorithm.

We consider context-free grammars and Lambek grammars enriched with semantic labeling. Such grammars do not just answer whether a given word belongs to the language described by the grammar, but, if the answer is positive, also assign the word a λ-term that corresponds to the semantic value (“meaning”) of the word. We present a modification of W. Buszkowski’s direct translation of context-free grammars in the Chomsky normal form into Lambek grammars; this modification preserves semantic values of words.

In a recent paper (M. Barash, A. Okhotin, "An extension of context-free grammars with one-sided context specifications", Inform. and Comput., 2014), the authors introduced an extension of the context-free grammars equipped with an operator for referring to the left context of the substring being defined. This paper proposes a more general model, in which context specifications may be two-sided, that is, both the left and the right contexts can be specified by the corresponding operators. The paper gives the definitions, presents several examples of grammars and establishes a basic normal form theorem. This normal form, in particular, leads to a simple parsing algorithm working in time O ( n 4 ) , where n is the length of the input string.

Tree adjoining grammars (TAGs) are mildly context sensitive formalisms used mainly in modelling natural languages. Usage and research on these psycho linguistic formalisms have been erratic in the past decade, due to its demanding construction and difficulty to parse. However, they represent promising future for formalism based NLP in multilingual scenarios. In this paper we demonstrate basic synchronous Tree adjoining grammar for English-Tamil language pair that can be used readily for machine translation. We have also developed a multithreaded chart parser that gives ambiguous deep structures and a par dependency structure known as TAG derivation. Furthermore we then focus on a model for training this TAG for each language using a large corpus of text through a map reduce frequency count model in spark and estimation of various probabilistic parameters for the grammar trees thereafter; these parameters can be used to perform statistical parsing on the trained grammar.

Writing a parser remains remarkably painful. Automatic parser generators offer a powerful and systematic way to parse complex grammars, but debugging conflicts in grammars can be time-consuming even for experienced language designers. Better tools for diagnosing parsing conflicts will alleviate this difficulty. This paper proposes a practical algorithm that generates compact, helpful counterexamples for LALR grammars. For each parsing conflict in a grammar, a counterexample demonstrating the conflict is constructed. When the grammar in question is ambiguous, the algorithm usually generates a compact counterexample illustrating the ambiguity. This algorithm has been implemented as an extension to the CUP parser generator. The results from applying this implementation to a diverse collection of faulty grammars show that the algorithm is practical, effective, and suitable for inclusion in other LALR parser generators.

The paper introduces node replacement graph grammars with dynamic node relabeling as an extension of the eNCE families of graph grammars. Initiated by NLC grammars in which graph embedding is based on node labels only, node distinction of the embedded graph extended NLC grammars to NCE grammars and dynamic edge relabeling further extended NCE grammars to eNCE grammars. Now, dynamic node relabeling, the node counterpart of the dynamic edge relabeling, is introduced as the next extension, which we call neNCE. The paper analyzes basic language-theoretical properties of the neNCE system.

Categorial Dependency Grammars (CDGs) are classical categorial grammars extended by oriented polarized valencies. At the same time, CDGs represent a class of completely lexicalized dependency grammars. They express both projective and non-projective dependencies. CDGs generate non-context-free languages. At that, they are parsed in polynomial time under realistic conditions. CDGs possess a normal form that is analogous to Greibach normal form for cf-grammars. CDG-languages are closed under almost all AFL operations and are accepted by a special class of push-down automata with independent counters.

The paper considers a family of formal grammars that extends linear context-free grammars with an operator for referring to the left context of a substring being defined, as well as with a conjunction operation (as in linear conjunctive grammars). These grammars are proved to be computationally equivalent to an extension of one-way real-time cellular automata with an extra data channel. The main result is the undecidability of the emptiness problem for grammars restricted to a one-symbol alphabet, which is proved by simulating a Turing machine by a cellular automaton with feedback. The same construction proves the Σ0 2 -completeness of the finiteness problem for these grammars and automata.

This paper proposes a Model Driven Engineering automatic translation approach based on the integration of rewriting logic formal specification and UML semi-formal models. This integration is a contribution in formalizing UML models since it lacks for formal semantics. It aims at providing UML with the capabilities of rewriting logic and its Maude language to control and detect incoherencies in their diagrams. Rewriting logic Maude language allows simulation and verification of system's properties using its LTL model-checker. This automatic translation approach is based on meta-modeling and graph transformation since UML diagrams are graphs. More precisely, the authors have proposed five meta-models and three triple graph grammars to perform the translation process. The authors have used Eclipse Generative Modeling tools: Eclipse Modeling Framework (EMF) for meta-modeling, Graphical Modeling Framework (GMF) for generating visual modeling tools and TGG Interpreter for proposing triple graph grammars. The approach is illustrated through an example.

Gap parsing is an algorithm for parsing incomplete input strings which include some gaps. Gap parsing is different from conventional parsing, and as known results, one-gap parsing algorithms for arbitrary context-free grammar and LL(1) grammar have and time complexity, respectively. This paper presents a one-gap parsing algorithm for extended PLR(1) grammars. Extended PLR(1) grammars are the class of grammars smaller than LR(1) but much larger than LL(1). The one-gap parsing algorithm of the grammar class is shown to have the time complexity of , which is equal to the complexity of one-gap parsing algorithms for LL(1) grammars.

The two main classes of grammars are (a) hand-crafted grammars, which are developed by language experts, and (b) data-driven grammars, which are extracted from annotated corpora. This paper introduces a statistical method for mapping the elementary structures of a data-driven grammar onto the elementary structures of a hand-crafted grammar in order to combine their advantages. The idea is employed in the context of Lexicalized Tree-Adjoining Grammars (LTAG) and tested on two LTAGs of English: the hand-crafted LTAG developed in the XTAG project, and the data-driven LTAG, which is automatically extracted from the Penn Treebank and used by the MICA parser. We propose a statistical model for mapping any elementary tree sequence of the MICA grammar onto a proper elementary tree sequence of the XTAG grammar. The model has been tested on three subsets of the WSJ corpus that have average lengths of 10, 16, and 18 words, respectively. The experimental results show that full-parse trees with average F1-scores of 72.49, 64.80, and 62.30 points could be built from 94.97%, 96.01%, and 90.25% of the XTAG elementary tree sequences assigned to the subsets, respectively. Moreover, by reducing the amount of syntactic lexical ambiguity of sentences, the proposed model significantly improves the efficiency of parsing in the XTAG system.

We propose an enhancement to current parsing and transformation systems by leveraging the expressive power of Boolean grammars, a generalization of context-free grammars that adds conjunction and negation operators. In addition to naturally expressing a larger class of languages, Boolean grammars capture multiple parse trees of the same document simultaneously and the ability to switch between these parse "views". In particular, source transformation and reengineering tasks can benefit from parse views by recasting the input text into whichever parse is most suitable for the task at hand. We introduce Boolean grammars from language theory to the parsing/reengineering community.We describe how Boolean grammars can improve programming language expressiveness and be used for agile parsing.We discuss its potential for source transformation systems.We demonstrate our progress implementing Boolean grammars in TXL.

This paper argues that graph grammars naturally model dynamic data structures such as lists, trees and combinations thereof. These grammars can be exploited to obtain finite abstractions of pointer-manipulating programs, thus enabling model checking. Experimental results for verifying Lindstrom's variant of the Deutsch-Schorr-Waite tree traversal algorithm illustrate this. We propose to employ graph grammars for modelling dynamic data structures.Typical examples include lists, trees and combinations thereof.We show how to obtain finite state-space abstractions of heap-manipulating programs.This enables the application of standard model checking techniques.We report on the automated verification of a stackless tree traversal algorithm.

Reference Attribute Grammars (RAGs) is a declarative executable formalism used for constructing compilers and related tools. Existing implementations support concurrent evaluation only with global evaluation locks. This may lead to long latencies in interactive tools, where interactive and background threads query attributes concurrently. We present lock-free algorithms for concurrent attribute evaluation, enabling low latency in interactive tools. Our algorithms support important extensions to RAGs like circular (fixed-point) attributes and higher-order attributes. We have implemented our algorithms in Java, for the JastAdd metacompiler. We evaluate the implementation on a JastAdd-specified compiler for the Java language, demonstrating very low latencies for interactive attribute queries, on the order of milliseconds. Furthermore, initial experiments show a speedup of about a factor 2 when using four parallel compilation threads.

The similarities and differences between attribute grammar systems are obscured by their implementations. A formalism that captures the essence of such systems would allow for equivalence, correctness, and other analyses to be formally framed and proven. We present Saiga, a core language and small-step operational semantics that precisely captures the fundamental concepts of the specification and execution of parameterised reference attribute grammars. We demonstrate the utility of by a) proving a meta-theoretic property about attribute caching, and b) by specifying two attribute grammars for a realistic name analysis problem and proving that they are equivalent. The language, semantics and associated tests have been mechanised in Coq; we are currently mechanising the proofs.

Extensible language frameworks aim to allow independently-developed language extensions to be easily added to a host programming language. It should not require being a compiler expert, and the resulting compiler should "just work" as expected. Previous work has shown how specifications for parsing (based on context free grammars) and for semantic analysis (based on attribute grammars) can be automatically and reliably composed, ensuring that the resulting compiler does not terminate abnormally. However, this work does not ensure that a property proven to hold for a language (or extended language) still holds when another extension is added, a problem we call interference. We present a solution to this problem using of a logical notion of coherence. We show that a useful class of language extensions, implemented as attribute grammars, preserve all coherent properties. If we also restrict extensions to only making use of coherent properties in establishing their correctness, then the correctness properties of each extension will hold when composed with other extensions. As a result, there can be no interference: each extension behaves as specified.

Parsing expression grammars (PEGs) are a powerful and popular foundation for describing syntax. Despite PEGs' expressiveness, they cannot recognize many syntax patterns of popular programming languages. Typical examples include typedef-defined names in C/C++ and here documents appearing in many scripting languages. We use a single unified state representation, called a symbol table, to capture various context-sensitive patterns. Over the symbol table, we design a small set of restricted semantic predicates and actions. The extended PEGs are called SPEGs, and are designed to be safe in contexts of backtracking and the linear time guarantee of packrat parsing. This paper will show that SPEGs have improved the expressive power in such ways that they recognize practical context-sensitive grammars, including back referencing, indentation-based code layout, and contextual keywords.

The paper presents attribute grammars as a unifying framework for modeling planning domains and problems. The motivation is to exploit techniques from formal languages in domain model verification, plan and goal recognition, domain model acquisition, as well as in planning. Grammar rules are used for action selection while specific set attributes are used to collect events (preconditions and effects of actions) that are ordered using a global timeline constraint. We show how classical STRIPS, hierarchical task networks, and procedural domain models are transformed to attribute grammars.

The article presents the use of generative grammars in linguistic modeling. A description of sentence syntax modeling is used to automate the process of analysis and synthesis of natural language texts. The article reveals the features of synthesizing sentences of different languages with the use of generative grammars. The article examines influence of norms and rules of a language on the process of constructing grammars. The use of generative grammars has great potential in the development and creation of automated systems for text content processing, linguistic support for linguistic computer systems etc. In natural languages there are situations where notions, which are dependent on the context, are described as independent of context, i.e. in terms of context-free grammars. This description is complicated by the formation of new categories and rules. The article features the process of introducing new restrictions on these grammar classes through the introduction of new rules. Uncut grammars were received if the number of characters in the right part of the rules were not less than the number of characters in the left one. Then by replacing the only character a context-sensitive grammar was received. A grammar with only one character in the left part of the rule is called a context-free grammar. No further natural restrictions may be applied to the left part of a rule. Based on the importance of automatic processing of text content in modern information media (e.g., information retrieval systems, machine translation, semantic, statistical, optical and acoustic analysis and speech synthesis, automated editing, extracting knowledge from text content, abstracting and annotating text content, indexing text content, teaching and didactic, management of linguistic corpora, various tools for lexicography, etc.), specialists are actively looking for new models, ways of their description and methods of automatic processing of text content. One of such methods lies in developing general principles of syntactic lexicographical systems formation and developing mentioned systems of processing text content for specific languages based in these principles. Any parsing tools consist of two parts: a knowledge base of concrete natural language and parsing algorithm, i.e. a set of standard operators of text content processing based on this knowledge. The source of grammatical knowledge is data of morphological analysis and various tables filled with concepts and linguistic units. They are the result of an empirical study of the text content in natural language by experts aiming at highlighting the basic laws for parsing.

This paper presents an attribute and-or grammar (A-AOG) model for jointly inferring human body pose and human attributes in a parse graph with attributes augmented to nodes in the hierarchical representation. In contrast to other popular methods in the current literature that train separate classifiers for poses and individual attributes, our method explicitly represents the decomposition and articulation of body parts, and account for the correlations between poses and attributes. The A-AOG model is an amalgamation of three traditional grammar formulations: (i) Phrase structure grammar representing the hierarchical decomposition of the human body from whole to parts; (ii) Dependency grammar modeling the geometric articulation by a kinematic graph of the body pose; and (iii) Attribute grammar accounting for the compatibility relations between different parts in the hierarchy so that their appearances follow a consistent style. The parse graph outputs human detection, pose estimation, and attribute prediction simultaneously, which are intuitive and interpretable. We conduct experiments on two tasks on two datasets, and experimental results demonstrate the advantage of joint modeling in comparison with computing poses and attributes independently. Furthermore, our model obtains better performance over existing methods for both pose estimation and attribute prediction tasks.