词条 | Range concatenation grammars |
释义 |
From a theoretical point of view, any language that can be parsed in polynomial time belongs to the subset of RCG called positive range concatenation grammars, and reciprocally.[3] Though intended as a variant on Groenink's Literal movement grammars, RCGs treat the grammatical process more as a proof than as a production. Whereas LMGs produce a terminal string from a start predicate, RCGs aim to reduce a start predicate (which predicates of a terminal string) to the empty string, which constitutes a proof of the terminal strings membership in the language. DescriptionFormal definitionA Positive Range Concatenation Grammar (PRCG) is a tuple , where:
A Negative Range Concatenation Grammar (NRCG) is defined like a PRCG, but with the addition that some predicates occurring in the right-hand side of a clause can have the form . Such predicates are called negative predicates. A Range Concatenation Grammar is a positive or a negative one. Although PRCGs are technically NRCGs, the terms are used to highlight the absence (PRCG) or presence (NRCG) of negative predicates. A range in a word is a couple , with , where is the length of . Two ranges and can be concatenated iff , and we then have: . For a word , with , the dotted notation for ranges is: . Recognition of stringsLike LMGs, RCG clauses have the general schema , where in an RCG, is either the empty string or a string of predicates. The arguments consist of strings of terminal symbols and/or variable symbols, which pattern match against actual argument values like in LMG. Adjacent variables constitute a family of matches against partitions, so that the argument , with two variables, matches the literal string in three different ways: . Predicate terms come in two forms, positive (which produce the empty string on success), and negative (which produce the empty string on failure/if the positive term does not produce the empty string). Negative terms are denoted the same as positive terms, with an overbar, as in . The rewrite semantics for RCGs is rather simple, identical to the corresponding semantics of LMGs. Given a predicate string , where the symbols are terminal strings, if there is a rule in the grammar that the predicate string matches, the predicate string is replaced by , substituting for the matched variables in each . For example, given the rule , where and are variable symbols and and are terminal symbols, the predicate string can be rewritten as , because matches when . Similarly, if there were a rule , could be rewritten as . A proof/recognition of a string is done by showing that produces the empty string. For the individual rewrite steps, when multiple alternative variable matches are possible, any rewrite which could lead the whole proof to succeed is considered. Thus, if there is at least one way to produce the empty string from the initial string , the proof is considered a success, regardless of how many other ways to fail exist. ExampleRCGs are capable of recognizing the non-linear index language as follows: Letting x, y, and z be variable symbols: The proof for {{not a typo|abbabbabb}} is then Or, using the more correct dotted notation for ranges: References1. ^{{cite techreport| author=Boullier, Pierre| title=Proposal for a Natural Language Processing Syntactic Backbone| date=Jan 1998| volume=3342| institution=INRIA Rocquencourt (France)| url=http://hal.archives-ouvertes.fr/docs/00/07/33/47/PDF/RR-3342.pdf}} {{Formal languages and grammars}}2. ^{{cite book| author=Pierre Boullier| chapter=Chinese Numbers, MIX, Scrambling, and Range Concatenation Grammars| title=Proc. EACL| year=1999| pages=53-60| url=http://acl.ldc.upenn.edu/E/E99/E99-1008.pdf| archive-url=https://web.archive.org/web/20030515052025/http://acl.ldc.upenn.edu/E/E99/E99-1008.pdf| dead-url=yes| archive-date=2003-05-15}} 3. ^{{cite book|author=Laura Kallmeyer|title=Parsing Beyond Context-Free Grammars|year=2010|publisher=Springer Science & Business Media|isbn=978-3-642-14846-0|page=37}} citing http://mjn.host.cs.st-andrews.ac.uk/publications/2001d.pdf 2 : Formal languages|Grammar frameworks |
随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识,基本涵盖了大多数领域的百科知识,是一部内容自由、开放的电子版国际百科全书。