Search

• Introduce the role of phrases in text representation and semantic disambiguation. • Propose ParsingPhrase to extracts combination phrases and improves phrase quality. • Mining candidate phrases efficiently by traversing the parse tree hierarchically. • Put forward a new phrase evaluation indicator to enhance phrase evaluation accuracy. • We suggest a joint scheme to solve sentence disambiguation and phrase optimization. Phrases represent independent semantics in natural language but usually have indeterminate lengths and different combinations. So, extracting meaningful phrases from unstructured texts will substantially reduce semantic ambiguity and lay the foundation for downstream natural language tasks. Most existing research obtains candidate phrases by N-grams, which includes meaningless word sequences and degrades algorithm performance. In this paper, we propose a novel phrase-mining algorithm, called ParsingPhrase, which effectively extracts combination phrases from text and improves phrase quality by syntactic features. It consists of three stages. Firstly, all sentences in texts are represented as parsing trees by PCFG (Probabilistic Context-Free Grammar). We propose PBMP (Parsing-Based Phrase mining) to obtain candidate phrases from those parsing trees. Then, we introduce a new phrase evaluation indicator, called Significance, that relies on the role of phrases to measure their importance. We integrate the Significance with conventional evaluation indexes for a more reasonable phrase evaluation. Finally, we optimize the phrase quality again by exploiting the optimal phrase composition features of sentences. To the best of our knowledge, it is the first work to employ parsing for combination phrase mining and evaluation, meanwhile offering a solution for syntactic disambiguation. Experiments on three real corpora demonstrate that the ParsingPhrase exceeds state-of-the-art baselines, is 7% higher in the candidate phrase conversion rate, and is 6% better in terms of Precision. [ABSTRACT FROM AUTHOR]

• BOP (bag of phrases) is a better text representation than BOW (bag of words). • Phrase2Vec can be solved through two stages: phrase mining and phrase embedding. • Hierarchical phrases in sentences can be mined by traversing the parse tree. • Phrase2Vec can effectively solve the problem of phrase embedding. • The BOP can improve the performance of downstream natural language processing tasks, e.g. text categorization, text clustering. Text is one of the most common unstructured data, and usually, the most primary task in text mining is to transfer the text into a structured representation. However, the existing text representation models split the complete semantic unit and neglect the order of words, finally lead to understanding bias. In this paper, we propose a novel phrase-based text representation method that takes into account the integrity of semantic units and utilizes vectors to represent the similarity relationship between texts. First, we propose HPMBP (Hierarchical Phrase Mining Based on Parsing) which mines hierarchical phrases by parsing and uses BOP (Bag Of Phrases) to represent text. Then, we put forward three phrase embedding models, called Phrase2Vec, including Skip-Phrase, CBOP (Continuous Bag Of Phrases), and GloVeFP (Global Vectors For Phrase Representation). They learn the phrase vector with semantic similarity, further obtain the vector representation of the text. Based on Phrase2Vec, we propose PETC (Phrase Embedding based Text Classification) and PETCLU (Phrase Embedding based Text Clustering). PETC utilizes the phrase embedding to get the text vector, which is fed to a neural network for text classification. PETCLU gets the vectorization expression of text and cluster center by Phrase2Vec, furthermore extends the K-means model for text clustering. To the best of our knowledge, it is the first work that focuses on the phrase-based English text representation. Experiments show that the introduced Phrase2Vec outperforms state-of-the-art phrase embedding models in the similarity task and the analogical reasoning task on Enwiki, DBLP, and Yelp dataset. PETC is superior to the baseline text classification methods in the F1-value index by about 4%. PETCLU is also ahead of the prevalent text clustering methods in entropy and purity indicators. In summary, Phrase2Vec is a promising approach to text mining. [ABSTRACT FROM AUTHOR]

In this paper we present a scheme for detecting and recovering from syntax errors in programs. The scheme, which is based on LR parsing. is driven by information which is directly and automatically obtainable from the information that is already present in an LR parser. The approach, which is patterned after that of Levy and Graham and Rhodes, appears to provide error recovery which is both simple and powerful. [ABSTRACT FROM AUTHOR]

This paper introduces an alternative lo context-free grammars called regular right part (RRP) grammars, which resemble PASCAL syntax diagrams. Formally, RRP grammars have production right parts, which are nondeterministic finite state machines (FSMs), and, as a special case, regular expressions, since these can be converted to FSMs. RRP grammars describe the syntax of programming languages more concisely and more understandably than is possible with CF grammars. Also introduced is a class of parsers, RRP LR(m, k) parsers, which includes the CF LR(k) parsers and provides the same advantages. Informally, an RRP LR(m, k) parser can determine the right end of each handle by considering at most k symbols to the right of the handle and the left end, after the right end has been found, by considering at most m symbols to the left of the handle. A mechanism for determining the left end is required because there is no bound on the length of the handle. [ABSTRACT FROM AUTHOR]

The problem of determining whether an arbitrary context-free grammar is a member of some easily parsed subclass of grammars such as the LR(k) grammars is considered. The time complexity of this problem is analyzed both when k is considered to be a fixed integer and when k is considered to be a parameter of the test. In the first case, it is shown that for every k there exists an O(nk+2) algorithm for testing the LR(k) property, where n is the size of the grammar in question. On the other hand, if both k and the subject grammar are problem parameters, then the complexity of the problem depends very strongly on the representation chosen for k. More specifically, it is shown that this problem is NP-complete when k is expressed in unary. When k is expressed in binary the problem is complete for nondeterministic exponential time. These results carry over to many other parameterized classes of grammars, such as the LL(k), strong LL(k), SLR(k), LC(k), and strong LC(k) grammars. [ABSTRACT FROM AUTHOR]

This paper describes a recovery scheme for syntax errors which provides automatically-generated high quality recovery with good diagnostic information at relatively low cost. Previous recovery techniques are summarized and empirical comparisons are made. Suggestions for further research on this topic conclude the paper. [ABSTRACT FROM AUTHOR]

This paper describes LPARS, a locally-organized parsing system, designed for use in a continuous speech recognizer. LPARS processes a string of phonemes which contains ambiguity and error. The system is locally-organized in the sense that it builds local parse structures from reliable word candidates recognized anywhere in an input utterance. These local structures are used as "islands of reliability" to guide the search for more highly garbledwords which might complete the utterance. [ABSTRACT FROM AUTHOR]

The paper describes a technique for compacting character sets in a digital computer while retaining fast access to individual bits. It considers the problem of minimizing the storage needed to contain such tables. Reduction techniques are developed, and the problem is shown to reduce to a covering problem. [ABSTRACT FROM AUTHOR]

A new parsing technique is proposed which allows parsing based only on syntactical characteristics of the decision problem. It requires a description of the problem in decision grid chart format and allows the development of decision tables within defined limits by avoiding, or at least minimizing, repetition of conditions and actions in the resulting tables. [ABSTRACT FROM AUTHOR]

Affix grammars are two-level grammars which are similar to van Wijngaarden's two-level grammars used in the definition of Algol 68. Affix grammars are shown by Koster to be equal in power to van Wijngaarden grammars. They are much more suited to parsing than are the latter, however. Koster, the inventor of affix grammars, suggests a top-down scheme for parsing them, based on recursive procedures. This paper presents a bottom-up scheme for parsing them, based on an extension of Floyd Production Language (FPL). Included is an algorithm, similar to that of DeRemer's, for converting a large class of affix grammars into FPL. The paper concludes by discussing briefly the applicabilities of the conversion algorithm and affix grammars in general, and some possible extensions to Koster's definition of affix grammars. [ABSTRACT FROM AUTHOR]

The use of augmented transition network grammars for the analysis of natural language sentences is described. Structure-building actions associated with the arcs of the grammar network allow for the reordering, restructuring, and copying of constituents necessary to produce deep-structure representations of the type normally obtained from a transformational analysis, and conditions on the arcs allow for a powerful selectivity which can rule out meaningless analyses and take advantage of semantic information to guide the parsing. The advantages of this model for natural language analysis are discussed in detail and illustrated by examples. An implementation of an experimental parsing system for transition network grammars is briefly described. [ABSTRACT FROM AUTHOR]

This paper presents a canonical form for context-sensitive derivations and a parsing algorithm which finds each context-sensitive analysis once and only once. The amount of memory required by the algorithm is essentially no more than that required to store a single complete derivation. In addition, a modified version of the basic algorithm is presented which blocks infinite analyses for grammars which contain loops. The algorithm is also compared with several previous parsers for context-sensitive grammars and general rewriting systems, and the difference between the two types of analyses is discussed. The algorithm appears to be complementary to an algorithm by S. Kuno in several respects, including the space-time trade-off and the degree of context dependence involved. [ABSTRACT FROM AUTHOR]

Although automatic syntactic and semantic analysis is not yet possible for all of an unrestricted natural language text, some applications, of which content analysis is one, do not have such a stringent coverage requirement. Preliminary studies show that the Harvard Syntactic Analyzer can produce correct and unambiguous identification of the subject and object of certain verbs for approximately half of the relevant occurrences. This provides a degree of coverage for content analysis variables which compares favorably to manual methods, in which only a sample of the total available text is normally processed. [ABSTRACT FROM AUTHOR]

A parsing algorithm which seems to be the most efficient general context-free algorithm known is described. It is similar to both Knuth's LR(k) algorithm and the familiar top-down algorithm. It has a time bound proportional to n3 (where n is the length of the string being parsed) in general; it has an n2 bound for unambiguous grammars; and it runs in linear time on a large class of grammars, which seems to include most practical context-free programming language grammars. In an empirical comparison it appears to be superior to the top-down and bottom-up algorithms studied by Griffiths and Petrick. [ABSTRACT FROM AUTHOR]

A syntactic parser is described for hierarchical concatenation patterns that are presented to the analyzer in the form of linear strings. Particular emphasis is given to the system of "significant addresses" by means of which processing times for large-wale matching procedures can be substantially reduced. The description makes frequent use of examples taken from the fully operational implementation of the parser in an experimental English sentence analyzer. By structuring an area of the computer's central core storage in such a way that the individual locations of bytes and bits come to represent the data involved in the matching procedure, the shifting of information is reduced to a minimum, and the searching of lists is eliminated altogether. The matches are traced by means of binary masks and the state of single bits determines the operational flow of the procedure. The method could be implemented with any interpretive grammar, provided it can be expressed by the functional classification of the items composing the input hierarchical structures. [ABSTRACT FROM AUTHOR]

Input limited transduction expressions, or translation equations, are used to describe the syntax and left-context sensitive semantics for context-free languages. A formal procedure is given for deriving from a set of translation equations the specifications for a pushdown translator. The translator consists of Mealy form finite-state automata interacting by means of a pushdown stack. Within the framework described, string recognition and parsing may be treated as special cases of the translation problem. [ABSTRACT FROM AUTHOR]

A program is described which produces syntactic analyses of English sentences with respect to o transformational grammar. The main features of the analyzer are that it uses only a limited dictionary of English words and that it pursues all analysis paths simultaneously while processing the sentence from left to right. The form of representation used for the dictionary and the grammar is indicated and an outline account is given of the analysis procedure. Techniques for keeping the size of the analysis record within reasonable limits and for avoiding the need for dynamic application of certain transformational rules are described. A number of examples of output produced by the program ore given. The output includes timing information. [ABSTRACT FROM AUTHOR]

The practical application of the theory of finite-state automata to automatically generate lexical processors is dealt with in this tutorial article by the use of the AED RWORD system, developed at M.I.T. as part of the AED-1 system. This system accepts as input descriptions of the multicharacter items or of words allowable in a language given in terms of a subset of regular expressions. The output of the system is a lexical processor which reads a string of characters and combines them into the items as defined by the regular expressions. Each output item is identified by a code number together with a pointer to a block of storage containing the characters and character count in the item. The processors produced by the system are based on finite- state machines. Each state of a "machine" corresponds to a unique condition in the lexical processing of a character string. At each state a character is read, and the machine changes to a new state. At each transition appropriate actions are taken based on the particular character read. The system has been in operation since 1966, and processors generated have compared favorably in speed to carefully hand-coded programs to accomplish the same task. Lexical processors for AED-0 and MAD are among the many which have been produced. The techniques employed are independent of the nature of the items being evaluated. If the word "events" is substituted for character string, these processors may be described as generalized decision-making mechanisms based upon an ordered sequence of events. This allows the system to be used in a range of applications outside the area of lexical processing. However convenient these advantages may be, speed is the most important consideration. In designing a system for automatic generation of a lexical processor, the goal was a processor which completely eliminated backup or rereading, which was nearly as fast as hand-coded processors, which would analyze the language and detect errors, and which would be convenient and easy to use. [ABSTRACT FROM AUTHOR]

Mathscout is a mathematica 1 [1] mathematica is a registered trademark of Wolfram Research Inc. package to postprocess the output of other programs for scientific calculations. We wrote mathscout to import data from a major program for ab initio computational chemistry into mathematica, so that we could postprocess the chemical results. It can be used to import the output of many other packages that are used, e.g. in molecular dynamics, crystallography, spectroscopic analysis, metabolic and physiological modeling, meteorology and other areas of environmental science, cosmology and particle physics. mathscout assigns a name to each table and non-tabular datum that it extracts. This name is constructed mechanically from the identifier or phrase that precedes or follows or embeds the item in the output that mathscout processes. A selection of non-contiguous items, or all the items in a section of the file, or in the entire file are extracted using simple commands. So far, we have focused on our immediate needs to postprocess the output of the Gaussian 2 [2] gaussian is a registered trademark of Gaussian Inc. program. Calculations on several molecules that illustrate the usage of the package are presented here and in the Supplementary Information. mathscout is shortened to msct in the software. Program summary: Program title: msct.m Catalogue identifier: ADZQ_v1_0 Program summary URL: http://cpc.cs.qub.ac.uk/summaries/ADZQ_v1_0.html Program obtainable from: CPC Program Library, Queen''s University, Belfast, N. Ireland Licensing provisions: Standard CPC licence, http://cpc.cs.qub.ac.uk/licence/licence.html No. of lines in distributed program, including test data, etc.: 30 396 No. of bytes in distributed program, including test data, etc.: 1 799 469 Distribution format: tar.gz Programming language: Mathematica Computer: Any computer running unix and Mathematica Operating system: Unix Supplementary material: The Development guide Classification: 4.14, 5, 16.1, 20 Nature of problem: Import data from output files of scientific computing packages, such as Gaussian, into Mathematica for symbolic calculation and production of publication quality tables and plots. Solution method: Provision of mnemonic top-down parsing procedures, functional programming. Running time: The complete extraction of data from a small basis density functional calculation on the water molecule, and from a larger basis density functional calculation on the zinc hydrate ion, that ran to 33 iterations, took 1 second and 23 seconds, respectively, on a Dell Poweredge 1750. [Copyright &y& Elsevier]

The 20th century is a time where often science fiction quickly becomes reality. Many of today's realities, including submarines, trips to the moon, and communications satellites, first appeared on the […]

Abstract: Negating a natural language statement may require more than a unary negation operator. Categories and Subject Descriptors: Antonym; morpheme; polysemy; copula; unnatural language; De Morgan; Uncle Jack; Python, Monty; […]

ALTHOUGH THE WORD "PROLOG" DERIVES FROM "PROGRAMMING LOGICALLY," THE LANGUAGE WAS INVENTED BY ALAIN COLMERAUER FOR NATURAL-LANGUAGE PROCESSING. MANY THINK OF PROLOG AS BEING PRIMARILY FOR EXPERT SYSTEMS, BUT THE […]

Product Information Parser/TP, v2.5 (02/14/94) Author: Ron Loewy HyperAct, Inc. P.O. Box 5517 Coralville, IA 52241 USA Email: CompuServe [76350,333] Phone/Fax: +1 319 351 8413 Registration: $30 U.S. ($40 elsewhere), […]

CAPABILITY FILES One of the great innovations of Berkeley UNIX was the inclusion of a set of routines that could run the vi screen editor on a wide variety of […]

YACC ATTACK II: RETURN OF THE PARSER In an earlier column (UNIX REVIEW, Vol. 6 No. 9), I tried to convince all you acolytes to try to parse a language […]

C ADVISOR Sooner or later, most of us will have to write a program that will require some non-trivial parsing of input. If the syntax of the input is fairly […]

Natural LANGUAGE QUERY Processing Natural-language access to database systems was one of the earliest commercial applications of AI technology. Relational databases have increased the viability of a general mechanism for […]

NLP TAKES OFF After years of looking as though it might never leave the runway, natural language processing is approaching takeoff as a commercial computing technology. The signs are multiplying: […]

literate programming WEAVING A LANGUAGE-INDEPENDENT WEB In the fall of 1987 I started planning the implementation of a suite of tools for building verified Ada programs [5]. The first tool […]

MKS Lex & YACC v. 3.1 have been announced by Mortice Kern Systems Inc. In this upgrade to its fully UNIX compatible scanner and parser generator, MKS has added YACC […]

Parsifal Software has released AnaGram, an extended LALR-1 parser generator. AnaGram supports lexical analysis in its grammar rules, and its notation links grammar tokens clearly to processing code. Parsers may […]

MicroQuill Software Publishing has acquired Autom's LALR Parser Generator. LALR is an alternative to YACC for programmers building compilers, interpreters, and macro languages. The features of LALR include the following: […]

MKS has released a major upgrade to its UNIX-compible scanner and parser and parser generators. The package now includes YACC Tracker, a diagnostic aid that allows programmers to see inside […]

SAN MATEO, Calif.--Looking to maintain high levels of performance for applications accessing multiple databases, Trifox last week introduced a set of tools called Vortex that allows applications to use shared-parsing […]

This volume contains a collection of small C utilities contributed by 12 authors. Most of the programs were developed under MS-DOS, but some programs are portable enough to be compiled […]