Augmented grammar

Part 1 of ebook "Compiler design in C" presents the following content: basic concepts; representing computer languages; a recursive-descent expression compiler; input and lexical analysis; context-free grammars; top-down parsing; bottom-up parsing; sentences, phrases, and context-free grammars; ambiguous grammars; augmented grammars and table-driven parsers;...

462p dieptieuung 14-07-2023 9 5   Download

Lecture Compiler construction: Lesson 24 - Sohail Aslam. The main topics covered in this chapter include: LR(1) items, building LR(1) tables, canonical collection, the closure procedure, simplify the task of building this initial state, the construction requires that the grammar have a unique goal symbol,...

28p youzhangjing_1909 28-04-2022 11 1   Download

Lecture Compiler construction: Lesson 26 - Sohail Aslam. The main topics covered in this chapter include: finite automaton of items, construction of collection of canonical sets of LR(1) items, sets of LR(1) items and augmented grammar, NFA of LR(0) items, LR table construction,...

35p youzhangjing_1909 28-04-2022 8 1   Download

Attribute grammars are an elegant formalization of the augmented context-free grammars characteristic of most current natural language systems. This paper presents an extension of Earley's algorithm to Knuth's attribute grammars, considering the case of S-attributed grammars. For this case, we study the conditions on the underlying base grammar under which the extended algorithm may be guaranteed to terminate. Finite partitioning of attribute domains is proposed to guarantee the termination of the algorithm, without the need for any restrictions on the context-free base. ...

4p buncha_1 08-05-2013 41 2   Download

Within unification-based grammar formalisms, providing a treatment of cross-categorial coordination is problematic, and most current solutions either over-generate or under-generate. In this paper we consider an approach to coordination involving "composite" feature structures, which describe coordinate phrases, and present the augmentation to the logic of feature structures required to admit such feature structures.

6p buncha_1 08-05-2013 39 2   Download

In this paper we present an efficient context-free (CF) bottom-up, non deterministic parser. It is an extension of the ICA (Immediate Constituent Analysis) parser proposed by Grishman (1976), and its major improvements are described. It has been designed to run Augmented Phrase-Structure Grammars (APSG) and performs semantic interpretation in parallel with syntactic analysis.

7p buncha_1 08-05-2013 41 1   Download

This paper describes some operational aspects of a language comprehension model which unifies the linguistic theory and the semantic theory in respect to operations. The computational model, called Augmented Dependency Grammar (ADG), formulates not only the linguistic dependency structure of sentences but also the semantic dependency structure using the extended deep case grammar and fleld-oriented fact-knowledge based inferences. Fact knowledge base and ADG model clarify the qualitative difference between what we call semantics and logical meaning. ...

7p buncha_1 08-05-2013 41 2   Download

This paper reports a completed stage of ongoing research at the University oF York. Landsbergen's advocacy of analytical inverses ~or compositional suntax rules encourages the application of Defini t e C l a u s e Grammar t e c h n i q u e s to the const~uction of a parser r e t u r n i n g Montague analysis trees. A parser MDCg i s presented which implements an augmented Friedman Warren algorithm permitting post referencing, and interfaces with a l a n g u a g e oF i n t e n...

10p buncha_1 08-05-2013 41 1   Download

Island parsing is a powerful technique for parsing with Augmented ~ a n s i t i o n Networks (ATNs) which was developed and successfully applied in the HWIM speech understanding project. The HWIM application grammar did not, however, exploit Woods' original full ATN specification. This paper describes an island parsing interpreter based on HWIM, but containing substantial and important extensions to enable it to interpret any grammar which conforms to that full specification of 1970.

5p buncha_1 08-05-2013 46 2   Download

This paper shows that a class of Combinatory Categorial Grammars (CCGs) augmented with a linguistically-motivated form of type raising involving variables is weakly equivalent to the standard CCGs not involving variables. The proof is based on the idea that any instance of such a grammar can be simulated by a standard CCG.

3p bunthai_1 06-05-2013 39 2   Download

A new approach to bottom-up parsing that extends Augmented Context-Free Grammar to a Process Grammar is formally presented. A Process Grammar (PG) defines a set of rules suitedfor bottom-up parsing and conceived as processes that are applied by a P G Processor. The matching phase is a crucial step for process application, and a parsing structure for efficient matching is also presented. The PG Processor is composed of a process scheduler that allows immediate constituent analysis of structures, and behaves in a non-deterministic fashion. ...

8p bungio_1 03-05-2013 62 2   Download

Parsing with categorial grammars often leads to problems such as proliferating lexical ambiguity, spurious parses and overgeneration. This paper presents a parser for French developed on an unification based categorial grammar (FG) which avoids these problem s. This parser is a bottom-up c hart parser augmented with a heuristic eliminating spurious parses. The unicity and completeness of parsing are proved.

8p bungio_1 03-05-2013 44 1   Download

In this paper, we show that one benefit of FUG, the ability to state global conslralnts on choice separately from syntactic rules, is difficultin generation systems based on augmented context free grammars (e.g., Def'mite Clause Cn'anmm~). They require that such constraints be expressed locally as part of syntactic rules and therefore,duplicated in the grammar. Finally, we discuss a reimplementation of l U g that achieves the similar levels of efficiency as Rubinoff's adaptation of M U M B L E , a detcrministc language generator. ...

7p bungio_1 03-05-2013 44 2   Download

Steedman (1985, 1987) and others have proposed that Categorial Grammar, a theory of syntax in which grammatical categories are viewed as functions, be augmented with operators such as functional composition and type raising in order to analyze • noncanonical" syntactic constructions such as wh- extraction and node raising. A consequence of these augmentations is an explosion of semantically equivalent derivations admitted by the grammar. The present work proposes a method for circumventing this spurious ambiguity problem.

8p bungio_1 03-05-2013 46 1   Download

Topics to be considered include the components of a natural language processing system; syntax analysis (including context-free grammars, augmented context-free grammars, grammatical constraints, and sources of syntactic ambiguity); semantic analysis (including meaning representation, semantic constraints, quantifier analysis); and discourse analysis (identifying implicit information, establishing text coherence, frames, and scripts). Examples will be drawn from various application areas, including database interface and text analysis.

1p bungio_1 03-05-2013 55 2   Download

A correct structural analysis of a discourse is a prerequisite for understanding it. This paper sketches the outline of a discourse grammar which acknowledges several different levels of structure. This gram~nar, the "Dynamic Discourse Model", uses an Augmented Transition Network parsing mechanism to build a representation of the semantics of a discourse in a stepwise fashion, from left to right, on the basis of the semantic representations of the individual clauses which constitute the discourse. ...

7p bungio_1 03-05-2013 43 3   Download

This paper presents a parser of an inflectional free word order language, namely Finnish. Two-way finite automata are used to specify a functional dependency grammar and to actually parse Finnish sentences. Each automaton gives a functional description of a dependency structure within a constituent. Dynamic local control of the parser is realized by augmenting the automata with simple operations to make the automata, associated with the words of an input sentence, activate one another.

4p bungio_1 03-05-2013 36 2   Download

The design, implementation, and use of grammar forma]isms for natural language have constituted a major branch of coml)utational linguistics throughout its development. By viewing grammar formalisms as just a special ease of computer languages, we can take advantage of the machinery of denotational semantics to provide a precise specification of their meaning.

7p bungio_1 03-05-2013 52 2   Download

A description will be given of a procedure to asslgn the most likely probabilitles to each of the rules of a given context-free grammar. The grammar developed by S. Kuno at Harvard University was picked as the basis and was successfully augmented with rule probabilities. A brief exposition of the method with some preliminary results, w h e n u s e d as a device for disamblguatingparsing English texts picked from natural corpus, will be given.

4p bungio_1 03-05-2013 38 3   Download

Research on the text generation task has led to creation of a large systemic grammar of English, Nigel, which is embedded in a computer program. The grammar and the systemic framework have been extended by addition of a semantic stratum. The grammar generates sentences and other units under several kinds of experimental control. This paper describes augmentations of various precedents in the systemic framework. The emphasis is on developments which control the text to fulfill a purpose, and on characteristics which make Nigel relatively easy to embed in a larger experimental program. ...

6p bungio_1 03-05-2013 47 2   Download