Search

When building a new programming language, it can be useful to compose parts of existing languages to avoid repeating implementation work. However, this is problematic already at the syntax level, as composing the grammars of language fragments can easily lead to an ambiguous grammar. State-of-the-art parser tools cannot handle ambiguity truly well: either the grammar cannot be handled at all, or the tools give little help to an end-user who writes an ambiguous program. This composability problem is twofold: (i) how can we detect if the composed grammar is ambiguous, and (ii) if it is ambiguous, how can we help a user resolve an ambiguous program? In this paper, we depart from the traditional view of unambiguous grammar design and enable a language designer to work with an ambiguous grammar, while giving users the tools needed to handle these ambiguities. We introduce the concept of resolvable ambiguity wherein a user can resolve an ambiguous program by editing it, as well as an approach to computing the resolutions of an ambiguous program. Furthermore, we present a method based on property-based testing to identify if a composed grammar is unambiguous, resolvably ambiguous, or unresolvably ambiguous. The method is implemented in Haskell and evaluated on a large set of language fragments selected from different languages. The evaluation shows that (i) the approach can handle significantly more cases of language compositions compared to approaches which ban ambiguity altogether, and (ii) that the approach is fast enough to be used in practice. Part of proceedings: ISBN 9781450383257, QC 20230117

A distance between two languages is a useful tool to measure the language similarity, and is closely related to the intersection problem as well as the shortest string problem. A parsing expression grammar (PEG) is an unambiguous grammar such that the choice operator selects the first matching in PEG while it can be ambiguous in a context-free grammar. PEGs are also closely related to top-down parsing languages. We consider two problems on parsing expression languages (PELs). One is the r-shortest string problem that decides whether or not a given PEL contains a string of length shorter than r. The other problem is the edit-distance problem of PELs with respect to other language families such as finite languages or regular languages. We show that the r-shortest string problem and the edit-distance problem with respect to finite languages are NEXPTIME-complete, and the edit-distance problem with respect to regular languages is undecidable. In addition, we prove that it is impossible to compute a length bound \(\mathcal {B}(G)\) of a PEG G such that L(G) has a string w of length at most \(\mathcal {B}(G)\).

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.

Query modification based on the pseudo relevance feedback(PRF) is an effective way for improving the performance of retrieval system. It is promising approach that used to solve the problems of ambiguous language and synonyms depending on the feedback. In this paper each of expansion and reduction approaches are used for query modification. A hybrid of distribution and association methods are used to select significant terms and expand the query. In this paper, Kullback-Leibler Divergence (KLD) and CHI squared were used as distribution methods that depend on the terms distribution at the top relevant documents and distribute them in the entire corpus. In addition, proximity term frequency method was used to show the semantic relationship between each candidate term with query terms. Different sets of candidate terms are produced from these methods will be combined by Borda aggregation method to get the strength of each individual method. The second direction is removing insignificant terms from the original query and terms' pool to prevent them from being used for expansion query.

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...

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.

This paper focuses on a multimodal language understanding method for carry-and-place tasks with domestic service robots. We address the case of ambiguous instructions, that is, when the target area is not specified. For instance "put away the milk and cereal" is a natural instruction where there is ambiguity regarding the target area, considering environments in daily life. Conventionally, this instruction can be disambiguated from a dialogue system, but at the cost of time and cumbersome interaction. Instead, we propose a multimodal approach, in which the instructions are disambiguated using the robot's state and environment context. We develop the Multi-Modal Classifier Generative Adversarial Network (MMC-GAN) to predict the likelihood of different target areas considering the robot's physical limitation and the target clutter. Our approach, MMC-GAN, significantly improves accuracy compared with baseline methods that use instructions only or simple deep neural networks., 9 pages, 7 figures, accepted for IEEE Robotics and Automation Letters (RA-L)

We introduce an approach to include formalized mathematics in regular undergraduate mathematics courses. In order to enable automatic parsing and checking, the Open image in new window code of our lecture notes systematically uses strict syntax conventions for all definitions and theorems, including in particular an unambiguous grammar for all formulas. Resulting from several years of experience, we present a body of about 1000 pages of notes for a course on modelling and a sequence of three courses on analysis and calculus which are a regular part in the undergraduate mathematics curriculum at the University of Constance. We explain the basic structure of the formalization and its syntax and discuss the practicability of the approach.

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.

Parsing plays an important role in static program analysis: during this step a structural representation of code is created upon which further analysis is performed. Parser generator tools, being provided with syntax specification, automate parser development. Language documentation often acts as such specification. Documentation usually takes form of ambiguous grammar in Extended Backus-Naur Form which most parser generators fail to process. Automatic grammar transformation generally leads to parsing performance decrease. Some approaches support EBNF grammars natively, but they all fail to handle ambiguous grammars. On the other hand, Generalized LL parsing algorithm admits arbitrary context-free grammars and achieves good performance, but cannot handle EBNF grammars. The main contribution of this paper is a modification of GLL algorithm which can process grammars in a form which is closely related to EBNF (Extended Context-Free Grammar). We also show that the modification improves parsing performance as compared to grammar transformation-based approach.

International audience; Type-logical grammars use a foundation of logic and type theory to model natural language. These grammars have been particularly successful giving an account of several well-known phenomena on the syntax-semantics interface, such as quantifier scope and its interaction with other phenomena. This chapter gives a high-level description of a family of theorem provers designed for grammar development in a variety of modern type-logical grammars. We discuss automated theorem proving for type-logical grammars from the perspective of proof nets, a graph-theoretic way to represent (partial) proofs during proof search.

A Szilard language is a language theoretical tool used to describe the derivation process in a formal grammar or grammar system. We investigate computational resources used by (alternating) Turing machines to accept Szilard languages of Chomsky grammars, regulated grammars and grammar systems. The results are related to the circuit complexity classes NC1 and NC2. The paper is a survey of the most important complexity results in the field, but it also brings several new insights into the parallel complexity of Szilard languages of grammar systems. We focus on parallel communicating grammar systems (PCGSs) with context-free components, and we prove that the class of Szilard languages of centralized (returning or non-returning) PCGSs is included in NC1.

Symbolic execution is being successfully used to automatically test statically compiled code. However, increasingly more systems and applications are written in dynamic interpreted languages like Python. Building a new symbolic execution engine is a monumental effort, and so is keeping it up-to-date as the target language evolves. Furthermore, ambiguous language specifications lead to their implementation in a symbolic execution engine potentially differing from the production interpreter in subtle ways. We address these challenges by flipping the problem and using the interpreter itself as a specification of the language semantics. We present a recipe and tool (called Chef) for turning a vanilla interpreter into a sound and complete symbolic execution engine. Chef symbolically executes the target program by symbolically executing the interpreter's binary while exploiting inferred knowledge about the program's high-level structure. Using Chef, we developed a symbolic execution engine for Python in 5 person-days and one for Lua in 3 person-days. They offer complete and faithful coverage of language features in a way that keeps up with future language versions at near-zero cost. Chef-produced engines are up to 1000 times more performant than if directly executing the interpreter symbolically without Chef.

The paper introduces an extension of context-free grammars equipped with an operator for referring to the left context of the substring being defined. For example, a rule A->[email protected]?B defines a symbol a, as long as it is preceded by a string defined by B. The conjunction operator in this example is taken from conjunctive grammars (Okhotin, 2001), which are an extension of ordinary context-free grammars that maintains most of their practical properties, including many parsing algorithms. This paper gives two equivalent definitions of grammars with left contexts-by logical deduction and by language equations-and establishes their basic properties, including a transformation to a normal form and a cubic-time parsing algorithm, with a square-time version for unambiguous grammars.

A mathematical apparatus for describing the context-free grammars of artificial languages is presented: the syntax of the language to describe them is defined, as well as logical and generative semantics, and examples are provided to show how the suggested apparatus can be used.

This paper introduces ATTORNEY 209: A Virtual Assistant Adviser for Family-Based Cases. It is a conversational chatbot which is designed to handle initial assessment for families who need legal guidance regarding family cases such as child custody and legal separation. Chart Parsing Algorithm, known in Natural Language Processing, is the approach implemented in this study. It is suitable for ambiguous grammar and uses the dynamic programming approach—partial hypothesized results are stored in a structure called a chart and can be re-used. This eliminates backtracking and prevents a combinatorial

Contextual grammars are introduced by Solomon Marcus in 1969 based on the fundamental concept of descriptive linguistics of insertion of strings in given contexts. Internal contextual grammars are introduced by Paun and Nguyen in 1980. For contextual grammars several descriptional complexity measures and levels of ambiguity have been defined. In this paper, we analyze the trade-off between ambiguity and complexity of languages generated by internal contextual grammars. The notion of a pseudo inherently ambiguous language with respect to two complexity measures is introduced and investigated. These languages can be generated by unambiguous grammars which are minimal with respect to one measure and ambiguous if they are minimal with respect to the other measure. An open problem from [15] is solved in this framework.

The syntax analysis phase of a Compiler is to check syntactic structure of Programming Language construct using Context Free Grammar. Either by using Top-Down or Bottom-Up parsing technique to parse string of a given language. The string of a Language is successfully parsed by parser of Context Free Grammar then that string is syntactically correct. In this paper CYK algorithm is membership algorithm which gives string is member of language generated by Context Free Grammar or not. We have found out the Context Free Grammar is ambiguous or not using CYK algorithm.

We defineWK linear grammars, as an extension of WK regular grammars with linear grammar rules, andWK context-free grammars, thus investigating their computational power and closure properties. We show that WK linear grammars can generate some context-sensitive languages. Moreover, we demonstrate that the family of WK regular languages is the proper subset of the family of WK linear languages, but it is not comparable with the family of linear languages. We also establish that the Watson-Crick regular grammars are closed under almost all of the main closure operations.

Evolutionary methods aff ord a productive and creative alternative design workfl ow. Crucial to success is the choice of formal representation of the problem. String-rewriting context-free grammars (CFGs) are one common option in evolutionary computation, but their suitability for design is not obvious. Here, a CFG-based evolutionary algorithm for design is presented. The process of meta-design is described, in which the CFG is created and then refi ned to produce an improved design language. CFGs are contrasted with another grammatical formalism better known in architectural design: Stiny's shape grammars. The advantages and disadvantages of the two types of grammars for design tasks are discussed.

Spatial grammars are rule based, generative systems for the specification of formal languages. Set and shape grammar formulations of spatial grammars enable the definition of spatial design languages and the creation of alternative designs. Since the introduction of the underlying formalism, they have been successfully applied to different domains including visual arts, architecture, and engineering. Although many spatial grammars exist on paper, only a few, limited spatial grammar systems have been computationally implemented to date; this is especially true for three-dimensional (3-D) systems. Most spatial grammars are hard-coded, that is, once implemented, the vocabulary and rules cannot be changed without reprogramming. This article presents a new approach and prototype implementation for a 3-D spatial grammar interpreter that enables interactive, visual development and application of grammar rules. The method is based on a set grammar that uses a set of parameterized primitives and includes the definition of nonparametric and parametric rules, as well as their automatic application. A method for the automatic matching of the left hand side of a rule in a current working shape, including defining parametric relations, is outlined. A prototype implementation is presented and used to illustrate the approach through three examples: the “kindergarten grammar,” vehicle wheel rims, and cylinder cooling fins. This approach puts the creation and use of 3-D spatial grammars on a more general level and supports designers with facilitated definition and application of their own rules in a familiar computer-aided design environment without requiring programming.

The paper studies the family of Boolean LL languages, generated by Boolean grammars and usable with the recursive descent parsing. It is demonstrated that over a one-letter alphabet, these languages are always regular, while Boolean LL subsets of Σ ∗ a ∗ obey a certain periodicity property, which, in particular, makes the language { a n b 2 n | n ⩾ 0 } non-representable. It is also shown that linear conjunctive LL grammars cannot generate any language of the form L ⋅ { a , b } , with L non-regular, and that no languages of the form L ⋅ c ∗ , with non-regular L , can be generated by any linear Boolean LL grammars. These results are used to establish a detailed hierarchy and closure properties of these and related families of formal languages.

In this paper, we place some left restrictions on derivations in CD grammar systems with phrase- structure grammars, controlled by the regular languages. The rst restriction requires that every production is always applied within the rst k nonterminals in every sentential form, for some k 1. The second restriction says how many blocks of non-terminals can be in each sentential form. The third restriction extends the second restriction and says how many blocks of non-terminals with limited length can be in each sentential form. We demonstrate that under these restrictions, the grammar systems generate dierent families of languages. Indeed, under the rst restriction, these systems generate only context-free languages. Under the second restriction, even one-component systems characterize the entire family of recursively enumerable languages. In the end, the family of languages generated by grammar systems under the third restriction is equal to the family of languages generated by programmed grammars with context-free rules without -rules of nite index.

Spoken language is one of the most intuitive forms of interaction between humans and agents. Unfortunately, agents that interact with people using natural language often experience communication errors and do not correctly understand the user's intentions. Recent systems have successfully used probabilistic models of speech, language and user behaviour to generate robust dialogue performance in the presence of noisy speech recognition and ambiguous language choices, but decisions made using these probabilistic models are still prone to errors owing to the complexity of acquiring and maintaining a complete model of human language and behaviour. In this paper, a decision-theoretic model for human-robot interaction using natural language is described. The algorithm is based on the Partially Observable Markov Decision Process (POMDP), which allows agents to choose actions that are robust not only to uncertainty from noisy or ambiguous speech recognition but also unknown user models. Like most dialogue systems, a POMDP is defined by a large number of parameters that may be difficult to specify a priori from domain knowledge, and learning these parameters from the user may require an unacceptably long training period. An extension to the POMDP model is described that allows the agent to acquire a linguistic model of the user online, including new vocabulary and word choice preferences. The approach not only avoids a training period of constant questioning as the agent learns, but also allows the agent actively to query for additional information when its uncertainty suggests a high risk of mistakes. The approach is demonstrated both in simulation and on a natural language interaction system for a robotic wheelchair application.

Boolean grammars are an extension of context-free grammars, in which conjunction and negation may be explicitly used in the rules. In this paper, the notion of ambiguity in Boolean grammars is defined. It is shown that the known transformation of a Boolean grammar to the binary normal form preserves unambiguity, and that every unambiguous Boolean language can be parsed in time O(n2). Linear conjunctive languages are shown to be unambiguous, while the existence of languages inherently ambiguous with respect to Boolean grammars is left open.

Several grammars of which generative power is between context-free grammar and context-sensitive grammar were proposed. Among them are macro grammar and tree adjoining grammar. Multiple context-free grammar is also a natural extension of context-free grammars, and is known to be stronger in its generative power than tree adjoining grammar and yet to be recognizable in polynomial time. In this paper, the generative power of several subclasses of variable-linear macro grammars and that of multiple context-free grammars are compared in details.

Building parsers is an essential task for the development of many tools, from software maintenance tools to any kind of business-specific, programmable environment having a command-line interface. Whilst grammars for many programming languages are available, these are, very often, almost useless because of the large diffusion of dialects and variants not contemplated by standard grammars. Writing a grammar by hand is clearly feasible, however it can be a tedious and error-prone task, requiring appropriate skills not always available. Grammar inference is a possible, challenging approach for obtaining suitable grammars from program examples. However, inference from scratch poses serious scalability issues and tends to produce correct, but meaningless grammars, hard to be understood and used to build tools. This paper describes an approach, based on genetic algorithms, for evolving existing grammars towards target (dialect) grammars, inferring changes from examples written using the dialect. Results obtained experimenting the inference of C dialect rules show that the algorithm is able to successfully evolve the grammar. Inspections indicated that the changes automatically made to the grammar during its evolution preserved its meaningfulness, and were comparable to what a developer could have done by hand.

We consider from a practical perspective the problem of checking equivalence of context-free grammars. We present techniques for proving equivalence, as well as techniques for finding counter-examples that establish non-equivalence. Among the key building blocks of our approach is a novel algorithm for efficiently enumerating and sampling words and parse trees from arbitrary context-free grammars; the algorithm supports polynomial time random access to words belonging to the grammar. Furthermore, we propose an algorithm for proving equivalence of context-free grammars that is complete for LL grammars, yet can be invoked on any context-free grammar, including ambiguous grammars. Our techniques successfully find discrepancies between different syntax specifications of several real-world languages, and are capable of detecting fine-grained incremental modifications performed on grammars. Our evaluation shows that our tool improves significantly on the existing available state of the art tools. In addition, we used these algorithms to develop an online tutoring system for grammars that we then used in an undergraduate course on computer language processing. On questions involving grammar constructions, our system was able to automatically evaluate the correctness of 95% of the solutions submitted by students: it disproved 74% of cases and proved 21% of them.

Hindi language is written and spoken by majority of people in India. Like other natural languages, Hindi is also an ambiguous language which creates obstacle in usage of information technology properly. To use Hindi language efficiently and effectively on web, we require a tool to remove ambiguity from a single word, or from all words, called word sense disambiguation (WSD). In this paper we introduce the reader to the brief introduction of task, resources required for disambiguation, applications, brief review of previous works. We also compare and investigate different techniques and algorithms under these approaches which can be used for Hindi Word Sense Disambiguation (HWSD) task and finally, some open problems, conclusion and future directions are discussed on the basis of these comparisons.

This paper describes a tool for intersecting context-free grammars. Since this problem is undecidable the tool follows a refinement-based approach and implements a novel refinement which is complete for regularly separable grammars. We show its effectiveness for safety verification of recursive multi-threaded programs.

Parsing turns unstructured data into structured data suitable for knowledge discovery and querying. The complexity of grammar notations and the difficulty of grammar debugging limit the availability of data parsers. Tier grammars are defined by simply dividing terminals into predefined classes and then splitting elements of some classes into multiple layered sub-groups. The set of predefined terminal classes can be easily extended. Tier grammars and their extensions are LL(1) grammars. Tier grammars are a tool for big data preprocessing.

Given a grammar compressed string S, a pattern P, and \(d\ge 0\), we consider the problem of finding all occurrences of \(P'\) in S such that \(d(P,P')\le d\) with respect to Hamming distance. We propose an algorithm for this problem in \(O(\lg \lg n \lg ^* N(m+d\ occ_d \lg \frac{m}{d}\lg N))\) time, where \(N=|S|\), \(m=|P|\), n is the number of variables in the grammar compression, and \(occ_d\) is the frequency of an evidence of a substring of P. We implement this algorithm and compare with a naive filtering on the grammar compression.

PurposeSince proposed by Darwin, evolution is considered to be dependent on a source of genetic variability that must be constrained by environmental conditions in order to generate stable (adapted) phenotypes. Several sources and causes of this variability have been proposed so far. This paper aims to posit that ambiguity of fuzzy grammars is the main source of genetic variability on which natural selection operates.Design/methodology/approachFormal grammars (FG) were proposed as the tool to deal with human and artificial languages. Fuzzy formal grammars (FFGs) are the extension of the formalism in the Theory of Fuzzy Logic and are ambiguous grammars. Here, the ambiguity of the ordered set of chemical interactions – the so‐called signal transduction pathways (stp), linking membranes events to DNA reading and protein synthesis – is assumed as an inner source of variability that must be constrained by environmental conditions. Fuzzy formal languages (FFL) theory is used to mathematically formalize the biology concept of stp.FindingsThe genome variability is the result of the constraints imposed by the environment on the grammar intrinsic ambiguity.Practical implicationsThe formalism of this model provides a new way to analyze and interpret the findings of the different genome sequencing projects.Originality/valueThe theoretical framework developed here provides a new perspective of understanding the code of life and evolution.

In the area of programming languages, context-free grammars (CFGs) are of special importance since almost all programming languages employ CFG's in their design. Recent approaches to CFG induction are not able to infer context-free grammars for general-purpose programming languages. In this paper it is shown that syntax of a small domain-specific language can be inferred from positive and negative programs provided by domain experts. In our work we are using the genetic programming approach in grammatical inference. Grammar-specific heuristic operators and nonrandom construction of the initial population are proposed to achieve this task. Suitability of the approach is shown by examples where underlying context-free grammars are successfully inferred.

We present a novel algorithm using new hypothesis representations for learning context-free grammars from a finite set of positive and negative examples. We propose an efficient hypothesis representation method which consists of a table-like data structure similar to the parse table used in efficient parsing algorithms for context-free grammars such as Cocke-Younger-Kasami algorithm. By employing this representation method, the problem of learning context-free grammars from examples can be reduced to the problem of partitioning the set of nonterminals. We use genetic algorithms for solving this partitioning problem. Further, we incorporate partially structured examples to improve the efficiency of our learning algorithm, where a structured example is represented by a string with some parentheses inserted to indicate the shape of the derivation tree of the unknown grammar. We demonstrate some experimental results using these algorithms and theoretically analyse the completeness of the search space using the tabular method for context-free grammars.

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 [email protected]?{a,b}^+.

The paper describes a system that can automatically generate tree adjoining grammars from abstract specifications. Our system is based on the use of tree descriptions to specify a grammar by separately defining pieces of tree structure that encode independent syntactic principles. Various individual specifications are then combined to form the elementary trees of the grammar. The system enables efficient development and maintenance of a grammar, and also allows underlying linguistic constructions (such as wh-movement) to be expressed explicitly. We have carefully designed our system to be as language independent as possible and tested its performance by constructing both English and Chinese grammars, with significant reductions in grammar development time. Provably consistent abstract specifications for different languages also offer unique opportunities for investigating how languages relate to themselves and to each other. For instance, the impact of a linguistic structure such as wh-movement can be traced from its specification to the descriptions that it combines with, to its actual realization in trees. By focusing on syntactic properties at a higher level, our approach allowed a unique comparison of our English and Chinese grammars.

There have been many arguments that the underlying structure of natural languages is beyond the descriptive capacity of context-free languages. A well-known example is tree adjoining grammars; less common are spine grammars, linear indexed grammars, head grammars, and combinatory categorial grammars. It is known that these models of grammars have the same generative power of string languages and fall into the class of mildly context-sensitive grammars. For an automaton, it is known that the class of languages accepted by transfer pushdown automata is exactly the class of linear indexed languages. In this paper, deterministic transfer pushdown automata is introduced. We will show that the language accepted by a deterministic transfer pushdown automaton is generated by an unambiguous spine grammar. Moreover, we will show that there exists an inherently ambiguous language.

State-alternating context-free grammars are introduced, and the language classes obtained from them are compared to the classes of the Chomsky hierarchy as well as to some well-known complexity classes. In particular, state-alternating context-free grammars are compared to alternating context-free grammars (Theoret. Comput. Sci. 67 (1989) 75–85) and to alternating pushdown automata. Further, various derivation strategies are considered, and their influence on the expressive power of (state-) alternating context-free grammars is investigated.

C# is the new flagship language in the Microsoft .NET platform. C# is an attractive vehicle for language design research not only because it shares many characteristics with Java, the current language of choice for such research, but also because it is likely to see wide use. Language research needs a large investment in infrastructure, even for relatively small studies. This paper describes a new C# compiler designed specifically to provide that infrastructure. The overall design is deceptively simple. The parser is generated automatically from a possibly ambiguous grammar, accepts C# source, perhaps with new features, and produces an abstract syntax tree, or AST.Subsequent phases--dubbed visitors--traverse the AST, perhaps modifying it, annotating it or emitting output, and pass it along to the next visitor. Visitors are specified entirely at compilation time and are loaded dynamically as needed. There is no fixed set of visitors, and visitors are completely unconstrained. Some visitors perform traditional compilation phases, but the more interesting ones do code analysis, emit non-traditional data such as XML, and display data structures for debugging. Indeed, most usage to date has heen for tools, not for language design experiments. Such experiments use source-to-source transformations or extend existing visitors to handle new language features. These approaches are illustrated by adding a statement that switches on a type instead of a value, which can be implemented in a few hundred lines. The compiler also exemplifies the value of dynamic loading and of type reflection.

We prove that, given as input two context-free grammars, deciding non-emptiness of intersection of the two generated languages is PSPACE-complete if at least one grammar is non-recursive. The problem remains PSPACE-complete when both grammars are non-recursive and deterministic. Also investigated are generalizations of the problem to several context-free grammars, of which a certain number are non-recursive. (C) 2004 Elsevier Inc. All rights reserved.

We propose and study a model of the graphical syllable using Marcus contextual grammars. For this purpose we introduce two new variants of Marcus contextual grammars: total Marcus contextual grammar with total leftmost derivation, and total Marcus contextual grammar with total leftmost derivation constrained by maximal use of selectors.

We consider the problem of inductively inferring a grammar for a language, given (positive) examples of the language and putative (possibly faulty) grammars for the complement of the language. The criterion of success is identification in the limit, defined by E. M. Gold (1967, Inform. and Control10, 447–474). Additional information is useful insofar as it allows the identification of language classes that would not be identified with positive examples alone. An infinite sequence of grammars past some finite position are correct for the complement of the input language, is not as useful a form of additional information as a single correct grammar for the complement. Grammars that are almost correct for the complement (that is, that make finitely many errors) are not as useful as correct grammars, and the usefulness of a grammar decreases with increasing numbers of errors.

We propose a family of static evaluators for subclasses of the well-defined (i.e., noncircular) attribute grammars. These evaluators augment the evaluator for the absolutely noncircular attribute grammars with look-ahead behaviors. Because this family covers exactly the set of all well-defined attribute grammars, well-defined attribute grammars may be classified into a hierarchy, called the NC hierarchy, according to their evaluators in the family. The location of a noncircular attribute grammar in the NC hierarchy is an intrinsic property of the grammar. The NC hierarchy confirms a result of Riis and Skyum (1981), which says that all well-defined attribute grammars allow a (static) pure multivisit evaluator by actually constructing such an evaluator. We also show that, for any finite m, an NC(m) attribute grammar can be transformed to an equivalent NC(0) grammar.

Given two context-free grammars (CFGs), G1 and G2, the language generated by the union of the grammars is not the union of the languages generated by each grammar: L(G1∪ G2)≠ L(G1∪ L(G2). In order to account for modularity of grammars, another way of defining the meaning of grammars is needed. This paper adapts results from the semantics of logic programming languages to CFGs. We discuss alternative approaches for defining the denotation of a grammar, culminating in one which we show to be both compositional and fully-abstract. We then show how grammar modules can be defined such that their semantics retains these desirable properties. This gives a clear, mathematically sound way for composing parts of grammars.

Software tools are fundamental to the comprehension, analysis, testing and debugging of application systems. A necessary first step in the development of many tools is the construction of a parser front-end that can recognize the implementation language of the system under development. In this paper, we describe our use of token decoration to facilitate recognition of ambiguous language constructs. We apply our approach to the C++ language since its grammar is replete with ambiguous derivations such as the declaration/expression and template-declaration/expression ambiguity. We describe our implementation of a parser front-end for C++, keystone, and we describe our results in decorating tokens for our test suite including the examples from Clause Three of the C++ standard. We are currently exploiting the keystone front-end to develop a taxonomy for implementation-based class testing and to reverse-engineer Unified Modeling Language (UML) class diagrams.

In a world characterised by cross-cultural communication, scientific and institutional languages have become increasingly important for linguists and translators. The characteristics of scientific and institutional languages clearly distinguish them from other types of registers. In terms of translation, texts in both registers under analysis should render exact meaning and context of the original text through clear, unequivocal lexis and concise, unambiguous grammar. This particular study focuses on conditional sentences in EU documents and popular science texts and attempts to uncover dominant patterns of the order of clauses in such sentences and whether the particular order is retained during the process of translation. The level of language formality in the two registers seems to be different, being higher in the institutional texts and, thus, imposing a more straightforward rendering of particular grammatical structures. More complex sentence structures with the conditional clause taking the middle position in a sentence are, therefore, expected to be more frequently observed in institutional texts. Likewise, an assumption is made that exactly the same ordering of clauses in a conditional sentence is rendered in another language more frequently in institutional than in science popular texts., Mokslinė ir administracinė kalba šiandieniniame tarpkultūrinės komunikacijos pasaulyje tampa vis svarbesnėmis kalbininkams ir vertėjams. Mokslinės ir administracinės kalbos stilius aiškiai skiriasi nuo kitų kalbos stilių. Kalbant apie vertimą, abiejų analizuojamų funkcinių stilių tekstai turi ypatingai tiksliai išreikšti mintį ir perteikti tą patį kontekstą kaip ir originalo tekste, t. y. leksika turi būti aiški ir nedviprasmiška, o gramatinės struktūros – glaustos ir tikslios. Šis tyrimas nagrinėja sąlygos sakinius Europos Sąjungos dokumentuose ir mokslo populiarinamojo postilio tekstuose. Ieškoma dominuojančių struktūrų šių sakinių dėmenų išsidėstymo tvarkoje ir stebima, ar ta pati dėmenų tvarka išlieka vertime. Akivaizdu, kad kalbos formalumo lygmuo skiriasi šių dviejų stilių tekstuose: administracinių tekstų kalba formalesnė, o verčiant dažniau išlaikoma originalo teksto sakinio dėmenų tvarka. Daroma prielaida, kad identiška originalo ir versto teksto sąlygos sakinio dėmenų tvarka dažniau bus aptinkama administraciniuose stiliaus tekstuose nei mokslo populiarinamojo postilio tekstuose, o pastarojo tipo tekstuose tokių sakinių bus apskritai mažiau. Tyrimo metu nustatyta, kad abiejų nagrinėtų tipų tekstuose sakinio struktūra, kai šalutinis sąlygos sakinio dėmuo yra sakinio pradžioje arba, atvirkščiai, pabaigoje, vertimo proceso metu išlaikoma. Administracinių tekstų vertėjai yra linkę išlaikyti tą pačią sudėtingą sakinio struktūrą, kai šalutinis sąlygos sakinio dėmuo yra sakinio viduryje, tačiau norint patvirtinti ir patikslinti šį pastebėjimą būtina atlikti platesnį tyrimą tiek administracinio stiliaus, tiek mokslo populiarinamojo postilio atveju.

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 analysis. In this paper, we propose a new approach to model transformation development which allows to simplify and improve the quality of the developed transformations via the exploitation of the languages' structures. The approach is based on context-free grammars and transformations defined by pairing productions of source and target grammars. We show that such transformations exhibit three important characteristics: they are sound, complete and deterministic.