Parsing beyond context-free grammars by Laura Kallmeyer

By Laura Kallmeyer

Given that context-free grammars (CFG) can't correctly describe common languages, grammar formalisms past CFG which are nonetheless computationally tractable are of vital curiosity for computational linguists. This publication offers an in depth evaluation of the formal language panorama among CFG and PTIME, relocating from Tree adjacent Grammars to a number of Context-Free Grammars after which to variety Concatenation Grammars whereas explaining to be had parsing options for those formalisms. even if familiarity with the elemental notions of parsing and formal languages is beneficial whilst examining this booklet, it's not a strict requirement. The presentation is supported with many illustrations and examples with regards to the several formalisms and algorithms, and bankruptcy summaries, difficulties and recommendations. The ebook can be worthy for college kids and researchers in computational linguistics and in formal language theory.

Show description

Read Online or Download Parsing beyond context-free grammars PDF

Best ai & machine learning books

Artificial Intelligence Through Prolog

Synthetic Intelligence via Prolog ebook

Language, Cohesion and Form (Studies in Natural Language Processing)

As a pioneer in computational linguistics, operating within the earliest days of language processing via laptop, Margaret Masterman believed that which means, now not grammar, used to be the foremost to figuring out languages, and that machines may make certain the that means of sentences. This quantity brings jointly Masterman's groundbreaking papers for the 1st time, demonstrating the significance of her paintings within the philosophy of technology and the character of iconic languages.

Handbook of Natural Language Processing

This learn explores the layout and alertness of traditional language text-based processing platforms, in line with generative linguistics, empirical copus research, and synthetic neural networks. It emphasizes the sensible instruments to deal with the chosen method

Additional resources for Parsing beyond context-free grammars

Example text

S2 , βa [. ] S3 , βb [ βb , 2 . ] → S2 , βb [. ] Fig. 13. 2 Grammar Formalisms Beyond CFG 33 Productions of the Generalized CFG (start symbol is S): S → f1 (A, B, C) A → f2 (A) B → f3 (B) C → f4 (C) A → f5 () B → f5 () C → f5 () Strings φ(t) yielded by the terms t: φ(f5 ()) := ε, ε , φ(f2 (t)) := aw1 , aw2 where w1 , w2 = φ(t), φ(f3 (t)) := bw1 , bw2 where w1 , w2 = φ(t), φ(f4 (t)) := cw1 , cw2 where w1 , w2 = φ(t), φ(f1 (t1 , t2 , t3 )) := w1 u1 v1 w2 u2 v2 where w1 , w2 = φ(t1 ), u1 , u2 = φ(t2 ), v1 , v2 = φ(t3 ) Fig.

1. Extending the height of the trees permitted leads to Tree Substitution Grammars: 2 A CFG is in Greibach Normal Form if each production is of the form A → a x with A ∈ N, a ∈ T, x ∈ (N ∪ T )∗ . 4 (Tree Substitution Grammar). A Tree Substitution Grammar (TSG) consists of a quadruple T, N, I, S such that • T and N are disjoint alphabets, the terminals and non-terminals, • I is a finite set of syntactic trees, and • S ∈ N is the start symbol. We call the syntactic trees in I the elementary trees.

S2 , βa [. ] S3 , βa [ βb , 2 . ] → S2 , βb [. ] S, α → S1 , βb [ α, 0 ] S1 , βb [. ] → b S2 , βb [. ] S2 , βb [. ] → S3 , βb [. ]b S2 , βa [. ] → S1 , βb [ βa , 2 . ] S2 , βb [. ] → S1 , βb [ βb , 2 . ] S3 , βb [ α, 0 . ] → S, α [. ] S3 , βb [ βa , 2 . ] → S2 , βa [. ] S3 , βb [ βb , 2 . ] → S2 , βb [. ] Fig. 13. 2 Grammar Formalisms Beyond CFG 33 Productions of the Generalized CFG (start symbol is S): S → f1 (A, B, C) A → f2 (A) B → f3 (B) C → f4 (C) A → f5 () B → f5 () C → f5 () Strings φ(t) yielded by the terms t: φ(f5 ()) := ε, ε , φ(f2 (t)) := aw1 , aw2 where w1 , w2 = φ(t), φ(f3 (t)) := bw1 , bw2 where w1 , w2 = φ(t), φ(f4 (t)) := cw1 , cw2 where w1 , w2 = φ(t), φ(f1 (t1 , t2 , t3 )) := w1 u1 v1 w2 u2 v2 where w1 , w2 = φ(t1 ), u1 , u2 = φ(t2 ), v1 , v2 = φ(t3 ) Fig.

Download PDF sample

Rated 4.38 of 5 – based on 50 votes