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 ...
详细信息
ISBN:
(纸本)9781467392143
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.
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 gen...
详细信息
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 omega omega with omega is an element of {a, b}(+). (c) 2005 Pattern Recognition Society. Published by Elsevier Ltd. All rights reserved.
In this paper, we propose an approach to quantitative structural information for inferring context free grammars. First, we construct derivative capacity of nonterminal symbols in context free grammar, concomitant ind...
详细信息
In this paper, we propose an approach to quantitative structural information for inferring context free grammars. First, we construct derivative capacity of nonterminal symbols in context free grammar, concomitant indicator and embedded dimensional number of strings in samples set, which are called as quantitative structural information;then, we rewrite Cocke-Younger-Kasarni (cyk) algorithm for parsing in the form of the derivative set;third, we present the construction of new production rule and the descriptive procedure for inferring with an extended cyk algorithm by the quantitative structural information. Finally, we discuss the extended cyk algorithm for inferring context free grammars. (C) 2011 Elsevier B.V. All rights reserved.
This paper describes an improved version of TBL algorithm [Y. Sakakibara, Learning context-free grammars using tabular representations, Pattern Recognition 38( 2005) 1372-1383;Y. Sakakibara, M. Kondo, GA-based learnin...
详细信息
This paper describes an improved version of TBL algorithm [Y. Sakakibara, Learning context-free grammars using tabular representations, Pattern Recognition 38( 2005) 1372-1383;Y. Sakakibara, M. Kondo, GA-based learning of context-free grammars using tabular representations, in: Proceedings of 16th International Conference in Machine Learning (ICML-99), Morgan-Kaufmann, Los Altos, CA, 1999] for inference of context-free grammars in Chomsky Normal Form. The TBL algorithm is a novel approach to overcome the hardness of learning context-free grammars from examples without structural information available. The algorithm represents the grammars by parsing tables and thanks to this tabular representation the problem of grammar learning is reduced to the problem of partitioning the set of nonterminals. Genetic algorithm is used to solve NP-hard partitioning problem. In the improved version modified fitness function and new delete specialized operator is applied. Computer simulations have been performed to determine improved a tabular representation efficiency. The set of experiments has been divided into 2 groups: in the first one learning the unknown context-free grammar proceeds without any extra information about grammatical structure, in the second one learning is supported by a partial knowledge of the structure. In each of the performed experiments the influence of partition block size in an initial population and the size of population at grammar induction has been tested. The new version of TBL algorithm has been experimentally proved to be not so much vulnerable to block size and population size, and is able to find the solutions faster than standard one. (C) 2009 Elsevier B. V. All rights reserved.
In this paper we present an optimal linear time algorithm for recognition and parsing of context-free languages on n x n mesh connected computers with multiple broadcasting, for an input string of length n. Our algori...
详细信息
In this paper we present an optimal linear time algorithm for recognition and parsing of context-free languages on n x n mesh connected computers with multiple broadcasting, for an input string of length n. Our algorithm is based on the well-known Cocke-Younger-Kasami (cyk) algorithm for the recognition and parsing of context-free languages, and is faster than two recent algorithms available in the literature. The parallel recognition of context-free languages is of particular importance since parallel compilation is an increasingly important application because of the availability of parallel hardware and the long running times of optimizing and parallelizing compilers. Our algorithm is a contribution towards this end.
Chord progression in Classical music is not random. It follows some specific structure and rules. In this paper, we present a generative account of chord progression described by a set of phrase-structure grammar rule...
详细信息
ISBN:
(纸本)9780769554372
Chord progression in Classical music is not random. It follows some specific structure and rules. In this paper, we present a generative account of chord progression described by a set of phrase-structure grammar rules from Martin Rohrmeier. With some modifications and simplifications, these rules can be used to correct chord errors. A chord classification system for classical music is developed. With the aid of beat and melodic information, processed pitch class vector is obtained from the extracted constant-Q transform spectra. Exploiting tonal grammar rules, the most probable and musically sensible chord sequence is derived from that sequence of pitch class vectors. Some examples of classical piano excerpts are evaluated. The experimental result shows that our system is useful to improve chord classification accuracy.
We consider the problem of incremental learning of context-free grammars, using inductive cyk (Cocke-Younger-Kasami) algorithm [4], based on the non-deterministic learning scheme proposed by Nakamura and Matsumoto in ...
详细信息
ISBN:
(纸本)9781424452507
We consider the problem of incremental learning of context-free grammars, using inductive cyk (Cocke-Younger-Kasami) algorithm [4], based on the non-deterministic learning scheme proposed by Nakamura and Matsumoto in 2005 [1]. We implement their learning scheme deterministically and illustrate several examples in order to understand the incremental learning process efficiently. On the basis of this study we also point out some lines of research for possible enhancements.
S analýzou řetězců, hledáním vzorů a kontrolou syntaktické správnosti se setkáváme každý den, ať jde o programovací jazyky, komunikační protokoly či psaný text. ...
详细信息
S analýzou řetězců, hledáním vzorů a kontrolou syntaktické správnosti se setkáváme každý den, ať jde o programovací jazyky, komunikační protokoly či psaný text. Oblastí, kterých se tento problém dotýká, neustále přibývá, proto je třeba hledat i nové postupy, které by byly vhodné, a jejich aplikace dostatečně efektivní. V této diplomové práci se zabýváme tématem paralelních E0L-systémů a multigenerativních gramatických systémů, a to především v oblasti jejich spojení pro analýzu či generování jazyka. Aplikujeme tyto postupy na cyk metodu a ukážeme si, jaké vlastnosti vyplývají z tohoto spojení a jak by se daly využít v praxi.
Tato bakalářská práce se zabývá obecními metodami syntaktické analýzy. Autor studuje Cocke-Younger-Kasami algoritmus a přichází s návrhem paralelní verze. Mo...
详细信息
Tato bakalářská práce se zabývá obecními metodami syntaktické analýzy. Autor studuje Cocke-Younger-Kasami algoritmus a přichází s návrhem paralelní verze. Motivací autora je zrychlení syntaktické analýzy založené na tomto algoritmu. Výsledkem práce je konzolová aplikace, která dokáže zjistit, zda vstupní řetězec patří do jazyka generovaného vstupní gramatikou, nebo nepatří, na základě navrženého paralelního algoritmu. Jako programovací jazyk byl zvolen jazyk C++. Pro dosažení paralelismu byla práce algoritmu rozdělena mezi několik vláken.
Stochastic context-free grammars (SCFGs) were first established in the context of natural language modelling, and only later found their applications in RNA secondary structure prediction. In this chapter, we discuss ...
详细信息
Stochastic context-free grammars (SCFGs) were first established in the context of natural language modelling, and only later found their applications in RNA secondary structure prediction. In this chapter, we discuss the basic SCFG algorithms (cyk and inside–outside algorithms) in an application-centered manner and use the pfold grammar as a case study to show how the algorithms can be adapted to a grammar in a nonstandard form. We extend our discussion to the use of grammars with additional information (such as evolutionary information) to improve the quality of predictions. Finally, we provide a brief survey of programs that use stochastic context-free grammars for RNA secondary structure prediction and modelling.
暂无评论