Log in

Relevant bibliographies by topics / Parsing (computer grammar) / Journal articles

To see the other types of publications on this topic, follow the link: Parsing (computer grammar).

Journal articles on the topic 'Parsing (computer grammar)'

Author: Grafiati

Published: 4 June 2021

Last updated: 29 July 2024

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the top 50 journal articles for your research on the topic 'Parsing (computer grammar).'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.

1

Handzhiyski, Nikolay, and Elena Somova. "Tunnel Parsing with Ambiguous Grammars." Cybernetics and Information Technologies 23, no. 2 (June 1, 2023): 34–53. http://dx.doi.org/10.2478/cait-2023-0012.

Full text

Abstract:

Abstract The article proposes an addition to the tunnel parsing algorithm that enables it to parse grammars having countable repetitions and configurations of grammar elements generating empty words without refactoring the grammar. The equivalency of trees built by the use of ambiguous grammar is discussed. The class of the ε-ambiguous grammars is defined as a subclass of the ambiguous grammars relative to these trees. The ε-deterministic grammars are then defined as a subclass of the ε-ambiguous grammars. A technique for linearly parsing on the basis of non-left recursive ε-deterministic grammars with the tunnel parsing algorithm is shown.

APA, Harvard, Vancouver, ISO, and other styles

2

Zhang, Songmao. "Story Parsing Grammar." Journal of Computer Science and Technology 9, no. 3 (July 1994): 215–28. http://dx.doi.org/10.1007/bf02939503.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Kuhlmann, Marco, Giorgio Satta, and Peter Jonsson. "On the Complexity of CCG Parsing." Computational Linguistics 44, no. 3 (September 2018): 447–82. http://dx.doi.org/10.1162/coli_a_00324.

Full text

Abstract:

We study the parsing complexity of Combinatory Categorial Grammar (CCG) in the formalism of Vijay-Shanker and Weir ( 1994 ). As our main result, we prove that any parsing algorithm for this formalism will take in the worst case exponential time when the size of the grammar, and not only the length of the input sentence, is included in the analysis. This sets the formalism of Vijay-Shanker and Weir ( 1994 ) apart from weakly equivalent formalisms such as Tree Adjoining Grammar, for which parsing can be performed in time polynomial in the combined size of grammar and input sentence. Our results contribute to a refined understanding of the class of mildly context-sensitive grammars, and inform the search for new, mildly context-sensitive versions of CCG.

APA, Harvard, Vancouver, ISO, and other styles

4

Shi, Zhi Yuan, Yu Qiang Sun, Yu Wan Gu, Fu Quan Ji, and Jing Fen Du. "The Study about Parsing of RGG Grammar." Advanced Materials Research 204-210 (February 2011): 255–58. http://dx.doi.org/10.4028/www.scientific.net/amr.204-210.255.

Full text

Abstract:

Visualization is the main form of human-computer interaction. The grammar formal description of visual language opens and explores the s application cope and theoretical research field of grammar. At present, graph grammar describing visual language is one of the best the formal methods. In the paper, formal parsing method of RGG grammar is studied deeply, a parsing algorithm about RGG grammar is described, and its application on Petri net is discussed.

APA, Harvard, Vancouver, ISO, and other styles

5

BORDIM, JACIR L., OSCAR H. IBARRA, YASUAKI ITO, and KOJI NAKANO. "INSTANCE-SPECIFIC SOLUTIONS FOR ACCELERATING THE CKY PARSING OF LARGE CONTEXT-FREE GRAMMARS." International Journal of Foundations of Computer Science 15, no. 02 (April 2004): 403–15. http://dx.doi.org/10.1142/s0129054104002492.

Full text

Abstract:

The main contribution of this paper is an FPGA-based implementation of an instance-specific hardware which accelerates the CKY (Cocke-Kasami- Younger) parsing of context-free grammars. Given a context-free grammar G and a string x, the CKY parsing determines whether G derives x. We developed a hardware generator that creates a Verilog HDL source to perform the CKY parsing for any fixed context-free grammar G. The generated source is embedded in an FPGA using the design software provided by the FPGA vendor. The results show that our instance-specific hardware solution attains an astonishing speed-up factor of up to 3,700 over traditional software solutions.

APA, Harvard, Vancouver, ISO, and other styles

6

Kallmeyer, L., W. Maier, Y. Parmentier, and J. Dellert. "TuLiPA - Parsing extensions of TAG with range concatenation grammars." Bulletin of the Polish Academy of Sciences: Technical Sciences 58, no. 3 (September 1, 2010): 377–91. http://dx.doi.org/10.2478/v10175-010-0036-0.

Full text

Abstract:

TuLiPA - Parsing extensions of TAG with range concatenation grammarsIn this paper we present a parsing framework for extensions of Tree Adjoining Grammar (TAG) called TuLiPA (Tübingen Linguistic Parsing Architecture). In particular, besides TAG, the parser can process Tree-Tuple MCTAG with Shared Nodes (TT-MCTAG), a TAG-extension which has been proposed to deal with scrambling in free word order languages such as German. The central strategy of the parser is such that the incoming TT-MCTAG (or TAG) is transformed into an equivalent Range Concatenation Grammar (RCG) which, in turn, is then used for parsing. The RCG parser is an incremental Earley-style chart parser. In addition to the syntactic anlysis, TuLiPA computes also an underspecified semantic analysis for grammars that are equipped with semantic representations.

APA, Harvard, Vancouver, ISO, and other styles

7

Underwood, William. "Grammar-Based Specification and Parsing of Binary File Formats." International Journal of Digital Curation 7, no. 1 (March 9, 2012): 95–106. http://dx.doi.org/10.2218/ijdc.v7i1.217.

Full text

Abstract:

The capability to validate and view or play binary file formats, as well as to convert binary file formats to standard or current file formats, is critically important to the preservation of digital data and records. This paper describes the extension of context-free grammars from strings to binary files. Binary files are arrays of data types, such as long and short integers, floating-point numbers and pointers, as well as characters. The concept of an attribute grammar is extended to these context-free array grammars. This attribute grammar has been used to define a number of chunk-based and directory-based binary file formats. A parser generator has been used with some of these grammars to generate syntax checkers (recognizers) for validating binary file formats. Among the potential benefits of an attribute grammar-based approach to specification and parsing of binary file formats is that attribute grammars not only support format validation, but support generation of error messages during validation of format, validation of semantic constraints, attribute value extraction (characterization), generation of viewers or players for file formats, and conversion to current or standard file formats. The significance of these results is that with these extensions to core computer science concepts, traditional parser/compiler technologies can potentially be used as a part of a general, cost effective curation strategy for binary file formats.

APA, Harvard, Vancouver, ISO, and other styles

8

Handzhiyski, Nikolay, and Elena Somova. "Tunnel Parsing with the Token’s Lexeme." Cybernetics and Information Technologies 22, no. 2 (June 1, 2022): 125–44. http://dx.doi.org/10.2478/cait-2022-0021.

Full text

Abstract:

Abstract The article describes a string recognition approach, engraved in the parsers generated by Tunnel Grammar Studio that use the tunnel parsing algorithm, of how a lexer and a parser can operate on the input during its recognition. Proposed is an addition of the augmented Backus-Naur form syntax that enables the formal language to be expressed with a parser grammar and optionally with an additional lexer grammar. The tokens outputted from the lexer are matched to the phrases in the parser grammar by their name and optionally by their lexeme, case sensitively or insensitively.

APA, Harvard, Vancouver, ISO, and other styles

9

Zhang, Songmao. "Weak precedence story parsing grammar." Journal of Computer Science and Technology 10, no. 1 (January 1995): 53–64. http://dx.doi.org/10.1007/bf02939522.

Full text

APA, Harvard, Vancouver, ISO, and other styles

10

Kulkarni, Amba. "Sanskrit Parsing Following Indian Theories of Verbal Cognition." ACM Transactions on Asian and Low-Resource Language Information Processing 20, no. 2 (April 8, 2021): 1–38. http://dx.doi.org/10.1145/3418061.

Full text

Abstract:

Pāṇini’s grammar is an important milestone in the Indian grammatical tradition. Unlike grammars of other languages, it is almost exhaustive and together with the theories of śābdabodha (verbal cognition), this grammar provides a system for language analysis as well as generation. The theories of śābdabodha describe three conditions necessary for verbal cognition. They are ākāṅkṣā (expectancy), yogyatā (meaning congruity), and sannidhi (proximity). We examine them from a computational viewpoint and provide appropriate computational models for their representation. Next, we describe the design of a parser following the theories of śābdabodha and present three algorithms for solving the constraints imposed by the theories of śābdabodha . The first algorithm is modeled as a constraint satisfaction problem, the second one as a vertex-centric graph traversal, and the third one as an edge-centric binary join, each one being an improvement over the previous one.

APA, Harvard, Vancouver, ISO, and other styles

11

Gildea, Daniel, and Giorgio Satta. "Synchronous Context-Free Grammars and Optimal Parsing Strategies." Computational Linguistics 42, no. 2 (June 2016): 207–43. http://dx.doi.org/10.1162/coli_a_00246.

Full text

Abstract:

The complexity of parsing with synchronous context-free grammars is polynomial in the sentence length for a fixed grammar, but the degree of the polynomial depends on the grammar. Specifically, the degree depends on the length of rules, the permutations represented by the rules, and the parsing strategy adopted to decompose the recognition of a rule into smaller steps. We address the problem of finding the best parsing strategy for a rule, in terms of space and time complexity. We show that it is NP-hard to find the binary strategy with the lowest space complexity. We also show that any algorithm for finding the strategy with the lowest time complexity would imply improved approximation algorithms for finding the treewidth of general graphs.

APA, Harvard, Vancouver, ISO, and other styles

12

Mohamad Zulkufli, Nurul Liyana, Sherzod Turaev, Mohd Izzuddin Mohd Tamrin, and Azeddine Messikh. "Watson–Crick Context-Free Grammars: Grammar Simplifications and a Parsing Algorithm." Computer Journal 61, no. 9 (January 10, 2018): 1361–73. http://dx.doi.org/10.1093/comjnl/bxx128.

Full text

APA, Harvard, Vancouver, ISO, and other styles

13

Gebhardt, Kilian, Mark-Jan Nederhof, and Heiko Vogler. "Hybrid Grammars for Parsing of Discontinuous Phrase Structures and Non-Projective Dependency Structures." Computational Linguistics 43, no. 3 (September 2017): 465–520. http://dx.doi.org/10.1162/coli_a_00291.

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

14

Flasiński, Mariusz. "Interpreted Graphs and ETPR(k) Graph Grammar Parsing for Syntactic Pattern Recognition." Machine Graphics and Vision 27, no. 1/4 (December 1, 2019): 3–19. http://dx.doi.org/10.22630/mgv.2018.27.1.1.

Full text

Abstract:

Further results of research into graph grammar parsing for syntactic pattern recognition (Pattern Recognit. 21:623-629, 1988; 23:765-774, 1990; 24:1223-1224, 1991; 26:1-16, 1993; 43:249-2264, 2010; Comput. Vision Graph. Image Process. 47:1-21, 1989; Fundam. Inform. 80:379-413, 2007; Theoret. Comp. Sci. 201:189-231, 1998) are presented in the paper. The notion of interpreted graphs based on Tarski's model theory is introduced. The bottom-up parsing algorithm for ETPR(k) graph grammars is defined.

APA, Harvard, Vancouver, ISO, and other styles

15

Kuhlmann, Marco. "Mildly Non-Projective Dependency Grammar." Computational Linguistics 39, no. 2 (June 2013): 355–87. http://dx.doi.org/10.1162/coli_a_00125.

Full text

Abstract:

Syntactic representations based on word-to-word dependencies have a long-standing tradition in descriptive linguistics, and receive considerable interest in many applications. Nevertheless, dependency syntax has remained something of an island from a formal point of view. Moreover, most formalisms available for dependency grammar are restricted to projective analyses, and thus not able to support natural accounts of phenomena such as wh-movement and cross–serial dependencies. In this article we present a formalism for non-projective dependency grammar in the framework of linear context-free rewriting systems. A characteristic property of our formalism is a close correspondence between the non-projectivity of the dependency trees admitted by a grammar on the one hand, and the parsing complexity of the grammar on the other. We show that parsing with unrestricted grammars is intractable. We therefore study two constraints on non-projectivity, block-degree and well-nestedness. Jointly, these two constraints define a class of “mildly” non-projective dependency grammars that can be parsed in polynomial time. An evaluation on five dependency treebanks shows that these grammars have a good coverage of empirical data.

APA, Harvard, Vancouver, ISO, and other styles

16

Leber, Žiga, Matej Črepinšek, Marjan Mernik, and Tomaž Kosar. "RNGSGLR: Generalization of the Context-Aware Scanning Architecture for All Character-Level Context-Free Languages." Mathematics 10, no. 14 (July 13, 2022): 2436. http://dx.doi.org/10.3390/math10142436.

Full text

Abstract:

The limitations of traditional parsing architecture are well known. Even when paired with parsing methods that accept all context-free grammars (CFGs), the resulting combination for any given CFG accepts only a limited subset of corresponding character-level context-free languages (CFL). We present a novel scanner-based architecture that for any given CFG accepts all corresponding character-level CFLs. It can directly parse all possible specifications consisting of a grammar and regular definitions. The architecture is based on right-nulled generalized LR (RNGLR) parsing and is a generalization of the context-aware scanning architecture. Our architecture does not require any disambiguation rules to resolve lexical conflicts, it conceptually has an unbounded parser and scanner lookahead and it is streaming. The added robustness and flexibility allow for easier grammar development and modification.

APA, Harvard, Vancouver, ISO, and other styles

17

Cousot, Patrick, and Radhia Cousot. "Parsing as abstract interpretation of grammar semantics." Theoretical Computer Science 290, no. 1 (January 2003): 531–44. http://dx.doi.org/10.1016/s0304-3975(02)00034-8.

Full text

APA, Harvard, Vancouver, ISO, and other styles

18

Fu, Z., and A. de Pennington. "Geometric Reasoning Based on Graph Grammar Parsing." Journal of Mechanical Design 116, no. 3 (September 1, 1994): 763–69. http://dx.doi.org/10.1115/1.2919448.

Full text

Abstract:

It has been recognized that future intelligent design support environments need to reason about the geometry of products and to evaluate product functionality and performance against given constraints. A first step towards this goal is to provide a more robust information model which directly relates to design functionality or manufacturing characteristics, on which reasoning can be carried out. This has motivated research on feature-based modelling and reasoning. In this paper, an approach is presented to geometric reasoning based on graph grammar parsing. Our approach is presented to geometric reasoning based on graph grammar parsing. Our work combines methodologies from both design by features and feature recognition. A graph grammar is used to represent and manipulate features and geometric constraints. Geometric constraints are used within symbolical definitions of features constraints. Geometric constraints are used within symbolical definitions of features and also to define relative position and orientation of features. The graph grammar parsing is incorporated with knowledge-based inference to derive feature information and propagate constraints. This approach can be used for the transformation of feature information and to deal with feature interaction.

APA, Harvard, Vancouver, ISO, and other styles

19

Cousot, Patrick, and Radhia Cousot. "Grammar semantics, analysis and parsing by abstract interpretation." Theoretical Computer Science 412, no. 44 (October 2011): 6135–92. http://dx.doi.org/10.1016/j.tcs.2011.06.005.

Full text

APA, Harvard, Vancouver, ISO, and other styles

20

Morrill, Glyn. "Parsing/Theorem-Proving for Logical Grammar CatLog3." Journal of Logic, Language and Information 28, no. 2 (January 18, 2019): 183–216. http://dx.doi.org/10.1007/s10849-018-09277-w.

Full text

APA, Harvard, Vancouver, ISO, and other styles

21

Bao, Lei. "A Trajectory Classification Model Using Grammar Parsing." IEEE Access 8 (2020): 218416–23. http://dx.doi.org/10.1109/access.2020.3042614.

Full text

APA, Harvard, Vancouver, ISO, and other styles

22

Green, Spence, Marie-Catherine de Marneffe, and Christopher D. Manning. "Parsing Models for Identifying Multiword Expressions." Computational Linguistics 39, no. 1 (March 2013): 195–227. http://dx.doi.org/10.1162/coli_a_00139.

Full text

Abstract:

Multiword expressions lie at the syntax/semantics interface and have motivated alternative theories of syntax like Construction Grammar. Until now, however, syntactic analysis and multiword expression identification have been modeled separately in natural language processing. We develop two structured prediction models for joint parsing and multiword expression identification. The first is based on context-free grammars and the second uses tree substitution grammars, a formalism that can store larger syntactic fragments. Our experiments show that both models can identify multiword expressions with much higher accuracy than a state-of-the-art system based on word co-occurrence statistics. We experiment with Arabic and French, which both have pervasive multiword expressions. Relative to English, they also have richer morphology, which induces lexical sparsity in finite corpora. To combat this sparsity, we develop a simple factored lexical representation for the context-free parsing model. Morphological analyses are automatically transformed into rich feature tags that are scored jointly with lexical items. This technique, which we call a factored lexicon, improves both standard parsing and multiword expression identification accuracy.

APA, Harvard, Vancouver, ISO, and other styles

23

Chen, Zhousi, and Mamoru Komachi. "Discontinuous Combinatory Constituency Parsing." Transactions of the Association for Computational Linguistics 11 (2023): 267–83. http://dx.doi.org/10.1162/tacl_a_00546.

Full text

Abstract:

Abstract We extend a pair of continuous combinator-based constituency parsers (one binary and one multi-branching) into a discontinuous pair. Our parsers iteratively compose constituent vectors from word embeddings without any grammar constraints. Their empirical complexities are subquadratic. Our extension includes 1) a swap action for the orientation-based binary model and 2) biaffine attention for the chunker-based multi-branching model. In tests conducted with the Discontinuous Penn Treebank and TIGER Treebank, we achieved state-of-the-art discontinuous accuracy with a significant speed advantage.

APA, Harvard, Vancouver, ISO, and other styles

24

Choi, Key-Sun, and Gil Chang Kim. "A controlled quantification in parsing of montague grammar." Information Processing Letters 22, no. 4 (April 1986): 207–16. http://dx.doi.org/10.1016/0020-0190(86)90030-x.

Full text

APA, Harvard, Vancouver, ISO, and other styles

25

Cahill, Aoife, Michael Burke, Ruth O'Donovan, Stefan Riezler, Josef van Genabith, and Andy Way. "Wide-Coverage Deep Statistical Parsing Using Automatic Dependency Structure Annotation." Computational Linguistics 34, no. 1 (March 2008): 81–124. http://dx.doi.org/10.1162/coli.2008.34.1.81.

Full text

Abstract:

A number of researchers have recently conducted experiments comparing “deep” hand-crafted wide-coverage with “shallow” treebank- and machine-learning-based parsers at the level of dependencies, using simple and automatic methods to convert tree output generated by the shallow parsers into dependencies. In this article, we revisit such experiments, this time using sophisticated automatic LFG f-structure annotation methodologies with surprising results. We compare various PCFG and history-based parsers to find a baseline parsing system that fits best into our automatic dependency structure annotation technique. This combined system of syntactic parser and dependency structure annotation is compared to two hand-crafted, deep constraint-based parsers, RASP and XLE. We evaluate using dependency-based gold standards and use the Approximate Randomization Test to test the statistical significance of the results. Our experiments show that machine-learning-based shallow grammars augmented with sophisticated automatic dependency annotation technology outperform hand-crafted, deep, wide-coverage constraint grammars. Currently our best system achieves an f-score of 82.73% against the PARC 700 Dependency Bank, a statistically significant improvement of 2.18% over the most recent results of 80.55% for the hand-crafted LFG grammar and XLE parsing system and an f-score of 80.23% against the CBS 500 Dependency Bank, a statistically significant 3.66% improvement over the 76.57% achieved by the hand-crafted RASP grammar and parsing system.

APA, Harvard, Vancouver, ISO, and other styles

26

Rodriguez-Leon, C., and L. Garcia-Forte. "Solving difficult LR parsing conflicts by postponing them." Computer Science and Information Systems 8, no. 2 (2011): 517–31. http://dx.doi.org/10.2298/csis101116008r.

Full text

Abstract:

Though yacc-like LR parser generators provide ways to solve shift-reduce conflicts using token precedences, no mechanisms are provided for the resolution of difficult shift-reduce or reduce-reduce conflicts. To solve this kind of conflicts the language designer has to modify the grammar. All the solutions for dealing with these difficult conflicts branch at each alternative, leading to the exploration of the whole search tree. These strategies differ in the way the tree is explored: GLR, Backtracking LR, Backtracking LR with priorities, etc. This paper explores an entirely different path: to extend the yacc conflict resolution sublanguage with new constructs allowing the programmers to explicit the way the conflict must be solved. These extensions supply ways to resolve any kind of conflicts, including those that can not be solved using static precedences. The method makes also feasible the parsing of grammars whose ambiguity must be solved in terms of the semantic context. Besides, it brings to LR-parsing a common LL-parsing feature: the advantage of providing full control over the specific trees the user wants to build.

APA, Harvard, Vancouver, ISO, and other styles

27

Jabri, Riad. "A generic parser for strings and trees." Computer Science and Information Systems 9, no. 1 (2012): 381–410. http://dx.doi.org/10.2298/csis101109004j.

Full text

Abstract:

In this paper, we propose a two fold generic parser. First, it simulates the behavior of multiple parsing automata. Second, it parses strings drawn from either a context free grammar, a regular tree grammar, or from both. The proposed parser is based on an approach that defines an extended version of an automaton, called positionparsing automaton (PPA) using concepts from LR and regular tree automata, combined with a newly introduced concept, called state instantiation and transition cloning. It is constructed as a direct mapping from a grammar, represented in an expanded list format. However, PPA is a non-deterministic automaton with a generic bottom-up parsing behavior. Hence, it is efficiently transformed into a reduced one (RBA). The proposed parser is then constructed to simulate the run of the RBA automaton on input strings derived from a respective grammar. Without loss of generality, the proposed parser is used within the framework of pattern matching and code generation. Comparisons with similar and well-known approaches, such as LR and RI, have shown that our parsing algorithm is conceptually simpler and requires less space and states.

APA, Harvard, Vancouver, ISO, and other styles

28

Kromann, Matthias Trautner. "Optimality parsing and local cost functions in Discontinuous Grammar." Electronic Notes in Theoretical Computer Science 53 (April 2004): 163–79. http://dx.doi.org/10.1016/s1571-0661(05)82581-2.

Full text

APA, Harvard, Vancouver, ISO, and other styles

29

Clark, Stephen, and James R. Curran. "Wide-Coverage Efficient Statistical Parsing with CCG and Log-Linear Models." Computational Linguistics 33, no. 4 (December 2007): 493–552. http://dx.doi.org/10.1162/coli.2007.33.4.493.

Full text

Abstract:

This article describes a number of log-linear parsing models for an automatically extracted lexicalized grammar. The models are “full” parsing models in the sense that probabilities are defined for complete parses, rather than for independent events derived by decomposing the parse tree. Discriminative training is used to estimate the models, which requires incorrect parses for each sentence in the training data as well as the correct parse. The lexicalized grammar formalism used is Combinatory Categorial Grammar (CCG), and the grammar is automatically extracted from CCGbank, a CCG version of the Penn Treebank. The combination of discriminative training and an automatically extracted grammar leads to a significant memory requirement (up to 25 GB), which is satisfied using a parallel implementation of the BFGS optimization algorithm running on a Beowulf cluster. Dynamic programming over a packed chart, in combination with the parallel implementation, allows us to solve one of the largest-scale estimation problems in the statistical parsing literature in under three hours. A key component of the parsing system, for both training and testing, is a Maximum Entropy supertagger which assigns CCG lexical categories to words in a sentence. The supertagger makes the discriminative training feasible, and also leads to a highly efficient parser. Surprisingly, given CCG's “spurious ambiguity,” the parsing speeds are significantly higher than those reported for comparable parsers in the literature. We also extend the existing parsing techniques for CCG by developing a new model and efficient parsing algorithm which exploits all derivations, including CCG's nonstandard derivations. This model and parsing algorithm, when combined with normal-form constraints, give state-of-the-art accuracy for the recovery of predicate-argument dependencies from CCGbank. The parser is also evaluated on DepBank and compared against the RASP parser, outperforming RASP overall and on the majority of relation types. The evaluation on DepBank raises a number of issues regarding parser evaluation. This article provides a comprehensive blueprint for building a wide-coverage CCG parser. We demonstrate that both accurate and highly efficient parsing is possible with CCG.

APA, Harvard, Vancouver, ISO, and other styles

30

Rosen, D. W., J. R. Dixon, and S. Finger. "Conversions of Feature-Based Design Representations Using Graph Grammar Parsing." Journal of Mechanical Design 116, no. 3 (September 1, 1994): 785–92. http://dx.doi.org/10.1115/1.2919451.

Full text

Abstract:

In order to trade off required functionality with manufacturing, cost, and other life-cycle considerations, it is necessary to evaluate designs in these secondary view-points. Representations of mechanical components designed with design features must be converted into representations containing relevant secondary viewpoint features. When describing a design verbally, designers often use languages of design features. In other viewpoints, different languages of viewpoint-specific features are used. Thus, translation capability between viewpoint languages is needed to convert from one representation to another. The approach taken here is to use formal graph grammars to define the feature-based design of thin-walled components and the secondary feature languages. Features are defined by graphs that explicitly represent the feature, its geometric entities, and their connectivity. Components are built up by combining feature graphs based on designer specified feature connectivity. To convert from the design to a secondary viewpoint, a three-step process is used where the last step is parsing by a grammar from the secondary viewpoint. To illustrate the conversion process, a converter for tool cost evaluation in injection molding and die casting is developed and applied to an example component.

APA, Harvard, Vancouver, ISO, and other styles

31

Redziejowski, Roman R. "Applying Classical Concepts to Parsing Expression Grammar." Fundamenta Informaticae 93, no. 1-3 (2009): 325–36. http://dx.doi.org/10.3233/fi-2009-0105.

Full text

APA, Harvard, Vancouver, ISO, and other styles

32

Gardent, Claire, and Shashi Narayan. "Multiple Adjunction in Feature-Based Tree-Adjoining Grammar." Computational Linguistics 41, no. 1 (March 2015): 41–70. http://dx.doi.org/10.1162/coli_a_00217.

Full text

Abstract:

In parsing with Tree Adjoining Grammar (TAG), independent derivations have been shown by Schabes and Shieber (1994) to be essential for correctly supporting syntactic analysis, semantic interpretation, and statistical language modeling. However, the parsing algorithm they propose is not directly applicable to Feature-Based TAGs (FB-TAG). We provide a recognition algorithm for FB-TAG that supports both dependent and independent derivations. The resulting algorithm combines the benefits of independent derivations with those of Feature-Based grammars. In particular, we show that it accounts for a range of interactions between dependent vs. independent derivation on the one hand, and syntactic constraints, linear ordering, and scopal vs. nonscopal semantic dependencies on the other hand.

APA, Harvard, Vancouver, ISO, and other styles

33

Strübbe, S., I. Sidorenko, A. Grünwald, and R. Lampe. "Semantic approach for solving the decision problem in natural language." Journal of Physics: Conference Series 2514, no. 1 (May 1, 2023): 012019. http://dx.doi.org/10.1088/1742-6596/2514/1/012019.

Full text

Abstract:

Abstract Every language, whether formal or natural, has a corresponding decision problem, the problem of whether a statement is well-formed and a valid sentence of the language. While compilers usually solve the decision problem for a computer language during compilation, there is no mathematical method to solve the decision problem in natural language. Although a human can use natural language grammar to reason whether a sentence is correct, computers have problems with this because natural language grammar is not a closed theory. We show that the decision problem for the German language can not be solved entirely by phrase structure grammar, dependency parsing or grammar checkers and develop a parser for the German language, which solves the decision problem for that language using a new semantic approach.

APA, Harvard, Vancouver, ISO, and other styles

34

Kumari, B. Venkata Seshu, and Ramisetty Rajeshwara Rao. "Improving Telugu Dependency Parsing using Combinatory Categorial Grammar Supertags." ACM Transactions on Asian and Low-Resource Language Information Processing 14, no. 1 (January 30, 2015): 1–10. http://dx.doi.org/10.1145/2693190.2693191.

Full text

APA, Harvard, Vancouver, ISO, and other styles

35

Nirmal, Yumnam, and Utpal Sharma. "A Context-Free Grammar for Parsing Manipuri Language." Journal of Computer Science 17, no. 9 (September 1, 2021): 855–69. http://dx.doi.org/10.3844/jcssp.2021.855.869.

Full text

APA, Harvard, Vancouver, ISO, and other styles

36

Nirmal, Yumnam, and Utpal Sharma. "A Context-Free Grammar for Parsing Manipuri Language." Journal of Computer Science 17, no. 9 (September 1, 2021): 857–69. http://dx.doi.org/10.3844/jcssp.2021.857.869.

Full text

APA, Harvard, Vancouver, ISO, and other styles

37

Gildea, Daniel. "Grammar Factorization by Tree Decomposition." Computational Linguistics 37, no. 1 (March 2011): 231–48. http://dx.doi.org/10.1162/coli_a_00040.

Full text

Abstract:

We describe the application of the graph-theoretic property known as treewidth to the problem of finding efficient parsing algorithms. This method, similar to the junction tree algorithm used in graphical models for machine learning, allows automatic discovery of efficient algorithms such as the O(n4) algorithm for bilexical grammars of Eisner and Satta. We examine the complexity of applying this method to parsing algorithms for general Linear Context-Free Rewriting Systems. We show that any polynomial-time algorithm for this problem would imply an improved approximation algorithm for the well-studied treewidth problem on general graphs.

APA, Harvard, Vancouver, ISO, and other styles

38

Cohen, Shay B., and Daniel Gildea. "Parsing Linear Context-Free Rewriting Systems with Fast Matrix Multiplication." Computational Linguistics 42, no. 3 (September 2016): 421–55. http://dx.doi.org/10.1162/coli_a_00254.

Full text

Abstract:

We describe a recognition algorithm for a subset of binary linear context-free rewriting systems (LCFRS) with running time O(nωd) where M(m) = O(mω) is the running time for m × m matrix multiplication and d is the “contact rank” of the LCFRS—the maximal number of combination and non-combination points that appear in the grammar rules. We also show that this algorithm can be used as a subroutine to obtain a recognition algorithm for general binary LCFRS with running time O(nωd+1). The currently best known ω is smaller than 2.38. Our result provides another proof for the best known result for parsing mildly context-sensitive formalisms such as combinatory categorial grammars, head grammars, linear indexed grammars, and tree-adjoining grammars, which can be parsed in time O(n4.76). It also shows that inversion transduction grammars can be parsed in time O(n5.76). In addition, binary LCFRS subsumes many other formalisms and types of grammars, for some of which we also improve the asymptotic complexity of parsing.

APA, Harvard, Vancouver, ISO, and other styles

39

Gómez-Rodríguez, Carlos, John Carroll, and David Weir. "Dependency Parsing Schemata and Mildly Non-Projective Dependency Parsing." Computational Linguistics 37, no. 3 (September 2011): 541–86. http://dx.doi.org/10.1162/coli_a_00060.

Full text

Abstract:

We introduce dependency parsing schemata, a formal framework based on Sikkel's parsing schemata for constituency parsers, which can be used to describe, analyze, and compare dependency parsing algorithms. We use this framework to describe several well-known projective and non-projective dependency parsers, build correctness proofs, and establish formal relationships between them. We then use the framework to define new polynomial-time parsing algorithms for various mildly non-projective dependency formalisms, including well-nested structures with their gap degree bounded by a constant k in time O(n5+2k), and a new class that includes all gap degree k structures present in several natural language treebanks (which we call mildly ill-nested structures for gap degree k) in time O(n4+3k). Finally, we illustrate how the parsing schema framework can be applied to Link Grammar, a dependency-related formalism.

APA, Harvard, Vancouver, ISO, and other styles

40

Gildea, Daniel, Giorgio Satta, and Xiaochang Peng. "Ordered Tree Decomposition for HRG Rule Extraction." Computational Linguistics 45, no. 2 (June 2019): 339–79. http://dx.doi.org/10.1162/coli_a_00350.

Full text

Abstract:

We present algorithms for extracting Hyperedge Replacement Grammar (HRG) rules from a graph along with a vertex order. Our algorithms are based on finding a tree decomposition of smallest width, relative to the vertex order, and then extracting one rule for each node in this structure. The assumption of a fixed order for the vertices of the input graph makes it possible to solve the problem in polynomial time, in contrast to the fact that the problem of finding optimal tree decompositions for a graph is NP-hard. We also present polynomial-time algorithms for parsing based on our HRGs, where the input is a vertex sequence and the output is a graph structure. The intended application of our algorithms is grammar extraction and parsing for semantic representation of natural language. We apply our algorithms to data annotated with Abstract Meaning Representations and report on the characteristics of the resulting grammars.

APA, Harvard, Vancouver, ISO, and other styles

41

Fraser, Alexander, Helmut Schmid, Richárd Farkas, Renjing Wang, and Hinrich Schütze. "Knowledge Sources for Constituent Parsing of German, a Morphologically Rich and Less-Configurational Language." Computational Linguistics 39, no. 1 (March 2013): 57–85. http://dx.doi.org/10.1162/coli_a_00135.

Full text

Abstract:

We study constituent parsing of German, a morphologically rich and less-configurational language. We use a probabilistic context-free grammar treebank grammar that has been adapted to the morphologically rich properties of German by markovization and special features added to its productions. We evaluate the impact of adding lexical knowledge. Then we examine both monolingual and bilingual approaches to parse reranking. Our reranking parser is the new state of the art in constituency parsing of the TIGER Treebank. We perform an analysis, concluding with lessons learned, which apply to parsing other morphologically rich and less-configurational languages.

APA, Harvard, Vancouver, ISO, and other styles

42

Redziejowski, Roman R. "BITES Instead of FIRST for Parsing Expression Grammar." Fundamenta Informaticae 109, no. 3 (2011): 323–37. http://dx.doi.org/10.3233/fi-2011-514.

Full text

APA, Harvard, Vancouver, ISO, and other styles

43

Nesson, Rebecca, Giorgio Satta, and Stuart M. Shieber. "Complexity, Parsing, and Factorization of Tree-Local Multi-Component Tree-Adjoining Grammar." Computational Linguistics 36, no. 3 (September 2010): 443–80. http://dx.doi.org/10.1162/coli_a_00005.

Full text

Abstract:

Tree-Local Multi-Component Tree-Adjoining Grammar (TL-MCTAG) is an appealing formalism for natural language representation because it arguably allows the encapsulation of the appropriate domain of locality within its elementary structures. Its multicomponent structure allows modeling of lexical items that may ultimately have elements far apart in a sentence, such as quantifiers and wh-words. When used as the base formalism for a synchronous grammar, its flexibility allows it to express both the close relationships and the divergent structure necessary to capture the links between the syntax and semantics of a single language or the syntax of two different languages. Its limited expressivity provides constraints on movement and, we posit, may have generated additional popularity based on a misconception about its parsing complexity. Although TL-MCTAG was shown to be equivalent in expressivity to TAG when it was first introduced, the complexity of TL-MCTAG is still not well understood. This article offers a thorough examination of the problem of TL-MCTAG recognition, showing that even highly restricted forms of TL-MCTAG are NP-complete to recognize. However, in spite of the provable difficulty of the recognition problem, we offer several algorithms that can substantially improve processing efficiency. First, we present a parsing algorithm that improves on the baseline parsing method and runs in polynomial time when both the fan-out and rank of the input grammar are bounded. Second, we offer an optimal, efficient algorithm for factorizing a grammar to produce a strongly equivalent TL-MCTAG grammar with the rank of the grammar minimized.

APA, Harvard, Vancouver, ISO, and other styles

44

Zhang, Xun, Yantao Du, Weiwei Sun, and Xiaojun Wan. "Transition-Based Parsing for Deep Dependency Structures." Computational Linguistics 42, no. 3 (September 2016): 353–89. http://dx.doi.org/10.1162/coli_a_00252.

Full text

Abstract:

Derivations under different grammar formalisms allow extraction of various dependency structures. Particularly, bilexical deep dependency structures beyond surface tree representation can be derived from linguistic analysis grounded by CCG, LFG, and HPSG. Traditionally, these dependency structures are obtained as a by-product of grammar-guided parsers. In this article, we study the alternative data-driven, transition-based approach, which has achieved great success for tree parsing, to build general dependency graphs. We integrate existing tree parsing techniques and present two new transition systems that can generate arbitrary directed graphs in an incremental manner. Statistical parsers that are competitive in both accuracy and efficiency can be built upon these transition systems. Furthermore, the heterogeneous design of transition systems yields diversity of the corresponding parsing models and thus greatly benefits parser ensemble. Concerning the disambiguation problem, we introduce two new techniques, namely, transition combination and tree approximation, to improve parsing quality. Transition combination makes every action performed by a parser significantly change configurations. Therefore, more distinct features can be extracted for statistical disambiguation. With the same goal of extracting informative features, tree approximation induces tree backbones from dependency graphs and re-uses tree parsing techniques to produce tree-related features. We conduct experiments on CCG-grounded functor–argument analysis, LFG-grounded grammatical relation analysis, and HPSG-grounded semantic dependency analysis for English and Chinese. Experiments demonstrate that data-driven models with appropriate transition systems can produce high-quality deep dependency analysis, comparable to more complex grammar-driven models. Experiments also indicate the effectiveness of the heterogeneous design of transition systems for parser ensemble, transition combination, as well as tree approximation for statistical disambiguation.

APA, Harvard, Vancouver, ISO, and other styles

45

Dimopoulos, Alexandros C., Christos Pavlatos, and George Papakonstantinou. "Hardware Inexact Grammar Parser." International Journal of Pattern Recognition and Artificial Intelligence 31, no. 11 (April 11, 2017): 1759025. http://dx.doi.org/10.1142/s021800141759025x.

Full text

Abstract:

In this paper, a platform is presented, that given a Stochastic Context-Free Grammar (SCFG), automatically outputs the description of a parser in synthesizable Hardware Description Language (HDL) which can be downloaded in an FPGA (Field Programmable Gate Arrays) board. Although the proposed methodology can be used for various inexact models, the probabilistic model is analyzed in detail and the extension to other inexact schemes is described. Context-Free Grammars (CFG) are augmented with attributes which represent the probability values. Initially, a methodology is proposed based on the fact that the probabilities can be evaluated concurrently with the parsing during the parse table construction by extending the fundamental parsing operation proposed by Chiang & Fu. Using this extended operation, an efficient architecture is presented based on Earley’s parallel algorithm, which given an input string, generates the parse table while evaluating concurrently the probabilities of the generated dotted grammar rules in the table. Based on this architecture, a platform has been implemented that automatically generates the hardware design of the parser given a SCFG. The platform is suitable for embedded systems applications where a natural language interface is required or in pattern recognition tasks. The proposed hardware platform has been tested for various SCFGs and was compared with previously presented hardware parser for SCFGs based on Earley’s parallel algorithm. The hardware generated by the proposed platform is much less complicated than the one of comparison and succeeds a speed-up of one order of magnitude.

APA, Harvard, Vancouver, ISO, and other styles

46

Man, Haixia, Manyi Wan, Yunbao Shi, and Peng Chen. "Parsing Chinese with Combinatory Categorial Grammar: A Linguistic and Computational Study." Complexity 2022 (September 30, 2022): 1–13. http://dx.doi.org/10.1155/2022/4057360.

Full text

Abstract:

Parsing Chinese language with CCG is very difficult because the architecture and assumptions of CCG do not fit well with facts from Chinese. Based on the concept of “realization” proposed by Zhu Dexi (1920–1992), this study sheds light on the discrepancy between CCG and Chinese syntax and puts forward a refined schema for Chinese compositionality. The discussion is supported by the data of Chinese CCGbank (CASS). Furthermore, by activating a function-based category setting and a noun/verb disambiguating tagging mechanism, we develop a rule-based mini-Chinese CCG parser without deep learning. The new NVN parser surpasses existing Chinese CCG parser C&C in parsing effect (LF 85.9 vs. LF 74.6) on a partial PCTB 6.0 test set of 500 sentences.

APA, Harvard, Vancouver, ISO, and other styles

47

Dong, Li, Furu Wei, Shujie Liu, Ming Zhou, and Ke Xu. "A Statistical Parsing Framework for Sentiment Classification." Computational Linguistics 41, no. 2 (June 2015): 293–336. http://dx.doi.org/10.1162/coli_a_00221.

Full text

Abstract:

We present a statistical parsing framework for sentence-level sentiment classification in this article. Unlike previous works that use syntactic parsing results for sentiment analysis, we develop a statistical parser to directly analyze the sentiment structure of a sentence. We show that complicated phenomena in sentiment analysis (e.g., negation, intensification, and contrast) can be handled the same way as simple and straightforward sentiment expressions in a unified and probabilistic way. We formulate the sentiment grammar upon Context-Free Grammars (CFGs), and provide a formal description of the sentiment parsing framework. We develop the parsing model to obtain possible sentiment parse trees for a sentence, from which the polarity model is proposed to derive the sentiment strength and polarity, and the ranking model is dedicated to selecting the best sentiment tree. We train the parser directly from examples of sentences annotated only with sentiment polarity labels but without any syntactic annotations or polarity annotations of constituents within sentences. Therefore we can obtain training data easily. In particular, we train a sentiment parser, s.parser, from a large amount of review sentences with users' ratings as rough sentiment polarity labels. Extensive experiments on existing benchmark data sets show significant improvements over baseline sentiment classification approaches.

APA, Harvard, Vancouver, ISO, and other styles

48

Johnstone, Adrian, Elizabeth Scott, and Giorgios Economopoulos. "The Grammar Tool Box: A Case Study Comparing GLR Parsing Algorithms." Electronic Notes in Theoretical Computer Science 110 (December 2004): 97–113. http://dx.doi.org/10.1016/j.entcs.2004.06.008.

Full text

APA, Harvard, Vancouver, ISO, and other styles

49

Dol, Sunita M. "Use of FOSS for Teaching the Parser Types to Improve Problem Solving Ability A Case Study on Analysis of Gender based Discrimination in Education." Journal of Engineering Education Transformations 36, S2 (January 1, 2023): 38–47. http://dx.doi.org/10.16920/jeet/2023/v36is2/23006.

Full text

Abstract:

Compiler Design is one of the core courses of Computer Science and Engineering. Syntax Analyzer or Parser is important phase in designing the compiler. So while designing this phase of the compiler, students must have thorough knowledge about the types of parser such as LL(1), SLR, Canonical LR and LALR. In the parser phase, the parsing table is built for given Context Free Grammar (CFG). While implementing this parsing phase in laboratory session, two Free Open Source Software (FOSS) - JFLAP and Parsing Emulator, are considered to explain the types of parser and building the parsing table for the CFG using these parser types. JFLAP is software for experimenting with formal languages topics including nondeterministic finite automata, nondeterministic pushdown automata, multi-tape Turing machines, several types of grammars, parsing, and Lsystems. So this tool is considered for parsing phase of Compiler. JFLAP tool is used to explain the steps to be followed to solve the given problem using the parsing technique. Parsing simulator is a software which implements the parsing table for the Context Free Grammars in tool. This simulator is used to generate parsing table (LL1, SLR, LR, and LALR). Parsing Emulator tool is used for practicing the problem statement given in the tool. In current study, use of FOSS such as JFLAP and Parsing Emulator is considered for teaching parser types to improve problem solving ability. The Learning Objectives (LOs) of this study are: To build the parsing table for given CFG using LL(1) and SLR parser (LO1) and to parse the given string using LL(1) and SLR parser (LO2). The research questions for this study are – whether the use of FOSS improves the problem solving ability of the students? and whether gender bias is there in education? Two groups post-test method is considered to check the effectiveness of this use of FOSS in learning the parser types. Also the students’ perception about this method is also considered. The result shows that the students’ problem solving ability of experimental group is improved as compared to the control group irrespective of gender. Keywords- FOSS (Free Open Source Software) JFLAP, Parsing Emulator, Bloom’s Taxonomy, Post-test, t-Test.

APA, Harvard, Vancouver, ISO, and other styles

50

Demberg, Vera, Frank Keller, and Alexander Koller. "Incremental, Predictive Parsing with Psycholinguistically Motivated Tree-Adjoining Grammar." Computational Linguistics 39, no. 4 (December 2013): 1025–66. http://dx.doi.org/10.1162/coli_a_00160.

Full text

Abstract:

Psycholinguistic research shows that key properties of the human sentence processor are incrementality, connectedness (partial structures contain no unattached nodes), and prediction (upcoming syntactic structure is anticipated). There is currently no broad-coverage parsing model with these properties, however. In this article, we present the first broad-coverage probabilistic parser for PLTAG, a variant of TAG that supports all three requirements. We train our parser on a TAG-transformed version of the Penn Treebank and show that it achieves performance comparable to existing TAG parsers that are incremental but not predictive. We also use our PLTAG model to predict human reading times, demonstrating a better fit on the Dundee eye-tracking corpus than a standard surprisal model.

APA, Harvard, Vancouver, ISO, and other styles

We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!