Predictive parsing

Lecture Compiler construction: Lesson 19 - Sohail Aslam. The main topics covered in this chapter include: LL(1) table construction, LL(1) parsing table, left factoring, a grammar must be left factored before use for predictive parsing, a graphical explanation,...

31p youzhangjing_1909 28-04-2022 11 2   Download

Lecture Compiler construction: Lesson 14 - Sohail Aslam. The main topics covered in this chapter include: predictive parsing, recursive descent parsing, mutually recursive routin, recursive descent in C++, each non-terminal symbol, non-terminal classes,...

52p youzhangjing_1909 28-04-2022 9 1   Download

Lecture Compiler construction: Lesson 17 - Sohail Aslam. The main topics covered in this chapter include: non-recursive predictive parsing, table-driven parsers, predictive parsing table, the predictive parser uses an explicit stack to keep track of pending non-terminals,...

57p youzhangjing_1909 28-04-2022 19 1   Download

Lecture Compiler construction: Lesson 18 - Sohail Aslam. The main topics covered in this chapter include: computing FIRST sets, terminal symbols, computing FOLLOW sets, the algorithm to construct a predictive parsing table, table construction,...

26p youzhangjing_1909 28-04-2022 8 1   Download

In this paper to encourage students to learn through experimentation, proposing tasks on their own initiative, which involves putting into use all the skills, abilities tools and knowledge needed to successfully solve them.

23p guernsey 28-12-2021 16 0   Download

Characterization of mature protein N-termini by large scale proteomics is challenging. This is especially true for proteins undergoing cleavage of transit peptides when they are targeted to specific organelles, such as mitochondria or chloroplast. Protein neo-N-termini can be located up to 100–150 amino acids downstream from the initiator methionine and are not easily predictable.

13p vioklahoma2711 19-11-2020 8 1   Download

We report grammar inference experiments on partially parsed sentences taken from the Wall Street Journal corpus using the inside-outside algorithm for stochastic context-free grammars. The initial grammar for the inference process makes no ,assumption of the kinds of structures and their distributions. The inferred grammar is evaluated by its predicting power and by comparing the bracketing of held out sentences imposed by the inferred grammar with the partial bracketings of these sentences given in the corpus.

7p buncha_1 08-05-2013 51 3   Download

Natural language systems based on Categorial Unification Grammar (CUG) have mainly employed bottomup parsing algorithms for processing. Conventional prediction techniques to improve the efficiency of the • parsing process, appear to fall short when parsing CUG. Nevertheless, prediction seems necessary when parsing grammars with highly ambiguous lexicons or with noncanonical categorial rules. In this paper we present a lexicalist prediction technique for CUG and show thai this may lead to considerable gains in efficiency for both bottom-up and top-down parsing. ...

6p buncha_1 08-05-2013 51 1   Download

In this paper a bidirectional parser for Lexicalized Tree Adjoining Grammars will be presented. The algorithm takes advantage of a peculiar characteristic of Lexicalized TAGs, i.e. that each elementary tree is associated with a lexical item, called its anchor. The algorithm employs a mixed strategy: it works bottom-up from the lexical anchors and then expands (partial) analyses making top-down predictions.

6p buncha_1 08-05-2013 50 2   Download

This paper assesses two new approaches to deterministic parsing with respect to the analysis of unbounded dependencies (UDs). UDs in English are highly locally (and often globally) ambiguous. Several researchers have argued that the difficulty of UDs undermines the programme of deterministic parsing. However, their conclusion is based on critiques of various versions of the Marcus parser which represents only one of many possible approaches to deterministic parsing.

7p buncha_1 08-05-2013 31 1   Download

The paper presents a language model that develops syntactic structure and uses it to extract meaningful information from the word history, thus enabling the use of long distance dependencies. The model assigns probability to every joint sequence of words-binary-parse-structure with headword annotation. The model, its probabilistic parametrization, and a set of experiments meant to evaluate its predictive power are presented.

3p bunthai_1 06-05-2013 34 1   Download

We describe several tabular algorithms for Tree Adjoining G r a m m a r parsing, creating a continuum from simple pure bottom-up algorithms to complex predictive algorithms and showing what transformations must be applied to each one in order to obtain the next one in the continuum.

8p bunthai_1 06-05-2013 46 4   Download

Myanmar language and script are unique and complex. Up to our knowledge, considerable amount of work has not yet been done in describing Myanmar script using formal language theory. This paper presents manually constructed context free grammar (CFG) with “111” productions to describe the Myanmar Syllable Structure. We make our CFG in conformity with the properties of LL(1) grammar so that we can apply conventional parsing technique called predictive top-down parsing to identify Myanmar syllables. We present Myanmar syllable structure according to orthographic rules. ...

6p bunthai_1 06-05-2013 59 2   Download

We present a web service for natural language parsing, prediction, generation, and translation using grammars in Portable Grammar Format (PGF), the target format of the Grammatical Framework (GF) grammar compiler. The web service implementation is open source, works with any PGF grammar, and with any web server that supports FastCGI. The service exposes a simple interface which makes it possible to use it for interactive natural language web applications. We describe the functionality and interface of the web service, and demonstrate several applications built on top of it. ...

4p bunthai_1 06-05-2013 32 2   Download

In this paper, we present an integrated model of the two central tasks of dialog management: interpreting user actions and generating system actions. We model the interpretation task as a classication problem and the generation task as a prediction problem. These two tasks are interleaved in an incremental parsing-based dialog model. We compare three alternative parsing methods for this dialog model using a corpus of human-human spoken dialog from a catalog ordering domain that has been annotated for dialog acts and task/subtask information.

9p bunthai_1 06-05-2013 40 2   Download

Parallel Multiple Context-Free Grammar (PMCFG) is an extension of context-free grammar for which the recognition problem is still solvable in polynomial time. We describe a new parsing algorithm that has the advantage to be incremental and to support PMCFG directly rather than the weaker MCFG formalism. The algorithm is also top-down which allows it to be used for grammar based word prediction.

8p bunthai_1 06-05-2013 34 2   Download

The paper demonstrates that exponential complexities with respect to grammar size and input length have little impact on the performance of three unification-based parsing algorithms, using a wide-coverage grammar. The results imply that the study and optimisation of unification-based parsing must rely on empirical data until complexity theory can more accurately predict the practical behaviour of such parserQ. 1.

8p bunmoc_1 20-04-2013 54 1   Download

In this paper we present a new parsing model of linguistic and computational interest. Linguistically, the relation between the paxsez and the theory of grammar adopted (Government and Binding (GB) theory as presented in Chomsky(1981, 1986a,b) is clearly specified. Computationally, this model adopts a mixed parsing procedure, by using left corner prediction in a modified LR parser.

3p bunmoc_1 20-04-2013 38 1   Download

Consideration of when Right Association works and when it fails lead to a restatement of this parsing principle in terms of the notion of heaviness. A computational investigation of a syntactically annotated corpus provides evidence for this proposal and suggest circumstances when RA is likely to make correct attachment predictions.

3p bunmoc_1 20-04-2013 40 1   Download

be used for efficiency by providing a best-first search heuristic to order the parsing agenda. This paper proposes an agenda-based probabilistic chart parsing algorithm which is both robust and efficient. The algorithm, 7)icky 1, is considered robust because it will potentially generate all constituents produced by a pure bottom-up parser and rank these constituents by likelihood. The efficiency of the algorithm is achieved through a technique called probabilistic prediction, which helps the algorithm avoid worst-case behavior. ...

8p bunmoc_1 20-04-2013 36 2   Download